Wednesday, March 18, 2009

Everyone Needs a Little Closure...

When I see the word closure in computer programming forums and email lists, it means means something completely different from common usage. When lisp people talk about closures, they are just talking about data, not concluding a difficult time of their life. Most people know what a function is, so let's start there. Functions can declare variables to store data inside the function. Now, what would happen if you moved the variable outside the function? In C this would break something, but in Lisp it is allowed. The most natural thing to assume is that the variable will continue to exist even after the function is done. By declaring multiple variables and returning a function that can get and set them, you have created a basic class. So closure is just another funny word for something simple.

Not exactly. While it is simple in theory, the implementation can get a little hairy, as I recently found out. In order to solve a set of related problems at work, I developed a quick Lisp-style interpreter. I used Paul Graham's Lisp-in-Lisp example from McCarthy's original implementation. Only, I did it in C. Not a big deal, the code is straightforward and the work was easy. I had a working REPL running from the command line in no time. By using a simple list for the variable names and pointing to the last one on the stack, I had workable function and variable environments. Not fancy, but better than I had before and still fast enough for what I'm doing.

Then I started playing around with it. I put in something like this:

(let ((x 1)
(y 2))
(fun get-x () x)
(fun get-y () y))

But when I called it, it couldn't find the variables! What in the world was going on? Well, in my simple stack-based environment once the variables were out of scope, the environment discarded then. My other functions worked fine however, and I didn't want to change they way they worked. Then, after a little while I understood what the problem was. When I define a function with lambda, I interpret it as a typical form. For example, (lambda (x) (...blah, blah, blah)). But when I invoke the function it evaluates to this: ((lambda (x) (...blah, blah, blah)) 'argument). I realized that if I create a lambda but don't run it, I would need to somehow save the variables it references.

That was well and good, but I already had my language defined. I really didn't want to create new 'placeholder' commands for my functions. I thought about hiding them with a special (extended) character. I almost made a closure a special object type. The more I thought about it, the more I intuitively knew there was a better solution. So, I did what I always do in this situation: I manually walked my way though the whole process.

What I found was, except for the arguments, all other variables were outside the function! I was ecstatic. I could simply recurse through the function and replace the variables and functions with their current value. Simple! Anything I couldn't find must be looked up dynamically. Then I tried to run a simple example. It broke.

It turned out that I was trying to look up the value of each item which was already done. I needed to find a way to keep that from happening. I started to make a special closure eval and eval-list but then it hit me: all I had to do was quote the values instead of the symbols, that would keep them from being evaluated. I made the change and it worked like a charm. I made a quick test to see what would happen:

(let ((x 1))
(fun test-closures (y)
(let ((x 2)
(z 100))
(list x y z))))

(test-closures 5)

I got a warning that symbol Z was not defined and would be looked up dynamically but it ran and returned:

(1 5 100)

At first I was just happy it ran, but looking at the first value, 1, I knew it wasn't working correctly. From the debug trail I saw that symbol x was being replaced with 1 everywhere. Since it is a valid name, let didn't give me any issues, but the value was set to 1 for every instance of x. So much for being clever. It works fine for the time being, but I will need to change create_closure() to add the name/value pairs to the environment instead of changing the code. I might add some values which are not needed but that shouldn't be too bad for a small interpreter.

I guess this just goes to show how much thought creating a language really takes. Lisp is very subtle, mathematically so. Looking back on writing my little language has given me a new found respect for those who have made "full" usable languages. And I have even more for those who implemented Lisp and Scheme. Once I finish this, I think I'll work on garbage collection.

No comments:

Post a Comment