Trends in Functional Programming Volume 1

This book brings together leading researchers and practitioners in the field of functional programming. The work presented here covers many aspects of the field, including: language design  proof and transformation semantics and models implementation applications type systems parallelism and distribution performance modelling and profiling programming methodologies The Editors provide a substantial introduction to a wide ranging set of papers, arranged by subject area. Appropriate overviews and summaries bring strong thematic links between chapters and sections covering: Parallel Systems and Programming Type Systems Architectures and Implementations Applications Theory The articles themselves are drawn from the First Scottish Functional Programming Workshop, held in Stirling in 1999. Central Scotland has been very influential in the development of functional programming, with notable contributions including the design, implementation and use of the SASL, Standard ML and Haskell languages.  The Workshops provide an international forum, linking a vibrant Scottish core with the wider community. As a product of this forum, the book brings a broad perspective on current research trends and practice in the field.

Table of Contents:
Acknowledgements                    i   Preface                    iii   I     PARALLEL SYSTEMS AND PROGRAMMING                    1 1     Bypassing of Channels in Eden                    2        Ulrike Klusike, Ricardo Peña and Clara Segura        1.1     Introduction               2        1.2     Eden and Bypassing               3        1.3     CoreEden and Annotated CoreEden               4        1.4     Bypassing Analysis               5        1.5     The Bypassing Protocol               6        1.6     Communication Costs and Conclusions               10   2     From GrandSim to Paradise                    11        Félix Hernández, Ricardo Peña and Fernando Rubio        2.1     Introduction               11        2.2     GrandSim               12        2.3     Eden               12        2.4     Paradise               14        2.5     Current State of the Implementation               19        2.6     Related Work, Future Work and Conclusion               19   3     BSP-based Cost Analysis of Skeletal Programs                    20        Yashushi Hayashi and Murray Cole         3.1     Introduction               20        3.2     Background and Previous Work               21        3.3     A BSP Cost Algebra               22        3.4     A VEC-BSP Implementation Strategy               23        3.5     A Cost Translation Framework               27        3.6     Example and Discussion               27        3.7     Summary and Future Work               27   4     High Level BSP Programming: BSML and BSλ                    29        4.1     Introduction               29        4.2     Explicit Processes + Flat Parallelism = Direct Mode               29        4.3     BSML               30        4.4     The BSMLlib Experiment               31        4.5     Timings for BSMLlib               33        4.6     Conclusions and Future Work               38   II     TYPES                    39 5     Deep Type Inference for Mobile Functions                    40        Stephen Gilmore        5.1     Introduction               40        5.2     Compiling to Java Byte Code               41        5.3     Understanding the Static Semantics               46        5.4     Using Deep Types to Detect Unchecked Updates               47        5.5     Related Work               48   6     Generalizing Techniques for Type Debugging                    49        Bruce J. McAdam        6.1     Introduction               49        6.2     Graphs               49        6.3     Basic Analysis of Graphs               51        6.4     Bernstein and Stark's Assumption Environments               53        6.5     Wand's Source of Type Errors               55        6.6     Duggan's Correct Type Explanations               56        6.7     Conclusions               57   7     Explaining Type Errors by Finding the Source of a Type Conflict                    58        Jun Yang        7.1     Introduction               58        7.2     Unification of Assumption Environments (μAE)               60        7.3     Incremental Error Inference               61        7.4     Conclusions               64        7.5     Acknowledgements               66   8     How to Combine the Benefits of Strict and Soft Typing                    67        Manfred Widera and Christoph Beierle         8.1     Introduction               67        8.2     The Use of Complete Type Checking               68        8.3     The Definition of Complete Subtyping               70        8.4     Conclusion and Future Work               75   III     ARCHITECTURES AND IMPLEMENTATION                    77 9     Interfacing Java with Haskell                    78        Mark Green and Ali E. Abdallah        9.1     Introduction               78        9.2     Possible Approaches               79        9.3     Java-Haskell Interface Implementation               80        9.4     Examples of Use               83        9.5     Conclusion               86   10   An Abstract Machine for Memory Management                    88        10.1   Introduction               88        10.2   Abstract Machines               89        10.3   Garbage Collection               91        10.4   Further Work               95   11   The MT Architecture and Allocation Algorithm                    97         Marco T. Morazán and Douglas R. Troeger        11.1   The MT System               97        11.2   Expected Advantages of MT               99        11.3   Experiment I: List of Fibonacci Numbers Using References to Objects               100        11.4   Experiment II: Simple Lists in MT               102        11.5   Experiment III: A List of Simple Lists               103        11.6   Summarising Remarks               104   12   ZG-machine: a Space-Efficient G-machine                    105        Gyun Woo and Taisook Han        12.1   Introduction               105        12.2   Tag-forwarding               106        12.3   Experiments               107        12.4   Summary and Related Work               112   IV     APPLICATIONS                    114 13   A Functional Design Framework for Genetic Algorithms                    115        Fethi A. Rabhi, Guy Lapalme and Albert Y. Zomaya        13.1   Introduction               115        13.2   Genetic Algorithms               116        13.3   The Single-row Routing (SRR) Problem               119        13.4   Solving the SRR Problem with the GA Framework               121        13.5   Conclusion and Future Work               123   14   An Industrial use of FP: A Tool for Generating Test Scripts from Sys-        tem Specifications                    125        Paul Baker, Clive Jervis and David J. King        14.1   Introduction               125        14.2   Motivation for Using Formal Methods               126        14.3   Formal Specification with Message Sequence Charts               126        14.4   Generating Test Scripts from MSCs               127        14.5   Implementation of ptk               129        14.6   How could Functional Languages be Improved to Better Meet the                   Requirements of Industry               131        14.7   Conclusions               132   V     THEORY                    133 15   List Homomorphisms with Accumulation and Indexing                    134        Walter Dosch and Bernd Wiedemann        15.1   Introduction               134        15.2   Data Parallel List Programming               135        15.3   List Homomorphisms With Accumulation               137        15.4   Conclusion and Related Work               141   16   Reuse by Program Transformation                    143        Ralf Lämmel        16.1   Introduction               143        16.2   Motivation by Examples               144        16.3   Transformation Operators               147        16.4   Concluding Remarks               151   17   An Abstract Machine for Parallel Lazy Evaluation                    153        Clem Baker-Finch        17.1   Introduction               153        17.2   Sequential Lazy Abstract Machines               154        17.3   Fully Speculative Evaluation               155        17.4   Parallelism with par and seq               158        17.5   Modelling Limited Resources               159        17.6   Conclusion               160   Bibliography                    162