[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

-------------------------------------------------------------------------------