Thursday, April 5, 2012

Fear and Loathing at the Lisp Syntax-Semantics Interface

You poor fool! Wait till you see those goddamn parentheses.

Recent investigations of xonses and first-class patterns have driven home an important point:

Part of Lisp's success stems from its heavy use of puns.

Take (LET ((X 1) (Y 2)) (+ X Y)) for example. The pun here is that the same syntactic device - parentheses - is used to express two wildly different things: calls to the LET and + combiners on the one hand, and a list of bindings on the other.

Let's step back from Lisp's typewriter-based syntax for a moment, and imagine a graphical 2D syntax and a convenient 2Dmacs hypercode editor. Since we're now fully graphic, fully visual, it makes little sense to construct lists. We construct real widgets. So we would have one widget for "list of bindings" and all kinds of snazzy displays and keyboard shortcuts for working with that particular kind of form.

We don't have that editor yet, but still it makes sense to think about first-class forms. Right now, we restrict ourselves to lists and atoms. But why shouldn't the list of bindings of a LET be a special form, with a special API? E.g. we could write (LET [bindings [binding X 1] [binding Y 2]] (+ X Y)). Of course this is horrible. But look back at the imaginary 2D editor again. There we wouldn't have to write the [bindings [binding ... stuff. We would be manipulating a first-class form, a special GUI widget for manipulating a list of bindings...


John Shutt said...

I agree and disagree. :-) Here's how I'd put it.

There are no syntactic puns here, and no syntax-semantics interface. For about as long as I've known Lisp, I've heard "Lisp has no syntax". I didn't fully grok what the saying meant until pretty recently. Lisp semantics has no syntax. Lisp has syntax to express data, but no syntax at all to express semantics. It's true that data is being used, through the evaluator algorithm, to represent both the combiner calls and their operands (such as let bindings), but that's not syntax (so, no syntactic puns). The syntax is already gone before anything interfaces with the semantics.

I do agree that the success of Lisp depends quite heavily on the fact that it has no syntax dedicated to semantics. But this means that, to the extent that a language introduces syntax dedicated to semantics, to just that extent the language becomes less Lisp.

Manuel Simoni said...

I think I'm using a wider definition of syntax - to me the data passed to the evaluator still has (or is?) syntax.

What the evaluator does is effectively parse the data passed to it (e.g. extract the operator of a compound form and evaluate it.)

But I'll have to meditate more on your "Lisp semantics has no syntax".

Arcane Sentiment said...

Instead of “syntax”, how about “structure” for the AST, and “skin” for its textual (or graphical) representation?

I think structure editors are a red herring here. They only replace the skin; the structure remains the same, and it's the important part.

"Lisp semantics has no syntax" isn't a profound concept; it's a simple matter of modularity. Lisp keeps its skin separate from its structure and its semantics, so they don't complicate each other. The skin doesn't have special cases for each special form (with a few exceptions, like quote and backquote), and the structure doesn't have a different representation for each semantic feature (except symbols and literals). If the structure distinguished special forms from function calls from non-form lists, it would be more complex, and it would take a large benefit to be worth complicating the heart of the language.

(I sometimes wish funcalls, special forms, and nonform lists had different skins, but this wish is based more on aesthetics and a desire for theoretical clarity than on any practical problem.)