Re: Pattern languages

The programming language Scheme, and the macro definition tool Scheme
provide the capabilites you are looking for: they allow easy
implementation of other programming languages within Scheme. This is
true of any Lisp dialect with macros, but Scheme is particularly well
suited for it.


The references are:
The Revised^3 report on the algorithmic language Scheme.
MIT, AI memo 848a. (Sept. 86).


Syntactic Extensions in the Programming Language Lisp.
Eugene Kohlbecker (Doctoral Dissertation)
Indiana University Tech. Report 199, August 1986.


In article <2866@ima.ima.isc.com> you write:
<[Existence of pattern language ...]


>The closest examples I can think of are not general tools, but the
>possibility to extend languages through overloading etc. Smalltalk,
>Prolog and Lisp all make it relatively easy to add new syntactic
>patterns (within certain constraints!).


The only constraint on Lisp, is that the patterns and expansions must
be syntactic objects (exrpressions).


>Examples of what you should be able to do include:
>- macro substitution


It does it.


>- expression re-writing (e.g., translation to postfix form)


Is this really what you want (Scheme, like all Lisps are prefix)?
If it is, then here is one solution: Write a macro called postfix.
Then (postfix (a + (b + c))) would expand into (a b c + +).
However, I am not sure you would want to change it into postfix, since
Scheme is prefix.


>- object classes (declaration, inheritance, ...)


This is more than syntactic transformation, but it can be done in Scheme.
It is done with lambda, Scheme's method of generating functions. Basically
an object is a function which is passed messages as arguments. More
complete definitions are doable, just a bit more complex.


>- control abstractions (e.g., loops, transactions, ...)


Scheme has call/cc, which allows modelling of almost all control constructs
(one exception is BASIC's goto, you have to do a bit more translation on
something like that). This allows you to make your own kind of loops,
backtracking, co-routines, and much more.


>- generic functions


Generic functions do not have much to do with syntactic forms/expansions.
In fact, the whole point of generic functions is that calls to them are
syntactically the same as calls to normal functions. Defining generic
functions can be done by creating a "lookup" function which uses tables.
Adding methods to the generic function does not change the lookup
function, it modifies the tables. There are other techniques for doing
this too.


>Since a pattern language should be a relatively simple tool (in the
>spirit of, say, awk), it should not be concerned with generation of
>addresses, optimization, or most of the nasty things real compilers do.


Extend-syntax is a source to source translation, and is also very simple
to use (easier than defmacro, and much easier than older lisp's expansion
function). As an example, here is the fibonacci function:


(extend-syntax (fib 0 1)
    ((fib 0) 1)
    ((fib 1) 1)
    ((fib n) (number? 'n) (with ((n-1 (- 'n 1))
(n-2 (- 'n 2)))
(+ (fib n-1) (fib n-2))))
    ((fib n) (fib-fun n))


This causes (fib 0) to expand to 1, (fib 1) to expand to 1, (fib 2) to
expand to (+ 1 1), (fib 3) to expand to (+ (+ 1 1) 1). All this happens
at macro expansion time (compile time). In the other case, fib is being
applied to something that is not known to be a number, so it just
generates a call to the fib function, which will be executed at runtime.


>The kind of functionality I believe a pattern language should provide
>would be:
>- definition of parameterized patterns and their semantic actions


See my example above, and more complex pattern matching is provided.


>- actions should include bookkeeping (management of scopes and
> symbol tables) and generation of output (translation)


Using the with expressions (see above), you can call arbitrary functions
at compile time, so this is easy.


>- a primitive form of type-checking for pattern parameters
> (i.e., parameters will also be matched by patterns)


Extend-syntax provides pattern matching, plus additional checks on the
input (see the (number? 'n) expression above, this insures that the
argument is a number).


>- recursive patterns


Fib as defined above is recursive.


Please contact me if you have more questions.


John Gateley
gateley@tilde.csc.ti.com
[Good point, people have been embedding languages in Lisp forever. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.