Chapter 4

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 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 eval will usually check fewer clauses than the original eval before identifying the type of an expression.

Let* is similar to let, except that the bindings of the let variables are performed sequentially from left to right, and each binding is made in an environment in which all of the preceding bindings are visible. For example \(\left.\left.\left.\begin{array}{l}\left(1 \text { et* }\left(\left(\begin{array}{ll}x & 3\end{array}\right)\right.\right. \\ (y(+x & 2)) \\ (z & (+x & y & 5\end{array}\right)\right)\right) } \\\\{(* x \text { z) })} \end{array}\) returns 39 . Explain how a let* expression can be rewritten as a set of nested let expressions, and write a procedure let*->nested-lets that performs this transformation. If we have already implemented let (exercise 4.6) and we want to extend the evaluator to handle let*, is it sufficient to add a clause to eval whose action is (eval (let*->nested-lets exp) env) or must we explicitly expand let* in terms of non-derived expressions?

Many languages support a variety of iteration constructs, such as do, for, while, and until. In Scheme, iterative processes can be expressed in terms of ordinary procedure calls, so special iteration constructs provide no essential gain in computational power. On the other hand, such constructs are of ten convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions.

In this exercise we implement the method just described for interpreting internal definitions. We assume that the evaluator supports let (see exercise 4.6). a. Change lookup-variable-value (section 4.1.3) to signal an error if the value it finds is the symbol *unassigned*. b. Write a procedure scan-out-defines that takes a procedure body and returns an equivalent one that has no internal definitions, by making the transformation described above. c. Install scan-out-defines in the interpreter, either in make-procedure or in procedure-body (see section 4.1.3). Which place is better? Why?

Ben Bitdiddle and Alyssa P. Hacker disagree over the importance of lazy evaluation for implementing things such as unless. Ben points out that it's possible to implement unless in applicative order as a special form. Alyssa counters that, if one did that, unless would be merely syntax, not a procedure that could be used in conjunction with higher-order procedures. Fill in the details on both sides of the argument. Show how to implement unless as a derived expression (like cond or let), and give an example of a situation where it might be useful to have unless available as a procedure, rather than as a special form.

Ben Bitdiddle tests the lazy list implementation given above by evaluating the expression \(\left(\right.\) car \(^{\prime}(\) a b c) \()\) To his surprise, this produces an error. After some thought, he realizes that the "lists" obtained by reading in quoted expressions are different from the lists manipulated by the new definitions of cons, car, and cdr. Modify the evaluator's treatment of quoted expressions so that quoted lists typed at the driver loop will produce true lazy lists.

Solve the following "Liars" puzzle (from Phillips 1934): Five schoolgirls sat for an examination. Their parents-so they thoughtshowed an undue degree of interest in the result. They therefore agreed that, in writing home about the examination, each girl should make one true statement and one untrue one. The following are the relevant passages from their letters: \- Betty: "Kitty was second in the examination. I was only third." \- Ethel: "You'll be glad to hear that I was on top. Joan was second." \- Joan: "I was third, and poor old Ethel was bottom." \- Kitty: "I came out second. Mary was only fourth." \- Mary: "I was fourth. Top place was taken by Betty." What in fact was the order in which the five girls were placed?

Define a rule that says that a person is a "big shot" in a division if the person works in the division but does not have a supervisor who works in the division.

Ben Bitdiddle has missed one meeting too many. Fearing that his habit of forgetting meetings could cost him his job, Ben decides to do something about it. He adds all the weekly meetings of the firm to the Microshaft data base by asserting the following: (meeting accounting (Monday 9am)) (meeting administration (Monday 10am)) (meeting computer (Wednesday 3pm)) (meeting administration (Friday 1pm)) Each of the above assertions is for a meeting of an entire division. Ben also adds an entry for the company-wide meeting that spans all the divisions. All of the company's employees attend this meeting. (meeting whole-company (Wednesday \(4 \mathrm{pm}\) )) a. On Friday morning, Ben wants to query the data base for all the meetings that occur that day. What query should he use? b. Alyssa P. Hacker is unimpressed. She thinks it would be much more useful to be able to ask for her meetings by specif ying her name. So she designs a rule that says that a person's meetings include all whole-company meetings plus all meetings of that person's division. Fill in the body of Alyssa's rule. (rule (meeting-time ?person ?day-and-time) \(\langle\) rule-body \(\rangle\) ) c. Alyssa arrives at work on Wednesday morning and wonders what meetings she has to attend that day. Having defined the above rule, what query should she make to find this out?