Lecture Notes, Week 02

• Kleene’s S-m-n theorem
  • Exercise 01
  • 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 02
  • Hint towards solving Exercise 02
  • Kleene’s S-m-n theorem
  • Exercise 03
  • Exercise 04
  • Exercise 05
  • Partial solution for Exercise 05
  • Food for thought
  • Specializing the partial evaluator with respect to the program to specialize
  • Exercise 06
  • Exercise 07
  • Partial solution for Exercise 07
  • Postlude
  • Version
• Computational paradigms
  • Goal
  • Imperative programming
  • Functional programming
  • Logic programming
  • Rewriting
  • Other computational paradigms
  • Version
• Finite description of arbitrarily large data
  • Goal
  • Resources
  • 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 08
  • Exercise 09
  • 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
  • Resources
  • 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 00
  • Mandatory exercises
  • Recommended additional exercise
  • Practicalities
  • Exercise 15
  • Exercise 16
  • Version