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 Millendoug@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