An eductive interpreter for the language Lucid

ABSTRACT

We describe an interpreter for pLucid, a member of the Lucid family of functional dataflow languages. In appearance, pLucid is similar to Landin's Iswim, exept that individual variables and expressions denote streams (infinite sequences of data items), and function variables denote filters (stream-to-stream transformations). The actual data objects in pLucid (the components of streams) are those of POP2: numbers, strings, words, and lists. The 'inner syntax' (infix operations, conventions for denoting constants) are those of POP2 as well.The interpreter (which was written in C) is eductive: it uses a tagged demand-driven scheme. Demands for values in the output stream generate demands for values of other variables internal to the program. These demands, and the values returned in response, are tagged according to "time" (sequence index) and place (node in the tree of function calls). Once computed, values are stored in an associative memory (the "warehouse") in case they are demanded again later in the computation. The warehouse is periodically cleaned out using a heuristic called the "retirement plan". The heuristic is not perfect, but does not have to be: in an eductive computation, the program is not altered as in reduction. If discarded values are needed again, they can be recomputed.The pLucid interpreter performs extensive runtime checks and error messages quote the source line containing the offended operator. A special end-of-data object permits a very simple treatment of finite (terminating) input and output. Of special interest is its interface to UNIX, which allows any system command to be used as a filter inside a pLucid program.The interpreter performs well enough for nontrivial programs to be developed and tested. These include (simple versions of) a text formatter, a distributed airline reservation system, and a full screen editor.

REFERENCES

• 1: E. A. Ashcroft , W. W. Wadge, Lucid, a nonprocedural language with iteration, Communications of the ACM, v.20 n.7, p.519-526, July 1977 [doi>10.1145/359636.359715]
• 2: Ashcroft, E. A., Jagannathan, R. and Lee, R. (1985) Emulating Eazyflow Technical Report, Computer Science Lab., SRI International.
• 3: Bagai, R. (1986) Compilation of the Dataflow Language Lucid MS Thesis December 1986 Department of Computer Science Univeristy of Victoria, Canada.
• 4: Burstall, R. M., Collins, J. S., and Popplestone, R. J. (1971). Programming in POP-2, Edinburgh University Press, Edinburgh.
• 5: Kahn, G., and MacQueen, D. B. (1977) Coroutines and networks of parallel processes, Proc. IFIP Congress 77, Elsevier North Holland, 993-998.
• 6: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 7: Ostrum, C. B. (1981). The Luthid 1.0 Manual, Dept. of Computer Science, Univ. of Waterloo, Waterloo, Ontario Canada.
• 8: Pilgram, P. (1983). Translating Lucid dataflow into message passing actors, PhD. dissertation, Univ. of Warwick.
• 9: Wadge, W. (1985). Viscid, a vi-like screen editor written in pLucid, Proceedings 4th PCCC.

INDEX TERMS

Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LUCID
      D.3.4 Processors
          Subjects: Interpreters

General Terms:
Design, Languages