внутренний и наружный редукция, такой же результат?

Question

Внутреннее и внешнее сокращение всегда создает одно и то же значение, если не то, что может вызвать разные?

Я говорю о Racket, функциональном языке.

Есть я знаю возможности, где это более эффективно, как в ракетке, но на самом деле вызывает другой результат. Я не смог создать случай, когда это произойдет, но я чувствую, что это должно быть возможно и, возможно, опасно не знать.

Пример:

;inner reduction 
    (sqr (* 3 (+ 1 (sqr 2)))) 
     ->(sqr (* 3 (+ 1 (* 2 2))) ;(sqr) 
     ->(sqr (* 3 (+ 1 4)) ;(*) 
     ->(sqr (* 3 5)) ;(+) 
     ->(sqr 15) ;(*) 
     ->(* 15 15) ;(sqr) 
     ->225 ;(*) 

;outer reduction 
    (sqr (* 3 (+ 1 (sqr 2)))) 
     ->(* (* 3 (+ 1 (sqr 2))) (* 3 (+ 1 (sqr 2))) ;(sqr) 
     ->(* (* 3 (+ 1 (* 2 2))) (* 3 (+ 1 (sqr 2))) ;(sqr) 
     ->(* (* 3 (+ 1 4)) (* 3 (+ 1 (sqr 2))) ;(*) 
     ->(* (* 3 5) (* 3 (+ 1 (sqr 2))) ;(+) 
     ->(* 15 (* 3 (+ 1 (sqr 2))) ;(*) 
     ->(* 15 (* 3 (+ 1 (* 2 2))) ;(sqr) 
     ->(* 15 (* 3 (+ 1 4))) ;(*) 
     ->(* 15 (* 3 5)) ;(+) 
     ->(* 15 15) ;(*) 
     ->225 ;(*) 

Answer 1

Я не знаю, рэкет, но в целом вы можете столкнуться с проблемами, если любой из ваших выражений имеют побочные эффекты, такие как изменение переменных, делая ввод/вывод и т.д.

Рассмотрим следующий пример:

(define x 1) 
(sqr (begin (set! x (add1 x)) x)) 

Внутренняя редукция:

; x = 1 
(sqr (begin (set! x (add1 x)) x)) 

; x = 2 
(sqr (begin x)) 

; x = 2 
(sqr (begin 2)) 

; x = 2 
(sqr 2) 

; x = 2 
(* 2 2) 

; x = 2 
4 

I.e. результатом является 4, а окончательное значение x - 2.

С внешним сокращением, вы получите:

; x = 1 
(* (begin (set! x (add1 x)) x) 
    (begin (set! x (add1 x)) x)) 

; x = 2 
(* (begin x) 
    (begin (set! x (add1 x)) x)) 

; x = 2 
(* 2 
    (begin (set! x (add1 x)) x)) 

; x = 3 
(* 2 
    (begin x)) 

; x = 3 
(* 2 
    (begin x)) 

; x = 3 
(* 2 
    3) 

; x = 3 
6 

Т.е. результатом является 6, а окончательное значение x - 3.

---

Есть еще одна разница. С внутренним сокращением вполне возможно, что вы не получите результат на всех:

(define (my-if c t e) 
    (if c t e)) 

(define (loop) 
    (loop)) 

(my-if #t 42 (loop)) 

С внешним сокращением:

(my-if #t 42 (loop)) 
; definition of 'my-if' 
(if #t 42 (loop)) 
; built-in 'if' 
42 

С внутренним сокращением:

(my-if #t 42 (loop)) 
; definition of 'loop' 
(my-if #t 42 (loop)) 
; definition of 'loop' 
(my-if #t 42 (loop)) 
; definition of 'loop' 
(my-if #t 42 (loop)) 
; definition of 'loop' 
... 

Это никогда не заканчивается.