A template based graph reduction system based on combinators. (Q1848712)

Summary: 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 combinators which would be drawn from a small pre-defined (fixed) set of combinators, or which would be drawn from an unlimited number of non-predefined set of dynamic super-combinators. We suggest 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 our approach increases the efficiency of super-combinators algorithms.