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.

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.

Answer 2

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

Answer 3

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