CMPS 574 Advanced Seminar in
         Computer Systems Design
Spring 1984

Focus on experimental research

Languages
  Backus FP
  Smalltalk
  Prolog
  Actors
  Flow Graph Lisp (FGL)
  Data Driven Nets (DDN)
  Single assignment languages
  Production systems

Architectures
  Data driven dataflow
  Demand driven dataflow
  Reduction engines
  Relational database machines
  Message passing
  Associative/content addressable memories

Projects
  Production system implementation
    YACC translator from programming language to internal database.
    Interpreter and on-line program debugger.
    Support routines (Input/output, symbol manipulation, etc.)
  Dataflow programming system.
    Translator, interpreter and support routines.
    Graphical program editor and execution environment.
  Apply Prolog to a large problem such as a VLSI design tool,
    programmer's assistant, circuit troubleshooter, etc.
  Dataflow + backtracking + retraction.
    Translator, interpreter and support routines.
  Object oriented programming system.
    Translator, interpreter and support routines.
  Apply dataflow to graphics or signal processing problem.
  VLSI implementation of co-processors, etc. (Requires a long
    term commitment to test and report fabrication results.)
  Import and document an existing programming system.

*********
Overviews
*********

Philip C. Treleaven, et al., Data-driven and demand-driven computer
architecture, Computing Survey, ACM, Vol. 14, No. 1, March 1982,
pg. 93-143.

Alan L. Davis and Paul J. Drongowski, Dataflow computers: A tutorial
and survey, Dept. of Computer Science, University of Utah,
Technical Report UUCS-80-109, July 1980.

Alan L. Davis, Computer architecture, IEEE Spectrum, Vol. 20, No. 11,
November 1983, pg. 94-99.

IEEE Spectrum, Special issue on the 5th Generation, Vol. 20, No. 11,
November 1983, pg. 94-99.

********************
Data driven dataflow
********************

Jack B. Dennis, Dataflow supercomputers, Computer, Vol. 13, No. 11,
IEEE Computer Society, November 1980, pg. 48-56.

Jack B. Dennis and David P. Misunas, A computer architecture for
highly parallel signal processing, Proc. 1974 NCC, AFIPS, 1974,
pg. 402-409.

Arvind, Decomposing a program for multiple processor systems,
Proc. 1980 International conference on Parallel Processing, pg. 7-14.

Alan L. Davis, The architecture and system method of DDM1:
A recursively structured data driven machine, Proc. 5th
Annual Symposium on Computer Architecture, ACM, April 1978,
pg. 210-215.

Alan L. Davis, A dataflow evaluation system based on the
concept of recursive locality, Proc. 1979 NCC, AFIPS,
June 1979, pg. 1079-1086.

J.C. Syre, D. Comte, and N. Hifdi, Pipelining, parallelism
and asynchronism in the LAU system, Proc. 1977 International
Conference on Parallel Processing, August 1977, pg. 87-92.

P.C. Treleaven, Exploiting program concurrency in computing
systems, Computer, IEEE Computer Society, Vol. 12, No. 1,
January 1979, pg. 42-49.

P.C. Treleaven, VLSI: Machine architecture and very high level
languages, SIGARCH Computer Architecture News, ACM, Vol. 8,
No. 7, 1980.

Ian Watson and John Gurd, A prototype data flow computer
with token labeling, NCC, AFIPS, June 1979, pg. 623-628.

D.D. Gajski, et al., Dependence driven computation,
Proc. IEEE CompCon'81, IEEE Computer Society, February 1981,
pg. 156-161.

J.A. Sharp, Some thoughts on data flow architectures,
SIGARCH Computer Architecture News, ACM, Vol. 8, No. 4,
June 1980, pg. 11-21.

**********
Petri Nets
**********

James L. Peterson, Petri Nets, Computing Surveys, ACM,
Vol. 9, No. 3, September 1977, pg. 223-252.

James L. Peterson, Petri net theory and the modeling of systems,
Prentice-Hall Inc., 1981.

******
Theory
******

John J. Horning and Brian Randell, Process structuring,
Computing Surveys, ACM, Vol. 5, No. 1, March 1973, pg. 5-30.

Irene Grief, A language for formal problem specification, CACM,
Vol. 20, No. 12, December 1977, pg. 931-935.

Leslie Lamport, Time, clocks and the ordering of events in
a distributed system, CACM, Vol. 21, No.2, July 1978, pg. 558-564.

V.M. Glushkov, et al., Recursive machines and computing technology,
IFIP '74, IFIPS, 1974, pg. 65-70.

Robert Kowalski, Algorithm = Logic + Control, CACM,
Vol. 22, No. 7., July 1979, pg. 424-436.

******************
Associative memory
******************

Kenneth J. Thurber and Leon D. Wald, Associative and parallel
processors, Computing Surveys, ACM, Vol. 7, No. 4, December
1975, pg. 215-255.

Arvind and Kim P. Gostelow, A computer capable of exchanging
processors for time, Proc. IFIP Congress, 1977, pg. 849-854.

A. Plas, et al., LAU system architecture: A parallel data driven
processor based on single assignment, Proc. 1976 International
Conference on Parallel Processing, August 1976, pg. 293-302.

*********************
Programming languages
*********************

E.A. Ashcroft and W.W. Wadge, LUCID, a nonprocedural language
with iteration, CACM, Vol. 20, No. 7, July 1977, pg. 519-526.

John Backus, Can programming be liberated from the von Neumann
style? A functional style and its algebra of programs,
CACM, Vol. 21, No. 8, August 1978, pg. 613-641.

M.R. Sleep, Applicative languages, dataflow and pure
combinatory code, Proc. IEEE CompCon'80, IEEE Computer Society,
February 1980, pg. 112-115.

D.A. Turner, A new implementation technique for applicative
languages, Software Practice and Experience, September 1979,
pg. 31-49.

D.A. Turner, Another algorithm for bracket abstraction,
Journal of Symbolic Logic, Vol. 44, No. 2, June 1979, pg. 267-270.

A. Bahrs, Programming language semantics and closed applicative
languages, Proc. ACM Symposium on Principles of Programming
Languages, ACM, 1972, pg. 71-86.

D.P. Friedman and D.S. Wise, Aspects of applicative programming
for parallel processing, IEEE Trans. on Computers, Vol. C-27,
No. 4, April 1978, pg. 289-296.

*****************
Reduction engines
*****************

Klaus J. Berkling, A computing machine based on tree structures,
IEEE Trans. on Computers, Vol. C-20, No. 4, January 1971,
pg. 404-418.

Klaus J. Berkling, Reduction languages for reduction machines,
Proc. 2nd International Symposium on Computer Architecture,
IEEE, January 1975, pg. 133-140.

Klaus J. Berkling, Computer architecture for correct programming,
Proc. 4th Symposium on Computer Architecture, ACM, April 1978,
pg. 78-84.

G.A. Mago, A cellular computer architecture for functional
programming, Proc. IEEE CompCon'80, IEEE Computer Society,
February 1980, pg. 179-187.

**********************
Demand driven dataflow
**********************

Robert M. Keller, Suhas Patil and Gary Lindstrom,
An architecture for a loosely coupled parallel processor,
Dept. of Computer Science, University of Utah, Technical
Report UUCS-78-105, October 1978.

Robert M. Keller, Suhas Patil and Gary Lindstrom,
A loosely coupled applicative multiprocessing system,
Proc. NCC 1979, AFIPS, June 1979, pg. 861-870.

L.G. Tesler and H.G. Enea, A language design for parallel processes,
SJCC, AFIPS, 1968, pg. 403-408.

***********************
Message passing systems
***********************

R. Atkinson and C. Hewitt, Synchronization in actor systems,
Proc. 4th ACM Conference on Principles of Programming Languages,
January 1977, pg. 267-280.

C. Hewitt, Viewing control structures as patterns of passing
messages, Artificial Intelligence, Vol. 8, No. 3, June 1977,
pg. 323-364.

C. Hewitt and H. Baker, Laws for communicating parallel
processes, IFIP 1977, July 1977, pg. 987-992.

J.F. Shoch, An overview of the programming language Smalltalk-72,
SIGPLAN Notices, ACM, Vol. 14, No. 9, September 1979, pg. 64-73.

Byte, Smalltalk issue, Byte magazine, Vol. 6, No. 8, August 1981.

Adele Goldberg and David Robson, Smalltalk-80: The Language and
its Implementation, Addison Wesley, 1983.

Adele Goldberg, Smalltalk-80: The Interactive Programming
Environment, Addison Wesley, 1984.

Glenn Krasner, Smalltalk-80: Bits of history, Words of Advice,
Addison Wesley, 1983.

**************
Expert systems
**************

Dana S. Nau, Expert computer systems, Computer, Vol. 16, No.2,
IEEE Computer Society, February 1983, pg. 63-85.

Gerald J. Sussman and Drew V. McDermott, From PLANNER to
CONNIVER -- A genetic approach, Proc. of the FJCC,
AFIPS, Vol. 41, Part II, December 1972, pg. 1171-1179.

Daniel G. Bobrow and Bertram Raphael, New programming languages for
artificial intelligence research, Computing Surveys, ACM,
Vol. 6, No. 3, September 1974, pg. 155-174.

*****************
Database machines
*****************

Haran Boral and David J. DeWitt, Applying data flow techniques
to data base machines, Computer, Vol. 15, No. 8, IEEE
Computer Society, August 1982, pg. 57-63.

David J. DeWitt, DIRECT -- A multiprocessor organization for
supporting relational database management systems, IEEE Trans.
on Computers, Vol. C-28, No. 6, June 1979, pg. 395-406.

Haran Boral and David J. DeWitt, Processor allocation strategies
for multiprocessor database machines, ACM Trans. on Database
Systems, Vol. 6, No. 2, June 1981, pg. 227-254.