Para-functional programming: a paradigm for programming multiprocessor systems

ABSTRACT

One of the most important pragmatic advantages of functional languages is that concurrency in a program is <i>implicit</i> -- there is no need for special constructs to express parallelism as is required in most conventional languages. Furthermore, it is fairly easy for compilers to automatically determine the concurrency as a step toward decomposing a program for execution on a suitable parallel architecture. Yet it is often the case that one knows precisely the <i>optimal decomposition</i> for execution on a particular machine, and one can never expect a compiler to determine such optimal mappings in all cases. This paper is concerned with ways to allow the programmer to <i>explicitly</i> express this mapping of program to machine, by using annotations that, given a few minor constraints, cannot alter the functional semantics of the program. We show through several detailed examples the expressiveness and conciseness of the resulting "para-functional" programming methodology, using an experimental language called <i>ParAlfl</i> based on our ideas. We also give a formal denotational description of the mapping semantics using a notion of <i>execution trees.</i>This research was supported in part by NSF Grants DCR-8403304 and DCR-8451415, and a Faculty Development Award from IBM.

REFERENCES

• 1: Arvind , Vinod Kathail, A multiple processor data flow machine that supports generalized procedures, Proceedings of the 8th annual symposium on Computer Architecture, p.291-302, May 12-14, 1981, Minneapolis, Minnesota, United States
• 2: Arvind and Gostelow, K. P. "The U-interpreter". <i>Computer 15,</i> 2 (Feb. 1982), 42--50.
• 3: Henry G. Baker, Jr. , Carl Hewitt, The Incremental Garbage Collection of Processes, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 4: Michael Beeler, Beyond the Baskett benchmark, ACM SIGARCH Computer Architecture News, v.12 n.1, p.20-31, March 1984 [doi>10.1145/641602.641605]
• 5: Burn, G. L., Hankin, C. L., and Abramsky, S. The theory and practice of strictness analysis for higher order functions. DoC 85/6, Imperial College of Science and Technology, Department of Computing, April, 1985.
• 6: F. Warren Burton, Annotations to Control Parallelism and Reduction Order in the Distributed Evaluation of Functional Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.159-174, April 1984 [doi>10.1145/2993.357241]
• 7: A. L. Davis, The architecture and system method of DDM1: A recursively structured Data Driven Machine, Proceedings of the 5th annual symposium on Computer architecture, p.210-215, April 03-05, 1978 [doi>10.1145/800094.803050]
• 8: Davis, A. L. Data driven nets: A maximally concurrent, procedural, parallel pocess representation for distributed control systems. UUCS-78--108, Univ. of Utah, July, 1978.
• 9: Deminet, J. "Experience with multiprocessor algorithms". <i>IEEE Trans. on Computers C-41,</i> 4 (April 1982), 278--287.
• 10: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
• 11: Daniel P. Friedman , Christopher T. Haynes, Constraining control, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.245-254, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318654]
• 12: Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 13: Dale H. Grit , Rex L. Page, Deleting Irrelevant Tasks in an Expression-Oriented Multiprocessor System, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.1, p.49-59, Jan. 1981 [doi>10.1145/357121.357125]
• 14: 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]
• 15: 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]
• 16: Paul Hudak , Benjamin Goldberg, Experiments in diffused combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.167-176, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802033]
• 17: Hudak, P. ALFL Reference Manual and Programmers Guide. Research Report YALEU/DCS/RR-322, Second Edition, Yale University, Oct., 1984.
• 18: Paul Hudak , Benjamin Goldberg, Distributed execution of functional programs using serial combinators, IEEE Transactions on Computers, v.34 n.10, p.881-891, Oct. 1985
• 19: Paul Hudak , Benjamin Goldberg, Serial combinators: “optimal” grains of parallelism, Proc. of a conference on Functional programming languages and computer architecture, p.382-399, January 1985, Nancy, France
• 20: Hudak, P. and Young, J. A set-theoretic characterization of function strictness in the Lambda Calculus. Research Report YALEU/DCS/RR-391, Yale University, June, 1985.
• 21: Paul Hudak , Adrienne Bloss, The aggregate update problem in functional programming systems, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.300-314, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318660]
• 22: Paul Hudak , Jonathan Young, Higher-order strictness analysis in untyped lambda calculus, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-109, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512653]
• 23: Intel Corporation. IPSC User's Guide -- Preliminary. 176455--001. Intel Corporation, July, 1985.
• 24: Johnsson. T. The G-machine: an abstract machine for graph reduction. PMG. Dept. of Computer Science, Chalmers Univ. of Tech., Feb., 1985.
• 25: Keller, R. M., Lindstrom, G., and Patil, S. A loosely-coupled applicative multi-processing system. AFIPS, AFIPS, June, 1979, pp. 613--622.
• 26: Keller, R. M., Jayaraman. B., Rose, D., Lindstrom, G. FGL programmer's guide. AMPS Technical Memo 1, Department of Computer Science, University of Utah, July, 1980.
• 27: Keller, R. M. FEL programmer's guide. AMPS TR 7. University of Utah. March, 1982.
• 28: Keller, R. M. and Lin, F.C.H. "Simulated performance of a reduction-based multiprocessor". <i>IEEE Computer 17,</i> 7 (July 1984), 70--82.
• 29: Keller, R. M. and Lindstrom, G. Approaching distributed database implementations through functional programming concepts. Int'l Conf. on Distributed Systems, May, 1985.
• 30: James R. McGraw, The VAL Language: Description and Analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.1, p.44-82, Jan. 1982 [doi>10.1145/357153.357157]
• 31: Robin Milner, A proposal for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.184-197, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802035]
• 32: Mycroft. A. <i>Abstract Interpretation and Optimizing Transformations for Applicative Programs.</i> Ph.D. Th., Univ. of Edinburgh, 1981.
• 33: Seymour Papert, Mindstorms: Children, computers, and powerful ideas, Basic Books, Inc., New York, NY, 1980
• 34: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• 35: Shapiro, E. Systolic programming: a paradigm of parallel processing. Dept. of Applied Mathematics CS84-21. The Weizmann Institute of Science. Aug., 1984.
• 36: Brian Cantwell Smith, Reflection and semantics in LISP, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.23-35, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800513]
• 37: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 38: Turner, D. A. SASL language manual. University of St. Andrews, 1976.
• 39: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France