List Processing Primitives for Parallel Computation

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. 1 Introduction Lists have been used as basic data structures within programming languages since the 1950s. The most elegant and successful formulation was in Lisp [9] 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 ..