Laurence Tratt's Blog

 

Debugging Layers

July 28 2015

A couple of weeks back, I joked to someone that one day I would write a condensed retrospective of all my failed research ideas but that, until I did, people could read my research papers for the long version. It seemed a clever thing to say at the time, and I dutifully slapped myself on the back. I then found myself discussing Converge's approach to error tracking and reporting with someone to whom I thought it might be vaguely relevant, later pointing my poor victim to a chunk of a paper and – when I later remembered its existence – a blog article. The core idea is simple: generated code can be related to one or more source locations. This means that when a user layers one piece of code atop another, each of those layers shows up in stack traces, making debugging significantly easier. When, with a fresh mind, I read over the paper and the blog article, I realised that it's hard to extract this, and a few related, albeit minor, ideas out of those bits and pieces: they assume the reader knows more about Converge than is realistic.

Normally I wouldn't necessarily mind too much if old ideas are a little hard to grasp, but I've come to view Converge's error tracking and reporting as probably the only useful piece of language design I managed in the five or so years I spent on Converge [1]. I therefore found myself deciding that I needed to write a brief retrospective on Converge and this feature so that some other poor soul doesn't spend five years of their life on a feature than can be explained in ten minutes. The aim of this article is to give enough background to understand the core idea of debugging layered programs, but what is enough depends on your point of view. I've therefore tried to aim this article at two audiences: one who just wants to quickly get a sense of the important idea (if that's you, skim the background material, but don't worry too much about the details); and another who wants to get a deeper sense of how the important idea really works (if that's you, it's worth spending some time getting a reasonable appreciation of the background). I'm sure I won't fully succeed in satisfying either audience, but hopefully both might find a little something of interest herein.

A quick introduction to Converge

For our purposes, Converge can be thought of as Python with a mildly modified syntax and somewhat different standard library: it's dynamically typed, has an indentation syntax, and a mostly similar world view. One immediately obvious difference is that programs must have a main function and that printing isn't a builtin statement or function. Here's a minimal hello world program:

import Sys

func main():
  Sys::println("Hello world!")
On top of this run-of-the-mill base [2], Converge adds a macro system [3] adopted from Template Haskell. In essence, one can generate program fragments at compile-time and splice them into the program such that they can be used as if the programmer had typed them into the original source file. Here's a contrived example:
import CEI, Sys, Time

func secs_from_epoch():
  Sys::println("Getting time")
  return CEI::iint(Time::current().sec)

func main():
  Sys::println($<secs_from_epoch()>)
Saving that code into a file t1.cv and running it a couple of times at the command-line gives the following:
% converge -v /home/ltratt/t1.cv
===> Compiling /home/ltratt/t1.cv...
Getting time
===> Finished compiling /home/ltratt/t1.cv.
===> Linking.
1436729518
% converge -v /home/ltratt/t1.cv
1436729518
I'm going to assume that Converge's basic syntax is fairly obvious, but there are a few other things that need to be explained before this example makes sense. First, Converge has distinct compile, link, and run-time phases. Running Converge with -v causes information lines to be printed on stderr (lines 2, 4, and 5) stating when compilation and linking have started and finished. Since there wasn't a cached compiled version of the program in the above example when it was first run, Converge compiled and linked the program (saving that output to a cache file) before running it. On the second run, Converge read the cached version in and ran it directly, rather than recompiling the source code.

Most of the program's source code is obvious except the $<e> construct which we'll call an explicit macro invocation. The expression e is evaluated at compile-time and is allowed to refer to any function or top-level variable defined above the macro invocation; it is expected to generate a program fragment as an Abstract Syntax Tree (AST); that program fragment then overwrites the macro invocation so that when the program is later run, the generated program fragment is run. The secs_from_epoch function generates a trivial program fragment, with an AST representation of an integer (the CEI::iint function takes an actual integer and returns an AST integer class). In essence, after the explicit macro invocation was evaluated, the program that was compiled and linked looked as follows:

import CEI, Sys, Time

func secs_from_epoch():
  Sys::println("Getting time")
  return CEI::iint(Time::current().sec)

func main():
  Sys::println(1436729518)
As this hopefully shows, even though the program was run twice, the macro invocation was only executed when the program was compiled in the first run. No matter how many subsequent times we run the program, it will print out the time that program was first compiled (1436729518). Only if the program is recompiled (e.g. because the cached compiled version is deleted or the source code has changed) will the secs_from_epoch function be called again.

DSL compilers

In my opinion, Converge's raw macro facility isn't hugely useful for day-to-day programming. Rather, it is intended to be used as a basis for what I should have called DSL compilers: in essence, one can embed arbitrary strings into a source and compile them into Converge ASTs at compile-time. In so doing, we've added a new layer on top of the main language. Although I'm not going to dwell on this, one can layer as deeply as one wants, and it's not unusual for DSLs to be implemented in terms of other DSLs.

As a simple example of embedding a DSL, I'm going to use a stack-based machine. At compile-time the DSL will be compiled into a Converge function which can then be called as normal, returning the top-most value on the stack. Here's a use of the DSL:

f := $<<sb>>:
  PUSH 2
  PUSH 3
  ADD

func main():
  Sys::println(f())
We'll see the definition of sb shortly, but you will be unsurprised to be told that the above program prints out 5 when run. The $<<sb>> syntax (line 1) means all the code on the next level of indentation (lines 2–4) should be left unparsed; the raw string representing that code should be passed to the function sb which will be called at compile-time. In essence, a simple variant of normal macros allows us to embed arbitrary syntaxes into a file, making use of Converge's indentation-based syntax to know when a DSL starts and finishes, and thus where normal parsing of Converge code can resume. If we take the full file and run it with converge -v, we see the following output:
===> Compiling /home/ltratt/t2.cv...
func ():
    stack := []
    stack.append(2)
    stack.append(3)
    $$3$$rhs$$ := stack.pop()
    $$4$$lhs$$ := stack.pop()
    stack.append($$4$$lhs$$ + $$3$$rhs$$)
    return stack[0 - 1]
===> Finished compiling /home/ltratt/t2.cv.
===> Linking.
5
As this might suggest, the sb function has compiled our DSL into an anonymous function (it also printed it out so that we can get some idea of what it did, but that isn't something it's required to do). The compilation is very simple-minded: an empty stack is created (line 3); the integers 2 and 3 are pushed onto the stack (lines 4 and 5); then they are popped off (lines 6 and 7) so that they can be added together and the result pushed onto the stack (line 8); and finally the top-most value on the stack is returned (line 9). Variables beginning with $$ might look scary, but for our purposes they're simply normal variables with unique names generated by the Converge compiler.

Let's start with a simple implementation of sb:

import Builtins, CEI, Sys

func sb(dsl_block, src_infos):
  instrs := [] // A sequence of Converge instructions
  // Iterate over each line in the DSL block
  for line := dsl_block.split("\n").iter():
    sp := line.stripped().split(" ") // Split the line into a list
    if sp[0] == "PUSH":
      ast_int := CEI::iint(Builtins::Int.new(sp[1]))
      instrs.append([| &stack.append(${ast_int}) |])
    elif sp[0] == "ADD":
      instrs.extend([|
        rhs := &stack.pop()
        lhs := &stack.pop()
        &stack.append(lhs + rhs)
      |])
  ast := [|
    func ():
      &stack := []
      $c{instrs}
      return &stack[-1]
  |]
  Sys::println(CEI::pp_itree(ast))
  return ast
This function takes in a string (the dsl_block argument in line 3) and gradually compiles it into a sequence of Converge expressions which are then inserted inside an anonymous function (line 17–22) which, to make our lives a bit easier, is printed out (line 23) and then returned (line 24).

Before going any further, I need to explain three bits of related syntax. First, are quasi-quotes [| ... |] which are a syntactic convenience, but an important one. Surrounding an expression with quasi-quotes makes that expression evaluate to its AST equivalent. Instead of laboriously writing out CEI::ibinary(0, CEI::iint(2), CEI::iint(3)) we can instead write [| 2 + 3 |] which compiles to exactly the same code. Second are insertions ${...} [4], which can be used inside quasi-quotes to insert one AST into another (e.g. lines 10 and 20). [| 2 + ${CEI::iint(3)} |] is thus equivalent to [| 2 + 3 |]. Most insertions splice in a single tree, but an insertion used alone on a line can also splice in a list of ASTs (e.g. line 20). Third, Converge has a hygienic name system, which renames all variables inside quasi-quotes which don't begin with a & to fresh (i.e. unique) names. In the case of sb, we want to stitch together multiple tree fragments and have the stack variable refer to the same thing across all of them. In general, one doesn't want to use & too frequently, though for the purposes of this article, it doesn't matter too much.

Better reporting of syntax errors

At this point, we've implemented a small DSL which is translated at compile-time into Converge code. However, our implementation of the DSL compiler is rather too simplistic: any mistake by a user of the stack machine DSL will lead to inscrutable errors. Consider a trivial syntax error, where the user forgets to add a value to a PUSH instruction:
f := $<<sb>>:
  PUSH 2
  PUSH
  ADD
This innocuous error leads to a long stack-trace [5] in the DSL compiler whose last few entries are:
   ...
   17: File "/home/ltratt/t3.cv", line 27, column 5, length 31
        f := $<<sb>>:...
   18: File "/home/ltratt/t3.cv", line 9, column 45, length 5
        ast_int := CEI::iint(Builtins::Int.new(sp[1]))
   19: (internal), in Builtins::List.get
 Bounds_Exception: 1 exceeds upper bound 1.
Let us assume we have a user brave enough to follow that stack-trace into code: they will probably deduce that the error relates to the PUSH instruction, but, if their input has multiple such instructions, which might be the culprit? Fortunately, Converge has two tools to help us.

The first tool is something I deliberately skipped over earlier. sb is passed two arguments, with the second conventionally called src_infos. If we print that argument out we see that it is a list of lists:

 [["overdrive.tratt.net:/home/ltratt/t3.cv", 725, 21]]
I'll go into more details of this later, but the basic idea is simple. The src_infos argument tells us where the DSL block started and its extent—in the file t3.cv, starting at character 725, and spanning 21 characters. This information gives us the potential to report back errors in the dsl_block string in terms of the real line numbers the user will see in their file. However, doing so manually is a tedious chore. Fortunately, the second tool is that Converge has a built-in parser DSL which can use src infos. We can adapt sb as follows:
import Builtins, CEI, CPK::Earley::DSL, Sys

parse := $<<DSL::mk_parser("machine", ["PUSH", "ADD"])>>:
    machine ::= instr ( "NEWLINE" instr )*
    instr   ::= push
              | add
    push    ::= "PUSH" "INT"
    add     ::= "ADD"

func sb(dsl_block, src_infos):
  parse_tree := parse(dsl_block, src_infos)
  instrs := [] // A sequence of Converge instructions
  for i := 0.iter_to(parse_tree.len(), 2):
    instr := parse_tree[i][0]
    instr_type := instr.name
    if instr_type == "push":
      ast_int := CEI::iint(Builtins::Int.new(instr[1].value))
      instrs.append([| &stack.append(${ast_int}) |])
    elif instr_type == "add":
      instrs.extend([|
        rhs := &stack.pop()
        lhs := &stack.pop()
        &stack.append(lhs + rhs)
      |])
  ast := [|
    func ():
      &stack := []
      $c{instrs}
      return &stack[-1]
  |]
  Sys::println(CEI::pp_itree(ast))
  return ast
The parsing DSL takes a fairly conventional context-free grammar (lines 4-8). Unless the user goes out of their way to do so, the parsing DSL automatically reuses Converge's lexer, so the stack machine DSL has access to lexing rules such as INT. The parsing DSL requires an explicit start rule (machine) and, optionally, a list of additional keywords over those it automatically inherits from Converge (PUSH and ADD). It then converts the grammar into a function which takes two arguments and returns a parse tree. For our very simple DSL, the tree is so shallow that I didn't need to bother writing a normal tree walker. The result of our simple change is powerful. If we rerun our faulty input against the new sb we get the following error:
 Error:
   File "/home/ltratt/t4.cv", line 36, column 8, length 0:
      PUSH 2
 Parsing error at or near `NEWLINE' token.
While I won't pretend this is the best possible parsing error message – as humans, we'd have preferred in this instance to have been shown the line before rather than after the newline – the text PUSH 2 really can be found on line 36 in the file t4.cv. Importantly, that puts us right next to the line of code which led to the bug, which is far preferable to trying to divine the source of the problem from a stack-trace. DSL Compilers can also use a related tactic to report static errors to the user using the CEI::error function, which takes a string and, optionally, src infos.

Run-time errors

Finding errors statically is useful but also somewhat easy—life gets a lot harder with run-time errors. The following program is syntactically valid but obviously incorrect, trying to add two items from the stack when only one item is present:
f := $<<sb>>:
  PUSH 2
  ADD

func main():
  Sys::println(f())
Since sb performs few static checks, this code will compile. Looking back at the definition of sb, we would expect that the ADD instruction will fail at run-time when it tries to perform the second pop. Indeed that's precisely what happens:
% converge -v t5.cv
===> Compiling /home/ltratt/t5.cv...
func ():
    stack := []
    stack.append(3)
    $$3$$rhs$$ := stack.pop()
    $$4$$lhs$$ := stack.pop()
    stack.append($$4$$lhs$$ + $$3$$rhs$$)
    return stack[0 - 1]
===> Finished compiling /home/ltratt/t3.cv.
===> Linking.
Traceback (most recent call at bottom):
  1: File "/home/ltratt/t5.cv", line 40, column 15, length 3
       Sys::println(f())
  2: File "/home/ltratt/t5.cv", line 22, column 15, length 12
       lhs := &stack.pop()
     File "/home/ltratt/t5.cv", line 28, column 6, length 10
       $c{instrs}
  3: (internal), in Builtins::List.pop
Bounds_Exception: -1 below lower bound 0.
The exception raised is Bounds_Exception, which is Converge's way of saying you tried to access an element beyond the start or end of the list. The stack-trace initially looks helpful: we can immediately see that Converge tracks errors down to the level of where within a line they occur; and we can also see that the problem is related to the &stack.pop() call. However, deeper inspection shows that it's hard to relate it to the source of the problem. After all, I made a mistake in my DSL code, but the stack-trace information is presented in terms of the DSL compiler. If my stack machine code had contained hundreds of ADD instructions, which would have been the source of the problem? Here we see the problem of debugging layers, as programming languages traditionally privilege one layer—the base programming language.

The stack-trace contains a clue that we might be able to do something about this. There are three frames on the stack (i.e. the main function has called another function, which has itself called another function), but the second frame is associated with two source locations (lines 22 and 28). In short, Converge ASTs can be associated with one or more src infos. ASTs that are created by quasi-quotes automatically have a src info relating them to the source location they were defined in; and further src infos are automatically added whenever ASTs are inserted into each other [6]. Users can then add additional src infos to a quasi-quote using the [<e>| ... |] syntax. Since every terminal and non-terminal in the parse tree records the src info it's associated with, it's trivial to pick out the appropriate src info from the parse tree and add it to a quasi-quote. In this case, we simply take the src infos from the ADD non-terminal when we construct the appropriate quasi-quotes, modifying sb as follows:

 elif instr_type == "add":
   instrs.extend([<instr.src_infos>|
     rhs := &stack.pop()
     lhs := &stack.pop()
     &stack.append(lhs + rhs)
   |])
With this small modification, running our incorrect program leads to the following stack-trace:
 Traceback (most recent call at bottom):
   1: File "/home/ltratt/t5.cv", line 40, column 15, length 3
        Sys::println(f())
   2: File "/home/ltratt/t5.cv", line 22, column 15, length 12
        lhs := &stack.pop()
      File "/home/ltratt/t5.cv", line 37, column 2, length 3
        ADD
      File "/home/ltratt/t5.cv", line 28, column 6, length 10
        $c{instrs}
   3: (internal), in Builtins::List.pop
 Bounds_Exception: -1 below lower bound 0.
We can now see that the second frame on the stack is associated with 3 entries, one of which is the line from the stack machine itself (lines 6 and 7 in the stack trace). With this, the user can quickly pinpoint which ADD instruction is the culprit, no matter how many such instructions their program contains.

A reasonable question to ask is whether it's really necessary to allow more than one src info. Could we not maintain the traditional one-source-location per stack frame location, but allow the user to choose what that location records, and still get the effect we wanted? As it so happens, the first version of Converge did just that so I can conclusively answer this with a no. The reason is very simple: when an error happens at run-time, there is no way of knowing which layer was responsible. Unlike traditional compilers, which are heavily tested over multiple years, DSL compilers tend to be more fragile and more susceptible to bugs. When an error happens, there are roughly even odds as to whether the DSL compiler author or the DSL user is at fault. Only if the debugging information for both layers is reported can both people have a chance of debugging the problem.

How it works

A src info is a triple (file identifier, character offset, character span); src infos are an ordered list of these triples. The key to what I've presented above is that src infos – and specifically the notion that there can be more than one at any point – are present in all aspects of the system: the tokenizer, the parser, the compiler, and the VM. In other words, all the parts that make up Converge were written with src infos in mind. The tokenizer starts the work off, giving each token a single src info (though, for consistency, it is a list of src infos that just so happens to have a single src info). The parser doesn't change tokens, but each time it creates a non-terminal, it calculates the span of the tokens in its subtree (i.e. it looks at all the tokens in the subtree in a depth-first fashion, finding the beginning of the first token in the subtree, and then calculating the span upto and including the last token in the subtree) and creates a src info based on that. As the compiler creates an AST from the parse tree, it copies src infos over (sometimes from tokens, sometimes from non-terminals). The bytecode saved by the compiler then associates each individual bytecode instruction with one or more src infos. When an error happens at run-time, the VM then digs out the appropriate src infos for each location in the relevant stack frame. Thus, src infos have no run-time cost, other when an exception is raised.

The bytecode format that Converge uses is not particularly innovative. Simplifying slightly, each compiled module is its own self-contained binary blob. Within that are several contiguous blocks recording various information. One of these blocks is the sequence of VM instructions (e.g. push, pop etc.), each of which we can think of as a single machine word. Another block then records one or more src infos, again each stored as a machine word, for each VM instruction. There must therefore be at least as many src infos as there are VM instructions. However, since high-level operations invariably compile to multiple VM instructions, it is generally the case that successive VM instructions records the same src infos. Converge therefore adds a few bits to each src info to record how many consecutive VM instructions the src info refers to. On average, this simple encoding reduces the size of the src infos block by half.

Summary

The scheme I've described in this article took full form in the second version of Converge. In my mind, Converge is a finished piece of work. At the very least, I feel that I've learnt pretty much all that I'm going to learn from Converge, and I think it unlikely I will do much work on it again. So why have I put together such a long-winded article on one little aspect of Converge? It's for the very simple reason that the idea of src infos – notice my deliberate use of the plural – might have relevance to other languages. In particular, any language which encourages its users to generate code might benefit from such a concept: it really does make debugging multiple layers of generated code much easier. My use of the word encourages is deliberate: I don't think a language needs to have a macro-ish system for the concept of multiple src infos to be useful. For example, there appears to be a growing culture of generating JavaScript code offline, and while, in such a scenario, src infos would need to be recorded differently, their benefits would be the same. I'm not suggesting that retrofitting this concept in is easy: it will often require changing various components, including delicate parts of VMs. I'm also not suggesting that every language would benefit from this concept: it seems unlikely that a C program would ever want the overhead, no matter how small, that src infos require.

So there you are—that's probably the most useful thing I managed in five years of language design. If I'm tempted to do language design again, I will print a t-shirt with the slogan I spent five years designing a programming language and I only got one lousy feature as a reminder to leave it to people with more talent for it than I.

Acknowledgements: My thanks to Carl Friedrich Bolz, Martin Berger, and Lukas Diekmann for insightful comments on early drafts of this article. All opinions, errors, omissions, or infelicities, are my own.

Footnotes

[1] In my opinion, Converge's experiment with an Icon-like expression evaluation system wasn't a success. Fortunately, as so often in research, the dung heap of failed ideas provided fertile ground for a new idea to grow. When I wrote that paper, I thought that the many stack operations needed by Icon's evaluation system precluded an efficient implementation, before foolishly hand-waving about a possible partial optimisation. What I didn't foresee at that point was that meta-tracing would optimise Icon's evaluation system without me having to do anything. Though I was slow to recognise it, meta-tracing had freed me from many onerous constraints I thought inevitable.
[2] My personal experience suggests that programming language designers resemble actors: most hopefuls, such as myself, lack the necessary talent; even for those who are talented, the odds of success are remote; and yet there is never any shortage of people who believe they are destined for greatness.
[3] Formally it should be called compile-time meta-programming, but that's a distracting mouthful. At some points I've tried abbreviating this term to CTMP, but, in retrospect, more readers would have been helped if I'd shortened it to macro. If you understand every detail of such systems, there's a minor difference between traditional macros and compile-time meta-programming but, for most of us, macro gets the point across well enough without requiring the digestion of new terminology.
[4] The $c{e} variant of insertion allows non-hygienic splicing. Put another way, it means splice e in and allow it to dynamically capture variables from the surrounding environment. Hygiene, and Converge's approach to it, aren't relevant to this article, so I refer interested parties to the documentation for further details.
[5] The bolding and highlighting you see is shown by default in the console.
[6] I'm not sure this is the best policy, because it often records semi or completely redundant src infos. However, all my attempts to find a predictable scheme that recorded less src infos led to cases where the lack of src infos hindered debugging. I have no idea whether this reflects a lack of imagination on my part or whether humans have expectations that no automatic scheme can ever quite meet.

Link to this entry


An Editor for Composed Programs

August 20 2014

A few of you might remember a blog post of mine from 2011 titled Parsing: The Solved Problem That Isn't. My hope with parsing has always been that I can take an off-the-shelf approach and use it without having to understand all the details. In that particular post, I was looking at parsing from the angle of language composition: is it possible to glue together two programming language grammars and parse the result? To cut a long story short, my conclusion was none of the current parsing approaches work well for language composition. I was nervous about going public, because I felt sure that I must have missed something obvious in what is a diffuse area (publications are scattered across different conferences, journals, and over a long period of time). To my relief, a number of parsing experts have read, or heard me talk about, the technical facts from that post without barring me from the parsing community [1].

When I wrote the original blog post, I did not know if a good solution to the problem I was considering could exist. I ended by wondering if SDE (Syntax Directed Editing) might be the solution. What I've discovered is that SDE is a wonderful way of guessing someone's age: those under 40 or so have rarely heard of SDE; and those above 45 [2] tend to either convulse in fits of laughter when it's mentioned, become very afraid, or assume I'm an idiot. In other words, those who know of SDE have a strong reaction to it (which, almost invariably, is against SDE). This blog post first gives an overview of SDE before describing a new approach to editing composed programs that we have developed.

Syntax directed editing

Imagine I want to execute a program which adds 2 and 3 times x together. I fire up my trusty text editor, type 2 + 3 * x in, and pass it to a compiler. The compiler first parses the text and creates a parse tree from it, in this case plus(int(2), mul(int(3), var(x)), and then uses that tree to do the rest of the compilation process. In a sense, when programming in a text editor I think in trees; mentally flatten that tree structure into sequences of ASCII characters that I can type into the text editor; and then have the parser recreate the tree structure I had in my head when I wrote the program. The problem with this process is not, as you might be thinking, efficiency—even naive parsing algorithms tend to run fast enough on modern machines. Rather it is that some apparently reasonable programs fail to parse, and the cause of the errors can be obscure, particularly to novice programmers.

In the early 80s, a number of researchers developed SDE tools as a solution to the problem of frustrated and demotivated novices. Instead of allowing people to type in arbitrary text and parsing it later, SDE tools work continuously on trees. SDE tools have the grammar of the language being edited built in, which means they know which trees are syntactically valid. Rather than typing in 2 + 3 * x, one first instructs the SDE tool to create a plus node. A box with a + character appears on screen with two empty boxes to the left and right. One then clicks in the left hand box, types 2, before clicking in the right hand box and typing *. Two more boxes appear on screen into which one enters 3 and x. There is therefore no need for parsing to ever occur: one can directly input the tree in one's head into the SDE tool, rather than indirectly specifying it via a sequence of ASCII characters.

The advantage of SDE is that it guides users in creating correct programs. Indeed, SDE tools actively prevent incorrect programs from being created: at all points the tree is syntactically correct, albeit some holes may be temporarily unfilled. However, this advantage comes at a severe cost: to be frank, SDE tools are generally annoying to use. Novices, like small children, will tolerate nearly anything you throw at them, because they are unaware of better alternatives. When seasoned programmers were asked to use SDE tools, they revolted against the huge decline in their productivity. SDE tools not only make inputting new programs somewhat annoying, but they completely change the way existing programs are edited. Two examples will hopefully give you an idea of why. First, programmers often get half way through an edit in one part of a file (e.g. starting an assignment expression) and realise they need to define something else earlier in a file. They therefore break off from the initial edit, often leaving the program in a syntactically invalid state, and make textual edits elsewhere, before returning to the initial edit. SDE tools tend to forbid such workflows since they need to keep the program in a syntactically valid state [3]. Second, when editing text, it is often convenient to forget the tree structure of the program being edited, and treat it as a simple sequence of ASCII characters. If you ever done something like selecting 2 + 3 from the expression 2 + 3 * x, you have done just this. SDE tools force edits to be relative to a tree. For example, code selections invariably have to be of a whole sub-tree: one can select 2, or +, or 3, or 3 * x (etc.) but not 2 + 3. If this this seems like a minor restriction, you should try using such a tool: I don't think there is a programmer on this earth who will not find the changes required to use such tools hugely detrimental to productivity.

SDE tools thus quickly disappeared from view and within a few years it was almost as if they had never existed. The world would not have been much worse off for this, except for the fact that SDE and language composition are a perfect match. Whereas composing traditional grammars or parsers always involves trade-offs of expressivity or reliability, SDE imposes no such compromise. Since SDE tools are always in control of the languages they are editing, they can allow arbitrary languages to be composed in powerful ways.

I was certainly not the first person to note the potential of SDE for language composition. JetBrains MPS tool is a relatively recent SDE tool which allows composition of powerful editors. To the best of my knowledge, it is the most pleasant SDE tool ever developed. In particular, when entering new text, MPS feels tantalisingly close to a normal text editor. One really can type in 2 + 3 * x as in a normal text editor and have the correct tree created without requiring unusual interactions with the user interface. MPS applies small tree-rewritings as you type, so if you follow 2 with +, the 2 node is shuffled in the tree to make it the left hand child of the +, and the cursor is placed in an empty box to the right hand side of the +. The author of the language being edited by MPS has to enable such transformations, and while this is no small effort, it is a cost that need be paid only once. However, whilst MPS does a good job of hiding its SDE heritage when typing in new text, editing old text has many of the same restrictions as traditional SDE tools. As far as I can tell, MPS has gradually special-cased some common operations to work normally (i.e. as in a text editor), but many common operations have surprising effects. In some cases, edits which are trivial in a traditional editor require special key-presses and actions in MPS to extract and reorder the tree.

MPS is a striking achievement in SDE tools. It lowers SDE to the point that some programmers can be forced, with some encouragement, to use it. Some of the compositions using MPS are truly stunning, and have pushed the envelope far further than anyone has ever managed before. But, if I'm being honest, I wouldn't want to edit a program in MPS, using its current editor, and nor do I think programmers will take to it voluntarily: it makes too many simple things complicated.

A new solution

Simplifying a little, it seemed to us that MPS had made as good a stab as anyone is likely to manage at moving an SDE tool in the direction of a normal text editor; we wondered if it might be possible to move a normal text editor in the direction of SDE. In other words, we hoped to make an editor with all the tree goodness of SDE tools, but which would feel like a normal text editor. So, two years ago, in the Software Development Team at King's College London, we set out to see if such a tool could exist. I am happy to say that we now believe it can, and we (by which I mostly mean Lukas Diekmann) have created a prototype editor Eco based on the principles we have developed. In essence, we have taken a pre-existing incremental parsing algorithm and extended it such that one can arbitrarily insert language boxes at any point in a file. Language boxes allow users to use different language's syntaxes within a single file. This simple technique gives us huge power. Before describing it in more detail, it's easiest to imagine what using Eco feels like.

An example

Imagine we have three modular language definitions: HTML, Python, and SQL. For each we have, at a minimum, a grammar. These modular languages can be composed in arbitrary ways, but let's choose some specific rules to make a composed language called HTML+Python+SQL: the outer language box must be HTML; in the outer HTML language box, Python language boxes can be inserted wherever HTML elements are valid (i.e. not inside HTML tags); SQL language boxes can be inserted anywhere a Python statement is valid; and HTML language boxes can be inserted anywhere a Python statement is valid (but one can not nest Python inside such an inner HTML language box). Each language uses our incremental parser-based editor. An example of using Eco can be seen in Figure 1.

Figure 1: Editing a composed program. An outer HTML document contains several Python language boxes. Some of the Python language boxes themselves contain SQL language boxes. Some specific features are as follows. ❶ A highlighted (SQL) language box (highlighted because the cursor is in it). ❷ An unhighlighted (SQL) language box (by default Eco only highlights the language box the cursor is in, though users can choose to highlight all boxes). ❸ An (inner) HTML language box nested inside Python.

From the user's perspective, after loading Eco, they can create a new file of type HTML+Python+SQL. After the blank page appears, they can start typing HTML exactly as they would in any other editor, adding, altering, removing, or copying and pasting text without restriction. The HTML is continually parsed by the outer language box's incremental parser and a parse tree constructed and updated appropriately within the language box. Syntax errors are highlighted as the user types with red squiggles. The HTML grammar is a standard BNF grammar which specifies where Python+SQL language boxes are syntactically valid by referencing a separate, modular Python grammar. When the user wishes to insert Python code, they press Ctrl+L, which opens a menu of available languages (see Figure 2); they then select Python+SQL from the languages listed and in so doing insert a Python language box into the HTML they had been typing. The Python+SQL language box can appear at any point in the text; however, until it is put into a place consistent with the HTML grammar's reference to the Python+SQL grammar, the language box will be highlighted as a syntax error. Note that this does not affect the user's ability to edit the text inside or outside the box, and the editing experience retains the feel of a normal text editor. As Figure 3 shows, Eco happily tolerates syntactic errors — including language boxes in positions which are syntactically invalid — in multiple places.

Figure 2: Inserting a language box opens up a menu of the languages that Eco knows about. Languages which Eco can be sure are valid in the current context are highlighted in bold to help guide the user.


Figure 3: Editing a file with multiple syntax errors. Lines 6, 8 and 11 contain syntax errors in the traditional sense, and are indicated with horizontal red squiggles. A different kind of syntax error has occurred on line 4: the SQL language box is invalid in its current position (indicated by a vertical squiggle).

Typing inside the Python+SQL language box makes it visibly grow on screen to encompass its contents. Language boxes can be thought of as being similar to the quoting mechanism in traditional text-based approaches which use brackets such as [|...|]; unlike text-based brackets, language boxes can never conflict with the text contained within them. Users can leave a language box by clicking outside it, using the cursor keys, or pressing Ctrl+Shift+L. Within the parse tree, the language box is represented by a token whose type is Python+SQL and whose value is irrelevant to the incremental parser. As this may suggest, conceptually the top-level language of the file (HTML in this case) is a language box itself. Each language box has its own editor, which in this example means each has an incremental parser.

Figure 4: An elided example of an SQL language box nested within an outer Python language box. From the perspective of the outer incremental parser, the tree stops at the SQL token. However, we can clearly see in the above figure that the SQL language box has its own parse tree.

Assuming that there are no syntax errors, at the end of the editing process, the user will be left with a parse tree with multiple nested language boxes inside it as in Figure 4. Put another way, the user will have entered a composed program with no restrictions on where language boxes can be placed; with no requirement to pick a bracketing mechanism which may conflict with nested languages; with no potential for ambiguity; and without sacrificing the ability to edit arbitrary portions of text (even those which happen to span multiple branches of a parse tree, or even those which span different language boxes). In short, Eco feels almost exactly like a normal text editor with the only minor difference being when one enters or exits a language box.

How it works

Language boxes are an embarrassingly simple concept, based on a very simple observation. Context free parsing orders tokens into a tree based solely on the types of tokens: the value is not looked at (doing so would make the parser context sensitive, which is generally undesirable). When the user presses Ctrl+L and selects language L, Eco simply creates a token in the parse tree of type L. From the perspective of each tree, language boxes are normal tokens; the fact that they have sub-trees as values is of no consequence to the parser.

Consequences

Since, in general, one cannot guarantee to be able to parse as normal text the programs that Eco can write, Eco's native save format is as a tree [4]. This does mean that one loses the traditional file-based notion of most programming languages. Fortunately, other communities such as Smalltalk have long since worked out how to deal with important day-to-day functionality like version control when one moves away from greppable, diffable, files. We have not yet incorporated any such work, but it seems unlikely to be a hugely difficult task to do so.

Some thoughts

We think that Eco is not only the first in a new class of editor, but the first editor which makes editing composed programs painless. Put another way, I wouldn't mind using an Eco-like tool to edit composed programs, and I am extremely fussy about my text editor. The fact that I say Eco-like is not accidental. Eco is a prototype tool, with all that entails: it is hugely incomplete (e.g. we currently have little or no undo functionality, depending on how you view things), buggy, and sometimes unexpectedly slow (though not because of the incremental parser, which is astonishingly fast). What we have learnt in building it, however, is more than sufficient to see how the ideas would scale up to an industrially ready tool. Will such a tool ever appear? I don't know. However, unlike when I wrote my original blog post, I can now state with some confidence that a good solution is possible and practical.

If you're interested in finding out more about Eco, you can read the (academic) SLE paper this blog post is partly based on, or download Eco yourself [5]. The paper explains a number of Eco's additional features—it has a few tricks up its sleeves that you might not expect from just reading this blog.

It is also important to realise that Eco is not magic: it is a tool to make editing composed programs practical. It is still necessary to specify what the composed syntax should mean (i.e. to give it semantics), assuming we want to do something with the result. In the case of the HTML+Python+SQL composition, composed programs can be exported to a Python file and then executed. Outer HTML fragments are translated to print statements; SQL language boxes to SQL API calls (with their database connection being to whatever variable a call to sqlite3.connect was assigned to); and inner HTML fragments to strings. We can thus export files from our composition and run them as normal Python programs. There are many other possible, and reasonable, ways to export a program from Eco, and one can imagine a single composition having multiple exporters. If you want to see how Eco fits into the wider language composition landscape, this video of a recent talk shows some of the directions we're pushing ahead on.

Acknowledgements: This work was generously funded by Oracle Labs without whom there would be no Eco. Lukas Diekmann has been the driving force behind Eco. Edd Barrett and Carl Friedrich Bolz gave insightful comments on a draft of this blog post.

Footnotes

[1] Though some of them quite reasonably disagree with me as to whether some of the limitations or trade-offs I mentioned really rule out some approaches from language composition.

[2] I'm not sure if my sample size of 40-45 year olds is insufficient, or whether they really are the inbetween generation when it comes to SDE. Fortunately, I will sleep soundly enough without knowing the answer to this particular question.

[3] I'm told that some of the original SDE tools were more flexible than this suggests, but these seem to be the exception, and not the rule. It's unclear to me exactly how flexible such tools were in this regard. Alas, the software involved has either disappeared or requires impossibly ancient hardware and software to run.

[4] It currently happens to be gziped JSON, which is an incidental detail, rather than an attempt to appeal to old farts like me (with gzip) as well as the (JSON-loving) kids.

[5] Depending on when you read this, you may wish to check out the git repository, in order to have the latest fixes included.

Link to this entry


The Bootstrapped Compiler and the Damage Done

December 4 2013

These days, it's not uncommon to hear that a language's compiler is written in itself. This phrase often confuses non-language implementers: how can a language's compiler be written in itself? The answer is surprisingly simple: what's being referred to is the second compiler created for the language. In such cases, the first compiler created is a bootstrapping compiler with just enough functionality to allow a compiler to be written in the language being created. In other words, when creating language NL, a basic compiler is first written in existing language OL, allowing a compiler for NL to be written in NL itself [1]. When the new compiler is completed, the language is said to be bootstrapped, and the bootstrapping compiler is thrown away, leaving only the bootstrapped compiler written in NL. Not every language bootstraps its compiler, but it is increasingly common to do so, especially for those languages which target VMs [2]. Indeed, it's become sufficiently common that I've sometimes seen new languages which haven't been bootstrapped looked on with slight suspicion (the argument seems to boil down to either or both of you clearly don't think much of your language if you're not prepared to use it to write its own compiler or your language is so underpowered, it can't even be used to write its own compiler).

There are obvious advantages to creating a bootstrapped compiler. Most notably, it means that the language being designed and implemented is also used early in the implementation process. What might otherwise be abstract musings about the use of the language are made concrete by the need to have the language be good enough to write the bootstrapped compiler in. As the compiler is written, missing or undesirable features in the language are discovered and the language's design extended and changed as appropriate. Bootstrapping thus tends to see the design and implementation of a language progressing in unison.

Traditionally, bootstrapping is seen as an almost universal good (apart from occasional griping over performance issues, which can be ignored). I have bootstrapped languages myself, and I will do so again (attacks by random buses allowing). However, I have recently become aware of a real problem with bootstrapping: it can, and does, distort language design. In other words, by having a bootstrapped compiler as the first – and, often, for some time the biggest – program in a language, the eventual language design is often unintentionally altered and rarely for the better. I suspect this has two root causes.

First, we understand how to design compilers better than any other type of program. There are many books devoted solely to the topic of writing compilers. Many clever researchers have put huge amounts of effort into understanding and optimising almost every aspect of compiler design. We have many example compilers and a huge folklore to draw on. This means that programming a compiler is unlike programming any other system I know. Normal programming – especially when starting – involves a huge degree of uncertainty as to how the program should be constructed; even what the program is expected to do is likely to be shrouded in fog. Not so with compilers: we know exactly what they should do, how their major components should be designed, and how those components should be integrated together. Programming a compiler therefore involves an unusually high degree of certainty right from the start. Compiler writers are able to focus on the essence of the task of the hand, without having to worry that choices taken will later necessitate a fundamental change in the compiler's design.

Second, compilers are an atypical class of program. In essence, a compiler is a simple batch pipeline process. A program is read in and translated to a tree; a series of tree transformations are applied; and eventually one of those trees is saved out as some sort of binary data (e.g. machine code or bytecode). Most of the intermediate tree transformations calculate a relatively simple bit of information about the program and create a slightly modified tree based on it. A few calculations crop up time and time again, such as: maps from variables to scopes or types; and stacks to determine closures. Significantly, and unlike most programs in the real world, there is no interaction with users: the compiler knows all it needs about the outside world from the moment it is called.

Since we know an unusual amount about how to write compilers, and because compilers are such a specific style of program, compilers tend to use programming languages in an unrepresentative fashion. A certain style of programming is common in compilers: pattern matching against trees and creating slightly altered trees from them. Most of the trees can be easily statically typed and are, or can trivially be made to be, immutable, since – relative to the capabilities of modern computers – the trees involved are rather small. If that is the program you are most used to writing, it is perhaps inevitable that your language design will make that use case particularly easy to realise, at the expense of more normal programs. On top of that, the complexity of the language is almost invisible to those bootstrapping the compiler, so there is a continual temptation to add features in to the language or its libraries.

In a sense, my fear is easily summarised: we language designers are all too often making languages which are much better for writing bootstrapped compilers than they are for writing other programs. We're coming up with languages with very odd features that are used relatively little other than by the compiler writer, and with languages so feature heavy that only the language designer can understand how everything fits together. Ultimately, we're thinking about ourselves much more than we are normal programmers. I have certainly been guilty of this myself and I fear I see it in several new languages too (though, thankfully, not all).

There is no guaranteed solution to this problem. We can't force an iron curtain to be drawn between language designer and compiler. But, as language designers, we can at least be aware of the dangers of drawing overly strong conclusions based solely on the experience of writing a compiler in our new language. As language users, we should treat the claims of language designers with scepticism until they, or other people, have written a reasonable number of non-compiler programs in their language. This still won't get us to nirvana, but it will stop us being distracted by shiny language features that solve issues compiler writers have that few other programmers share. If we don't, not only shall the meek inherit the earth, but they may choose to do so with non-bootstrapped languages.

Acknowledgements: My thanks to Edd Barrett, Carl Friedrich Bolz, and Lukas Diekmann for insightful comments on early drafts of this article. All opinions, errors, omissions, or infelicities, are my own.

Footnotes

[1] Converge's bootstrap compiler, for example, was written in Python.

[2] For no particular reason that I can think of, languages which compile to machine code seem less inclined to bootstrap.

Link to this entry


Relative and Absolute Levels

September 24 2013

Recently, I've seen a number of discussions along the lines of what makes a language declarative or imperative? (see, in chronological order, William Cook, Bob Harper, and Neel Krishnaswami). Trying to get a crisp definition of vague terms often involves endlessly going around circles. Just in case that isn't bad enough, in this specific case, some believe that their favourite term connotes superiority, thus setting otherwise reasonable people against each other. Intuitively, the two terms are talking about the level of abstraction of a programming language: declarative means that something provides more what and less how; while imperative is more how and only implicitly what. We have a vague feeling that the terms should be precise opposites, but in practice we keep stumbling across examples which are hard to fit precisely into exactly one of the terms. William and Bob are, I believe, both correct in saying that, if the terms declarative or imperative once had a specific meaning, they have long been robbed of it.

I would suggest that what's really going on is that we're trying to use the terms to express absolutes when they can only meaningfully express the relative relation of one thing to another. Before tackling the original point directly, let me try and give an example that is less likely to offend those of us immersed in programming languages. Imagine there are two people competing against each other in a 4km cycle race. Jim takes 5 minutes and Tim takes 4 minutes 50. We might say Tim is quick but we would be incorrect. Tim is only quick relative to Jim. When Kim — who can do the race in 4 minutes 30 — comes into the room, we can clearly see that Tim is not quick compared to Kim. Thus, while relative comparisons between individuals are safe, absolute statements are not: we can't be sure if we will encounter a person who changes our notions of quickest or slowest. Put more carefully, the absolute statements are only correct for the set of individuals we've sampled. Relative statements (e.g. Tim is quicker than Jim) remain correct even when we encounter new individuals.

With that in mind, let's look at a few examples from programming languages:

  • Absolute: Haskell is a declarative language. Incorrect.
  • Relative: Haskell is a more declarative language than C. Correct.
  • Absolute: C is an imperative language. Incorrect.
  • Relative: C is a more imperative language than Haskell. Correct.

Depending on your background, you may find the two incorrects hard to swallow initially. Consider this little C fragment:

a = 1;
b = 2;
c = 3;
d = a + b + c;
print_int(d);
and an example compilation of it into ARM assembler [1].:
MOV R0, #1
MOV R1, #2
MOV R2, #3
ADD R3, R0, R1
ADD R3, R3, R2
STMDB R13!, {R0}
MOV R0, R3
BL print_int
LDMIA R13!, {R0}

Both fragments behave the same, in the sense that they describe the same output (the printing of the number 6). The C version however states much less detail about how that output should occur. The assembler version first has to break the addition down into 2 separate instructions. It then has to save the original value of R0 to prevent it being clobbered by the argument being passed to print. Relative to C, the assembler version feels much less declarative: one might even be moved to say that the assembler version is more imperative.

The fun begins when one realises that the assembly version is not the end of the road. We could, if we wished, go all the way down to electrons when considering a program executing. In the opposite direction, a DSL for expressing Context Free Grammars may feel much more declarative than the Haskell program that is generated from it. As that might suggest, we also need to bear in mind that there isn't a strict hierarchy here. There are multiple dimensions in which different languages can be considered declarative or imperative relative to each other.

This has an interesting implication. For any given two abstraction levels, we can find another in between, or one sideways (and so on). If we wanted to name each, we'd go mad. Thus, proposals such as Neel Krishnaswami's are interesting thought exercises, but we simply can't scale them up (unless you find the prospect of a massive, ever-expanding dictionary appealing).

In summary, trying to define declarative and imperative precisely as absolute terms will never work, if it ever did. Using them as relative terms can feel pedantic, but at least has the virtue of not being inaccurate. Although we really only need one of imperative or declarative, I expect both terms to comfortably outlive me, and for people to use them as vague absolutes in the same way that we use quick and slow as vague absolutes. It's also worth noting that the programming language community is not the only one bedevilled by this issue. The UML folk tie themselves in knots over Platform Independent and Platform Specific Models (PIMs and PSMs). Students of war have spent hundreds of years trying to nail down perfect definitions of strategy and tactics, without success. Humans like the seeming certainty of absolute statements, even in cases where only relative comparisons are safe.

Acknowledgements: My thanks to Carl Friedrich Bolz and Edd Barrett for insightful comments on early drafts of this article. All opinions, errors, omissions, or infelicities, are my own.

Footnotes

[1] It's been 15 years since I last wrote ARM assembler, so my apologies if I've got any minor details wrong.

Link to this entry


General Purpose Programming Languages' Speed of Light

April 9 2013

Having recently returned from a week of talks on programming languages, I found myself wondering where general purpose programming languages might go in the future; soon I wondered where they could go. The plain truth about programming languages is that while there have been many small gains in the last 20 years, there have been no major advances. There have been no new paradigms, though some previously obscure paradigms have grown in popularity; I'm not even aware of major new language features (beyond some aspects of static type systems), though different languages combine features in slightly different ways.

The lack of major advances in a given time period may not seem surprising. After all, major advances are like earthquakes: they occur at unpredictable intervals, with little prior warning before their emergence. Perhaps we are on the cusp of a new discovery and none of us – except, possibly, its authors – are aware of that. That is possible, but I am no longer sure that it's likely. If it doesn't happen, then it seems clear to me that we are getting ever closer to reaching general purpose programming language's speed of light—the point beyond which they cannot go.

Programming languages cannot grow in size forever

The basis of my argument is simple:

  1. Every concept in a programming language imposes a certain cognitive cost upon users.
  2. Our brains ability to comprehend new concepts in a language is inversely proportional to the number of concepts already present.
  3. At a certain number of concepts, we simply can't understand new ones.
Note that I deliberately phrased the first point to reflect the fact that some concepts are more complex to learn than others; but that, at a certain point, the volume of concepts becomes at least as important as the cumulative complexity because of the inevitable interactions between features. In other words, if language L1 has 20 features, of which 6 are complex and 14 simple, the cognitive cost is similar to L2 which has 3 complex and 17 simple features.

This doesn't sound too bad, until one considers the following:

  1. The core of virtually every extant programming language is largely similar.
  2. That core contains many concepts.
  3. Many of those concepts have a high cognitive cost.
In other words, most programming languages are surprisingly similar at their core. Before we can differentiate L1 from L2, we must already have understood features ranging from variables to recursion, from built-in datatypes to evaluation order.

Programming languages' core

The overly earnest teenage boy that lives within all of us wants to believe that programming languages are massively different. At any given moment, someone with a nihilistic bent and an internet connection can find fans of different programming languages fighting pitched battles where language L1 is argued to be always better than L2. The dreary irony, of course, is that what L1 and L2 share in common is nearly always greater than that which differentiates them. How many people use programming languages without function calls? without recursion? without variables? without ...? Nobody does, really. Those languages that are truly unique, such as stack-based languages, remain locked in obscurity.

The reality is that, since the late 1950s, programming languages have steadily been converging towards a stable core of features. That core has proven itself sufficiently good to allow us to develop huge pieces of software. However, it leaves our brain surprisingly little capacity to understand new features. Try and do too much in one language, and problems accrue. We long ago developed the technical ability to create programming languages too complicated for any single person to fully understand. C++ is the standard (though not the only) example of this, and far be it for me not to pick on an easy target. As far as I can tell, not a single person on the planet understands every aspect of C++, not even Stroustrup. This is problematic because one always lives in fear of looking at a C++ program and finding uses of the language one doesn't understand. At best, individuals have to continually look up information to confirm what's going on, which limits productivity. At worse, people misinterpret programs due to gaps in their understanding; this introduces new bugs and allows old bugs to hide in plain view.

In an ideal world, we would be able to understand programming languages in a modular fashion. In other words, if I don't use a feature X, I don't need to know anything about X. Sometimes this works, and organisational coding standards are one way to try and take advantage of this. If this modularity property held fully, it would allow us to add as many modularised features to programming languages as we wanted. However, programming rarely involves creating a program in isolation from the rest of the world, particularly in the modern era. Instead, we pull in libraries from multiple external sources. Even if I don't want to use feature X, a library I use might; and, if it does, it can easily do so in a way which forces me to know about X. Take C++ again: I might not want to use templates in my C++ programs but most modern C++ libraries do. Even if a programming language is designed so that its features are modular, the social use of such a language tends to destroy its modularity. This explains why it's virtually impossible to be a competent programmer without a reasonable understanding of nearly every feature in a language.

Better education?

A reasonable question to ask is whether this ability to exceed the human brain's capacity is a temporary one, due to poor education. As time goes on, we tend to become better at condensing and passing on knowledge. I have heard it said, for example, that what might have baffled an early 20th century physics PhD student is now considered a basic part of an undergraduate education (since I struggled with physics as soon as it became semi-mathematical, I am not in a position to judge). Perhaps, given time, we can teach people the same number of concepts that they know now, but at a lower cognitive cost.

I do expect some movement along these lines, but I'm not convinced it will make a fundamental difference. It seems unlikely that programming students of the future will find it substantially easier to learn recursion or iteration, to pick two semi-random examples. Every language needs to choose at least one of these concepts. Of the two, most people find recursion harder to grasp, but nested iteration doesn't come naturally to many people either. Those of us who've been programming for many years consistently underestimate how difficult newcomers find it. Starting programming education from a young age might change this dynamic, but it's difficult to imagine that sufficient quantities of competent programmers will move to become teachers, at least in the short term.

Better language design

Let's assume, briefly, that you agree that C++ is too complex but are wondering whether its difficulties are due to bad design rather than size. Perhaps all I've really done so far is point out that badly designed languages overload our brains sooner than well designed ones? There is clearly some truth in this but, again, I'm not sure that it fundamentally changes the landscape.

Let's take two statically typed functional languages as an example of more considered language design: Scala and Haskell. Both languages aim to stop users shooting themselves in the foot through the use of expressive type systems. Maybe by constraining users, we can help our brains absorb more general language concepts? Alas, I am not convinced. Some of the things Haskell and Scala's type systems can express are astonishing; but I have also seen each type system baffle world-renowned experts. Type systems, like any other language feature, do not come for free. Even if we could design a perfect programming language, I doubt it could be much larger than such languages are today.

What the above means is that the space for a major advance in general purpose programming languages is limited. The analogy with the speed of light works well here too. As an object's speed approaches the speed of light, the energy required to accelerate it reaches infinity, which is why a normal object can't ever travel at the speed of light. Worse, the energy required is non-linear, so the closer you get to the speed of light, constant increases in energy lead to ever-slower acceleration. Language design is rather like that. Beyond a certain point, every feature – no matter how well designed – has a disproportionate cost. It takes longer to understand, longer to learn how to use idiomatically, and longer to understand its interactions with other features.

Tooling

The tooling that surrounds programming languages has changed significantly in the last two decades. Most developers now use huge IDEs [1], which offer a variety of ways to understand and manipulate programs. Verification techniques and tools have made major advances [2]. And whole new styles of tools now exist. To take two examples: Valgrind allows one to analyse dangerous run-time behaviour in a way that can significantly tame the danger of even unsafe languages such as C; Moose allows one to gain a reasonable high-level understanding of large programs in a fraction of the time it takes to wade through source code by hand.

Clearly, such tooling will only increase in quantity and quality as we move forwards. But will it help us understand programming languages more effectively? Again, I expect it to help a bit, but not to make a fundamental difference. Perhaps future editors will have the ability to simplify code until we zoom in (rather like an extreme version of folding). Ultimately, however, I don't know how we can avoid understanding the detail of programming languages at some point in the development process.

Moving beyond general purpose

What are we to do? Give up on general purpose programming language design? No—for two reasons. First, because a degree of group-think in language design means that we haven't explored the language design space as well as we should have yet. For all we know, there could be useful discoveries to be made in unexplored areas [3]. Second, because the general purpose part of the name is subtly misleading. A traditional assumption is that every programming language has been expected to be applicable to every problem. This then leads to the my language is better than yours notion, which is clearly nonsense. Anyone who tells you their favoured programming language – or even their favoured paradigm – is always the best is delusional. There is no such thing, and my experience is that programming language designers are almost universally modest and realistic about the areas to which their language is best suited.

In a single day, I can do Unix daemon programming in C, virtual machine development in RPython, system administration in the Unix shell, data manipulation in Python, and websites in a hodge podge of languages. Each has strengths and weaknesses which make it better suited to some situations than others. People who need certain styles of concurrent programming might favour Erlang for that, but more conventional languages for sequential processing. Many use cases are currently uncatered for: languages which target power efficient execution may become of greater interest in the future. All in all, I suspect we will see a greater level of customisation of nominally general purpose languages in the future.

I also suspect we will see greater use of more obviously restricted languages, which are often called domain specific languages [4]. Rather than try and make features that work well for all users – and that must still be understood by those for whom they don't work well – we are likely to have better luck by focussing on specific groups and making their life easier. For example, I do not wish to have my programming language cluttered with syntax for traditional mathematics (beyond the bare essentials of addition and the like), because I don't use it often enough. A programmer crunching data to produce statistics, on the other hand, would be much more productive with such a syntax. My current guess is that we will build such languages by composing smaller ones, but there are other possible routes.

In many ways, neither of these outcomes is quite as exciting as the notion of a perfect language. The contemporary emergence of a wide class of acceptable general purpose languages is an acknowledgement that we can't squeeze every feature we might like into a single language—our brains simply can't handle the result. Rather than try and move general purpose languages beyond the speed of light, we'll probably end up with many different points near it. At the same time, the possibility of restricted domain specific languages may enhance our productivity in narrower domains. This is, perhaps, not as immediately exciting a prospect as targeting all users, but it is its relative modesty that makes it more likely to pay off. Furthermore, unlike general purpose languages, that journey is nearer its beginning than its end. We might be reaching the speed of light for general purpose programming languages, but we've barely started with domain specific languages.

And, of course, there's always the remote possibility of an unforeseeable earthquake hitting programming languages. Unlike in the real world, we are not callous or inhuman for hoping that such an earthquake will hit us, even though many of us are not sure it will ever come.

Acknowledgements: My thanks to Martin Berger, Carl Friedrich Bolz, Lukas Diekmann, and Naveneetha Vasudevan for insightful comments on an early draft of this article. All opinions, errors, and infelicities are my own.

Footnotes

[1] I don't, because I'm a Unix Luddite at heart, but you may well think that's my loss.

[2] Even the simple static analyser in clang catches a host of nasty bugs that previously escaped the eyes of even the best developers. More advanced tools can do even better, though one should not overstate the power of such tools.

[3] As an example of the fun to be had exploring unusual language design, I immodestly offer my experiences on integrating an Icon-like expression system into a Python-like language. If nothing else, it taught me that it is possible to completely subvert expectations of how standard parts of a programming language work. The HOPL series of workshops, and the generally wonderful papers therein, are another excellent source of programming language design ideas.

[4] Note that I'm talking about languages with distinct syntax and semantics; the term is also currently used to describe particular idioms of library design and use in conventional languages, though I suspect that will fade in the future.

Link to this entry

Earlier posts

 

All posts

 

Last 10 posts

Debugging Layers
An Editor for Composed Programs
The Bootstrapped Compiler and the Damage Done
Relative and Absolute Levels
General Purpose Programming Languages' Speed of Light
Another Non-Argument in Type Systems
Server Failover For the Cheap and Forgetful
Fast Enough VMs in Fast Enough Time
Problems with Software 3: Creating Crises Where There Aren't Any
Problems with Software 2: Failing to Use the Computing Lever
 
 

DSLs

Tony Clark
Zef Hemel
 

Modelling

Mark Delgano
Steven Kelly
Jim Steel
 

OS

Marc Balmer
Ross Burton
Peter Hansteen
OpenBSD Journal
Ted Unangst
 

Programming

Gilad Bracha
Tony Clark
Cliff Click
William Cook
Jonathan Edwards
Fabien Fleutot
Martin Fowler
John Goerzen
Grace
James Hague
James Iry
JOT
Ralf Laemmel
Lambda the Ultimate
Daniel Lemire
Michael Lucas
Dan Luu
Bertrand Meyer
Keith Packard
Brown PLT
John Regehr
Diomidis Spinellis
Shin Tai
Markus Voelter
Phil Wadler
Russel Winder