Parallele Implementierung funktionaler Programmiersprachen
The book under review stems from the authors PhD thesis addressing the topic of graph reduction on distributed memory multiprocessor hardware using an abstract machine model (like for example Johnsson's abstract G- machine), to improve efficiency of reduction for functional languages with lazy evaluation upon implementations on von Neumann architectures. The approach defines an applicative language SAL (Simple Applicative Language) by extending the \(\lambda\)-calculus to abstract from specific functional languages (e.g. LazyML, Mirandan, SASL etc.). A parallelizing compiler which translates a SAL program into a flat language with explicit parallelism to be executed on an abstract parallel machine is developed. The abstract parallel machine is defined by appropriate machine instructions and realizes a set of processing elements performing reductions in parallel. Because of the distributed nature of the target hardware, energy abstract processing element is (besides the reduction engine) also assigned a communication engine. A prototype implementation of the system using transputer hardware is working, but not reported in this publication in detail. SAL is based on the typed \(\lambda\)-calculus (restricted to monomorphic types) and is formally introduced by its syntax according reduction semantics. SAL expressions are syntactically built by let and case- constructs, conditions, recursion, application and \(\lambda\)-abstraction (local declarations remain allowed). Reduction employs an integrated strategy combining the advantages of completeness of the reduction semantics and the use of potentially infinite data structures of the normal-order (call-by-name) reduction, with the potential parallelism of the applicative-order (call-by-value) reduction. As an implementation technique a combination of environmental schemes and programmed graph reduction (whole activation blocks are organized in the graph structure) has been chosen according to the work of Hudak and Goldberg in the DAPS project. A parallelizing compiler first translates into a serial combinator system upon which strictness analysis (using the technique of abstract interpretation) is applied. The key for parallelization is to find out which arguments combinators are strict (strict arguments can be reduced using call-by-value, i.e. in parallel, while nonstrict arguments have to be reduced by call-by-name) - this is naturally the most `expensive' task in compilation and leads to a parallelized combinator system with explicit annotation of `useful' parallelism (syntactically: letpar). (Useful parallelism is the result of aggregating `potential' parallelism according to an assumed (not defined) complexity measure based on expected execution time and task migration overhead.) Graph reduction semantics for parallelized combinator systems defining an abstract machine presuming an arbitrary number of processors are formally introduced. The instruction set of the abstract machine (stack-, graph-, process- and control instructions) are formally specified and implemented on a distributed memory multiprocessor architecture.
- An implementation of syntax directed functional programming on nested- stack machines
- Implementing recursive functions as processor farms
- Implementation of a Pascal based parallel language for a multiprocessor computer
- HYBRID COMBINATORS FOR DISTRIBUTED EVALUATION OF FUNCTIONAL PROGRAMS
- Distributed computation by graph reduction
- scientific article; zbMATH DE number 3942995 (Why is no real title available?)
- scientific article; zbMATH DE number 4052997 (Why is no real title available?)
- scientific article; zbMATH DE number 48833 (Why is no real title available?)
- scientific article; zbMATH DE number 194911 (Why is no real title available?)
- scientific article; zbMATH DE number 3307150 (Why is no real title available?)
- A chemical abstract machine for graph reduction extended abstract
This page was built for publication: Parallele Implementierung funktionaler Programmiersprachen
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3993453)