Tuesday, March 22, 2005

Abstract syntax isn't?

Abstract syntax is so called because it eliminates the elements of syntactic sugar that are irrelevant to the meaning of an expression. For example, in the following expression:
let x = 2 in (x + 3) end
the = symbol has no informational content; it's only there for legibility. So an AST is more abstract than a concrete syntax in the sense that it strips out details that are irrelevant to the meaning of a program.

But in another sense, abstract syntax is less abstract than so-called concrete syntax: in meta-programming, for example, when we write programs that pattern match on the surface syntax, we treat the surface syntax as the interface to the AST, and our code is oblivious to the particular representation of the code. As I have pointed out before, pattern matching is more abstract than code with explicit selectors.

I'm surprised out how infrequently the software engineering papers I read talk explicitly about abstraction. Bravenboer and Visser have written a couple of papers on embedding languages with concrete syntax. I like their work, and it might strengthen their point to discuss the notion of concrete syntax as an interface for the AST representation.

S-expressions are a sweet spot in these two aspects of the abstractness of syntax: there is very little syntactic sugar, so going from the surface syntax of a Lisp or Scheme program to an AST is trivial; on the other hand, macros can operate by pattern matching directly on surface syntax and splicing back into templates written in surface syntax. In a sense, it's a pun between object- and meta-language. But it allows for very powerful macros. Otherwise, when your surface syntax distinguishes similar types of expressions, you have to write multiple, near-identical macros to operate on the different forms.

No comments: