An Introduction to Functional Programming Through Lambda Calculus by Michaelson, Greg -- Read -- Imperial Library of Trantor

Index

Cover Page Title Page Copyright Page Preface to the Dover Edition Preface Contents Trademark notice Chapter 1 Introduction

1.1 Names and values in programming 1.2 Names and values in imperative and functional languages 1.3 Execution order in imperative and functional languages 1.4 Repetition in imperative and functional languages 1.5 Data structures in functional languages 1.6 Functions as values 1.7 The origins of functional languages 1.8 Computing and the theory of computing 1.9 λ calculus Summary

Chapter 2 λ calculus

2.1 Abstraction 2.2 Abstraction in programming languages 2.3 Introducing λ calculus 2.4 λ expressions 2.5 Simple λ functions 2.6 Introducing new syntax 2.7 Notations for naming functions and β reduction 2.8 Functions from functions 2.9 Argument selection and argument pairing functions 2.10 Free and bound variables 2.11 Name clashes and α conversion 2.12 Simplification through η reduction Summary Exercises

Chapter 3 Conditions, booleans and numbers

3.1 Truth values and conditional expression 3.2 NOT 3.3 AND 3.4 OR 3.5 Natural numbers 3.6 Simplified notations Summary Exercises

Chapter 4 Recursion and arithmetic

4.1 Repetitions, iteration and recursion 4.2 Recursion through definitions? 4.3 Passing a function to itself 4.4 Applicative order reduction 4.5 Recursion function 4.6 Recursion notation 4.7 Arithmetic operations Summary Exercises

Chapter 5 Types

5.1 Types and programming 5.2 Types as objects and operations 5.3 Representing typed objects 5.4 Errors 5.5 Booleans 5.6 Typed conditional expression 5.7 Numbers and arithmetic 5.8 Characters 5.9 Repetitive type checking 5.10 Static and dynamic type checking 5.11 Infix operators 5.12 Case definitions and structure matching Summary Exercises

Chapter 6 Lists and strings

6.1 Lists 6.2 List representation 6.3 Operations on lists 6.4 List notation 6.5 Lists and evaluation 6.6 Deletion from a list 6.7 List comparison 6.8 Strings 6.9 String comparison 6.10 Numeric string to number conversion 6.11 Structure matching with lists 6.12 Ordered linear lists, insertion and sorting 6.13 Indexed linear list access 6.14 Mapping functions Summary Exercises

Chapter 7 Composite values and trees

7.1 Composite values 7.2 Processing composite value sequences 7.3 Selector functions 7.4 Generalized structure matching 7.5 Local definitions 7.6 Matching composite value results 7.7 List inefficiency 7.8 Trees 7.9 Adding values to ordered binary trees 7.10 Binary tree traversal 7.11 Binary tree search 7.12 Binary trees of composite values 7.13 Binary tree efficiency 7.14 Curried and uncurried functions 7.15 Partial application 7.16 Structures, values and functions Summary Exercises

Chapter 8 Evaluation

8.1 Termination and normal form 8.2 Normal order 8.3 Applicative order 8.4 Consistent applicative order use 8.5 Delaying evaluation 8.6 Evaluation termination, the halting problem, evaluation equivalence and the Church-Rosser theorems 8.7 Infinite objects 8.8 Lazy evaluation Summary Exercises

Chapter 9 Functional programming in Standard ML

9.1 Types 9.2 Lists 9.3 Tuples 9.4 Function types and expressions 9.5 Standard functions 9.6 Comparison operators 9.7 Functions 9.8 Making bound variables’ types explicit 9.9 Definitions 9.10 Conditional expressions 9.11 Recursion and function definitions 9.12 Tuple selection 9.13 Pattern matching 9.14 Local definitions 9.15 Type expressions and abbreviated types 9.16 Type variables and polymorphism 9.17 New types 9.18 Trees 9.19 λ calculus in SML 9.20 Other features Summary Exercises

Chapter 10 Functional programming and LISP

10.1 Atoms, numbers and symbols 10.2 Forms, expressions and function applications 10.3 Logic 10.4 Arithmetic and numeric comparison 10.5 Lambda functions 10.6 Global definitions 10.7 Conditional expressions 10.8 Quoting 10.9 Lists 10.10 List selection 10.11 Recursion 10.12 Local definitions 10.13 Binary trees in LISP 10.14 Dynamic and lexical scope 10.15 Functions as values and arguments 10.16 Symbols, quoting and evaluation 10.17 λ calculus in LISP 10.18 λ calculus and Scheme 10.19 Other features Summary Exercises

Answers to exercises Bibliography Index Back Cover