Boolean operators tail-call optimized?

Question

While learning Racket and getting into programming in general I was defining ormap in two different ways:

(define (or-map proc lst)
  (cond
    [(null? lst) #false]
    [(proc (car lst)) #true]
    [else (or-map proc (cdr lst))]))


(define (or-map proc lst)
  (if (null? lst)
      #false
      (or (proc (car lst)) ; <-- this one
          (or-map proc (cdr lst)))))

The following questions came to mind:

Is the second one tail-call optimized? I was not sure if the commented line gets thrown away (or the (or ...) stacks up it's arguments), because if it's #true the function call ends and if it's #false it should be irrelevant for further evaluation of the (or ...) statement.

So I ran the following test and looked at the task manager for memory usage:

(define (test)
  (or #f
      (test)))

(test)

The memory stayed the same. So I think I can conclude (or ...*) gets tail-call optimized? I assumed that stays true for (and ...*) and other boolean operators, but as I changed the or in (test) to nor the memory filled up.

So all in all, do I

• have some mistakes in my conclusions thus far?
• what's going on with the nor-test?
• rightfully assume both of my definitions of or-map are equivalent performance wise, or is one preferable over the other?
• (is my use of the task manager in this case even legitamate and is the phenomenon I witness there when the memory fills up stackoverflow or a implication thereof?)

Answer 1

Given that your username is Tracer, you may find it amusing that you can use racket/trace to examine this. :)

First an example of functions you would expect to use tail elimination and not:

#lang racket

(define (tail-call xs [results '()])
  (match xs
    [(list) results]
    [(cons x xs) (tail-call xs (cons x results))]))

(define (no-tail-call xs)
  (match xs
    [(list) (list)]
    [(cons x xs) (cons x (no-tail-call xs))]))

We can trace them and see this reflected in the call depth:

(require racket/trace)
(trace tail-call no-tail-call)

(tail-call '(1 2 3 4 5))
;; >(tail-call '(1 2 3 4 5))
;; >(tail-call '(2 3 4 5) '(1))
;; >(tail-call '(3 4 5) '(2 1))
;; >(tail-call '(4 5) '(3 2 1))
;; >(tail-call '(5) '(4 3 2 1))
;; >(tail-call '() '(5 4 3 2 1))
;; <'(5 4 3 2 1)
;; '(5 4 3 2 1)

(no-tail-call '(1 2 3 4 5))
;; >(no-tail-call '(1 2 3 4 5))
;; > (no-tail-call '(2 3 4 5))
;; > >(no-tail-call '(3 4 5))
;; > > (no-tail-call '(4 5))
;; > > >(no-tail-call '(5))
;; > > > (no-tail-call '())
;; < < < '()
;; < < <'(5)
;; < < '(4 5)
;; < <'(3 4 5)
;; < '(2 3 4 5)
;; <'(1 2 3 4 5)
;; '(1 2 3 4 5)

Next let's do that for your two definitions of or-map. We see the same, flat shape for both:

(define (or-map/v1 proc lst)
  (cond
    [(null? lst) #false]
    [(proc (car lst)) #true]
    [else (or-map/v1 proc (cdr lst))]))

(define (or-map/v2 proc lst)
  (if (null? lst)
      #false
      (or (proc (car lst)) ; <-- this one
          (or-map/v2 proc (cdr lst)))))

(trace or-map/v1 or-map/v2)

(or-map/v1 even? '(1 1 1 2))
;; >(or-map/v1 #<procedure:even?> '(1 1 1 2))
;; >(or-map/v1 #<procedure:even?> '(1 1 2))
;; >(or-map/v1 #<procedure:even?> '(1 2))
;; >(or-map/v1 #<procedure:even?> '(2))
;; <#t
;; #t

(or-map/v2 even? '(1 1 1 2))
;; >(or-map/v2 #<procedure:even?> '(1 1 1 2))
;; >(or-map/v2 #<procedure:even?> '(1 1 2))
;; >(or-map/v2 #<procedure:even?> '(1 2))
;; >(or-map/v2 #<procedure:even?> '(2))
;; <#t
;; #t