Understanding Scheme function

Question

The following question is given in our Programming language practice exam and I am having a hard time understating how this works. Could someone tell me what the flow of code is? I have run it in racket and know what the answer is. It looks like the first lambda function is taking the other two functions as argument. But then where are the inputs (lambda (x) 2) and (lambda (y) 3) passed to?

(((lambda (x y) (x y)) (lambda (y) (lambda (y x) (x (x y)))) (lambda (x) (lambda (x y) (x (y x))))) (lambda (x) 2) (lambda (y) 3))

The answer to the question is 3.

Marjorymarjy

Answer 1

We humans like to name things. Succinct notation with short names makes it easy to manipulate the code mentally, because so much of our mental abilities are tied into our massively parallel visual recognition system:

(((lambda (x y) (x y))
  (lambda (y) (lambda (y x) (x (x y))))
  (lambda (x) (lambda (x y) (x (y x)))))
 (lambda (x) 2)
 (lambda (y) 3)) =>

((u               where u = (lambda (x y) (x y))
  f                     f = (lambda (y) (lambda (y x) (x (x y))))
  g)                    g = (lambda (x) (lambda (x y) (x (y x))))
 (lambda (x) 2)
 (lambda (y) 3)) =>

((u               where (u x y) = (x y)
  f                     (f y)   = \(y x) -> (x (x y))     ; (*)
  g)                    (g x)   = \(x y) -> (x (y x))
 (lambda (x) 2)
 (lambda (y) 3)) =>

((f               where (f g)   = \(y x) -> (x (x y))
  g)                    (g x)   = \(x y) -> (x (y x))
 (lambda (x) 2)
 (lambda (y) 3)) =>

(h                where h       = \(y x) -> (x (x y))
 p                      p       = \(x) -> 2
 q) =>                  q       = \(y) -> 3

(h                where (h y x) = (x (x y))
 p                      (p x)   = 2
 q) =>                  (q y)   = 3

(q (q p))         where (p x)   = 2
                        (q y)   = 3
    => 

(q 3)             where (q y)   = 3
    => 

3

The (*) definition has all the variables bound in the lambda expression (lambda (y x) (x (x y))) -- both x and y. The argument y in (f y) is thus ignored. It would have been referenced by a free variable y in the lambda expression, but there is none.

Schouten

Thanks for the reply. This is very helpful. I didn't understand it at first after googling a bit and reading what alpha, beta and eta reductions are I was able to understand this. Thanks again :) – Marjorymarjy

@Marjorymarjy You're welcome. You should've said you're unsure about the basic rules, I'd expound a bit on that. – Schouten

Answer 2

This is a job for the algebraic stepper!

Enter this (no #lang line) in the interaction window of DrRacket. In the lower left corner change the language to "Intermediate Student with Lambda". Now click the "Run" button. Finally click the "Stepper" button (the left most button to the left of the run button.

You can now single step through the program (and go back!).

(((lambda (x y) (x y))
  (lambda (y) (lambda (y x) (x (x y))))
  (lambda (x) (lambda (x y) (x (y x)))))
 (lambda (x) 2)
 (lambda (y) 3))

Familist

ok so this is really helpful. thanks! So the first function takes as argument the other two functions and the inputs (lambda (x) 2) and (lambda (y) 3) are passed to them. But what i don't understand is that scheme does not evaluate the function (lambda (x) (lambda (x y) (x (y x)))) and only returns the value 3 from the first one. I guess this is where I was making the mistake when i was dry running the code. I was evaluating the 2nd function as well. So my question now is why does it not evaluate the 2nd function? Thanks again. – Marjorymarjy

@Marjorymarjy (lambda (x) (lambda (x y) (x (y x)))) the one expression in the body of the lambda is a lambda form, thus when you apply it you can expext to get back a procedure that takes two arguments. – Iaverne

Answer 3

But then where are the inputs (lambda (x) 2) and (lambda (y) 3) passed to?

For this, adding println statements can help:

(((lambda (x y)
    (println "In Lxy fn")
    (x y))
  (lambda (y)
    (println "In Ly fn")
    (lambda (y x)
      (println "In Lyxi fn")
      (x (x y))))
  (lambda (x)
    (println "In Lx fn")
    (lambda (x y)
      (println "In Lxyi fn")
      (x (y x)))))
 (lambda (x) 2)
 (lambda (y) 3))

Output:

"In Lxy fn"
"In Ly fn"
"In Lyxi fn"
3

Part of this function is redundant and can be removed without any effect on output. In the following, literally any value can be put instead of the removed part:

(((lambda (x y)
    (println "In Lxy fn")
    (x y))
  (lambda (y)
    (println "In Ly fn")
    (lambda (y x)
      (println "In Lyxi fn")
      (x (x y))))
  ;(lambda (x)
  ;  (println "In Lx fn")
  ;  (lambda (x y)
  ;    (println "In Lxyi fn")
  ;    (x (y x))))
  "any value"
  )
 (lambda (x) 2)
 (lambda (y) 3)) 

In your own format, following produces same output as before:

(((lambda (x y) (x y))
  (lambda (y) (lambda (y x) (x (x y))))
  ;(lambda (x) (lambda (x y) (x (y x))))
  "any value"
  )
 (lambda (x) 2)
 (lambda (y) 3))

Faith

Correct me if i am wrong. According to my understanding, after doing all the reduction the inputs (lambda (x) 2) and (lambda (y) 3) are passed to the fn (lambda (y x) (x (x y)) – Marjorymarjy