Feeds:
Posts
Comments

Archive for the ‘Chapter 3’ Category

Exercise 3.9

Let’s start with the recursive factorial:

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

For simplicity, especially since drawing these pictures in OpenOffice is a bit tedious, let’s trace out the evaluation of (factorial 3) instead of (factorial 6). When the procedure factorial is applied to the argument 3 a new environment E1 is created who’s parent environment is the environment in which factorial was defined (the global environment), and in which the formal parameter n is bound to the value 3. Then the body of factorial is evaluated in this new environment, resulting in another application of factorial with 2 as an argument. This creates a new environment E2 in which the formal parameter n is bound to 2. The environment E3 is created in a similar manner, with n bound to 1. Finally the base case of factorial is reached, the computation unwinds and finishes:

Now let’s examine the iterative version of factorial:

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

Again everything starts with the application (factorial 3). The body of factorial is evaluated in an environment E1, where the formal parameter n is bound to 3. This results in the application (fact-iter 1 1 n), which reduces to evaluating the body of the procedure fact-iter in a new environment E2 with the formal parameters product, counter, and max-count bound to 1, 1, and 3 respectively. The process continues with the environments E3, E4, and E5 being created along the way until the computation finally ends:

Read Full Post »

Exercise 3.7

Make-joint can be implemented to return a procedure that takes two arguments – a password password and a message m. It works by checking whether password and new-password match and if they do sends the message to the local account object along with the original password:

(define (make-joint account account-password new-password)
  (lambda (password m)
    (if (eq? password new-password)
        (account account-password m)
        "Incorrect password")))

No changes to make-account are required.




Exercise 3.8

Let f be a procedure with a single local state variable last which stores the value of the argument x that was last passed to f. Initially, if f has not been called, last has the value of 0. When applied, f updates the value of last to that of its argument and returns the old value of last:

(define f
  (let ((last 0))
    (lambda (x) 
      (let ((result last))
        (set! last x)
        result))))

Now let’s consider the evaluation of the expression (+ (f 0) (f 1)). If the arguments are evaluated from left to right the first application (f 0) will evaluate to 0 (the initial value of last), and the second application (f 1) will also evaluate to 0 (the value of the argument in the previous application). Adding up 0 and 0 we get 0. If, however, the arguments are evaluated from right to left the first application would be (f 1) which evaluates to 0 (the initial value of last), and the second application (f 0) would evaluate to 1 – the value of the argument in the previous application. When we add the two together we get 1.

Read Full Post »

Exercise 3.5

Estimate-integral defines an internal test procedure. Its task is to generate random x and y coordinates and check whether they satisfy the predicate P. This procedure is then passed as the experiment argument to the Monte Carlo simulation. The result of the simulation is multiplied by the area of the bounding rectangle within which the random coordinates are generated:

;; Returns a random number in the interval [low, high).
(define (random-in-range low high)
  (let ((range (- high low)))
    (+ low (* range (random)))))

(define (estimate-integral P x1 x2 y1 y2 trails)
  (define (test)
    (P (random-in-range x1 x2)
       (random-in-range y1 y2)))
  (let ((area (* 1.0 (- x2 x1) (- y2 y1))))
    (* area (monte-carlo trails test))))

Having defined estimate-integral we can use it to estimate the area of a unit circle by passing the appropriate predicate, bounding rectangle and number of trials:

(estimate-integral 
 (lambda (x y)
   (<= (+ (square x) (square y)) 1))
 -1.0
 1.0
 -1.0
 1.0
 100000)

=> 3.14292

Note that in PLT Racket random is not defined when the language is set to R5RS. Furthermore, if we change the language to Racket, random does not work with a single argument that is a floating point number. However, if random is called with no arguments, it returns a random number in the range [0, 1). This number can then be multiplied by some other number, say r, to get a random number in the range [0, r). This is the technique random-in-range uses.




Exercise 3.6

The message-passing paradigm is very appropriate for dealing with this particular task. Rand can be defined as a procedure that takes a single argument – a message. If the message is the symbol generate, then the local state of the random-number generator is updated, and the next value in the sequence is returned. If, however, the message is the symbol reset, then a new procedure that resets the internal state variable to a provided value is returned.

(define rand 
  (let ((x random-init))
    (lambda (m)
      (cond ((eq? m 'generate)
             (set! x (random-update x))
             x)
            ((eq? m 'reset)
             (lambda (value)
               (set! x value)))
            (else (error "Unkown request -- RAND" m))))))

Read Full Post »

Exercise 3.1

Definition of make-accumulator:

(define (make-accumulator sum)
  (lambda (amount)
    (set! sum (+ sum amount))
    sum))




Exercise 3.2

The implementation of make-monitored uses the message-passing style of programming:

(define (make-monitored f)
  (let ((times-called 0))
    (lambda (arg)
      (cond ((eq? arg 'how-many-calls?) times-called)
            ((eq? arg 'reset-count) (set! times-called 0))
            (else 
             (set! times-called (+ times-called 1))
             (f arg))))))




Exercise 3.3

In order to modify the make-account procedure, so that it creates password-protected accounts, we can change the definition of the internal dispatch procedure, to first check the provided password. If it is incorrect then the string “Incorrect password” is returned. Otherwise the message is processed and the appropriate procedure, either withdraw or deposit, is returned. The benefit of this approach is that the password check has to be implemented only in a single place:

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

Note that using this implementation, will cause the second example in the book to return an error rather than the message “Incorrect password”. The expression (acc ‘some-other-password ‘deposit) will evaluate to the string “Incorrect password” which will then be applied to 50. However the fact that the incorrect password is detected and signaled at the earliest possible moment makes much more sense than returning some procedure that, when called, will complain about the incorrectness of the previously provided password.




Exercise 3.4

The “centralized” password validation implemented in the previous exercise makes the new modification much easier. All code changes are limited to the bad-password? predicate and to introducing a new local variable – incorrect-guesses.

(define (make-account balance password)
  (let ((incorrect-guesses 0))
    (define (withdraw amount)
      (if (>= balance amount)
          (begin (set! balance (- balance amount))
                 balance)
          "Insufficient funds"))
    (define (deposit amount)
      (set! balance (+ balance amount))
      balance)
    (define (bad-password? pass)
      (cond ((eq? pass password) 
             (set! incorrect-guesses 0)
             #f)
            (else 
             (set! incorrect-guesses (+ incorrect-guesses 1))
             (if (> incorrect-guesses 7) (call-the-cops))
             #t)))
    (define (dispatch pass m)
      (cond ((bad-password? pass) "Incorrect password")
            ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            (else (error "Unknown request -- MAKE-ACCOUNT" m))))
    dispatch))

Read Full Post »