Direct computation of recursive functions often leads to a repeated evaluation of the same recursive calls. Various techniques to overcome this drawback exist. The authors develop their methods on the basis of tupling and memoization, and on the assumption that the programming language (Haskel or one of its relatives) allows for the use of functions of higher order. They start with lambda-abstraction, which makes the recursive scheme simpler by paying the price of introducing higher-order functions, which can work with lambda expressions. The algorithm at this stage is more amenable to further transformation, but no more efficient than the original algorithm, because it still may evaluate the same call many times. The decisive step (called vector conversion) is to convert lambda abstractions into vectors, keeping the values of function calls as components of these vectors and using them more than once without recomputation (tabulation). Thus it all comes down to a form of memoization. Additional transformation may sometimes be done, such as conversion of the algorithm into an iterative form by tail recursion.
Vector conversion should, clearly, lessen the overhead of tabulation. The question is, how much, when compared with traditional methods of memoization? The authors present a table of time and space resources spent in computation of binomial coefficients C kn using their method and by “fully memoized” computation. Unfortunately, the choice of what they call the “fully memoized” form of memoization is not very informative. The presented data make one believe that this form is simply keeping a list of pairs’ argument-values and traversing it, which makes access time quadratic in n. It is not surprising, then, that the authors’ program works more than 100 times faster in some cases. Comparison of vector conversion with memoization through a two-dimensional table is discussed in the paper, but no figures are given. The paper is well written and can be recommended to those who are interested in non-automatic function transformation.
