Path: utzoo!attcan!utgpu!watmath!clyde!ima!compilers-sender From: ti-csl!tilde.ti.com!Gateley@cs.utexas.edu (John Gateley) Newsgroups: comp.compilers Subject: Re: Pattern languages Message-ID: <2873@ima.ima.isc.com> Date: 8 Nov 88 20:00:26 GMT Sender: compilers-sender@ima.ima.isc.com Reply-To: John Gateley Organization: TI Computer Science Center, Dallas Lines: 117 Approved: compilers@ima.UUCP Posted-Date: Tue, 8 Nov 88 14:00:26 CST In-Reply-To: Msg of Tue, 8 Nov 88 12:34:46 CST from Mail Delivery Subsystem In-Reply-To: <2866@ima.ima.isc.com> 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] -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU Plausible paths are { decvax | harvard | yale | bbn}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request