Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbosgd!gatech!seismo!cit-vax!alfke
From: alfke@cit-vax.Caltech.Edu (J. Peter Alfke)
Newsgroups: net.ai,net.research,net.lang,net.lang.lisp
Subject: Re: String reduction
Message-ID: <404@cit-vax.Caltech.Edu>
Date: Mon, 21-Apr-86 22:17:10 EST
Article-I.D.: cit-vax.404
Posted: Mon Apr 21 22:17:10 1986
Date-Received: Thu, 24-Apr-86 06:32:30 EST
References: <1031@eagle.ukc.ac.uk> <994@umn-cs.UUCP>
Reply-To: alfke@cit-vax.UUCP (J. Peter Alfke)
Organization: California Institute of Technology
Lines: 28
Xref: watmath net.ai:3420 net.research:461 net.lang:2386 net.lang.lisp:812

Organization : California Institute of Technology
Keywords: 

In article <994@umn-cs.UUCP> amit@umn-cs.UUCP (Neta Amit) writes:
>In article <1031@eagle.ukc.ac.uk> sjl@ukc.ac.uk (S.J.Leviseur) writes:
>>Does anybody have any references to articles on string reduction
>>as a reduction technique for applicative languages (or anything
>>else)? They seem to be almost impossible to find! Anything welcome.
>
>String reduction as a model of computation was suggested by
>A.A.Markov, in his 1954(?) paper, and is proved to be equivalent in
>power to the other two general models of compution (Turing machine and
>the Lambda Calculus).

This sounds similar to Calvin Mooers' TRAC language of mid-sixties.  That
language was based entirely on macro expansion; rather strange, but actually
a lot more powerful than the toy it first appeared to be.

There was also a language called SAM76 that showed up in 1976, that seemed
close enough to TRAC to warrant a lawsuit.  It seemed identical in concept,
with only minor differences in syntax and function-names.

TRAC is pretty easy to implement; I have an incomplete version written in
C that I did some years back.  I also have a paper on TRAC which is probably
long out of print by now.

						--Peter Alfke
						  alfke@csvax.caltech.edu