A template based graph reduction system based on combinators

Abstract

Graph reduction is one of the important evaluation strategy for lazy functional programming. A combinator is a function that contains no free variables. The idea is based on the fact that, all of the variables in a program can be removed by transforming it into a sequence of combiriators which would be drawn from a small pre-defined (fixed) set of combinators (SKI), or which would be drawn from an unlimited number of non-pre-defined set of dynamic super-combinators (SC). We are suggesting a template based algorithm which reduces the stored graph structure of the super-combinators. We can define any produced super-combinators by using templates and use them to perform reduction on the graph. The template based algorithm could be extended and any produced super-combinators can be defined with a predefined template list. The test results show that pur approach increases the efficiency of super-combinators algorithms,