Lambda the Ultimate

I suppose in a strict, effectful language it makes sense to say that macros are a form of 'extensible syntax', but I tend to favor languages where that role (of behavior-pattern abstraction) is fulfilled by pure functions.

My working definition of 'extensible syntax' involves a developer's ability to influence the parser and parse-tree structure. (I assume the parser subsumes any need for a lexer.) I wouldn't usually count Lisp macros (except for reader macros, which are almost never used). Expressive DSLs will often have their own parse structure.

Rather than extensible syntax, I now favor a syntax per module design. Modularity has a lot to do with this decision.

Unfair of me to allude to "extensible syntax of a sort" without explaining what sort of beast I'm picturing. If one has always thought of syntax extension in terms of extending the set of possible parse trees, it may not be clear how one can do something that qualifies as syntax extension while preserving what my techreport called cumulativity.

The basic technique is simple: start with an unambiguous CFG that defines the set of possible parse trees, and then treat individual grammar rules within that structure just the way most programming languages treat identifiers — as structures that may or may not be bound. This supports the syntax-represents-data approach of Lisp, preventing syntax from being entangled with behavioral issues.

The arrangement of this sort I particularly have in mind to try out, to see how well it works in practice, distinguishes two scales of syntax. Larger-scale syntax (spanning more than one logical line, but within a single source file) would use linebreaks, indentation, and demarcational pseudo-statements (generalizing begin/end). Small-scale syntax, i.e., within a logical line, would be almost-fully-parenthesized; each expression would be generated by a grammar rule whose right-hand side alternates between keywords (terminals) and subexpressions (nonterminals). The pattern of keywords and subexpressions would be the bindable syntactic structure. Some reasonably simple scanning rules can provide, I think, a readable and quite versatile notation, in which the first two tokens of an expression always suffice to determine whether the keywords are the odd elements of the expression, or the even elements. (Anyway, that's the gist of it, hopefully giving a sense of the sort of thing I mean.)

I see, you're constraining how grammars are extended such that developers can at least have some familiar meta-structure.

Your proposed model (alternating keywords and actions) is powerful enough for most of what people need (e.g. developer preference of 'Action if Condition else Action' vs. 'if Condition then Action else Action', support for both postfix and prefix operators, etc.).

I suspect it would run into hiccups for other tasks, though, such as capturing regular expressions, or compact APL-like collections processor functions, or other compact DSLs. It would be 'interesting' to support analog literals. And I would sort of like to support interactive fiction, e.g. via near Inform 7 like program text, or more 'markup' styles of programming where display data is the primary element for a region or module.

I'm not too sure there would really be a problem, once one had all the details worked out. I would expect, for example, that expressions (foo 5) and (** foo) would be unambiguously prefix notation, while (5 foo) and (foo **) would be unambiguously postfix notation. If there were a practical problem with regular expressions, I suspect it would be caused by the depth of nested parentheses.

We're both guessing, of course. Which is why I want to set up a working implementation: I don't know, and there's no substitute for working examples.

Where I refer to APL and regular expressions, I'm aiming to connote the compact, concise formula for disproportionately rich (but domain-specific) behaviors. By 'hiccups' I mean I doubt you can conveniently build these compact, concise forms.

For example, let's have a regular expression to match dates of the form yyyy-mm-dd for the 20th and 21st centuries:

(19|20)[0-9][0-9]-(0[1-9]|1[012])-(0[1-9]|[12][0-9]|3[01])

This is something a developer could create after a brief intro to regular expressions, but adding it to your language may require a rather significant adjustment to the parser for a region of code. My intuition is that the extra keywords, spaces, and parentheses would turn this one-liner into a grand sprawl.

That said, you might also encounter some prefix/postfix hiccups. (foo bar) isn't very clear.

Whether one can define that regular-expression notation depends on subtleties of the syntax mechanism. Starting with how the input stream is tokenized. I don't pretend to have every detail worked out; I like that example, for the questions it raises about just how those details ought to work.

The case of (foo bar), I had noticed, yes. The simplest solution is to disallow it: require that something occur in the first two tokens of the expression that disambiguates which of the first two elements is terminal. The way to do that for (foo bar) is to parenthesize one or the other element, forcing it to become a subepxression:  (foo (bar))  or  ((foo) bar).

if a language system had s-exprs as the basic core for humans, but then layered algolish or m-exprs or whatever on top for humans which then presumably gets translated into s-exprs, could one still let the macros be written in s-expr form so they are easy to write, but still work with the m-exprs because those m's get turned into s's where the macros work?

Boo is a statically-inferred language for the CLR which happens to look like Python. It has a macro system which manipulates the AST directly.

Generally, languages with 'conventional syntax' are an interesting problem for syntax extensions.

Metalua has special escapes for AST literals which makes it less code-heavy:

X = +{ 2 + 2 }  -- put AST of '2 + 2' in X
Y = +{ four = -{ X } } -- make the AST for four = 2 + 2

But yes, it is perfectly possible for such a language to encode the macros as S-exprs; it's just that this notation is more natural for users of the language.

However, I'm noticing a distinctive lack of anything suggesting that anyone has actually studied the effect of syntax or syntax extensibility, specifically, on programmer productivity.

Cognitive dimension research on C#

I doubt you'll find much research in general on syntax traits or other abstractions. It's hard enough to draw conclusions on wholly formed concrete implementations.

There may have been a study with at least some of the properties you're asking for. With actual programmers actually programming on an actual working implementation of an extensible development environment. If there has been, methinks it would have been with the ECL programming environment, back in the 1970s. For all I know, ECL may still be the most complete concrete extensible programming environment ever implemented. Because ECL was so long ago, digging up such a study could take nontrivial library research (at a really good academic library; if I were going after it, I'd probably arrange a day trip to MIT); it's not overwhelmingly likely to be freely (or maybe at all) available on the web.

It is clear that syntax extension mechanisms, used tastelessly or clumsily, can create code whose wretched awfulness transcends what is otherwise possible.

This is the mark of any programming language feature that can do great things, isn't it, that its linguistic goodness can also be used for evil?

Indeed. Since RMS is a well known lover of Lisp, it would be nice if Ray would edit his post to rectify the issue; we don't want to start any rumors on these here internets. ;-)

The attribution to RMS surprised me but RMS, the iconoclast that he is, frequently says surprising and provocative things so I just thought it lacked context.

Surprising, yes, provocative, yes, but pretty consistent.

All nontrivial programming is incremental development of new programming languages. I've found this a basic concept that naturally arises when one starts really focusing on abstraction as a general principle; at any rate, it can be found in the early abstraction writings of the 1970s, I quickly arrived at it when I started looking at abstraction in the late 1980s, and I subsequently found Henning Christiansen had independently gotten there around the same time as I — his dissertation on adaptive grammars was titled "Programming as Language Development".

Some extension mechanisms only work well in the hands of an expert. This has been recognized for decades; Thomas Standish observed it about macro-based extensible languages in 1975 (Sigplan Notices, July). It doesn't follow that all extension mechanisms are that hard to use.

This is what I hope for in my 'structured syntax extension' device: programmers don't find it too difficult to deal with defining new symbols, so I'm thinking if one arranges more general notations in a straightfoward enough way, programmers shouldn't find it too difficult to deal with defining those either.

I've found the view that programming is language creation to be very useful myself. Programming languages have a basic language predefined but the really powerful part is their role as a meta-language for extending the built-in concepts with new ones more appropriate for the problem domain.

The problem that would generally arise would be people creating and using clever syntax too early making the semantics of expressions very opaque to people unfamiliar with the abstractions. Balancing conciseness with clarity is tough to do well but I suspect there are real productivity gains to be had if done right.

Add multiple extensions from people with different visions and you have the ultimate mad language forking tool.

Is this necessarily a bad thing?

I mean let's assume that we have something like John Shutt describes earlier, where there's some elemental grammar that defines tokenization and generally provides a core for developers to work off. One of the great strengths then of a language with extensible syntax is the creation of DSLs. I wouldn't really expect DSLs to exactly harmonize with others, but if the core language allows you to mix and match DSLs for your particular domains that seems like it would be a big win.

Even for things that would more properly be considered separate languages, they probably didn't get their overnight. If programmers' needs or preferences drive a particular variant that hard, isn't that useful in and of itself? Having an environment that allows languages to evolve and fork over time (like natural languages do) while maintaining some level of interoperability would be an interesting experiment if nothing else.

But then the DSL design means that you have defined a predictable environment.

The issue is that extensions can not generally be composed. You get fighting grammars ;) So I like what John Shutt says about extensions being a per-module thing.

And totally true, making extension easy pushes language design forward.

You're right, of course.

But I don't think I quite understand why this was considered to be a desirable design decision.

It's clear from r3rs that the main problem with rebinding keywords was to do with the semantics of special forms. Once a principled semantics of macros was fixed, and special forms could be defined in terms of them, then this objection evaporates, hence the change with r5rs. This makes the "little languages" approach more flexible.

It's a bit hard to see the IEEE approving a Scheme that allows such rebinding, though.

While I'm talking about r3rs and keywords, the r3rs standard's Texinfo source has the following, intriguing commented-out text:

@ignore todo
The Miller vs. Dybvig debate over reserving new keywords. What to
do?
@end ignore

I assume this Miller is the Jim Miller of Multischeme fame. I'm curious as to what the debate was about.

A principled semantics of macros made it possible to define special forms in terms of macros. I do not believe that it therefore follows that those definitions ought to be mutable or capable of being shadowed by local definitions.

These are separate questions. I would have argued in favor of introducing immutable and "luminous" (unshadowable) items, even if only for syntactic bindings, to the language in order to allow the definition of special forms.

It has always been true in Scheme that there are no reserved value identifiers (variables); one can locally rebind cons or list or < without problem, and in certain contexts this is good style — for example, defining a list-sorting function with two formal parameters named list and < actually contributes to readability.

As long as the list of Scheme syntax keywords was fixed, it was plausible to reserve them, but with extensible syntax, treating syntax keywords and variables uniformly makes sense to me. It's less likely that you'd locally redefine if than < (an instance of Quine's "maxim of minimum mutilation"), but neither seems inconceivable.