Page Numbers: Yes X: 306 Y: 0.9" First Page: 1
Margins: Top: 1.1" Bottom: 1.2"
Heading:

PROBLEM SET #1 LISP: LANGUAGE AND LITERATURE April 12, 1984
————————————————————————————————————————————

Problem Set #1: Procedural Abstraction

Distributed:April 16, 1984
Answers due:April 30, 1984

Filed as:[phylum]<3-lisp>course>problem-sets>ps-1a,b,c.bravo, ps-1.press
User.cm:[phylum]<BrianSmith>system>user.classic
Last edited:April 11, 1984 4:13 PM

————————————————————————————————————————————

Introduction

As mentioned in class, we cannot undertake programming projects that deal with semantically complex domains until we have explored the crucial questions of data and representation. In this first problem set, therefore, we will write programs about simple numbers, sequences, and strings. Problem 1 reviews some basic 3-LISP constructs; problems 2 through 5 explore issues of procedural abstraction, modularity, and higher-order procedures in these different domains.

As this is the first problem set, we need to spell out some general ground rules. Before starting to work on specific solutions, you should read through a problem set fairly carefully, thinking about the questions, planning how you will deal with issues that will arise, etc. In many cases, knowing in advance what sorts of questions and problems are going to come up will motivate the earlier parts of the work, and enable you to avoid wandering down blind alleys. It also leads to a cleaner, more organized programming style, and discourages a "debug a blank page" style of hacking. On the other hand, it is equally bad practice to work out solutions to a whole problem set ahead of time, type them into the machine, and then try the final, most complex example first, to see if the whole assemblage works. One reason programming is such an art is that it takes considerable experience to blend the proper amount of careful analysis with practical experimentation.

Another reason to read through the problem set first is to familiarize yourself with the various conventions we use in this document: how we indicate schematic variables, when we use capitals and lower-case, etc. These conventions are explained at the point when they are first introduced.

We are asking you to submit solutions. By this we mean a variety of things: procedure definitions you develop to solve the problems, English answers to ordinary questions, and any other material you think will help us to understand your grasp of the issues involved. We don’t want to see a complete listing of every example you tried, nor do we want telegraphic "yes, I did it" answers. Use your judgment; the most important thing is that your solutions should be clear. Also, feel free to use your solutions as a mechanism of routing feedback to us about the course in general.

When you need to define procedures of one sort or another, you should edit definitions in an EMACS window, and then move them for testing into the so-called "top-level-typescript-window" (it will have this name in the black bar at the top of the window). You can do this moving either with "shift-selection" or with special EMACS commands (your section leader will explain how to do both of these). You can also compose English text in the file in which you prepare your procedure definitions, either between definitions, or in comments (i.e., on lines with a semi-colon in the first column). As you build up your file of definitions and commentary, you should save it on the file computer from time to time (again, your section leader will explain how). When it comes time to hand in your solutions, you should print out your file on the printer, and hand in a paper copy to your section leader. Make sure that the printed version indicates the name of the file itself, in case we need to load your definitions into 3-LISP in order to determine whether, or how, they work.

Don’t be discouraged if it seems to take you an inordinate amount of time to work this problem set. Although in just a few weeks they will seem relatively routine, a great many background assumptions and basic details are exercised here for the first time. You will encounter more new notions in this first problem set than in any of the subsequent ones.

Above all, good luck!

1−1. Basic Programming Constructs

1-1-a. Simplify the following arithmetic expressions, and others you make up of the same sort (keep our realist approach to mathematics in mind while you do this):

234
(+ 2 3)
(/ 10 2)
(/ 10 3)

(1+ 10000)
(1- 10000)

(= 4 (* 2 2))
(= 12 (* 3 (/ 12 3)))
(= 13 (* 3 (/ 13 3)))

(< 10 20)

None of the foregoing expressions have any substantial procedural "effect" or "consequence"; they return or result in simple (canonical) designators. Simplify the following expressions, so as to get a feel for the effect that an expression can have on the state of the computational process.

(set b 10)
(set a (1+ b))

(* a b)

(set b 20)

(* a b)

Note: When A was set to (1+ B) in the second line, the "(1+ B)" occured in what in philosophy of language would be called an extensional context. (SET A (1+ B)), in other words, didn’t mean that a should mean (1+ B), in the sense of always designating the number one greater than the number designated by B. If it had, the second instance of (* A B) above would have returned 420, rather than what it did return. 1

Note: In the indented code 6−10 lines above this line, you will note that we used lower-case letters in variable names, whereas in the paragraph just preceding, we used upper case. 3-LISP is insensitive to case in variable names; you can use either one, or a mixture, interchangeably. As far as the 3-LISP processor is concerned, in other words, the strings ‘abc’, ‘ABC’, and ‘aBc’ all notate the same atom (though they are admittedly different strings). In these problem sets, we will use lower case for variable names in code that is set off on its own, since that is the way we normally write programs, and will use upper case when it is embedded within an English sentence, so as to help us distinguish expressions in 3-LISP from expressions in English. (One exception: we use upper-case to indicate where a variable is being defined, as for example in the definition 4 lines below this one.) All of these conventions are instances of us imposing structure on our programs above and beyond that explicitly supported by the langage definition itself. 1

The procedure DEFINE is rather like SET, except that we use it to define new procedures. For example, the following code defines a procedure that squares its single argument:

(define SQUARE
(lambda [x] (* x x)))

This would support the following sort of behaviour:

1> (square 10)
1= 100
1> (square (square (square 3)))
1= 6561

1-1-b. Define a procedure, called ABSOLUTE-VALUE, that returns the absolute value of a number. (The absolute value of a number is essentially the magnitude of the number, without regard to its sign — i.e., whether it is positive or negative. Thus the absolute value of 3 is 3, and the absolute value of -125 is 125.)

1-1-c. The factorial function, often written "n!", and defined as the product of the integers from 1 through n, is a classic example of a simple recursive function. In addition, the standard definition of that function is a classic example of a recursive definition (remember from class the difference between recursive functions, recursive definitions, and recursive procedures). Define a 3-LISP version of factorial. It should support the following behaviour:

1> (factorial 3)
1= 6
1> (factorial 10)
1= 3628800
1> (factorial 0)
1= 1 ; This is a commonly accepted extension
1> (factorial (factorial 3))
1= 720

1-1-d. In a similar vein, define (and test!) a FIBONNACI procedure (fibonnaci of 1 is 1, fibonnaci of 2 is also 1, and in general fibonnaci of n is the sum of fibonnaci of n-1 and fibonnaci of n-2).

The following procedure also computes the fibonnaci function, though it is probably different from the procedure you defined. Read it through, in order to understand how it works. Then type it in so that you can play around with it, and try it on the same numbers you tried your version on.

(define FIB-2
(lambda [n]
(fib-2-helper n 0 0 1)))

(define FIB-2-HELPER
(lambda [n counter last this]
(if (= counter n)
this
(fib-2-helper n
(1+ counter)
this
(+ last this)))))

1-1-e. Do you notice a difference in behaviour between your definition and FIB-2? Do you have an explanation as to why this difference exists (hint: try them on 16)?

As will be explained in section, the definition of FIB-2-HELPER is rather inelegant, for two reasons: it makes public what is essentially an accessory procedure, and it passes as an explicit argument a number that is always the same. A more elegant and economic version is the following (LETREC is defined in the manual, and will be explained in section):

(define FIB-3
(lambda [n]
(letrec
[[helper (lambda [counter last this]
(if (= counter n)
this
(helper (1+ counter)
this
(+ last this))))]]
(helper 0 0 1))))

1-1-f. The expression for FIB-3 seems quite a bit more complex than the ones for FIB-2 and FIB-2-HELPER. Why do you think we call FIB-3 simpler? Do you agree that it is simpler? Do you think it is better?

1-1-g. Note the use of the variable "n" in the definition of HELPER within FIB-3, even though it is not passed to HELPER as an explicit argument. Would the following definition also work? If not, why not?

(define FIB-4
(letrec
[[helper (lambda [counter last this]
(if (= counter n)
this
(helper (1+ counter)
this
(+ last this))))]]
(lambda [n]
(helper 0 0 1))))

3-LISP supports so-called "higher-order" functions as well as first-order ones: namely, functions that take other functions as arguments, or return other functions as values. For example, the following function takes two functions as arguments, and returns a function as a result that is the composition of the original two functions:

(define COMPOSE
(lambda [f g]
(lambda [n] (f (g n)))))

1-1-h. Define a procedure called DOUBLE that doubles its argument, and simplify the following expressions (SQUARE was defined in problem 1-1-a, above):

((compose double square) 5)
((compose square double) 5)
((compose square square) 5)

Another simple higher order function is one that takes a single function as an argument, and then returns a function that applies the first function composed with itself. Call this function TWICE, and define a procedure that implements it. Your definition should support:

1> ((twice factorial) 3)
1= 720
1> ((twice 1+) 10)
1= 12

Did your definition of TWICE use COMPOSE? If not, define a version that does.

1-1-i. Define THRICE, analogous to TWICE (i.e., a function of a single functional argument that yields a function that composes that argument with itself three times). For example, you should have:

1> ((thrice 1+) 10)
1= 13

Using your definition, simplify the following expressions:

((thrice (thrice 1+)) 0)
(((thrice thrice) 1+) 0)

((thrice (thrice (thrice 1+))) 0)
(((thrice thrice) (thrice 1+)) 0)
((((thrice thrice) thrice) 1+) 0)

When trying the last of these, you should remember that typing ↑D (i.e., control-d) will interrupt and reset the 3-LISP processor. Estimate the number designated by the last of these expressions.

1-1-j. 3-LISP has two standard conditional expressions: IF and COND. As we saw in class,

(if (= 10 20)
2
3)

"returns" or simplifies to 3, and

(cond [(= 1 2) "that would be odd"]
[(= 1 3) "to say nothing of this"]
[$true "no surprise"])

returns "no surprise". Suppose someone thought they might like a slightly more expansive version of IF (we’ll call it IF*) that used the keywords THEN and ELSE. I.e., they would like to be able to write:

(if* (= 10 20) then 2 else 3)

and have it return 3, as above. Their first idea is to define a procedure IF* that ignores the two keywords. An attempt:

(define IF*
(lambda [premise then c1 else c2]
(if premise c1 c2)))

This doesn’t work — can you say why? (If not, try it.) One possible fix is to leave the definition unchanged, but to use it differently; viz:

(if* (= 10 20)
"then" 2
"else" 3)

This definition seems to work fine when used on the example above (try it), but it has a crucial problem. Can you identify it? (One way to discover it quickly is to use IF* in the definition of FACTORIAL you wrote in problem 1.) Can you fix the definition of IF*? If so, write a correct one; if not, say why not.

1−2. A Procedure for Approximating Square Roots

The following is a general procedure for calculating the square root of a number by approximation:

(define SQUARE-ROOT
(lambda [n]
(square-root-approximate n 1)))

(define SQUARE-ROOT-APPROXIMATE
(lambda [n guess]
(if (good-enough guess n)
guess
(square-root-approximate n (improve guess n)))))

In order to use these definitions, we need to define IMPROVE, of two arguments GUESS and N, that returns a better guess for the square root of N than GUESS is. The following will do:

(define IMPROVE
(lambda [guess n]
(average guess (/ n guess))))

1-2-a: Make this definition work by defining AVERAGE, such that (AVERAGE X Y) designates the number that is the average of the numbers designated by X and Y. Try it out on some examples.

We also need to define GOOD-ENOUGH. An appropriate definition is a bit subtle. As a first attempt, we define the following:

(define GOOD-ENOUGH
(lambda [guess n]
(< (absolute-value (- n (* guess guess)))
1)))

This works properly on perfect squares:

1> (square-root 16)
1= 4

1> (square-root 40000)
1= 200

But it has problems on numbers that aren’t perfect squares.

1-2-b: What is the problem with our definition of GOOD-ENOUGH?

In particular ways you will just have described, GOOD-ENOUGH imposes too strict a requirement on guesses. What we want, instead, is for the GUESS itself to be within 1 of the real square-root.

1-2-c: Define a new version of GOOD-ENOUGH such that (GOOD-ENOUGH GUESS N) = M implies that M is the closest integer to the real (positive) square root of N. You will need to assume for simplicity, for any x, y, and z, that if x is closer to y than to z, then f(x) will be closer to f(y) than to f(z). (In the terminology of calculus, this condition is described by saying that the derivative of the function in question is roughly constant within the range of the desired answer.)

Note: This whole exercise arises only because we cannot calculate exact quantities. Approximation — making do, in the most general case, with only partial information about the subject matter — is a constant theme in programming, not only in numerical programming but in a wide variety of applications. 1

1-2-d: It seems that we ought to be able to use the insights we have embedded in defining GOOD-ENOUGH to test approximations for lots of different functions. Define a more abstract (i.e., more highly parameterized) version of GOOD-ENOUGH, called WITHIN-1, of three arguments, so that the expression:

(within-1 guess function n)

is true just in case GUESS is the closest integer to the number X such that (FUNCTION X) = N. Assuming the definition of SQUARE suggested above, and given a proper definition of WITHIN-1,

(within-1 3 square 10)
(within-1 3 square 11)
(within-1 3 square 12)

should all be true (return $TRUE), whereas

(within-1 3 square 13)

should be false. Similarly, the following should be true and false, respectively:

(within-1 3 (lambda [n] (* n 10)) 34)
(within-1 3 (lambda [n] (* n 10)) 36)

Proceeding further in this general move towards more abstraction, we can define SQUARE-ROOT in a more abstract way, in terms of a general iterative improver called INTEGER-APPROXIMATION. The idea is that

(integer-approximation guess function n improver)

would cyclically test to see whether or not the current GUESS is close enough (specifically, within 1) of the real number that FUNCTION would map onto N. If so, it would return the GUESS; if not, it would repeat the whole thing, using (IMPROVER GUESS) in place of GUESS.

Note: As a convention, we use italicized names in 3-LISP expressions for schematic expressions. In other words, the code 5 lines back is meant to be a schema, instances of which would include the following (and an infinite number of other such expressions):

(integer-approximation 3 square 20 foo)
(integer-approximation (* 2 3) (lambda [n] (* n n)) $true [])
...

Sometimes these schematic expressions are called "meta-syntactic variables" — i.e., variables in the theoretic language in which we are describing 3-LISP. On our reconstruction, we should call them theoretic variables. This is a natural way to view them, since they function as terms we can use in our theoretic language to designate expressions in 3-LISP (the current object language). If they are variables at all, they are certainly theoretic variables; they are certainly not 3-LISP variables. When we get to the section of the course on notation and communication protocols, and the section on theoretic languages, we will be able to explain these things more precisely. 1

Given such an INTEGER-APPROXIMATION, we could define SQUARE-ROOT as follows:

(define SQUARE-ROOT
(lambda [n]
(integer-approximation
1
square
n
(lambda [guess] (average guess (/ n guess))))))

1-2-e: Define a straight-forward version of INTEGER-APPROXIMATION.

1-2-f: Chances are, your definition of INTEGER-APPROXIMATION calls itself recursively each time around the loop. Note that the second, third, and fourth arguments of your embedded recursive call are (probably) exactly the same as the second, third, and fourth arguments passed in at the outset. I.e., these three arguments will be exactly the same each time around the loop. This suggest that more power is being used than is really required. Define a more sophisticated version of INTEGER-APPROXIMATION, that doesn’t do any of this needless passing of variables. (Hint: See FIB-3, above.)