[net.lang.lisp] String Reduction

amit@umn-cs.UUCP (Neta Amit) (04/18/86)

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        

meier@srcsip.UUCP (Christopher Meier) (04/19/86)

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.
>...
>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.
>
Karl can be reached at ihnp4!srcsip!fant (or through any path I can...).
-- 
Christopher Meier  MN65-2300      {osu-eddie,okstate,bthpyd}\
S&RC Signal and Image Processing     {ihnp4,philabs,,gnutemp}\
3660 Technology Drive    (612)       {hyper,umn-cs,mmm,meccts}!srcsip!meier
Mpls, MN  55413         782-7191

alfke@cit-vax.Caltech.Edu (J. Peter Alfke) (04/22/86)

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

jkm@security.UUCP (Jonathan K.Millen) (04/24/86)

------
     If you are interested in an applicative Lisp-like language
based on string substitution and reduction, you might want to look
at "TRAC, A Procedure-Describing Language for the Reactive Typewriter",
by Calvin N. Mooers, Comm ACM, Vol. 9, No. 3, March, 1966.

Jon Millen

doug@terak.UUCP (04/24/86)

> 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.

If anyone cares, TRAC stands for Text Reckoner And Compiler, and is
trademarked.

It is discussed at some length in Peter Wegner's book, "Data Structures,
Information Processing and Machine Organization" (the title may be off
a bit, the book is at home and it's hard to remember such a lengthy
title :-)

Stanford used to have a version they called WYMPI.  The main differences
were the use of "*" instead of "#" and -- more significantly -- they
permitted string (macro) names to be specified as the operator, rather
than requiring as TRAC does that strings be specifically called with
the "cl" operator.  In other words, you could say *(macro,...) instead
of #(cl,macro,...).  Wegner leaves it as an exercise to the reader to
show why the "cl" was an important architectural feature of TRAC which
shouldn't have been tampered with.  Something about trying to make
#(cl,macro,...) == #(macro,...)   and at the same time making
##(cl,macro,...) == ##(macro,...)
-- 
Doug Pardee -- CalComp -- {elrond,seismo,decvax,ihnp4}!terak!doug

molson@apollo.uucp (Margaret Olson) (05/02/86)

>requiring as TRAC does that strings be specifically called with
>the "cl" operator.  In other words, you could say *(macro,...) instead
>of #(cl,macro,...).  Wegner leaves it as an exercise to the reader to

In the version of TRAC that I worked with in 1983, you could say
#(macro) and ##(macro).  As I recall, these two cases were treated
exactly like #(cl,macro) and ##(cl,macro).  This version had a considerably
larger set of primitives than those discussed in all the TRAC papers and
documentation that I ever saw.
               
String reduction has been used to solve real problems.  A company called 
Data Concepts used TRAC to write an applications generator.  The applications 
generator was used by insurance raters to write rating systems.  Rating systems 
are hard because insurance rating rules change all the time (like every day as 
far as I could tell).  Anyway, TRAC was used for a real product.  I think that 
Allstate is still using this stuff for some kinds of commercial policies.  

TRAC trivia: It was developed and originally owned by Calvin Mooers, and then
sold to Data Concepts Inc.  Data Concepts has since gone bankrupt, so I beleive 
that TRAC is now owned by some type of bankruptcy court entity.  It is (presumably)
for sale.

Margaret Olson.
molson@apollo