Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/References coverage

How to Design Programs

edit
  I  Processing Simple Forms of Data

l1  1  Students, Teachers, and Computers

l1  2  Numbers, Expressions, Simple Programs
--      2.1  Numbers and Arithmetic
--      2.2  Variables and Programs
--      2.3  Word Problems
--      2.4  Errors
--      2.5  Designing Programs

l2  3  Programs are Function Plus Variable Definitions
--      3.1  Composing Functions
--      3.2  Variable Definitions
--      3.3  Finger Exercises on Composing Functions

l2  4  Conditional Expressions and Functions
--      4.1  Booleans and Relations
--      4.2  Functions that Test Conditions
--      4.3  Conditionals and Conditional Functions
--      4.4  Designing Conditional Functions

l2  5  Symbolic Information
--      5.1  Finger Exercises with Symbols

l3  6  Compound Data, Part 1: Structures
--      6.1  Structures
--      6.2  Extended Exercise: Drawing Simple Pictures
--      6.3  Structure Definitions
--      6.4  Data Definitions
--      6.5  Designing Functions for Compound Data
--      6.6  Extended Exercise: Moving Circles and Rectangles
--      6.7  Extended Exercise: Hangman

l3  7  The Varieties of Data
--      7.1  Mixing and Distinguishing Data
--      7.2  Designing Functions for Mixed Data
--      7.3  Composing Functions, Revisited
--      7.4  Extended Exercise: Moving Shapes
--      7.5  Input Errors

    8  Intermezzo 1: Syntax and Semantics
        8.1  The Scheme Vocabulary
        8.2  The Scheme Grammar
        8.3  The Meaning of Scheme
        8.4  Errors
        8.5  Boolean Expressions
        8.6  Variable Definitions
        8.7  Structure Definitions

  II  Processing Arbitrarily Large Data

l3  9  Compound Data, Part 2: Lists
--      9.1  Lists
--      9.2  Data Definitions for Lists of Arbitrary Length
--      9.3  Processing Lists of Arbitrary Length
--      9.4  Designing Functions for Self-Referential Data Definitions
--      9.5  More on Processing Simple Lists

l3  10  More on Processing Lists
--      10.1  Functions that Produce Lists
--      10.2  Lists that Contain Structures
--      10.3  Extended Exercise: Moving Pictures

l3  11  Natural Numbers
--      11.1  Defining Natural Numbers
--      11.2  Processing Natural Numbers of Arbitrary Size
--      11.3  Extended Exercise: Creating Lists, Testing Functions
--      11.4  Alternative Data Definitions for Natural Numbers
--      11.5  More on the Nature of Natural Numbers

    12  Composing Functions, Revisited Again
        12.1  Designing Complex Programs
        12.2  Recursive Auxiliary Functions
        12.3  Generalizing Problems, Generalizing Functions
        12.4  Extended Exercise: Rearranging Words

l3  13  Intermezzo 2: List Abbreviations

  III  More on Processing Arbitrarily Large Data

    14  More Self-referential Data Definitions
        14.1  Structures in Structures
        14.2  Extended Exercise: Binary Search Trees
        14.3  Lists in Lists
        14.4  Extended Exercise: Evaluating Scheme

    15  Mutually Referential Data Definitions
        15.1  Lists of Structures, Lists in Structures
        15.2  Designing Functions for Mutually Referential Definitions
        15.3  Extended Exercise: More on Web Pages

    16  Development through Iterative Refinement
        16.1  Data Analysis
        16.2  Defining Data Classes and Refining Them
        16.3  Refining Functions and Programs

    17  Processing Two Complex Pieces of Data
        17.1  Processing Two Lists Simultaneously: Case 1
        17.2  Processing Two Lists Simultaneously: Case 2
        17.3  Processing Two Lists Simultaneously: Case 3
        17.4  Function Simplification
        17.5  Designing Functions that Consume Two Complex Inputs
        17.6  Exercises on Processing Two Complex Inputs
        17.7  Extended Exercise: Evaluating Scheme, Part 2
        17.8  Equality and Testing

    18  Intermezzo 3: Local Definitions and Lexical Scope
        18.1  Organizing Programs with local
        18.2  Lexical Scope and Block Structure

  IV  Abstracting Designs

    19  Similarities in Definitions
        19.1  Similarities in Functions
        19.2  Similarities in Data Definitions

    20  Functions are Values
        20.1  Syntax and Semantics
        20.2  Contracts for Abstract and Polymorphic Functions

    21  Designing Abstractions from Examples
        21.1  Abstracting from Examples
        21.2  Finger Exercises with Abstract List Functions
        21.3  Abstraction and a Single Point of Control
        21.4  Extended Exercise: Moving Pictures, Again
        21.5  Note: Designing Abstractions from Templates

    22  Designing Abstractions with First-Class Functions
        22.1  Functions that Produce Functions
        22.2  Designing Abstractions with Functions-as-Values
        22.3  A First Look at Graphical User Interfaces

    23  Mathematical Examples
        23.1  Sequences and Series
        23.2  Arithmetic Sequences and Series
        23.3  Geometric Sequences and Series
        23.4  The Area Under a Function
        23.5  The Slope of a Function

    24  Intermezzo 4: Defining Functions on the Fly

  V  Generative Recursion

    25  A New Form of Recursion
        25.1  Modeling a Ball on a Table
        25.2  Sorting Quickly

    26  Designing Algorithms
        26.1  Termination
        26.2  Structural versus Generative Recursion
        26.3  Making Choices

    27  Variations on a Theme
        27.1  Fractals
        27.2  From Files to Lines, from Lists to Lists of Lists
        27.3  Binary Search
        27.4  Newton's Method
        27.5  Extended Exercise: Gaussian Elimination

    28  Algorithms that Backtrack
        28.1  Traversing Graphs
        28.2  Extended Exercise: Checking (on) Queens

    29  Intermezzo 5: The Cost of Computing and Vectors
        29.1  Concrete Time, Abstract Time
        29.2  The Definition of ``on the Order of''
        29.3  A First Look at Vectors

  VI  Accumulating Knowledge

    30  The Loss of Knowledge
        30.1  A Problem with Structural Processing
        30.2  A Problem with Generative Recursion

    31  Designing Accumulator-Style Functions
        31.1  Recognizing the Need for an Accumulator
        31.2  Accumulator-Style Functions
        31.3  Transforming Functions into Accumulator-Style

    32  More Uses of Accumulation
        32.1  Extended Exercise: Accumulators on Trees
        32.2  Extended Exercise: Missionaries and Cannibals
        32.3  Extended Exercise: Board Solitaire

    33  Intermezzo 6: The Nature of Inexact Numbers
        33.1  Fixed-size Number Arithmetic
        33.2  Overflow
        33.3  Underflow
        33.4  DrScheme's Numbers

  VII  Changing the State of Variables

    34  Memory for Functions

    35  Assignment to Variables
        35.1  Simple Assignments at Work
        35.2  Sequencing Expression Evaluations
        35.3  Assignments and Functions
        35.4  A First Useful Example

    36  Designing Functions with Memory
        36.1  The Need for Memory
        36.2  Memory and State Variables
        36.3  Functions that Initialize Memory
        36.4  Functions that Change Memory

    37  Examples of Memory Usage
        37.1  Initializing State
        37.2  State Changes from User Interactions
        37.3  State Changes from Recursion
        37.4  Finger Exercises on State Changes
        37.5  Extended Exercise: Exploring Places

    38  Intermezzo 7: The Final Syntax and Semantics
        38.1  The Vocabulary of Advanced Scheme
        38.2  The Grammar of Advanced Scheme
        38.3  The Meaning of Advanced Scheme
        38.4  Errors in Advanced Scheme

  VIII  Changing Compound Values

    39  Encapsulation
        39.1  Abstracting with State Variables
        39.2  Practice with Encapsulation

    40  Mutable Structures
        40.1  Structures from Functions
        40.2  Mutable Functional Structures
        40.3  Mutable Structures
        40.4  Mutable Vectors
        40.5  Changing Variables, Changing Structures

    41  Designing Functions that Change Structures
        41.1  Why Mutate Structures
        41.2  Structural Design Recipes and Mutation, Part 1
        41.3  Structural Design Recipes and Mutation, Part 2
        41.4  Extended Exercise: Moving Pictures, a Last Time

    42  Equality
        42.1  Extensional Equality
        42.2  Intensional Equality

    43  Changing Structures, Vectors, and Objects
        43.1  More Practice with Vectors
        43.2  Collections of Structures with Cycles
        43.3  Backtracking with State

An Introduction to Scheme and its Implementation

edit
    * Overview
          o Scheme: A Small But Powerful Language
          o Who Is this Book For?
          o Why Scheme?
          o Why Scheme Now?
          o What this Book Is Not
          o Structure of this Book 
    * Introduction
l1        o What is Scheme? (Hunk A)
          o Basic Scheme Features
l1,l2           + Code Consists of Expressions
--                    # Parenthesized Prefix Expressions
--                    # Expressions Return Values, But May Have Side-Effects
--                    # Defining Variables and Procedures
--                    # Most Operators are Procedures
--                    # Definitions vs. Assignments
--                    # Special Forms
--                    # Control Structures are Expressions 
l1              + The Boolean Values #t and #f
l2              + Some Other Control-Flow Constructs: cond, and, and or
--                    # cond
--                    # and and or 
l1              + Comments (Hunk C)
l2              + A Note about Parentheses and Indenting
--                    # Let Your Editor Help You
--                    # Indenting Procedure Calls and Simple Control Constructs
--                    # Indenting cond
--                    # Indenting Procedure Definitions 
l1              + All Values are Pointers to Objects
l1                    # All Values are Pointers
                      # Implementations Optimize Away Pointers
                      # Objects on the Heap 
                + Scheme Reclaims Memory Automatically
l1              + Objects Have Types, Variables Don't
l1                    # Dynamic typing 
l3              + The Empty List (Hunk E) 
l3        o Pairs and Lists
--              + cdr-linked lists
--              + Lists and Quoting
--              + Where the Empty List Got its Name 
          o Recursion Over Lists and Other Data Structures
l3        o Type and Equality Predicates (Hunk G)
--              + Type Predicates
--              + Equality Predicates
--              + Choosing Equality Predicates (Hunk I) 
l3        o Quoting and Literals
--              + Simple Literals and Self-Evaluation 
          o Local Variables and Lexical Scope
l2              + let
--                    # Indenting let Expressions 
                + Lexical Scope
                      # Binding Environments and Binding Contours
                      # Block Structure Diagrams for lets 
l2              + let* 
          o Procedures (Hunk K)
                + Procedures are First Class
                + Higher-Order Procedures
                + Anonymous Procedures and lambda
                + lambda and Lexical Scope (Hunk M)
l2              + Local Definitions
                + Recursive Local Procedures and letrec
                + Multiple defines are like a letrec
l2              + Variable Arity: Procedures that Take a Variable Number of Arguments
                + apply 
l2        o Variable Binding Again
--              + Identifiers and Variables
--              + Variables vs. Bindings vs. Values 
          o Tail Recursion (Hunk O)
          o Macros
          o Continuations
          o Iteration Constructs
          o Discussion and Review 
    * Using Scheme (A Tutorial)
          o An Interactive Programming Environment (Hunk B)
                + Starting Scheme
                + Making mistakes and recovering from them
                + Returns and Parentheses
                + Interrupting Scheme
                + Exiting (Quitting) Scheme
                + Trying Out More Expressions
l2              + Booleans and Conditionals
l2              + Sequencing
                + Other Flow-of-control Structures
                      # Using cond
                      # Using and and or 
l3              + Making Some Objects (Hunk D)
l3              + Lists (Hunk F) 
l2        o Using Predicates (Hunk H)
--              + Using Type Predicates
--              + Using Equality Predicates 
          o Local Variables, let, and Lexical Scope (Hunk J)
          o Using First-Class, Higher-Order, and Anonymous Procedures (Hunk L)
                + First-Class Procedures
                + Using and Writing Higher-Order Procedures 
          o Interactively Changing a Program (Hunk N)
                + Replacing Procedure Values
                + Loading Code from a File
                + Loading and Running Whole Programs 
          o Some Other Useful Data Types
l3              + Strings
l3              + Symbols
--                    # A Note on Identifiers 
l3              + Lists Again
--                    # Heterogeneous Lists
--                    # Operations on Lists 
          o Basic Programming Examples (Hunk P)
                + An Error Signaling Routine
                + length
                + Copying Lists
                + append and reverse
                      # append
                      # reverse 
                + map and for-each
                      # map
                      # for-each 
                + member and assoc, and friends
                      # member, memq, and memv
                      # assoc, assq, and assv 
          o Procedural Abstraction
                + Procedure Specialization
                + Procedure Composition
                + Currying 
          o Discussion and Review 
    * Writing an Interpreter
          o Interpretation and Compilation
          o Implementing a Simple Interpreter
                + The Read-Eval-Print Loop
                + The Reader
                      # Implementing read
                      # Implementing read-list
                      # Comments on the Reader 
                + Recursive Evaluation
                + A Note on Snarfing and Bootstrapping
                      # Snarfing
                      # Bootstrapping and Cross-compiling 
                + Improving the Simple Interpreter 
          o Discussion and Review 
    * Environments and Procedures
          o Understanding let and lambda
                + let
                + lambda
                      # define and lambda
                      # Currying
                      # Procedures are Closures 
          o Lambda is cheap, and Closures are Fast
          o An Interpreter with let and lambda
                + Nested Environments and Recursive Evaluation
                + Integrated, Extensible Treatment of Special Forms
                + Interpreting let
                + Variable References and set!
                + Interpreting lambda and Procedure Calling
                      # Mutual Recursion Between Eval and Apply 
          o Variants of let: letrec and let*
                + Understanding letrec
                      # Using letrec and lambda to Implement Modules 
                + let* 
          o Iteration Constructs
                + Named let 
          o Programming with Procedures and Environments
          o do
          o Exercises 
    * Recursion in Scheme
          o Subproblems and Reductions (non-tail and tail calls)
          o The Continuation Chain
          o Exploiting Tail Recursion
                + Passing Intermediate Values as Arguments
                      # Summing a List
                      # Implementing length tail-recursively 
                + reduce 
    * Quasiquotation and Macros
          o quasiquote
                + unquote-splicing 
          o Defining New Special Forms
                + Macros vs. Procedures 
          o Implementing More Scheme Special Forms
                + let
                + let*
                + cond
                + Discussion 
          o Lisp-style Macros
                + Ultra-simple Lispish Macros
                      # Better Lisp-style Macros
                      # Problems With Lisp-Style Macros
                      # Ugly Hacks Around Name Conflicts 
          o Implementing Simple Macros and Quasiquote
                + Implementing Simple Macros
                + Implementing quasiquote and unquote
                      # Translating backquotes to quasiquote
                      # quasiquote
                      # define-rewriter
                      # define-macro 
          o Procedural Macros vs. Template-filling Macros
          o Programming Examples Using Macros 
    * Records and Object Orientation
          o Records
                + Data Abstraction
                + Implementing Records 
          o Objects
                + Object Orientation
                + Implementing a Simple Object System
                      # Generic Functions and Dynamic Dispatch
                      # Inheritance 
    * Other Useful Features
          o Special Forms
          o Input-Output Facilities
                + read and write
                + display
                + Ports
                + with-input-\dots{} Forms 
          o Useful Types and Associated Procedures
                + Numeric Types
                      # Floating-Point Numbers
                      # Arbitrary-Precision Integers
                      # Ratios
                      # Coercions and Exactness 
                + Vectors
                + Strings and Characters 
    * call-with-current-continuation
          o Implementing a Better Read-Eval-Print Loop
          o Implementing Catch and Throw
          o Implementing Backtracking
          o Implementing Coroutines
          o Implementing Cooperative Multitasking
          o Caveats about call-with-current-continuation 
    * A Simple Scheme Compiler
          o What is a Compiler?
                + What is an Interpreter?
                + OK, so what's a compiler? 
          o What Does a Compiler Generate?
          o Basic Structure of the Compiler
          o Data Representations, Calling Convention, etc.
                + The Registers
                + The Evaluation Stack (or Eval Stack, for short)
                + The Continuation Chain
                + Environments
                + Closure Representation and Calling 
          o Continuations
                + Applying a Procedure Doesn't Save the Caller's State
                + Continuation Saving
                + An Example
                + Generating Unique Labels 
          o More on Representations of Environments
          o Compiling Code for Literals
          o Compiling Code for Top-Level Variable References
          o Precomputing Local Variable Lookups using Lexical Scope
                + Lexical Addressing and Compile-Time Environments
                + A Detailed Example 
          o Preserving Tail-Recursiveness using Compile-Time Continuations
                + When Should We Save Continuations?
                      # Compiling Returns 
          o Compiling Top-Level Expressions
          o Compiling lambda Expressions Inside Procedures
          o Compiling Top-level Definitions
          o Interfacing to the Runtime System
                + Garbage Collection
                      # Safe Points
                      # GC at Any Time 
                + Interrupts 
          o Advanced Compiler and Runtime System Techniques
                + Inlining Small Procedures
                + Type Declarations and Type Analysis
                + Using More Hardware Registers
                + Closure Analysis
                + Register Allocating Loop Variables for Loops
                + Conventional Optimizations
                + Stack Caches 
    * Concept Index 

Practical Common Lisp

edit
l1   1.  Introduction: Why Lisp?
--       Why Lisp?
--       Where It Began
--       Who This Book Is For
l1   2. Lather, Rinse, Repeat: A Tour of the REPL
--       Choosing a Lisp Implementation
--       Getting Up and Running with Lisp in a Box
--       Free Your Mind: Interactive Programming
--       Experimenting in the REPL
--       "Hello, World," Lisp Style
--       Saving Your Work
     3. Practical: A Simple Database
l1,l2 4. Syntax and Semantics
--       What's with All the Parentheses?
--       Breaking Open the Black Box
--       S-expressions
--       S-expressions As Lisp Forms
--       Function Calls
--       Special Operators
         Macros
--       Truth, Falsehood, and Equality
--       Formatting Lisp Code
l2   5. Functions
--       Defining New Functions
--       Function Parameter Lists
--       Optional Parameters
--       Rest Parameters
--       Keyword Parameters
--       Mixing Different Parameter Types
--       Function Return Values
         Functions As Data, a.k.a. Higher-Order Functions
         Anonymous Functions
     6. Variables
l2       Variable Basics
         Lexical Variables and Closures
         Dynamic, a.k.a. Special, Variables
l2       Constants
l2       Assignment
         Generalized Assignment
         Other Ways to Modify Places
     7. Macros: Standard Control Constructs
l2       WHEN and UNLESS
l2       COND
l2       AND, OR, and NOT
         Looping
         DOLIST and DOTIMES
         DO
         The Mighty LOOP
     8. Macros: Defining Your Own
     9. Practical: Building a Unit Test Framework
l3  10. Numbers, Characters, and Strings
--       Numbers
--       Numeric Literals
--       Basic Math
--       Numeric Comparisons
--       Higher Math
--       Characters
--       Character Comparisons
--       Strings
--       String Comparisons
l3  11. Collections
--       Vectors
--       Subtypes of Vector
--       Vectors As Sequences
--       Sequence Iterating Functions
--       Higher-Order Function Variants
--       Whole Sequence Manipulations
--       Sorting and Merging
--       Subsequence Manipulations
--       Sequence Predicates
--       Sequence Mapping Functions
--       Hash Tables
--       Hash Table Iteration
l3  12. They Called It LISP for a Reason: List Processing
--       "There Is No List"
--       Functional Programming and Lists
--       "Destructive" Operations
--       Combining Recycling with Shared Structure
--       List-Manipulation Functions
--       Mapping
--       Other Structures
l3  13. Beyond Lists: Other Uses for Cons Cells
--       Trees
--       Sets
--       Lookup Tables: Alists and Plists
--       DESTRUCTURING-BIND
    14. Files and File I/O
    15. Practical: A Portable Pathname Library
    16. Object Reorientation: Generic Functions
    17. Object Reorientation: Classes
    18. A Few FORMAT Recipes
    19. Beyond Exception Handling: Conditions and Restarts
    20. The Special Operators
    21. Programming in the Large: Packages and Symbols
    22. LOOP for Black Belts
    23. Practical: A Spam Filter
    24. Practical: Parsing Binary Files
    25. Practical: An ID3 Parser
    26. Practical: Web Programming with AllegroServe
    27. Practical: An MP3 Database
    28. Practical: A Shoutcast Server
    29. Practical: An MP3 Browser
    30. Practical: An HTML Generation Library, the Interpreter
    31. Practical: An HTML Generation Library, the Compiler
    32. Conclusion: What's Next?