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
0 521 27724 8 paperback  14.95

Further information may be obtained and orders can be placed direct with
CUP over email to [EMAIL PROTECTED] 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.

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

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   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.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.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.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.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             TURNER'S 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.4            STATES OF EVALUATION    203
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.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

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

----------------------------------------------------------------------------
---
>From the "blurb":

Here is an introduction to functional programming and its associated
systems. A unique feature is its use of the language Haskell for teaching
both the rudiments and the finer points of the functional technique.
Haskell is a new, internationally agreed and accepted functional language
that is designed for teaching, research and applications, that has a
complete formal description, that is freely available, and that is based on
ideas that have a wide consensus. Thus it encapsulates some of the main
thrusts of functional programming itself, which is a style of programming
designed to confront the software crisis directly. Programs written in
functional languages can be built up from smaller parts, and they can also
be proved correct, important when software has to be reliable. Moreover, a
certain amount of parallelism can be extracted from functional languages
automatically.
This book serves as an introduction both to functional programming and
Haskell, and will be most useful to students, teachers and researchers in
either of these areas. An especially valuable feature are the chapters on
programming and implementation, along with a large number of exercises.
Tony Davie               Department of Mathematical and Computational
Sciences
Tel: +44 334 76161 x8136 St.Andrews University
Fax: +44 334 77068       North Haugh
[EMAIL PROTECTED]   St.Andrews
Scotland
KY16 9SS