[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
NEW BOOK
ANNOUNCING:
"An Introduction to Functional Programming Systems Using Haskell"
by A. Davie, St.Andrews University
Cambridge University Press, 1992
ISBN 0 521 25830 8 hardback #42.50 pounds
0 521 27724 8 paperback #14.95 pounds
Further information may be obtained and orders can be placed direct with
CUP over email to DT105@PHOENIX.CAMBRIDGE.AC.UK with credit cards if people
so wish, and inspection copies are available to people teaching courses.
Full details of course, enrolement and current required/recommended books
are required.
-------------------------------------------------------------------------------
TABLE OF CONTENTS
Preface xi
Chapter 1 Introduction 1
1.1 THE VON NEUMANN BOTTLENECK 1
1.2 VON NEUMANN LANGUAGES 2
1.3 PARALLELISM 3
1.4 MATHEMATICS Q A STATIC LANGUAGE 4
1.5 THE COMPLEXITY OF PROGRAMMING LANGUAGES 4
1.6 REFERENTIAL TRANSPARENCY 5
1.7 HIGHER ORDER FUNCTIONS 6
1.8 l-CALCULUS 7
1.9 IMPLEMENTATION OF FUNCTIONAL LANGUAGES 8
1.10 AREAS OF APPLICATION 8
1.11 SUMMARY 9
Chapter 2 Introduction to Functional Programs 11
2.1 GETTING STARTED 11
2.2 NAMES 13
2.3 FUNCTIONS 14
2.4 SCOPE 15
2.5 DEFINITION BY CASES 18
2.6 ALGORITHMS 18
2.7 DATA TYPES 19
2.7.1 Guards 21
2.7.2 Characters 22
2.8 LISTS 23
2.8.1 Constructing Lists 24
2.8.2 Selection 25
2.9 PATTERN MATCHING 26
2.10 TUPLES 27
2.11 SHOW 28
2.12 CONDITIONALS 28
2.13 MODULES AND THE INTERACTIVE ENVIRONMENT 30
2.14 MISCELLANEOUS POINTS 31
2.14.1 Comments 31
2.14.2 Identifiers and Operators 31
2.14.3 Layout 31
2.14.4 A few useful predeclared functions 32
2.15 SUMMARY 32
2.16 EXERCISES 32
Chapter 3 Techniques and Methods 35
3.1 INTRODUCTION 35
3.2 RECURSIVE FUNCTIONS 35
3.3 COMPLETENESS 37
3.4 HIGHER ORDER FUNCTIONS 39
3.5 SYNTAX OF FUNCTION DEFINITIONS 40
3.6 SIMULATION OF A STACK 41
3.7 MODELLING CONVENTIONAL PROGRAMMING 44
3.8 NON-LOCAL VARIABLES 45
3.9 ACCUMULATING RESULTS 46
3.10 MAPS 48
3.10.1 Maps 48
3.10.2 Filters 49
3.10.3 Folds 51
3.11 LIST COMPREHENSIONS 52
3.11.1 Translation to simpler Haskell 54
3.12 SUMMARY 55
3.13 EXERCISES 55
Chapter 4 Types 59
4.1 INTRODUCTION 59
4.2 TYPE OPERATORS 60
4.3 POLYMORPHIC TYPES 61
4.3.1 New Type Names 62
4.4 ALGEBRAIC TYPES 62
4.4.1 Pattern Matching 65
4.5 ABSTRACT TYPES 66
4.6 ARRAYS 67
4.7 TYPE INFERENCE 68
4.8 OVERLOADING 70
4.9 LAWS 73
4.10 SUMMARY 75
4.11 EXERCISES 76
Chapter 5 Lambda Calculus 79
5.1 INTRODUCTION 79
5.2 ABSTRACTION 79
5.3 REDUCTION 81
5.4 l-EXPRESSIONS 82
5.5 THE DANGERS OF SUBSTITUTION 83
5.6 MODEL OF A TEST FOR FREEDOM 85
5.7 CONVERSION 87
5.8 NORMAL FORMS 90
5.9 ORDER OF REDUCTION 92
5.10 CONVERTING HASKELL TO l-EXPRESSIONS 95
5.10.1 Expressions with definitions 96
5.10.2 Definitions within definitions 97
5.10.3 Simultaneous definitions and patterns 97
5.10.4 Recursion 99
5.10.5 Constructed Values 103
5.10.6 Patterns 103
5.10.7 Overloading 104
5.11 SUMMARY 105
5.12 EXERCISES 106
Chapter 6 Applicative Implementation 109
6.1 INTRODUCTION 109
6.2 THE SECD MACHINE 109
6.3 REPRESENTATION 112
6.4 OPERATIONAL SEMANTICS 114
6.5 AN IMPROVED SECD MACHINE 122
6.6 SECD2 MACHINE CODE 123
6.7 DROPPING STITCHES 128
6.8 FURTHER IMPROVEMENTS 128
6.9 SUMMARY 128
6.10 EXERCISES 129
Chapter 7 Lazy Evaluation 131
7.1 INTRODUCTION 131
7.2 INFINITE OBJECTS 132
7.3 STREAMS 135
7.3.1 Stream diagrams 136
7.4 LIST COMPREHENSIONS 139
7.4.1 Diagonalisation 139
7.5 INPUT/OUTPUT 140
7.6 IRREFUTABLE PATTERNS 144
7.7 MODULARITY 144
7.8 MEMO FUNCTIONS 146
7.9 SUMMARY 147
7.10 EXERCISES 147
Chapter 8 Implementation of Lazy Evaluation 149
8.1 INTRODUCTION 149
8.2 LAZY EVALUATION 150
8.3 ADAPTING THE SECD MACHINE 151
8.4 GRAPH REDUCTION 152
8.5 TURNERUS COMBINATOR MACHINE 153
8.5.1 Combinators 154
8.5.2 Translation of Haskell to Combinators 154
8.5.3 Interpreting 158
8.5.4 Book-keeping 161
8.6 THE G-MACHINE 162
8.7 TRANSFORMATION TO SUPER-COMBINATORS 163
8.8 PROGRAMS FOR THE G-MACHINE 164
8.9 STRICTNESS ANALYSIS 168
8.10 FURTHER DEVELOPMENTS 170
8.11 SUMMARY 170
8.12 EXERCISES 170
Chapter 9 Correctness 173
9.1 INTRODUCTION 173
9.2 MATHEMATICAL INDUCTION 174
9.3 INDUCTION ON LISTS 177
9.4 STRUCTURAL INDUCTION 178
9.5 INDUCTION ON FUNCTIONS 180
9.6 APPROXIMATION 180
9.7 CHAINS OF APPROXIMATIONS 182
9.8 FIXED POINT INDUCTION 184
9.9 PRACTICAL USE OF FIXED POINT INDUCTION 185
9.10 SUMMARY 187
9.11 EXERCISES 187
Chapter 10 Applicative Program Transformation 189
10.1 INTRODUCTION 189
10.2 LANGUAGE DEFINITION 189
10.3 TRANSFORMATIONS IN COMPILERS 192
10.3.1 Dependency Analysis 192
10.3.2 Transforming Pattern Matching 194
10.4 SYSTEMATIC TRANSFORMATION 195
10.5 OTHER TRANSFORMATIONS 198
10.6 SUMMARY 198
10.7 EXERCISES 198
Chapter 11 Parallel Evaluation 201
11.1 INTRODUCTION 201
11.2 EAGER EVALUATION 201
11.3 SPARKING NEW TASKS 203
11.4 STATES OF EVALUATION 203
11.5 POOLS OF TASKS 204
11.6 PARALLEL PROJECTS 204
11.6.1 ALICE 204
11.6.2 GRIP 205
11.6.3 The <n-G> Machine 205
11.6.4 Monsoon 205
11.6.5 P-RISC 205
11.6.6 Other Projects 206
11.7 STAR:DUST 206
11.7.1 Requirements 206
11.7.2 Machine Architecture 207
11.7.3 STAR:DUST as a Parallel Processor 207
11.7.4 Executing Sub-tasks in Parallel 209
11.7.5 Evaluating Suspensions 211
11.7.6 Load Distribution 211
11.8 SUMMARY 211
Bibliography 213
Appendix A Predefined Haskell Operators 227
Appendix B The Haskell Preludes 229
Prelude 230
PreludeBuiltin 233
PreludeCore 235
PreludeRatio 242
PreludeComplex 243
PreludeList 245
PreludeArray 251
PreludeText 253
PreludeIO 258
Appendix C Haskell Syntax 263
C.1 Notational Conventions 263
C.2 Lexical Syntax 264
C.3 Layout 266
C.4 Context-Free Syntax 267
C.5 Interface Syntax 271
Appendix D Haskell Class Structure 273
Index 275
-------------------------------------------------------------------------------