Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We argue that the 'equal civil rights' principle inherent in the lambda calculus base of applicative languages may be extended to encompass parallelism. In our model, all applicative expressions are viewed as processes, whether they represent primitives such as integers, or complex higher order functions. We present an early CCS-based notation which supports an active interpretation of applicative expressions, and illustrate its generality by presenting translations of the Schonfinkel combinators to processes. In general, we may combine applicative expressions using function application. A variety of process interpretations of application are possible, reflecting a range of evaluation strategies.

REFERENCES

• 1: An Asynchronous Programming Language and Computing Machine. Arvind, Gostelow K.P. and Plouffe W. UC (Irvine) report TR114a, 1978.
• 2: 1977 ACM Turing Award Lecture. Backus J. CACM, 21, no.8, August 1978.
• 3: Recursive Programming Techniques. Burge W.H. Addison-Wesley, 1975.
• 4: F. Warren Burton , M. Ronan Sleep, Executing functional programs on a virtual tree of processors, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.187-194, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806778]
• 5: John Darlington , Mike Reeve, ALICE a multi-processor reduction machine for the parallel evaluation CF applicative languages, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.65-76, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806764]
• 6: The Varieties of Dataflow Computers. Dennis J.B. Proc. 1st. Int. Conf. on Distributed Computing, Huntsville, Alabama 1979.
• 7: CONS Should Not Evaluate Its Arguments. in Automata, Languages and Programming, ed. Michaelson and Milner. Edinburgh University Press.
• 8: Eager Beaver Evaluation on the R-ary N-cube. Grit D.H. and Page R.L. Dept. of Computer Science, Colorado State Univ., March 1981.
• 9: A Data Driven System for High Speed Parallel Computing. Gurd J. and Watson I. Computer Design 19, nos. 6 and 7, June/July 1980.
• 10: 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]
• 11: Applicative Caching. Keller R.M. and Sleep M.R. ACM Conf. on Functional Programming Languages and Computer Architectures. New Hampshire, October 1981.
• 12: A Network of Microprocessors to Execute Reduction Languages. Magó G.A. Int. J. of Computer and Systems Sciences, 8, nos. 5 and 6, October/December 1979.
• 13: A Calculus of Communicating Systems. Milner R. Springer Verlag Lecture Notes in Computer Science, no. 81.
• 14: James H. Morris , Eric Schmidt , Philip Wadler, Experience with an applicative string processing language, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-46, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567450]
• 15: Uber die Bausteine der Mathematischen Logik. Schonfinkel M. Math. Annalen, 92, 305 (1924).
• 16: 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, February 1979.
• 17: A New Implementation Technique for Applicative Languages. Turner D.A. Software - Practice and Experience, 9, pp. 31-49 (1979).
• 18: 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]
• 19: Semantics and Pragmatics of the Lambda Calculus. Wadsworth C. P. D. Phil. Thesis, Oxford, 1971.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation

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

General Terms:
Theory