Section 3.2 solutions

Exercise 3.9

In this exercise, we are asked to show the environment structure when evaluating the two provided procedures for computing factorials.

Recursive solution

The recursive code is given as follows:-

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

The environment structures creating by evaluating (factorial 6) is as follows:-

Environment structure for recursive case

Iterative solution

The iterative code is given as follows:-

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product 
                   counter 
                   max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Environment structure for iterative case

Exercise 3.10

In this exercise, we are tasked with illustrating the environment model for the given make-withdraw procedure as follows:-

(define (make-withdraw initial-amount)
  (let ((balance initial-amount))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance 
                       (- balance amount))
                 balance)
          "Insufficient funds"))))

To understand what happens, let us desugar the let expression:-

(define (make-withdraw initial-amount)
  ((lambda (balance)
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance 
                       (- balance amount))
                 balance)
                 "Insufficient funds")))
    initial-amount))

First, when the initial definition of make-withdraw is created, the following environment is set up:-

Next, calling (define W1 (make-withdraw 100)) establishes the following environment after evaluating the inner lambda:-

After that, calling (W1 50) does the following:-

This sets balance value to 50 based on the definition of W1 and evaluates to 50 similar to the original function. Finally, defining another function W2 similar to W1 ends up with the following:-

As can be seen, both W1 and W2 share the same function code but point to a separate environment. Ultimately, this yields in code very similar to what we have before but has an extra initial-amount defined which could be used to extend the functionality of the code.

Exercise 3.11

In this exercise, we are tasked with showing the environment structure generated by the message passing definition version of make-account as given below:-

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance 
                        amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch m)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "Unknown request: 
                        MAKE-ACCOUNT" 
                       m))))
  dispatch)

With this definition, the following environment is set up by simply storing the definition:-

Next, calling (define acc (make-account 50)) evaluates the function body and produces the following structure. The newly defined acc points to the same location as the inner dispatch function:-

After that, when we call ((acc 'deposit) 40) the inner function evaluates to deposit in environment E1 and subsequently, that gets evaluated:-

Evaluating E2 updates the value of balance prints out the updated balance value of 90. Next, calling ((acc 'withdraw) 60) does something similar:-

Evaluating E3 updates balance and outputs 30.

Finally, calling (define acc2 (make-account 100)) sets up the following:-