Archive for May, 2011

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

    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
    module com.obua.util.orderedset.unittest.functionality2
    module com.obua.util.orderedset.unittest.functionality3.sub1
    module com.obua.util.orderedset.unittest.functionality3.sub2

    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

    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.