List Processing Primitives for Parallel Computation?
School of Computer Science, University of Birmingham
Birmingham B15 2TT, U.K.
Department of Computer Science, University of Warwick
Coventry CV4 7AL, U.K.
c Copyright TH Axford & MS Joy 1992
A new model of list processing is proposed which is more suitable as a basic data structure for architecture-independent programming languages than the traditional model of lists. Its main primitive functions are: concatenate, which concatenates two lists; split, which partitions a list into two parts; and length, which gives the number of elements in a list. This model contains a degree of non-determinism which allows greater freedom to the implementation to achieve high performance on both parallel and serial architectures.
Keywords: data structures, functional programming, list processing, parallel programming.
Lists have been used as basic data structures within programming languages since the 1950s. The most elegant and successful formulation was in Lisp  with its primitive functions car, cdr and cons, often now referred to by the more meaningful names of head, tail and cons respectively. Lisp and its model of list processing based on the head, tail and cons primitives have given rise to a large number of programming languages over the three and a half decades since Lisp was invented; for example, following closely to the pure Lisp tradition are ML, Miranda and Haskell.
The success of the Lisp model of list processing is due to a combination of its semantic elegance on the one hand and its simplicity and efficiency of implementation on the other.1 In the context of functional languages particularly, it has given rise to a style of programming which is clear, concise and powerful. This style is well documented in many publications, for example .
?Published in Computer Languages 19(1), 1?12 (1993)
1In the early development of Lisp, efficiency of implementation was a major concern, while the desire for an elegant and coherent semantic model of list processing was much less pressing. Nevertheless, the reason that Lisp was more successful than its list-processing competitors almost certainly had a lot to do with McCarthy's perceptive choice of the basic routines that operated on lists.