A Case for Gestures/Visualizations and Against Concrete Syntax

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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

[admin]

Just for future reference, we generally discourage posting such long and relatively substantial pieces directly on LtU. There's a line about this buried in the policies which reads, "If a long description proves necessary, it should be posted elsewhere, such as on your own blog or website, and posted as a link on LtU."

That said, this at least seems on topic enough, so I'm not suggesting any action now.

Some possibly relevant work in this area is Jonathan Edward's work on Subtext.

[admin] noted

Noted. Sorry about that.

-t

Source control

I've designed something similar recently, but I look at it as a way to improve source control and not peculiar to programming languages. Lots of applications (not just document editors) would benefit from having their undo/redo functionality integrated with revision control for implicit commits of every keystroke/command. Surely we don't want the semantics assigned to a program to depend on the edit path by which that program was obtained.

As for editing the AST in some abstract form directly rather than just editing text, it does make some things easier for a live editor - you can keep your tree well-structured and don't have to worry about problems like deleted closing braces. I personally decided on staying with text and making an effort to notice when things haven't changed and cached results are still valid.

(re "source ctl.") teleology and practicalities

Part of my hope here is that the utility goes beyond merely source control but really into changing what artifacts we regard as programs for the practical purpose of having new kinds of tools we use to build and maintain programs. Not just source control but an encouragement to think of programs as abstract syntax objects that can be directly analyzed and that can undergo transforms that can be automated.

What is the purpose - teleology, so to speak - of a programming language and is a canonical concrete syntax really contributory to that purpose or is it a historical accident?

As for text vs. structure editing in UIs, I think that that's an orthogonal implementation choice / issue.

-t

I think concrete is good

I think there's something valuable in being able to look at something concrete and say *that* is the program, and proceed to reason about what it means. Doing programming in a more structured editor (that enforces a tree hierarchy of constructs, for example) is certainly possible and I see it as having pros and cons with text and I personally chose text because it supports the way we're accustomed to editing it (the broken intermediate stages of cut/paste, etc.). I still consider an XML tree concrete, though.

But if you go further and start having abstract values for language constructs that persist in some nebulous binary format and are responsible for projecting themselves somehow, I see that as a bad idea. One reason is that you'll probably want an extensible language where you can add new types of constructs, but then you have this chicken/egg problem where the source code is defining the meaning of the very constructs used to define that meaning.

I think it's preferable to define a mapping from some concrete syntax into abstract constructs. This approach is compatible with programming in a live/dynamic environment where the constructs you've entered can provide feedback/interaction.

concrete is here

I've not suggested or limited myself to "language constructs that persist in some nebulous binary format" - I've tried to draw a distinction from that.

In the implementation tactic I suggested, for example, programs are reducible to XML representations of their abstract syntax objects. In a way, I've said "get rid of concrete syntax" but superficially contradicted myself by saying "use XML as a concrete syntax".

Perhaps a more banal way to describe that is to say that canonical concrete syntaxes should emphasize machine rather than human processing, although it should not be impractical for humans to work with the concrete syntax using a text editor (hence the choice of XML). I don't think that means I've crossed into "nebulous binary formats".

-t

Apologies for the strawman

Apologies for the strawman, I didn't actually think you were advancing an opaque binary format (I really wasn't sure). I suppose I just don't understand your idea - particularly the part about the transcript being the program. Suppose you start with a null program, and then insert "print 'A'" and then insert "print 'B'" after that. Is that different than starting with null program, inserting "print 'B'" and then inserting "print 'A'" above that? If those are different programs, that sounds pretty confusing to me. If they're the same, how does this differ from S-Expressions?

(no apology nec. and...) how distinct from s-exps

Languages which use s-exps as their syntax are typically designed and defined with the expectation that users will be typing s-exps as text. What I am describing has no singular textual or graphical input format - it is "language definition in terms of abstract trees and composable transforms on trees" rather than programming as writing a text or drawing a diagram. I'm redefining the role of the language designer and nudging what it is we trade when we trade "the source" to a program.

-t

Let me see if I understand...

It looks to me like you want to do the following things:

1. Replace concrete syntax with a customizable skin over XML or S-Exprs.

2. Improve source control to know about each gesture used to generate the source.

3. Have everyone adopt a practice of exchanging their improved revision histories instead of just snapshots of their programs.

4. Change the terminology so that "program" now refers to the reversion history instead of the final source.

I'm with you until 4. I find that confusing. (And 3 should be opt-in)

"Final Source"? "The Last First"?!?!

4. Change the terminology so that "program" now refers to the reversion history instead of the final source.

I'm with you until 4. I find that confusing. (And 3 should be opt-in)

"the final source" sounds confusing...

re "change terminology so that 'program' == revision history"

I should make a new distinction re (4).

A "program" now refers to a construction by composition of commonly understood transforms. It *may* usefully be the literal revision history of the program as people came to it over time or it may be a literary reconstruction - a useful "just so" story of what transforms added up to the program at hand.

-t

No

That's a convoluted definition of program. I like what Pontus Johnson and Mathias Ekstedt have to say in The Grand Unified Theory of Software Engineering (The GUTSE Book). They are translationists; Model-Driven Architecture weenies like me. Highly recommended philosophical reading on "What is a program?" They dig into Wirth's and Djikstra's philosophies, etc.

Retconning

With this model, a useful "normal form" can be defined, which is the single transformation from the null program to the final program. Which I would tend to want to call "the program". :)

clever, Anton, but...

So, in that case a key distinction to which to draw attention is the issue of "static analysis". The analysis of a composition of transforms that describe how an idealized person might have written the program in the first place is different (a superset, I claim) of the useful analyses that could be performed on a simple "here's the final text" version of the program.

One key here is that when I invoke a particular transform on the way from null to the what runs I can decorate it with assertiosn about my assumptions and about conditions I'd like to preserve.

-t

Example: As an axiom, the "null program" can't blow up the nuclear power plant. That requirement is our "partial correctness" criterea. Proofs exist for each transform along the way. If you want to duplicate that from just the "final text" of the program you have a harder job.

One key here is that when I

One key here is that when I invoke a particular transform on the way from null to the what runs I can decorate it with assertiosn about my assumptions and about conditions I'd like to preserve.

I talk about this a lot, and think I've even given the below critera on Lambda the Ultimate before. However, the earliest time I recall defining these requirements was in an Artima.com thread about Knuth on Literate Programming: You can read my comments in the threaded discussion.

In essence, I take a Cleanroom Software Engineering approach. You may feel free to disagree with my key statement: "There are four levels of specification: defined, implementation defined, unspecified and undefined." This basically defines a rigorous structure for applying such assertions. Most languages today are astonishingly bad at providing compiler writers with enough assertions; most compiler research today is about data mining programs for assertions that are true within the context of the source text. For instance, pointer aliasing research targeted towards C compilers is basically trying to solve pointer aliasing problems given extremely difficult constraints. As a consequence, a lot of optimization ideas have to be thrown out the window because they cause huge graph explosions trying to prove an optimization exists, rather than verifying that an optimization is possible.

the proofs ...

Proofs exist for each transform along the way.

I'm having some difficulty gauging this. Intuitively, it feels like for current languages, such proofs might exist only for some of the most trivial transforms - probably what automatic refactoring tools have managed to crack. (They are trivial in the sense that they are very easy to conceive of - ex: rename a variable - though not necessarily easy to implement - ex: accounting for scoping rules, etc.)

In other words, it really depends on how useful and valid a partial program is and I doubt if very many partial programs are valid and useful. It'll be great to have an example worked out in detail - i.e. one non-trivial program that is constructed as a series of transforms from the null program, with each step annotated with assertions as you mention. May I suggest "quick-sort of a file of numbers with a number on each line"?

re "the proofs..."

I am not claiming that there are proofs that become possible when regarding programs as transcripts of annotated gestures that are impossible when treating them as texts. I'm not claiming any kind of "foundational" breakthrough in that sense - merely a pragmatic one.

One set of examples comes from equivalence. Let's suppose that I replace a loop with Duff's device. "It would be nice" to have a ready-made transform for doing so, given user-supplied parameters, and proof schema that go along with it that says the before and after programs are the same. And it would be nice to have a record of this - e.g., for people studying the code. For example, it may be useful, when modifying the loop, to revert to the simple loop, make changes, and re-apply the Duff transform. Interactively, wouldn't it be nice to be immediately alerted if the changes to the simple loop preclude the changes to the Duff version?

That example revolves around equivalence and simple (programmer guided) optimization so it might seem thin. Perhaps another is:

I've some web site code for a large complex site with various complicated functionality available at various APIs. I want to apply a cross-cutting transform to the authentication methods used for various APIs. Regardless of what can be proved about the code itself - which annotations (between the authentication libraries and the protected libraries) are now in conflict? Wouldn't it be nice to both have that result instantly as I make the cross-cutting change (contrast with running a sed script over the code) and wouldn't it be nice to, during code review, have reference to that cross-cutting change as a unit of "the things to be analyzed" along with an automated report of the impact on assertions?

Your message, Srikumar, sounds to my ear like one that says "I worry you're just blowing smoke up our (possibly including your own) butts" and, frankly, I worry about that too since I'm making semi-speculative comments here. I take your "call" here pretty seriously. In that spirit I ask if the above makes you more comfortable or if I've just dug myself into a deeper hole.

Regards,

-t

equivalent changes ...

One set of examples comes from equivalence....

Sure. However the transforms for equivalence that we need to consider here are largely from human interaction perspective rather than, say, optimizations. The replacement of a loop with Duff's device example can be handled by a compiler, for instance.

I've some web site code for a large complex site with various complicated functionality available at various APIs.

Agree with all that and that's why I'm quite intrigued by this idea, but the point I'm concerned about it is that I'm rarely able to effect such cross cutting changes in one sweep. Therefore I'm pondering the intermediate steps and what they might mean.

In that spirit I ask if the above makes you more comfortable or if I've just dug myself into a deeper hole.

Not a deeper hole, but the cliche "the devil is in the details" is quite unavoidable here. There are a few different approaches possible. One is to accept a concrete syntax such as text and have watchdogs that detect groups of changes with specific provable properties. These groups can then be accumulated into the history that you seek and it might be possible to work with the groups as transformation units. For example, consider the series of transformations -

a)x1 + f * (x2 - x1)

b)x1 + f*x2 - x1

c)x1 + f*x2 - f*x1

d)x1 - f*x1 + f*x2

e)x1 *(1-f) + x2*f

a->b and b->c don't preserve equivalence, but the a->b->c group does and so do c->d and d->e. You might even want to split those steps into keystrokes, but it is useful to see this even at this granularity.

Imagine an IDE that highlights the line and all the code influenced by it in red when you make the change a->b ... and turns off the red when you make the b->c (and, of course, keeps the history). That's the kind of aid you're looking for, right?

Now lets complicate it a bit. Equivalence is easy to understand, but what if I want to change the formula to -
x1*(1-f^2) + x2*(f^2)
i.e. change the behaviour of the program? What kind of help do you expect from the IDE in such a case?

Would this be a possible

Would this be a possible approach to explore this area -

If instead of programmers (us) making changes to "the program", we have to write code that makes the changes. Therefore for each change in the history of a program, we have another program that completely captures the essence of the change. All proving efforts can then be directed at the change programs. The change programs can also be abstracted and reused in different contexts.

Of course, that doesn't in any way answer my own questions. Its just a different way to look at the problem.

In some sense, Jonathan

In some sense, Jonathan Edwards' Subtext 2 does some of the transforms you are talking about for you (taking an action on code transforms the representation of the code). Currently, I am working on modularizing Subtext 2 for the Subtext Project fans out (on the mailing list). Jonathan has requested the code be licensed under MIT License (for attribution purposes).

Let me be clear however that I don't think Subtext 2 is suitable for program development. Instead, I want to modularize it so people have a playground for studying programming languages strictly from a usability perspective, using Subtext 2's data model as a somewhat limited backend.

In addition to making it more modular, I will be making it multi-targeted, with support for WPF 3.5 SP1 and Silverlight 3. The idea is really just to target Silverlight 3, as touching-and-feeling gets orders of magnitude more response than a video, just as a video gets orders of magnitude more response than a paper.

Smalltalk

Most versions of Smalltalk implement part of this proposal. The program is stored as whatever the user typed in PLUS an internal representation, and the internal representation is taken as canonical. The user has a choice of representations they can see (usually limited to three: what they typed in, a pretty-printed version of what they typed in, and the internal representation).

As far as I know, Smalltalks don't have a very wide range of transformations they can perform automatically, but they do have some. The best example I know is the refactoring browser, which uses the internal representation to do a range of things like extracting small fuctions from large functions.

Hmm...

Sounds like I've been thinking about things somewhat along the lines of both you and Tom lately. Although it sounds like I've been thinking something closer to your idea.

Me four

Fellow LtU'er Barak Pearlmutter has been invaluable to me in giving me a great idea for how to build a system out of abstract gestures. He pointed out to me the functional programming technique "forward-accumulation mode automatic differentiation". His real contribution to me was giving me a "design pattern" name for something I was doing.

"forward-accumulation mode automatic differentiation" is still verbose, but very clear in its meaning (to me, anyway).

Conal E's notes on AD

beautiful differentiation (presumably if one considers Haskell to be beautiful :-)

Nesting

I should also mention that Barak pounded away at me the importance of allowing nesting. He repeated it like three or four times, which is great because I am thickheaded :)

Also, Barak has a couple of papers on the topic...

how is AD good for gestures?

i am probably failing to expand the definitions and see an overlap / relationship -- any succinct thoughts on how AD is useful there? thanks.

he lost me there, too

-t

Ok...

I'll need either more feedback and/or maybe even more time to think of a good explanation. By the way, I don't want Barak to take any flack for any lack of my ability to communicate. I merely asked Barak about a general technique, and he gave me a general answer. He has no idea what my applications for it are.

Coccinelle

One similar area of work is Coccinelle. They have a "semantic patch" representation, which is used to define a transformation on C code. Mentioned on LtU here.

Coccinelle thanks and comparison

Thank you.

At first skim, that very much looks like the kind of programmed transformation I'd want to see the system I described support.

To draw a distinction, what I'm proposing here on LtU is the notion of changing the formalism of how new languages are defined by doing away with a concrete syntax but adding in visualizations and semi-algebras of gestures over abstract syntax objects -- language design as if tools like Coccinelle were the main way that code got written. The notion of programs as transcripts of gestures opens the door to new kinds of analysis of programs, too, I think.

-t

Syntax all the way down

At the risk of more shameless but hopefully inoffensive self-promotion I'll point you to some discussion here, basically a (constructive) critique of Subtext, which touches on much of the same stuff. "Doing away with concrete syntax" could equally well mean promoting visualisations to the status of concrete syntax (as you allude to in your original post), and then your gestures over these syntactic artefacts become structural deltas which are incrementally interpreted as changes in some other (ultimately syntactic) domain.

you win the "prior work" prize

Thank you for pointing out (via your link) that Edwards quote to me ("use syntactic techniques a visualization in the UI instead of as a representation of the source"). I was aware of some of his work but I suspect now that in what I wrote in the post at the top I was taking more from him than I was aware I was taking. (Now I'll go enjoy your critique.)

-t

distinction from Edwards

I think that the main distinction from Edwards, aside from pragmatics like "use XML", is in the notion of programs as annotated and analyzed transcripts of gestures rather than as live diagrams. A program is its own history rather than its current portrait, so to speak.

-t

Self-versioning documents

I had a feeling (but only from memory of the demo) that Subtext 2 reified user interactions as mutations of a versioned tree structure. In other words the program wasn't just its current state, but a history of how it was built.

Another useful link is Efficient Self-Versioning Documents, although as the title suggests, the focus is on performance. More generally we have fully persistent data structures, and more generally still (and related to incremental computation) retroactive data structures. Apologies if you're already familiar with this stuff.

Subtext programs can be

Subtext programs can be mapped into an XML Infoset data model, certainly. However, you probably do not want to do that, for various reasons... Jonathan hasn't really done any "Flyweight pattern"-style optimizations yet. For those wondering about the design of Subtext 2, just check out the source.

Link update: why syntax

Interaction as meta-programming?

This sounds similar to what I call interactive programming. I see interactive programming as a latent paradigm that lies somewhere at the intersection of incremental computation, dataflow programming and functional debugging. There's some pointers to related work on my website.

A very immature version of the philosophy appears in this OOPSLA 2005 paper, but nonetheless I think you'll find some ideas that resonate with your thoughts. For example we talk of programs being nothing more than the canonical delta that builds them from the null program, etc. Our product never saw the light of day, but the core idea is now the focus of my PhD research.

"Interaction/meta-prog." thanks and reply

Wow! Thanks.

There is indeed (at first skim) apparently considerable overlap.

A possible distinction that comes to mind is this: you are linking programming-by-interaction/transform to a specific class of run-time models (e.g., defined values that are automatically updated upon changes in depended-upon values). I am talking in way meant to be independent of a particular execution semantics. That is, you are talking about transforms on a flow graph while I'm talking more generally about transforms on abstract syntax objects.

I am looking forward to digging more into the paper and learning more from your thesis. I think it's interesting the way your stuff, what I'm talking about, and what Edwards talks about, and quite a few other research directions have a kind of eerie resonance among them even though it's (at least initially) unclear how to resolve the distinctions and incongruities between them. It's that "we're all onto *something* but it isn't clear *what*" feeling / hunch.

-t

Synchronisation continuum

Re. the distinction, ok (although that paper is old :) Maybe you can think of automatic vs. batch update as just two ends of a synchronisation continuum: i.e. of both really as instances of the same computational model. (Disconnection is really just connection with unbounded latency.) What I find exciting is the possibility of building a new computational substrate where state synchronisation is automatic (although perhaps only eventual) - a law of computational physics.

As for eerie resonance: indeed. I guess that's why I tend to think of it as a latent paradigm: it has its roots at least as far back as the early dataflow/visual/spreadsheet languages, and there seems to be convergence on it from a number of other quarters, incremental computation being one. It strikes me as a much more radical shift than say procedural to OO, or OO to functional: the shift from algorithmic to interactive.

re "sync cont" - just separate concerns

Just be aware that you can talk about gestures without implying anything about run-time system or execution model (and I hypothesize it is useful to do so), is all I ask.

-t

Actually, gestures are

Actually, gestures are independent and it makes sense to think of them as separate from the basis set of a language, in much the same way that a DBMS could also include a "rule engine", but it makes much better sense to logically -- and physically -- seprarate the two.

At the physical level, this is basically an understudied and underappreciated performance optimization technique IBM invented that is called "wait-based performance tuning", althuogh it is also indirectly described in at least one RFC and the famous End-to-end arguments in Systems Designpaper by Saltzer et al.

Good methodology

Ok, I see your point. Identifying programs with their canonical deltas from the null term (essentially an algebraic perspective) might be useful independently of whether you want to interpret those deltas.

Basic feedback for Tom/Roly/others

I basically agree with Tom's summary.

I mentioned in my thread a few weeks back about Literate Programming and the need to escape from Web - Tangle - Weave.

What you propose above, and what Roly is working on, is approximately what I had in mind. Actually, Roly was an inspiration in this stuff and so is Jonathan Edwards. Other inspirations include Jeremy Siek and Walid Taha's work on gradual typing as well as Taha and Tim Sheard's work on multi-stage programming. Sean McDirmid's work on "live languages" is also relevant (for me). CJ Date, with his firm advocacy of semantic optimization, is another inspiration. There are others I am ignoring at the moment, mainly because I am not sure how to categorize their contributions.

Literate Programming was chosen by me as a pilot study for eliminating syntax completely, because in many ways Literate Programming is the forefather of the concepts important here. Except, LP doesn't have a mathematical foundation.

Basically, unifying all of these things would make my head spin much less, so I see immense value in that for me. I cannot handle too many cool ideas, but I can generally master one big idea. I have a rather boring blog post about My Re-thinking of Literate Programming, where I start to look at the situation at a high-level.

Mergeable with David Durand's Palimpsest

This view of documents as a stream of changes would play well together with David Durand's work on Palimpsest (full dissertation). Palimpsest models the change operations of insert, delete, move, and copy and specifies how to generate a document based on the application of an arbitrary set of change operations to produce a deterministic and (when possible) coherent result. The change operations need not be sequential, which makes Palimpsest a potential underlying model for change-centric (as opposed to revision-centric) source control.

Palimpsest applies to a linear sequence of segments (lines, characters, slides) rather than a tree, but I think it would be easy to adjust the model appropriately. This table (which is my work, and for which Durand is not responsible, compactly states how change conflicts are resolved in Palimpsest; it does not explain Palimpsest's unique version-independent addressing scheme.

Nice connection

I appreciate it. I also saw Kay Schluehr use the palimpsest metaphor here on LtU not too long ago.

Another connection would be Viewpoints Research Institute's work on Parseable Expression Grammars (PEGs). They've been working on breakthroughs in PEG-based parsing technology, and believe PEGs will in the long run be superior to GLRs. (In fact, for this reason among perhaps many, VPRI doesn't seem too enamored with Microsoft Oslo, which uses a GLR parser.) However, currently, PEGs do not support indirect left recursion (a practical limitation that leads to some considerable implementation complexity, especially when combining DSLs). Note, however, that VPRI is most likely working on this problem, since they were the ones who showed a technique for supporting direct left recursion - proving left recursion is in fact possible.

The big idea, although not really widely demonstrated or publicly acknowledged, I believe, is to show how to use PEGs to remove concrete syntax from programming. If successful, this has all sorts of implications. Most notably, the difficulty in combining DSLs in a way that supports "configurable modularity".

Yes, but what is the abstract syntax?

I agree that your perspective opens up a new space of language designs. But it is easier said than done. I have been struggling with it for years. Gestures and visualizations will only be comprehensible if they are based on a simple underlying data model. Strings are such a model. What is your alternative proposal? Language design is really hard - it is a balancing act between many conflicting goals. Our current bag of textual conventions occupy a sweet spot that has taken 50 years to settle. It is not easy to come up with an alternative that immediately and obviously beats those 50 years of refinement. In my experience, no one will pay any attention otherwise.

Barriers to entry and exit

Our current bag of textual conventions occupy a sweet spot that has taken 50 years to settle.

Besides how long it's taken to settle, there's also the question of how long it takes to repurpose to new languages and environments, and how well it supports arbitrary tools developed by people who didn't have to spend months learning how to integrate with a complex development environment, or pay for an SDK, etc.

Text is agnostic about concrete syntax, abstract syntax, and of course semantics. Its low barrier to entry limits what you can practically do with it in some ways, but also limits what you can easily replace it with.

history needn't impede new ideas ..

I'd say the problems and triumphs of text-based languages needn't impede thinking about ideas such as this one. The idea seems interesting, appealing and potentially applicable, albeit in a restricted form, to text-based languages as well.

For me, though, it needs details and examples. Given that the problem being solved by a program will change with every transformation (otherwise there is technically no need for the change), I can't help wonder what kinds of proofs will be applicable.

t

I don't have anything much to argue against in or (at the moment) to add to the ancestor comments of this sub-thread (for the record, in case someone was expecting a reply).

Thank you each,

-t

What arbitrary tools do you use today?

I like your objection, but details, details, details.

In my experience, languages and environments that require me to use a lot of arbitrary tools are in many ways the result of improper language and library design.

Even then, the tools I use, like RedGate SQL Toolbelt, are hardly arbitrary but the work of some deliberate thinking. RDBMSs have to be the most non-arbitrary data model supported by the most arbitrary languages imaginable. In response to arbitrary languages, I use more non-arbitrary tools. And it is the non-arbitrary tools on a platform that make it worth using.

What I mean by "arbitrary"

What I mean by "arbitrary" in this context is that they're not part of the language developer's standard SDK or of a standard toolchain for a particular language. They also often weren't originally written specifically for the languages they're used on.

I'd say that Emacs and Vim qualify as arbitrary tools, as do grep and ctags and countless other tools that people use on source code in all sorts of languages, and across languages and platforms, all the time. Not to mention custom tools that people write themselves to generate or transform code.

My comment wasn't so much an objection as an extension to one of Jonathan's points about why replacing the current textual conventions is "easier said than done". For an attempt in this area to really succeed, it has to be able to address such points somehow.

I agree with Srikumar that this shouldn't impede thinking about such ideas, but I was really just responding on that specific point of Jonathan's.

I understood what you meant,

I understood what you meant, but I think that there is a barrier between entertaining these ideas and actually discussing them on a What needs to get done? level.

For instance, I am usually very frustrated but have long since accepted the fact that SQL makes me type a lot. Where I can, I use concept-based query languages instead that map into SQL instructions.

I've long wanted to write something substantial about this, since I feel I understand intuitively what things need to be solved, yet I'm very skeptical of any place caring to publish it. I also think it is taboo for a practitioner to publish a position paper, as it seems like an unwritten rule in computer science that a position paper leads to more published papers.

Maybe LtU could use a language subforum devoted specifically to language usability studies/how human factors research can educate good language design; there are a fair amount of LtU'ers I talk to who after getting their Ph.D. in PLT moved on things closer to human factors. (Concept-based query languages are a good example of human factors research; a long time ago Elmsari and Navathe showed the tremendous productivity benefits over traditional data access sublanguages like SQL).

Edit: Also, I agree, Emacs is the killer arbitrary app aside from "perl -e RSAEncryptedCode".

hear hear

+1 for the general theme of "language usability studies/how human factors research can educate good language design"

Usability isn't even in the

Usability isn't even in the LtU taxonomy list of things moderators can tag forum discussion with. The ugly truth is such discussion is secondary to mathematical elegance and implementation elegance. (Not criticizing, just wondering if Usability is even appropriate to discuss here.)

Emphasis on model

Strings can be called an underlying data model, but most programs are a few large strings roped together by a Build/Link/Load tool.

The problem is waiting until Build to rope together strings. As an example, batch compilers, for throughput performance reasons, are fundamentally differently designed from interactive compilers. IDEs today build separate tools to improve interactive experience, but even the IDE itself fails to capture a lot of rich semantic detail. Finally, because our IDEs struggle with strings so much, we have Byte Code Engineering Libraries (BCELs) that weave code declarations into the source code during the Build process. We're continuously destroying and building a data model, so it is somewhat of a mistake to say strings are today's model. We lack a stable data model. We need to start thinking about modular program construction that makes invisible Build/Link/Load and other batch optimizations like Web/Tangle/Weave.

Build Dependence, Link Dependence, and Load Dependence all must fade away for a stable data model to emerge.

SVG as the ASCII for graphical languages?

I could imagine something like SVG becoming a basis for graphical languages in the future, occupying the same niche that strings do for current programming languages - as a common data format that syntax rules can be constructed over.

SVG editors of the moment would be analogous to "dumb" text editors like notepad, in that they could be used to create programs in an arbitrary graphical language but don't provide any special features for it. One could then imagine various editors springing up which provide richer features for graphical programming (equivalents of Vim, Emacs, Eclipse, et al.).

BTW Jonathan - quite impressed with what I've seen of Subtext so far!

Been working on something similar

I came to similar conclusions as the OP while using git a while back. I've in the early stages of bootstrapping a little project, and my current direction on the structure editor is that it needs to behave pretty much like a regular text editor (even though it will be rendered in OpenGL). I completely agree with you that an evolutionary move away from concrete syntax will have to adhere to existing convention otherwise.

As for the underlying data model, after discarding general graphs due to intractability, the data format has evolved to a simple system where each component contains a tree of atoms. Atoms are either basic datatypes or references to other atoms. Components form a DAG much like in git. Though the data format is text-based for now, there's no hope for a human to edit the data by hand anyway; my aim is to have the node viewer/editor as robust and intuitive as a modern text editor. Once again you are correct: that is a hard problem.

Re: representation (i jest)

i'd like to make a gui e.g. dataflow language ide and then have it all actually rendered in ascii mode a la ascii doom

Been done (sort of)

John Dunn's Music Box was an early Max-MSP precursor that ran on MS-DOS. The implementation, in x86 assembler, was released to the public domain in 1986. It drew all of its fairly inscrutable graphics on a 16 color 24x80 character display.

Like Max it was a dataflow system modeled on the large analog music synthesizers of the late 1960s and early '70s. Unlike Max, it was synchronous: instead of nodes firing on input changes, all nodes fired on every tick of the MIDI clock.

The Programmer in the Language

My recent language design experiences seem to have paralleled some of Thomas Lord's ideas.

I've been developing an arrowized reactive model of a nature similar to FRP (RDP diverges from FRP with respect to state, effects, resources). I have always felt that tacit programming would be a good fit for arrowized models, and (being unable to settle on a syntax) I chose to pursue a tacit model. Initially, I thought it would be an intermediate and distribution language, but it grew on me very quickly. I loved the minimal syntax and boiler plate, the ability to get right to the code.

Anyhow, one weakness of tacit programming is that a lot of 'data plumbing' becomes explicit words and functions. FORTH had pick, roll, over, and other operations. With my arrowized model, I developed similar operations, albeit operating in the type system instead of on runtime values.

This will be important: Tacitly manipulating a statically typed environment is a very different programming experience than manipulating a runtime stack. The 'values' in this stack are the types in the underlying arrow. In my case, developers would often be manipulating time-varying signals; such 'runtime' values cannot directly be observed. Since the "shape" of the environment is static; it can easily be envisioned by a programmer. Further, we don't need to rely on a good programmer imaginations: the shape of the environment can be continuously rendered by an IDE. By probing different locations within the program, one could find different shapes, or even animate the transitions between them.

Anyhow, after writing a few pages of code to get a feel for my new tacit language, I quickly realized a problem: Operating on a single stack is painfully cramped when I have complicated dataflows. A single stack works great for a relatively sequential workflow. But in practice, I often want multiple parallel pipelines - representing different tasks - with occasional scatter/gather integration.

So I changed the environment. And this is where it starts getting closer to Thomas Lord's ideas. Some of the changes:

  • Instead of a single stack, I model multiple stacks. Programmers have a "list" of stacks. They can navigate this list: stepLeft and stepRight. They can create a new stack to their right, or destroy an empty stack to their right. The normal stack operations now manipulate the 'current' stack, and literals are added to the current stack. (In the type system, the list is modeled as a heterogeneous list zipper.)
  • To provide an effective means to integrate work between stacks, I model a programmer's "hand" - a stack that they carry with them as they step left or right. They can 'take' objects into this hand, or 'put' objects from this hand, and also 'juggle' a few objects - which is basically like 'roll' but applies to the hand instead. The hand serves a similar role to a clipboard in a more traditional UI.
  • I also added simple static introspection and choice to the language, i.e. words can inspect some types and static values. This allows me to model keyword arguments, extensible records, and 'named stacks' that can serve a similar role to variables. The programmer has a second 'hand' just to carry environment extensions based on introspection.

As I developed in this direction, I noticed how closely my programming model parallels a user interface or IDE. Programmers are, in a sense, manipulating an avatar within the program that edits the program. It would even be feasible to render the multi-stack environment to screen, and animate a little data-plumber in a red hat stepping back and forth between the stacks to pick things up, move them around, and combine them. Given such a visualization, I can imagine programming with a gamepad.

The step from what I've developed to supporting Thomas Lord's vision is a simple one: metaprogramming. Gestures are essentially 'words' in a tacit language that construct a program. They can - literally and effectively - be modeled as words in a tacit programming language. Assuming, of course, that the tacit model has a sufficiently rich environment and model for programmer location, carried objects, and other context.

The metaprogramming aspect requires that, instead of runtime-varying signals, the stacks and inventories primarily carry first-class blocks of code and other static values. In my language, blocks are opaque, so developers might wish to model higher-level 'block constructors' that remain open to introspection, partial decomposition, copies, re-editing, and re-configuration.

(Note: I wonder whether some form of mixed-level programming might be a sweet spot. I.e. where the IDE encourages rich metaprogramming, but developers can also "hard-wire" specific resources and signals into otherwise reusable components.)

Anyhow, the "output type" of the tacit arrowized program now holds the place of what we traditionally consider to be "the program". However, developers would also be able to view the sequence of words that constructed the program - the edit history. And they might edit it. In practice, such edits can break some of what they have written since, but those would show up easily in both views: e.g. highlight problem type, highlight the problem words that lead to it.

There would be a lot of power in having a formal, strongly typed, first-class language and editing environment.

In such an environment, programmers would systematically create more 'robust' editing words, i.e. leveraging introspection and stable identifiers. Further, IDEs could provide some support or guidance on repairs based on type-matching. And real-time rewrite rules could recognize common sequences of "low level" operations and automatically translate them into more robust, higher level gestures - a kind of event recognition, easily made visible to programmers.

Arrows aren't essential for this, but I think they might be a sweet spot: Arrows are expressive enough for rich computation, environment, and programmer models. (I actually scaled back from "tree zipper of trees" to "list zipper of stacks" because the former was expressive enough to get eaten by a grue.) But arrows are also rigid enough to support effective visualization, and enforce a critical separation of static program structure from runtime values.