You are previewing The Functional Approach to Programming.
O'Reilly logo
The Functional Approach to Programming

Book Description

A programming course should concentrate as much as possible on a program's logical structure and design rather than simply show how to write code. The Functional Approach to Programming achieves this aim because logical concepts are evident and programs are transparent so can be written quickly and cleanly. In this book the authors emphasise the notions of function and function application which relate programming to familiar concepts from mathematics and logic. They introduce functional programming via examples but also explain what programs compute and how to reason about them. They show how the ideas can be implemented in the Caml language, a dialect of the ML family, and give examples of how complex programs from a variety of areas (such as arithmetic, tree algorithms, graph algorithms, text parsing and geometry) can be developed in close agreement with their specifications. Many exercises and examples are included throughout the book; solutions are also available.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Contents
  5. Preface
  6. Introduction
  7. I: Basic Principles
    1. 1 Expressions
      1. 1.1 Expressions and Definitions
        1. 1.1.1 Expressions
        2. 1.1.2 Definitions
        3. 1.1.3 Local Definitions
      2. 1.2 Elementary Types
        1. 1.2.1 Integers
        2. 1.2.2 Floating-Point Numbers
        3. 1.2.3 Floating Mode
        4. 1.2.4 Booleans
        5. 1.2.5 Character Strings
        6. 1.2.6 Characters
      3. 1.3 Cartesian Product
      4. 1.4 Functions
        1. 1.4.1 Defining Simple Functions
        2. 1.4.2 Function Expressions
        3. 1.4.3 Higher Order Function Expressions
        4. 1.4.4 Recursive Functions
        5. 1.4.5 Mutually Recursive Functions
        6. 1.4.6 Functions Defined by Case
        7. 1.4.7 The function Construction
        8. 1.4.8 The match with Construction
      5. 1.5 Polymorphism
        1. 1.5.1 Type Variables
        2. 1.5.2 Type Synthesis
      6. 1.6 About Syntax
        1. 1.6.1 Application Notation
        2. 1.6.2 Syntactic Analysis of Caml Expressions
        3. 1.6.3 Infix Operators Defined by the User
      7. 1.7 Scope of Identifiers
      8. 1.8 More about Function Types: Equivalent Function Spaces
        1. 1.8.1 The Types of Predefined Operators
      9. 1.9 Examples: Expressive Power
        1. 1.9.1 Bounded Iterations
        2. 1.9.2 Unbounded Iterations
        3. 1.9.3 Binary Method
        4. 1.9.4 Newton’s Method
        5. 1.9.5 About Iteration
        6. 1.9.6 Summations
      10. 1.10 Summary
      11. 1.11 To Learn More
    2. 2 Data Structures
      1. 2.1 Record or Named Cartesian Products
      2. 2.2 Sums with Constructors
        1. 2.2.1 Constant Constructors
        2. 2.2.2 Constructors with Arguments
        3. 2.2.3 Types with Only One Constructor and Abbreviations
        4. 2.2.4 Recursive Types
        5. 2.2.5 Polymorphic Types
        6. 2.2.6 Lists
        7. 2.2.7 Recursive Definitions of Values
        8. 2.2.8 Abstract Types
        9. 2.2.9 Concrete Syntax of Data Structures
      3. 2.3 Lists
        1. 2.3.1 General Functionals for Lists
        2. 2.3.2 Partitioning and Sorting
        3. 2.3.3 Representing Sets by Lists
        4. 2.3.4 Searching in a List
      4. 2.4 Summary
      5. 2.5 To Learn More
    3. 3 Semantics
      1. 3.1 Evaluation
        1. 3.1.1 Evaluation as Rewriting Expressions
        2. 3.1.2 Evaluation Strategies
        3. 3.1.3 How to Deal with Recursion
        4. 3.1.4 Another Way of Handling Recursion
        5. 3.1.5 Behavior of Evaluation Processes
      2. 3.2 Defining Strategies
        1. 3.2.1 The Caml Strategy, or Evaluation by Value
        2. 3.2.2 Another Strategy: Delayed Evaluation
        3. 3.2.3 Extending Delayed Evaluation to Data Structures
      3. 3.3 Program Semantics
        1. 3.3.1 Rewrite Semantics
        2. 3.3.2 Denotational Semantics
      4. 3.4 Proving the Correctness of Programs
        1. 3.4.1 Equational Reasoning
        2. 3.4.2 Taking Functions as Values into Account
        3. 3.4.3 Reasoning by Case
        4. 3.4.4 Reasoning by Induction
        5. 3.4.5 Proof of Termination
        6. 3.4.6 First Example: Mirror Image of Trees
        7. 3.4.7 Second Example: Associativity of append
        8. 3.4.8 Example: Using Generalization
        9. 3.4.9 Example: Using Lemmas
        10. 3.4.10 Example: Proof under Hypothesis or Proof by Assumption
      5. 3.5 Typing Expressions
      6. 3.6 Summary
      7. 3.7 To Learn More
    4. 4 Imperative Aspects
      1. 4.1 Exceptions
        1. 4.1.1 Examples of Exceptions
        2. 4.1.2 Defining Exceptions
        3. 4.1.3 Creating an Exceptional Value
        4. 4.1.4 Filtering Exceptional Values
        5. 4.1.5 Using Exceptions
      2. 4.2 Input and Output
        1. 4.2.1 Sequence
        2. 4.2.2 The Type unit
        3. 4.2.3 I/O Functions
        4. 4.2.4 Example: Print Function
        5. 4.2.5 Example: Interaction
      3. 4.3 Character Streams
        1. 4.3.1 Constructing Streams
      4. 4.4 Modifiable Data Structures
        1. 4.4.1 Vectors
        2. 4.4.2 Records with Modifiable Fields
        3. 4.4.3 References
        4. 4.4.4 Circular Lists
        5. 4.4.5 Doubly Linked Lists
        6. 4.4.6 Comparing with Pascal, C, and Lisp
      5. 4.5 Semantics of Destructive Operations
      6. 4.6 Summary
      7. 4.7 To Learn More
  8. II: Applications
    1. 5 Formal Terms, Pattern Matching, Unification
      1. 5.1 Trees
        1. 5.1.1 A Few Useful Functions
        2. 5.1.2 Functionals for Trees
        3. 5.1.3 Occurrences in a Tree
        4. 5.1.4 Trees and Abstract Syntax
      2. 5.2 Terms with Variables
        1. 5.2.1 Introducing Variables
        2. 5.2.2 Substitutions
        3. 5.2.3 Filtering and Pattern Matching
        4. 5.2.4 Unification
      3. 5.3 Application: Type Synthesis
        1. 5.3.1 Constraints on Types
        2. 5.3.2 Generating Constraints
        3. 5.3.3 Constraint Resolution
      4. 5.4 Summary
      5. 5.5 To Learn More
    2. 6 Balanced Trees
      1. 6.1 Binary Trees
      2. 6.2 Tree Traversais and Morphisms
      3. 6.3 Order and Pre-Order Relations
      4. 6.4 Binary Search Trees
        1. 6.4.1 Searching for an Element
        2. 6.4.2 Adding an Element
        3. 6.4.3 Adding an Element to the Root
        4. 6.4.4 Removing an Element
      5. 6.5 Balanced Trees
        1. 6.5.1 Rotations
        2. 6.5.2 AVL Trees
        3. 6.5.3 Adding Elements to an AVL Tree
        4. 6.5.4 Removing Elements from an AVL Tree
      6. 6.6 Dictionaries
      7. 6.7 Ordered Sets
      8. 6.8 Functional Queues
      9. 6.9 Summary
      10. 6.10 To Learn More
    3. 7 Graphs and Problem Solving
      1. 7.1 Algorithms to Explore Graphs
        1. 7.1.1 Naive Breadth-First Search
        2. 7.1.2 Naive Depth-First Search
        3. 7.1.3 Optimal Breadth-First Search
        4. 7.1.4 Variations and Improvements
        5. 7.1.5 Optimal Depth-First Search
        6. 7.1.6 Exhaustive Search
        7. 7.1.7 Computing Connected Components
      2. 7.2 The Red Donkey
      3. 7.3 The Game of Solitaire
      4. 7.4 Summary
      5. 7.5 To Learn More
    4. 8 Syntactic Analysis
      1. 8.1 Regular Expressions
      2. 8.2 Context-Free Grammar
        1. 8.2.1 Types and Values
        2. 8.2.2 Ambiguities
      3. 8.3 Recognizers
        1. 8.3.1 Recognizer Constructors
        2. 8.3.2 Limitations
        3. 8.3.3 Recognizers for Regular Expressions
        4. 8.3.4 Recognizers for Grammars
        5. 8.3.5 Various Derived Forms
      4. 8.4 Analysis = Recognition + Values
        1. 8.4.1 Constructors for Analyzers
        2. 8.4.2 A Lexical Analyzer
        3. 8.4.3 Analyzer for Nested Parentheses
        4. 8.4.4 Derived Forms and Higher Order Analyzers
        5. 8.4.5 An Analyzer for Arithmetic Expressions
        6. 8.4.6 Predictive Analysis
      5. 8.5 Streams and Pattern Matching
        1. 8.5.1 Streams
        2. 8.5.2 Stream Pattern Matching
        3. 8.5.3 Lexical Analysis by Stream Pattern Matching
        4. 8.5.4 Higher Order Analyzers
        5. 8.5.5 Syntactic Analysis by Stream Pattern Matching
      6. 8.6 Compiling Regular Expressions
        1. 8.6.1 Finite Automata
        2. 8.6.2 Abstract Syntax Trees for Regular Expressions
        3. 8.6.3 Computing Null, First, and Last
        4. 8.6.4 Computing follow
        5. 8.6.5 Representing Automata
        6. 8.6.6 Computing Automata
        7. 8.6.7 Interpreting a Deterministic Finite Automaton
      7. 8.7 Summary
      8. 8.8 To Learn More
        1. 8.8.1 Comparing with Other Methods of Syntactic Analysis
        2. 8.8.2 Further References
    5. 9 Geometry and Drawings
      1. 9.1 Meet MLgraph
        1. 9.1.1 Geometric Plane
        2. 9.1.2 Geometric Elements
        3. 9.1.3 Constructing Images
      2. 9.2 Drawing Trees
        1. 9.2.1 Drawing Principles
        2. 9.2.2 Computing the Reduction Coefficients
      3. 9.3 Tiling
        1. 9.3.1 The Method Used
        2. 9.3.2 Generating Transformations
        3. 9.3.3 Colored Tilings
        4. 9.3.4 Handling Transformations Formally
      4. 9.4 Tiling a Hyperbolic Plane
        1. 9.4.1 Complex Arithmetic
        2. 9.4.2 Hyperbolic Isometries
        3. 9.4.3 Escher’s Fish
        4. 9.4.4 The Isometry Group
        5. 9.4.5 Escher’s Circle Limit III
      5. 9.5 Summary
      6. 9.6 To Learn More
        1. 9.6.1 About PostScript
        2. 9.6.2 About Drawing Trees
        3. 9.6.3 About Tilings
    6. 10 Exact Arithmetic
      1. 10.1 Representing Integers by Lists
        1. 10.1.1 Choosing a Base
        2. 10.1.2 Operations with the Least Significant Digit at the Head
        3. 10.1.3 Comparisons as Operations
        4. 10.1.4 Division as an Operation
        5. 10.1.5 A Type for Natural Numbers (Integers for Counting)
        6. 10.1.6 Exponentiation
        7. 10.1.7 Computing Square Roots
        8. 10.1.8 Reading and Printing Natural Numbers
      2. 10.2 Other Representations of Natural Numbers
        1. 10.2.1 Doubly Linked Circular Lists
        2. 10.2.2 Arrays
      3. 10.3 Signed Integers, Both Negative and Positive
      4. 10.4 Rational Numbers
      5. 10.5 An Application: Computing π
      6. 10.6 Summary
      7. 10.7 To Learn More
  9. III: Implementation
    1. 11 Evaluation
      1. 11.1 Evaluation with the Help of Environments
      2. 11.2 Writing an Evaluator in Caml
      3. 11.3 Evaluation by Necessity = Lazy Evaluation = Delayed Evaluation
      4. 11.4 Summary
      5. 11.5 To Learn More
    2. 12 Compilation
      1. 12.1 A Simplified Model of Computer Memory
      2. 12.2 Implementation of Data Structures
        1. 12.2.1 Coding Data
        2. 12.2.2 CONS as an Operation
        3. 12.2.3 Sharing Data
        4. 12.2.4 Representing Other Types of Data
        5. 12.2.5 Recovering Allocated Memory
      3. 12.3 Producing Code
        1. 12.3.1 List of Instructions
        2. 12.3.2 Principle behind Compilation
        3. 12.3.3 About the Compilation Scheme
      4. 12.4 Implementation
        1. 12.4.1 Code Simulation
        2. 12.4.2 Producing Code
      5. 12.5 Examples
      6. 12.6 Summary
      7. 12.7 To Learn More
    3. 13 Type Synthesis
      1. 13.1 Type Rules
        1. 13.1.1 Polymorphism by Substitution
        2. 13.1.2 Parametric Polymorphism
        3. 13.1.3 Generalizing Type Schemes
        4. 13.1.4 Instantiation
        5. 13.1.5 Type Rules with Parametric Polymorphism
      2. 13.2 Writing a Program to Synthesize Types
        1. 13.2.1 Generalizing a Type
        2. 13.2.2 Instantiation
        3. 13.2.3 A Few Utilities
        4. 13.2.4 Main Function
        5. 13.2.5 Examples
      3. 13.3 Synthesizing Types by Destructive Unification
        1. 13.3.1 Destructive Unification
        2. 13.3.2 Instantiation and Generalization
        3. 13.3.3 The Algorithm for Synthesis
      4. 13.4 Summary
      5. 13.5 To Learn More
  10. Quick Reference to the Syntax of Caml Light
  11. How to Get Caml, MLgraph, and the Examples
  12. References
  13. Index
  14. Index of Types and Functions