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. ---------------------------------------------------------------------------- --- 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 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 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.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 ---------------------------------------------------------------------------- --- >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