What am I doing wrong with this Scheme evaluation?

Question

Evaluate:

((((lambda (x) (lambda (y) (lambda (x) (+ x y)))) 3) 4) 5)

This is what I did:

• evaluate ((((lambda (x) (lambda (y) (lambda (x) (+ x y)))) 3) 4) 5)

  • evaluate 5 -> 5

• evaluate (((lambda (x) (lambda (y) (lambda (x) (+ x y)))) 3) 4)

  • evaluate 4 -> 4

• evaluate ((lambda (x) (lambda (y) (lambda (x) (+ x y)))) 3)

  • evaluate 3 -> 3

• (lambda (x) (lambda (y) (lambda (x) (+ x y)))) -> (lambda (x) (lambda (y) (lambda (x) (+ x y))))

• apply (lambda (x) (lambda (y) (lambda (x) (+ x y)))) to 3

  • substitute 3 -> x in (lambda (y) (lambda (x) (+ x y))

  • (lambda (y) (lambda (x) (+ 3 y))

  • evaluate (lambda (y) (lambda (x) (+ 3 y)) -> (lambda (y) (lambda (x) (+ 3 y))

  • apply (lambda (y) (lambda (x) (+ 3 y)) to 4

  • subsitute 4 -> y in (lambda (y) (lambda (x) (+ 3 y))

  • (lambda (y) (+ 3 4))

  • evaluate (lambda (y) (+ 3 4)) -> (lambda (y) (7))

    • subsitute 5 -> ?

And then I'm stuck.

Answer 1

I suggest you break this down into individual 'defined' procedures.

(define part1 (lambda (y) (lambda (x) (+ x y)))) ; basically an adder
(define part2 (lambda (x) part1))  ; just return part1, x has no effect

Now call (((part2 3) 4) 5) => 9

Answer 2

-substitute 3 -> x in (lambda (y) (lambda (x) (+ x y))
-(lambda (y) (lambda (x) (+ 3 y))

First, this is wrong. You don't substitute 3 for all occurrences of x, only for the free ones. The x you're replacing here is bound by the inner lambda expression and therefore not free.

Second, there's nothing wrong with substituting a value for a variable that's never used, so substituting 5 for y in (+ 3 4) is fine and yields (+ 3 4).

Answer 3

Your first substitution is wrong; the x in (+ x y) is bound by the innermost lambda, not the outermost. This means the result of that substitution is just (lambda (y) (lambda (x) (+ x y))). The 3 is "lost". (Perhaps you should look up the substitution rules and apply them step by step to getter a better grasp of it.)

Regardless of this, to finish you can still apply (lambda (y) (7)) (or (lambda (y) (+ 4 x)) if you fix the above) to 5 to get 7 (or (+ 4 5) which evaluates to 9).