Lecture Notes, Week 02

• Kleene’s S-m-n theorem
  • Exercise 1
  • Programs and the function they compute
  • Interlude about the halting predicate
  • Aftermath
  • Kleene’s S-m-n function
  • Interlude
  • I-diagrams, revisited
  • Program equivalence
  • Exercise 2
  • Hint towards solving Exercise 2
  • Kleene’s S-m-n theorem
  • Exercise 3
  • Exercise 4
  • Exercise 5
  • Partial solution for Exercise 5
  • Food for thought
  • Specializing the partial evaluator with respect to the program to specialize
  • Exercise 6
  • Exercise 7
  • Partial solution for Exercise 7
  • Postlude
  • Version
• Computational paradigms
  • Goal
  • Imperative programming
  • Functional programming
  • Logic programming
  • Rewriting
  • Other computational paradigms
  • Version
• Finite description of arbitrarily large data
  • Goal
  • Grammars for finite languages
  • Grammars as a logical system
  • Grammars as a rewriting system
  • Abstract-syntax trees
  • Concrete and abstract syntax
  • Parsing and unparsing
  • Using a grammar to generate grammatically correct sentences
  • Grammars for infinite languages
  • Using a grammar to generate grammatically correct sentences, continued
  • Exercise 8
  • Exercise 9
  • Exercise 10
  • Soundness and completeness
  • Example of a sound representation
  • Example of an unsound representation
  • Example of a complete representation
  • Example of an incomplete representation
  • A sound and complete representation of natural numbers
  • Computer data
  • The onion, revisited
  • More agricultural vagaries: the case of shallots
  • Postlude
  • Version
• Syntax of regular expressions
  • Goal
  • A BNF for regular expressions
  • Exercise 11
  • Exercise 12
  • A BNF for regular expressions, logically
  • Exercise 13
  • Exercise 14
  • Syntax errors
  • Version
• Exercises for Week 02
  • Exercise 0
  • Mandatory exercises
  • Recommended additional exercises
  • Practicalities
  • Exercise 15
  • Exercise 16
  • Version