This is a free transcription of the author's keynote held at the Workshop on Original and Open Problems of Software Language Engineering. ? Copyright c 2020 for this paper by its author. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Software Language Engineering (SLE) is the study of techniques and tools for SLE. It follows from the recursiveness in this denition of SLE that for any challenge of SLE identied, there will be a next challenge, namely to devise a technique or tool for addressing it.
That would be an SLEish explanation of the title of my keynote. However, the true reason for the ominous n + 1 is that at the time of its announcement, I was not sure how many challenges I wanted to present; I only knew that I wanted to present one concluding, down-to-earth challenge that everyone could relate to.
The list of challenges I ended up with has length 5 + 1, and is a personal one. I am sure that others see other challenges, and also that some may not even regard my challenges as such. However, if the presented challenges cause frowning, I am happy, since frowning usually marks the beginning of progress.
Without further ado, here are my challenges, nicely enumerated and terminated by one banal bonus challenge. Text-based language is inherently linear. This holds for spoken as well as for written language. Graphs are not generally linear, but can be linearized; in fact, they must be linearized when speaking or writing about them (using language, that is). The linearization of non-linear content requires encodings that may add complexity to interpretation, which is needed to reconstruct the information lost by linearization.
Not all types of graphs suer equally from linearization. For instance, trees like
a b c are conveniently encoded as terms, which blend seamlessly with linear text, as in
terms like a(b; c) blend seamlessly with text.
While the same holds for set-notation based lineaer representations of graphs like f(a; b); (a; c)g f(a; b); (a; a)g their interpretation requires the build-up of a (mental) environment, or lookup table, here to note that a occurs twice, meaning that the graph has two edges starting from the same node. The term representation, which does not need lookup for its interpretation, is therefore at advantage here.
Term representation is however challenged by graphs that are not trees. For instance, which is but a slight variation of (1), cannot be directly encoded as a term: whereas (2) delinearizes as (1) (2) its naive rendering as a term a(b; a), if at all considered legal, delinearizes as in which the two occurrences of a represent dierent nodes, meaning that a(b; a) represents a dierent graph than (2). To encode the same graph as a term, an explicit lookup must be introduced, as in a(b; a ): while syntactically, this still represents a tree the quoting can be used to construct the graph a
b b
a a a a b b a from it. However, now the term representation has lost its above-noted advantage, namely its independence from lookup.
Even if it requires lookup, using terms for the representation of graphs still
has the advantage of overlaying the graphs with trees, which requires special
markup for set-based representations of graphs like (1) and (2) (see the nal
challenge for an example). This overlaid tree not only xes linearization (for the
set-based linearization, the order of edges is arbitrary), it also denes a
containment relation that can be used, for instance, for restricting lookup. However,
most realistic languages have more than one such relation, so that markup will
be needed anyway, and lookup cannot generally rely on containment alone (see,
e.g., [
When looking at our metalanguages, and also at the metatheories that come with them, we nd that terms are the predominant data structure: terms encode the syntactic structure of the subjects of the metalanguages, and also drive inductive denitions and proofs. And yet, the general insuciency of terms becomes all too evident in the omnipresence of environments, or lookup tables (often encoded in Greek, with the usual connotation that it is getting complicated), which are required to account for the inherent non-treeness of the subject matter.
So, are trees a necessary tribute to the use of metalanguages and their
theories? Rather not. As has been pointed out by Martin Erwig [
The Graph Paradox: In dealing with graphs, we resort to trees. It is a paradox because we express the general in terms of the special, which should be impossible. That it is possible nevertheless is because actually, we resort to trees plus environments, and to lookup for extracting edges on the y.
Leaving this academic kink aside, the preference of trees over graphs appears
to come with a preference of functional metalanguages over relational ones.
However, just like trees are more constrained than graphs, functional languages are
more constrained than relational languages. While being more constrained can
amount to being more powerful, more power usually comes with less
expressiveness, and indeed, functions are uni-directional, and dealing with partiality
(partial undenedness) and mapping to more than one value require clumsy
workarounds. It is somewhat revealing how the functional community takes pride
in their Maybe and List monads, which eectively make functional languages
more relational, yet only at the price of adding indirection through a container,
which adds considerable complexity [
Language shapes thought. Maybe the linearity of languages leads to a preference of trees; and with it to a preference of functions, over graphs and relations. Maybe we would fare better if we used graphs and relations directly, rather than encode them as trees and functions. We will not know until we try.
Tend To Your Metalanguage, or: Use One that Works
In his acclaimed keynote It’s Time for a New Old Language [
Terseness combined with implicit standardization, or conventions, can be
a hindrance to the accessibility of papers. For instance, and as also noted by
Steele [
C(C f ) fsuper(f ); this:f = f ; g
(from the specication of Featherweight Java [
C( [ C f f ; C f g ] ) fsuper( [ f f;f g ] ); fthis:f = f ;gg which in turn must be expanded to or even, in the most general case, to
C(C1 f1; : : : ; Cn fn) fsuper(f1; : : : ; fn); this:f1 = f1; : : : this:fn = fn; g C(C1 f1; : : : ; Cn fn) fsuper(f10 ; : : : ; f n00 ); this:f100 = f1000; : : : this:f n0000 = f n00000 ; g when it comes to specifying semantics. As if this were not occult enough, dierent papers use dierent notations, so that accessing any one of these papers is only possible if one already knows which content to expect. Wouldn’t it be great to have a single metalanguage whose mastering is sucient to access the contents of all papers?
Of course, the community has such a metalanguage: Latex. Unfortunately, Latex is a highly underconstrained language that is not at all related to, let alone domain-specic for, solving the problems of SLE. 1 What would be needed instead is a unied language for SLE, or a
(USLES).
And yet, experience with another unied language standard tells us that usefulness may be compromised, rather than increased, by unication. Why, then, not use an existing, versatile, proven language as metalanguage? A language that works not only on paper, but that can actually do something? Like ML, Prolog, or Coq?
In fact, although not generally a requirement, it would be good to have executable metalanguages, since only executable languages can actually do some work for us. This of course would make all our specications programs, which is great, since programs we know how to test and debug. And, after all, isn’t the passion for programming much wider spread than the passion for specication? 3
Operationalize Editing
Like object languages, metalanguages are usually constrained by static semantics. The metalanguages in which static semantics are expressed additionally need dynamic, or operational, semantics, for otherwise, the constraints expressed cannot be evaluated. However, these constraint languages are usually not programming languages in the sense that they are unable to construct new objects, or lack a notion of state. Programming languages, on the other hand, can be, and routinely are, used to express both static and dynamic semantics of metalanguages, even though most programming languages are not particularly suited for this purpose. That’s why SLE is so rich in DSLs.
For many programming languages, statically type-safe ones in particular,
static and dynamic semantics work hand in hand so as to guarantee certain
runtime properties of programs. These properties usually include notions of
wellformedness of run-time structures (preservation [
Why not apply this situation to the level of metalanguages? After all, when we run an editor as a program, its operations are the edit operations, and its state is the current shape of the object (program, model) being edited. And yet, even though a semantic editor embodies the static semantics of the object language (i.e., the language of the object being edited), its edit operations usually make only weak guarantees with regard to preserving well-formedness of the object (the runtime structure manipulated by the editor as a program), and leave most of the constraints of the static semantics of the object language to runtime checking. This is so because many well-formedness constraints of the object languages are non-local, and because single primitive edit operations, even in a semantic editor (in which an AST is manipulated directly and hence in a typesafe manner), are generally insucient to preserve global well-formedness. Yet, this is not a lost case.
For instance, sound refactoring tools compute sequences of primitive edit
operations required to make the intended change and to keep the program
wellformed [
Edit transactions will also be needed in the context of collaboration, or
parallel editing of the same object [
Speaking of version control: what do programming languages have to do with les? Nothing! 2 Files are the subjects of programming tools, that’s all. There is no theoretical obstacle to storing source programs in databases, and to use more sophisticated representations than plain text for this on the contrary, there’s a lot to be gained from doing so. SLE will know that it has delivered when programmers no longer ask for copy &paste of arbitrary (i.e., not structurally bounded) ranges of text. 2 Of course, some languages are dened as depending of les, like C for instance. Java on the other hand replaces les with the notion of compilation units, which are storage technology neutral. Yet, compilation units are chunks of text, which can be edited just like (text) les.
A compiler that compiles itself, a metalanguage that denes itself SLE is the metacircular discipline of metacircularity. While others 3 consider eating their own dog food an academic exercise, the SLE community lives on it.
While such a practice may be considered educational, and certainly is both witty and economic (what an undefeatable combination!), I conjecture that it generates generations of scholars for whom SLE tools are the only programs they have ever seen the inners of. As a corollary to this conjecture, I assume that the same scholars prefer to model everything as an immutable tree. Life can be wonderful if spent inside an ivory tower.
The real world is very dierent, however. In the society that covers my salary, an estimated 80% of all software created is embedded, and security, real-time, and resource eciency are as important as safety guarantees. For the remaining 20% of software created, distribution, persistence, and integrity are just as vital.
Almost none of this is the subject of SLE. Yet, SLE is dearly needed in these contexts, as the demands from software, and with it the software, grow rapidly beyond what can be managed without SLE techniques and tools. But would companies whose revenues come from other products than geeks’ tools hire software language engineers? If they did, what would they get? From inside an ivory tower, it is easy to judge what is going on out in the wild, yet almost impossible to change it for the better. Only if software language engineers know enough about security, real-time, and resource eciency, as well as distribution, persistence, and integrity, they will have a real impact. And real impact can be more rewarding than agreeing inside an ivory tower on how the outside world should be. 5
Escape the Empiricism Trap, or: Formalize Utility Relevance requires utility. After too many papers making too grandiose claims supported by too little, the scientic community agreed that if formal proofs cannot be delivered, empirical evidence will be needed instead. Hard empirical evidence is however hard to obtain in a eld in which experiments have strong cognitive aspects and confounding factors are hard to control. Specically, the performance of humans making use of the latest SLE product depends on experience and education, and memory makes every experiment a confounding factor for the next. It is therefore questionable whether SLE experiments with humans provide more reliable answers than clear judgment common sense reasoning.
So, what can we do to escape the empiricism trap? In economics, very
prestigious prizes have been repeatedly awarded to the development of mathematical
models of human behavior in decision making problems, aka game theory.
Programming is a decision making problem; more specically, and when taking tool
support into account, it is a game played by the programmer and the IDE, in
3 It seems that as a tool, metacircularity works only for informatics; in other
disciplines, it is either impossible to construct, or considered bogus.
which each take turns: the programmer strikes a key, the IDE responds with
immediate feedback such as proposing completions or marking or unmarking errors.
In fact, programming with an IDE is a cooperative game, one in which the
programmer has the idea of what the program should do, while the IDE knows how
the program may evolve. The programmer works towards the program becoming
useful, and the IDE works towards best use of existing code and error-freeness.
Any new aid in this process that is put forward in a scientic context should
show how it improves this game, by some self-selected metric. Metrics can be:
number of decisions to be made by the programmer until a program is correct;
number of choices oered by the IDE at each decision point; information
content of the made proposals, etc. If analytical captures of the complexity (big
O) of the decision problems are too hard to derive (which, given the complexity
of the nature of programming, would not be surprising), simulation and Monte
Carlo techniques may still provide acceptable evidence. Some rst work in this
direction (albeit restricted to software processes, not tool interaction) has only
just appeared [
Abstract syntax trees are typed and attributed graphs in which each node is an instance of a type (or class) representing a syntactic category, and in which attributes hold either values or references to other nodes. Attributes are also typed; reference-typed attributes provide for the edges of the graph.
Some of the attributes dened for each node type are designated as child attributes; they dene the spanning trees that let us regard abstract syntax graphs as trees (cf. Challenge 1). This tree structure is of special signicance even at the abstract syntax level, namely when it denes the containment relation of a programming language, and with it its lexical scopes. Because of this special role, the containment relation almost always needs to be navigated in both directions: from the owner of the attribute to the child and from the child to the owner, aka parent. The parent direction of the relation is usually also represented by an attribute (which may be derived, though) and, therefore, is also typed. The question is, what is its type?
Naively, it has the type of the owner of the corresponding child attribute, but this does not work if dierent parent node types share the same child node type. This however is routinely the case; for instance, for programs comprised of (global) variables and functions, where functions may have local variables, we may nd the node type declarations node type Prog = child var : Var; child fun : Fun end; node type Var =
parent() : Prog end; node type Fun = child var : Var; parent() : Prog end; (where parent() means that the parent is derived). Now given the nodes
p : Prog var v : Var
fun f : Fun v0 : Var var the expression v0.parent().parent(), which would get one from v0 to f to p, is ill-typed, because the type of v0.parent() is Prog, and Prog does not have a parent() attribute.
While this problem is a very standard one, it seems that it is solved by every implementation of abstract syntax trees anew: some use union types (here: Prog#Fun for the parent attribute of type Var) or least common supertypes for parent attributes, and resort to type tests and downcasts for accessing attributes specic to an actual parent node (here: to access parent() on v0.parent()), while others may use more sophisticated type systems or bypass static typing entirely. Why is that so?
We get: the world depends on software software depends on software languages the world depends on software languages