Understanding result from Scheme code

Question 1

I'm going to explain this with the substitution model. The idea is that you can replace a variable with it's definition and substitute a procedure application with the expression in the body of the procedure and the formal perameters are expanded to it's aguments. Eg.:

(define square (lambda (x) (* x x)))
(square 5)

So we start with (sqrt 5) since it starts the processs (not a definition)

(square 5)               ; ==> subst square 
((lambda (x) (* x x)) 5) ; ==> apply x=5
(* 5 5)                  ; ==> 25

Now let's do the same with your example:

(define f (lambda (g) (lambda (x) (g (+ (g x) (g x)))))) (define e (lambda (x) (* x 3))) (define d (f e)) (d 4)

Or we could just start with d since it's definition is an expression (f e):

(f e) ; subs f ==>
((lambda (g) (lambda (x) (g (+ (g x) (g x))))) e)   ; apply g=e ==>
(lambda (x) (e (+ (e x) (e x))))                    ; subst first e ==>
(lambda (x) ((lambda (x) (* x 3)) (+ (e x) (e x)))) ; apply x=(+ (e x) (e x)) ==>
(lambda (x) (* (+ (e x) (e x)) 3))                  ; subst e+apply x=x ==>
(lambda (x) (* (+ (* x 3) (* x 3)) 3))              ; now this is d

So in reality f and e is now irrelevant since by substitution rules you could have written (define d (lambda (x) (* (+ (* x 3) (* x 3)) 3)) instead. Then we do the (d 4) using it's new definition:

(d 4)                                      ; subst d ==>
((lambda (x) (* (+ (* x 3) (* x 3)) 3)) 4) ; apply x=4 ==>
(* (+ (* 4 3) (* 4 3)) 3)                  ; ==> 72

I've done this manually but you can do it automatically for simple Scheme code in DrRacket by choosing "Intermediate student" as language at the bottom left dropdown menu and press STEP >|. Your code has 13 steps. However, it helps to do it manually a couple of times to get the hang of it and you'll understand better after watching the SICP videoes and you'll be quite good if you finish the questions in the book. Book and videos are free so you only have to pay with your time to ace Scheme.

Question 2

Your program is equivalent to

(let ((f (lambda (g) (lambda (x) (g (+ (g x) (g x)))))))
  (let ((e (lambda (x) (* x 3))))
    (let ((d (f e)))
      (d 4))))

In general, letrec should've been used, not let, but here it makes no difference. letrec allows for a procedure to refer to its own name inside its body, i.e. to be recursive. let does not allow for such references. For example, the lambda expression defining f does not contain any references to f.

Now the evaluation proceeds by trying to find out the value of d, to use it as a function to be called with the value of 4 as an argument. The application (f e) is hence performed. In general, an application ((lambda (x) ...) v) is reduced as (let ((x v)) ...):

(let ((f (lambda (g) (lambda (x) (g (+ (g x) (g x)))))))
  (let ((e (lambda (x) (* x 3))))
    (let ((d (let ((g e))           ; <---
               (lambda (x) (g (+ (g x) (g x)))) )
           ))
      (d 4))))

A closure is returned:

(let ((f (lambda (g) (lambda (x) (g (+ (g x) (g x)))))))
  (let ((e (lambda (x) (* x 3))))
             (let ((g e))
      (let ((d (lambda (x) (g (+ (g x) (g x))))))
        (d 4)))))       ; <---

Now d's value is found to be a procedure, so the application (d 4) is performed:

(let ((f (lambda (g) (lambda (x) (g (+ (g x) (g x)))))))
  (let ((e (lambda (x) (* x 3))))
    (let ((g e))
      (let ((d (lambda (x) (g (+ (g x) (g x))))))
        (let ((x 4))
          (g (+ (g x) (g x))) )))))    ; <---

(let ((f (lambda (g) (lambda (x) (g (+ (g x) (g x)))))))
  (let ((e (lambda (x) (* x 3))))
    (let ((g e))
      (let ((d (lambda (x) (g (+ (g x) (g x))))))
        (let ((x 4))
          (let ((temp1 (+ (g x) (g x))))    ; <---
            (g temp1) ))))))

which is

......
        (let ((x 4))
          (let ((temp2 (g x))               ; <---
                (temp3 (g x)))               
            (let ((temp1 (+ temp2 temp3)))   
               (g temp1) )))))))           

......
        (let ((x 4))
          (let ((temp2 ( (lambda (x1) (* x1 3)) x ))   ; <---
                (temp3 (g x)))               
            (let ((temp1 (+ temp2 temp3)))   
               (g temp1) )))))))             

......
        (let ((x 4))
          (let ((temp2 (let (x1 x) (* x1 3)))     ; <---
                (temp3 (g x)))               
            (let ((temp1 (+ temp2 temp3)))   
               (g temp1) )))))))             

......
        (let ((x 4))
          (let ((temp2 (let (x1 4) (* x1 3)))     ; <---
                (temp3 (g x)))               
            (let ((temp1 (+ temp2 temp3)))   
               (g temp1) )))))))             

......
        (let ((x 4))
          (let ((temp2             (* 4 3))       ; <---
                (temp3 (g x)))               
            (let ((temp1 (+ temp2 temp3)))   
               (g temp1) )))))))

etc. This is not how Scheme actually operates, but close. Finally we arrive at

......
        (let ((x 4))
          (let ((temp2 12) 
                (temp3 12))               
            (let ((temp1 24))   
               (g temp1) )))))))             ; <---

......
            (let ((temp1 24))   
               ( (lambda (x2) (* x2 3)) temp1) )))))     ; <---

......
               (let (x2 24) (* x2 3)) ))))     ; <---

......
               (* 24 3)  ))))     ; <---

......
               72  ))))           ; []

Question 3

In order for

(d 4)

to work, d must be a procedure. Since d was defined using

(define d (f e))

then

(f e)

must return a procedure. The way f has been defined, its return value is indeed a lambda expression.

The return value of

(f e)

is

(lambda (x) (e (+ (e x) (e x))))

If you substitute what e stands for, you get:

(lambda (x) (* (+ (* x 3) (* x 3)) 3))

Thus,

(define d (f e))

can be translated to

(define d (lambda (x) (* (+ (* x 3) (* x 3)) 3)))

Now,

(d 4)

can be translated to

(* (+ (* 4 3) (* 4 3)) 3)

which evaluates to 72.