Babel-17 v0.3 is out !

June 30, 2011

Check it out now at ww.babel-17.com.

Advertisements

Automatic Type Conversions

June 29, 2011

Writing unit tests is a great thing. It makes you think even harder than usually about the semantics of your code.

In Babel-17 you have real interval arithmetic; for example, to describe the interval between 4 and 5, you could write [4.0; 5.0]. This notation, [a;b] assumes that a and b are reals, and forms the convex hull that contains both a and b.

Now. Should it be possible to also write [4; 5] for the above interval?

In my current preliminary spec for Babel-17 v0.3 the answer is NO. An integer is not a real; for example you cannot compare them, 2 == 2.0 evaluates to false. This point of view has a lot going for it; it seems pure.

(Un)fortunately, people don’t care so much about purity. I can already see the looks on faces when I try to explain that [4.0; 5.0] is a real interval, but [4; 5] is not even a legal expression.

There is an obvious solution to this dilemma: type conversions. These are already a part of Babel-17 v0.3: for example, 3 :> real converts the integer 3 to the real 3.0 .

Type conversions could be used such that whenever I need in a particular situation a value of a certain type T, I check if my value at hand can be converted into something of type T. If yes, I use the converted value instead, if not, then it’s a DomainError.

For this not to result in total chaos, a necessary condition for a type conversion to succeed should be that the conversion is reversible (at least in principle). Note that this is only a necessary condition, and you should really think twice before providing a type conversion. Often it makes more sense not to provide a type conversion, but just a conversion function which has to be invoked explicitly.

As an example, look at the conversion between integers and reals. It should be possible to convert integers that are not too large to a real; but if the integer is too large to be represented faithfully as a real number, the conversion should fail. Likewise, a real r for which r.round == r holds should be convertible to an integer. But the conversion should fail for those r with not(r.round == r).

This is a big issue, and adding automatic type conversions to Babel-17 changes the whole look and feel of the language. It will make it a lot easier for beginners to get friendly with the language; at the same time it will make it harder for a compiler (but not impossible, especially for a JIT) to generate fast code.

Automatic type conversions will be introduced in the upcoming Babel-17 v0.3, and further developed in Babel-17 v0.3.1.

Feature Complete

June 28, 2011

Babel-17 v0.3 is feature complete! Everything has been implemented, and there is also a new version of the Babel-17 plugin for Netbeans 7.0. The two biggest changes in the plugin are:

  • there are Babel-17 projects now
  • there is support for running unit tests

Tuesday is dedicated to going through the specification and writing unit tests that check the spec. Hopefully only minor fixes will be necessary; if so, then Tuesday night Babel-17 v0.3 will be released!

Implementing This

June 20, 2011

I am currently teaching the interpreter how to handle evaluation of this. While this is an intuitive concept, its correct implementation results in quite some work. The following code snippet,

val r = 
  object
    def outer = this
    def name = "r"
    def u =
      object
        def test = (inner, outer)
        def inner = this
        def name = "u"
      end
  end
val (i, o) = r.u.test
(i.name, o.name)

should evaluate to ("u", "r"). To achieve this, the interpreter converts the above program into something like:

val r = 
  object
    def outer this_a = this_a
    def name = "r"
    def u this_a =
      object
        def test this_b = (inner this_b, outer this_a)
        def inner this_b = this_b
        def name = "u"
      end
  end
val (i, o) = 
  begin
    val u = r.u r
    u.test u
  end
(i.name, o.name)

Off trying to implement this in a not too messy way …

No Wildcard Import

June 11, 2011

I have implemented wildcard import in Babel-17, i.e. you can do something like

import com.coollib._

or even more complicated imports like

import com.coollib.{coolfun => f, -notneeded}

which will import everything from com.coollib except notneeded. The value com.coollib.coolfun is accessible by the local name f.

But now I decided to get rid of wildcard imports again. There are two major points why wildcard imports are not such a good idea:

  1. Wildcard imports can lead to name collisions that you are not aware of. Right now, it is an error if an imported name collides with a local def or val, but it is no error to collide with names defined not in the local, but an outer scope. This rule makes sense for all imports except wildcard imports, where it is dangerous, especially since Babel-17 is dynamically typed.
  2. Wildcard imports are the only thing standing in the way of a complete separate compilation of Babel-17 files. Right now, all modules are scanned in a first phase. In the second phase, this module information is used for wildcard resolution.

The second point is annoying, but obviously I have already worked around it. But the first point really is a deal breaker. Wildcard imports gotta go.

Lenses Suck Less

May 27, 2011

The day started well when I found an email with a link to the following video in my inbox:
Making Apps That Don’t Suck.

After watching and enjoying that video, I stumbled (via the scala-debate mailing list) onto the following talk:
Lenses: A Functional Imperative. This was when this day really started to rock.

I mean, how \emph{cool} are Lenses? They are such an obvious concept; maybe so obvious that people who used lenses before didn’t bother to give them an explicit name. But as it is, often sometimes becomes visible and tangible only once it has a name.

Lenses seem to be a must-have for Babel-17. I always wondered how to generalize the following shortcut update notation which is currently available in Babel-17:

val x = { a = 3, b = 2 }
x.b = 7

Here x.b = 7 is short for

x = { a = x.a, b = 7 }

I don’t think that lenses will make it into the Babel-17 v0.3 release, but expect them in Babel-17 v0.3.1 .

Reals and Order

May 19, 2011

What else do I need to put into Babel-17 v0.3 to be able to use it in real-world projects? As a prerequisite for things like graphics, floating point arithmetic is highest on my wish list.

So I want to add a new type real. But the thing is, I never liked the way floating point was usually treated in programming languages. When working on my diploma thesis and especially when working on my PhD, what I needed wasn’t mere floating point arithmetic, but interval floating point arithmetic.

Babel-17 will be radical in its treatment of floating point arithmetic: there will be only interval arithmetic. Interval arithmetic is just so obviously superior to ordinary floating point arithmetic that this decision is a no-brainer. The only theoretical reason against interval arithmetic I can think of is the dependency problem: when you evaluate an expression in which the same variable occurs several times, interval arithmetic will often overestimate the error. For example, the expression

x - x

will yield something non-zero if x is an interval of width greater than zero. Therefore,

1.0/3.0 - 1.0/3.0

will never be zero when doing classical interval floating point arithmetic.

But in my opinion this is not a problem at all. First, in order to reduce the error introduced by dependencies, just make your interval bounds tighter. Second, in case this is not good enough for your application and you really need x - x to evaluate to zero, you probably shouldn’t do floating point arithmetic at all, but rather turn to computer algebra.

A practical problem with interval arithmetic is that it is not very well supported on many platforms. For example in Java, it is downright impossible to implement a performant implementation of interval arithmetic that calculates bounds as tight as the underlying hardware would support it. But again, this just means that your intervals will be a little wider than they could be. Also, Babel-17 implementations that compile directly to machine code can circumvent most of these problems.

Introducing interval arithmetic into Babel-17 has ripple effects. The main reason for this is the ordering imposed on intervals. The most appropriate order seems to be defined via

[a; b] <= [c; d] iff (b < c or (a = c and b = d))

There are other orders of interest like inclusion of intervals, but the above seems to be the right choice for the canonical order of intervals.

Unfortunately, there is no way that such an interval type together with this order could currently be defined in Babel-17. Of course I could implement special magic for reals, and the importance of this particular type would justify such a special treatment; but it still feels odd and I just don’t like such a resolution of the problem.

Another thing to consider is the interplay between integers and reals. Once you start using special magic, you would definitely expect to allow the comparison of integers and reals. But this leads to results a naive user might be unprepared for, like

2 == 4.0 / 2.0

not being true (depending on how the particular interval arithmetic implementation works). Let’s face it: It is just not a good idea to compare integers and reals. If you want to do this, do it by explicitly converting between integers and reals.

Extending the above discussion, one might also ask: Is it a good idea to canonically compare lists with vectors? And, is it a good idea to canonically compare values of different types at all? I think the answer is no. Those parts of Babel-17 relating to order, I definitely need to rework them.

Unit Testing

May 8, 2011

The changes I currently make to Babel-17 for the jump from v0.21 to v0.3 reach deeply into the current code base. This makes me think about how to verify that the changes are consistent with my spec of Babel-17. Obviously, an important corner stone for interpreter / compiler correctness is a test suite. Most of the tests in this test suite can just be treated like unit tests for ordinary Babel-17 programs. This leads naturally to the question, how should unit testing work in Babel-17 ?

I am a strong advocate of providing programming language support for unit testing. Especially for Babel-17 this seems obvious: Babel-17 is dynamically typed, and although you can now (in v0.3) have modules, data encapsulation and abstract datatypes, there is only minimal static type checking in Babel-17 that merely ensures that the types you talk about really exist. You will still need unit testing to see that your types behave like you expect them to. Writing unit tests will be a standard task for every serious programmer who uses Babel-17, and therefore Babel-17 should provide language support for it. If you are saying, hey, this argument is bullshit, because for example version control is also a routine task, but best be left to external tools, then you might be right; but maybe you are very wrong 🙂

An important feature of testing is that the testing code does not affect the original production code. Many people interpret this as an argument against language support for unit testing, but actually only language support can guarantee the separation of production and testing code.

So, Babel-17 v0.3 will provide the following language level support for unittesting:

  • a new keyword unittest
  • you can define modules that contain unittest as part of their path, like in
    
    module com.obua.util.orderedset.unittest
    ...
    end

    This module would typically test functionality of the module com.obua.util.orderedset. If you’d like to distinguish further the tests of this module, you can name your modules like this:

    
    module com.obua.util.orderedset.unittest.functionality1
    ...
    end
    module com.obua.util.orderedset.unittest.functionality2
    ...
    end
    module com.obua.util.orderedset.unittest.functionality3.sub1
    ...
    end
    module com.obua.util.orderedset.unittest.functionality3.sub2
    ...
    end

    and so on. Any module that has unittest in its path is called a unit test module. Note that a module path cannot repeat parts of itself; in particular, only a single component of the path can be unittest

  • you can use the unittest keyword as part of a module name also for the
    import statement, but only if it is issued from a unit test module
  • the last statement of a (non-unittest) module can be a unittest statement, like in
    
    module com.obua.util.orderedset
    ...
    unittest
    ...
    end
    

    This has the same effect of defining a module com.obua.util.orderedset.unittest, but with the difference that it shares the namespace of its surrounding module. In particular it can see the private definitions and type definitions (and the inner values of those types) of its surrounding module.

  • The pragma #assert is only executed and checked when running unittests, never in production code.
  • The new pragma #catch takes a constructor name (like InvalidArgument) and an expression. It signals an error if the evaluation of the expression does not yield an exception with that name. It also is only executed when running unittests.

Taken together this allows for the flexible creation of unit tests, while at the same time completely shielding production code from testing code.

Commas

April 25, 2011

Trying to introduce typedef into the new Babel-17 grammar, I noticed that there was a problem with the combination of blocks and commas in the grammar. I then realized that I had hit this problem earlier but had been able to circumvent it: the memoize construct is currently used like this:

memoize a b c

and NOT like this:

memoize a, b, c

With typedef such a hack was not possible anymore, so I had to track down the cause of this problem. After hours of examining the grammar with ANTLRWorks, which is by the way one of the greatest software tools I have worked with (the up-side: now I finally completely understand the alternative display of ANTLRWorks), the problem turned out to be the block part of lambda expressions:

(x => memoize a, b)

could be understood as

((x => memoize a), b)

but also as

(x => memoize a; memoize b)

After pondering the different ways of resolving this dilemma for a while, I decided that a clean solution is to distinguish between lambda expressions that are surrounded by round brackets, and those that are not. Basically, for those that are protected by surrounding brackets, the rule is

lambda_expr_1 := pattern => block

for those that are not the rule is

lambda_expr_2 := pattern => expr

This means that the expression

(x => memoize a, b)

is now interpreted as

(x => memoize a; memoize b)

As a consequence, both memoize and private will use commas instead of just spaces as separators of their multiple arguments.

Deconstructors

April 24, 2011

Currently the pattern

f ? p

has two different meanings, depending on whether f is a function or not. If f is not a function, then the message deconstruct_ is sent to the value to be matched, the result is applied to f, and then result of this application is matched against p.

This, so I thought, should enable pattern matching against cexprs even for values that are no cexprs.

In the light of how types are going to work in Babel-17, this does not seem to be so useful anymore. Instead of the pattern

Plus ? p

why not write directly the pattern

Plus p

All that is needed for this to work is to modify the semantics of above pattern such that code like

match v
  case Plus p => ...
  ...
end 

leads to the result of v.deconstruct_ Plus being matched against p. Original cexprs have an obvious default implementation of deconstruct_, and other values can optionally implement it.

This is a good place to also announce another change: the pattern

match v
  case Plus => ...
  ...
end

will not any longer be synonym with

match v
  case (Plus nil) => ...
  ...
end

but instead with

match v
  case Plus _ => ...
  ...
end

The reason for this is that especially exception handling becomes more robust and streamlined, for example the code

match
  exception MyError "my bad"
case (exception MyError) => "hello"
end

will now result in the value "hello".