Trends in Functional Programming Volume 1
Will be published approx. on 1. December 2000
Book
Hardback
256 pages
978-1-84150-024-9 (ISBN)
Description
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.
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.
More details
Series
Language
English
Place of publication
United Kingdom
Publishing group
Intellect
Target group
Professional and scholarly
Dimensions
Height: 229 mm
Width: 178 mm
ISBN-13
978-1-84150-024-9 (9781841500249)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
Acknowledgements i
Preface iii
I PARALLEL SYSTEMS AND PROGRAMMING 1
1 Bypassing of Channels in Eden 2
Ulrike Klusike, Ricardo Pena 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
Felix Hernandez, Ricardo Pena 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. Morazan 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 Laemmel
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
Preface iii
I PARALLEL SYSTEMS AND PROGRAMMING 1
1 Bypassing of Channels in Eden 2
Ulrike Klusike, Ricardo Pena 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
Felix Hernandez, Ricardo Pena 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. Morazan 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 Laemmel
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