Functional programming -- 2009-2010 -- info.uvt.ro/Laboratory/References coverage
Appearance
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?