Search code examples
lambdaracketexpression-evaluation

Evaluation order of lambda functions in Racket

Currently working through the Racket Guide at https://docs.racket-lang.org and reading up on lambda functions. The explanation of their usefulness is lucid, but I am not sure I quite grasp the order in which such functions are evaluated. Consider the following example from the Guide:

(define (twice f v)
  (f (f v)))

(define (make-add-suffix s2)
  (lambda (s) (string-append s s2)))

(twice (make-add-suffix "!") "hello")

The function call to twice here is said to evaluate to "hello!!". Here is my guess at what the evaluation process looks like:

(twice (make-add-suffix "!") "hello")

((make-add-suffix "!") ((make-add-suffix "!") "hello")

((make-add-suffix "!") (string-append "hello" "!"))

(string-append (string-append "hello" "!") "!")

(string-append "hello!" "!")

"hello!!"

Is this an accurate assessment, or have I missed something?

Solution

  • Slogan: The outermost and left-most nested expression should be evaluated first.

    (twice (make-add-suffix "!") "hello")

; (define (f x) ...) is short for (define f (lambda (x) ...)) so,
; = { substitute twice with  (lambda (f v) (f (f v)))}

((lambda (f v) (f (f v))) (make-add-suffix "!") "hello")

; = { substition of make-add-suffix with (lambda (s2) (lambda (s) (string-append s s2)))}

((lambda (f v) (f (f v)))
 ((lambda (s2) (lambda (s) (string-append s s2))) "!")
 "hello")

    Terminology before we move on:

    • Beta Reduction: ((lambda (x-1 ... x-n) f-body) v-1 ... v-n) == f-body with all occurrences of x-1 ... x-n replaced with v-1 ... v-n, respectively.

    • Call by Value: The arguments of a function call are evaluated before beta reduction.

    ; = { beta-reduction of ((lambda (s2) (lambda (s) (string-append s s2))) "!") }

((lambda (f v) (f (f v))) (lambda (s) (string-append s "!")) "hello")

; = { beta-reduction of the whole expression }

((lambda (s) (string-append s "!"))
 ((lambda (s) (string-append s "!")) "hello"))

; = { beta-reduction of the expression in the argument position first }

((lambda (s) (string-append s "!")) (string-append "hello" "!"))

; ... and the rest is easy:
((lambda (s) (string-append s "!")) "hello!")
(string-append "hello!" "!")
"hello!!"