Lambda the Ultimate

Ok, then.

I think you should search the archives for discussions of visual programing languages and 2D languages. Both terms appeared quite a bit in the first couple of years.

EBNF is (occasionally) good for specification of syntax, not semantics.

Most 'visual' languages are actually variants of data flow ones. Take a look at Ptolemy II, a modeling environment for them -- they provide a nice IDE / libraries / layering scheme for plugging in your own semantics. Peter van Roy's book CTM might help you a little, but he mostly focuses on assign once variables, not really live variables. As for languages used in the wild, labview and Max's patcher system are dominant.

Beyond those, look at kahn processes, clock calculus, frp, and some of walid taha's recent work in tying lambda calculus into it all. Some 'live' programming systems like superglue and subtext were formally specified as well.

The most common approach I'm aware of for specifying visual language syntax is metamodeling. The OMG defines UML syntax via a (somewhat self-referential) metamodel. Vanderbilt's Generic Modeling Environment allows new visual languages to be specified by constructing a model of the syntax using a mix of UML and OCL. DOME, originally developed at Honeywell, seems to use a similar approach (although a different notation). Granted, the metamodels focus more on abstract syntax than concrete syntax (although the AST definition can usually be annotated with information about concrete representations). But then it's not clear to me from your question which aspect you're most interested in.

See my other comment below. I will look into these but I am initially doubtful that they are really akin to EBNF. I think I've been down that path before (metamodeling) and felt like it wasn't at a high enough level of abstraction and formalization for what I want but I will look again thank you.

Syntax in two dimensions is really tricky. I think the main 2d programming systems that get used for practical purposes are all data-flow systems (e.g. LabView, Max/msp, pd, Slim, Houdini's graphical geometry notation, TouchDesigner, Shake and nxt-g (the Lego Mindstorms programming system)). All of these use the obvious boxes-and-lines notation. The first Lego Mindstorms system, no longer available, was not a data-flow language, and used a notation that looked a lot like pictures of ASTs. So in all cases, the syntax is trivial.

That's because (he avers, reading multiple minds simultaneously) the existing formalisms for dealing with 2d syntax are all completely unusable. There's been a lot of work on graph, tree and picture grammars over the last 35 or 40 years, but it's only a mild exaggeration to say that no two papers use the same formalism. And most of the results say that anything interesting is uncomputable. (If you're lucky the interesting things are only P-space complete.) The notable exception is L-systems, which are widely used to model growth and morphology of plants, and have a rich theory and lots of interesting applications. But L-systems aren't really 2d grammars (i.e. they don't generate 2 dimensional structures directly), but (parallel) string grammars with geometric interpretation rules to convert to 2d pictures. Even so, I believe the parsing problem for L-systems is Turing-complete in general.

None of these systems save programs as pictures. They all use the underlying graph or tree structure with some annotations indicating where to put them on the screen, bypassing the parsing problem. On the other hand, there's a fair number of hardware design systems whose native representation is geometric (circuit diagrams or even raw integrated circuit masks), and that do something a lot like parsing of the drawings to extract circuit graphs. (But again, hardware has dataflow semantics, so the extracted representations are again boxes-and-lines.)

Thanks very much for your answer. And thank you to everyone else for responding as well.

Re: storage, the usefulness of formal common syntax definitions is not necessarily dependent upon the final storage format.

Re: computability for parsing, the systems I envision would not necessarily parse visual programs in the traditional sense. I was thinking of using this non-existent syntax definition form as a starting point for brainstorming the implementation of an application that would leverage GUI functionality to reduce or eliminate the (initial) parsing step.

My motivation for starting this topic is the idea that 2d representations of formulas, tables, circuits, domain objects, data, spreadsheets, ontologies, entity models, UML, algorithms, etc. are necessary and that having a standard metasyntax notation that could specify syntax for some or all of these things might bring some of the benefits that EBNF (or similar formalisms) brought to textual computer languages. I see the response on metamodeling which I must now investigate further but I have a feeling these are all variations on boxes and lines (might be a good place to start but different scope/approach I believe and I think they are relying heavily on natural language descriptions of diagram features in a diverse and somewhat ad hoc way).

I guess the idea is that I want my programming language to allow, for one example, simple embedded equations in a more natural readable way without having to serialize them to text but there is no common formal approach to the definition of this syntax. Everything up until that part I could clearly explain the syntax of with EBNF for example but by virtue of the fact that I want some text above the bar and some below it (as a representation of a numerator and denominator for example), the entire formalism and related tool support breaks down.

I think I see where you're trying to get to now. It sounds like a worthwhile goal. Unfortunately, I'm afraid that based on what you're trying to do (which involves concrete as much as abstract syntax) that metamodels probably won't help you that much. It sounds like you're looking for something like a mix of a graph grammar (e.g. Hyperedge Replacement Grammars) and a layout language (e.g. TeX or CSS). I'm not sure if anything like that exists. I'm pretty sure there's nothing like it that's "mainstream" or "standard" in the way that EBNF has become. Might make a neat research project for some eager PhD student though...

There's a long history into parsing graph and picture representations, and if the theory is not as well developed as for sequences of characters, there's lot that is known. In particular, many attempts to represent the Chomksy hierarchy for graph grammars have been made, cf. the survey (GR 1999).

(Scarpazzi 2004) gives an interesting technique in a grammar that can reasonably be called context free, which gives a kind of picture grammar represented by tile rewriting. I don't think the technique is, as it stands, general enough to stand as a theoretical foundation for visual languages, but I think that picture grammars which can be parsed by applying a set of picture productions in reverse do provide the most promising foundation for visual languages; if this result can be appropriately extended.

Giammarresi & Restivo (1999). Extending formal languages hierarchies to higher dimensions. In ACM Computing Surveys 31.
Scarpazzi (2004). A Parsing Technique for Tile Rewriting Picture Grammars. Tech. report. Politechnico di Milano, Dipar timento di Elettronica e Informazione, 2004.11.

To give some details, the textual syntax of Faust is based on an algebra of five operations on block-diagrams ( : , <: :> ~ ). For example a one-pole filter (corresponding to the difference equation y(n) = x(n)+k*y(n-1)) can be written in Faust + ~ *(k) using the recursive composition operator ~ that allows to create block-diagrams with cycles.

A description of the algebra can be found here : http://www.grame.fr/pub/faust-soft-computing.pdf

Another formalism is Gheorghe Stefanescu's algebra of flownomials : http://www4.in.tum.de/publ/papers/TUM-I9437.pdf

Thanks this is exactly the type of thing I was asking about (although obviously no standard). The block diagrams in Faust are along the type I imagined previously to correspond to similar representations and Faust follows a semantic compilation approach that is probably a pretty useful approach in general to VPLs and the type of thing I was thinking of. Flownomials sounds like it could be very useful as a tool for analyzing data flow languages.. but looking at that and taking a step back on the whole topic,

I have been starting to think that maybe rather than looking at academic formalisms I just want to go straight to devising a user interface that would allow users to enter new notations or diagram/graphic types etc. by pulling from a set of primitives and/or relating to previously defined notations and then translating to terms from some semantic representation or to code. Either that or break down graphical features and dimensions into some set of functions that are composed (maybe visually represented with just some ordinary data flow or some variation, or something inspired by Eros) and use that as a base level.. but the goal is to try to make most manipulation and display use representations that are closest or most natural/convenient and to be able to mix them and then generate (high (or low) level) code.

nice