inner and outer reduction, same result?

Does inner and outer reduction always create the same value, if not what would cause different ones?

I am talking about Racket, a functional language.

There are I know possibilities where it is more efficient like in Racket but actually causing a different result. I wasn't able to create a case where that happens, but I feel like it should be possible and may be. dangerous not to know.

Example:

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

Solution

I don't know Racket, but in general you can run into trouble if any of your expressions have side effects, such as modifying variables, doing input/output, etc.

Take the following example:

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

Inner reduction:

; 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. the result is 4 and the final value of x is 2.

With outer reduction, you get:

; 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

I.e. the result is 6 and the final value of x is 3.

There's another difference. With inner reduction it's possible that you don't get a result at all:

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

(define (loop)
  (loop))

(my-if #t 42 (loop))

With outer reduction:

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

With inner reduction:

(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'
...

This never terminates.