eighty-twenty

Since I last posted about ThiNG, my ideas have shifted closer to those expressed in Jay & Kesner’s Pure Pattern Calculus, and I’ve built a few experimental spikes to gain some concrete experience with some of the language features and designs I’ve been thinking about - among other things, that traits and modules share a number of core characteristics, and that using monads to structure effects can be profitable even in a dynamically-typed environment.

Traits in Scheme (source code link)

A few weeks ago, I implemented a simple, small traits language based on the formal model of traits of Schärli, Nierstrasz et. al. The language has no fields (methods suffice!) and no classes (prototypes suffice!). The implementation, a macro which embeds traits into regular PLT Scheme, is a toy, intended only to explore the idea of traits; in particular, it doesn’t “flatten” composed traits.

PLT Scheme’s match operator was used to match method signatures to method invocations, which is a little unusual - pattern-matching in object-oriented languages is usually restricted to searches by method name (“selector” in Smalltalk terminology).

It turned out to be tiny. Traits are represented as functions from a message to a handling thunk or false (representing “does not understand this message”). Implementing the trait composition operations (sum, override, remove, and rename) is done in a combinator-like way. The core routine for finding a method to invoke for a given message is twenty-one lines long and dirt simple.

If this spike were to be taken further, perhaps integrated with an existing OO system for Scheme, a few things would need to be changed. Firstly, while using full pattern-matching for message dispatch leads to a very user-friendly OO programming system, very few existing object systems do anything more than method name searches, so the traits implementation would have to be changed to be more method name based; and secondly, it’s not clear how a traits system would interact with multimethod-capable generic functions. Brian Rice has done some thinking and experiments along these lines in the context of Slate.

Monads in Scheme (source code link)

A couple of years ago, I stumbled across Oleg Kiselyov’s “Monadic Programming in Scheme”. Right near the bottom of the page, he points out a problem with his Scheme implementation of monads, which is that you don’t get automatic resolution of overloading of the bind and return operators. In Haskell, the type system figures out which monad is intended, usually without requiring programmer-supplied type annotations, but in Scheme there’s no analogous constraint-propagation system, so you have to select which monad you’re binding or returning into explicitly.

As part of thinking about the design of ThiNG, I’ve more-or-less settled on a strict Haskell-style monad-based separation of effects from computations, and I’ve come up with a simple runtime constraint-propagation-based way of getting the same automatic bind- and return-overloading as Haskell gives you, using OO dynamic dispatch instead of a static type system. The monads are fully “type-checked” before they’re run, so no actions are taken until the whole monad is correctly assembled.

During the weekend, I implemented a first stab at the constraint-propagation idea in Scheme. Currently it only type-checks the monad immediately before running it, rather than type-checking incrementally based on the best available information as the monad is being assembled. I plan to update the implementation to do as much early constraint propagation as possible, rather than waiting until the last minute. This will allow Oleg’s final example, involving simultaneous use of an IO and a List monad, to be automatically disambiguated.

Haskell-based ThiNG r3/r4 evaluator (source code link)

I’ve been meaning to experiment with Haskell for a while, so last weekend I built a toy evaluator for my most recent ThiNG ideas using GHC. I used the Parsec parser-combinator library to build a parser. The parser and printer together took 86 lines of code; the evaluator itself, a mere 90 lines. The type system both helped and hindered: it caught a few stupid errors I made while initially constructing the program, but on the other hand also forced me into a slightly awkward design (almost identical AST, Value and Pattern types, with concomitant almost-duplication of code) that Scheme’s unityped nature would have allowed me to avoid.

The model of the language I built has allowed me to get a clear idea of how scoping should behave. It’s also clarified the semantics enough that I ought now to be able to build a partial-evaluator for it, to see how hard it’s going to be to get a usefully fast implementation.