Pilgram, Paul Theo (1983) Translating lucid data flow into message passing actors. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Pilgram_1983.pdf - Submitted Version - Requires a PDF viewer. Download (10Mb) | Preview

Request Changes to record.

Abstract

This thesis is the first translation of full Lucid into code for von Neumann machines ("imperative code"). It demonstrates that it is possible to produce efficient code even in the presence of advanced features such as "currenting", recursive functions or operators whose semantics favour concurrency. Earlier compiled implementations stopped well short of this.

Lucid is a family of non-procedural programming languages, invented by Wadge and Ashcroft. Lucid is neither tied to any particular data algebra, nor to a particular implementation technique. However. Data Flow (with its variants) lends itself particularly well to the implementation of Lucid.

Message Passing Actors is an imperative programming technique which leaves scope for cooperating concurrency. This benefits hardware (multi—computers, transputers'') and software technology alike. In this thesis, LUX. a PASCAL-like language with Message Passing Actors, has been chosen as the target language.

It is shown that there is a subset of Lucid (a "nucleus") which has the same expressive capacity as full Lucid. The nucleus is easier to implement than full Lucid. As a prerequisite for the translation, a LUX actor equivalent is formulated for each operator of the nucleus, once and for all. The design of these operator—actors is strongly guided by the execution strategy of demand driven Data Flow (''lazy evaluation"). Their data storage is based on FIFO queues ("pipelines"). The actors operate concurrently, but they harmonise their actions by exchanging messages which follow an agreed protocol.

The translation is carried out in successive stages. First the Lucid program is transformed to make it lie entirely within the nucleus. The program is then mapped into LUX, where each operator is represented by an operatoi—actor and the references to the variables are manifested in the environment setup of these actors. Finally, the LUX code is made more efficient by the application of a variety of analysis and optimisation methods.

Lucid programs can be analysed for various properties, and the resulting information can assist the code optimisation (while also revealing program errors). Particularly important among these program analyses is a queue length determination based on Wadge’s Cycle Sum Test.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)
Library of Congress Subject Headings (LCSH):	Lucid (Computer program language), Pascal (Computer program language)
Official Date:	1983
Dates:	Date Event 1983 UNSPECIFIED
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Wadge, William W.
Sponsors:	Deutscher akademischer Austauschdienst
Extent:	x, 270 leaves
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads