Archive for July, 2010

Reference implementations

July 24, 2010

It is time to move the development of the reference implementation of Babel-17 v0.21 forward. At lot of work has already been done: a complete parser is available that spits out a validated syntax tree (including linear scope checks), and a continuation passing interpreter that runs deBruijn-index functional code. What is missing are a few details concerning the interpreter, a reference implementation for the Babel-17 library, connecting the interpreter with the library, and a translation from the syntaxtree to the functional code.

Still work enough to rethink the approach. Was it the right decision to choose deBruijn-indexed environments for a reference implementation? Was it necessary to use continuation-passing, which complicates the code for a feature that only a few serious users will notice positively because it allows to run programs only bound by memory, not by stack size, and allows for proper tail-recursion, and a lot of others might notice in a negative way, because it slows down execution?

The temptation is big to scrape the continuation passing deBruijn stuff, also to switch from Java to Scala, and proceed like it worked out so well for the Mini Babel-17 interpreter.  Write a small and simple interpreter in Scala, then bootstrap and write a proper and efficient compiler in Babel-17. Write most of the library also in Babel-17.

Is this just the usual “I am close to the finishing line, lets start fresh from the beginning” anxiety? Hard to tell. But it really seems to me that the second approach is the much better one. But why did I choose the first one in the first place?

Apart from the usual “lets build some cool tech and try out some cool techniques” reason the most important reason, as far as I remember, was to have a reference implementation that would be also a reference with respect to performance. Of course the hope is that later implementations are a magnitude faster, but they should differ in behavior from the original implementation only by a linear factor. I think there is a much better chance of later quality implementations to properly handle tail-recursion and memory management if the reference implementation does. And deBruijn environments exhibit the same behavior as environments in compiled code would.

 

Difficult decision ahead.

Advertisements

Javascript ain’t so bad

July 11, 2010

It is getting darker, the heat is almost bearable now. The phlegmatic programmer’s brain starts working again.

Extensive Javascript experience during the last month lead to the decision to add a new feature to Babel-17 v0.21 .  In Javascript, you can do the following:

var x = new Object()
x.a = 10
x.b = 20
x.c = 30

In Babel-17 v0.2 you could achieve the above only like this:

val x = object
  def a = 10
  def b = 20
  def c = 30
end

In Babel-17 v0.21, you can also write:

val x = nil
x.a = 10
x.b = 20
x.c = 30

which has exactly the same effect. How is this possible? Isn’t Babel-17 purely functional?

First, the keyword nil is just an abbreviation, we have

nil == object end

Second, the assignment x.a = t is short for:

x =
  begin
    val evaluated_t = t
    object+(x)
      def a = evaluated_t
    end
  end

The nice thing about the new feature is that it integrates seamlessly with the linear scope rules of Babel-17. For example, you can write

val x = nil
if some_condition then
  x.a = 10
else
  x.b = 20
end

Break is over

July 11, 2010

Things are heating up, especially here in Germany. There is much to do for the phlegmatic programmer these days, but first he needs to finish writing his Babel-17 paper.

It would be nice to have a running Babel-17 implementation to accompany the paper. To achieve this, there will soon be a new spec of Babel-17, Babel-17 v0.21. This spec will be stripped off the module system that was described in Babel-17 v0.2, because the phlegmatic programmer still needs more experience in purely functional structured programming before deciding on a module system. A complete implementation of Babel-17 v0.21 will help to gain this experience.

Babel-17 v0.21 will provide for the possibility to derive an object from other objects. Let’s say you have two objects aObj and bObj:

val aObj = object
  def a = 10
end

val bObj = object
  def b = 20
end

You could derive a third object from these two like this:

val cObj = object +(aObj, bObj)
  def c = 30
end

The above is equivalent to:

val cObj = object
  def a = 10
  def b = 20
  def c = 30
end

Object composition like illustrated above looks simple enough, but as always, the devil is in the details.
Consider we changed the definition of aObj to be:

val aObj = object
  def b = 100
end

What would cObj.b then evaluate to, 100 or 20 ? Babel-17 resolves this question by giving messages in bObj precedence over messages in aObj . Therefore the following would evaluate to true:

cObj.b == 20

Now, instead of the above, imagine we instead changed aObj to:

val aObj = object
  def a = this
  def b = 100
end

The value of cObj.b would still be 20. But what would be the value of cObj.a.b ?
If your guess is 100, then you are right. If you compose objects via +, then a “this” that appears in the message definition of a parent still refers to that parent after composition. If you want that “this” points to the composed object, you have to compose objects via *. Therefore, with

val cObj = object *(aObj, bObj)
  def c = 30
end

the expression cObj.a.b would actually evaluate to 20.