CODEWITHSUNDEEP
lambdaschemeracket
Hien
Hien

Reputation: 101

Understanding Lambda in Scheme

I'm studying for a test, and looking at some of the old tests we've been given, there's a lot of trick questions where you're given a confusing looking scheme code featuring lambda and you need to state what it outputs. Seems simple enough if you understand lambda, but after reading a bunch of scheme tutorials/lessons, I still can't seem to crack these questions. Here are some examples:

(define y 10)

((lambda (x y)
   (x (x (x y y) y) y))
 (lambda (x y)
   (+ x y))
 7)

outputs 28.

(define (f x y) (* 5 (+ x y)))
((lambda (y x z)
   (f y (x y z)))
 10
 *
 3)

outputs 200.

Can someone walk me through either one or both of these examples, and explain HOW we get those answers? I've been racking my brains trying to understand this. I've been dissecting these problems on Racket to see if I can get a better understanding, but no luck. I went and created an account just to ask this.

Upvotes: 1

Views: 1468

Answers (3)

Mulan
Mulan

Reputation: 135227

If you're having trouble rewrite the lambdas as defines

;; original
(define y 10)

((lambda (x y)
   (x (x (x y y) y) y))
 (lambda (x y)
   (+ x y))
 7)

;; could be rewritten with defines as
(define y 10)

(define f
  (lambda (x y)
   (x (x (x y y) y) y))

(define g
  (lambda (x y)
     (+ x y))

(f g 7)

Using substitution in the rewrite, it's quite simple to follow the code

;; g and 7 are applied to f   
(f g 7)
(g (g (g 7 7) 7) 7)

;; 7 and 7 are applied to g
(+ 7 7)
14

;; which gives us
(g (g 14 7) 7)

;; 14 and 7 are applied to g
(+ 14 7)
21

;; which gives us
(g 21 7)

;; lastly, 21 and 7 are applied to g
(+ 21 7)
28

You can use this identical approach to evaluating the other lambda expression

Another approach would be to notice that

(lambda (x y) (+ x y))

is the same as

+

Which means you can rewrite the entire problem as

((lambda (x y)
   (x (x (x y y) y) y))
 +
 7)

Then using substitution

(+ (+ (+ 7 7) 7) 7)
(+ (+ 14 7) 7)
(+ 21 7)
28

Warning: the (define y 10) is a red herring. That value will not be used as each lambda uses a bound y variable and the outer y (10) is never used.

Upvotes: 1

uselpa
uselpa

Reputation: 18917

For the first example:

The procedure (lambda (x y) (x (x (x y y) y) y)) is passed 2 parameters x and y: x will be bound to (lambda (x y) (+ x y)), and y will be bound to 7.

Start by substituting y by 7 yields the following (I've taken the liberty to change x to f because I find it shows better that the parameter is a function/procedure):

((lambda (f) (f (f (f 7 7) 7) 7))
 (lambda (x y) (+ x y)))

Now, the inner (f 7 7) evaluates to (+ 7 7) hence 14. Continuing the substitution this gives (f (f 14 7) 7)) then (f 21 7) and finally 28.

Upvotes: 1

Haris
Haris

Reputation: 12270

The second one.

(define (f x y) (* 5 (+ x y)))
((lambda (y x z)
   (f y (x y z)))
 10
 *
 3)

First lambda is solved. In that procedure is (y x z) call is defined by (f y (x y z)). And the call is (10 * 3).

So (f y (x y z)) becomes (f 10 (* 10 3)). Solving the inside () first, we get (f 10 30).

Then applying procedure f we get, (* 5 (+ 10 30)), solving the inside (), we get (* 5 40), and then finally solving the outer (), we get 200.

Upvotes: 0

Related Questions