Lambda the Ultimate

Noted. Sorry about that.

-t

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 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.

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, 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?

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

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)

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...

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

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.

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". :)

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 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.

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"?

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

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 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 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.

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.

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.

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).

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

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...

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

-t

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.

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

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.

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

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

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 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 won't go away.

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

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.

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 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.

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.

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".

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.

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.

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

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" 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, 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".

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

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.)

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.

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!

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.

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

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.