Fri Sep 26 11:30:58 CEST 2008

A type system for Coma

I've been thinking a bit about a type system for Coma, and I've run
into two problems where dynamic typing features are used in a way that
is not trivially eliminated:

  * Quasiquotation from Scheme expressions.
  * Code generation dispatch on operand values.

My conclusion is that adding the appropriate ``compile time value
passing'' is probably going to impose some restrictions that require
invasive restructuring.

A more interesting approach is probably to try to build the core of
the compiler on top of a language with static typing.  The
functionality of the compiler itself is available in high-level form
and straightforwardly transferred to Haskell or Ocaml code.

Ignoring the prefix -> postfix trick, this:

  Techniques for Embedding Postfix Languages in Haskell by Chris
  Okasaki. Haskell Workshop, October 2002, pages 105-113.

contains a straightforward type system, modeling stacks as nested

   add :: ((s, Int), Int) -> (s, Int)

Which is simply extended using type classes as:

   add :: Num n => ((s, n), n) -> (s, n)

It looks like this solves the main embedding problem.  The patterns
macro can then be replaced by Haskell's (or Ocaml's) pattern matching

Such an approach should be able to be used as a test suite for Staapl.
As long as a translation exists from (a subset of) Staapl's
transformer core to an embedding in a typed language, the system
(subset) is type safe.

This approach is rooted in the idea that program correctness can be
approached from two sides: dynamic type systems + tests (allow more,
but cannot eliminate all run-time type errors) or static type systems
(allow less, but eliminate all rtte).