Subtext 9

Subtext 10 is well underway, but version 9 deserves some mention. I didn’t record a demo video as in the past, because I have concluded that medium fails to communicate in sufficient detail. In the future I am going to try the forms discussed in my last post. Unfortunately Subtext 9 has fallen between the cracks, and all it gets is this lousy blog post.

Here is the abstract for a presentation I gave last fall, back in the halcyon days of jetting off to international conferences.

Between spreadsheets and programming

The simplicity and utility of spreadsheets puts programming to shame. We believe the power of spreadsheets is that they offer a computational substrate: an autonomous artifact combining code and persistent data that is presented through a simple spatial metaphor. Can we invent other computational substrates with more general programming capabilities than spreadsheets, while retaining some of their magical simplicity? Subtext is an experimental computational substrate structured as a tree. Its key difference from conventional programming systems is that code is not a syntax tree but a semantics tree — a tree representing an execution trace. Execution is not, as we usually imagine it, the effects of a machine running in a sealed box, but rather is woven into the fabric of the substrate itself. Program execution is in plain sight of the developer, even while they edit it: What You See Is What You Execute. Perhaps surprisingly, programs can also benefit from observing their own execution, as when, for example, a parsing function’s execution is itself the parse tree. But there is a difficult research problem at the heart of this enterprise: finding a language whose execution semantics can be materialized as data structures within that language, done so simply and naturally that it supplants the need for syntax. After much trial and error, Subtext has converged on a design in which the execution of a block of straight-line code is a record datatype, conditionals form a discriminated union, a loop is an array, and calls are nested executions. This research is still in an early stage, and is presented in the spirit of provoking discussion and the hope of receiving advice.

In the demo I built a parser for a simple language of arithmetic expressions. It was coded as a recursive descent parser, which was simple because of the SNOBOL-like semantics of failure. The highlight of the demo was how the parser generated an AST. Normally the AST would be a recursive discriminated union (AKA sum), constructed as a return value of the parser. It is very boilerplate code, constructing back together the ASTs of the bits that have just been parsed apart. And plumbing the AST back through the parser is a pain. An advantage of parsing DSLs is that they can do all of this automatically for you

The highlight of the demo was showing how Subtext gives you “ASTs for free”. The trick is that because of the unification of code and data structures, the execution trace of the parser IS the AST. The recursive execution of the parser is physically a tree, and the conditional clauses trying to parse each kind of term are physically a sum. As a result, the execution trace of the parser is itself the AST, and this is made available to the code is a form of reflection.

Subtext 9 was progress for me: I finally figured out how to unify conditionals and sums after many failed prior attempts. I find this a deeply satisfying insight. On the downside, it turned out that thinking about executions as a data type was more abstract than I liked, and visualizing them in the programming environment was tricky. Subtext 10 will have a simpler way to expose these semantics. And advance in some other important directions, but that is another story.

4 Replies to “Subtext 9”

  1. This is a really interesting research direction. Why do you choose a tree structure for your programs? The challenge I see is: some computations are not easily expressed as a tree. The most obvious example would be graph traversals (which underlie many kinds of computation). How do you represent graph-like data structures & computational structures cleanly? I tried to figure that out myself previously and it led me to relational/rule-based languages.

    1. Good questions. My general philosophy is that graphs are too general and complex, and we should avoid them wherever possible, which is almost all the time. I also believe that a language should come with built-in visualizations for all code and data structures. Trees are a lot easier to visualize than graphs. So I am voluntarily sacrificing the power of logic programming.

      1. That’s an interesting constraint; I’m looking forward to seeing what you can achieve within it. I’m aiming for the same kind of visualizability but with graphs & rules (logic). We’ll compare notes once we’ve published some demos!

Leave a Reply

Your email address will not be published. Required fields are marked *