Chapter 3

An accumulator is a procedure that is called repeatedly with a single numeric argument and accumulates its arguments into a sum. Each time it is called, it returns the currently accumulated sum. Write a procedure make-accumulator that generates accumulators, each maintaining an independent sum. The input to make-accumulator should specify the initial value of the sum; for example (define A (make-accumulator 5)) (A 10) 15 (A 10) 25

In software-testing applications, it is useful to be able to count the number of times a given procedure is called during the course of a computation. Write a procedure make-monitored that takes as input a procedure, \(f\), that itself takes one input. The result returned by make-monitored is a third procedure, say mf, that keeps track of the number of times it has been called by maintaining an internal counter. If the input to \(\mathrm{mf}\) is the special symbol how-many-calls?, then \(\mathrm{mf}\) returns the value of the counter. If the input is the special symbol reset-count, then \(m f\) resets the counter to zero. For any other input, \(m f\) returns the result of calling \(f\) on that input and increments the counter. For instance, we could make a monitored version of the sqrt procedure: (define s (make-monitored sqrt)) \((\mathrm{s} 100)\) 10 \(\left(\mathrm{~s}^{\prime}\right.\) hou-many-calls?) 1

Modify the make-account procedure so that it creates password-protected accounts. That is, make-account should take a symbol as an additional argument, as in (define acc (make-account 100 'secret-password)) The resulting account object should process a request only if it is accompanied by the password with which the account was created, and should otherwise return a complaint: ((acc' 'secret-password 'withdraw) 40) 60 ((acc' 'some-other-password 'deposit) 50) "Incorrect password"

Give all possible values of \(x\) that can result from executing (define \(x\) 10) (parallel-execute (lambda () (set! \(x(* x x))\) ) (lambda () (set! \(x(* x x x))\) )) Which of these possibilities remain if we instead use serialized procedures: (define \(x\) 10) (define s (make-serializer)) (parallel-execute (s (lambda () (set! \(x(* x x))\) )) )) (s (lambda () (set! \(x(* x x x))\) )

It is useful to be able to reset a random-number generator to produce a sequence starting from a given value. Design a new rand procedure that is called with an argument that is either the symbol generate or the symbol reset and behaves as follows: (rand 'generate) produces a new random number, ((rand 'reset) (new-value )) resets the internal state variable to the designated \(\langle\) new-value \(\rangle\). Thus, by resetting the state, one can generate repeatable sequences. These are very handy to have when testing and debugging programs that use random numbers.

Define a procedure partial-sums that takes as argument a stream \(S\) and returns the stream whose elements are \(S_{0}, S_{0}+S_{1}, S_{0}+S_{1}+S_{2}, \ldots\) For example, (partial-sums integers) should be the stream \(1,3,6,10,15, \ldots\)

A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2,3 , or 5 . One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2,3 , and 5 . But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers \(S\) and notice the following facts about it. \- S begins with \(1 .\) \- The elements of (scale-stream S 2) are also elements of S. \- The same is true for (scale-stream \(\mathrm{S} 3\) ) and (scale-stream \(5 \mathrm{~S}\) ). \- These are all the elements of \(\mathrm{S}\). Now all we have to do is combine elements from these sources. For this we define a procedure merge that combines two ordered streams into one ordered result stream, eliminating repetitions: (define (merge s1 s2) (cond ((stream-null? s1) s2) ((stream-nul1? s2) s1) (else (let ( s1car (stream-car s1)) (s2car (stream-car s2))) (cond ((< s1car s2car) (cons-stream s1car (merge (stream-cdr s1) s2))) ((> s1car s2car) (cons-stream s2car (merge s1 (stream-cdr s2)))) (else (cons-stream s1car (merge (stream-cdr s1) Then the required stream may be constructed with merge, as follows: (define \(\mathrm{S}\) (cons-stream 1 (merge \(\langle ? ?\rangle\langle ? ?\rangle)\) ) Fill in the missing expressions in the places marked \(\langle ? ?\rangle\) above.

Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that make-account-and-serializer should have exported the serializer (for use by such procedures as serialized-exchange) in addition to (rather than instead of) using it to serialize accounts and deposits as makeaccount did. He proposes to redefine accounts as follows: (define (make-account-and-serializer balance) (define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) (define (deposit amount) (set! balance (+ balance amount)) balance) (let ((balance-serializer (make-serializer))) (define (dispatch m) (cond ((eq? m'withdraw) (balance-serializer withdraw)) (Ceq? m 'deposit) (balance-serializer deposit)) ((eq? m 'balance) balance) ((eq? m 'serializer) balance-serializer) (else (error "Unknown request -- MAKE-ACCot dispatch)) Then deposits are handled as with the original make-account: (define (deposit account amount) ((account' 'deposit) amount)) Explain what is wrong with Louis's reasoning. In particular, consider what happens when serialized-exchange is called.

When we defined the evaluation model in section 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. Define a simple procedure \(f\) such that evaluating (+ (f 0) ( \(f\) ) ) will return 0 if the arguments to \(+\) are evaluated from left to right but will return 1 if the arguments are evaluated from right to left.

Instead of representing a queue as a pair of pointers, we can build a queue as a procedure with local state. The local state will consist of pointers to the beginning and the end of an ordinary list. Thus, the make-queue procedure will have the form (define (make-queue) (let ((front-ptr ...) (rear-ptr ...)) (definitions of internal procedures) (define (dispatch m) ...) dispatch)) Complete the definition of make-queue and provide implementations of the queue operations using this representation.