We model a deterministic parallel program by a directed acyclic graph of tasks, where a task can execute as soon as all tasks preceding it have been executed. Each task can allocate or release an arbitrary amount of memory (i.e., heap memory allocation can be modeled). We call a parallel schedule "space efficient" if the amount of memory required is at most equal to the number of processors times the amount of memory required for some depth-first execution of the program by a single processor. We describe a simple, locally depth-first scheduling algorithm and show that it is always space efficient. Since the scheduling algorithm is greedy, it will be within a factor of two of being optimal with respect to time. For the special case of a program having a series-parallel structure, we show how to efficiently compute the worst case memory requirements over all possible depth-first executions of a program. Finally, we show how scheduling can be decentralized, making the approach scalable to a large number of processors when there is sufficient parallelism.

Arrays are probably the most widely used data structure in imperative programming languages, yet functional languages typically only support arrays in a limited manner, or prohibit them entirely. This is not too surprising, since most other mutable data structures, such as trees, have elegant immutable analogues in the functional world, whereas arrays do not. Previous attempts at addressing the problem have suffered from one of three weaknesses, either that they don't support arrays as a persistent data structure (unlike the functional analogues of other imperative data structures), or that the range of operations is too restrictive to support some common array algorithms efficiently, or that they have performance problems. Our technique provides arrays as a true functional analogue of imperative arrays with the properties that functional programmers have come to expect from their data structures. To efficiently support array algorithms from the imperative world, we provide O (1) operations for single-threaded array use. Fully persistent array use can also be provided at O (1) amortized cost, provided that the algorithm satisfies a simple requirement as to uniformity of access. For those algorithms which do not access the array uniformly or single-threadedly, array reads or updates take at most O (log n ) amortized time, where n is the size of the array. Experimental results indicate that the overheads of our technique are acceptable in practice for many applications.

The amount of memory required by a parallel program may be spectacularly larger than the memory required by an equivalent sequential program, particularly for programs that use recursion extensively. Since most parallel programs are nondeterministic in behavior, even when computing a deterministic result, parallel memory requirements may vary from run to run, even with the same data. Hence, parallel memory requirements may be both large (relative to memory requirements of an equivalent sequential program) and unpredictable. Assume that each parallel program has an underlying sequential execution order that may be used as a basis for predicting parallel memory requirements. We propose a simple restriction that is sufficient to ensure that any program that will run in n units of memory sequentially can run in mn units of memory on m processors, using a scheduling algorithm that is always within a factor of two of being optimal with respect to time. Any program can be transformed into one that satisfies the restriction, but some potential parallelism may be lost in the transformation. Alternatively, it is possible to define a parallel programming language in which only programs satisfying the restriction can be written.

We define a simple non-deterministic functional language that has definite variables and where function application is unfoldable. This language demonstrates the Søndergaard and Sestoft's claim, that in a non-deterministic language we cannot obtain both definiteness and unfoldability, assumes a fairly general notion of non-determinism. Our language relies on using a restricted notion of non-determinism called partial determinism.

Abstract Many of the details that a programmer must manage when programming in a procedural language are handled by the implementation in a functional language. In a parallel functional language, we would expect the assignment of processes to processors and the scheduling of processes to be handled by the implementation. The partitioning of a program into processes may be handled by the implementation as well. We will assume that a parallel functional program may create processes dynamically, and that processes may synchronize in an arbitrary manner. It does not matter whether processes are defined in the source program or generated by the implementation. On parallel systems where each processor has some local memory, it is common practice not to move processes once they have started to execute. We will show that if each process must be executed on a single processor, then no fully automatic scheduling strategy can ensure good performance. We also will show that if all processes are sequential processes (i.e. do not contain internal parallelism), and if a process may be moved whenever it resumes execution following synchronization with another process, then good performance can be assured, at least in theory.

Abstract Pattern matching in modern functional programming languages is tied to the representation of data. Unfortunately, this is incompatible with the philosophy of abstract data types. Two proposals have been made to generalize pattern matching to a broader class of types. The laws mechanism of Miranda allows pattern matching with non-free algebraic data types. More recently, Wadler proposed the concept of views as a more general solution, making it possible to define arbitrary mappings between a physical implementation and a view supporting pattern matching. Originally, it was intended to include views in the new standard lazy functional programming language Haskell. Laws and views each offer important advantages, particularly with respect to data abstraction. However, if not used with great care, they also introduce serious problems in equational reasoning. As a result, laws have been removed from Miranda and views were not included in the final version of Haskell. We propose a third approach which unifies the laws and views mechanisms while avoiding their problems. Philosophically, we view pattern matching as a bundling of case recognition and component selection functions instead of a method for inverting data construction. This can be achieved by removing the implied equivalence between data constructors and pattern constructors. In practice, we allow automatic mapping into a view but not out of the view. We show that equational reasoning can still be used with the resulting system. In fact, equational reasoning is easier, since there are fewer hidden traps.

Abstract We show how improving values (Burton, 1991) can be extended to handle both upper and lower bounds. The result is a new data type, called improving intervals . We give a simple implementation of improving intervals that uses a list of successively tighter bounds to represent a value. A program using improving intervals can be evaluated as a parallel program using speculative evaluation. The utility of improving intervals is demonstrated through two programs: parallel alpha-beta and parallel branch-and-bound

Abstract In a functional program, a simple random number generator may generate a lazy list of random numbers. This is fine when the random numbers are consumed sequentially at a single point in the program. However, things are more complicated in a program where random numbers are used at many locations, such as in a large simulation. The programmer should not need to worry about providing separate generators with a unique seed at each point where random numbers are used. At the same time, the programmer should not need to coordinate the use of a single stream of random numbers in many parts of the program, which can be particularly difficult with lazy evaluation or parallel processing. We discuss several techniques for distributing random numbers to various parts of a program, and some methods of allowing different program components to evaluate random numbers locally. We then propose a new approach in which a random number sequence can be split at a random point to produce a pair of random number sequences that can be used independently at different points in the computation. The approach can also be used in distributed procedural programs, where it is desirable to avoid dealing with a single source of random numbers. The approach has the added advantage of producing repeatable results, as might be needed in debugging, for example.

Abstract A parallel program may be indeterminate so that it can adapt its behavior to the number of processors available. Indeterminate programs are hard to write, understand, modify or verify. They are impossible to debug, since they may not behave the same from one run to the next. We propose a new construct, a polymorphic abstract data type called an improving value , with operations that have indeterminate behavior but simple determinate semantics. These operations allow the type of indeterminate behavior required by many parallel algorithms. We define improving values in the context of a functional programming language, but the technique can be used in procedural programs as well.

The aim of this study is to present an algorithm which manipulates overlapping B-trees. The characteristic of the algorithm is that it uses a number of pointer manipulation routines which may replace pointer manipulations within an ordinary B-tree without sharing. The main advantages of the approach are (a) that any code operating on ordinary B-tree may be easily extended to cope with overlapping B-tree, and (b) that the pointer manipulation routines are general purpose in the sense that they may be applied to a broader family of tree structures

Motivated by our interest in the use of functional programming languages to write parallel programs, we have been led to consider the anomaly of more processors possibly leading to a slower execution time. After reviewing known results from the theory of list-scheduling, we introduce generalisations of the familiar breadth-first and depth-first tree-searching algorithms to arbitrary dags and consider them in a list-scheduling framework. We prove that with UET actions (corresponding to pre-emptive scheduling with integer execution times for actions), breadth-first scheduling never leads to an increase in the execution time when the number of processors is increased. We also prove that for any list-scheduling algorithm with UET actions, there is no speed-up anomaly when going from two to three processors.

A record data type can be extended by addition of more fields. The extended type is a subtype of the original, in that any value of the extended type can be regarded as a value of the original type by ignoring the additional fields. This results in a type hierarchy. Milner [3] has proposed a polymorphic type system. With the Milner approach, the type of a function may contain type variables. This also results in a type hierarchy. In a language with a polymorphic type system, if it is anticipated that a record type will need to be extended, then the record type can be defined to have a dummy extension field . In the parent type, the extension field will have null contents of type void . The type of the extension field can differ with different subtypes. The approach can be extended to allow a type to be subtype of two or more parent types. To a limited extent, this approach can be used in Ada and other languages with generic program units.

Procedural programmers have found nondeterminism to be unavoidable in many parallel programs (e.g. operating systems). If function programming languages are to be usable as general-purpose parallel-programming languages then provision of some nondeterministic language construct appears to be necessary. Existing constructs for nondeterminism are not functional and are not compatible with the mathematical foundations of functional programming, which require that the value of a function be uniquely determined by the values of its arguments. We propose to solve this problem by placing the nondeterminism in pseudo-data. A program is passed an infinite tree of two-valued decisions, along with its input. These decisions may be fixed at run time, thereby permitting nondeterminism. Once fixed, a decision remains unchanged, so equivalent expressions must always have the same value. The approach generalizes so that a program can make use of other run-time information such as the current time or the current amounts of available storage.

Many parallel algorithms, particularly divide-and-conquer algorithms, may be structured as dynamic trees of tasks. In general, as parallelism increases, storage requirements also increase. A sequential program keeps storage requirements small by finishing one task (or procedure invocation) before going on to another, so that the entire task tree is never in existence at any one time. This corresponds to a depth-first expansion of a tree of tasks. On the other hand, a breadth-first expansion often produces a higher degree of parallelism, but also may produce an exponential growth in storage requirements. The resources (processors and memory) of a given system can be matched by alternating between depth-first and breadth-first expansion. The author's approach is to determine how much storage would have been available to a task in a sequential system, and to ensure that at least as much storage is available to the task when it is executed in a distributed system.>

There are at least two approaches to the design of languages for parallel computing. One approach is to use functional or relational languages which are easy to read, write, transform and verify. The more conventional approach is to use procedural languages which give a programmer a high degree of control over the run-time behaviour of a program. There is a need to reconcile these two approaches in a language which permits both simplicity and efficiency. We propose a small and simple set of annotations (or pragmas) to control the run-time behaviour of a functional program. The annotations allow a programmer to use three forms of parameter passing. The parameter-passing mechanisms correspond to passing by name, value and need in a sequential language. In addition, in a distributed system a programmer can specify that work should be done on the current processor, an arbitrary processor, or a particular processor such as the one containing a specific data item. The annotations cannot affect the meaning (result) of a functional program, except for causing non-termination in some cases (which we view as an extreme form of inefficiency). This separation of meaning from control allows a program to be both simple and efficient. Since non-determinism appears to be unavoidable without significant loss of efficiency in a concurrent system, the interaction of the proposed annotations with non-determinism is briefly considered. The run-time behaviour of an annotated functional program is similar to that of procedural programs using message passing, semaphores or rendezvous to control communication and synchronisation.

A simple but general map overlay function is defined for quadtrees. It is shown that many common quadtree operations, including union, intersection, relative complement, masking, copy, complement and generalisation of quadtrees, can all be viewed as special cases of map overlay, depending on how pixel values of the result of an overlay are determined from the corresponding pixels of the maps being overlaid. It is shown that some operations, such as union, can be more efficiently performed by specialised algorithms. A more general overlay function is given, which is optimal (to within a constant factor) with respect to both time and space for all of the above operations. This overlay function requires two functions as parameters. One function determines when the quadtrees being overlaid are simple enough to be processed without further subdivision. The other performsthe overlay for simple cases.

In a previous study an ordered array of N keys was considered and the problem of locating a batch of M requested keys was investigated by assuming both batched sequential and batched binary searching. This paper introduces the idea of batched interpolation search, and two variations of the method are presented. Comparisons with the two previously defined methods are also made.

Call-by-need is widely regarded as an optimal (to within a constant factor) parameter passing mechanism for functional programming languages. Except for certain special cases involving higher order functions, call-by-need is optimal with respect to time. However, call-by-need is far from optimal with respect to space. We examine some of the space problems which can arise with call-by-need and other parameter passing mechanisms. A simple optimizing technique, based on work by Mycroft [1], is proposed. If it can be determined both that an expression must be evaluated eventually and that the evaluation of the expression is likely to reduce the space required by the program, then the evaluation is performed as soon as possible. This optimization does not result in optimal space performance in all cases. However, in most of the common cases where call-by-need causes a problem the proposed optimization avoids the problem. Since our technique is not always optimal, it is likely to be of greatest advantage in situations where efficiency is important but not critical. For example, functional languages with call-by-name semantics are increasingly being used as specification languages. Since such a specification is runnable, it may be used as a prototype. This makes it possible to experiment with a program and refine the specification before the implementation in the target language is started.

A new approach to the buddy system for dynamic storage allocation is presented in which a block of a given size may be split in more than one way. It is demonstrated that this approach can be used to reduce the memory fragmentation of a buddy system.

When repeatedly editing a text file, one is often faced with a choice of keeping previous generations for backup or deleting previous generations to reduce storage requirements. Since one generation of a text file is often very similar to the previous generation, the above conflict can often be resolved by sharing much of the common information. We propose using a tree structure to represent a text file. Common subtrees can be shared. Results of an experiment with one file are reported.

Many problems can be solved more quickly on parallel machines if some work can be started before it is known to be necessary. If work which is known to be necessary (mandatory work) is given priority over other work (speculative work), then performing speculative work can only speed computation. A simple functional language feature to control speculative work is proposed.

In many applications it is necessary to be able to determine if a point is contained in a polygon. If co-ordinate values are approximate, we may be happy to have borderline cases dealt with in an arbitrary manner. However, if two regions have a common border section, decisions should be consistent. A simple algorithm for determining containment consistently is given.

A virtual tree machine consists of a fixed finite network of processors together with a suitable algorithm for deciding when and where to solve each subproblem.

When evaluating a functional program on a network of processors, it is necessary to decide when parallelism is desirable, which work may be transferred to another processor, and in what form the work is to be transferred.If the wrong decisions are made, a parallel evaluation may require asymptotically more time than a sequential evaluation, owing to communication costs.The introduction of annotations to give the programmer control over the above decisions is proposed.The annotations and their effects are defined in terms of the lambda calculus.Each application must have one of three annotations.No other annotations are required.Examples and possible extensions to this work, including annotated combinators, are briefly considered.

A generalised subtype definition facility is described. A subtype may be restricted in its values, its operations or both. Coercion from a subtype value to a parent type value is always possible. The reverse coercion may or may not be allowed, depending on the subtype. A subtype may or may not use the same form of representation as the parent type. Several examples showing the usefulness of the subtype facility are given. It is shown that, with a few additional facilities, subtypes may be useful in providing data independence in a general purpose language. Finally, it is shown that the concept of subtype is useful in understanding the relationships between certain other programming language constructs.

In an encapsulated data abstraction definition a data type and the set of all operations which may access or modify instances of the type are defined together. A simple extension to FORTRAN and a preprocessor to translate from the extended FORTRAN to standard FORTRAN are described. The extended FORTRAN supports encapsulated data abstraction definitions and permits the writing of clear and reliable programs. The preprocessor can do extensive error checking and produce efficient FORTRAN programs as its output. Definitions of stacks and dynamics arrays are given as examples.

Schneiderman and Goodman (1976) considered queries based on primary key values and they argued that the process of batching may reduce their response time. This study considers the effect of batching queries based on secondary key values and proposes some means of scheduling the queries which substantially reduces the required disc head movements. The method is a variation of the SCAN disc scheduling policy and it can be applied to online retrieval systems because it works even for very small batch sizes and because it does not impose prohibitive overheads in evaluating/implementing it.