An indeterminate constructor for applicative programming

ABSTRACT

This paper proposes the encapsulization and control of contending parallel processes within data structures. The advantage of embedding the contention within data is that the contention, itself, thereby becomes an object which can be handled by the program at a level above the actions of the processes themselves. This means that an indeterminate behavior, never precisely specified by the programmer or by the input, may be shared in the same way that an argument to a function is shared by every use of the corresponding parameter, an ability which is of particular importance to applicative-style programming.

REFERENCES

• 1: 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]
• 2: W. H. Burge, Recursive Programming Techniques, Reading, Massachusetts, Addison-Wesley (1975).
• 3: J. B. Dennis, First version of a data flow procedure language, Programming Symposium, Proceedings Colloque sur la Programmation, p.362-376, April 09-11, 1974
• 4: Jack B. Dennis, A language design for structured concurrency, Proceedings of the DoD Sponsored Workshop on Design and Implementation of Programming Languages, p.231-242, September 30-October 01, 1976
• 5: D. P. Friedman and D. S. Wise. CONS should not evaluate its arguments. In Automata, Languages and Programming, S. Michaelson and R. Milner (eds.), Edinburgh, Edinburgh University Press (1976), 257-284.
• 6: Daniel P. Friedman , David S. Wise, A note on conditional expressions, Communications of the ACM, v.21 n.11, p.931-933, Nov. 1978 [doi>10.1145/359642.359650]
• 7: D. P. Friedman and D. S. Wise. Applicative multiprogramming. Technical Report No. 72, Computer Science Department, Indiana University (1979).
• 8: Daniel P. Friedman , David S. Wise, An Approach to Fair Applicative Multiprogramming, Proceedings of the International Sympoisum on Semantics of Concurrent Computation, p.203-225, July 02-04, 1979
• 9: Donald I. Good , Richard M. Cohen , James Keeton-Williams, Principles of proving concurrent programs in Gypsy, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.42-52, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567757]
• 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: M. C.B. Hennessy , E. A. Ashcroft, Parameter-passing mechanisms and nondeterminism, Proceedings of the ninth annual ACM symposium on Theory of computing, p.306-311, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803420]
• 12: Keller, R. M. Denotational models for parallel programs with indeterminant operators. In Formal Description of Programming Concepts, E. J. Neuhold (ed.). Amsterdam, North-Holland (1978), 337-366.
• 13: Paul R. Kosinski, A data flow language for operating systems programming, ACM SIGPLAN Notices, v.8 n.9, p.89-94, September 1973
• 14: P. J. Landin, Correspondence between ALGOL 60 and Church's Lambda-notation: part I, Communications of the ACM, v.8 n.2, p.89-101, Feb. 1965 [doi>10.1145/363744.363749]
• 15: J. McCarthy. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems, P. Braffort and D. Hirschberg (eds.), Amsterdam, North-Holland (1963), 33-70.
• 16: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 17: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 18: J. Vuillemin. Correct and optimal implementation of recursion in a simple programming language. J. Comp. Sys. Sci. 9, (June, 1974), 332-354.
• 19: C. Wadsworth. Semantics and Pragmatics of Lambda-calculus, Ph.D. dissertation, Oxford, (1971).
• 20: R. J. Waldinger and K. N. Levitt. Reasoning about programs. Artificial Intelligence 5, 3 (Fall, 1974), 235-316.
• 21: S. A. Ward. Functional Domains of Applicative Languages, Ph.D. dissertation, M.I.T. (1974).