Items related to Functional Implementation of Lenient Programming Languages...
Functional Implementation of Lenient Programming Languages (Research Monographs in Parallel & Distributed Computing) - Softcover
Synopsis
Modern "non-strict" functional programming languages are a powerful means of programming highly parallel computers, but are intrinsically difficult to compile well because decisions about ordering of subcomputations must be taken at compile time. This book represents a new technique for compiling such languages by partitioning a program into sequential threads. While the interleaving of threads can vary at run time, within each thread the order is fixed.A program is compiled by analyzing its data dependences, and developing from that a set of partitioning constraints. These practical algorithms are founded on a new theory of data dependence and ordering within functional programs, which defines dependence graphs in terms of a rewrite-rule operational semantics for the language.By attacking the ordering problem directly, the book departs from previous approaches that obtain partitioning as a byproduct of optimizing lazy evaluation, and cleanly separates partitioning from other code generation issues. Furthermore, the method is flexible enough to produce both lazy code and also a less restrictive "lenient" variant which allows larger threads with only a slight decrease in expressive power. Code generation and optimization are explored in depth for both uniprocessor and multiprocessor targets.Kenneth R. Traub is a researcher with the Motorola Cambridge Research Center.Contents: Introduction. Background - Functional Language Compilers. Lenient Evaluation. Functional Quads. Code Generation. A Syntactic Theory of Data Dependence. Dependence-Based Partitioning. Conclusion.
"synopsis" may belong to another edition of this title.
Synopsis
In "non-strict" functional languages, a data structure may be read before all its components are written, and a function may return a value before finishing all its computation or even before all its arguments have been evaluated. Such flexibility gives expressive power to the programmer, but makes life difficult for the compiler because it may not be possible to totally order instructions at compile time; the correct order can vary dramatically with the input data. Presently, compilers for non-strict languages rely on "lazy evaluation", in which a subexpression is not evaluated until known (at run time) to contribute to the final answer. By scheduling each subexpression separately, lazy evaluation automatically deals with the varying orderings required by non-strictness, but at the same time incurs a great deal of overhead. Recent research has employed strictness analysis and/or annotations to make more scheduling decisions at compile time, and thereby reduce the overhead, but because these techniques seek to retain laziness, they are limited in effectiveness.
This work presents an alternative compilation strategy which deals with non-strictness independent of laziness, through the analysis of data dependence. The analysis determines which instructions can be ordered at compile time and which must be scheduled at run time in order to implement non-strictness properly. The option is then presented of imposing laziness or ignoring it - and it is found that choosing the latter path can lead to significantly reduced overhead. Abandoning laziness means certain programs (those which use "infinite objects") may fail to terminate properly. It is suspected that non-strictness and not the ability to handle infinite objects is the more important feature for the programmer; nevertheless, annotations are provided for the programmer to achieve termination in the presence of infinite objects. Even with annotations, this approach entails less overhead. The strategy is discussed in the context of both sequential implementations and parallel implementations where the object code is partially sequentialized. It also show how lazy code can be generated from this framework."About this title" may belong to another edition of this title.
- PublisherFinancial Times Prentice Hall
- Publication date1990
- ISBN 10 0273088270
- ISBN 13 9780273088271
- BindingPaperback
- LanguageEnglish
- Number of pages224
(No Available Copies)
Search Books: Create a WantCan't find the book you're looking for? We'll keep searching for you. If one of our booksellers adds it to AbeBooks, we'll let you know!
Create a Want
