Lambda the Ultimate

inactiveTopic Extensible Syntax with Lexical Scoping
started 6/9/2003; 6:21:08 AM - last post 6/9/2003; 6:21:08 AM
Ehud Lamm - Extensible Syntax with Lexical Scoping  blueArrow
6/9/2003; 6:21:08 AM (reads: 1429, responses: 0)
Extensible Syntax with Lexical Scoping
Extensible syntax with lexical scoping. Luca Cardelli, Florian Matthes, and Martín Abadi. SRC Research Report 121, Digital Equipment Corporation Systems Research Center, February 21, 1994.

A frequent dilemma in programming languages design is the choice between a language with a rich set of notations and a small, simple core language. We address this dilemma by proposing extensible grammars, a syntax-definition formalism for incremental language extensions ans restrictions. The translation of program written in rich object languages into a small code language is defined via syntax-directed patterns. In contrast to macro-expansion and program-rewriting tools, our extensible grammars respect scoping rules. Therefore, we can introduce binding constructs while avoiding problems with unwanted name clashes. We develop extensible grammars and illustrate their use by extending the lambda calculus with let-bindings, conditionals, and constructs from database programming languages, such as SQL query expressions. We then give a formal description of the underlying rules for parsing, transformation, and substitution. Finally, we sketch how these rules are exploited in an implementation of a generic, extensible parser package.

An interesting paper on language extension (think macros). An interesting feature of the approach described here is that it deals explicitly with the effect language extensions have on parsing.

One of the recurring issues with language embedding (startified design), is that of combining pieces code written in different sub-languages. Languages that use normalized syntax (e.g., Lisp's use of S-expressions), are much easier to extend than languages that have a more ad-hoc syntactic structure.

This paper explores the more general case, but doesn't neglect the fundamental issue of correctly handling lexical scope.

Posted to general by Ehud Lamm on 6/9/03; 6:23:22 AM