A few speed bumps

It's a bit hard to recall the process by which I changed my mind about Lisp. I remember the first couple of '001 lectures because they directly contradicted what I thought I knew. I didn't become an immediate lover of Lisp by any means, but my antipathy was much weaker. There are a few incidents that do stand out in my memory. The first one was 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 polynomialx^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.