An Introduction to Functional Programming Through Lambda Calculus

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0009.djvu
Preface......Page __sk_0003.djvu
1. Introduction......Page __sk_0015.djvu
1.2 Names and values in imperative and functional languages......Page __sk_0016.djvu
1.3 Execution order in imperative and functional languages......Page __sk_0017.djvu
1.4 Repetition in imperative and functional languages......Page __sk_0019.djvu
1.5 Data structures in functional languages......Page __sk_0021.djvu
1.6 Functions as values......Page __sk_0022.djvu
1.7 The origins of functional languages......Page __sk_0023.djvu
1.8 Computing and the theory of computing......Page __sk_0025.djvu
1.9 lambda calculus......Page __sk_0027.djvu
Summary......Page __sk_0028.djvu
2. lambda calculus......Page __sk_0029.djvu
2.1 Abstraction......Page __sk_0030.djvu
2.2 Abstraction in programming languages......Page __sk_0033.djvu
2.3 Introducing lambda calculus......Page __sk_0034.djvu
2.4 lambda expressions......Page __sk_0035.djvu
2.5 Simple lambda functions......Page __sk_0037.djvu
2.6 Introducing new syntax......Page __sk_0044.djvu
2.8 Functions from functions......Page __sk_0045.djvu
2.9 Argument selection and argument pairing functions......Page __sk_0047.djvu
2.10 Free and bound variables......Page __sk_0052.djvu
2.11 Name clashes and a conversion......Page __sk_0057.djvu
2.12 Simplification through eta reduction......Page __sk_0058.djvu
Summary......Page __sk_0059.djvu
Exercises......Page __sk_0061.djvu
3. Conditions, booleans and numbers......Page __sk_0063.djvu
3.1 Truth values and conditional expression......Page __sk_0064.djvu
3.2 NOT......Page __sk_0065.djvu
3.3 AND......Page __sk_0066.djvu
3.4 OR......Page __sk_0068.djvu
3.5 Natural numbers......Page __sk_0069.djvu
3.6 Simplified notations......Page __sk_0073.djvu
Summary......Page __sk_0075.djvu
Exercises......Page __sk_0076.djvu
4. Recursion and arithmetic......Page __sk_0079.djvu
4.1 Repetitions, iteration and recursion......Page __sk_0080.djvu
4.2 Recursion through definitions?......Page __sk_0082.djvu
4.3 Passing a function to itself......Page __sk_0083.djvu
4.4 Applicative order reduction......Page __sk_0086.djvu
4.5 Recursion function......Page __sk_0087.djvu
4.6 Recursion notation......Page __sk_0091.djvu
4.7 Arithmetic operations......Page __sk_0092.djvu
Summary......Page __sk_0096.djvu
Exercises......Page __sk_0098.djvu
5. Types......Page __sk_0101.djvu
5.1 Types and programming......Page __sk_0102.djvu
5.2 Types as objects and operations......Page __sk_0103.djvu
5.3 Representing typed objects......Page __sk_0105.djvu
5.4 Errors......Page __sk_0106.djvu
5.5 Booleans......Page __sk_0108.djvu
5.6 Typed conditional expression......Page __sk_0111.djvu
5.7 Numbers and arithmetic......Page __sk_0112.djvu
5.8 Characters......Page __sk_0115.djvu
5.9 Repetitive type checking......Page __sk_0118.djvu
5.11 Infix operators......Page __sk_0121.djvu
5.12 Case definitions and structure matching......Page __sk_0122.djvu
Summary......Page __sk_0125.djvu
Exercises......Page __sk_0127.djvu
6. Lists and strings......Page __sk_0129.djvu
6.1 Lists......Page __sk_0130.djvu
6.2 List representation......Page __sk_0133.djvu
6.3 Operations on lists......Page __sk_0136.djvu
6.4 List notation......Page __sk_0138.djvu
6.6 Deletion from a list......Page __sk_0141.djvu
6.7 List comparison......Page __sk_0143.djvu
6.8 Strings......Page __sk_0145.djvu
6.9 String comparison......Page __sk_0146.djvu
6.10 Numeric string to number conversion......Page __sk_0148.djvu
6.11 Structure matching with lists......Page __sk_0153.djvu
6.12 Ordered linear lists, insertion and sorting......Page __sk_0154.djvu
6.13 Indexed linear list access......Page __sk_0156.djvu
6.14 Mapping functions......Page __sk_0160.djvu
Summary......Page __sk_0164.djvu
Exercises......Page __sk_0165.djvu
7. Composite values and trees......Page __sk_0167.djvu
7.1 Composite values......Page __sk_0168.djvu
7.2 Processing composite value sequences......Page __sk_0169.djvu
7.3 Selector functions......Page __sk_0171.djvu
7.4 Generalized structure matching......Page __sk_0174.djvu
7.6 Matching composite value results......Page __sk_0178.djvu
7.7 List inefficiency......Page __sk_0181.djvu
7.8 Trees......Page __sk_0182.djvu
7.9 Adding values to ordered binary trees......Page __sk_0183.djvu
7.10 Binary tree traversal......Page __sk_0187.djvu
7.11 Binary tree search......Page __sk_0188.djvu
7.12 Binary trees of composite values......Page __sk_0190.djvu
7.13 Binary tree efficiency......Page __sk_0192.djvu
7.14 Curried and uncurried functions......Page __sk_0193.djvu
7.15 Partial application......Page __sk_0195.djvu
Summary......Page __sk_0197.djvu
Exercises......Page __sk_0198.djvu
8. Evaluation......Page __sk_0201.djvu
8.1 Termination and normal form......Page __sk_0202.djvu
8.2 Normal order......Page __sk_0203.djvu
8.3 Applicative order......Page __sk_0204.djvu
8.4 Consistent applicative order use......Page __sk_0205.djvu
8.5 Delaying evaluation......Page __sk_0207.djvu
8.6 Evaluation termination, the halting problem, evaluation equivalence and the Church-Rosser theorems......Page __sk_0210.djvu
8.7 Infinite objects......Page __sk_0211.djvu
8.8 Lazy evaluation......Page __sk_0213.djvu
Summary......Page __sk_0218.djvu
Exercises......Page __sk_0219.djvu
9. Functional programming in Standard ML......Page __sk_0221.djvu
9.1 Types......Page __sk_0222.djvu
9.2 Lists......Page __sk_0223.djvu
9.3 Tuples......Page __sk_0224.djvu
9.4 Function types and expressions......Page __sk_0225.djvu
9.5 Standard functions......Page __sk_0226.djvu
9.7 Functions......Page __sk_0232.djvu
9.8 Making bound variables\' types explicit......Page __sk_0233.djvu
9.9 Definitions......Page __sk_0234.djvu
9.11 Recursion and function definitions......Page __sk_0235.djvu
9.12 Tuple selection......Page __sk_0236.djvu
9.13 Pattern matching......Page __sk_0237.djvu
9.14 Local definitions......Page __sk_0239.djvu
9.15 Type expressions and abbreviated types......Page __sk_0240.djvu
9.16 Type variables and polymorphism......Page __sk_0241.djvu
9.17 New types......Page __sk_0244.djvu
9.18 Trees......Page __sk_0248.djvu
9.19 lambda calculus in SML......Page __sk_0251.djvu
Exercises......Page __sk_0252.djvu
10. Functional programming and LISP......Page __sk_0257.djvu
10.1 Atoms, numbers and symbols......Page __sk_0258.djvu
10.3 Logic......Page __sk_0259.djvu
10.4 Arithmetic and numeric comparison......Page __sk_0260.djvu
10.5 Lambda functions......Page __sk_0262.djvu
10.6 Global definitions......Page __sk_0264.djvu
10.7 Conditional expressions......Page __sk_0265.djvu
10.8 Quoting......Page __sk_0266.djvu
10.9 Lists......Page __sk_0267.djvu
10.10 List selection......Page __sk_0269.djvu
10.11 Recursion......Page __sk_0270.djvu
10.13 Binary trees in LISP......Page __sk_0271.djvu
10.14 Dynamic and lexical scope......Page __sk_0273.djvu
10.15 Functions as values and arguments......Page __sk_0275.djvu
10.16 Symbols, quoting and evaluation......Page __sk_0277.djvu
10.17 lambda calculus in LISP......Page __sk_0279.djvu
10.18 lambda calculus and Scheme......Page __sk_0280.djvu
Exercises......Page __sk_0282.djvu
Answers to exercises......Page __sk_0287.djvu
Bibliography......Page __sk_0319.djvu
Index......Page __sk_0327.djvu