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:
Posts
No comments:
Post a Comment