CS312 Functional and Logic Programming
Lecture Notes

Carl Alphonce
(with revisions by Michael Horsch)

September 9, 1997

Note: These notes are being revised as the term progresses. Please do not print out these notes too early, as they may be revised before we get to the material in class.

  • Introduction to Logic Programming
  • Introduction
  • Syntax
  • Logic databases
  • Introduction
  • Recursive rules
  • structured data
  • Recursive data structures
  • A binary recursive type
  • Some list predicates
  • Types
  • A unary recursive type
  • Unification
  • Revisiting the abstract interpreter
  • Example
  • Proof Trees
  • Search Trees
  • Traversing the search tree
  • Order and trees
  • Semantics
  • Minimal model semantics
  • Program correctness and completeness
  • Soundness and completeness
  • Introduction
  • Soundness
  • Completeness
  • Negation
  • Negative knowledge
  • The Closed World Assumption (CWA) and Negation as Failure (NAF)
  • Reconciling NAFF with our semantics
  • Interpreters
  • Meta-interpreters
  • Natural Language Analysis
  • Grammar rules
  • Context-free grammar rules
  • Context-free grammar rules expressed in Prolog
  • Definite-clause grammar rules
  • Nondeterminism
  • Generate and Test
  • Introduction to functional programming and ML
  • Introduction
  • Types
  • Boolean operations and if-then-else expressions
  • Local bindings
  • Patterns
  • Examples
  • Extending ML's type system
  • Exceptions and exception handlers
  • User-defined types
  • Equality
  • Interface vs. implementation
  • Modules
  • Structures
  • signatures
  • Example: priority queues
  • Abstract types and structures
  • Functors
  • Higher order functions
  • Anonymous functions
  • Functions as returned value: Curried functions
  • Functions as args
  • Mapping, filtering, and reduction
  • Infinite data structures
  • Sequences: infinite lists
  • Representation of matricies
  • Memoization
  • How to start SICStus Prolog
  • How to start SML
  • Footnotes

  • horsch@cs.ubc.ca