The Blog

Life has been hectic as of late. Details will remain sparse, but I plan to get some writing up on this blog soon, but, as the title implies, this blog post is about the blog itself. Part of the reason that I have had gaps between posts here is that, by nature, I am a person with many interests and, while computers are a big one, they are by no means the only one. So, I am going to take a moment to admit what some of them are.

Literature. I love literature, poetry, folklore, and mythology. So much so that going back to school to work on an MA and PhD in English literature sounds lovely–except that I don’t have $100K to spare.

Music. I have recently begun trying to learn guitar. My wife bought me a guitar over a year ago. During the last  few months of her pregnancy with our first son, I lost complete track of this attempt. As far as music  that I like, I like some Christian contemporary (though not much), Celtic in all flavors, some folk, and some oldies rock.

Writing. I have a pile of finished or partially finished short stories that I have been writing as well as a partially put together novel manuscript.

History, politics, philosophy, and theology. I have an interest in all of these things, though not, perhaps, as deep as some of my other interests.

Anyway, I mention it because this blog probably, in order to prevent these times of radio silence, will begin including anecdotes from my other interests. Anyway, stay tuned!

Work on the Bootstrapper

Work’s been hectic lately, so I haven’t had as much time to work on Ocean, with other responsibilities at home and such. Anyway, here’s what’s been happening of late. The byte code generator for the bootstrapper is almost done. So, as the ultimate test, I started writing the interpreter. Nothing fancy, nothing interesting (yet). I quickly hit a roadblock. Picking types for fields works pretty well, however, types for functions (methods, if you prefer that parlance) do not. The return type is not inferred at all, which causes an issue when trying to infer types for some variables and the parameter types are also not inferred. The attempts to fix these bugs quickly and easily have resulted in some clumsy code (like, for example, a “junk generator” that is used to generate “throw away” byte code and infer types).

So, a decision needs to be made. Here are the ideas I am looking at. Resurrecting the C# interpreter (it was deleted from Subversion a while ago) and using it to interpret the compiler compiling itself and the “real” interpreter. This has a great deal of merit. The C# interpreter was pretty much working, except for a few features that were missing like continuations and macros. This need not be a problem. I do not typically use either feature when writing Scheme code and could probably avoid it. However, it might prove to be easier to use these advanced features in the code for the “real” compiler, as it is planned to include some rather beefy features behind the scenes. This is not a deal breaker for two reasons. First of all, the language the bootstrapper understands does not currently support either of these features, so if the interpreter does not offer them, it is not losing any ground. Continuations could probably be implemented slowly, but accurately in this ethereal “bootstrapping interpreter” without too much extra work. Alternatively, something truly odd (and slow) could be done. The C# interpreter could be used to interpret a fully featured interpreter which itself interprets the compiler compiling itself and the fully featured interpreter. So, the idea would look like this:

C# Interpreter -> Scheme Interpreter -> Compiler (as it compiles itself and the Scheme Interpreter).

The idea wouldn’t be fast when building, but it would allow fully featured code to be used in the compiler itself. If continuations were added to the C# interpreter and macros (through an external library, perhaps) to the Scheme, the work could be split and all the features attained.

The competing plan of action is to continue implementing the bootstrap compiler. The compiler itself could use a simple, aggressive form of SUA based on Algorithm 2.1 in the paper “Storage Use Analysis and its Applications” by Manuel Serrano and Marc Feeley (available here). Types could then be inferred and the code cleaned. Continuations could wait until they are built with the final compiler and macros could be added to the interpreter as above so that the picture becomes:

C# Compiler -> Scheme Interpreter -> Scheme Compiler  (compiling itself and the interpreter)

We could then gain macros, but not continuations, when writing the compiler itself and we could use neither in the Scheme interpreter. The build, however, should be much quicker.

What to do? I am leaning heavily towards the latter and will probably start writing some code to see how it works out. I expect macros to be a far more important feature for this type of work than continuations which are, largely, a fancy form of goto. If continuations are used often, it amounts to high-brow spaghetti code, made with bigger and badder spaghetti.

Ruminations on Continuations and Ocean

Continuations have been one of the features that I have been the most anxious to include in the 0.1 release of Ocean. Why? Quite simply because it is not done often enough. Most .NET/JVM implementations of Scheme offer half-hearted or no support for continuations. Scheme is, by nature, a very simple language. It seems almost paradoxical, then, that it has received as much attention as it has from the PL research community. The reason is simple. Its simplicity allows it to be used as a teaching tool (either by using a subset as a model language or by demoing code in Scheme), but it is its power that allows it to be useful to the researcher.

The power comes in a few forms. One is the mandated support for full numeric tower. Many languages include library support, but few include it built in. Another is the flexibility that hygienic macros allow. This allows the creation of new constructs in code that would normally have to be included in the compiler (switch statement anyone?). Yet another is in the use of first-class continuations.

This power is the difference between Scheme and VB. VB is simple, but weak, but Scheme is simple and powerful. So, one of the goals of Ocean is to ensure that both the simplicity and the power are maintained. I don’t want another Scheme-like scripting language. Nothing against them, but I want Scheme.

Anyway, now that I have explained why continuations are not a feature that I want to let go of (at least, not without a fight), the question becomes how to implement them. There is no built-in support for continuations in the ECMA 335. Mono has gone ahead and added them anyway. While this is terrific, I want Ocean to be fully compatible, to the maximum extent with all three of the platform implementations of which I am aware: Mono (by far, this one takes priority as it is more platform independent), Microsoft’s (the “canonical” one and, by far, the most important to the developer who wants to interact with commercial software), and GNU’s (the least important and, despite being almost the same age as Mono, the least mature for “real work”).

Because of this, I have been continually snooping around on the web and through academic papers. To date, I have found two possible methods and I am considering them both. The first, is good old fashioned CPS where some sort of custom class (that implements ICloneable) is used represent a continuation. Things could still get sticky with object references that are stored in classes that are bound in the continuation.

The second one I found is the more interesting. The paper is available here: http://www.ccs.neu.edu/scheme/pubs/stackhack4.html  There is a lot of heavy lifting to be done, but the essential idea is to transform the programs so that they “build” the continuations themselves, as they execute, where each procedure must be modified to “co-operatively” (in the words of the authors) help to construct the continuation.

It is tough. CPS, in this case, would be slower as any reference will have to be tracked down with two “reads” instead of just one. Both seem like they could, potentially, have issues with nested references. The latter looks as though it would have a problem interfacing code compiled with this technique (Ocean, if that is the design route taken vs. code compiled in a C# compiler) according to the paper itself. CPS would not have this problem, however, because a continuation would become first-class in more than one meaning of the word. How are things going to be done? I don’t know. A third possibility that I am still considering is waiting until the next version (0.2) to implement continuations. I don’t like it, but it would get a useable piece of software released. And that, my friends, is my non conclusion. Hey, there was a reason that this article was dubbed a rumination.

Out of Town

Once again, I am sorry for the air silence, but I’ve been out of town with relatively little web access (did any of you out there know that there is no WiFi in a barn?). More coming.