A Brief History Of Stream Parallel Logic Programming

Appeared in Volume 7/2, May 1994

Graem A Ringwood

What follows attempts to outline highlights in the history of the development without going into unilluminating detail or side issues.

1963 Conway describes coroutines in the context of multipass compilers.

1965 Streams are introduced by Landin in the context of lambda calculus. A stream is an incrementally constructed sequence of data objects. Streams can provide modularity without the need for state variables. Landin proposes lazy evaluation for processing streams.

1974 Kahn proposes coroutines for processing streams. A parallel computation is organized as a set of autonomous processes that are connected to each other in a network by communication channels (streams). The model is proposed as suitable for systems programming and the design of operating systems. While the theory only allows determinate programs, Kahn speculates that it is possible to extend it to indeterminate programs.

1977 Kahn and McQueen extend Khan's model to allow dynamic process creation and termination. A functional syntax is presented which relieves the programmer of the burden of programming the synchronization. This subordinates the control to the binding of variables (data flow). The authors suggest that channels may be broadened from linear lists to trees and tableaux.

1976 Friedman and Wise relate coroutining with a designated producer to lazy evaluation in functional programming.

1979 Van Emden and De Luceana embed the Kahn and MacQueen's model in logic programming. This gives a process interpretation of goals in contrast to the previous procedural interpretation. Goals in a query or body of a clause are grouped into sequential and parallel conjunctions. Variables shared between parallel conjunctions are regarded as communication channels. Parallel processes suspend if shared variables are not instantiated to lists. Input and output modes are determined by the initial goal. The example given is determinate. There is no discussion of nondeterminacy. The authors have great difficulty in getting their paper accepted for publication. It is not published until three years later as an invited contribution to a book.

Dausmann et al. use a variable delay annotation /B to synchronize processes in concurrent logic programming. The occurrence of the annotation X/B delays reduction of the goal containing it until X is bound.

Clark and McCabe offer IC-Prolog, a version of Prolog that introduces a profusion of control facilities for synchronizing the parallel evaluation of goals. IC-Prolog provides producer consumer variable annotations to synchronize coroutines. This is similar to Conniver [Sussmann and McDermott, 1972]. Both producer and consumer annotations are allowed. The same annotations can also appear in the head of a clause as well as the body. IC-Prolog introduces Dijkstra [1975] like guards that make clause head unification and guard constraints atomic. Unlike guarded commands, a clause with a successful guard is not exclusive. There is variable delay annotation '!', similar to Dausmann et al. Input and output is handled by stream primitives.

1980 Rather than Horn clauses, Hansson et al. propose a Kahn and McQueen interpretation of a logic language based on a natural deduction system of Prawitz [1965]. Producers and consumers are designated by an equational functional syntax. Nondeterminacy is handled by backtracking.

Belia et al. describe FPL (Functional plus Predicate Logic) a Horn clause equational functional setting for a determinate language with guards (the word constraint is used) and directed relations. Arguments of relations are designated as inputs and outputs. This is similar to the modes used in Edinburgh Prolog compiler [Warren, 1977] to improve the efficiency of compilation. A program is viewed as a set of conditional rewrite rules. A Lazy evaluation semantics allows the use of streams.

1981 With the Relational Language, Clark and Gregory [1981] make the guard introduced in IC-Prolog indeterminate (committed choice) as is the case with guarded commands. Variables in the guard must be ground by the call pattern. In the examples given, the guard constraints are primitives (flat) but this is not explicitly stated as a restriciton. Producer occurrences of variables in goals are annotated. Data flows from annotated variables to unannotated variables. Unannotated variables are "read-only". Any attempt to bind a read only variable by clause head unification causes suspension of the clause.

In this year, the first FGCS International Conference on 5th Generation Computer Systems is held in Japan.

1982 Japanese launch FGCS initiative to build parallel knowledgebased machines using Prolog as a kernel language. Initial funding for five years is granted with a promise of renewal for a further five subject to satisfactory progress.

1983 Shapiro attempts to clean up the Relational Language with Concurrent Prolog. Shapiro relaxes the restriction that guard variables need be ground and primitive. Allowing variables and user defined relations in the guard introduces the possibility of premature binding [see Ringwood, 1989 for a clear expalantion of this problem]. This is handled by having multiple binding environments as in or-parallel Prolog. Synchronization is controlled by variable annotations. Rather than output variables being annotated "read-only" variables are annotated. As a visitor to ICOT, Shapiro persuades the FGCS project to change allegiance from Prolog to Concurrent Prolog.

In response to Concurrent Prolog, Clark and Gregory propose Parlog by weakening the restrictions on the guard of the Relational language. Rather than use multiple environments, they require guards to be safe; a property that is undecidable. They abandon producer annotations and use input output argument modes assigned on a per relation basis as done by Belia et al. [1980].

1985 FGCS project produces first PSI (Personal Sequential Inference Machine) with SIMPOS operating system written in object oriented extension of Prolog, KL0.

Read-only unification turns out to be order dependent [Ueda, 1985a; Saraswat, 1986] and multiple environments are difficult to implement. Under the influence of Parlog, Ueda [1985b] transforms Concurrent Prolog into GHC (Guarded Horn Clauses). GHC uses a single binding environment and dispenses with read-only variables. The guard is used as a runtime safety check. GHC programs have a greater tendency to deadlock. Body goals are allowed to be spawned before commitment, which causes a large amount of speculative computation. The principle criticism of the synchronization mechanism is that it fails to be modular: the behaviour depends on the nesting of subsequent guard calls.

Because of difficulties with implementation of multiple environments, Concurrent Prolog goes flat: (only primitives in the guard). Semantic problems prompts restricted use of read-only annotations [Mierkowsky, Taylor, Shapiro, Levy and Safra, 1985]. The principle difficulty with read-only variable as a method of synchronization is that it fails to be modular: the program behaviour depends on the form of the call.

1986 Ringwood [1986] cleanses Parlog under influence of GHC: GDC (Guarded Definite Clauses) replaces misleading mode declarations by pattern matching and explicit output. Like GHC the guard is the only form of synchronization. Unlike GHC, programs are modular but guards are unsafe. Flat GDC is safe. The language is viewed as a set of indeterminate conditional rewrite rules Ringwood [1988].

1987 FGCS secures funding for further 5 years, and produces first version of multi- PSI - a number of PSI connected by a network. Multi-PSI is used to prototype PIM (Parallel Inference Machine).

Chikayama at ICOT enhances GHC (by adding Parlog-like metacalls), while simplifying it (by making it flat, FGHC) to produce KL1 (Kernel Language 1), the kernel language of FGCS. KL1 is modular and almost indistinguishable from FGDC.

1988 FGCS produce PIMOS operating system for PIM, written in KL1 and tested on multi-PSI [Chikayama et al, 1988].

AI Ltd produce Strand88 [Foster and Taylor, 1988] a commercial implementation of a restricted version of FGDC (previously known as Flat Parlog with Assignment) for distributed memory machines.

1991 FGCS produce first working PIM.

Strand Software Technologies spun off from collapse of AI Ltd produce a distributed version of Strand88.

1992 FGCS complete the 10-year research program with an international conference. FGCS software made public domain: IFS (ICOT free Software). Unfortunately software only runs on PSI and PIMs which are not sold commercially. ICOT gets extension for further two years on much reduced scale to provide implementations for Unix boxes.

1993 Ericsson produce a Strand like language with a functional syntax called Erlang [Armstrong et al, 1993]. The language is targeted at realtime programming in particular telephony applications.

References

Belia m, Degano P and Levi G (1980) A functional plus predicate logic language, in Tarnlund SA (ed) Proc of Logic Programming Workshop, Debrecen, Hungary, 334- 347

Chikayama T, Satoh H and Miyazaki T (1988) Overview of the parallel Inference Machine Operating System (PIMOS), in Proc of Int Conf on Fifth Generation Computing Systems 1988, Tokyo

Clark KL and Gregory S (1981) A relational language for parallel programming, in Proceedings ACM Conference on Functional Programming Languages and Computer Architecture (Portsmouth, NH Oct 18-22), ACM, New York, 171-178

Clark KL and Gregory S (1983) Parlog: a parallel logic programming language, TR 83/5, Imperial College and improved version with set predicates (1986) ACM Transactions on Programming Languages and Systems 8, 1-49

Clark KL, McCabe FG (1979) The control facilities of IC-Prolog, in Expert Systems in the Micro-electronic Age, ed Michie D, Edinburgh University Press

Conway ME (1963) Design of a separable transition diagram compiler, Comm ACM 6(7), 396-408

Dausmann M, Perch G and Winterstein G (1979) Concurrent logic, Proc 4th Workshop on Artificial Intelligence, Bad Honnef

Dijkstra EW (1975) Guarded commands, nondeterminacy and formal derivation of programs, Comm ACM 18, 453-57

Foster I and Taylor S (1990) Strand: New Concepts in Parallel Programming, Prentice Hall

Freidman D and Wise D (1976) CONS should not evaluate its arguments, in michaelson D (ed) Automata, Languages and Programming, Edinburgh Univ Press, 256-284

Hansson A, Haridi and Tarnlund SA (1980) Some aspects of a logic machine prototype, in Tarnlund SA (ed) Proc of Logic Programming Workshop, Debrecen, Hungary

Landin PJ (1965) A correspondence between Algol 60 and Church's lambda- Notation, parts I and II, Comm ACM 8(2 & 3)

Mierkowsky C, Taylor S, Shapiro E, Levy J and Safra S (1985) The design and implementation of Flat Concurrent Prolog, TR CS85-09, Weizmann Inst

Prawitz D (1965) Natural deduction: a proff theoretical study, PhD thesis, Almqvist and Wiksell, Stockholm

Ringwood GA (1986) Parlog86 and the Dining Logicians, TR Imperial College and (1988) CACM 31, 10-25

Ringwood GA (1987) Pattern-Directed, Markovian, Linear, Guarded Definite Clause Resolution

Ringwood GA (1989) A Comparative Exploration of Concurrent Logic Languages. Knowledge Engineering Review, 4, 305-332

Saraswat VA. (1986) Problems with Concurrent Prolog, TR 86-100, Carnegie Mellon University

Shapiro EY (1983) A subset of Concurrent Prolog and its interpreter, ICOT TR-003, Tokyo

Sussmann GJ and McDermott DV (1972) From Planner to Coniver - a genetic approach, Proc AFIPS Fall Conference, 1171-79

van Emden MH van and De Luceana GJ (1979) Predicate logic as a language for parallel programming, TR CS 79-15, University of Waterloo and in Logic Programming, Clark KL and Tarnlund SA eds (1982), Academic Press, 189-98

Ueda K (1985a) Concurrent PROLOG re-examined, TR 102, ICOT, Tokyo

Ueda K (1985b) Guarded Horn Clauses, TR 103, ICOT Tokyo

Warren DHD (1977) Implementing Prolog - compiling predicate logic programs, TR DAI 39/40, Dept Artificial Intelligence, Edinburgh

Graem A Ringwood 
Computer Science Dept 
QMW, Univ. of London 
Mile End Rd, London E1 4NS, UK 
Tel: +44 71 975 5212
Fax: +44 81 980 6533
Email: gar@dcs.qmw.ac.uk">