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).