graph reduction

1 definition found

graph reduction - Free On-line Dictionary of Computing (26 May 2007) :

  graph reduction
  
     A technique invented by Chris Wadsworth where an expression is
     represented as a directed graph (usually drawn as an
     inverted tree).  Each node represents a function call and its
     subtrees represent the arguments to that function.  Subtrees
     are replaced by the expansion or value of the expression they
     represent.  This is repeated until the tree has been reduced
     to a value with no more function calls (a normal form).
  
     In contrast to string reduction, graph reduction has the
     advantage that common subexpressions are represented as
     pointers to a single instance of the expression which is only
     reduced once.  It is the most commonly used technique for
     implementing lazy evaluation.