Lambda the Ultimate

Background

In traditional formalisms, programs are texts that conform to some concrete syntax. These are presented to a computing system which interprets them and produces output.

In graphical programming languages, the notion of a "text" is generalized to include various forms of diagram rather than simply linear texts. But graphical languages can still be regarded has having a concrete syntax - it just happens to be a diagram syntax.

Visual programming systems (e.g., Scratch) offer dynamic graphical languages, usually over simple object models. Thus, as a programmer edits the diagram which defines a program, interpretation of the diagram is interleaved and the effects of program changes immediately appear in the running program.

Drawbacks

Relative to string-based languages, graphical languages typically suffer the drawback of limiting the kinds of transformations that are conveniently available to write programs. For example, when writing C programs we certainly make use of transforms that can be expressed using a C pre-processor but, beyond that, it is often helpful to write simple text processing programs (e.g., sed or AWK programs) that carry out global transformations on large bodies of source. I see no theoretical obstacle to having similar tools for graphical languages but they do not seem to be common. Perhaps this situation will change as more mature, more general purpose graphical languages arise.

Even text-based languages suffer from weaknesses in how user-initiated program transformations are handled. For example, consider two (textual) programs which differ by the systematic renaming of some globally visible function. Typically, software development tools regard the change between these programs in terms of retroactively computed "diffs" - a note of which lines of code have been altered. In "diff" format, the information content of the transformation - the renaming of a function - is lost. The information is lost in the sense that if we begin with the original program, then make unrelated changes (say, simply reformatting the code), and then try to apply the diff - we usually will not get a new program with that function successfully renamed.

One response to this drawback can be seen in contemporary "integrated development environment" editors. It is common and popular, these days, for such editors to have features which automate various commonly used transformations, such as renaming a function (and updating all callers). Taken to an extreme, such editors become fully "syntax directed editors" in which all changes to a program text are expressed as transformations that are sensible from the perspective of an underlying abstract syntax. Still, the concrete syntax of the underlying program is king in these systems: it is what is saved on disk or in revision control systems and it is the input to interpretation. For example, using a syntax directed editor on a program does not help someone else to merge the transformations you performed into a related but variant copy of the program, nor is there a handy record of the transformations for other programmers to study to try to understand the program.

Gestures and Visualizations

Consider a language defined in terms of an abstract syntax but, for the moment, not given a concrete syntax. Any language you like can be "reduced" to such and we can use "'" ("prime") to denote that: C' is C without concrete syntax (hence to CPP, either); Scheme' is Scheme without surface syntax, etc.

Given such a language, two useful constructions can be made: a class of concrete visualizations for the language and a basis set of abstract transformations of programs.

Visualizations are simply various means of presenting the abstract syntax of a program - pretty printing, picture drawing, etc.

Gestures are a class of abstract transformations on abstract syntax objects that form a basis set and have certain compositional properties. The basis set of gestures is minimally sufficient to construct any possible abstract syntax object as a series of transformations that begin with a "null program" (e.g., "main(){ return 0; }"). Gestures can be composed (yielding more complex gestures).

Programs as Edit Histories

Consider the "hello world" program. One way to describe in C is (essentially) "main() { printf ("hello world\n"); return 0; }". The same program could be described as gestures: "begin with the null program; insert an initial statement which is a call to 'printf'; pass the constant string 'hello world\n' to printf."

If we drop the first part of that gesture ("begin with the null program") we're left with a parameterized gesture: it takes any program as input and modifies that program by inserting the printf call at the top of 'main'. If one started with the null program and applied the hello world gesture twice, presumably the result would be a program that printed "hello world", twice.

Programs in any of our "primed" languages (C', Scheme') can be regarded not as a string in a concrete syntax but, rather, as a transcript of the gestures used to form the program.

Gesture transcripts, of course, have some semi-algebraic properties. For example, a transcript that inserts the hello world printf 3 times and then deletes one printf is recognizably the same program as a transcript that only inserts the printf twice: the equivalence is reflected in the final abstract syntax object constructed from the gesture transcript.

Interesting Possibilities

One simple but potentially powerful observation is that if programs are gesture transcripts, then programs are also revision control records: the two become one and the same. Contemporary and historic revision control systems struggle at fundamental operations such as "merging" the changes made in one version of a program to a variant version of the program. They struggle because, as mentioned above, they work with textual differences rather than with the desired semantic transformations. Gesture based languages could begin to repair that situation.

Perhaps more interestingly: consider the myriad possibilities that arise if we permit:

• annotations to gestures (commenting)
• attachment of verifiable assertions to gestures (applicability and effect checking)
• programmatic generation and transformation of complex generators (macros)

The concept suggests to me that we could build "Domain Specific Programming Systems" rather than traditional "Domain Specific Languages". That is, in place of a traditional language definition - a concrete syntax over an abstract syntax over a semantics - we would have at core an abstract syntax and a semantics, sure, but atop those an integrated editor command set, revision control record type specification, and an extensible means of defining what constitutes "correctness preserving" transformations on programs (for some definitions of "partial correctness").

What Would it Look Like? How Can it Be Built?

There are many ways in which a C' or Scheme' (or YourFavoriteLanguage') system could be built. I'll sketch one that seems practical to me, although it is not a small job, and from this sketch we can get at least one imagining of what a system would "look like" in practice and real-world use.

Let's choose C' for a concrete example.

The abstract syntax of C' can be derived from the specification of C and described as an XML Schema (that is to say, as a sub-type of XML data objects generally). Given a C' program that has been reduced to an AST in XML form, it is a trivial matter to "pretty print" that XML as standard C code and pass the result to an existing C compiler. We thus obtain, fairly trivially, an interpreter for C' abstract syntax trees.

An XML representation for abstract syntax objects affords a wide range choices for how to define and implement gestures. For illustration I'll choose a certainly imperfect and ad hoc technique: gestures for C' can be defined to be a subset of XSLT programs. For those less familiar, XSLT programs are programs in a widely implemented, simple, functional language for expressing tree transformations on XML data. The input to a gesture program is in part the abstract syntax object of a program but additional parameters (e.g., a number or string provided by a user) can also be provided. If suitable conventions are created, gestures-as-xslt can be referenced and accessed by globally unique name. XSLT programs are themselves XML datums and they can be extended in ways that support annotations such as the verifiable assertions we want to add to gestures. XSLT programs can be modular and automatically constructed. (Summary: XML and XSLT give us a simple but workable programming environment for tree transformations, suitable to the task at hand.)

Visualizations are then easily programmed as XSLT transformations, CSS, and optionally Javasccript to render programs in browsers in any number of ways. Interactive editors for transcripts of gestures fall out of this naturally.

One example benefit I mentioned earlier was the notion of directly using gesture transcripts as the unit of storage in revision control systems so as to, for example, improve the quality of support for complex merging of changes among variations on a program. How would this work? Well... a "transcript" can be defined as a member of a slender subset of all XSLT programs that have the form of a simple composition of primitive gestures and other transcripts along-side user-supplied parameters. C.f., for example, Darcs for an introduction to the semi-algebraic ways in which archives of such compositions can be manipulated to implement familiar revision control system practices.

Summary

The hypothesis argued for in this piece is that:

Concrete syntaxes are the wrong input to programming systems.

Programming languages should be defined in terms of an abstract syntax and a semi-algebraic structure of transformations of abstract syntax objects. We dub these transformations "gestures".

We regard programs as transcripts of gestures that, beginning with the null program, produce the desired program.

This understanding of programming affords the possibility of multiple ways to visualize a program and edit a program.

This understanding of a programming unifies (roughly, identifies) a program with its revision control history.

Through extensions such as annotating gestures, verifying assertions in gestures, and automatically generating gestures a new and interesting approach to domain specific programming systems is revealed.

It is not a small project but not a hard project to begin to build such a thing.

Disclaimer: The author is not aware of prior work that is quite like this but welcomes news of such.

-t