Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site umn-cs.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!stolaf!mmm!umn-cs!amit
From: amit@umn-cs.UUCP (Neta Amit)
Newsgroups: net.ai,net.research,net.lang,net.lang.lisp
Subject: Re: String reduction
Message-ID: <994@umn-cs.UUCP>
Date: Fri, 18-Apr-86 11:59:06 EST
Article-I.D.: umn-cs.994
Posted: Fri Apr 18 11:59:06 1986
Date-Received: Mon, 21-Apr-86 01:46:00 EST
References: <1031@eagle.ukc.ac.uk>
Reply-To: amit@umn-cs.UUCP (Neta Amit)
Organization: Computer Science Dept., U of Minn, Mpls, MN
Lines: 42
Xref: watmath net.ai:3413 net.research:457 net.lang:2379 net.lang.lisp:804

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).
 
Markov algorithm consists of an input string S and a program P, which
is a sequence of BNF-like productions LHS --> RHS. The evaluator scans
P top to bottom (that's sequencing), looking for a match between a
substring of S and the LHS of a production (that's conditionals). When
a match is found, the RHS replaces the matching substring in S, and
the scanning is restarted from the top of P (that's looping).  Let's
not consider termination and error conditions.  As stated here, this
isn't a purely applicative model, but there is no inherent reason why
the new S couldn't in fact be new!

Michael Barnett of Brooklyn College, CUNY, (a Chemist turned Computer
Scientist) has recently suggested (See Sigplan Notices in the last 12
months) that it may be possible to synthesize molecules that will do
string substitution (a biological computer) and that this might be a
good model to describe the functionality of the human brain.

If I understand correctly, you are looking for an applicative model,
in which functions cause string-substitution instead of returning
values. Notice that this is the mechanism used by parametrized macro
expansion (so you can easily simulate an applicative string reduction
machine in Pure Lisp, using macros alone.)

A guy named Karl Fant, from Honeywell Research (in Minneapolis), has
been developing an applicative string-reduction model, but I don't
think he has published in a publicly available journal.

Anyway, I would be interested in expanding this discussion.

Cheers,	
	--Neta			CSNET: amit@umn-cs                 
				ARPA:  amit%umn-cs@csnet-relay.ARPA
				UUCP:  ...ihnp4!umn-cs!amit