A note on leftmost innermost term reduction

Küchlin presents an indeterministic abstract term-reduction algorithm that allows one to select arbitrarily which node to reduce next---an algorithm that (by using explicit labeling of nodes) is optimal in the sense that it does not attempt to reduce nodes again that have already been fully reduced...

Full description

Saved in:
Bibliographic Details
Published in:SIGSAM bulletin 1983-08, Vol.17 (3-4), p.19-20
Main Author: Stickel, Mark E.
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Küchlin presents an indeterministic abstract term-reduction algorithm that allows one to select arbitrarily which node to reduce next---an algorithm that (by using explicit labeling of nodes) is optimal in the sense that it does not attempt to reduce nodes again that have already been fully reduced by it. He then analyzes two standard reduction algorithms (leftmost innermost and leftmost outermost reduction) that employ implicit labeling of nodes to preclude attempts to reduce anew already fully reduced nodes. In the case of leftmost innermost reduction, the implicit labeling designates all terms to the left of or below the term currently being reduced as being already fully reduced. His algorithm for leftmost innermost reduction is as follows:
ISSN:0163-5824
DOI:10.1145/1089338.1089340