All Too Easy

One thing that I've learned about Friedman's class is to expect the unexpected. But one unexpected I never expected to expect was an easy homework assignment. Gilead posted the specifications of the assignment (we only got a preview in class today) - and I was done in 36 minutes. And the only reason it even took THAT long was because they had a tricky inconsistent definition in our test problems. There are several instances where the interpreter we were supposed to write had to recognize the empty list (everything in Scheme is built on lists) - and they had two different notations for it. Once it was shown simply as (), and another time as (list). I had only noticed the first kind originally, and I kept getting an obscure error about how the variable "list" was undefined - which seemed like an unlikely report considering that "list" is a keyword in Scheme! But then I realized that the error message wasn't coming from Scheme itself but rather from an error procedure in the interpreter we were supposed to write - and that's when it was clear that there were two notations for the empty list. So I just added one line to my code to deal with that, and everything worked.

Which gives me the eerie feeling I've missed something...

Not to worry, though, I should think because whatever it is I'm not sure how they'd know about it. The tests we were given as benchmarks, after all, WORK, so...

Which puts me in an odd position. I could turn in the assignment today - roughly a week early, and run the risk that Friedman will notice and realize the assignment was too easy and make it harder. I could really do with the extra time this weekend, so I don't wanna do that. On the other hand, the brownie point factor...you know? But I've decided to wait. On the off chance there IS some kind of "easter egg" in the assignment that we're supposed to notice but which doesn't show up in the tests, and also with the hidden motive of not doing more than I have to - I've decided to wait. I'll mull over it, and if something occurs to me, then I have until Sunday. If nothing occurs to me, I'll just turn in what I have and assume that was all there was to it.

The concept being taught, though, is very interesting indeed. It has to do with the difference between lexical and dynamic scope.

Now, Scheme is fiercely lexically scoped. That was, in fact, one of the original design considerations. Scheme is often called a dialect of LISP - and that's fair because it clearly took LISP as its model. It appears to many as a scaled-down, minimalist version of LISP. I would consider it a fully separate language myself, though. Maybe the way Romanian and Italian are different human languages. Or Spanish and Italian (Scheme and LISP really are close). Reason being - when Scheme was introduced it was introduced as an extension of the Lambda Calculus - i.e. was a kind of philosophy on its own. It was meant to be a contribution to computational theory, not just the "cleaned-up" version of LISP that it is often taken to be. And one of the things that made it different was this fierce devotion to lexical scoping.

So what is lexical scoping? So glad you asked. One of the primitives in programming is something called a variable - everyone knows what that means. It's something whose value can change, obviously, hence the name. You store information there (it's best to think of it as a name for a memory location that you want to refer to many times in a program) and perform operations on the information. Well, Scheme's main concern was semantic clarity - and so it took the fairly radical position that insofar as possible, variables shouldn't change. Sounds like an abuse of term, right?

From a certain programming perspective, it is. But that's what I meant in some earlier posts about how there's a learning curve to Scheme. You really do have to think differently to appreciate it. At first (as I well remember), Scheme just seems like a frustrating, completely counter-intuitive waste of time. But the more you work with it and the more "Scheme-like" your brain becomes, the more you realize how elegant and powerful it is. (By the way, at the end of Nathan's series of pictures of saws and swords as programming language analogies, I would have chosen the katana rather than the foil as the Scheme metaphor. A katana is simple, elegant, finely-crafted and powerful. The foil is definitely simple and light, which is I guess what Nathan was going for, but it doesn't require much training to use and doesn't have all that much power. I should speak to him about this.) This fierce devotion to lexical scoping and the fact that it makes it difficult to change variables is one of the hardest things to get your mind around. However, soon you realize that meaning in Scheme is at the level of the function call - not the operation so much. And so once you get used to recursion, you realize that when you want to change a variable, you just call the function your in on itself with a new value. Nice, eh?

That's lexical scoping. Variables are bound at the time of the function call - and they stay the same for the duration of that call - in that environment.

Here's some example Scheme code from the assignment:

(let ([x 2])
     (let ([f (lambda (e) x)])
       (let ([x 5])
         (f 0)))))

What's going on here, for the Scheme-uninitiated, is this. First x is given the value 2. Then we make a function (lambda is Scheme for "this is a function") that takes one argument (call it 'e') - and it returns x. Of crucial importance here is that 'e' doesn't actually do anything - it doesn't need to be there. All the function does is tell us what x is (silly, I know, but this is an example). Then we define x to be something else - 5 - and THEN we call our function f by passing it 0. When the function call happens, of course e gets the value 0 - but this, as we've already established, means nothing - because e is never used. Cute. So f returns x - and x is....(drumroll)....?

2 of course! Because that's what it was when we defined the function.

That's lexical scope. At the time a function is defined, all the variables are clear, and they don't change within the scop of that function. Scheme is very concerned with "meaning" and keeping things consistent (one of the main reasons I like it - as anyone who read the earlier post on politics will know).

If we had dynamic scoping, however, the value of this code would be 5. And that's because the value of x would have been clobbered, and the new value would be the most 'recent' value.

That's the difference. "Lexical scope" means - keep the value at definition time for whatever function it is. "Dynamic scope" means - value can change, use whatever value is most "current."

So - our assignment was to add dynamic scope to Scheme. We have been writing interpreters - programs that read programs and tell you what they mean (Python, for example, is an interpreted language - it's really just a program in C that reads "Python" code and tells you what it "means" - that is, what value it would return in the end if Python were a stand-alone language. C, on the other hand, is "compiled." There is a program that reads C code and turns it into machine language specific to the computer you're working on - translates it into machine language.). The interpreter we've been writing is written in Scheme, and it reads Scheme code and tells you what it means. (!!!) Counterintuitive concept, eh? Scheme that reads things written in Scheme - I mean, what's the point, right? But as a pedagogical tool it's quite valuable - because in principle it's the same concept. I could, if I wanted, just change it to output Python code or something. But this is beside the point.

The point is, we've been writing programs in Scheme that read other programs in Scheme and tell you what they mean. So this makes it easy to add dynmaic scope. You just add, to your interpreter, a new kind of function - call it dynamic-lambda instead of lambda. And you tell the interpreter how to handle it. Very simple. And indeed, it is - shockingly simple. What you do -the "trick" - is that you "remember" all the variables in the program by storing them in a list. When your interpreter sees a lambda call - you "interpret" this as a function that takes a value and the list of variables as arguments. So you just wrap your function that you're reading in another function. And then within this function - depending on whether it's lambda or dynamic-lambda, you tell it how to handle the variables. Specifically - you tell it when it looks up a variable to use the list that was present at the time it was created (if it's lexical lambda) or to use the list that is passed to it when it's called (if it's dynamic lambda).

Very simple. And yet the effect on program behavior is dramatic.

It's not just about preserving "meaning" at each level, in fact. The more estute of you will have noticed that the interpreter that only deals with lexically-scoped functions is actually more efficient. This is because if we only have lexical scoping, we don't have to pass a new list of variables into the function when it's called at all!!!. You can just define the function with the list of variables already in it. It is the dynamically-scoped function that has to take this second "environment" argument. For consistency in the interpreter, we have to enfoce this formally on the lexically-scoped function too - but it doesn't really need it. So there's a tiny bit of bloat associated with dynamic scoping. One of the reasons why Scheme is so fast, I guess, is because it doesn't have this bloat - and also becuase the streamlined definition (there is only one type of scope) makes it easy to write Scheme compilers (you don't have to deal with as many situations in Scheme).

But of course, as this assignment well demonstrates, if you happen to want dynamic scoping in Scheme, it's easy to add it in.

The question is why would you want it? Well, in fact, there are advantages. Gilead explained this in class today. Suppose we have a function called
addnum, an it's purpose in life is to add a fixed number to whatever number you pass it.

(define addnum
 (lambda (n)
  (+ x n)))

So this function takes an argument and adds 'x' to it. Whatever 'x' is. Let's say, for a time, we want a function that adds 2 to our argument. Simple - we just throw in a (define x 2) line, and it's done. If we later are in a situation where we have to add 5 to a bunch of stuff, we just clobber x by redefiniting it to be : (define x 5). Same function, but now it does something new. So dynamic scoping gives you the power to change the behavior of a function from without.

Now, the Schemers would argue (and I would whole-heartedly agree) that this is a silly way of looking at life. Surely we want our functions to stay the same. If you need a function that adds some fixed number to another number, why not just pass in the number you need added as a second argument? Well, OK, is the response, you could - but that's a bit inefficient, no? Why pass this argument in thousands of times when we can just have a function that adds 2?
To which the Schemers would respond - well, fine, have two functions then! Better yet, have a function that builds these functions itself:

(define adder-builder
  (lambda (x)
  (lambda (n)
   (+ x n))))

This is a function that takes an argument (whatever fixed value we want to add to things over and over again) and returns a function that performs the specified task.

And that's what I like about Scheme. Higher-order functions. Functions that make functions. Programs that write programs. Scheme is such a beautiful thing!

Yeah, fine, it's not quite as tight as letting yourself just clobber the value of x whenever you need. But it keeps all the meanings straight - and that's what's more important.

Friedman et al want to say that there is some global ethical philosophical reason why lexical scoping is better. Which is one of the reasons it was nice having Gilead teaching class today - because this is one time I could have done without the soapbox. Yes, yes, of course I'm on Friedman's side. I like my programming languages lexically scoped too. I'm a HUGE Scheme fan (as the masses upon mases of regular readers of this blog have no doubt figured out by now). But Gilead was reasonable about it - and said that there was no problem in principle with dynamic scope if that's how you're used to doing things. And indeed, he's right.

Perl is a language like that. All variables are global unless you specifically say otherwise. So it's sort of the anti-Scheme in that sense. And I find that feature of it highly annoying. But there is, of course, no use denying that lots of smart people write efficient code in Perl. So the fucked-up scope rules are manageable, if you know what you're doing. No doubt they find the way we do things equally frustrating. Actually - probably more so. since to them it would seem like we're unnecessarily limiting what we can do.

To which the appropriate response is a smug smirk.