Series vs. streams

A generator is an abstraction of a sequence of values. It is a procedure that returns the next value in the sequence each time it is invoked. The generator can run out of items to return at some point if the sequence is finite, or it can keep generating values if the sequence is ininite.

A generator is decidely non-functional. Each time it is called it has the potential to return a different value. But let's make it functional. Instead of returning a single value, let's return two values: the next value in the sequence and the next state of the generator. The generator can now be pure functional and return the exact same two values each time. The caller will keep track of the current generator will replace the current generator with the next one returned by the call.

We implement generators as a promise that returns a pair of the next value and the next generator. The returned pair is what S&ICP call a stream. In other words, a stream is output of a functional generator that is 180 degrees out of phase of the generator.

Streams are similar to series in that you can write computations that operate on the aggregate stream, but it will be piplined to operate one element at time. But rather than having the compiler perform a code walk to set up an explicit pipeline, the runtime system sets up an implicit pipeline through the constraints of the promises. This makes streams a bit more flexible than series.

Series are more efficient than streams because the compiler can turn the implicit pipeline into an explicit one that is easy to optimize. Streams turn into a series of nested lexical closures with the attendant overhead.

One of the difficulties in using streams is that you often have to pay very careful attention to avoid fencepost errors and generating elements one beyond what is necessary. This isn't just a matter of using up a tad more storage, but it can lead to unexpected infinite loops because you attempt to reach one beyond the base case. Very often you find that you need two versions of each function: one that takes a stream argument, and one that takes a generator argument that you are careful to avoid calling unless necessary.

Streams are lazy by nature. Laziness introduces a need for static types. If you have a computed value, you can examine it to find out its type, but if you have a promise, you cannot tell what type of object it will return without forcing the promise. You cannot do a type dispatch on a promise because you don't know what it will return. A static type would indicate the type of the returned value without forcing the promise.

Series requires that the entire pipeline from source to sink be visible to the compiler. Streams do not have this requirement.

Despite their drawbacks, I rather like streams. I use them in my linear-fractional-transformations package to represent exact real numbers as streams of linear fractional transformations. I also use streams of integers to represent the continued fraction expansion of exact real numbers.

Lisp: Second impression

My first impressions of Lisp were not good. I didn't see how navigating list structure was of any use. It seemed to be just a more cumbersome way of getting at the data.

In fact, my first impressions of computer science were not very positive. I enjoyed hobbyist coding on my TRS-80, but “real” programming was tedious and the proscriptions of “doing it the correct way” took the joy out of it. I explored other options for my major. Fate intervened. Over the next year I realized my calling was EECS, so in my sophomore year I took all the intro courses.

I had heard that the introductory computer science course used Lisp. That was disappointing, but I started hearing things about Lisp that made me think I should take a second look. I learned that Lisp was considered the premier language of MIT's Artificial Intelligence Laboratory. It was invented by hackers and designed to be a programmable programming language that was infinitely customizable. The lab had developed special computers that ran Lisp on the hardware. The OS was even written in Lisp. I wasn't looking forward to car and cdr'ing my way through endless cons cells, but I figured that there had to be more going on.

6.001 was unlike the prior computer courses I had taken. The course was not about how to instruct a computer to perform a task — the course was about expressing ideas as computation. To me, this seemed a much better way to approach computers. Professor Hal Abelson was co-lecturing the course. He said that he chose Lisp as the teaching language because it was easier to express ideas clearly.

Two things stood out to me in the first lecture. Professor Abelson showed the recursive and iterative versions of factorial. Of course I had seen recursive factorial from the earlier course and I knew how it worked. Clearly the iterative version must work the same way. (One of my early hangups about Lisp was all the recursion.) I was suprised to find out that the Lisp system would automatically detect tail recursive cases and turn them into iteration. Evidentally, the makers of Lisp had put some thought into this.

Professor Abelson also demonstrated first class functions. He wrote a procedure that numerically approximates the derivative of a function. He then used that in a generic Newton's method solver. This is all straightforward stuff, but to a newbie like me, I thought it was amazing. In just a few lines of code we were doing simple calculus.

It was a mystery to me how first class functions were implemented, but I could see how they were used in the Newton's method solver. The code Professor Abelson wrote was clear and obvious. It captured the concept of derivatives and iterative improvement concisely, and it effectively computed answers to boot. I had to try it. Right after the lecture I went to lab and started typing examples at the REPL. Sure enough, they worked as advertised. A tail-recursive loop really didn't push any stack. It didn't leak even the tiniest bit of memory, no matter how long the loop. I tried the Newton's method solver to take cube roots. I passed the cube function to the derivative function and the result was a function that was numerically close to the derivative.

Now I was a bit more impressed with Lisp than I was earlier. I wasn't completely sold, but I could see some potential here. I wanted to learn a bit more before I dismissed it entirely. It took me several months to become a Lisp fan. The parenthesis were a small hurdle — it took me a couple of weeks to get the hang of let forms. There was a week or two of navigating cons cells to wade through. But I eventually came to love the language.

My first impression of Lisp was poor. The uselessness of traversing random list structure was unmotivating. My second impression was better. Professor Abelson teaching directly from preprints of S&ICP might have had something to do with it.