Оптимизирован оптимизация булевых операторов?

Question

В процессе обучения ракетки и получать в программирование вообще я определял 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) 

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

Так что в целом, я

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

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#node_sec_11.20.

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

Answer 3

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

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

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

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

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