Time for a progress report, now that I have some progress to report. I didn’t get much research done last semester because I was teaching a new class: 6.170 Software Studio. It was a noble experiment with mixed results, but that is another story. Back in March I presented the latest version of Subtext at the IFIP Working Group 2.16 on Programming Language Design. I realized then that Subtext should be statically typed. Ever since I have been falling down the rabbit hole of types.
Perhaps the most compelling need for static types are in the UI and the DB, which ironically are considered extraneous by much of the PL community. It is commonplace to map a standard model object like a Customer into a corresponding screen form. Screen fields are in a sense statically typed: a field can accept a string, or maybe a number, or perhaps select from an enumeration, but you certainly can’t inject an arbitrary object pointer. Traditionally dynamic languages use templates to hard-code this type information into a UI language like HTML, spreading and coupling design information across different languages. A framework like Rails maintains its own internal type information from which it can generate screen forms and run an object-relational mapping. I conjecture that any sufficiently advanced dynamic language framework has its own ad hoc, informally specified, bug-ridden, slow implementation of a type system [with apologies to Greenspun]. DB schemas are really a form of static typing too, enforcing a rigid homogeneity needed for queries and indexing. Since UIs and DBs are naturally statically typed, it is natural that Subtext be also.
I have spent the last nine months trying to work out an acceptable type system. People give me funny looks when I say that. After all, type theory is well understood, and most modern languages have converged on largely similar types. What’s the problem? The problem is that these systems are far too complex. What percentage of Java programmers fully understand its type system? I’m guessing 1%. I shudder to think what it is for Scala. I am not blaming type theorists – they are just the messenger – telling us that our language semantics are too complex to make sense of at compile time. I have considered and discarded maybe a dozen type systems because they were all just too damn complicated. I need something dead simple that will be clear to a novice programmer.
It was only at the point of desperation that I could accept the solution: reject first-class functions. Specifically, function calls must statically resolve to a literal function. Subclasses are limited to static hierarchies (no inner classes). There is no truly dynamic dispatch: all function and methods calls can in principle be inlined. This restriction bans dynamically created closures, often used in callbacks. But a major goal of Subtext is to avoid the need for callbacks in the first place. Fancy closure tricks are disallowed, but I want to discourage tricky programming anyway. Fortunately key functional idioms like mapping, folding, and comprehensions can still be provided by generics (aka templates).
This design decision triggers a gratifying cascade of simplifications to the semantics and type system of the language. In fact the type system sublimes into what might better be called “static prototypes”. This feel right. It is also highly suggestive. My recent work has been about simplifying side-effects by restricting the ability to read and write through pointer variables. Now to simplify static types I am also restricting the ability to jump through pointers. The emerging moral is that pointers are the root of all semantic evil.
Eliminating first-class functions is not a fashionable idea to say the least. Functional programming is all the rage in modern languages, as well as modern programming culture, not to mention its long dominance of PL theory. I too was a true believer. But I must follow where simplicity leads. What a long strange trip it’s been.