When you ask ISL+ to apply some function f to an argument a, you usually get some value v. If you evaluate (f a) again, you get v again. As a matter of fact, you get v no matter how often you request the evaluation of (f a). The function application may also loop forever or signal an error, but we ignore these possibilities. We also ignore random, which is the true exception to this rule. Whether the function is applied for the first time or the hundredth time, whether the application is located in DrRacket’s interactions area or inside the function itself, doesn’t matter. The function works according to its purpose statement, and that’s all you need to know.
This principle of context-independence plays a critical role in the design
of recursive functions. When it comes to design, you are free to assume
that the function computes what the purpose statement promises—
While context-independence facilitates the design of functions, it causes two problems. In general, context-independence induces a loss of knowledge during a recursive evaluation; a function does not “know” whether it is called on a complete list or on a piece of that list. For structurally recursive programs, this loss of knowledge means that they may have to traverse data more than once, inducing a performance cost. For functions that employ generative recursion, the loss means that the function may not be able to compute the result at all. The preceding part illustrates this second problem with a graph traversal function that cannot find a path between two nodes for a circular graph.
This part introduces a variant of the design recipes to address this “loss of context” problem. Since we wish to retain the principle that (f a) returns the same result no matter how often or where it is evaluated, the only solution is to add an argument that represents the context of the function call. We call this additional argument an accumulator. During the traversal of data, the recursive calls continue to receive regular arguments while accumulators change in relation to those and the context.
Designing functions with accumulators correctly is clearly more complex than any of the design approaches from the preceding chapters. The key is to understand the relationship between the proper arguments and the accumulators. The following chapters explain how to design functions with accumulators and how they work.
Both functions designed according to structural recipes and the generative
one suffer from the loss of knowledge, though in different ways. This
chapter explains with two examples—
Let’s start with a seemingly straightforward example:
Sample Problem You are working for a geometer team that will measure the length of roads segments. The team asked you to design a program that translates these relative distances between a series of road points into absolute distances for some starting point.
Designing a program that performs this calculation is a mere
exercise in structural function design. Figure 192
contains the complete program. When the given list is not '(),
the natural recursion computes the absolute distance of the remainder of
the dots to the first one on ( l). Because the first
is not the actual origin and has a distance of ( l) to the
origin, we must add ( l) to each number on the result of
the natural recursion. This second step—
; [List-of Number] -> [List-of Number] ; convert a list of relative to absolute distances ; the first number represents the distance to the origin ( (relative->absolute '(50 40 70 30 30)) '(50 90 160 190 220)) ( (relative->absolute l) ( [( l) '()] [ ( (( rest-of-l (relative->absolute ( l))) ( adjusted (add-to-each ( l) rest-of-l))) ( ( l) adjusted))])) ; Number [List-of Number] -> [List-of Number] ; add n to each number on l ( ( 50 (add-to-each 50 '(40 110 140 170))) '(50 90 160 190 220)) ( (add-to-each n l) ( [( l) '()] [ ( (+ ( l) n) (add-to-each n ( l)))]))
(relative->absolute (build-list size ))
(relative->absolute (build-list size ))
Considering the simplicity of the problem, the amount of work that the program performs is surprising. If we were to convert the same list by hand, we would tally up the total distance and just add it to the relative distances as we take steps along the line. Why can’t a program do so?
( (relative->absolute/a l) ( [( l) ] [ ( ( l) (relative->absolute/a ( l)) )]))
(relative->absolute/a ( 3 2 7)) == ( 3 (relative->absolute/a ( 2 7))) == ( 3 ( 2 (relative->absolute/a ( 7)))) == ( 3 ( 2 ( 7 (relative->absolute/a '()))))
Again, the problem is that recursive functions are independent of their context. A function processes L in ( N L) the same way as in ( K L). Indeed, if given L by itself, it would also process the list in that way.
To make up for the loss of “knowledge,” we equip the function with an additional parameter: accu-dist. The latter represents the accumulated distance, which is the tally that we keep when we convert a list of relative distances to a list of absolute distances. Its initial value must be 0. As the function traverses the list, it must add its numbers to the tally.
( (relative->absolute/a l accu-dist) ( [( l) '()] [ ( (( tally (+ ( l) accu-dist))) ( tally (relative->absolute/a ( l) tally)))]))
(relative->absolute/a ( 3 2 7)) == (relative->absolute/a ( 3 2 7) 0) == ( 3 (relative->absolute/a ( 2 7) 3)) == ( 3 ( 5 (relative->absolute/a ( 7) 5))) == ( 3 ( 5 ( 12 ???))) == ( 3 ( 5 ( 12 '())))
The hand-evaluation shows just how much the use of an accumulator simplifies the conversion process. Each item in the list is processed once. When relative->absolute/a reaches the end of the argument list, the result is completely determined and no further work is needed. In general, the function performs on the order of N natural recursion steps for a list with N items.
One problem is that, unlike relative->absolute, the new function consumes two arguments not just one. Worse, someone might accidentally misuse relative->absolute/a by applying it to a list of numbers and a number that isn’t 0. We can solve both problems with a function definition that uses a definition to encapsulate relative->absolute/a; figure 193 shows the result. Now, relative->absolute is indistinguishable from relative->absolute.v2 with respect to input-output.
; [List-of Number] -> [List-of Number] ; convert a list of relative to absolute distances ; the first number represents the distance to the origin ( (relative->absolute.v2 '(50 40 70 30 30)) '(50 90 160 190 220)) ( (relative->absolute.v2 l0) ( ( ; [List-of Number] Number -> [List-of Number] ( (relative->absolute/a l accu-dist) ( [( l) '()] [ ( (( accu (+ ( l) accu-dist))) ( accu (relative->absolute/a ( l) accu)))]))) (relative->absolute/a l0 0)))
(relative->absolute.v2 (build-list size ))
( (relative->absolute l) ( ( ( (f l) ( (+ f ( l)) l)) ( ( l)) ( ( l)))))
Does your friend’s solution mean there is no need for our complicated design in this motivational section? For an answer, see Recognizing the Need for an Accumulator, but reflect on the question first. Hint Try to design on your own.
Sample Problem Design an algorithm that checks whether two nodes are connected in a simple graph. In such a graph, each node has exactly one, directional connection to another, and possibly itself.
Consider the sample graph in figure 194. There are six nodes: A through F, and six connections. A path from A to E must contain B and C. There is no path, though, from A to F or from any other node besides itself.
( a-sg '((A B) (B C) (C E) (D E) (E B) (F F)))
; A SimpleGraph is a [List-of Connection] ; A Connection is a list of two items: ; ( Node Node) ; A Node is a Symbol.
; Node Node SimpleGraph -> Boolean ; is there a path from origin to destination ; in the simple graph sg ( (path-exists? 'A 'E a-sg) #true) ( (path-exists? 'A 'F a-sg) #false) ( (path-exists? origin destination sg) #false)
The problem is trivial if origin is the same as destination.
The trivial solution is #true.
If origin is not the same as destination, there is only one thing we can do: step to the immediate neighbor and search for destination from there.
There is no need to do anything if we find the solution to the new problem. If origin’s neighbor is connected to destination, then so is origin. Otherwise there is no connection.
; Node Node SimpleGraph -> Boolean ; is there a path from origin to destination in sg ( (path-exists? 'A 'E a-sg) #true) ( (path-exists? 'A 'F a-sg) #false) ( (path-exists? origin destination sg) ( [( origin destination) #t] [ (path-exists? (neighbor origin sg) destination sg)])) ; Node SimpleGraph -> Node ; determine the node that is connected to a-node in sg ( (neighbor 'A a-sg) 'B) ( (neighbor 'G a-sg) "neighbor: not a node") ( (neighbor a-node sg) ( [( sg) ( "neighbor: not a node")] [ ( ( ( ( sg)) a-node) ( ( sg)) (neighbor a-node ( sg)))]))
Figure 195 contains the complete program, including the
function for finding the neighbor of a node in a simple graph—
(path-exists? 'C 'D '((A B) (F F))) == (path-exists? 'E 'D '((A B) (F F))) == (path-exists? 'B 'D '((A B) (F F))) == (path-exists? 'C 'D '((A B) (F F)))
Our problem with path-exists? is again a loss of “knowledge,” similar to that of relative->absolute above. Like relative->absolute, the design of path-exists? uses a recipe and assumes that recursive calls are independent of their context. In the case of path-exists? this means, in particular, that the function doesn’t “know” whether a previous application in the current chain of recursions received the exact same arguments.
The solution to this design problem follows the pattern of the preceding section. We add a parameter, which we call seen and which represents the accumulated list of starter nodes that the function has encountered, starting with the original application. Its initial value must be '(). As the function checks on a specific origin and moves to its neighbors, origin is added to seen.
(path-exists?/a 'C 'D '((A B) (F F)) '())
== (path-exists?/a 'E 'D '((A B) (F F)) '(C)) == (path-exists?/a 'B 'D '((A B) (F F)) '(E C)) == (path-exists?/a 'C 'D '((A B) (F F)) '(B E C))
All we need to do now, is to make the algorithm exploit the accumulated knowledge. Specifically, the algorithm can determine whether the given origin is already an item in seen. If so, the problem is also trivially solvable yielding #false as the solution. Figure 196 contains the definition of path-exists.v2?, which is the revision of path-exists?. The definition refers to , an ISL+ function.
; Node Node SimpleGraph -> Boolean ; is there a path from origin to destination in sg ( (path-exists.v2? 'A 'E a-sg) #true) ( (path-exists.v2? 'A 'F a-sg) #false) ( (path-exists.v2? origin destination sg) ( (; Node Node SimpleGraph [List-of Node] -> Boolean ( (path-exists?/a origin seen) ( [( origin destination) #t] [( origin seen) #f] [ (path-exists?/a (neighbor origin sg) ( origin seen))]))) (path-exists?/a origin '())))
The definition of path-exists.v2? also eliminates the two minor problems with the first revision. By localizing the definition of the accumulating function, we can ensure that the first call always uses '() as the initial value for seen. And, path-exists.v2? satisfies the exact same signature and purpose statement as the path-exists? function.
Still, there is a significant difference between path-exists.v2? and relative-to-absolute2. Whereas the latter was equivalent to the original function, path-exists.v2? improves on path-exists?. While the latter fails to find an answer for some inputs, path-exists.v2? finds a solution for any simple graph.
Exercise 537. Modify the definitions in figure 183 so that the program produces #false, even if it encounters the same origin twice.
The preceding chapter illustrates the need for accumulating extra knowledge with two examples. In one case, accumulation makes it easy to understand the function and yields one that is far faster than the original version. In the other case, accumulation is necessary for the function to work properly. In both cases though, the need for accumulation becomes only apparent once a properly designed function exists.
the recognition that a function benefits from an accumulator;
an understanding of what the accumulator represents.
; [List-of X] -> [List-of X] ; construct the reverse of alox ( (invert '(a b c)) '(c b a)) ( (invert alox) ( [( alox) '()] [ (add-as-last ( alox) (invert ( alox)))])) ; X [List-of X] -> [List-of X] ; add an-x to the end of alox ( (add-as-last 'a '(c b)) '(c b a)) ( (add-as-last an-x alox) ( [( alox) ( an-x)] [ ( ( alox) (add-as-last an-x ( alox)))]))
If a structurally recursive function traverses the result of its natural recursion with an auxiliary, recursive function, consider the use of an accumulator parameter.
Take a look at the definition of invert in figure 197. The result of the recursive application produces the reverse of the rest of the list. It uses add-as-last to add the first item to this reversed list and thus creates the reverse of the entire list. This second, auxiliary function is also recursive. We have thus identified an accumulator candidate.It is now time to study some hand-evaluations, as in A Problem with Structural Processing, to see whether an accumulator helps. Consider the following:
(invert '(a b c)) == (add-as-last 'a (invert '(b c))) == (add-as-last 'a (add-as-last 'b (invert '(c)))) == &hellip == (add-as-last 'a (add-as-last 'b '(c))) == (add-as-last 'a '(c b)) == '(c b a)Stop! Replace the dots with the two missing steps. Then you can see that invert eventually reaches the end of the given list— just like add-as-last— and if it knew which items to put there, there would be no need for the auxiliary function.
If we are dealing with a function based on generative recursion, we are faced with a much more difficult task. Our goal must be to understand whether the algorithm can fail to produce a result for inputs for which we expect a result. If so, adding a parameter that accumulates knowledge may help. Because these situations are complex, we defer the discussion of an example to More Uses of Accumulation.
Exercise 538. Argue that, in the terminology of Intermezzo: The Cost of Computation, invert consumes O(n2) time when the given list consists of n items.
Exercise 539. Does the insertion sort> function from Auxiliary Functions that Recur need an accumulator? If so, why? If not, why not?
Determine the knowledge that the accumulator represents, what kind of data to use, and how the knowledge is acquired as data.
For example, for the conversion of relative distances to absolute distances, it suffices to accumulate the total distance encountered so far. As the function processes the list of relative distances, it adds each new relative distance found to the accumulator’s current value. For the routing problem, the accumulator remembers every node encountered. As the path-checking function traverses the graph, it es each new node on to the accumulator.In general, you want to proceed as follows.
- Create an accumulator template:
; Domain -> Range ( (function d0) ( (; Domain AccuDomain -> Range ; accumulator ... ( (function/a d a) )) (function/a d0 a0)))Sketch a manual evaluation of an application of function to understand the nature of the accumulator.
Determine the kind of data that the accumulator tracks.
Write down a statement that explains the accumulator as a relationship between the argument d of the auxiliary function/a and the original argument d0.
Note The relationship remains constant, also called invariant, over the course of the evaluation. Because of this property, an accumulator statement is often called an invariant.
Use the invariant to determine the initial value a0 for a.
Also exploit the invariant to determine how to compute the accumulator for the recursive function calls within the definition of function/a.
Exploit the accumulator’s knowledge for the design of function/a.
For a structurally recursive function, the accumulator’s value is typically used in the base case, that is, the clause that does not recur. For functions that use generative recursive functions, the accumulated knowledge might be used in an existing base case, in a new base case, or in the clauses that deal with generative recursion.
(invert '(a b c))
== (invert/a '(a b c) a0) == (invert/a '(b c) 'a a0) == (invert/a '(c) 'b 'a a0) == (invert/a '() 'c 'b 'a a0)
Note how, once again, invert.v2 merely traverses the list. In contrast, invert re-processes every result of its natural recursion with add-as-last. Stop! Measure how much faster invert.v2 runs than invert.
Terminology Programmers use the phrase accumulator-style function to discuss functions that use an accumulator parameter. Examples of functions in accumulator-style are relative->absolute/a, invert/a, and path-exists?/a.
Articulating the accumulator statement is difficult but without formulating a good invariant, it is impossible to understand an accumulator-style function. Since the goal of a programmer is to make sure that others who follow understand the code easily, practicing this skill is critical. And formulating invariants deserves a lot of practice.
The goal of this section is to study the formulation of accumulator statements with three case studies: a summation function, the factorial function, and a tree-traversal function. Each such case is about the conversion of a structurally recursive function into accumulator style. None actually call for the use of an accumulator parameter. But they are easily understood and, with the elimination of all other distractions, using such examples allows us to focus on the articulation of the accumulator invariant.
( (sum.v1 alon) ( [( alon) 0] [ (+ ( alon) (sum.v1 ( alon)))]))
As suggested by our first step, we have put the template for sum/a into a definition, added an accumulator parameter, and renamed the parameter of sum .
a is the sum of the numbers that alon lacks from alon0
'(10 4 6)
'(10 4 6)
'(10 4 6)
Exercise 540. Complete the manual evaluation of (sum/a '(10 4) 0) in figure 198. Doing so shows that the sum and sum.v2 add up the given numbers in reverse order. While sum adds up the numbers from right to left, the accumulator-style version adds them up from left to right.
Note on Numbers Remember that for exact numbers, this difference has no effect on the final result. For inexact numbers, the difference can be significant. See the exercises at the end of Intermezzo: The Cost of Computation.
The factorial function is useful for the analysis of algorithms.
a is the product of the natural numbers in the interval [n0,n).
For the third and last example, we use a function that measures the height of simplified binary trees. The example illustrates that accumulator-style programming applies to all kinds of data, not just those defined with single self-references. Indeed, it is as common for complicated data definitions as it is for lists and natural numbers.
( (height abt) ( [( abt) 0] [ (+ ( (height (node-left abt)) (height (node-right abt))) 1)]))
(make-node '() '())
(make-node (make-node '() (make-node '() '())) '())
a is the number of steps it takes to reach abt from abt0.
If abt0 is the complete tree and abt is the subtree pointed to by the circled 1, the accumulator’s value must be 1 because it takes exactly one step to get from the root of abt to the root of abt0.
In the same spirit, for the subtree labeled 2 the accumulator is 2 because it takes two steps to get this place.
; Tree -> N ; measure the height of abt0 ( (height.v2 example) 3) ( (height.v2 abt0) ( (; Tree N -> N ; measure the height of abt ; accumulator a is the number of steps ; it takes to reach abt from abt0 ( (height/a abt a) ( [( abt) a] [ ( (height/a (node-left abt) (+ a 1)) (height/a (node-right abt) (+ a 1)))]))) (height/a abt0 0)))
Following the design recipe also tells us that we need to interpret the two values to find the appropriate function. According to the purpose statement for height/a, the first value is the height of the left subtree, and the second one is the height of the right one. Given that we are interested in the height of abt itself and that the height is the largest number of steps it takes to reach a leaf, we use the function to pick the proper one; see figure 200 for the complete definition.
the first accumulator, a, represents the number of steps it takes to reach abt from abt0 and the second accumulator, stands for the tallest branch in the part of abt0 that is to the left of abt.
Exercise 543. Complete the design of height.v3. Hint In terms of the bottom-most tree of figure 199, the place marked 1 has no complete paths to leafs to its left while the place marked 2 has one complete path and it consists of two steps.
This second design has a more complex accumulator invariant than the first one. By implication, its implementation requires more care than the first one. At the same time, it comes without any advantages, meaning it is inferior to the first one.
Our point is that different accumulator invariants yield different variants. You can design both variants systematically following the same design recipe. When you have complete function definitions, you can compare and contrast the results, and you can then decide which one to keep based on evidence. End
Exercise 544. Design an accumulator-style version of product, the function that computes the product of a list of numbers. Stop when you have formulated the accumulator invariant and have someone check it.
Exercise 545. Design an accumulator-style version of how-many, which is the function that determines the number of items on a list. Stop when you have formulated the invariant and have someone check it.
The performance of how-many is O(n) where n is the length of the list. Does the accumulator version improve on this?
Computer scientists refer to this space as stack space but you can safely ignore this terminology for now.
via all-but-last again, and
via , which is ISL+’s version of inverse.
rows in M
Formulate an accumulator statement. Then follow the accumulator design recipe to complete the above function. Measure how fast it runs on a Matrix that consists of rows with leading 0s except for the last one. If you completed the design correctly, the function is quite fast.
Exercise 549. Design to10. It consumes a list of digits and produces the corresponding number. The first item on the list is the most significant digit. Hence, when applied to '(1 0 2), it produces 102.
Domain Knowledge A number n is prime if it is not divisible by any number between n - 1 and 2.
; version 2 ( (f*ldl f l) ( (( ( l) ( [( l) '()] [ (add-to-end ( l) ( ( l)))])) ( (add-to-end x l) ( [( l) ( x)] [ ( ( l) (add-to-end x ( l)))])) ( ( l) ( [( l) ] [ (f ( l) ( ( l)))]))) ( ( l))))
; version 3 ( (f*ldl f l) ( (( (invert/a l a) ( [( l) a] [ (invert/a ( l) ( ( l) a))])) ( ( l) ( [( l) ] [ (f ( l) ( ( l)))]))) ( (invert/a l '()))))
; version 4 ( (f*ldl f l0) ( (( (fold/a a l) ( [( l) a] [ (fold/a (f ( l) a) ( l))]))) (fold/a l0)))
; [X Y] [X Y -> Y] Y [List-of X] -> Y
; version 5 ( (f*ldl f i l) ( [( l) i] [ (f*ldl f (f ( l) i) ( l))]))
( (build-l*st n f) (build-list n f))
A Graphical Editor introduces the notion of a one-line editor and presents a number of exercises on creating a graphical editor. Recall that a graphical editor is an interactive program that interprets key events as editing actions on a string. In particular, when a user presses the left or right arrow key, the cursor moves left or right; similarly, pressing the delete key removes a 1String from the edited text. The editor program uses a data representation that combines two strings in a structure. A Graphical Editor, Revisited resumes these exercises and shows how the same program can greatly benefit from a different data structure, one that combines two strings.
Neither of these sections deals with mouse actions for navigation, even though all modern applications support this functionality. The basic difficulty with mouse events is to place the cursor at the appropriate spot. Since the program deals with a single line of text, a mouse click at (x,y) clearly aims to place the cursor between the letters that are visible at or around the x position. This section fills the gap.
Recall the relevant definitions from A Graphical Editor, Revisited:
( FONT-SIZE 11) ( FONT-COLOR "black") ; [List-of 1String] -> Image ; render a string as an image for the editor ( (editor-text s) ( ( s) FONT-SIZE FONT-COLOR)) ( editor [pre post]) ; An Editor is a structure: ; (make-editor [List-of 1String] [List-of 1String]) ; interpretation if (make-editor p s) is the state of ; an interactive editor, ( p) corresponds to ; the text to the left of the cursor and s to the ; text on the right
(make-editor p s)
( ( p s) ed)
( ( (editor-text p)) x ( (editor-text ( p ( s)))))
Hints (1) The x-coordinate measures the distance from the left. Hence the function must check whether smaller and smaller prefixes of ed fit into the given width. The first one that doesn’t fit corresponds to the pre field of the desired Editor, the remainder of ed to the post field.
(2) Designing this function calls for thoroughly developing examples and tests. See Intervals, Enumerations, Itemizations.
Exercise 554. Design the function split. Use the accumulator design recipe to improve on the result of exercise 553. After all, the hints already point out that when the function discovers the correct split point, it needs both parts of the list and one part is obviously lost due to recursion.
Once you have solved this exercise, equip the main function of
A Graphical Editor, Revisited with a clause for mouse
clicks. As you experiment with moving the cursor via mouse clicks, you will
notice that it does not exactly behave like applications that you use on
your other devices—
Graphical programs, like editors, call for experimentation to come up with best “look and feel” experiences. In this case, your editor is too simplistic with its placement of the cursor. After the applications on your computer determine the split point, they also determine which letter division is closer to the x-coordinate and place the cursor there.
Exercise 555. Many operating systems come with the fmt program, which can re-arrange the words in a file so that all lines in the resulting file have a maximal width. As a widely used program, fmt supports a range of related functions. This exercise focuses on its core functionality.
Design the program fmt. It consumes a natural number w,
the name of an input file in-f, and the name of an output file
This chapter presents three more uses of accumulators. The first section concerns the use of accumulators in conjunction with tree-processing functions. It uses the compilation of ISL+ as an illustrative example. The second section explains why we occasionally want accumulators inside of data representations and how to go about it. The final section resumes the discussion of rendering fractals.
When you ask DrRacket to run an ISL+ program, it translates the program to commands for your specific computer. This process is called compilation and the part of DrRacket that performs the task is called a compiler. Before the compiler translates the ISL+ program, it checks that every variable is declared via a , , or a .
Stop! Enter x, ( (y) x), and (x 5) as complete ISL+ programs into DrRacket and ask it to run each. What do you expect to see?
Sample Problem You have been hired to re-create a part of the ISL+ compiler. Specifically, your task deals with the following language fragment, specified in the so-called grammar notation that many programming language manuals use:We use the Greek letter λ instead of to signal that this exercise deals with ISL+ as an object of study not just a programming language.
expression = variable | ( (variable) expression) | (expression expression)Remember from BSL Grammar that you can read the grammar aloud replacing = with “is one of” and | with “or.”
Recall that expressions are functions without names. They bind their parameter in their body. Conversely, a variable occurrence is declared by a surrounding that specifies the same name as a parameter. You may wish to revisit Intermezzo: Scope and Abstraction because it deals with the same issue from the perspective of a programmer. Look for the terms “binding occurrence,” “bound occurrence,” and “free.”
Develop a data representation for the above language fragment; use symbols to represent variables. Then design a function that replaces all undeclared variables with '*undeclared.
( (x) x) is the function that returns whatever it is given, also known as the identity function;
( (x) y) looks like a function that returns y whenever it is given an argument, except that y isn’t declared;
( (y) ( (x) y)) is a function that, when given some value v, produces a function that always returns v;
(( (x) x) ( (x) x)) applies the identity function to itself;
(( (x) (x x)) ( (x) (x x))) is a short infinite loop; and
((( (y) ( (x) y)) ( (z) z)) ( (w) w)) is a complex expression that is best run in ISL+ to find out whether it terminates.
( ex1 '(λ (x) x)) ( ex2 '(λ (x) y)) ( ex3 '(λ (y) (λ (x) y))) ( ex4 '((λ (x) (x x)) (λ (x) (x x))))
λ-para, which extracts the parameter from a λ expression;
λ-body, which extracts the body from a λ expression;
app-fun, which extracts the function from an application; and
app-arg, which extracts the argument from an application.
( (undeclareds le) ( [(is-var? le) ] [(is-λ? le) ( (undeclareds (λ-body le)) )] [(is-app? le) ( (undeclareds (app-fun le)) (undeclareds (app-arg le)) )]))
a represents the list of λ parameters encountered on the path from the tope of le0 to the top of le.
'(((λ (y) (λ (x) y)) (λ (z) z)) (λ (w) w))
'(((λ (y) (λ (x) y)) (λ (z) z)) (λ (w) w))
Figure 201: Lam terms as trees
the initial accumulator value of '();
we can use to add (λ-para le) to a; and
once undeclareds/a reaches a variable, it can use the accumulator to check whether the variable is in the scope of a declaration.
Figure 202 shows how to translate these ideas into a complete function definition. Note the name declareds for the accumulator; it brings across the key idea behind the accumulator invariant, helping the programmer understand the definition. The base case uses from ISL+ to determine whether the variable le is in declareds and, if not, replaces it with '*undeclared. The second clause uses a to introduce the extended accumulator newd. Because para is also used to rebuild the expression, it has its own local definition. Finally, the last clause concerns function applications, which do not declare variables and do not use any directly. As a result, it is by far the simplest of the three clauses.
( (undeclareds le0) ( (; Lam [List-of Symbol] -> [List-of Symbol] ; accumulator declareds is a list of all λ ; parameters on the path from le0 to le ( (undeclareds/a le declareds) ( [(is-var? le) ( ( le declareds) le '*undeclared)] [(is-λ? le) ( (( para (λ-para le)) ( body (λ-body le)) ( newd ( para declareds))) ( 'λ ( para) (undeclareds/a body newd)))] [(is-app? le) ( (( fun (app-fun le)) ( arg (app-arg le))) ( (undeclareds/a fun declareds) (undeclareds/a arg declareds)))]))) (undeclareds/a le0 '())))
Exercise 559. Make up an ISL+ expression in which x occurs both free and bound. Formulate it as an element of Lam. Does undeclareds work properly on your expression?
( (*undeclared) (( (x) (x *undeclared)) y))
( '*undeclared 'x)
( '*declared 'y)
Exercise 561. Re-design the undeclareds function for the structure-based data representation from exercise 558.
'((λ (x) (λ (y) (y x))) (λ (z) z))
The end of Intermezzo: The Cost of Computation explains that *SL measures the size of containers, say lists, by traversing them and hints that other programming languages use a different, See Finite State Machines for an early example of this idea. a less expensive way to compute sizes. In this section, we show how to implement this idea with the addition of an accumulator to data representations.
Consider the ubiquitous lists in *SL. All lists are constructed from and '(); operations such as and , for example, are merely abbreviations for these two. As What Is '(), What Is shows, it is also possible to mimic lists in BSL with suitable structure type and function definitions.
( pair [head right]) ; ConsOrEmpty is one of: ; – '() ; – (make-pair Any ConsOrEmpty) ; Any ConsOrEmpty -> ConsOrEmpty ( (our-cons a-value a-list) ( [( a-list) (make-pair a-value a-list)] [(our-cons? a-list) (make-pair a-value a-list)] [ ( "our-cons: ...")])) ; ConsOrEmpty -> Any ; extracts the left part of the given pair ( (our-first mimicked-list) ( ( mimicked-list) ( "our-first: ...") (pair-left mimicked-list)))
Figure 204 recalls the basic idea. Stop! Can you define our-rest now?
( cpair [count left right]) ; A [MyList X] is one of: ; – '() ; – (make-cpair (tech "N") X [MyList X]) ; accumulator the count field is the number of cpairs
; data definitions, via a constructor-function ( (our-cons f r) ( [( r) (make-cpair 1 f r)] [(cpair? r) (make-cpair (+ (cpair-count r) 1) f r)] [ ( "our-cons: ...")]))
The second problem with the addition of a count field concerns
performance. Indeed, there are two concerns. On one hand, every single
list construction comes with an extra field now, meaning a 33% increase in
memory consumption. On the other hand, the addition of the field decreases
how fast our-cons constructs a list. In addition to the check
that the extended list is either '() or an instance of a cpair,
the constructor now computes the size of the list. Although this
computation consumes a constant amount of time, it is imposed on every
single use of our-cons—
While the addition of count field to list is questionable, sometimes data accumulators play a crucial role in finding a solution. The next example is about adding so-called artificial intelligence to a board-game playing program, and its data accumulator is an absolute necessity.
Sample Problem Your manager tells you the following story.
“Once upon a time, three cannibals were guiding three missionaries through a jungle. They were on their way to the nearest mission station. After some time, they arrived at a wide river, filled with deadly snakes and fish. There was no way to cross the river without a boat. Fortunately, they found a rowing boat with two oars after a short search. Unfortunately, the boat was too small to carry all of them. It could barely carry two people at a time. Worse, because of the river’s width someone had to row the boat back.
“Since the missionaries could not trust the cannibals, they had to figure out a plan to get all six of them safely across the river. The problem was that these cannibals would kill and eat missionaries as soon as there were more cannibals than missionaries in some place. Our missionaries had to devise a plan that guaranteed that there were never any missionaries in the minority on either side of the river. The cannibals, however, could be trusted to cooperate otherwise. Specifically, they would not abandon any potential food, just as the missionaries would not abandon any potential converts.”
While your manager doesn’t assign any specific design task, he wants to explore whether the company can design (and sell) programs that solve such puzzles.
Now that you have a way to write down the state of the puzzle, you can think about the possibilities at each stage. Doing so yields a tree of possible moves. Figure 205 sketches the first two and a half layers in such a tree. The left-most state is the initial one. Because the boat can transport at most two people and must be rowed by at least one, you have five possibilities to explore: one cannibal rows across, two, one missionary and one cannibal go, one missionary, or two missionaries. These possibilities are represented with five arrows going from the initial state to five intermediate states.
For each of these five intermediate states, you can play the same game again. In figure 205 you see how the game continues for the middle (third) one of the new states. Because there are only two people on the right river bank, you see three possibilities: a cannibal goes back, a missionary, or both. Hence three arrows connect the middle state to the three states on the right side of the tree. If you keep drawing this tree of possibilities in a systematic manner, you eventually discover the final state.
A second look at figure 205 reveals two problems with this naive approach to generating the tree of possibilities. The first one is the dashed arrow that connects the middle state on the right to the initial state. It indicates that rowing back the two people from the right to the left gets the puzzle back to its initial state, meaning you’re starting over, which is obviously undesirable. The second problem concerns those states with a star in the top-right corner. In both cases, there are more white-circle cannibals than black-circle missionaries on the left river bank, meaning the cannibals would eat the missionaries. Again, the goal is to avoid such states, making these moves undesirable.
; PuzzleState -> PuzzleState ; is the final state reachable from state0 ; generative create a tree of possible boat rides ; termination ??? ( (solve initial-puzzle) final-puzzle) ( (solve state0) ( (; [List-of PuzzleState] -> PuzzleState ; generative generate the successors of los ( (solve* los) ( [( final? los) ( ( final? los))] [ (solve* (create-next-states los))]))) (solve* ( state0))))
Clearly, solve is quite generic. As long as you define a collection of PuzzleStates, a function for recognizing final states, and a function for creating all “successor” states, solve can work on your puzzle.
Exercise 565. The solve* function generates all states reachable with n boat trips before it looks at states that require n + 1 boat trips, even if some of those boat trips return to previously encountered states. Because of this systematic way of traversing the tree, solve* cannot go into an infinite loop. Why? Terminology This way of searching a tree or a graph is dubbed breadth-first search.
Exercise 566. Develop a representation for the states of the missionary-and-cannibal puzzle. Like the graphical representation, a state must obviously record the number of missionaries and cannibals on each side of the river plus the location of the boat. After all, these are the properties of the world that change with one boat trip.
The description of PuzzleStates calls for a new structure type. Represent the above initial, intermediate, and final states in your representation.
Design the function final?, which detects whether in a given state all people are on the right river bank.
The problem is that returning the final state says nothing about how the player can get from the initial state to the final one. In other words, create-next-states forgets how it gets to the returned states from the given ones. And this situation clearly calls for an accumulator, but at the same time, the accumulated knowledge is best associated with the individual PuzzleStates not solve* or any other function.
Exercise 567. Modify the representation from exercise 566 so that a state records the sequence of states traversed to get there. Use a list of states.
Articulate and write down an accumulator statement with the data definition that explains the additional field.
Ignore the accumulator in the first draft of create-next-states, but make sure that the function does not generate states where the cannibals can eat the missionaries.
The given problem is a triangle. When the triangle is too small to be sub-divided any further, the algorithm does nothing; otherwise, it finds the midpoints of its three sides and deals with the three outer triangles recursively.
Sample Problem Design the add-sierpinski function. It consumes an image and three Posns describing a triangle. It uses the latter to add a Sierpinski triangle to this image.
The problem is trivial if the triangle is too small to be sub-divided.
In the trivial case, the function returns the given image.
Otherwise the midpoints of the sides of the given triangle are determined to add another triangle. Each “outer” triangle is then processed recursively.
Each of these recursive steps produces an image. The remaining question is how to combine these images.
; Image Posn Posn Posn -> Image ; generative adds the triangle (a, b, c) to s, ; sub-divides it into three triangles by taking the ; midpoints of its sides; stop if (a, b, c) is too small ( (add-sierpinski scene0 a b c) ( [(too-small? a b c) scene0] [ ( (( scene1 (add-triangle scene0 a b c)) ( mid-a-b (mid-point a b)) ( mid-b-c (mid-point b c)) ( mid-c-a (mid-point c a)) ( scene2 (add-sierpinski scene0 a mid-a-b mid-c-a)) ( scene3 (add-sierpinski scene0 b mid-b-c mid-a-b)) ( scene4 (add-sierpinski scene0 c mid-c-a mid-b-c))) ; — IN— ( scene1 scene2 scene3 ))]))
Figure 206 shows he the result of translating these answers into a skeletal definition. Since each midpoint is used twice, the skeleton uses a expression to formulate the generative step in ISL+. The expression introduces the three new midpoints plus three recursive applications of sierpinski. The dots in its body suggests a combination of the scenes.
Now that we have all the auxiliary functions, it is time to return to the problem of combining the three images that are created by the recursive calls. One obvious guess is to use the or function, but a test at in the interaction area of DrRacket shows that the functions hide the underlying triangles.
> scene1 > scene2 > scene3
> ( scene1 scene2 scene3) > ( scene1 scene2 scene3)
; Image Posn Posn Posn -> Image ; generative adds the triangle (a, b, c) to s, ; sub-divides it into three triangles by taking the ; midpoints of its sides; stop if (a, b, c) is too small ; accumulator the function accumulates the triangles scene0 ( (add-sierpinski scene0 a b c) ( [(too-small? a b c) scene0] [ ( (( scene1 (add-triangle scene0 a b c)) ( mid-a-b (mid-point a b)) ( mid-b-c (mid-point b c)) ( mid-c-a (mid-point c a)) ( scene2 (add-sierpinski scene1 a mid-a-b mid-c-a)) ( scene3 (add-sierpinski scene2 b mid-b-c mid-a-b))) ; — IN— (add-sierpinski scene3 c mid-c-a mid-b-c))]))
Figure 207 shows the reformulation based on this insight. The three highlights pinpoint the key design idea. All concern the case when the triangle is sufficiently large and it is added to the given scene. Once its sides are sub-divided, the first outer triangle is recursively processed using scene1, the result of adding the given triangle. Similarly, the result of this first recursion, dubbed scene2, is used for the second recursion, which is about processing the second triangle. Finally, scene3 flows into the third recursive call. In sum, the novelty is that the accumulator is simultaneously an argument, a tool for collecting knowledge, and the result of the function.
( MT ( 400 400)) ( A ( 200 50)) ( B ( 27 350)) ( C ( 373 350)) (add-sierpinski MT A B C)
Design the function add-savannah. The function consumes an image and four numbers: (1) the x-coordinate of a line’s base point, (2) the y-coordinate of a line’s base point, (3) the length of the line, and (4) the angle of the line. It adds a fractal Savannah tree to the given image.
Unless the line is too short, the function adds the specified line to the image. It then divides the line into three segments. It recursively uses the two intermediate points as the new starting points for two lines. The lengths and the angles of the two branches change in a fixed manner, but independently of each other. Use constants to define these changes and work with them until you like your tree well enough.
Hint Experiment with shortening the left branches by at least one third and rotating it left by at least 0.15 degrees. For the right branch, shorten it by at least 20% and rotate it by 0.2 degrees in the opposite direction.
Now turn to the image in the middle It explains the essential idea of the generative step. The algorithm determines the midpoint on the two observer lines, A-B and B-C, as well as their midpoint, A-B-C.
Finally, the rightmost image shows how these three new points generate two distinct recursive calls: one deals with the new triangle on the left and the other one with the triangle on the right. More precisely, A-B and B-C become the new observer points and the lines from A to A-B-C and from C to A-B-C become the foci of the two recursive calls.
When the triangle is small enough, we have a trivially solvable case. The algorithm just draws the triangle, and it appears as a point on the given image. You may need to experiment with the notion of “small enough” to make the curve look smooth.
The first step is to recognize the need for introducing an accumulator. Traversals “forget” pieces of the argument when they step from piece to the next. If you discover that such knowledge could simplify the function’s design, consider introducing an accumulator. The first step is to switch to the accumulator template.
The key step is to formulate an accumulator statement. The latter must express what knowledge the accumulator gathers as what kind of data. In most cases, the accumulator statement describes the difference between the very original argument and the current one.
The third step, a minor one, is to deduce from the accumulator statement (1) what the initial accumulator value is, (2) how to maintain it during traversal steps, and (3) how to exploit its knowledge.
The idea of accumulating knowledge is ubiquitous, and it appears in many different forms and shapes. It is widely used in so-called functional languages like ISL+. Programmers using imperative languages encounter accumulators in a different way, mostly via assignment statements in primitive looping constructs, because the latter cannot return values. Designing such imperative accumulator programs proceeds just like the design of accumulator functions here, but the details are beyond the scope of this first book on systematic program design.