Executing functional programs on a virtual tree of processors

ABSTRACT

A wide variety of computational models, including the lambda calculus, may be represented by a set of reduction rules which guide the (run-time) construction of a process tree. Even a single source of parallelism in an otherwise lazy evaluator may give rise to an exponential growth in the process tree, which must eventually overwhelm any finite architecture. We present a simple model for concurrently executing such process trees, which gives us a basis for matching the production of new tasks to the available resources. In addition, we present a generalised interpretation of a familiar topology suited to the support of large, perhaps irregular, virtual process trees on a much smaller physical network.

REFERENCES

• 1: An Asynchronous Programming Language and Computing Machine. Arvind, Gostelow K. P. and Plouffe W. UC (Irvine) report, Dept. of Computer Science, 1978.
• 2: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 3: William Allan Clark , D. Aspinall, Microprocessor and Its Application, Cambridge University Press, New York, NY, 1978
• 4: Recursive Programming Techniques. Burge W.H. Addison-Wesley, 1975.
• 5: HOPE: An Experimental Applicative Language. Burstall R.M., MacQueen D.B. and Sannella D.T. University of Edinburgh, Dept. of Computer Science, Internal Report CSR-62-8O.
• 6: A Network for the Rapid Distribution of Work. Burton F.W. and-Sleep M.R. Report CS/80/018/E. University of East Anglia, Norwich.
• 7: Communication in a Distributed Implementation of an Applicative Language. Burton F.W. and Sleep M.R. Proc. 6th ACM European regional conference on Systems Architecture, London, April 1981.
• 8: The Varieties of Data Flow Computers. Dennis J.B. Proc. 1st International Conference on Distributed Computing, Huntsville, Alabama 1979.
• 9: The Design of Special Purpose VLSI Chips. Foster M.J. and Rung H.T. IEEE COMPUTER, Jan. 1980, pp. 26-40.
• 10: Eager Beaver Evaluation on the R-ary N-cube. Grit D.H. and Page R.L. Dept. of Computer Science, Colorado State University, March 1981.
• 11: A Data Driven System for High Speed Parallel Computing. Gurd J. and Watson I. Computer Design V. 19, nos. 6, 7 (2 parts) Jun/Jul. 1980.
• 12: Peter Henderson , James H. Morris, Jr., A lazy evaluator, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.95-103, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811543]
• 13: A Loosely-Coupled Applicative Multi-Processing System. Keller R.M., Lindstrom G. and Patil S. NCC 1979, AFIPS V. 48, pp. 613-622.
• 14: FGL Programmer's Manual. Keller R.M., Jayaraman B., Rose D. and Lindstrom G. AMPS Technical Memo no. 1, Dept. of Computer Science, University of Utah, June 1980.
• 15: A Network of Microprocessors to Execute Reduction Languages, Parts 1 and 2. Magó Gyula A. Int. J. of Computer and Systems Sciences, V8, Nos. 5 and 6, Oct/Dec. 1979, pp. 349-385,
• 16: Gyula Magó, Copying operands versus copying results: A solution to the problem of large operands in FFP'S, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.93-98, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806767]
• 17: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 18: Notes on Shuffle/Exchange-type Switching Networks. Parker D.S. IEEE Trans. on Computers, vol. C-29, pp. 213-222.
• 19: The Indirect Binary n-cube Hicroprocessor Array. Pease M.C. IEEE Trans. on Computers, vol. C-26, pp. 458-473.
• 20: The Cube Connected Cycles: A Versatile Network for Parallel Computation. Preparata F.P. and Vuillemin J. Proc. 20th IEEE Conference on the Foundations of Computer Science, Puerto Rico, 1979.
• 21: A Survey of Interconnection Methods for Reconfigurable Parallel Processing Systems. Siegel J.H., McHillen R.J. and Mueller P.T.Jr. Nat. Computer Conf., 1979, pp. 529-542.
• 22: Applicative Languages, Dataflow and Pure Combinatory Code. Sleep M.R. IEEE 20th Computer Conference Digest, Feb. 1980.
• 23: Towards a Zero Assignment Parallel Processor. Sleep M.R. and Burton F.W. Proc. 2nd Int. Conf. on Distributed Computing, Paris, April 1981.
• 24: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 25: Concurrent Computing System Design at Newcastle. Treleaven P.C., Farrel E.P., Ghani N. and Jones S. Proc. ONERA Workshop on Data Driven Languages and Machines, Toulouse, Feb. 1979.
• 26: SASL Language Manual. Turner D.A. Computing Lab., University of Kent, 1979.
• 27: A New Implementation Technique for Applicative Languages. Turner D.A. Software, Practice and Experience, V. 9, pp. 31-49 (1979).
• 28: Programming Languages: Current and Future Developments. Turner D.A. Info-tech State of the Art Report, London, June 1980.
• 29: D. A. Turner, The semantic elegance of applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.85-92, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806766]
• 30: Semantics and Pragmatics of the Lambda Calculus. Wadsworth C.P. Ph.D. Thesis, Oxford, U.K. September 1971.
• 31: Communication Structures for Large Networks of Microcomputers. Wittie Larry D. IEEE Trans. on Computers, Vol. C30, no. 4, April 1981, pp. 264-273.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages, Management