Saturday, November 20, 2010

Frege 3.0

It's been a long time since I last posted, but I have not been idle since then, though some private affairs detracted my attention from programming.

I've come to the conclusion that the original idea how frege programs should work is not viable. Until now, any Java function (or method, if you like that better) could simply be made available in Frege through a native definition. If that method had side effects, the Frege programmer would take care. Or wouldn't he? And there was the do ... for ...construct that was transformed to nested case statements whose patterns were all strict. And, of course, like in the german proverb "Ist der Ruf erst ruiniert, lebt sich's g√§nzlich ungeniert." (Once reputation is ruined, one can live completely unembarrassed.), why not have mutable references?

This works well in small programs. But the compiler is a mess. Imperative and functional parts are mixed like spaghetti in a bowl.  Need access to the symbol table somewhere in the middle? No problem, we have a global value for that. Of course, it's not just a Symtab, it's a Var Symtab, a mutable reference cell to a symtab, because sometimes we need to change it, you know. And so on.
One day I contemplated what would it take to compile two source files in parallel. Or to use the scanner in a Java-GUI for syntax highlighting. It's just impossible as it stands.

There was but one way out of this calamity: monads. I had ignored monads previously, because I felt I didn't understand them. But nowadays, I think I do understand them. And, in principle, it's really no big deal. The IO monad, for instance, is just a way to write imperative code and, at the same time, separate that code from pure code with the help of the type system. The type system tells you if your code may have side effects. That's great.

So I decided:
  1. Every native function must have an IO return type by default. (If one is really really sure, one can override this.)
  2. No mutable types in Frege anymore, except arrays, but of course the mutating functions are in the IO monad.
  3. The do-notation is for monadic code, like in Haskell.
  4. Get rid of the anachronistic and superfluous while, break and continue.
While I was at it, some more changes came to mind:
  1. Abandon record types. They had been somewhat clumsy in practice. It turned out, that most of them lived as single arguments of some constructor, adding one more indirection. Of course, they also were mutable meanwhile. Instead of this, constructor fields can be named now, and there are all sorts of fancy syntax to non.destructively update or change a value with fields. This turns out to be very nice.
  2. Change the way insatance method dispatch works. Currently, to use an instance function of some unknown type a, one must provide a value of type a, even when the function does not use this value. Then, at runtime, the correct function is looked up in a Map<String, Lambda> that is kown to the type. This used to work most of the time, but for monads, where return has type forall a m.Monad m => a -> m a, it means essentialy that one cannot write many functions (sequence for instance) that should work on any monad. Moreover, the concept will not work at all for multiple parameter classes (they will be in version 3.1, hopefully). Thus, we will switch to dictionary passing. Every class constraint will correspond to a dictionary that must be passed by the caller. Of course, the compiler will arrange this.
  3. Implement usable higher order polymorphism, this means, we need a forall keyword.