ACD Atlas Computing Division Distributed Computing Systems

Jump To Main Content

Jump Over Banner

Home

Jump Over Left Menu

DCS Projects: University of Warwick

W W WADGE

LUCID AS A DATAFLOW LANGUAGE

Oct 80 - Sept 83

Background

The overall aim of the project is to investigate the potential of the programming language LUCID as a serious and fairly general purpose dataflow language.

LUCID was designed by Bill Wadge and Ed Ashcroft (of the University of Waterloo in Canada). It is a purely declarative language with the property that programs can (in spite of the non procedural nature of the language) be understood as iteration or repetition (recursion is also allowed). LUCID is based on an algebra of histories, a history being an infinite sequence of data items. Operationally, a history can be thought of as a record of the changing values of a variable, history operations such as first and next can be understood in ways suggested by their names. LUCID was originally thought of as a kind of very disciplined mathematically pure single assignment language in which verification would be very much simplified. However, the dataflow interpretation has been very important in helping the direction in which LUCID has evolved.

Achievements

A LUCID interpreter (written in 'C') has bee

A book LUCID the Dataflow Programming Language is in preparation (Academic Press, 1985).

DR C WHITBY-STREVENS and D MAY

A BUILDING BLOCK SYSTEM FOR DISTRIBUTED COMPUTING

Oct 77 - April 80

Background

The increased use of distributed computing systems has made the development of the new techniques for designing and programming them essential. The aim of this was to provide a set of building blocks to support a top-down design process and to experiment with various topologies for a system containing a number of processors.

Achievements

The project centred around the design and implementation of a programming language called EPL, intended to be used for the implementation of distributed database systems, real-time control systems etc.

EPL is based on the idea of actors, which communicate only by sending and receiving messages. EPL separates the description of a computation from the actor which performs it. (Such a description is often called an act.) Thus many actors may be created to perform the same act (on different data). Although an act may not refer to any global variables, it may have parameters, which are initialised when an actor is created from the act, and are then treated as local variables of the actor. This provides a means to inform actors about each other's existence, thereby allowing them to communicate.

EPL allows the declaration of structures of actors, such as arrays. Once such a structure is created, all the component actors start executing simultaneously, probably exchanging messages with each other. Note that each of the actors may itself be expressed in terms of other actors. This provides a means of top-down programming, since any actor can be decomposed into a set of intercommunicating sub-actors. In fact, an actor may have no existence at run-time, serving only to encapsulate a group of smaller actors.

The message sending primitives contain no buffering. Thus when an actor tries to receive a message, it waits until another actor sends it one, and when an actor tries to send a message, it waits until the target actor receives it. This provides a conceptually simple mechanism for the programmer, and it is relatively easy to implement on different architectures. However, there are arguments in favour of other schemes. For example, single buffering enables a communication system to proceed with the transmission of a message while the sender continues executing.

This project terminated in April 1980, following the resignations of Dr Whitby-Strevens and Mr May from the University to take up appointments with Inmos Ltd.

References

1. M. D. May, R. J. B. Taylor and C. Whitby-Strevens, EPL - An Experimental Language for Distributed Computing, Proceedings Trends and Applications: 1978 Distributed Processing, IEEE Computer Society, May 1978.

2. M. D. May and R. J. B. Taylor, The EPL Programming Manual', Distributed Computing Project No. 1, University of Warwick, May 1979.

3. C. Whitby-Strevens (ed), Record of a Workshop on Programming Languages for Distributed Computing; September 1978, Distributed Computing Project Report No.2, University of Warwick, June 1979.

4. C. Whitby-Strevens, On the Performance of Dijkstra's Self-Stabilising Algorithms in Spite of Distributed Control, 1st Annual Conference on Distributed Computing Systems, IEEE October 1979, pp 582-592.

5. C. Whitby-Strevens, Towards the Performance Evaluation of Distributed Computing Systems, COMPSAC '78 (in expanded form in Computer Centre Report No 18, University of Warwick, August 1978).