Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-12-03T19:16:12.376Z Has data issue: false hasContentIssue false
  • English
  • Français

Parallel functional programming on recursively defined data via data-parallel recursion

Published online by Cambridge University Press:  01 July 1999

SUSUMU NISHIMURA  and
ATSUSHI OHORI
SUSUMU NISHIMURA
Affiliation:
Research Institute for Mathematical Sciences, Kyoto University, Sakyo-ku, Kyoto 606-8502, Japan (e-mail: [email protected], [email protected])
ATSUSHI OHORI
Affiliation:
Research Institute for Mathematical Sciences, Kyoto University, Sakyo-ku, Kyoto 606-8502, Japan (e-mail: [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This article proposes a new language mechanism for data-parallel processing of dynamically allocated recursively defined data. Different from the conventional array-based data- parallelism, it allows parallel processing of general recursively defined data such as lists or trees in a functional way. This is achieved by representing a recursively defined datum as a system of equations, and defining new language constructs for parallel transformation of a system of equations. By integrating them with a higher-order functional language, we obtain a functional programming language suitable for describing data-parallel algorithms on recursively defined data in a declarative way. The language has an ML style polymorphic type system and a type sound operational semantics that uniformly integrates the parallel evaluation mechanism with the semantics of a typed functional language. We also show the intended parallel execution model behind the formal semantics, assuming an idealized distributed memory multicomputer.

Type
Research Article
Information
Journal of Functional Programming , Volume 9 , Issue 4 , July 1999 , pp. 427 - 462
Copyright
© 1999 Cambridge University Press

Footnotes

A preliminary summary of some of the results of this article appeared in the Proceedings of the Workshop on Theory and Practice of Parallel Programming, Sendai Japan (LNCS 907, 1995, under the title “A Calculus for exploiting data parallelism on recursively defined data.”
Submit a response

Discussions

No Discussions have been published for this article.