Implementing recursive functions as processor farms

The theoretical foundation of functional languages in the lambda calculus makes the detection of parallelism in such languages relatively straightforward. Exploiting this potential parallelism has proven more difficult. Much attention has been devoted to concurrent graph reduction but there has also been interest in the use of well known parallel programming constructs as a way of structuring parallel implementations of functional programs. In this paper a general technique for implementing linear recursive functions as processor farms is presented. A system is described which utilises the technique to produce concurrent transputer based implementations from SML source programs. The system uses information gathered from the analysis of test cases in conjunction with a performance model for processor farms to determine which functions in the source program may be suitable for farming. © 1993.