I've had this project on the supreme back burner for a few weeks. My initial attempt at Lambda the Ultimate just wouldn't come together and I have been coding like crazy on this other project I am doing with Narwhal and CouchDB for one of my professors.

Speaking of that project, working with JavaScript as my server-side, client-side, and query languages has been a lot of fun. Turtles all the way down, and all that. One product of the project (so far, not close to done yet) is Reform. I didn't expect the amount dynamicism that this nurtures. I don't have any definition of my documents or schemas except for the forms that I define with Reform. My data is truly fluid in a way that doesn't happen even when I use Python with CouchDB.

But back to Scheming: Today I revisited my Scheme interpreter in Ada and my non-working implementation of Lambda the Ultimate. Where an unbreachable brick wall had been before, now a mere fence lay. The fence even had a gate, though it took me a while to look over and see it from where I was at. I found and fixed that annoying bug in my Lambda implementation that was breaking everything.

Embarassingly enough, it was a one line fix.

You see, Ada has this great idea that there should be some way to segregate pure functions from ones that perform side-effects and mutate data. From what I gather, Haskell does similar segregation, although via certain monads. (I haven't tinkered with Haskell yet, but I just finished Simon Peyton-Jones' interview in Coders at Work. Go buy that book, I'm halfway through and it is great.) People seem to really like the way Haskell does it. Of course, Haskell and Ada are almost polar opposites and I do not like Ada's implementation of this segregation at all. It all goes right out the window as soon as you start dealing with pointers, and frankly its annoying refactoring a "pure" function when you realize it needs to perform side-effects as a procedure with an "out" parameter. Although the refactor is a straight forward process, you need to spend some time finding every call to the old function and rewriting them as procedure calls. Time that could be better spent making progress with the code. 

-- Function calls like this
foo := func(bar, baz);
-- must be rewritten as procedure calls, like this
proc(foo, bar, baz);
-- everywhere func was ever called.

Some of the rules feel almost arbitrary, too. I can't rebind a parameter's symbol to another value while, in this case, iterating through environments and parent environments. You have to make a copy of that parameter, and then you can do whatever you like. Here is the fingerprint of the problematic function: 

function Lookup_Variable_Value (Var : Access_Object;
                                Env : Access_Object) return Access_Object;

The purpose of this function is to take a variable's symbol and return the value associated with it by finding it in the current environment, or the parent environments. Now, one of the requirements of implementing a "real" Scheme, is that tail calls be optimized. Ada doesn't do that, so I have to do it myself via loops all over the place, just to be safe. This function is one such example: I have to use a loop, and after an iteration, if the variable isn't found, I added this little line of code to change "Env" to the next environment for the next iteration. 

function Lookup_Variable_Value (Var : Access_Object;
                                Env : Access_Object) return Access_Object is
   -- <Local variable declarations>
begin
   loop
      -- <Look for variable in the environment and return the value if found>

      -- Get ready for the next iteration.
      Env := Enclosing_Environment(Env);

      -- <Exit loop when there are no more environments to check>
   end loop;
   -- Variable is not found
   raise Constraint_Error;
end;

Uh oh, not compiling. Argh, I'm not trying to perform side-effects, what could be wrong?! Well, Gnat thinks that I'm tring to mutate the value associated with "Env" by changing it to the next environment, when really I just want to re-associate the local symbol "Env" with the next environment. The first would perform side-effects in the world outside of this function, the second wouldn't. The solution is to copy the "Env" parameter from the start and replace all operations involving "Env" with operations on the copy. 

function Lookup_Variable_Value (Var : Access_Object;
                                Env : Access_Object) return Access_Object is
   -- <Local variable declarations>

   -- Make a copy of the parameter, so that we "own" it.
   This_Env : Access_Object := Env;
begin
   loop
      -- <Look for variable in the environment and return the value if found>

      -- Get ready for the next iteration.
      This_Env := Enclosing_Environment(This_Env);

      -- <Exit loop when there are no more environments to check>
   end loop;
   -- Variable is not found
   raise Constraint_Error;
end;

Which is exactly what I did a few weeks ago. Although it was compiling, it was throwing Constraint_Errors every time a variable lookup happened outside the global scope. 

> *
; #<primitive procedure>
> (define (square x) (* x x))
; ok
> (square 5)
; Error: Unbound variable "*"
Restarting REPL

This is where I was at after coming back to my code. I spent some time adding print statements, and then I looked up and saw that gate in the fence that had previously been a brickwall. I felt silly, why hadn't I seen it earlier? It was such a stupid little thing!

When I was changing all references of "Env" to "This_Env" in the body of Lookup_Variable_Value I had forgotten to change a single reference.

Here is the commit that fixes everything.

All said and done, I feel great though: My first ever implementation of Lambda the Ultimate is complete! I can't explain how cool it feels to me. 

> (define (factorial x)
    (if (eq? x 1)
        1
      (* x (factorial (- x 1)))))
; ok
> (factorial 2)
; 2
> (factorial 3)
; 6
> (factorial 4)
; 24
> (factorial 5)
; 120
> (factorial 10)
; 3628800