Wednesday, May 23, 2007

Three thoughts about programming languages

What is the simplest programming language that can do interesting things with non-strict (lazy) evaluation? The key is that the thing that distinguishes lazy from strict is skipped infinite loops. Thus you only need one type -- say the Unit type (), which actually has two values: () and Bottom _|_, and therein lies heart of non-strict evaluation.

The ability to annotate a program openly and arbitrarily is very key -- more so than any language has been designed for. It can be done at the token level, as C pragmas. At the parse tree. And as a type annotation, limited only to points in the parse tree that are typeable. The lowest level (tokens) is extremely ugly, but with open and close tags, any arbitrary span can be annotated.

To limit expansions of a Data alternatives, one can annotate as a type annotation, putting the limitations (or permitted expansions) on a node anywhere a type can be specified.

No comments :