Monday, September 18, 2006

Call it how You Like it

Here's a cool little concept courtesy of Oleg Kiselyov, who, for the uninitiated, is a Certified Programming Languages Badass and also happens to be one of the co-authors on Friedman's awesome-but-difficult new book.

The idea is to demonstrate that you can have call-by-reference semantics in Scheme - with a minor bit of work.

Call-by-reference, for the uninitiated, is the idea that when you pass a variable to a function in a programming language, the function can actually modify that variable. Under the more usual call-by-value, what happens is that the function just gets a copy of the variable, which it then does computation on. Nothing changes in the program proper, it merely gives you an answer.

To illustrate - let's say I have a function that converts Fahrenheit to EuroSpeak. I might have my temperature stored in a variable called "temp." Now, in "temp" I have some meaningful number, like 47. If I want to tell my European friends how hot it's not, though, I have to translate this into something they can understand. Now, I don't know how to do that by myself, so I use my function. Feed the temperature into the mysterious black box by value, and I'm told that 47 is apparently 8. Wonderful. Fortunately for me, though, I passed in "temp" to my function by value, so the function only really got a copy of it, and I still know that the temperature is 47. Had I passed it by reference, then my function would have changed the value of "temp" to something meaningless like 8.

I don't want to give the impression that passing by reference is ipso facto a bad idea. There are times when it's very useful. To use another example - if I had a list of bills and I wanted to see them in order from highest to lowest - I might pass in an array of all these values to some function that orders things from highest to lowest. If I do this by value, it will copy everything in the array and then sort the new copy and then return the copy, which I then have to assign to my old array, and woah that's a lot more work than we really need to do! It would have been simpler just to call by reference and let the function play with my array directly.

OK, OK, well, to the point. The point is that Scheme, like most programming languages, just assumes call-by-value. This is for reasons of semantic consistency. We like to believe that what's going on in a function only effects things in that function. After all, functions are like little mini-programs. We'd like to keep all programs separated out.

Ok, but what if you WANT call-by-reference (like in our array example)? Well, this being Scheme, the answer is "if it's call-by-reference you want, then it is call-by-reference you shall have! (But I don't want to do anything immoral, so you'll have to show me how to do it without violating my design specifications.)"

And that is exactly what Oleg did. It's very clever, I think. The basic idea is that when you make something into a reference, all you do is wrap it in a small function that handles it appropriately. Then, rather than passing the actual variable to the calling function (our Temperature translator, for example), what you do is pass this wrapper function. The wrapper function has the ability to change the variable in the global namespace (using set!).

This is indeed a very cool solution. It doesn't violate any programming principles - functions in Scheme still create local namespaces i.e. are still closures. All changes to the global namespace are contained within a function, so you know where they are. The semantics come out the same regardless. So I'm impressed.

The function call looks like this:
(convert (& x))

Notice that the variable - x - is passed in as a function (a call to '&' - which is of course chosen to mimic C/C++ syntax) rather than as a variable. This enforces a principled difference between the situations - as it probably should. Call-by-value (for anyone who doesn't know) looks like this in Scheme (convert x).

Nice little example of how cool Scheme is. Now - I'm really curious whether this is possible in Java. Friedman made a good case last year for Object Oriented Programming being a Bad Thing for a similar kind of reason - that it allows you to violate lexical scoping rules in undesirable ways. So it's entirely possible that Java can do this too, but of course it would be clumsy about it. You would have to make the variable into a class or something, and who knows ahead of time to go to all that trouble? Making a simple variable into a class is a lot of work! Scheme can get you the same messiness that C/C++ has by default, but by a much simpler method than the hoops you would have to jump through in Java.

And so once again we see that good will always triumph because evil is dumb.


Post a Comment

<< Home