Reduction Semantics

From: http://www.intertrust.com/star/wright/441/notes/l9.html:

"A reduction semantics or rewriting semantics defines an an evaluation function eval for expressions based on a notion of reduction. We say that an expression e evaluates to an answer a if and only if e reduces to a..."

ReductionSemantics evaluates expressions by rewriting them to a new form. For any given form there may be one or more steps that may be applied to reduce it to a new form. The steps may be applied in any order. It is gauranteed that if an expression is reducable all reduction strategies that succeed will terminate in the same form. This is called the normal form or value of the expression.

There are (at least) two strategies for applying reductions: applicitive-order reduction and normal-order reduction. Applicitive-order reduction evaluates the arguments of a function first and then apply the function, and is also known as call-by-value. Normal-order reduction evaluates the function first and then the arguments. This is like call-by-name parameter passing.

Reduction results are immutable values not references to mutable objects so there are no aliasing problems. Reductions do not have side effects and so may be applied in any order.

Once an expression has been reduced any future instance of that expression may be directly replaced by its reduced form.