Saturday, October 22, 2005

Language that represent themselves

In studying macros, I've discovered a fundamental complexity in one axis of language design: making aspects of a language easily representable within itself hampers the plasticity of the language. That is, as soon as you make it easy to observe the internals of the language, any changes you make to the language become by definition observable. As a result, any time you add, remove, or change a language feature, you add must consider that feature's representation within the language and how it affects the semantics.

This is well known to designers of languages with reflection, and causes all sorts of ulcers for compiler writers. But it's also a pain for designers of macros. For example, every time you add a new type of expression to the language, macros must be able to consume and produce that type of expression. Scheme makes this easier by generally having just one kind of expression--but in reality, that's a lie! Definitions are different from expressions, and cause lots of subtle complexities.


Anonymous said...

For example?

Dave Herman said...

Definitions are strange beasts because they have a linear/block structure rather then the tree structure of expressions. Bindings introduced by a definition are in scope for the rest of the definition's containing block.

Internal definitions are the reason for a subtle complexity in the marking logic of the syntax-case hygiene algorithm (the "toggling" mechanism).

They can apparently be used to generate bizarre mutual recursions between the parsing and expansion algorithms that expose the internal order of expansion of the underlying macro system.