Булевы операторы хвостового вызова оптимизированы?

Question

Изучая Racket и изучая программирование в целом, я определял ormap двумя различными способами:

(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)))))

На ум пришли следующие вопросы:

Оптимизирован ли второй хвостовой вызов? Я не был уверен, что закомментированная строка отбрасывается (или (или...) складывает свои аргументы), потому что если это #true, то вызов функции завершается, и если это #false, это не имеет значения для дальнейшей оценки (или...) заявление.

Поэтому я запустил следующий тест и посмотрел на диспетчер задач для использования памяти:

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

(test)

Память осталась прежней. Так что я думаю, что могу заключить (или...*) оптимизировать хвостовой вызов? Я предположил, что это верно для (и...*) и других логических операторов, но, когда я изменил или в (тест), ни память не заполнилась.

Так в общем, я

• есть какие-то ошибки в моих выводах до сих пор?
• что происходит с ни-тестом?
• справедливо предположить, что оба моих определения or-map эквивалентны с точки зрения производительности или одно предпочтительнее другого?
• (Является ли мое использование диспетчера задач в этом случае легитимным, и является ли явление, которое я наблюдаю там, когда память заполняет переполнение стека, или следствием этого?)

Answer 1

Учитывая, что ваше имя пользователя Tracerможет показаться забавным то, что вы можете использовать racket/trace изучить это.:)

Сначала приведем пример функций, которые вы ожидаете использовать для исключения хвоста, а не:

#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))]))

Мы можем trace они и видят это в глубине звонка

(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)

Теперь давайте сделаем это для ваших двух определений or-map, Мы видим одинаковую плоскую форму для обоих:

(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

Answer 2

and а также or оцените их последнее выражение в хвостовой позиции. Это гарантируется стандартом Схемы; см., например, http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html.

norс другой стороны, должен отрицать результат or, По определению это означает, что результат or не оценивается в хвостовой позиции, так как он должен быть передан not прежде чем вернуться к звонящему.

Answer 3

Вы спрашиваете:

справедливо предположить, что оба моих определения or-map эквивалентны с точки зрения производительности или одно предпочтительнее другого?

но обратите внимание, что ваша первая функция не эквивалентна второй (не дает того же результата). Вы можете проверить это, если позвоните им с помощью:

(or-map (lambda (x) (member x '(1 2 3))) '(1 2 a))

Причина в том, что в первой функции вы возвращаете #true когда (proc (car lst)) возвращает что-то отличное от #false, но функция должна возвращать значение (proc (car lst)), Таким образом, "правильная" версия (то есть версия, эквивалентная ракетке ormap) только второй.