(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50) ))

(count-change 100)
292

Consider the problem of representing line segments in a plane. Each segment is reprsented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the reprsentation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line-segment as argument and returns its midpoint (the point whose coordinates the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points:

   (define (print-point p)
     (newline)
     (display "(")
     (display (x-point p))
     (display ",")
     (display (y-point p))
     (display ")"))

Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work with either representation?

Here is an alternate procedural representation of pairs. For this representation, verify that (new-car (new-cons x y)) yields x for any objects x and y.

   (define (new-cons x y)
     (lambda (m) (m x y)))

   (define (new-car z)
     (z (lambda (p q) p)))

What is the corresponding definition of new-cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order:

   (reverse (list 1 4 9 16 25))
   (25 16 9 4 1)

Give combinations of cars and cdrs that will pick 7 from each of the following lists:

   (1 3 (5 7) 9)

   ((7))

   (1 (2 (3 (4 (5 (6 7))))))

What would the interpreter print in response to evaluating each of the following expressions?

   (list 'a 'b 'c)

   (list (list 'george))

   (cdr '((x1 x2) (y1 y2)))

   (cadr '((x1 x2) (y1 y2)))

   (pair? (car '(a short list)))

   (memq 'red '((red shoes) (blue socks)))

   (memq 'red '(red shoes blue socks))

Eva Lu Ator types to the interpreter the expression

   (car ''abracadabra)

To her surprise, the interpreter prints back quote. Explain.

Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

   (define x (list (list 1 2) (list 3 4)))

   x
   ((1 2) (3 4))

   (reverse x)
   ((3 4) (1 2))

   (deep-reverse x)
   ((4 3) (2 1))

Give a Theta(n) implementation of union-set for sets represented as ordered lists.

   (define (entry tree) (car tree))
   (define (left-branch tree) (cadr tree))
   (define (right-branch tree) (caddr tree))
   (define (make-tree entry left right)
      (list entry left right))

   (define (element-of-set? x set)
     (cond ((null? set) false)
           ((= x (entry set)) true)
           ((< x (entry set))
            (element-of-set? x (left-branch set)))
           ((> x (entry set))
            (element-of-set? x (right-branch set)))))

   (define (adjoin-set x set)
     (cond ((null? set) (make-tree x '() '()))
           ((= x (entry set)) set)
           ((< x (entry set))
            (make-tree (entry set)
                       (adjoin-set x (left-branch set))
                       (right-branch set)))
           ((> x (entry set))
            (make-tree (entry set)
                       (left-branch set)
                       (adjoin-set x (left-branch set))))))

       7         3             5
      / \       / \           / \
     3   9     1   7         3   9
    / \   \       / \       /   / \
   1   5  11     5   9     1   7  11
                      \
                      11

Insatiable Enterprises, Inc., is a highly decentralized conglomerate company consisting of a large number of independent divisions located all over the world. The company's computer facilities have just been interconnected by means of a clever network-interfacing scheme that makes the entire network appear to any user to be a single computer. Insatiable's president, in her first attempt to exploit the ability of the network to extract administrative information from division files, is dismayed to discover that, although all the division files have been implemented as data structures in Scheme, the particular data structure used varies from division to division. A meeting of division managers is hastily called to search for a strategy to integrate the files that will satisfy headquarters' needs while preserving the existing autonomy of the divisions.

Show how such a strategy can be implemented with data-directed programming. As an example, suppose that each division's personnel records consist of a single file, which contains a set of records keyed on employees' names. The structure of the set varies from division to division. Furthermore, each employee's record is itself a set (structured differently from division to division) that contains information keyed under identifiers such as address and salary. In particular:

a. Implement for headquarters a get-record procedure that retrieves a specified employee's record from a specified personnel file. The procedure should be applicable to any division's file. Explain how the individual divisions' files should be structured. In particular, what type information must be supplied?

b. Implement for headquarters a get-salary procedure that returns the salary information from a given employee's record from any division's personnel file. How should the record be structured in order to make this operation work?

c. Implement for headquarters a find-employee-record procedure. This should search all the divisions' files for the record of a given employee and return the record. Assume that this procedure takes as arguments an employee's name and a list of all the divisions' files.

d. When Insatiable takes over a new company, what changes must be made in order to incorporate the new personnel information into the central system?

The following procedure for appending lists was introduced in section 2.2.1:

   (define (append x y)
     (if (null? x)
         y
         (cons (car x) (append (cdr x) y))))

Append forms a new list by successively consing the elements of x onto y. The procedure append! is similar to append, but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of x so that its cdr is now y. (It is an error to call append! with an empty x.)

   (define (append! x y)
     (set-cdr! (last-pair x) y)
     x)

Here, last-pair is a procedure that returns the last pair in its argument:

   (define (last-pair x)
     (if (null? (cdr x))
         x
         (last-pair (cdr x))))

Consider the interaction:

   (define x (list 'a 'b))

   (define y (list 'c 'd))

   (define z (append x y))

   z
   (a b c d)

   (cdr x)
   <response>

   (define w (append! x y))

   w
   (a b c d)

   (cdr x)
   <response>

What are the missing <response>s? Draw box-and-pointer diagrams to explain your answer.

Consider the following make-cycle procedure, which uses the last-pair procedure defined in exercise 3.12:

   (define (make-cycle x)
     (set-cdr! (last-pair x) x)
     x)

Draw a box-and-pointer diagram that shows the structure z created by:

   (define z (make-cycle (list 'a 'b 'c)))

What happens if we try to compute (last-pair z)?

The following procedure is quite useful, although obscure:

   (define (mystery x)
     (define (loop x y)
       (if (null? x)
           y
           (let ((temp (cdr x)))
             (set-cdr! x y)
             (loop temp x))))
     (loop x '()))

Loop uses the "temporary" variable temp to hold the old value of the cdr of x, since the set-cdr! on the next line destroys the cdr. Explain what mystery does in general. Suppose v is defined by (define v (list 'a 'b 'c 'd)). Draw the box-and-pointer diagram that represents the list to which v is bound. Suppose we now evaluate (define w (mystery v)). Draw the box-and-pointer diagrams that show the structures v and w after evaluating this expression. What would be printed as the values of v and w?

Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to cons in list-of-values are evaluated from left to right, then list-of-values will evaluate operands from left to right; and if the arguments to cons are evaluated from right to left, then list-of-values will evaluate operands from right to left.

Write a version of list-of-values that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version of list-of-values that evaluates operands from right to left.

Louis Reasoner plans to reorder the cond clauses in mc-eval so that the clause for procedure applications appears before the clause for assignments. He argues that this will make the interpreter more efficient: Since programs usually contain more applications than assignments, definitions, and so on, his modified mc-eval wil usually check fewer clauses than the original mc-eval before identifying the type of an expresssion.

a. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with the expression (define x 3)?)

b. Louis is upset that his plan didn't work. He is willing to go to any lengths to make his evaluator recognize procedure applications before it checks for most other kinds of expressions. Help him by changing the syntax for the evaluated language so that procedure applications start with call. For example, instead of (factorial 3) we will now have to write (call factorial 3) and instead of (+ 1 2) we will have to write (call + 1 2).

Recall the definitions of the special forms and and or from chapter 1:

• and: The expressions are evlauated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there aer no expressions then true is returned.
• or: The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all experssions evaluate to false, or if there are no expressions, then false is returned.

Install and and or as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures eval-and and eval-or. Alternatively, show how to implement and and or as derived expressions.

Scheme allows an additional syntax for cond clauses, (<test> => <recipient>). If <test> evaluates to a true value, then <recipient> is evaluated. Its value must be a procedure of one argument; this procedure is then invoked on the value of the <test>, and the result is returned as the value of the cond expression. For example

   (cond ((assoc 'b '((a 1) (b 2))) => cadr)
         (else false))

Returns 2. Modifying the handling of cond so that it supports this extended syntax.

Suppose we type in the following definitions to the lazy evaluator:

   (define count 0)

   (define (id x)
     (set! count (+ count 1))
     x)

Give the missing values in the following sequence of interactions, and explain your answers.

   (define w (id (id 10)))

   ;;; L-Eval input:
   count
   ;;; L-Eval value:
   <response>

   ;;; L-Eval input:
   w
   ;;; L-Eval value:
   <response>

   ;;; L-Eval input:
   count
   ;;; L-Eval value:
   <response>

Exhibit a program that you would expect to run much more slowly without memoization than with memoization. Also, consider the following interaction, where the id procedure is defined as in exercise 4.27 and count starts at 0:

   (define (square x)
     (* x x))

   ;;; L-Eval input:
   (square (id 10))
   ;;; L-Eval value:
   <response>

   ;;; L-Eval input:
   count
   ;;; L-Eval value:
   <response>

Give the responses both when the evaluator memoizes and when it does not.

help "item

erase [procedure]

Write a procedure an-integer-between that returns an integer between two given bounds. This can be used to implement a procedure that finds Pythagorean triples, i.e., triples of integers (i, j, k) between the given bounds such that i <= j and i² + j² = k², as follows:

(define (a-pythagorean-triple-between low high)
  (let ((i (an-integer-between low high)))
    (let ((j (an-integer-between i high)))
      (let ((k (an-integer-between j high)))
        (require (= (+ (* i i) (* j j)) (* k k)))
        (list i j k) ))))

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?

(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
      (distinct? (list baker cooper fletcher miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith)) ))

(define (distinct? items)
  (cond ((null? items) true)
        ((null? (cdr items)) true)
        ((member (car items) (cdr items)) false)
        (else (distinct? (cdr items))) ))

Modify the multiple-dwelling procedure to omit the requirement that Smith and Fletcher do not live on adjacent floors. How many solutions are there to this modified puzzle?