Sunday, June 7, 2015

Why Programming Languages Use Only One 'View,' and How to Fix That

(note 1: This is the first of a two part series; part two is here: How to Make View-Independent Program Models)

(note 2: In the interest of a little more context/concreteness: here's a video of an editor I made that works by rendering a tree-based program model as described in the article (this just uses an AST, though, not a 'pure' model): Tiled Text)

---------------

It's pretty well acknowledged that the reason source languages exist is that they are better interfaces for program creation than, say, typing and reading machine code. And yet, it's kind of weird to call them 'user interfaces'—probably because they are each comprised partly of the concrete interface to some external text editor and partly of an abstract specification, this combination being a more nebulous construct than we're accustomed to labeling 'user interface.' At the same time, however, even if its form differs from our typical user interfaces, its function matches well: programmers use a text editor and programming language features as their interface to program creation.

User interfaces are something we've learned a lot about since the original architecture for program authoring software was laid down (which determines that programs will arrive in the form of character sequences and then be parsed into something more useful). Among these things learned is a useful way of analysing systems into 'models' and representations of those models, called 'views'. Furthermore, probably the strongest reason for an architecture to adopt a model/view split is that the software will require multiple representations of one model. This is very much the case for program authoring tools: for instance, source code and machine code could be generated as two representations from a pure program model (which I describe how to build here)—and we could far more easily allow multiple source views.

There are a few points I've come to believe are true which have led to a new perspective on program creation systems:

(Note: I'm going to use 'machine code' as catchall for any kind of target/output language in any kind of interpreter/compiler.)

(1) The only reason we have source languages (as opposed to machine code) is because they are better interfaces for human programmers.

(2) Program source and machine code are two representations of one abstract thing. This common 'abstract thing' is much like the models in MVC systems; accordingly, I call it a 'program model' here.

(3) ASTs are an approximation to this 'program model,' but they are biased towards one potential representation: source code.

(4) It's possible to construct generic program models, which are better at capturing the essential properties of programming languages (including, e.g., 'type' information), and which are not tied to any particular representation.

The more I think about 'program models,' the more our treatment of program source code seems bizarre. Why aren't the models of computer programs prior to their source code representations? Shouldn't program models be the basis for generating program views? Shouldn't we store models on disk and build views when using our programming tools? Shouldn't we pass models around the internet instead of views?

This more symmetric relation of the various views of a language to a single generic model, as in the image, seems more natural:


Among the many benefits we could expect to arise from structuring things this way:

  • Swappable views for programming languages (think, e.g., personally configurable 'syntactic sugar,' but on a much grander scale—definitely edging in on the realm of meat and potatoes. A primitive example: you check a box in your editor,  and now your Python-like language is rendered with curly braces instead of just tabs. A little more complex: instead of 'new Color(20, 30, 50);'—your editor renders a color picker).
  • Experimenting with UI concepts for program construction would be far less costly.
  • No need for parsing at all.
  • Dead simple for tools to give feedback on what's possible to do within your language, significantly reducing the learning curve of using a new language. (More on this in Part 2.)
  • More diverse, interesting textual representations are possible since you don't have to parse.
  • Program models could be much simpler than source code (aside from LISP: my particular formulation ends up looking like this:  (2 (3 0 0 0 1 (0 3) 4))), hence they are easier to manipulate via algorithms.

Program Views on Generic Models

The editor 'Moonchild' has some examples of the sorts of 'node views' I'm imagining in the section below. 

So, assuming we now have a generic program model (I describe how to actually build these in part two: How to Make View-Independent Program Models), what would it look like to build views based on such a model? There is a powerful, natural approach to this, which is for programming tools to mimic web browsers, whose displays are built up using algorithms on DOM trees. Our 'program model' is very similar to a DOM tree: first, it's a tree, and second, it contains the abstract structure and content of the thing to render, but doesn't say how to render it. The modern web is ample evidence that this kind of structure works well as the basis for rendering complex, diverse, text-centric layouts, with varied interaction styles.

It's probably not hard to see that we could use this structure to build visual representations of programs that exactly mirror the look of present day, pure text source code—so if 100% text is preferred, that's absolutely possible. But imagine, now that it's built on a structure that matches the web, how we could evolve pieces of our document into rich, interactive elements, when desired.


What I mean to propose here isn't that we use one view or another, though; rather, only that we maintain a more direct correspondence between elements in the visual display of our programs, and their backing models (as in the image). This is in strong contrast to the unfortunately indirect relationship found in most modern programming systems, which is necessarily mediated by parsing. For example, with this more direct relationship, just by placing your cursor somewhere in the document your programming tool knows which node in your program's model you are considering interacting with. The node might have an "on click" script attached—it might expand its visual representation, pushing the views for other nodes to the side, or shrinking nodes whose types are irrelevant to what you're interacting with.

Again though: I don't know what the better interface is, just that this opens up our freedom to explore. In our current systems, the only time we experiment with alternate views is when designing whole new programming languages; using generic program models, we can keep every other aspect of the language and just change how it's rendered for programmers.

The Difference Between ASTs and 'Program Models'

While ASTs are a sort of approximation to program models, It's probably more accurate to call them models of program source, than of programs themselves. Well, what if we model 'programs themselves' instead of 'program source'? After all, modeling program source does imply that unhealthy dependence on one view; can't we consider 'language constructs' in the abstract, separate from a visual representation? We can!

It's very common to use formal grammars to generate software for building ASTs out of program source. These grammars define the set of abstractions (i.e. 'language constructs') available to the programmers of a given language—but they do so in terms of a textual representation of these abstractions. However, if our grammars were to not bottom out in a 'lexical section,' i.e. without describing the decomposition of abstractions into character sequences—we could more directly address the 'essence' of our programming language, handling representation later.

More important than the actual act of omitting the lexical section, though, is the different way of thinking about grammars when you aren't tied to characters as the 'atoms' of your language. What would your primitive types be if not characters? Well, why not the abstract primitive types of your language?

Here's an example of the difference: let's consider how a simple function call is represented in an AST first, then in a generic program model. Here's our function call:

doCoolThing(intVar, boolVar);


And this is what it might look like as represented by an AST:

Now, as represented by a generic program model:
Notice how in the AST the function name and both arguments all appear to be the same kind of thing? That's because in the model of the source code, they are all the same thing: they're all character sequences following the rules for identifiers. In the program model, the node types relate to meaningful types within the programming language—it's not talking about character sequences at all. This makes it a much more useful model for programming systems to work with: it's a structure that relates more closely to meaning within a programming language.

The long numbers you see in the program model diagram are IDs used to associate certain nodes with arbitrary, external representations. If you'd like, there's no reason this representation couldn't just be a sequence of characters—but now it could be interchanged with any number of other things, without changing the rest of the language.

The next half of this essay: How to Make View-Independent Program Models


You might also check out: A Short Dialogue on How Crazy Human Programmers Are

Some more examples of editors that operate on models instead of text, but aren't visual languages: LamduUnisonJetBrains MPSeco

6 comments:

  1. This is amazing!

    I really hope we can use this in the near furture...

    ReplyDelete
  2. Replies
    1. Right—there is a resemblance. So, first I'll say that I'm only talking about an architecture, not a language, so they are fundamentally different for that reason. But, it's true that a very natural way of encoding 'program models' is in something that looks very much like Lisp (see part two of this essay). You could consider that to be a language if you'd like, though doing so would ultimately be misleading.

      The reason why the subject of these articles is important, however, is that you can make languages structured this way look however you want without changing their fundamental properties. If you introduced richer syntax to Lisp, you'd lose all of its elegance and nobody would be interested anymore: its macro system, for one, would no longer be magical.

      Delete
  3. This comment has been removed by a blog administrator.

    ReplyDelete