Saturday, January 31, 2009

SICP Section 4.3 Variations on a Scheme -- Nondeterministic Computing

Exercise 4.35. 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 i2 + j2 = k2, as follows:


Exercise 4.36. Exercise 3.69 discussed how to generate the stream of all Pythagorean triples, with no upper bound on the size of the integers to be searched. Explain why simply replacing an-integer-between by an-integer-starting-from in the procedure in exercise 4.35 is not an adequate way to generate arbitrary Pythagorean triples. Write a procedure that actually will accomplish this. (That is, write a procedure for which repeatedly typing try-again would in principle eventually generate all Pythagorean triples.)

Answer: Here is what the procedure explained in exercise 4.35 would look like if we rewrite it using an-integer-starting-from

This procedure can be invoked as follows: (all-pythagorean-triples-starting-from 1)

The amb operator starts with i = 1. This leads to j = 1 and k = 1. As these values do not meet the Pythagorean condition the operator retraces its path to the *most recent choice point* and tries the next alternative. That means heading back to k = 1 and resuming with k = 2. Since this also fails k = 3 is selected and so on. This continues until *all values* of k are tried. As this is an impossible task we are stuck in a situation where i and j never proceed beyond 1. This is similar to the problems faced in chapter 3 while working with infinite streams. The search will not proceed meaningfully without some form of interleaving.

I am not able to come up with a good answer to the second part of the problem.

Exercise 4.37. Ben Bitdiddle claims that the following method for generating Pythagorean triples is more efficient than the one in exercise 4.35. Is he correct? (Hint: Consider the number of possibilities that must be explored.)

Answer: Ben's version generates fewer options to explore due the condition (require (>= hsq ksq)). Further those values of i^2 + j^2 whose root is not an integer are not explored. Together these conditions make Ben's version more efficient than the version given in exercise 4.35.

Exercise 4.39. Does the order of the restrictions in the multiple-dwelling procedure affect the answer? Does it affect the time to find an answer? If you think it matters, demonstrate a faster program obtained from the given one by reordering the restrictions. If you think it does not matter, argue your case.

Answer: The order of the restrictions does not affect the answer. The answer has to meet ALL of them, so whatever emerges would have met all the conditions.

The time taken is affected by the order of restrictions. Take for example this variant which moves the restriction for distinct floors for each resident to the end of the list. Distinct? takes relatively more time compared to the other restrictions. It operates on 5 tuples (one for each resident-floor pair) each time it is called. It is therefore better to invoke this procedure *after* as many of the restrictions as possible have been met.

Exercise 4.40. In the multiple dwelling problem, how many sets of assignments are there of people to floors, both before and after the requirement that floor assignments be distinct? It is very inefficient to generate all possible assignments of people to floors and then leave it to backtracking to eliminate them. For example, most of the restrictions depend on only one or two of the person-floor variables, and can thus be imposed before floors have been selected for all the people. Write and demonstrate a much more efficient nondeterministic procedure that solves this problem based upon generating only those possibilities that are not already ruled out by previous restrictions. (Hint: This will require a nest of let expressions.)

Answer: There is no need for distinctness before the first restriction is imposed. This means that for every assignment for the first person there are 5 for the next, 5 * 5 for the third, 5 * 5 * 5 for the fourth person and so on. Therefore there is a grand total of 5^5 = 3125 assignments of people to floors before distinct?.

After the distinct? restriction is applied this reduces to 5 possibilities for the first person, 4 for the next (as the first and second cannot be on the same floor), 3 thereafter and so on. We get 5! = 120 possibilities afterwards.

More efficient solution:

Let us start with the restrictions on individuals. Some of the possibilities can be "trimmed" by avoiding certain assignments. For instance Baker cannot be on the fifth floor. Therefore we can remove 5 from the amb expression generating floors for Baker. Similarly we can remove 1 from the list for Cooper and both 1 and 5 from the list for Fletcher.

Miller has to live above Cooper. As the lowest floor Cooper can live on is 2, Miller can only live on floors 3, 4 or 5. Here is a version of the program incorporating all these:

We can further refine the program as the authors have hinted. For instance if we first enforce the restriction that Miller should live above Cooper then we are left with the following Six possibilities: (Cooper, Miller): (2, 3), (2,4) (2,5), (3, 4), (3, 5), (4, 5). We can delay the assignment of floors for Baker until after after all the other restrictions have been imposed.

Exercise 4.41. Write an ordinary Scheme program to solve the multiple dwelling puzzle.

Answer: This solution makes use of the permutations procedure from Chapter 2.

Exercise 4.42. Solve the following ``Liars'' puzzle (from Phillips 1934):

Five schoolgirls sat for an examination. Their parents -- so they thought -- showed 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?

Answer: I wrote an utility procedure or for the solution.

Exercise 4.43. Use the amb evaluator to solve the following puzzle:

Mary Ann Moore's father has a yacht and so has each of his four friends: Colonel Downing, Mr. Hall, Sir Barnacle Hood, and Dr. Parker. Each of the five also has one daughter and each has named his yacht after a daughter of one of the others. Sir Barnacle's yacht is the Gabrielle, Mr. Moore owns the Lorna; Mr. Hall the Rosalind. The Melissa, owned by Colonel Downing, is named after Sir Barnacle's daughter. Gabrielle's father owns the yacht that is named after Dr. Parker's daughter. Who is Lorna's father?

Try to write the program so that it runs efficiently (see exercise 4.40). Also determine how many solutions there are if we are not told that Mary Ann's last name is Moore.

Answer: 1. Mary Ann is Mr. Moore's daughter. Therefore her father is Mr. Moore. We can remove Mr. Moore for consideration as the father of other girls.

2. Sir Barnacle owns the Gabrielle. So he cannot be Gabrielle's father.

3. Mr. Moore owns the Lorna and is Mary Ann's father.

4. Mr. Hall owns the Rosalind. Mr. Hall cannot be Rosalind's father.

5. The Melissa is owned by Col. Downing and named after Sir Barnacle's daughter. We can name Sir Barnacle as Melissa's father and remove him from the lists of possible fathers of other girls.

6. Gabrielle's father owns the yacht that is named after Dr. Parker's daughter. In my opinion formulating this restriction is the key learning of this exercise. Here is my approach: Gabrielle father is one of the following three: Col. Downing, Mr. Hall or Dr. Parker. If Dr. Parker is her father then the condition cannot be true as no man owns a yacht named after his own daughter. That leaves two possibilities and the restriction can be expressed in terms of those two.

If Col. Downing is Gabrielle's father Lorna must be Dr. Parker's daugther. On the other hand if Mr. Hall is Gabrielle's father then Rosalind must be Dr. Parker's daughter.

Executing this, I got 'downing. Lorna's father is Col. Downing.

If we are not told about the identity of Mary Ann's father then the problem can be restructured as follows: 1. Sir Barnacle owns the Gabrielle. So he cannot be Gabrielle's father.

3. Mr. Moore owns the Lorna and therefore cannot be Lorna's father.

4. Mr. Hall owns the Rosalind. Mr. Hall cannot be Rosalind's father.

5. The Melissa is owned by Col. Downing and named after Sir Barnacle's daughter. We can name Sir Barnacle as Melissa's father and remove him from the lists of possible fathers of other girls.

6. Gabrielle's father owns the yacht that is named after Dr. Parker's daughter. In this scenario Gabrielle father is one of the following four: Col. Downing, Mr. Hall, Mr. Moore or Dr. Parker. If Dr. Parker is her father then the condition cannot be true as no man owns a yacht named after his own daughter. Col. Downing cannot be Gabrielle's father as his yacht is not named after Dr. Parker's daughter. That leaves two possibilities and the restriction can be expressed in terms of the two.

If Mr. Hall is Gabrielle's father then Rosalind must be Dr. Parker's daughter. If Mr. Moore is Gabrielle's father then Lorna must be Dr. Parker's daughter.

This problem has two answers: Lorna's father could be Col. Downing or Mr. Parker.

Exercise 4.44. Exercise 2.42 described the ``eight-queens puzzle'' of placing queens on a chessboard so that no two attack each other. Write a nondeterministic program to solve this puzzle.


Exercise 4.45. With the grammar given above, the following sentence can be parsed in five different ways: ``The professor lectures to the student in the class with the cat.'' Give the five parses and explain the differences in shades of meaning among them.

Answer: Parse 1: The professor is lecturing with the cat, in the classroom.
 The professor 
        to the student
    in the class with the cat

Parse 2: The student has the cat. The professor is lecturing the student.
 The professor
        to the student in the class with the cat

Parse 3: The professor has the cat. The professor is lecturing the student in the classroom. However it is not clear if the cat is in the classroom.
 The professor
        to the student in the class
    with the cat

Parse 4: The student has the cat. However it is not clear if the student has brought the cat to the classroom.
 The professor
        to the student in the class
        with the cat

Parse 5: There classroom has the cat. The professor is lecturing the student in this classroom. It is not clear if the cat belongs to the student or the professor. It could be a studious and independent cat choosing to spend its time in the classroom for all we know.
 The professor
        to the student
        in the class with the cat

Exercise 4.46. The evaluators in sections 4.1 and 4.2 do not determine what order operands are evaluated in. We will see that the amb evaluator evaluates them from left to right. Explain why our parsing program wouldn't work if the operands were evaluated in some other order.

Answer: I'll use the simplest grammar used at the start of the section to tackle this problem. A sentence is parsed as follows:

Consider the sample input '(the cat eats). Parse-sentence simply makes a call to list. Let us assume that the arguments to list are evaluated from right to left. (parse-word verbs) would therefore get invoked first. This procedure requires that the first word in *unparsed* should be present in the cdr of the word list passed in. In this case it would expect 'the to be present in the list of verbs supplied. As this condition is never met, parsing fails. Thus we can see that the evaluator should use a left-to-right order for evaluating operands.

Exercise 4.47. Louis Reasoner suggests that, since a verb phrase is either a verb or a verb phrase followed by a prepositional phrase, it would be much more straightforward to define the procedure parse-verb-phrase as follows (and similarly for noun phrases):

Does this work? Does the program's behavior change if we interchange the order of expressions in the amb?

Answer: Louis' version of parse-verb-phrase will work. Take for example the sentence 'The professor lectures to the student with the cat. Parse-verb-phrase will start by invoking (parse-word verbs) which will search *unparsed* for verbs. As 'lectures is a verb it will succeed and return '(verb lectures). Parsing will continue as there are more words left.

On the subsequent try the second argument to amb, i.e. (list 'verb-phrase (parse-verb-phrase) (parse-prepositional-phrase)) is evaluated. By the time the second argument is evaluated the set! operation would have been undone and *unparsed* would have been restored as 'lectures to the student with the cat. (parse-verb-phrase) will return '(verb lectures) and (parse-prepositional-phrase) will continue to parse the rest of the words.

If we interchange the arguments to amb, the procedure becomes:

When the procedure is invoked, the arguments to list are evaluated. As the second argument is a recursive call to the same procedure, (parse-verb-phrase) is again invoked. This leads to an infinite loop as parse-verb-phrase never gets a chance to return.

Exercise 4.48. Extend the grammar given above to handle more complex sentences. For example, you could extend noun phrases and verb phrases to include adjectives and adverbs, or you could handle compound sentences.

Answer: This solution assumes the simplest case of adjective use - adjectives used as pre-modifiers. The adjective appears before the noun, after the article. For example 'the old professor. Such phrases are called adjective phrases. With this assumption we can modifiy the parse-simple-noun-phrase as follows:

Here is a partial list of adjectives:

Similarly adverbs have varying rules of placement. Here is a simple solution which tackles adverbs placed after the verb. For example 'the old professor quietly lectured the young student with the black cat. Here 'quietly is an adverb modifying the verb, 'lectured. I have added a new category simple-verb-phrase and an utility procedure to parse them.

The parse-verb-phrase procedure has been changed accordingly.

Exercise 4.49. Alyssa P. Hacker is more interested in generating interesting sentences than in parsing them. She reasons that by simply changing the procedure parse-word so that it ignores the ``input sentence'' and instead always succeeds and generates an appropriate word, we can use the programs we had built for parsing to do generation instead. Implement Alyssa's idea, and show the first half-dozen or so sentences generated.


The sample sentences generated are quoted below. Apparently the recursive nature of the definition causes the new prepositional phrases to be generated and attached to the sentence rather than generating a new sentence. This looks like the recursion trap mentioned in footnote 54.

Exercise 4.50. Implement a new special form ramb that is like amb except that it searches alternatives in a random order, rather than from left to right. Show how this can help with Alyssa's problem in exercise 4.49.

Answer: My implementation of ramb works by fetching one element at random from its choices. This element is removed after use and the the process is continued with the rest of the elements. I have used the filter procedure defined in chapter 2 inside the utility procedure remove-from-list. Ramb fails after all its choices have been exhausted.

The second part of the question is to demonstrate how ramb can help Alyssa's problem in exercise 4.49. My solution to exercise 4.49 does not involve amb. Parse-word simply picks up a word at random from the list given. I am unable to figure out how to use ramb to assist solving exercise 4.49.

Exercise 4.51. Implement a new kind of assignment called permanent-set! that is not undone upon failure. For example, we can choose two distinct elements from a list and count the number of trials required to make a successful choice as follows:

What values would have been displayed if we had used set! here rather than permanent-set! ?


Count would be printed as 1 always if we had used set! instead of permanent-set!

Exercise 4.52. Implement a new construct called if-fail that permits the user to catch the failure of an expression. If-fail takes two expressions. It evaluates the first expression as usual and returns as usual if the evaluation succeeds. If the evaluation fails, however, the value of the second expression is returned, as in the following example:


Exercise 4.53. With permanent-set! as described in exercise 4.51 and if-fail as in exercise 4.52, what will be the result of evaluating

Answer: The expression will print ((8 35) (3 110) (3 20))

Exercise 4.54. If we had not realized that require could be implemented as an ordinary procedure that uses amb, to be defined by the user as part of a nondeterministic program, we would have had to implement it as a special form. This would require syntax procedures

and a new clause in the dispatch in analyze

as well the procedure analyze-require that handles require expressions. Complete the following definition of analyze-require.


Wednesday, January 14, 2009

SICP Section 4.2 Variations on a Scheme -- Lazy Evaluation

Exercise 4.25. Suppose that (in ordinary applicative-order Scheme) we define unless as shown above and then define factorial in terms of unless as

What happens if we attempt to evaluate (factorial 5)? Will our definitions work in a normal-order language?

Answer: The expression (factorial 5) leads to the following application of unless:

In an applicative-order language all the arguments to a procedure are evaluated when the procedure is applied. In the case of the above expression the first and third arguments are readily evaluated irrespective of the order of evaluation (left to right or vice-versa). The second argument however requires evaluating (factorial (-n 1)), i.e. (factorial 4) for completion. This is turn requires that (factorial 3) be evaluated and so on. The evaluation never completes even when n becomes 1 as the second argument never gets evaluated. Therefore we are left with an infinite loop.

In a normal-order language evaluation of procedure arguments are delayed until the actual argument values are needed. In the case of the above expression (factorial 4) is invoked as n != 1. The recursive invocation continues until the time n becomes 1. When n = 1, the second argument of the unless expression is not evaluated and 1 is returned. Therefore the program completes and we get the result.

Exercise 4.26. 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.


I am not able to come up with any examples of using unless as a higher order procedure. :(

Exercise 4.27. Suppose we type in the following definitions to the lazy evaluator:

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


Explanation: When the preceding statement (define w (id (id 10))) is evaluated only the outer call to id is forced as it is immediately required. This causes count to be incremented once, to 1. The value of w becomes a thunk consisting of the inner call to id and the environment. This can be inspected by calling (lookup-variable-value 'w the-global-environment) after evaluating the expressions.

When w is called the driver-loop forces the actual-value of the thunk to be evaluated before presenting it to the output. This causes the delayed call to (id 10) to be executed. This expression increments count again and returns 10.

As the actual-value of w was forced in the last expression count has become 2.

Exercise 4.28. Eval uses actual-value rather than eval to evaluate the operator before passing it to apply, in order to force the value of the operator. Give an example that demonstrates the need for this forcing.

Answer: Consider the following function. It retruns either of the procedures even? or odd? depending on the input.

Now invoke this function as shown below

If the evaluator did not use actual-value to evaluate the operator the operand would have been a thunk representing (choose 1) and not the actual result. Consequently the expression would have thrown an error.

Exercise 4.29. 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:

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

Answer: The program given below involves two recursive calls to itself. It will be faster with memoization than without.

This result is the same with or without memoization.

When (square (id 10)) is called, the evaluation of (id 10) is delayed until it is actually needed. The need for forcing (id 10) happens when (* x x) is evaluated. Without memoization the procedure id is invoked twice, once for each argument to *, causing count to be incremented twice. With memoization id is only invoked once. The return value is used without calling it again for the second argument to *. Therefore count is incremented only once with memoization.

Exercise 4.30. Cy D. Fect, a reformed C programmer, is worried that some side effects may never take place, because the lazy evaluator doesn't force the expressions in a sequence. Since the value of an expression in a sequence other than the last one is not used (the expression is there only for its effect, such as assigning to a variable or printing), there can be no subsequent use of this value (e.g., as an argument to a primitive procedure) that will cause it to be forced. Cy thus thinks that when evaluating sequences, we must force all expressions in the sequence except the final one. He proposes to modify eval-sequence from section 4.1.1 to use actual-value rather than eval:

a. Ben Bitdiddle thinks Cy is wrong. He shows Cy the for-each procedure described in exercise 2.23, which gives an important example of a sequence with side effects:

He claims that the evaluator in the text (with the original eval-sequence) handles this correctly:

Explain why Ben is right about the behavior of for-each. b. Cy agrees that Ben is right about the for-each example, but says that that's not the kind of program he was thinking about when he proposed his change to eval-sequence. He defines the following two procedures in the lazy evaluator:

What are the values of (p1 1) and (p2 1) with the original eval-sequence? What would the values be with Cy's proposed change to eval-sequence?

c. Cy also points out that changing eval-sequence as he proposes does not affect the behavior of the example in part a. Explain why this is true.

d. How do you think sequences ought to be treated in the lazy evaluator? Do you like Cy's approach, the approach in the text, or some other approach?

Answer: a. The lambda procedure used with for-each uses two primitive procedures, newline and display. As apply does not delay the arguments in the case of primitive procedures, newline and display are executed immediately. Hence Ben is able to predict that the original evaluator can handle the operation correctly.

(p1 1) returns (1 2) with the original eval-sequence.
(p2 1) returns 1 with the original eval-sequence.
The set! expression is passed to the internal procedure p in the form of a thunk. As this thunk is not forced, the value of x remains unchanged. Hence (p2 1) returns 1.

After implementing Cy's changes the behaviour of (p1 1) remains unchanged. However (p2 1) will return (1 2). This is a consequence of forcing all expressions in eval-sequence. The set! expression passed on to the internal procedure p as a thunk gets forced, thereby changing the value of x. Hence (p2 1) returns (1 2).

c. The example in part a uses primitive procedures for display. As arguments to primitive procedures were not delayed to begin with, the behavior remains unchanged.

d. Both approaches have their own trade offs. I prefer Cy's approach where assignment is involved. However this approach can slow things down where long sequences are involved.

Exercise 4.31. The approach taken in this section is somewhat unpleasant, because it makes an incompatible change to Scheme. It might be nicer to implement lazy evaluation as an upward-compatible extension, that is, so that ordinary Scheme programs will work as before. We can do this by extending the syntax of procedure declarations to let the user control whether or not arguments are to be delayed. While we're at it, we may as well also give the user the choice between delaying with and without memoization. For example, the definition

would define f to be a procedure of four arguments, where the first and third arguments are evaluated when the procedure is called, the second argument is delayed, and the fourth argument is both delayed and memoized. Thus, ordinary procedure definitions will produce the same behavior as ordinary Scheme, while adding the lazy-memo declaration to each parameter of every compound procedure will produce the behavior of the lazy evaluator defined in this section. Design and implement the changes required to produce such an extension to Scheme. You will have to implement new syntax procedures to handle the new syntax for define. You must also arrange for eval or apply to determine when arguments are to be delayed, and to force or delay arguments accordingly, and you must arrange for forcing to memoize or not, as appropriate.


This was a truly fascinating exercise. It looked intimidating but I came to enjoy doing it.

Exercise 4.32. Give some examples that illustrate the difference between the streams of chapter 3 and the ``lazier'' lazy lists described in this section. How can you take advantage of this extra laziness?

Answer: The ability to delay both car and cdr operation allows us to create data structures that behave like streams w.r.t car as well as cdr. One such structure would be an infinite tree. If we recall how trees were implemented as lists earlier we can see how lazy car and cdr allow us to convert those to infinite trees.

Exercise 4.33. Ben Bitdiddle tests the lazy list implementation given above by evaluating the expression

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.

Answer: The key change is in the way quoted expressions are evaluated. The eval procedure is changed to construct and evaluate lazy lists if the quoted text contains a list. Lazy lists are constructed using a utility procedure text-list->lazy-list.

Exercise 4.34. Modify the driver loop for the evaluator so that lazy pairs and lists will print in some reasonable way. (What are you going to do about infinite lists?) You may also need to modify the representation of lazy pairs so that the evaluator can identify them in order to print them.

Answer: In order to print lazy lists we should first identify them as such. Ideally there should be a tag, say 'lazy-list or some such for the same. Right now I am using a make shift solutions, identifying them by matching them with the structure of cons. i.e. (lambda (m) (m x y))

Next, driver-loop should be modified to check if the output is a lazy list. If so it invokes a special procedure to print the output. The first 5 elements of a list are printed followed by "..." if there are more. This number is arbitrary.

Finally a special procedure to print a lazy list.

Tuesday, January 13, 2009

SICP Section 4.1 The Metacircular Evaluator

Exercise 4.1. 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.

Answer: Version of list-of-values that evaluates from left to right irrespective of order of evaluation in the underlying Lisp.

Version of list-of-values that evaluates from right to left irrespective of order of evaluation in the underlying Lisp.

Exercise 4.2. 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.

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 of 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).

Answer: a. After Louis' changes, all definitions will be evaluated as procedure applications. This can lead to errors. In the example (define x 3) will be treated as the application of the procedure define on the values x and 3.

b. This can be achieved by changing the selectors.

Exercise 4.3. Rewrite eval so that the dispatch is done in data-directed style. Compare this with the data-directed differentiation procedure of exercise 2.73. (You may use the car of a compound expression as the type of the expression, as is appropriate for the syntax implemented in this section.).

Exercise 4.4. Recall the definitions of the special forms and and or from chapter 1:
  • and: The expressions are evaluated 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 are 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 expressions 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.


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

returns 2. Modify the handling of cond so that it supports this extended syntax.


Exercise 4.6. Let expressions are derived expressions, because

is equivalent to

Implement a syntactic transformation let->combination that reduces evaluating let expressions to evaluating combinations of the type shown above, and add the appropriate clause to eval to handle let expressions.


Exercise 4.7. 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

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

or must we explicitly expand let* in terms of non-derived expressions?

Answer: a.

b. It is sufficient to add the given snippet to eval to make let* work.

Exercise 4.8. ``Named let'' is a variant of let that has the form

The <bindings> and <body> are just as in ordinary let, except that <var> is bound within <body> to a procedure whose body is <body> and whose parameters are the variables in the <bindings>. Thus, one can repeatedly execute the <body> by invoking the procedure named <var>. For example, the iterative Fibonacci procedure (section 1.2.2) can be rewritten using named let as follows:

Modify let->combination of exercise 4.6 to also support named let.


Exercise 4.9. 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 often convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions.


Exercise 4.11. Instead of representing a frame as a pair of lists, we can represent a frame as a list of bindings, where each binding is a name-value pair. Rewrite the environment operations to use this alternative representation.

Answer: Lookup function remains unchanged. Changed code follows.

Exercise 4.12. The procedures set-variable-value!, define-variable!, and lookup-variable-value can be expressed in terms of more abstract procedures for traversing the environment structure. Define abstractions that capture the common patterns and redefine the three procedures in terms of these abstractions.

Answer: This solution depends on the original mechanism of representing frames.

Exercise 4.13. Scheme allows us to create new bindings for variables by means of define, but provides no way to get rid of bindings. Implement for the evaluator a special form make-unbound! that removes the binding of a given symbol from the environment in which the make-unbound! expression is evaluated. This problem is not completely specified. For example, should we remove only the binding in the first frame of the environment? Complete the specification and justify any choices you make.

Answer: I prefer to treat make-unbound! as the functional opposite of define-variable!. Therefore it should only remove the binding from the first frame. This also prevents the operation from affecting the global environment, which is desirable. The operation raises an error if the value being unbound is not present in the first frame.

Exercise 4.14. Eva Lu Ator and Louis Reasoner are each experimenting with the metacircular evaluator. Eva types in the definition of map, and runs some test programs that use it. They work fine. Louis, in contrast, has installed the system version of map as a primitive for the metacircular evaluator. When he tries it, things go terribly wrong. Explain why Louis's map fails even though Eva's works.

Answer: Louis' version of map uses the primitive version of the procedure. This version expects a <procedure> in the *native language* as the first argument, to be applied by the *native apply*. However the argument supplied to map is in the *new language*. This leads to errors.

Exercise 4.15. Given a one-argument procedure p and an object a, p is said to ``halt'' on a if evaluating the expression (p a) returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure halts? that correctly determines whether p halts on a for any procedure p and object a. Use the following reasoning: If you had such a procedure halts?, you could implement the following program:

Now consider evaluating the expression (try try) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?.

Answer: Executing (try try) evaluates (halts? try try). Assume that this returns true, implying that the application of (try try) is expected to halt. However this leads to the program running forever as (run-forever) is invoked.

If the return value is false, indicating that (try try) should not halt, then the program will halt. As both the outcomes contradicts the purpose of checking using halt?, there cannot be such a function.

Exercise 4.16. 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?

Answer: a.


c. A procedure is defined or redefined fewer times than it is executed/applied. As procedure-body is used by apply for each execution of the procedure it is better to install scan-out-defines in make-procedure which is used only when the procedure definition is being evaluated.

Exercise 4.17. Draw diagrams of the environment in effect when evaluating the expression in the procedure in the text, comparing how this will be structured when definitions are interpreted sequentially with how it will be structured if definitions are scanned out as described. Why is there an extra frame in the transformed program? Explain why this difference in environment structure can never make a difference in the behavior of a correct program. Design a way to make the interpreter implement the ``simultaneous'' scope rule for internal definitions without constructing the extra frame.

Answer: The new frame is introduced due to the let operation being used. Every time a let is used a new frame is added which contains the expressions defined in the let.

As this newly introduced frame contains only those variables used by the let it should not make any difference to the behaviour of a correct program.

Exercise 4.18. Consider an alternative strategy for scanning out definitions that translates the example in the text to

Here a and b are meant to represent new variable names, created by the interpreter, that do not appear in the user's program. Consider the solve procedure from section 3.5.4:

Will this procedure work if internal definitions are scanned out as shown in this exercise? What if they are scanned out as shown in the text? Explain.

Answer: This procedure will not work if the internal definitions are scanned out as shown in this exercise. Consider the outer let statement. When it is evaluated y and dy are both set to '*unassigned*. Intermediate variables a and b are then evaluated in the inner let. Their values will be evaluated as (integral (delay '*unassigned*) y0 dt) and (stream-map f '*unassigned*) respectively. The latter throws an error as the second argument of stream-map is not a stream as expected.

Scanning out the internal definitions as shown in the text will work. In this case only one let expression is constructed. At the time of evaluation y and dy are initially assigned the value '*unassigned*. By the time the set! expression for dy is executed y has already been set to (integrate (delay dy) y0 dt), the result of which is in fact a stream. This satisfies the requirement that the second argument to stream-map should be a stream. Thereby the procedure works.

Exercise 4.19. Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about the desired result of evaluating the expression

Ben asserts that the result should be obtained using the sequential rule for define: b is defined to be 11, then a is defined to be 5, so the result is 16. Alyssa objects that mutual recursion requires the simultaneous scope rule for internal procedure definitions, and that it is unreasonable to treat procedure names differently from other names. Thus, she argues for the mechanism implemented in exercise 4.16. This would lead to a being unassigned at the time that the value for b is to be computed. Hence, in Alyssa's view the procedure should produce an error. Eva has a third opinion. She says that if the definitions of a and b are truly meant to be simultaneous, then the value 5 for a should be used in evaluating b. Hence, in Eva's view a should be 5, b should be 15, and the result should be 20. Which (if any) of these viewpoints do you support? Can you devise a way to implement internal definitions so that they behave as Eva prefers?

Answer: The ideal case would be to have simultaneous evaluations as Eva prefers. However this is quite complex to implement, especially when mutual recursion is involved. Delay could be used in such cases thought it wouldn't be straightforward to implement. Given the difficulties involved in implementing the best alternative would be to support Alyssa's position and throw an error.

Exercise 4.20. Because internal definitions look sequential but are actually simultaneous, some people prefer to avoid them entirely, and use the special form letrec instead. Letrec looks like let, so it is not surprising that the variables it binds are bound simultaneously and have the same scope as each other. The sample procedure f above can be written without internal definitions, but with exactly the same meaning, as

Letrec expressions, which have the form

are a variation on let in which the expressions that provide the initial values for the variables are evaluated in an environment that includes all the letrec bindings. This permits recursion in the bindings, such as the mutual recursion of even? and odd? in the example above, or the evaluation of 10 factorial with

a. Implement letrec as a derived expression, by transforming a letrec expression into a let expression as shown in the text above or in exercise 4.18. That is, the letrec variables should be created with a let and then be assigned their values with set!.

b. Louis Reasoner is confused by all this fuss about internal definitions. The way he sees it, if you don't like to use define inside a procedure, you can just use let. Illustrate what is loose about his reasoning by drawing an environment diagram that shows the environment in which the is evaluated during evaluation of the expression (f 5), with f defined as in this exercise. Draw an environment diagram for the same evaluation, but with let in place of letrec in the definition of f.

Answer: a.

b. (1) f written as in this exercise using letrec. Consider how the letrec would have been transformed using lambda:

It is clear that the procedures even? and odd? can see each other as they are defined in the same environment. The rest-of-the-body-of-f is eveluated in the same environment as even? and odd?. This would not have been possible if let had been used instead of letrec (see below).

(2) f using let instead of letrec. In order to understand this better let us rewrite the let expression using lambda.

It can be seen that the rest-of-the-body-of-f is evaluated in an environment different from that of the two lambda procedures defining even? and odd?. These procedures cannot see each other - the body of even? will not find odd? and vice versa. Therefore this tranformation should not work. However this snippet *does* work in Dr Scheme. I suspect that this is perhaps because Dr Scheme treats such expressions in the same way as letrec.

Exercise 4.21. Amazingly, Louis's intuition in exercise 4.20 is correct. It is indeed possible to specify recursive procedures without using letrec (or even define), although the method for accomplishing this is much more subtle than Louis imagined. The following expression computes 10 factorial by applying a recursive factorial procedure:27

a. Check (by evaluating the expression) that this really does compute factorials. Devise an analogous expression for computing Fibonacci numbers.

b. Consider the following procedure, which includes mutually recursive internal definitions:

Fill in the missing expressions to complete an alternative definition of f, which uses neither internal definitions nor letrec:

Answer: a.


Exercise 4.22. Extend the evaluator in this section to support the special form let. (See exercise 4.6.)

Answer: We have already defined the opreation let->combination which transforms a given let expression to a lambda form. As analyze can understand lambda expressions it is sufficient to add the following condition to analyze to achieve the result:

Exercise 4.23. Alyssa P. Hacker doesn't understand why analyze-sequence needs to be so complicated. All the other analysis procedures are straightforward transformations of the corresponding evaluation procedures (or eval clauses) in section 4.1.1. She expected analyze-sequence to look like this:

Eva Lu Ator explains to Alyssa that the version in the text does more of the work of evaluating a sequence at analysis time. Alyssa's sequence-execution procedure, rather than having the calls to the individual execution procedures built in, loops through the procedures in order to call them: In effect, although the individual expressions in the sequence have been analyzed, the sequence itself has not been.

Compare the two versions of analyze-sequence. For example, consider the common case (typical of procedure bodies) where the sequence has just one expression. What work will the execution procedure produced by Alyssa's program do? What about the execution procedure produced by the program in the text above? How do the two versions compare for a sequence with two expressions?

Answer: Alyssa's version produces an execution procedure whose body contains a call to execute-sequence. Execute-sequence is actually run only at runtime when the execution procedure runs.

The original version of analyze-sequence invokes execute-sequence *during* anaylsis. The results of the call are embedded in the execution procedure.

Exercise 4.24. Design and carry out some experiments to compare the speed of the original metacircular evaluator with the version in this section. Use your results to estimate the fraction of time that is spent in analysis versus execution for various procedures.

Answer: Experiment:


Without analyze: cpu time: 44838 real time: 45448 gc time: 160

With analyze: cpu time: 21961 real time: 22004 gc time: 116. There is a saving of around 50%.

SICP Section 3.5 Streams

Exercise 3.50. Complete the following definition, which generalizes stream-map to allow procedures that take multiple arguments, analogous to map in section 2.2.3, footnote 12.


Exercise 3.51. In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:

What does the interpreter print in response to evaluating each expression in the following sequence?


(stream-ref x 7) does not print 1 through 5 as show is not invoked thanks to memo-proc. Instead the stored results from previous invocations is reused.

Exercise 3.52. Consider the sequence of expressions

What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>) simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.


Without memo-proc:

Exercise 3.53. Without running the program, describe the elements of the stream defined by

Answer: This is the stream 1, 2, 4, 8, 16, 32, 64 etc. It represents the powers of 2: 20, 21, 22, 23, 24 etc.

The very first value is 1, the hard-coded start value for s. Subsequent elements are created by invoking add-streams. Add-streams creates a new stream whose car is the result of adding the car of its argument streams. The very first time around this yields 1 + 1 = 2. As the stream is defined self-referentially, the car of s becomes 2 following the first call to add-streams. subsequent calls to add-streams causes addition of 2 and 2, yielding 4; 4 and 4 yielding 8 and so on.

Exercise 3.54. Define a procedure mul-streams, analogous to add-streams, that produces the elementwise product of its two input streams. Use this together with the stream of integers to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:


Exercise 3.55. Define a procedure partial-sums that takes as argument a stream S and returns the stream whose elements are S0, S0 + S1, S0 + S1 + S2, .... For example, (partial-sums integers) should be the stream 1, 3, 6, 10, 15, ....

Answer: This is an interesting exercise. As with many other exercises related to Streams it becomes easier if the solution is initially worked out on paper. In this case, the key to the solution is realizing that partial sum at any point is the sum of the partial sum up to that point and the element at the point. This yields the following self-referential definition:

Exercise 3.56. 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 S 3) and (scale-stream 5 S).
  • These are all the elements of 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:

Then the required stream may be constructed with merge, as follows:

Fill in the missing expressions in the places marked <??> above.


Exercise 3.57. How many additions are performed when we compute the nth Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay ) simply as (lambda () ), without using the optimization provided by the memo-proc procedure described in section

Answer: First, let us define the Fibonacci series as a stream.

Tracing the flow on paper reveals that n-2 additions are required to calculate the nth Fibonacci number (counting n from 1).

Without memo-proc, each call to (stream-cdr fibs) would calculate the series from the beginning up to that point. This would exponentially increase the number of additions performed.

Exercise 3.58. Give an interpretation of the stream computed by the following procedure:

(Quotient is a primitive that returns the integer quotient of two integers.) What are the successive elements produced by (expand 1 7 10) ? What is produced by (expand 3 8 10) ?

Answer: This procedure produces the series of digits after the decimal point from the result of long division of the numerator (num) by the denominator (den) using the given radix base.

(expand 1 7 10) produces a series whose first six elements are 1, 4, 2, 8, 5 and 7. The rest of the elements is a repetition of these six. (1/7 = 0.1428571428...)

(expand 3 8 10) produces a series whose first three elements are 3, 7 and 5. The rest of the elements are all 0. (3/8 = 0.3750000...)

Exercise 3.59. In section 2.5.3 we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with power series, such as

represented as infinite streams. We will represent the series a0 + a1 x + a2 x2 + a3 x3 + ··· as the stream whose elements are the coefficients a0, a1, a2, a3, ....

a. The integral of the series a0 + a1 x + a2 x2 + a3 x3 + ··· is the series

where c is any constant. Define a procedure integrate-series that takes as input a stream a0, a1, a2, ... representing a power series and returns the stream a0, (1/2)a1, (1/3)a2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use integrate-series, we will cons on the appropriate constant.)

b. The function x |--> ex is its own derivative. This implies that ex and the integral of ex are the same series, except for the constant term, which is e0 = 1. Accordingly, we can generate the series for ex as

Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:


Exercise 3.60. With power series represented as streams of coefficients as in exercise 3.59, adding series is implemented by add-streams. Complete the definition of the following procedure for multiplying series:

You can test your procedure by verifying that sin2 x + cos2 x = 1, using the series from exercise 3.59.


Exercise 3.61. Let S be a power series (exercise 3.59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S · X = 1. Write S = 1 + SR where SR is the part of S after the constant term. Then we can solve for X as follows:

In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of SR times X. Use this idea to write a procedure invert-unit-series that computes 1/S for a power series S with constant term 1. You will need to use mul-series from exercise 3.60.


Exercise 3.62. Use the results of exercises 3.60 and 3.61 to define a procedure div-series that divides two power series. Div-series should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then div-series should signal an error.) Show how to use div-series together with the result of exercise 3.59 to generate the power series for tangent.


Exercise 3.63. Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:

Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?

Answer: In Louis' version all stream-cdr calls to a given square root stream executes the procedure sqrt-stream. This in turn creates a new stream object each time. Calls to sqrt-stream and subsequent creation of new stream objects are avoided by using the local variable.

The two versions would still differ in efficiency as the difference is not dependent on the use of memo-proc.

Exercise 3.64. Write a procedure stream-limit that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by


Exercise 3.65. Use the series

to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for . How rapidly do these sequences converge?

Answer: We'll start by defining the summands of the log2 stream.

1. Straightforward summation using partial-sums. The value of log2 oscillates between 0.6687714031754279 and 0.7163904507944756 after 20 iterations.

2. Log2 using Euler Transformation. Value converges to 0.6932106782106783 after 10 iterations.

3. Accelerated summation. Value converges to 0.6931488693329254 in 4 iterations.

Exercise 3.66. Examine the stream (pairs integers integers). Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)? the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.)

Answer: (1, 100) will be preceded by 197 pairs. (1, n) will be preceded by 2n-3 pairs.

(99, 100) will be preceded by 1 + 3(2^98 - 1) pairs. (n, n+1) preceded by 1 + 3(2^(n - 1) - 1) pairs.

(100, 100) will be preceded by 6 + (2^96 - 1) pairs. (n, n) will be preceded by 6 + (2^(n - 4) - 1) pairs.

Exercise 3.67. Modify the pairs procedure so that (pairs integers integers) will produce the stream of all pairs of integers (i,j) (without the condition i <= j). Hint: You will need to mix in an additional stream.


Exercise 3.68. Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S0,T0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:

Does this work? Consider what happens if we evaluate (pairs integers integers) using Louis's definition of pairs.

Answer: When (pairs s t) is evaluated a call is made to stream-map and pairs (arguments for interleave). The call to pairs in turn spawns another call to pairs and so on, causing an infinite loop.

Exercise 3.69. Write a procedure triples that takes three infinite streams, S, T, and U, and produces the stream of triples (Si,Tj,Uk) such that i <= j <= k. Use triples to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i <= j and i2 + j2 = k2.


Exercise 3.70. It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an ad hoc interleaving process. We can use a technique similar to the merge procedure of exercise 3.56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i1,j1) is less than (i2,j2) if W(i1,j1) < W(i2,j2). Write a procedure merge-weighted that is like merge, except that merge-weighted takes an additional argument weight, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.69 Using this, generalize pairs to a procedure weighted-pairs that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate

a. the stream of all pairs of positive integers (i,j) with i <= j ordered according to the sum i + j

b. the stream of all pairs of positive integers (i,j) with i <= j, where neither i nor j is divisible by 2, 3, or 5, and the pairs are ordered according to the sum 2 i + 3 j + 5 i j.


Exercise 3.71. Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called Ramanujan numbers, in honor of the mathematician Srinivasa Ramanujan.70 Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i3 + j3 (see exercise 3.70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five?


Next five after 1729 are 4104, 13832, 20683, 32832, 39312.

Exercise 3.72. In a similar way to exercise 3.71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written).


Exercise 3.73. v = v0 + (1/C)0ti dt + R i

Figure 3.33: An RC circuit and the associated signal-flow diagram.

We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an RC circuit consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in figure 3.33, whose structure is shown by the accompanying signal-flow diagram.

Write a procedure RC that models this circuit. RC should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v0 and produces as output the stream of voltages v. For example, you should be able to use RC to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating (define RC1 (RC 5 1 0.5)). This defines RC1 as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages.


Exercise 3.74. Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the zero crossings of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.) For example, a typical input signal with its associated zero-crossing signal would be

...1 2 1.5 1 0.5 -0.1 -2 -3 -2 -0.5 0.2 3 4 ...... 0 0 0 0 0 -1 0 0 0 0 1 0 0 ...

In Alyssa's system, the signal from the sensor is represented as a stream sense-data and the stream zero-crossings is the corresponding stream of zero crossings. Alyssa first writes a procedure sign-change-detector that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:

Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of stream-map from exercise 3.50:

Complete the program by supplying the indicated <expression>.


Exercise 3.75. Unfortunately, Alyssa's zero-crossing detector in exercise 3.74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:

This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to make-zero-crossings.)

Answer: I couldn't come up with an answer. If you know the answer and can explain it, do let me know.

Exercise 3.76. Eva Lu Ator has a criticism of Louis's approach in exercise 3.75. The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure smooth that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use smooth as a component to implement the zero-crossing detector in a more modular style.


Exercise 3.77. The integral procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section 3.5.2. Alternatively, we can give a definition of integral that is more like integers-starting-from (also in section 3.5.2):

When used in systems with loops, this procedure has the same problem as does our original version of integral. Modify the procedure so that it expects the integrand as a delayed argument and hence can be used in the solve procedure shown above.


Exercise 3.78.

Figure 3.35: Signal-flow diagram for the solution to a second-order linear differential equation.

Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation

The output stream, modeling y, is generated by a network that contains a loop. This is because the value of d2y/dt2 depends upon the values of y and dy/dt and both of these are determined by integrating d2y/dt2. The diagram we would like to encode is shown in figure 3.35. Write a procedure solve-2nd that takes as arguments the constants a, b, and dt and the initial values y0 and dy0 for y and dy/dt and generates the stream of successive values of y.


Exercise 3.79. Generalize the solve-2nd procedure of exercise 3.78 so that it can be used to solve general second-order differential equations d2 y/dt2 = f(dy/dt, y).


Exercise 3.80. A series RLC circuit consists of a resistor, a capacitor, and an inductor connected in series, as shown in figure 3.36. If R, L, and C are the resistance, inductance, and capacitance, then the relations between voltage (v) and current (i) for the three components are described by the equations

and the circuit connections dictate the relations

Combining these equations shows that the state of the circuit (summarized by vC, the voltage across the capacitor, and iL, the current in the inductor) is described by the pair of differential equations

The signal-flow diagram representing this system of differential equations is shown in figure 3.37.

Figure 3.36: A series RLC circuit.

Figure 3.37: A signal-flow diagram for the solution to a series RLC circuit.

Write a procedure RLC that takes as arguments the parameters R, L, and C of the circuit and the time increment dt. In a manner similar to that of the RC procedure of exercise 3.73, RLC should produce a procedure that takes the initial values of the state variables, vC0 and iL0, and produces a pair (using cons) of the streams of states vC and iL. Using RLC, generate the pair of streams that models the behavior of a series RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, dt = 0.1 second, and initial values iL0 = 0 amps and vC0 = 10 volts.


Exercise 3.81. Exercise 3.6 discussed generalizing the random-number generator to allow one to reset the random-number sequence so as to produce repeatable sequences of ``random'' numbers. Produce a stream formulation of this same generator that operates on an input stream of requests to generate a new random number or to reset the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution.


Exercise 3.82. Redo exercise 3.5 on Monte Carlo integration in terms of streams. The stream version of estimate-integral will not have an argument telling how many trials to perform. Instead, it will produce a stream of estimates based on successively more trials.