Comparing Two Functional Programming Systems

Abstract

Comparing the efficiency of different implementation techniques for functional languages is clearly a difficult problem. Normally, the implementations in question are designed to evaluate all kinds of recursively defined functions and thus, the time complexity of the evaluation process cannot be limited by any computable function of the size of the input. Therefore, standard complexity theory is useless in this case. As a result, we must rely on statistical methods. The use of statistical methods also has many problems, because of the large number of parameters that can influence the results. This paper presents our attempt at reducing the number of parameters by factoring out as many as possible when gathering performance statistics. We illustrate our method by describing two entirely different functional programming systems and applying our method to the two systems using a collection of benchmark programs. The resulting data show the efficiency difference between a simple strict interpreter for FP and a general lazy interpreter for full lambda calculus. Furthermore, our figures for lambda-calculus interpreters on two radically different machines (IBM 370 architecture 3081 and IBM PC/AT) support our claim that we can factor-out much of the machine-dependent performance effects. © 1989 IEEE