Tuesday, November 17, 2009

Reading Notes #2: Passing functions as arguments to higher order functions

Does Erlang allow you to pass functions (not "funs" or anonymous functions) as arguments to higher order functions? I was under the impression that it doesn't. To find out I tweeted a question about the same. After looking at the answers I decided to rephrase the question with the help of a concrete example. Here it goes:

Step 1: Define a function add_one in a module named test.

Step 2: Start the erlang shell and try to use this function.

As you can see I have tried three different combinations. Line #3 shows a call to the higher order function lists:map passing in the qualified name of the add_one function as first argument. The shell throws an error.

In Line #4 I wrap test:add_one inside a fun and it works.

In Line #5 I replicate the code of add_one inside an anonymous fun and everything works fine.

Contrast this with say, Python.

Definition:

Usage:

Now I'll repeat the question: Does Erlang allow you to pass functions (not "funs" or anonymous functions) as arguments to higher order functions? Or am I missing something?

Please share your thoughts in the comments.

Update #1:
Got an answer. There is a way to do it. It still involves using the fun keyword.
Update #2:
Got another answer which does *not* use fun. The syntax is just a little different. Thanks to Justin Sheehy.

Wednesday, October 14, 2009

Reading Notes #1

I have been reading Joe Armstrong's paper "Making reliable distributed systems in the presence of software errors" and making notes as I go. In chapter 3 the author gives examples of how Erlang handles higher order functions. One of them is a "generator" function.

Line 1 defines an Adder that returns another function with X bound to the input to Adder. In line 2 we create a specific adder - in this case a function that adds 10 to its input. I think line 3 was meant to show how the specific adder created in line 2 could be invoked. If Adder10 were to be called with 5 as argument it would return 15. Instead Adder is invoked again and the result shown is not correct as Adder(10) would return a generator, not 15. I think the snippet can be modified thus:

Monday, August 10, 2009

Ticket #11627

Logged another Django ticket related to test client. I find that most of my Django pet peeves are related to two areas: the ORM and testing framework.

Thursday, July 23, 2009

DRY Logging in Django

I have found custom logging a very useful tool for dealing with production issues. Especially when the users are not easily reachable. I recently configured custom logging messages for a Django project I have been working on. As logging is usually only initiated once per application I chose to do it in my settings.py. The code looked something like this:

This configuration worked out well in development. However I maintain a separate settings file for production, production.py. Production.py merely imports everything from settings.py and selectively overrides some of the attributes (set DEBUG = False, for instance).

My problem was that I wanted the production logs to be written to a different location and perhaps even use a different handler. I could not think of a good way to do this without calling the logging code fragment again in production.py. I wrote a utility function to do this (configure_logging(filename)). This reduced code repetition but revealed another problem. When production.py imports everything from settings.py it triggers logging to be configured once using the LOG_FILENAME attribute used in development and then *again* using the LOG_FILENAME attribute used in production.

This was ugly. For one there is no need to configure logging twice; for another the initial configuration throws an error if the path described by LOG_FILENAME in development is not present in the production machine.

I wasn't sure how to proceed and I posed this question at Stack Overflow. I got an answer suggesting to switch LOG_FILENAME based on the DEBUG attribute. Something like this:

This looked good, but almost immediately revealed a problem. DEBUG is overridden *inside* production.py whereas this code snippet is inside settings.py. Consequently when the above given snippet gets executed DEBUG is still True and LOG_FILENAME will be pointed at the development environment.

I eventually found a solution from an answer to a different question. User Bluebird75 suggested using the 'module singleton' pattern to ensure that logging is only configured once. I extended his(?) suggestion to come up with the following solution:

The singleton module ensures that logging is only configured once. As this module resides within the app directory Django would already have loaded settings before this module is loaded, thereby ensuring the presence of settings.LOG_FILENAME. I can add as many settings files as I want and all I have to do is override the LOG_FILENAME attribute in each file.

Tuesday, July 21, 2009

Ticket #11475

Logged a Django bug related to test client. Part of my continuing series of adventures in Django.

Sunday, July 12, 2009

Learning to write smaller sentences

I have started to use Twitter. There are many things I'd like to write about that do not merit a blog post. Twitter is the right place to scribble in such cases. I hope to be a more regular writer using the new medium :)

Monday, March 23, 2009

Quick and dirty serial numbers across pages in Django templates

Update:

Scratch that. I just learned that this can be done in a much simpler way:

I recently had to write a template for a paginated view which displayed a serial number for each object in the object_list. I normally use forloop.counter for general purpose serial numbers. However this did not work with paginated views as the counter gets reset in each page. This caused the serial numbers to go from 1 to #-of-results-in-the-page and then repeat. I wrote a filter to tackle this problem.

The code (add to your filters file under ./templatetags/):

And the template snippet:

The adjust_for_pagination filter adjusts the value of forloop.counter based on the current page. Page and is_paginated variables are expected to be present in the context. These should respectively denote the current page number (1 based) and if the results are paginated. RESULTS_PER_PAGE is currently taken from the settings file. I couldn't think of a way to pass this value also from the template.

Sunday, March 08, 2009

SICP Section 5.2 A Register-Machine Simulator

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" :)

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:

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.