Part II: Functional Programming and Context-Free Parsing

• 4 Basic Data Structures, Expressions and Statements
  • 4.1 Statements versus Expressions
  • 4.2 Values and Types
  • 4.3 Expressions for Values
  • 4.4 Variables, Scope, and Binding
  • 4.5 Scoping in the Interactive User Interface
  • 4.6 Inspecting Values and Types
  • 4.7 Type Checks
  • 4.8 Testing Equality
  • 4.9 Procedures
  • 4.10 Functions as Relations
  • 4.11 Boolean Conditionals
  • 4.12 Records
  • 4.13 Tuples
  • 4.14 Lists
  • 4.15 Characters, Strings, and Virtual Strings
  • 4.16 Loops
  • 4.17 Pattern Matching and Conditionals
  • 4.18 Towards State and Abstract Data Structures
  • 4.19 Modules
  • 4.20 Exercises
  • 4.21 Program Collection

• 5 A Naive Parser for Context-Free Grammars
  • 5.1 Natural Language, Syntax and Context-Free Grammar
    • 5.1.1 Parsing
  • 5.2 Bottom-up Recognition/Parsing
    • 5.2.1 Recognition as Inferential Closure
    • 5.2.2 Inferential Closure Algorithm
  • 5.3 A Bottom-Up Recognizer
    • 5.3.1 Grammar Rules
    • 5.3.2 Agenda
    • 5.3.3 Bag
    • 5.3.4 Parse
    • 5.3.5 The Complete Program
  • 5.4 Experiments, Critique, Improvements and Extensions
    • 5.4.1 Redundant Derivations
    • 5.4.2 Building Parse Trees
  • 5.5 Exercises

• 6 Loops, Exception Handling, and Threads
  • 6.1 Loops
    • 6.1.1 Basic Loops
    • 6.1.2 Loops by Recursion
    • 6.1.3 Parallel Iteration
    • 6.1.4 Quit a Loop
    • 6.1.5 Loops and State
  • 6.2 Example: Finite Automata
    • 6.2.1 Membership
    • 6.2.2 Emptyness
  • 6.3 Exception Handling
    • 6.3.1 Basic Statements
    • 6.3.2 Quit Recursion
    • 6.3.3 Quit Loops
  • 6.4 Concurrent Threads and Logic Variables
  • 6.5 Debugger
  • 6.6 Exercises
  • 6.7 Program Collection

• 7 Stateful Data Structures
  • 7.1 State in Abstract Data Structures
  • 7.2 Object versus Library Style
  • 7.3 Cells
    • 7.3.1 Library Style
    • 7.3.2 Object Style
  • 7.4 Bags
    • 7.4.1 Library Style
    • 7.4.2 Object Style
  • 7.5 Dictionaries
    • 7.5.1 Library Style
    • 7.5.2 Object Style
  • 7.6 Stacks
    • 7.6.1 Library Style
    • 7.6.2 Object Style
  • 7.7 Queues
    • 7.7.1 Library Style
    • 7.7.2 Object Style
  • 7.8 Arrays
    • 7.8.1 Library Style
    • 7.8.2 Object Style
  • 7.9 Module Abstract.oz
  • 7.10 Oz Object System
  • 7.11 Exercises
  • 7.12 Program Collection

• 8 Functors and Modular Programming
  • 8.1 Functors as values
    • 8.1.1 Features of functors
    • 8.1.2 Functors as abstract datatypes
    • 8.1.3 Module creation = functor linking
  • 8.2 Imports
  • 8.3 Persistent Functors
  • 8.4 Functor Programs
    • 8.4.1 ozmake
  • 8.5 Functors at Abstract URIs
    • 8.5.1 A Simple Makefile
  • 8.6 Creating a Package
    • 8.6.1 Package Creation
    • 8.6.2 Package Installation
    • 8.6.3 Package Download
  • 8.7 Refactoring the Naïve Parser
    • 8.7.1 Course Libraries
    • 8.7.2 NaiveClosure.ozf: Inferential Closure
    • 8.7.3 NaiveParser.ozf: Grammatical Processing
    • 8.7.4 naive-makefile.oz
    • 8.7.5 Using the new libraries
  • 8.8 Exercises
  • 8.9 Exercises

• 9 A Chart Parser for Context Free Grammars
  • 9.1 Chart Parsing
    • 9.1.1 What's Wrong with the Naive Parser?
    • 9.1.2 Chart Parsing as Inferential Closure
    • 9.1.3 What's a chart? What is it good for?
    • 9.1.4 Chart Parsing
    • 9.1.5 Looking to the Right is Enough
    • 9.1.6 Exercise
  • 9.2 Implementing a bottom-up chart parser
    • 9.2.1 Charts as arrays
    • 9.2.2 Parsing with a chart
    • 9.2.3 Initialising the agenda
    • 9.2.4 Processing the agenda
    • 9.2.5 Processing an edge
    • 9.2.6 A Test Interface
    • 9.2.7 The Complete Package
    • 9.2.8 Exercises