This is the third post of my notes from Emerging Languages Camp last year. If you haven’t seen it already, you might want to read the Introduction to this series.
Noether: Symmetry in Programming Language Design
I found this presentation to be at once fascinating and frustrating. It was the single best talk at ELC in terms of changing how I think about programming languages. To whatever degree I went to ELC in order to learn and change my thinking about programming, this talk really delivered. At the same time, the presentation itself was kind of a mess. There were far too many sides (69, and dense with text, equations, and citations), with far too much information for the allotted time (less than an hour!). It felt like the author had planned on a full day presentation and was surprised when the hour was up. However, I will take substance over style any day. The ideas presented here were so big that a full-day seminar would probably just scratch the surface.
Daira asked: How should we program gigantic computers? Have languages and tools improved proportional to hardware? No. The NSA (calling back to the previous presentation) exploits flaws because the tools are not good enough. The "software crisis" is still here. However, some techniques, like pure functional programming seem to help. How?
By imposing a symmetry. If you change a program in the same way, you should get a similar program.
Here’s some examples of symmetries in programming:
- Confluence: in a pure language, evaluating in different orders produces the same result.
- Alpha renaming.
- Macro expansion (or abstraction)
- Comments and dead code can be added and removed without changing the meaning of the program.
However, there are other programming language features which break symmetries we would like to have. Some are essential features, like failure handling and concurrency. Others are probably less essential: implicit conversion, unhygienic macros, global state, global floating-point modes, etc. A design wart in a feature can stop it from having desirable symmetries.
How do we keep desirable symmetry breaking while making undesirable symmetry breaking as difficult as possible? A possible solution to this question is a "stratified language." To some degree, languages like Erlang, Oz, and Haskell already do this, but Noether takes this idea much, much further. The name of the language is, obviously, a nod to Noether’s theorem.
There were not any substantive syntax examples in the presentation, as far as I recall. The presentation almost exclusively discussed semantics. The semantics themselves seem to be very much a work in progress. Daira’s approach is to create a hierarchy of "sublanguages" for each desirable level of symmetry-breaking. As you’ll see, this results in a somewhat dizzying taxonomy of sublanguages. However, ze says that as the language design progresses, many of these will be combined when it seems appropriate. The goal is to retain properties of inner languages when you compose them in a coordinating language.
The best "big picture" slide in the deck lists eight different sublanguages, but other sides imply there are many more. These languages add things like, variously, failure handling (but not failure creation; that’s a different sublanguage!), task-local mutable state, or Turing completeness.
Daira also listed some disadvantages of stratified languages. Rarely-used features will impose significant costs in implementation and specification complexity. The language is more complicated and will take longer to learn. Refactoring could be more difficult if it imposes a smaller sublanguage constraint on existing code.
Ze also said something which has been in the back of my mind for a few years: "Just apply existing research; termination provers got really good and nobody noticed!" Indeed, SAT solvers in general have gotten really good. A few people have noticed: They’re finding use in package management and static analysis applications. But it’s a very general technique and those applications are just the tip of the iceberg.
In the next post in this series, I’ll discuss the presentations on the Nimrod and Dao programming languages.