Lambda the Ultimate

inactiveTopic RhoStratego
started 7/30/2002; 2:10:43 AM - last post 7/30/2002; 2:42:10 AM
jon fernquest - RhoStratego  blueArrow
7/30/2002; 2:10:43 AM (reads: 1263, responses: 1)

The original rho-calculus or rewriting calculus aims to "integrate first-order rewriting, the lambda calculus, and non-determinism." RhoStratego [1, 2] is basically the lambda calculus extended with constructors, let bindings, and from Stratego "first class pattern matching and generic traversals." (32) The semantics are well-organized:

"We first present a set of rewrite rules on the language. By taking different subsets of these rules, we obtain lazy or strict semantics. ...all sets of rules as a whole gives a non-confluent calculus ...the lazy and strict subsets themselves are confluent. ... The fact that the semantics is given as a set of rewrite rules from the language to the language, i.e., as source-to-source transformation, means that they can be used directly in, e.g., an optimiser or an interpreter for the language. In fact, an interpreter based directly on these rewrite rules is given in appendix B." (23)

Another Stratego paper by the same author Building Interpreters with Rewriting Strategies includes lambda calculus interpreters with strategies including "normalization, eager evaluation, lazy evaluation, and lazy evaluation with updates. An extension with pattern matching and choice shows that such interpreters can easily be extended." (Possible Analogy: These papers are to Rewrite interpreters as EOPL is to Scheme interpreters?)

Posted to LC by jon fernquest on 7/30/02; 2:14:46 AM

jon fernquest - Re: RhoStratego  blueArrow
7/30/2002; 2:42:10 AM (reads: 517, responses: 0)
For an introduction to term rewrite systems and the idea of confluence Burris's Logic for Mathematics and Computer Science is the easiest book to read and understand.