ERights Home elang / grammar 
Back to: QuasiLiterals On to: Obsolete: Quasi-Literals and XML

and Term / Functor Trees

Note: This page will explain E's current plans for quasi-literals on symbol trees, but is still terribly incomplete. In the meantime, this page should give a sense for where we're going. It expresses the same set of concepts in terms of our earlier plans to use Minimal-XML DOM trees.

Match-Bind-Substitute Programming
Extensible Symbolic Notations

*** write overview

  • A Parser Generator whose actions build Term trees.

    This technology creates notational interoperability.

  • A QuasiParser generator for creating QuasiParsers, for creating quasi-literal expressions and quasi-literal patterns

    With this technology, programmers can write transformation code in the match-bind-substitute programming paradigm in the context of general programmability

Universal vs Specialized Syntaxes?

Lisp S-Expressions, Prolog Term Trees, and XML all demonstrate the power of using a "universal" notation for trees of symbols to represent information that could have been encoded in a great variety of separately designed notations. The most common approach to using this power is to express oneself directly in this universal notation. For example, the strength of this approach is the most often cited explanation of XML's popularity: By using a common underlying representation (e.g., XML), generic tools (e.g. XSLT) can often be written to apply to many particular forms of symbolic information (e.g. domain-specific XML conforming to a particular DTD) not known to the tool creator.

However, this approach by itself has a great cost. It would have us forsake the use of specialized syntaxes optimized for use in specialized domains. The history of at least Math, Physics, many domains of Engineering, and especially Computer Science shows the surprising degree to which a well designed notation can aid human thinking in novel complex domains.

Example: Algebraic Expressions

The simple expression, written in standard math notation as

x2 + x3

is expressed in MathML as


MathML is a particularly notorious example of the price XML pays for using a single generic syntax for all jobs. But even with Lisp E-Expressions, we might express this as

'(plus (power x 2) (power x 3))

or, similarly, in Prolog Term Trees as

plus(power("x", 2), power("x", 3))

While both of these are vast improvements over MathML, they are still vastly worse for this purpose than the conventional specialized algebraic notation. Such is the price of universal notations, even well designed ones.

Notational Interoperability: Many Surfaces on One Tree

*** Explain about Antlr ASTs and Tokens and parser generation.

*** Explain bout Term / Functor trees, and about our universal Term tree syntax.

*** Explain briefly about Astro and AstroToken.

Match-Bind-Substitute Programming

*** Show symbolic differentiation

By contrast, using the QuasiParser technology described below, we can express the same transformation in E as

def deriv(expr, var) :any {
    switch(expr) {
        match math`$var ** @exp` ? (isConst(exp)) {
            math`$exp * $var ** ($exp - 1)`
        match math`@a + @b` {
            def da := deriv(a, var)
            def db := deriv(b, var)
            math`$da + $db`
        # ...

The last 3 lines could have instead been written as

            math`${deriv(a, var)} + $(deriv(b, var)}`

depending on your taste. This is not only compact, readable, and maintainable, it also states the transformation rules in a notation recognizable to the relevant subject domain specialists -- in this case, to mathematicians. Despite the notational shift, the output is a Term tree which can be written out as a ...

*** write the rest

Unless stated otherwise, all text on this page which is either unattributed or by Mark S. Miller is hereby placed in the public domain.
ERights Home elang / grammar 
Back to: QuasiLiterals On to: Obsolete: Quasi-Literals and XML
Download    FAQ    API    Mail Archive    Donate

report bug (including invalid html)

Golden Key Campaign Blue Ribbon Campaign