Rewrite Rules

It's possible to model computation as carrying out a series of rewrite rules.

You have a database of rules and an input datum. Each rule says, basically, "If the input looks like THIS, rewrite it like THIS."

You try to match the input datum against the rules. When you find the best match, the rule will specify a way to rewrite the input pattern. (Alternatively, all matching rules are followed, as is common in LogicProgramming and AutomatedTheoremProving.)

The rewritten pattern becomes a new input pattern and the process repeats. If an input pattern doesn't match any rules, computation stops. Traditionally, one ensures that there are a variety of 'canonical forms' that are not matched by any rule; these correspond to 'values' in the language.

This is the way most of us were taught to do algebra and calculus.

Languages & systems based on RewriteRules, in whole or part:

Those for whom SchemeMacros are just not twisted enough may be interested in sendmail configuration files; these are based on rewrite rules, and are famously Turing-complete. See http://www.hopf.demon.co.uk/demon/turing.txt and http://okmij.org/ftp/Computation/sendmail-as-turing-machine.txt. Exim's address-routing language is similarly powerful (http://dotat.at/writing/exim-turing.conf).

Rewrite systems are often able to perform computations bi-directionally, producing inputs from a source. Some rewrite systems distinguish between '=' and '=>', with the former allowing flow in both directions and the latter to be uni-directional.

AutomatedTheoremProving also can be done using RewriteRules using axioms and theorems from logic as the rules.

Every day actions are similar to RewriteRules (a ProductionSystem? mapping from actions to actions):

go to work -> drive to work, get coffee, go to office, check email drive to X -> get things for X, go to car, start car, take route to X, park get coffee -> order, pay, pour, add cream/sugar, stir go to office -> take elevator, greet receptionist, say hello to people in hallway ...

Such rules are actually coded into robots and HomeAutomation systems where they have to perform the actions or accommodate a person's habits, eg car automatically set seat for driver D because this is the time she drives to work. See also EventDrivenProgramming.

RewriteRules are considerably more powerful than this example. For example, if you want to write a program to evaluate Scheme expressions, you can have a machine state that looks like one of these:

 (eval <expr> <env> <k>)
 (call <proc> <args> <k>)
 (return <k> <retval>)

The eval state means that the machine is about to evaluate the expression <expr> in the environment <env> and return the result to the continuation <k>.

The call state means that the machine is about to call the procedure <proc> with arguments <args> and return the result to the continuation <k>.

The return state means that the machine has already computed <retval> and is about to return it to the continuation <k>.

To stop the machine, you need a final continuation FK. Then your first rule is the one that stops the machine.

 [Rule #1] (return FK <retval>) -> STOP (processing was successful; maybe display <retval> for the user)

Then you can create other rules. Here's the rule that evaluates literals:

 [Rule #2] (eval <literal> <env> <k>) -> (return <k> <literal>)

This pattern has to be implemented in such a way that <literal> only matches a self-evaluating object. If the pattern does not match you have to use some other rule.

Here's four rules that handle begin. First the begin with only one expression in it:

 [Rule #3] (eval (begin <e1>) <env> <k>) -> (eval <e1> <env> <k>)

That's pretty simple, it just throws away the begin. Then the begin with multiple expressions:

 [Rule #4] (eval (begin <e1> <e2> ...) <env> <k>) -> (eval <e1> <env> (begin-continuation <env> <k> <e2> ...))

This rewrites the whole state so that the first expression of the begin will be evaluated, and the result will be returned to a new begin-continuation which will throw away the result and evaluate the subsequent expressions of the begin.

To make the begin-continuation work we have to write rules to match it. Here's the case where the begin continuation contains only one more expression:

 [Rule #5] (return (begin-continuation <env> <k> <e2>) <retval>) -> (eval <e2> <env> <k>)

This evaluates the expression in the tail position. Then we handle the case where the begin continuation contains two or more subsequent expressions:

 [Rule #6] (return (begin-continuation <env> <k> <e2> <e3> ...) <retval>) -> (eval <e2> <env> (begin-continuation <env> <k> <e3> ...))

This starts the evaluation of the second subexpression and sets it up to return its value to a begin-continuation which will evaluate the remaining expressions of the begin.

To evaluate (begin 1 2 3), you write an initial machine state and then apply the matching rules, as follows:

 (eval (begin 1 2 3) #f FK)
   [matches Rule #4]
 (eval 1 #f (begin-continuation #f FK 2 3))
   [matches Rule #2]
 (return (begin-continuation #f FK 2 3) 1)
   [matches Rule #6]
 (eval 2 #f (begin-continuation #f FK 3))
   [matches Rule #2]
 (return (begin-continuation #f FK 3) 2)
   [matches Rule #5]
 (eval 3 #f FK)
   [matches Rule #2]
 (return FK 3)
   [matches Rule #1 -- STOP! Final result is 3]

To make call-with-current-continuation, you have to define a rule that matches the call state where call-with-current-continuation is about to be called...

See ModelsOfComputation

CategoryModels