`LET`

expressions.I remembered from my first encounter with Lisp that there were these things called ‘lambda-expressions’. A lambda expression allowed you to make a temporary name for some quantity. Suppose you had some code that had a common subexpression like this:

(/ (+ (* x x) 2) (* x x))and you wanted to pull out the common subexpression, you'd do this:

((lambda (temp) (/ (+ temp 2) temp)) (* x x))I admit that that is pretty weird, but for some reason I was able to remember it.

Of course assigning names to certain subexpressions is something you do all the time in any computer language. While it is nice to know that you can do this with a simple function call, an embedded lambda expression like this is not the clearest way to express it. The values of the bound variables are too far removed from their names.

Lisp's

`LET`

expression is a very handy bit of syntax that fixes that
problem. It looks like this:
(let ((temp (* x x))) (/ (+ temp 2) temp))But I found this to be a bit confusing. There seem to be too many parenthesis here. And there is something irregular going on because if you bind two variables, it can look like this:

(let ((count 22) (tail elements)) (if (null? tail) ....Which seems to have too few parenthesis at first glance. Or maybe three variables looks like this:

(let ((ok '()) (count 1) (tail (cdr elements))) (if (null? tail) ...Which seems to have both problems.

It wasn't obvious to me what was going on. My brain kept telling me that when I saw a pair of open parenthesis I should expect a pair of close parenthesis at the other end. That's simply not true. I learned to parse

`LET`

expressions sooner than I learned to write them.
I'd write out the lambda expression first and then carefully transform
it into the appropriate `LET`

expression.It took me a bit of practice (not much, maybe a few days worth) before I was comfortable with

`LET`

expressions. Even these days I will on
occasion use non-standard code formatting to reduce ambiguity.
(There is a balance between parsimony of expression and ambiguity.
A larger Hamming distance between legitimate programs will help
protect you from typos, but it will also make your program text quite
a bit more verbose.)It can be tricky getting the right number of parenthesis. The editor can help balance them, but it doesn't help if you have correctly balanced an incorrect number of parens. Sometimes this leads to a syntax error, but sometimes it leads to syntactically correct program that bombs out. The usual error is something like ‘The object 3 is not applicable.’ If you wrap an extra set of parenthesis around a function that you intend to pass as a first-class object, you'll end up invoking the function and passing the

*result*instead. Then somewhere later on when you think you are invoking a function, you'll get that error. The problem isn't just the presence of extra parenthesis; it is the fact that the extra parenthesis may indicate a perfectly valid program (one with an extra level of function invocation) that isn't the one you thought you wrote.

The second speed bump was when we got to compound data. I had seen linked lists in the prior course, and I'd written down box and pointer diagrams before, so I had a tiny head start. Despite this, it was not particularly easy. It's hard to remember when to use

`CONS`

, `LIST`

, or
`APPEND`

, or whether you want a quoted list of literals or a list of
quoted literals. Sometimes I admit I just flailed around and tried
the different combinations until it worked.A particular problem stands out in my mind. We were doing arithmetic on univariate polynomials with integer coefficients. Each polynomial had a `term list' and each term had a coefficient and an ‘order’. So the polynomial

`x^3 + 3x^2 - 7`

would be represented like this:
`((1 3) (3 2) (7 0))`

The problem set already had a skeleton for the division program:

(define (div-terms L1 L2) (if (empty-termlist? L1) (list (the-empty-termlist) (the-empty-termlist)) (let ((t1 (first-term L1)) (t2 (first-term L2))) (if (> (order t2) (order t1)) (list (the-empty-termlist) L1) (let ((new-c (div (coeff t1) (coeff t2))) (new-o (- (order t1) (order t2)))) (let ((rest-of-result <compute rest of result recursively> )) <form complete result> ))))))This isn't a particularly hard problem, but it has a subtle pitfall. The function really wants to return two values, a quotient and a remainder. Instead, it returns a single value, a

*list*of a quotient and remainder. The caller will need to extract those two components in order to use them. Now since this function is recursive, it is itself a caller and therefore has to destructure its own answer. So where we see this code:

(let ((rest-of-result <compute rest of result recursively> )) <form complete result> ))))))We'll have to do something like this:

(let ((rest-of-result <compute rest of result recursively> )) (let ((rest-quotient (first rest-of-result)) (rest-remainder (second rest-of-result))) (list <form complete quotient> <form complete remainder> ))))))))Sticking a single term on to the front of a term-list is done by calling

`CONS`

. Creating a term from a coefficient and order is done by
calling `MAKE-TERM`

which is essentially an alias for
`LIST`

.An experienced coder would already notice a bunch of red flags by now. This is starting to get confusing and it would be a good idea to be real careful. Unfortunately, at that time I was an inexperienced programmer. I started in a confused state and didn't know how much more confusing it could get, and I was already being as careful as I could be.

So what are the potential pitfalls? The most difficult one to deal with is incorrectly destructuring the recursive result. If instead of using

`FIRST`

and `SECOND`

you used `CAR`

and `CDR`

, you'd get the quotient
correctly, but rather than the remainder you'd get a list containing
the remainder. At each recursive step this list would get deeper and
deeper and you end up with some very deeply nested list structure.The second pitfall is to

`CONS`

the quotient and remainder
together rather than to `LIST`

them. Both produce list
structure, but the other places where answers are returned use
`LIST`

, and the problem statement says that a *list*is returned. If you

`CONS`

the quotient and remainder
together, you'll have one of two problems. If you have correctly used
`FIRST`

and `SECOND`

to destructure the
recursive call, then the cons cell you generated will end up being
destructured ‘too far’. Instead of a remainder that is a list of
terms, you'll end up with a remainder that is a single term dropping
the other terms. You'll probably notice the missing terms when you
finally get a result, but you may not know where they disappeared.On the other hand, if you incorrectly use

`CONS`

to
construct the recursive result, *and*incorrectly used

`CAR`

and `CDR`

to destructure it on the
recursive call, nearly everything will ‘work’. Of course
you will not have satisfied the problem statement that the result is a
*list*of quotient and remainder, but it will be made from ‘list structure’. But the innermost remainder will have been produced by one of the other clauses that return answers. Since these use

`LIST`

, the innermost remainder will have one
extra level of list structure.Have your eyes glazed over yet? This is a mess, and I can see why it is a stumbling block. There are some obvious ways to fix it within Lisp (using structures, self-descriptive data, and predicates to ensure the answers are well-formed) or outside Lisp (using a language with static annotations to get the compiler to prove that the answer is well-formed), but that's not my point. List structure can be confusing, and you have to trade the convenience of just consing up a data structure versus the complexity of debugging the code.

It seems to me that this particular problem set could have been made an awful lot easier by first having the students write some defensive code that checked its arguments and such, but I'm not sure if the point of the exercise is to either discover this yourself, or to force you to

*think*a bit harder about what you are doing (it really only takes an extra few minutes to reason things out at the level of detail you need), or just to get you used to the kind of nested list structure you are likely to find in legacy Lisp programs. Or maybe I'm singling out this particular problem set because it was tricky for me.

This comment has been removed by the author.

ReplyDeletei like your posts in this series

ReplyDeleteI now regret clicking "More Detail" on the last post... ;)

ReplyDeletePersonally, I never got tripped up with first/second car/cdr, but I will admit to creating complicated list structures resulting in much write-only lisp due to the incomprehensible structuring and destructuring embedded in the functions.

I would be interested in hearing further about the ways to write clearer, more readable code, especially in a language like Scheme without a formal object system.

Kyle you should take a look at _How To Design Programs_.

ReplyDelete