Lambda the Ultimate

A college project of mine was to write a library to manipulate sparse arrays using circa 1970 Fortran. It annoyed me that the library calls were not expressed in the same syntax as standard Fortran arrays. And, similar scenarios annoyed my throughout my career, syntax for libraries could not be altered to represent the semantics.

Over the years extensions, including macro front-ends, have helped programmers make syntax match semantics. However, Thomas A. Standish pointed out that metaphrase extensions, using macros to extend syntax is not a panacea for language extension. See: "Extensibility in Programming Language Design," afips, pp.287, 1975 Proceedings of the National Computer Conference, 1975.

An extensible syntax that avoids metaphrase layering may simplify the process of matching syntax and semantics, which IMO would be a good thing.

The Ameba symbol table uses folded strings for symbols, but that is not a replacement for an AST. An AST can be developed and used effectively. Both the folded symbol table and an AST have data that can be used by some processes to do the same thin, but the symbol table cannot replace an AST.

Ameba is a very simple language. Like a calculator or machine language, it reads an op-code and evaluates it. When processing source, it acts similarly, as soon as a symbol is recognized it is converted into and op-code and evaluated. Thus, an AST is not necessary to process basic Ameba syntax. On the other hand, an AST would be very handy for metaprocessing such as optimization and translation.

Extensible syntax is possible, even under the above definition. Christiansen grammars (attribute grammars where one attribute is the grammar) would support the level of flexibility described here. More precisely: your 'language' would be described by the abstract syntax tree rather than by the syntax, and your initial grammar would describe a default syntax that will generate a tree of the target format - including a feature to tweak the grammar-attribute. Any extensions to or mutations of the syntax would still reduce to a common AST-type, but you could control syntax (eliminate keywords, for example) in order to support programming disciplines and protocols.

The real difficulty is making the extensible syntax modular, such that they can be provided by library and syntaxes from multiple libraries combine in a sane manner in a single program. Name spaces are problematic enough for multiple libraries, and dealing with overlapping names is a relatively simple problem compared to coordinating overlapping grammar extensions.

I had my heart set on fully extensible syntax for several years, but I'm less convinced today. I am concerned about complexity, difficulty of implementation, clarity of error reporting, and potential for confusion among developers. The final argument that changed my mind was Gilad Bracha's 'ban on imports', which discourages named dependencies between libraries.

I've decided to favor a much weaker variation of extensible syntax: the ability to name a basic parser (really, a stage-0 interpreter) at the top of a 'page' of code. This is sufficient for versioning the language syntax and providing alternative syntaxes for data description, DSLs, and so on. These stage-0 interpreters must produce an AST of a common type, and strictly keeping the dependencies shallow (a module depends on multiple interpreters, and a project composes multiple modules) also satisfies Gilad Bracha's arguments for reusable code and avoiding dependency hell. This is more a plug-in extensible language than true syntax extension.

Yes, the computer industry is locked into doing business without syntax extensibility. If techniques to extend languages had been discovered in the '50s, computing tools and artifacts would probably be very different.

The extensibility solution developed by me does not need an adaptive grammar. The default syntax allows all possible variations of subroutine call, which alleviates the need to modify the default syntax. In a program, every character and token is processed by a routine. Ameba calls a routine for every character and token, including, but not limited to the following: do, while, if, then, else, and fi,

Machine language also works this way, each op-code calls a routine. Ameba extends the idea of an op-code to include characters, tokens, and expressions, which are the language. A program is a file of characters. Characters are collected into tokens, Tokens are collected into expressions. Ameba is expression based, so has no statements.

A subroutine that processes its own syntax may need to read from a file to get data necessary to process its arguments. Such a subroutine must be called before its arguments and their syntax can be known. Ameba, assumes this scenario.

Based on this assumption, a library of extensible code cannot be distributed as we currently distribute libraries. On the other hand, libraries written in existing languages can be used by an extensible language interpreter, because the interpreter for the extensible language must be written in an existing language, such as C.

I hope you do not give up on an extensible language. IMO the difficulty is not the technology; rather, it is thinking outside the box to understand it and find simpler solutions.

Many years ago, during the punch card era, I noticed the evolution of card readers. They began as rivals to Rube Goldberg machines and became simpler and simpler. As the era closed, a card reader was trivially simple. A tilted table to feed the cards, a read station, and a bin to catch read cards. New technology is unnecessarily complex and evolves to be simpler; it is a recurring pattern.

If my body allows, you will be able to test drive Ameba in the not too distant future. Version 0.1 will run on Linux.

I had my heart set on fully extensible syntax for several years, but I'm less convinced today.

Agree 100% for all the reasons you listed. Once you support prefix, infix and postfix operators, you've covered probably 99.9% of what anyone would want to express in a language.

People aren't generally interested in the syntax IMO, as long as the language is sufficiently expressive, they are more interested in altering the semantics of embedded constructs via safe metaprogramming of some sort. Safe stage-0 interpreters, macros, and so on are what's needed. We should be able to transform a program statically ala Active Libraries in a safe and modular way.

It does seem that programmers are not really interested in syntax. On the other hand, mathematicians and authors write very precise syntax and occasionally invent a syntax nuance.

Thanks for your compliment.

On the other hand, mathematicians and authors write very precise syntax and occasionally invent a syntax nuance.

I think the convention is to use a symbol only to make an important semantic distinction. They wouldn't have adopted the integral symbol, or gradients, etc. if they were not semantically distinct from every other mathematical operation at the time.

In programming, our convention is to invent names for semantic distinctions. IMO, we need better ways to make semantics extensible and composable, not syntax. Syntax is just window dressing to understanding a program. Any syntax that makes semantics clear would suffice.

Certainly a certain syntax is clearer with a new syntax, but that seems the exception, not the rule. I'd like to see examples of programs where prefix/infix/postfix operators were unsufficient before accepting that arbitrary extensible syntax ala Katahdin is truly necessary.

> Once you support prefix, infix and postfix operators, you've covered probably 99.9% of what anyone would want to express in a language.

I'm not that sure, most programmer who know several programming languages regrets that contruct 'foo' is not available in the programming language he has to use and those construct are not necessarily doable with infix,prefix,post operators.

My own language construct that I tend to miss in the 'normal' programming languages are
- embedded evaluation/variable ie print("this is a text ${foo}\n");
- enums with strings representations:
enum type_enum { foo, bar, baz };
type_enum v = foo;
print(v); // prints foo not 0

Sure you can do print("this is a text %s\n",foo) or use C++ style and create classes for the enum but these are workarounds from a syntactic point of view they don't look very pretty..

- embedded evaluation/variable ie print("this is a text ${foo}\n");

Right, but casting this as a syntax issue is questionable. It's more like a dependent typing issue, or you can by adding more structure to the control string.

You can probably solve it with syntax too, since string delimiters cause the quotation issues in the first place. If you could come up with some unambiguous way to specify a string without delimiters, or with some set of delimiters that allow splicing operations, that could work, but it's starting to look like Danvy's solution.

In any case, solutions to printf certainly don't require syntax changes, or even syntax extensibility.

- enums with strings representations:

This doesn't seem like a syntax issue either, it's just an overloaded "show" as in Haskell (ToString() in .NET/Java).

Your first example is a perfect example of the general "quotation" mechanism : a closed fragment of program that is written in a completely different syntax -- translated after the fact in the syntax of the host language -- that possibly itself includes "antiquotations", that is fragments of the horiginal host language. A preprocessing phase can expand the quotations away into the simple language syntax.

Quotations account for most uses of domain-specific syntax in a given language (think specific XML syntax, SQL-like embedded syntax, and possibly even printf-like format strings), and they are easy to delimit and naturally generic (just add an anotation to specify which specific parser is to be used for the quotation). It is therefore easy to include from the start a general quotation syntax in your language, and does not require full syntax extensibility.

Your second example can also be accounted for a common case of metaprogramming : annotating the language constructs with code producers. In your example, you overload a supposedly existing language feature (enum types) with a specific behavior (direct string representation). You could formulate it as a generator that, given the AST of an enum type definition, would implicitly produce additional toplevel definitions such as a printing function (say string_of_type_enum), so that you could use `print(string_of_type_enum v)` in your code.

Such generators are also quite easy to plan in the initial syntax of your language : devise a generic generator syntax for some of the syntaxic constructs (a generator for type declarations and a generator for value definitions may have a slightly different specification in what kind additional code they may produce), and let other people plug their generators as a preprocessing phase.

In general, I think that it would be fruitful to isolate such uses of syntax flexibility, and try to add for them a fixed, but flexible and plugin-ready syntax. Those use cases are generally much easier to handle that general syntax extensibility (changing syntax rules of an already existing syntaxic class, etc.), and much more well-behaved. Comments might ultimately be one instance of this global idea as well.

It certainly is possible. It's done in Felix. The whole grammar is dynamically loaded from a bootstrap. There are no keywords. A few symbols are fixed as punctuation marks such as parens, asterisk, comma but these have no semantics. Felix also fixes the lexicology of some core literals (although that's not necessary except for some integers).

The parser is Dypgen, an extensible GLR parser with many extra features. The action codes for the reductions are arbitrary Scheme codes evaluating to S-expressions (which are converted into Felix's native terms which are Ocaml variants).

Not at all.

Those mnemonics are the language. Even if you're making some sort of meta language definition you need some syntax to use, otherwise you end up with people writing something like cil by hand alongside BNF.