Experiments in diffused combinator reduction

ABSTRACT

In recent years there has been a fair amount of interest both in using combinators to represent functional programs, and in using graph reduction as an underlying valuation strategy. Combining these ideas within a single framework for an “applicative architecture” is very appealing because: (1) the normally ubiquitous “environment” is eliminated, (2) the evaluation strategy becomes very simple (amenable to VLSI), and (3) there is a great potential for parallelism. We have been exploring a model of diffused combinator reduction in which the reduction process is distributed “by demand” among a network of closely-coupled processors. We have tested our ideas via simulation, with encouraging results. This research was supported in part by NSF Grant MCS-8302018 and ONR Grant N00014-84-K-0043.

REFERENCES

• 1: T. J.W. Clarke , P. J.S. Gladstone , C. D. MacLean , A. C. Norman, SKIM - The S, K, I reduction machine, Proceedings of the 1980 ACM conference on LISP and functional programming, p.128-135, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802798]
• 2: Halstead, R.H. Jr. Multiple-processor implementations of message-passing systems. Technical Report MIT/LCS/TR-198, MIT Laboratory for Computer Science, January 1978.
• 3: Halstead, R.H. Jr. Reference tree networks: virtual machine and implementation. Technical Report MIT/LCS/TR-22, MIT Laboratory for Computer Science, 1979.
• 4: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 5: Hewitt, C. Viewing control structures as patterns of passing messages. Working Paper 92, MIT, April 1976.
• 6: Carl Hewitt, The Apiary network architecture for knowledgeable systems, Proceedings of the 1980 ACM conference on LISP and functional programming, p.107-117, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802796]
• 7: Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802147]
• 8: Hudak, P. Distributed Graph Marking. Research Report 268, Yale University, January 1983.
• 9: Paul Hudak, Distributed task and memory management, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.277-289, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806728]
• 10: Hudak, P. Distributed Applicative Processing Systems: Project Goals, Motivation, and Status Report. Research Report 317, Yale University, May 1984.
• 11: Paul Hudak , David Kranz, A combinator-based compiler for a functional language, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.122-132, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800523]
• 12: Hudak, P. ALFL Reference Manual. Working Paper 1, Yale University, January 1984.
• 13: R. J. M. Hughes, Super-combinators a new implementation method for applicative languages, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.1-10, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802129]
• 14: Simon L Peyton Jones, An investigation of the relative efficiencies of combinators and lambda expressions, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.150-158, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802145]
• 15: Keller, R.M. Semantics and applications of function graphs. Technical Report UUCS-80-112, Department of Computer Science, University of Utah, October 1980.
• 16: Keller, R.M. and Lin, F.C.H. Simulated performance of a reduction-based multiprocessor. IEEE Computer 17(7):to appear, July 1984.
• 17: J. R. Kennaway , M. R. Sleep, Expressions as processes, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.21-28, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802131]
• 18: Jonathan A. Rees , Norman I. Adams IV, T: a dialect of Lisp or LAMBDA: The ultimate software tool, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.114-122, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802142]
• 19: Philip C. Treleaven , David R. Brownbridge , Richard P. Hopkins, Data-Driven and Demand-Driven Computer Architecture, ACM Computing Surveys (CSUR), v.14 n.1, p.93-143, March 1982 [doi>10.1145/356869.356873]
• 20: Turner, D.A. A new implementation technique for applicative languages. Software-Practice and Experience 9:31-49, 1979.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
      G.2.2 Graph Theory

General Terms:
Theory