Exercise 5.7. Use the simulator to test the machines you designed in exercise 5.4.
Answer:
1. Recursive Version
2. Iterative Version
Exercise 5.8. The following register-machine code is ambiguous, because the label here is defined more than once:
With the simulator as written, what will the contents of register a be when control reaches there? Modify the extract-labels procedure so that the assembler will signal an error if the same label name is used to indicate two different locations.
Answer:
Using the current implementation goto will direct control to the first occurrence of the label here in the sequence of instructions. This means that (assign a (const 3)) will get executed before control proceeds to the label there. Therefore register a will contain the value 3 at the end of execution.
This version of extract-labels checks if a given label is already present in the labels processed so far. If so it raises an error.
Exercise 5.9. The treatment of machine operations above permits them to operate on labels as well as on constants and the contents of registers. Modify the expression-processing procedures to enforce the condition that operations can be used only with registers and constants.
Answer:
I have moved the code that generates aprocs for an operation expression to a helper procedure. This procedure will raise and error if any of the operands of the expression is not a register or a constant.
Exercise 5.10. Design a new syntax for register-machine instructions and modify the simulator to use your new syntax. Can you implement your new syntax without changing any part of the simulator except the syntax procedures in this section?
Skipping.
Exercise 5.11. When we introduced save and restore in section 5.1.4, we didn't specify what would happen if you tried to restore a register that was not the last one saved, as in the sequence
There are several reasonable possibilities for the meaning of restore:
a. (restore y) puts into y the last value saved on the stack, regardless of what register that value came from. This is the way our simulator behaves. Show how to take advantage of this behavior to eliminate one instruction from the Fibonacci machine of section 5.1.4 (figure 5.12).
b. (restore y) puts into y the last value saved on the stack, but only if that value was saved from y; otherwise, it signals an error. Modify the simulator to behave this way. You will have to change save to put the register name on the stack along with the value.
c. (restore y) puts into y the last value saved from y regardless of what other registers were saved after y and not restored. Modify the simulator to behave this way. You will have to associate a separate stack with each register. You should make the initialize-stack operation initialize all the register stacks.
Answer:
a. The first two statements under the label afterfib-n-2 perform the following actions:
1) Transfer the value of val to n. This means copying fib(n - 2) to n.
2) Restore previously saved fib(n - 1) to val.
N and val are subsequently added to yield fib(n).
These two statements can be replaced with a single restore statement. Consider executing (restore n) instead of these two statements. As fib(n - 1) was the last value restored on the stack n will be assigned the value fib(n - 1). Val already contains fib(n - 2). We can proceed to add them together and still get fib(n).
b. Save instruction has been changed to pass the register name to the stack along with its value. The stack will maintain a list of register-name/value tuples. Pop has been changed to pass the target register name as a parameter. Stack will raise an error if the target register name is not the same as the name associated with the top value in the stack.
c. A new table named stack-table will maintain a list of register names and associated stacks. Allocate-register will create a new entry in this table each time a new register is allocated. Make-save will first get the appropriate stack from the machine before pushing the value in. Similarly make-restore will first retrieve the appropriate stack before popping the value.
Exercise 5.12. The simulator can be used to help determine the data paths required for implementing a machine with a given controller. Extend the assembler to store the following information in the machine model:
* a list of all instructions, with duplicates removed, sorted by instruction type (assign, goto, and so on);
* a list (without duplicates) of the registers used to hold entry points (these are the registers referenced by goto instructions);
* a list (without duplicates) of the registers that are saved or restored;
* for each register, a list (without duplicates) of the sources from which it is assigned (for example, the sources for register val in the factorial machine of figure 5.11 are (const 1) and ((op *) (reg n) (reg val))).
Extend the message-passing interface to the machine to provide access to this new information. To test your analyzer, define the Fibonacci machine from figure 5.12 and examine the lists you constructed.
Answer:
I am not quite satisfied with the way I have answered this question. The solution looks flaky and involved too many set! operations in my opinion. If you have any suggestions about how to improve the answer let me know.
Exercise 5.13. Modify the simulator so that it uses the controller sequence to determine what registers the machine has rather than requiring a list of registers as an argument to make-machine. Instead of pre-allocating the registers in make-machine, you can allocate them one at a time when they are first seen during assembly of the instructions.
Answer:Make-machine does not require the list of registers to be explicitly passed.
Update-insts will scan each instruction to find the registers used by that instruction. If that register has not already been installed update-insts will install it. Registers have to be allocated *before* installing the instruction execution procedures.
Find-registers-used will scan the given instruction to find the registers used.
Exercise 5.14. Measure the number of pushes and the maximum stack depth required to compute n! for various small values of n using the factorial machine shown in figure 5.11. From your data determine formulas in terms of n for the total number of push operations and the maximum stack depth used in computing n! for any n > 1. Note that each of these is a linear function of n and is thus determined by two constants. In order to get the statistics printed, you will have to augment the factorial machine with instructions to initialize the stack and print the statistics. You may want to also modify the machine so that it repeatedly reads a value for n, computes the factorial, and prints the result (as we did for the GCD machine in figure 5.4), so that you will not have to repeatedly invoke get-register-contents, set-register-contents!, and start.
Answer:
The total number of pushes and max depth of the stack for calculating n! is given by the formula 2(n - 1).
Exercise 5.15. Add instruction counting to the register machine simulation. That is, have the machine model keep track of the number of instructions executed. Extend the machine model's interface to accept a new message that prints the value of the instruction count and resets the count to zero.
Answer:
Exercise 5.16. Augment the simulator to provide for instruction tracing. That is, before each instruction is executed, the simulator should print the text of the instruction. Make the machine model accept trace-on and trace-off messages to turn tracing on and off.
Answer:
Exercise 5.17. Extend the instruction tracing of exercise 5.16 so that before printing an instruction, the simulator prints any labels that immediately precede that instruction in the controller sequence. Be careful to do this in a way that does not interfere with instruction counting (exercise 5.15). You will have to make the simulator retain the necessary label information.
Answer: Extract-labels will include labels as part of instructions.
Make-execution-procedure will create a special execution procedure for labels. These procedures will advance the program counter (pc) and return the name of the label.
Machine with tracing and counting. Count is not incremented if the instruction being executed is a label.
Exercise 5.18. Modify the make-register procedure of section 5.2.1 so that registers can be traced. Registers should accept messages that turn tracing on and off. When a register is traced, assigning a value to the register should print the name of the register, the old contents of the register, and the new contents being assigned. Extend the interface to the machine model to permit you to turn tracing on and off for designated machine registers.
Answer:
Exercise 5.19. Alyssa P. Hacker wants a breakpoint feature in the simulator to help her debug her machine designs. You have been hired to install this feature for her. She wants to be able to specify a place in the controller sequence where the simulator will stop and allow her to examine the state of the machine. You are to implement a procedure
that sets a breakpoint just before the nth instruction after the given label. For example,
installs a breakpoint in gcd-machine just before the assignment to register a. When the simulator reaches the breakpoint it should print the label and the offset of the breakpoint and stop executing instructions. Alyssa can then use get-register-contents and set-register-contents! to manipulate the state of the simulated machine. She should then be able to continue execution by saying
She should also be able to remove a specific breakpoint by means of
or to remove all breakpoints by means of
Answer: I had a LOT of fun doing this exercise. Sure it took time and I messed up in between. But in the end it was worth the time and energy spent. I present, my first "debugger" :)
Showing posts with label SICP. Show all posts
Showing posts with label SICP. Show all posts
Sunday, March 08, 2009
Wednesday, February 25, 2009
SICP Section 5.1 Designing Register Machines
Exercise 5.2. (and 5.1) Use the register-machine language to describe the iterative factorial machine of exercise 5.1.
Answer:
Exercise 5.3. Design a machine to compute square roots using Newton's method, as described in section 1.1.7:
Begin by assuming that good-enough? and improve operations are available as primitives. Then show how to expand these in terms of arithmetic operations. Describe each version of the sqrt machine design by drawing a data-path diagram and writing a controller definition in the register-machine language.
Answer: I am skipping the data-path diagrams for the three different versions of sqrt. Controller definitions of the three versions in the register-machine language follow. All three versions assume that abs, square and average are available as primitive operations along with - and /.
Version 1.
Version 2. In this version good-enough? is expanded using arithmetic operations.
Version 3. Improve is also expanded using arithmetic operations.
Exercise 5.4. Specify register machines that implement each of the following procedures. For each machine, write a controller instruction sequence and draw a diagram showing the data paths.
a. Recursive exponentiation:
b. Iterative exponentiation:
Answer:
a. Recursive exponentiation.
b. Iterative exponentiation.
Exercise 5.5. Hand-simulate the factorial and Fibonacci machines, using some nontrivial input (requiring execution of at least one recursive call). Show the contents of the stack at each significant point in the execution.
Answer: (factorial 3)
Init:
continue = fact-done; n = 3;
Iteration round 1.
Test (= n 1) fails.
Stack: continue => fact-done; n=> 3.
n = 2; continue = after-fact.
Iteration round 2.
Test (= n 1) fails.
Stack: continue => after-fact, fact-done; n=> 2, 3.
n = 1; continue = after-fact.
Iteration round 3.
Test (= n 1) succeeds. Proceed to base-case
val = 1; proceed to after-fact
After-fact round 1.
n <= 2. continue <= after-fact.
Stack: continue => fact-done; n=> 3.
val = 2 * 1 = 2
After-fact round 2.
n <= 3. continue <= fact-done.
Stack: empty
val = 3 * 2 = 6
Proceed to fact-done
Exercise 5.6. Ben Bitdiddle observes that the Fibonacci machine's controller sequence has an extra save and an extra restore, which can be removed to make a faster machine. Where are these instructions?
Answer: The redundant save and restore statements occur in the set of instructions labeled afterfib-n-1. The (restore continue) and (save continue) statements that occur at the top can be removed as the value of continue will never change between restore and save calls. The machine can be now re-written as follows:
Answer:
Exercise 5.3. Design a machine to compute square roots using Newton's method, as described in section 1.1.7:
Begin by assuming that good-enough? and improve operations are available as primitives. Then show how to expand these in terms of arithmetic operations. Describe each version of the sqrt machine design by drawing a data-path diagram and writing a controller definition in the register-machine language.
Answer: I am skipping the data-path diagrams for the three different versions of sqrt. Controller definitions of the three versions in the register-machine language follow. All three versions assume that abs, square and average are available as primitive operations along with - and /.
Version 1.
Version 2. In this version good-enough? is expanded using arithmetic operations.
Version 3. Improve is also expanded using arithmetic operations.
Exercise 5.4. Specify register machines that implement each of the following procedures. For each machine, write a controller instruction sequence and draw a diagram showing the data paths.
a. Recursive exponentiation:
b. Iterative exponentiation:
Answer:
a. Recursive exponentiation.
b. Iterative exponentiation.
Exercise 5.5. Hand-simulate the factorial and Fibonacci machines, using some nontrivial input (requiring execution of at least one recursive call). Show the contents of the stack at each significant point in the execution.
Answer: (factorial 3)
Init:
continue = fact-done; n = 3;
Iteration round 1.
Test (= n 1) fails.
Stack: continue => fact-done; n=> 3.
n = 2; continue = after-fact.
Iteration round 2.
Test (= n 1) fails.
Stack: continue => after-fact, fact-done; n=> 2, 3.
n = 1; continue = after-fact.
Iteration round 3.
Test (= n 1) succeeds. Proceed to base-case
val = 1; proceed to after-fact
After-fact round 1.
n <= 2. continue <= after-fact.
Stack: continue => fact-done; n=> 3.
val = 2 * 1 = 2
After-fact round 2.
n <= 3. continue <= fact-done.
Stack: empty
val = 3 * 2 = 6
Proceed to fact-done
Exercise 5.6. Ben Bitdiddle observes that the Fibonacci machine's controller sequence has an extra save and an extra restore, which can be removed to make a faster machine. Where are these instructions?
Answer: The redundant save and restore statements occur in the set of instructions labeled afterfib-n-1. The (restore continue) and (save continue) statements that occur at the top can be removed as the value of continue will never change between restore and save calls. The machine can be now re-written as follows:
Thursday, February 19, 2009
SICP Section 4.4 Logic Programming
Exercise 4.55. Give simple queries that retrieve the following information from the data base:
a. all people supervised by Ben Bitdiddle;
b. the names and jobs of all people in the accounting division;
c. the names and addresses of all people who live in Slumerville.
Answer: a. All people supervised by Ben Bitdiddle.
b. The names and jobs of all people in the accounting division.
c. The names and addresses of all people who line in Slumerville.
Exercise 4.56. Formulate compound queries that retrieve the following information:
a. the names of all people who are supervised by Ben Bitdiddle, together with their addresses;
b. all people whose salary is less than Ben Bitdiddle's, together with their salary and Ben Bitdiddle's salary;
c. all people who are supervised by someone who is not in the computer division, together with the supervisor's name and job.
Answer: a.
b.
c.
Exercise 4.57. Define a rule that says that person 1 can replace person 2 if either person 1 does the same job as person 2 or someone who does person 1's job can also do person 2's job, and if person 1 and person 2 are not the same person. Using your rule, give queries that find the following:
a. all people who can replace Cy D. Fect;
b. all people who can replace someone who is being paid more than they are, together with the two salaries.
Answer:
a.
b.
Exercise 4.58. 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.
Answer:
Exercise 4.59. 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:
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.
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 specifying 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.
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?
Answer: a.
b.
c.
Exercise 4.60. By giving the query
Alyssa P. Hacker is able to find people who live near her, with whom she can ride to work. On the other hand, when she tries to find all pairs of people who live near each other by querying
she notices that each pair of people who live near each other is listed twice; for example,
Why does this happen? Is there a way to find a list of people who live near each other, in which each pair appears only once? Explain.
Answer: Lives-near works by showing all entries in the database that matches a certain pattern. If person1 and person2 match the pattern by virtue of being neighbors then the reverse is also true and therefore person2 and person1 also meet the pattern. There is no way to prevent this given the current definition of the rule.
The rule can be changed to add an artificial constraint to avoid the names being printed twice. For instance we can compare the lengths of the names of the people and print only those results where the name of person1 is longer than the name of person2.
String>? is a built in operator which compares strings according to the order of the characters they contain.
Exercise 4.61. The following rules implement a next-to relation that finds adjacent elements of a list:
What will the response be to the following queries?
Answer:
Exercise 4.62. Define rules to implement the last-pair operation of exercise 2.17, which returns a list containing the last element of a nonempty list. Check your rules on queries such as (last-pair (3) ?x), (last-pair (1 2 3) ?x), and (last-pair (2 ?x) (3)). Do your rules work correctly on queries such as (last-pair ?x (3)) ?
Answer:
Exercise 4.63. The following data base (see Genesis 4) traces the genealogy of the descendants of Ada back to Adam, by way of Cain:
Formulate rules such as ``If S is the son of F, and F is the son of G, then S is the grandson of G'' and ``If W is the wife of M, and S is the son of W, then S is the son of M'' (which was supposedly more true in biblical times than today) that will enable the query system to find the grandson of Cain; the sons of Lamech; the grandsons of Methushael. (See exercise 4.69 for some rules to deduce more complicated relationships.)
Answer:
Exercise 4.64. Louis Reasoner mistakenly deletes the outranked-by rule (section 4.4.1) from the data base. When he realizes this, he quickly reinstalls it. Unfortunately, he makes a slight change in the rule, and types it in as
Just after Louis types this information into the system, DeWitt Aull comes by to find out who outranks Ben Bitdiddle. He issues the query
After answering, the system goes into an infinite loop. Explain why.
Answer: I'll use the procedure explained in section 4.4.2 (pg. 460) to explore how this query is executed.
1. Unify query with the conclusion of the rule to form, if successful, an extension of the original frame. By unifying the query (outranked-by (Bitiddle Ben) ?who) with the conclusion of the rule (outranked-by ?staff-person ?boss) we get a frame where ?staff-person and ?boss are bound to (Bitiddle Ben) and ?who respectively.
2. Relative to the extended frame, evaluate the query formed by the body of the rule. The query formed by the body of the rule in this case is:
The first argument to or immediately produces a match from the database: (supervisor (Bitiddle Ben) (Warbucks Oliver)). This result is printed. The second argument to or is the and sub-query, the first part of which uses the outranked-by rule. This leads the interpreter to again evaluate the rule body resulting in a frame where ?staff-person and ?boss are bound to to ?middle-manager and ?who respectively. This once again leads to the evaluation of outranked-by and so on infinitely.
I can see how the infinite loop is triggered. What I don't understand is how the first part of or, i.e., (superior ?staff-person ?boss) is not matched in these infinite calls and their results printed (like how the first result got printed). Perhaps I'll be able to explain it once I study how the query interpreter is implemented.
Exercise 4.65. Cy D. Fect, looking forward to the day when he will rise in the organization, gives a query to find all the wheels (using the wheel rule of section 4.4.1):
To his surprise, the system responds
Why is Oliver Warbucks listed four times?
Answer: Once again I'll use the procedure explained in section 4.4.2 (pg. 460) to explore how this query is executed.
1. Unify query with the conclusion of the rule to form, if successful, an extension of the original frame. By unifying the query (wheel ?who) with the conclusion of the rule (wheel ?person) we get a frame where ?person is bound to ?who.
2. Relative to the extended frame, evaluate the query formed by the body of the rule. The query formed by the body of the rule in this case is:
This query produces multiple matches, one each for every instance of a supervisor-employee pair where the supervisor reports to ?person.
The rule conclusion is instantiated with the value for ?person for every result produced by the query. Therefore we find that Oliver Warbuck's name pops up four times.
Exercise 4.66. Ben has been generalizing the query system to provide statistics about the company. For example, to find the total salaries of all the computer programmers one will be able to say
In general, Ben's new system allows expressions of the form
where accumulation-function can be things like sum, average, or maximum. Ben reasons that it should be a cinch to implement this. He will simply feed the query pattern to qeval. This will produce a stream of frames. He will then pass this stream through a mapping function that extracts the value of the designated variable from each frame in the stream and feed the resulting stream of values to the accumulation function. Just as Ben completes the implementation and is about to try it out, Cy walks by, still puzzling over the wheel query result in exercise 4.65. When Cy shows Ben the system's response, Ben groans, ``Oh, no, my simple accumulation scheme won't work!''
What has Ben just realized? Outline a method he can use to salvage the situation.
Answer: Consider the following application of Ben's new system:
This query is meant to calculate the sum of the salaries paid to "wheels". As we saw in exercise 4.65 the (wheel ?who) query will repeat Oliver Warbuck's name. Consequently his salary will be added up multiple times. This is the error Ben has realized - that queries can repeat the results.
One way to solve Ben's problem would be to ensure that the query pattern produces unique results. This can be done by implementing the equivalent of distinct? for the query results.
Exercise 4.68. Define rules to implement the reverse operation of exercise 2.18, which returns a list containing the same elements as a given list in reverse order. (Hint: Use append-to-form.) Can your rules answer both (reverse (1 2 3) ?x) and (reverse ?x (1 2 3)) ?
Answer:
(reverse (1 2 3) ?x) returns (reverse (1 2 3) (3 2 1)).
(reverse ?x (1 2 3)) prints (reverse (3 2 1) (1 2 3)) and goes into an infinite loop if the order of the reverse rules is as shown. If the second rule is added first then the evaluator goes into infinite loop without printing any result.
Exercise 4.69. Beginning with the data base and the rules you formulated in exercise 4.63, devise a rule for adding ``greats'' to a grandson relationship. This should enable the system to deduce that Irad is the great-grandson of Adam, or that Jabal and Jubal are the great-great-great-great-great-grandsons of Adam. (Hint: Represent the fact about Irad, for example, as ((great grandson) Adam Irad). Write rules that determine if a list ends in the word grandson. Use this to express a rule that allows one to derive the relationship ((great . ?rel) ?x ?y), where ?rel is a list ending in grandson.) Check your rules on queries such as ((great grandson) ?g ?ggs) and (?relationship Adam Irad).
Answer:
Exercise 4.70. What is the purpose of the let bindings in the procedures add-assertion! and add-rule! ? What would be wrong with the following implementation of add-assertion! ? Hint: Recall the definition of the infinite stream of ones in section 3.5.2: (define ones (cons-stream 1 ones)).
Answer: The implementation given in the question uses THE-ASSERTIONS in the cons-stream operation. This defines THE-ASSERTIONS recursively as a combination of the given assertion and THE-ASSERTIONS. Such a definition would make THE-ASSERTIONS an infinite stream (whose stream-car is the new assertion) rather than a finite stream of assertions. The original definition creates a finite stream by joining the given assertion with the empty stream.
Exercise 4.71. Louis Reasoner wonders why the simple-query and disjoin procedures (section 4.4.4.2) are implemented using explicit delay operations, rather than being defined as follows:
Can you give examples of queries where these simpler definitions would lead to undesirable behavior?
Answer: The call to delay application of rules will prevent infinite looping in cases where the rules recursively rely on themselves and/or assertions. In such cases the delay will ensure that results matching the assertions in the database are printed before the rules get evaluated rather than going into an infinite loop immediately.
Exercise 4.72. Why do disjoin and stream-flatmap interleave the streams rather than simply append them? Give examples that illustrate why interleaving works better. (Hint: Why did we use interleave in section 3.5.3?)
Answer: The hint is sufficient to get you started towards the answer. Interleaving was originally introduced to handle multiple infinite streams. Interleaving prevented any one stream being explored infinitely and ensured that values from all component streams were explored in turn. These reasons are still valid here in the case of stream-flatmap and disjoin.
Exercise 4.73. Why does flatten-stream use delay explicitly? What would be wrong with defining it as follows:
Answer: Flatten-stream internally calls the interleave procedure. The first argument to interleave is the stream-car of the input stream. The second argument is the result of flattening the stream-cdr of the input stream. In the absence of an explicit delay the second argument is evaluated before being passed to interleave. As the second argument recursively calls flatten-stream this leads to a loop. The loop will not terminate until the input stream is exhausted. In case of infinite streams this leads to an infinite loop.
Exercise 4.74. Alyssa P. Hacker proposes to use a simpler version of stream-flatmap in negate, lisp-value, and find-assertions. She observes that the procedure that is mapped over the frame stream in these cases always produces either the empty stream or a singleton stream, so no interleaving is needed when combining these streams.
a. Fill in the missing expressions in Alyssa's program.
b. Does the query system's behavior change if we change it in this way?
Answer: a.
b. The changes will not affect the behavior of the query system. The end result of simple-stream-flatmap remains a stream of singleton streams in the same order as before the changes. Therefore the overall behavior should remain unchanged.
Exercise 4.75. Implement for the query language a new special form called unique. Unique should succeed if there is precisely one item in the data base satisfying a specified query. For example,
should print the one-item stream
since Ben is the only computer wizard, and
should print the empty stream, since there is more than one computer programmer. Moreover,
should list all the jobs that are filled by only one person, and the people who fill them.
There are two parts to implementing unique. The first is to write a procedure that handles this special form, and the second is to make qeval dispatch to that procedure. The second part is trivial, since qeval does its dispatching in a data-directed way. If your procedure is called uniquely-asserted, all you need to do is
and qeval will dispatch to this procedure for every query whose type (car) is the symbol unique.
The real problem is to write the procedure uniquely-asserted. This should take as input the contents (cdr) of the unique query, together with a stream of frames. For each frame in the stream, it should use qeval to find the stream of all extensions to the frame that satisfy the given query. Any stream that does not have exactly one item in it should be eliminated. The remaining streams should be passed back to be accumulated into one big stream that is the result of the unique query. This is similar to the implementation of the not special form.
Test your implementation by forming a query that lists all people who supervise precisely one person.
Answer:
Exercise 4.76. Our implementation of and as a series combination of queries (figure 4.5) is elegant, but it is inefficient because in processing the second query of the and we must scan the data base for each frame produced by the first query. If the data base has N elements, and a typical query produces a number of output frames proportional to N (say N/k), then scanning the data base for each frame produced by the first query will require N2/k calls to the pattern matcher. Another approach would be to process the two clauses of the and separately, then look for all pairs of output frames that are compatible. If each query produces N/k output frames, then this means that we must perform N2/k2 compatibility checks -- a factor of k fewer than the number of matches required in our current method.
Devise an implementation of and that uses this strategy. You must implement a procedure that takes two frames as inputs, checks whether the bindings in the frames are compatible, and, if so, produces a frame that merges the two sets of bindings. This operation is similar to unification.
Answer:
Note: I am skipping the last three problems of this chapter and moving on to Chapter 5. I will revisit them after completing Chapter 5.
b. the names and jobs of all people in the accounting division;
c. the names and addresses of all people who live in Slumerville.
Answer: a. All people supervised by Ben Bitdiddle.
b. The names and jobs of all people in the accounting division.
c. The names and addresses of all people who line in Slumerville.
Exercise 4.56. Formulate compound queries that retrieve the following information:
a. the names of all people who are supervised by Ben Bitdiddle, together with their addresses;
b. all people whose salary is less than Ben Bitdiddle's, together with their salary and Ben Bitdiddle's salary;
c. all people who are supervised by someone who is not in the computer division, together with the supervisor's name and job.
Answer: a.
b.
c.
Exercise 4.57. Define a rule that says that person 1 can replace person 2 if either person 1 does the same job as person 2 or someone who does person 1's job can also do person 2's job, and if person 1 and person 2 are not the same person. Using your rule, give queries that find the following:
a. all people who can replace Cy D. Fect;
b. all people who can replace someone who is being paid more than they are, together with the two salaries.
Answer:
a.
b.
Exercise 4.58. 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.
Answer:
Exercise 4.59. 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:
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.
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 specifying 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.
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?
Answer: a.
b.
c.
Exercise 4.60. By giving the query
Alyssa P. Hacker is able to find people who live near her, with whom she can ride to work. On the other hand, when she tries to find all pairs of people who live near each other by querying
she notices that each pair of people who live near each other is listed twice; for example,
Why does this happen? Is there a way to find a list of people who live near each other, in which each pair appears only once? Explain.
Answer: Lives-near works by showing all entries in the database that matches a certain pattern. If person1 and person2 match the pattern by virtue of being neighbors then the reverse is also true and therefore person2 and person1 also meet the pattern. There is no way to prevent this given the current definition of the rule.
The rule can be changed to add an artificial constraint to avoid the names being printed twice. For instance we can compare the lengths of the names of the people and print only those results where the name of person1 is longer than the name of person2.
String>? is a built in operator which compares strings according to the order of the characters they contain.
Exercise 4.61. The following rules implement a next-to relation that finds adjacent elements of a list:
What will the response be to the following queries?
Answer:
Exercise 4.62. Define rules to implement the last-pair operation of exercise 2.17, which returns a list containing the last element of a nonempty list. Check your rules on queries such as (last-pair (3) ?x), (last-pair (1 2 3) ?x), and (last-pair (2 ?x) (3)). Do your rules work correctly on queries such as (last-pair ?x (3)) ?
Answer:
Exercise 4.63. The following data base (see Genesis 4) traces the genealogy of the descendants of Ada back to Adam, by way of Cain:
Formulate rules such as ``If S is the son of F, and F is the son of G, then S is the grandson of G'' and ``If W is the wife of M, and S is the son of W, then S is the son of M'' (which was supposedly more true in biblical times than today) that will enable the query system to find the grandson of Cain; the sons of Lamech; the grandsons of Methushael. (See exercise 4.69 for some rules to deduce more complicated relationships.)
Answer:
Exercise 4.64. Louis Reasoner mistakenly deletes the outranked-by rule (section 4.4.1) from the data base. When he realizes this, he quickly reinstalls it. Unfortunately, he makes a slight change in the rule, and types it in as
Just after Louis types this information into the system, DeWitt Aull comes by to find out who outranks Ben Bitdiddle. He issues the query
After answering, the system goes into an infinite loop. Explain why.
Answer: I'll use the procedure explained in section 4.4.2 (pg. 460) to explore how this query is executed.
1. Unify query with the conclusion of the rule to form, if successful, an extension of the original frame. By unifying the query (outranked-by (Bitiddle Ben) ?who) with the conclusion of the rule (outranked-by ?staff-person ?boss) we get a frame where ?staff-person and ?boss are bound to (Bitiddle Ben) and ?who respectively.
2. Relative to the extended frame, evaluate the query formed by the body of the rule. The query formed by the body of the rule in this case is:
The first argument to or immediately produces a match from the database: (supervisor (Bitiddle Ben) (Warbucks Oliver)). This result is printed. The second argument to or is the and sub-query, the first part of which uses the outranked-by rule. This leads the interpreter to again evaluate the rule body resulting in a frame where ?staff-person and ?boss are bound to to ?middle-manager and ?who respectively. This once again leads to the evaluation of outranked-by and so on infinitely.
I can see how the infinite loop is triggered. What I don't understand is how the first part of or, i.e., (superior ?staff-person ?boss) is not matched in these infinite calls and their results printed (like how the first result got printed). Perhaps I'll be able to explain it once I study how the query interpreter is implemented.
Exercise 4.65. Cy D. Fect, looking forward to the day when he will rise in the organization, gives a query to find all the wheels (using the wheel rule of section 4.4.1):
To his surprise, the system responds
Why is Oliver Warbucks listed four times?
Answer: Once again I'll use the procedure explained in section 4.4.2 (pg. 460) to explore how this query is executed.
1. Unify query with the conclusion of the rule to form, if successful, an extension of the original frame. By unifying the query (wheel ?who) with the conclusion of the rule (wheel ?person) we get a frame where ?person is bound to ?who.
2. Relative to the extended frame, evaluate the query formed by the body of the rule. The query formed by the body of the rule in this case is:
This query produces multiple matches, one each for every instance of a supervisor-employee pair where the supervisor reports to ?person.
The rule conclusion is instantiated with the value for ?person for every result produced by the query. Therefore we find that Oliver Warbuck's name pops up four times.
Exercise 4.66. Ben has been generalizing the query system to provide statistics about the company. For example, to find the total salaries of all the computer programmers one will be able to say
In general, Ben's new system allows expressions of the form
where accumulation-function can be things like sum, average, or maximum. Ben reasons that it should be a cinch to implement this. He will simply feed the query pattern to qeval. This will produce a stream of frames. He will then pass this stream through a mapping function that extracts the value of the designated variable from each frame in the stream and feed the resulting stream of values to the accumulation function. Just as Ben completes the implementation and is about to try it out, Cy walks by, still puzzling over the wheel query result in exercise 4.65. When Cy shows Ben the system's response, Ben groans, ``Oh, no, my simple accumulation scheme won't work!''
What has Ben just realized? Outline a method he can use to salvage the situation.
Answer: Consider the following application of Ben's new system:
This query is meant to calculate the sum of the salaries paid to "wheels". As we saw in exercise 4.65 the (wheel ?who) query will repeat Oliver Warbuck's name. Consequently his salary will be added up multiple times. This is the error Ben has realized - that queries can repeat the results.
One way to solve Ben's problem would be to ensure that the query pattern produces unique results. This can be done by implementing the equivalent of distinct? for the query results.
Exercise 4.68. Define rules to implement the reverse operation of exercise 2.18, which returns a list containing the same elements as a given list in reverse order. (Hint: Use append-to-form.) Can your rules answer both (reverse (1 2 3) ?x) and (reverse ?x (1 2 3)) ?
Answer:
(reverse (1 2 3) ?x) returns (reverse (1 2 3) (3 2 1)).
(reverse ?x (1 2 3)) prints (reverse (3 2 1) (1 2 3)) and goes into an infinite loop if the order of the reverse rules is as shown. If the second rule is added first then the evaluator goes into infinite loop without printing any result.
Exercise 4.69. Beginning with the data base and the rules you formulated in exercise 4.63, devise a rule for adding ``greats'' to a grandson relationship. This should enable the system to deduce that Irad is the great-grandson of Adam, or that Jabal and Jubal are the great-great-great-great-great-grandsons of Adam. (Hint: Represent the fact about Irad, for example, as ((great grandson) Adam Irad). Write rules that determine if a list ends in the word grandson. Use this to express a rule that allows one to derive the relationship ((great . ?rel) ?x ?y), where ?rel is a list ending in grandson.) Check your rules on queries such as ((great grandson) ?g ?ggs) and (?relationship Adam Irad).
Answer:
Exercise 4.70. What is the purpose of the let bindings in the procedures add-assertion! and add-rule! ? What would be wrong with the following implementation of add-assertion! ? Hint: Recall the definition of the infinite stream of ones in section 3.5.2: (define ones (cons-stream 1 ones)).
Answer: The implementation given in the question uses THE-ASSERTIONS in the cons-stream operation. This defines THE-ASSERTIONS recursively as a combination of the given assertion and THE-ASSERTIONS. Such a definition would make THE-ASSERTIONS an infinite stream (whose stream-car is the new assertion) rather than a finite stream of assertions. The original definition creates a finite stream by joining the given assertion with the empty stream.
Exercise 4.71. Louis Reasoner wonders why the simple-query and disjoin procedures (section 4.4.4.2) are implemented using explicit delay operations, rather than being defined as follows:
Can you give examples of queries where these simpler definitions would lead to undesirable behavior?
Answer: The call to delay application of rules will prevent infinite looping in cases where the rules recursively rely on themselves and/or assertions. In such cases the delay will ensure that results matching the assertions in the database are printed before the rules get evaluated rather than going into an infinite loop immediately.
Exercise 4.72. Why do disjoin and stream-flatmap interleave the streams rather than simply append them? Give examples that illustrate why interleaving works better. (Hint: Why did we use interleave in section 3.5.3?)
Answer: The hint is sufficient to get you started towards the answer. Interleaving was originally introduced to handle multiple infinite streams. Interleaving prevented any one stream being explored infinitely and ensured that values from all component streams were explored in turn. These reasons are still valid here in the case of stream-flatmap and disjoin.
Exercise 4.73. Why does flatten-stream use delay explicitly? What would be wrong with defining it as follows:
Answer: Flatten-stream internally calls the interleave procedure. The first argument to interleave is the stream-car of the input stream. The second argument is the result of flattening the stream-cdr of the input stream. In the absence of an explicit delay the second argument is evaluated before being passed to interleave. As the second argument recursively calls flatten-stream this leads to a loop. The loop will not terminate until the input stream is exhausted. In case of infinite streams this leads to an infinite loop.
Exercise 4.74. Alyssa P. Hacker proposes to use a simpler version of stream-flatmap in negate, lisp-value, and find-assertions. She observes that the procedure that is mapped over the frame stream in these cases always produces either the empty stream or a singleton stream, so no interleaving is needed when combining these streams.
a. Fill in the missing expressions in Alyssa's program.
b. Does the query system's behavior change if we change it in this way?
Answer: a.
b. The changes will not affect the behavior of the query system. The end result of simple-stream-flatmap remains a stream of singleton streams in the same order as before the changes. Therefore the overall behavior should remain unchanged.
Exercise 4.75. Implement for the query language a new special form called unique. Unique should succeed if there is precisely one item in the data base satisfying a specified query. For example,
should print the one-item stream
since Ben is the only computer wizard, and
should print the empty stream, since there is more than one computer programmer. Moreover,
should list all the jobs that are filled by only one person, and the people who fill them.
There are two parts to implementing unique. The first is to write a procedure that handles this special form, and the second is to make qeval dispatch to that procedure. The second part is trivial, since qeval does its dispatching in a data-directed way. If your procedure is called uniquely-asserted, all you need to do is
and qeval will dispatch to this procedure for every query whose type (car) is the symbol unique.
The real problem is to write the procedure uniquely-asserted. This should take as input the contents (cdr) of the unique query, together with a stream of frames. For each frame in the stream, it should use qeval to find the stream of all extensions to the frame that satisfy the given query. Any stream that does not have exactly one item in it should be eliminated. The remaining streams should be passed back to be accumulated into one big stream that is the result of the unique query. This is similar to the implementation of the not special form.
Test your implementation by forming a query that lists all people who supervise precisely one person.
Answer:
Exercise 4.76. Our implementation of and as a series combination of queries (figure 4.5) is elegant, but it is inefficient because in processing the second query of the and we must scan the data base for each frame produced by the first query. If the data base has N elements, and a typical query produces a number of output frames proportional to N (say N/k), then scanning the data base for each frame produced by the first query will require N2/k calls to the pattern matcher. Another approach would be to process the two clauses of the and separately, then look for all pairs of output frames that are compatible. If each query produces N/k output frames, then this means that we must perform N2/k2 compatibility checks -- a factor of k fewer than the number of matches required in our current method.
Devise an implementation of and that uses this strategy. You must implement a procedure that takes two frames as inputs, checks whether the bindings in the frames are compatible, and, if so, produces a frame that merges the two sets of bindings. This operation is similar to unification.
Answer:
Note: I am skipping the last three problems of this chapter and moving on to Chapter 5. I will revisit them after completing Chapter 5.
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:
Answer:
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:
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.
Answer:
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.
Parse 2: The student has the cat. The professor is lecturing the student.
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.
Parse 4: The student has the cat. However it is not clear if the student has brought the cat to the classroom.
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.
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.
Answer:
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! ?
Answer:
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:
Answer:
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.
Answer:
Answer:
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.''
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.
Answer:
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
lectures
to the student
in the class with the cat
Parse 2: The student has the cat. The professor is lecturing the student.
The professor
lectures
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
lectures
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
lectures
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
lectures
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.
Answer:
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! ?
Answer:
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:
Answer:
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.
Answer:
Subscribe to:
Posts (Atom)
Posts
