Lecture Materials

Lecture outlines, some of the lecture notes, and source code of examples will be posted here after each lecture (most recent first).

  • Feb 19. The propositional logic example (conversion to NNF, CNF, DNF) expanded - the final program is available here.
  • Feb 17. More on pattern matching (database example is here). Polymorphism in OCaml - parametric and ad-hoc. Unions (variants) - the propositional logic example is here. Read Section 5.1 and Chapter 6 up to Section 6.4 in Introduction to Objective Caml, do exercises 5.5, 6.2-6.4.
  • Feb 13. Tail-recursion examples (len_tr.ml, prefix_tr.ml, fib_tr.ml. Pattern matching. Read Chapter 4, in Introduction to Objective Caml, do exercises 4.1-4.3.
  • Feb 10. The dictionary example revisited. Recursion and tail-recursion. The tail-recursive factorial is here: fact2.ml. Read Section 5.3 and 5.4 in Introduction to Objective Caml, do exercises 5.4 and 5.8. Exercise 5.7 will be part of your assignment.
  • Feb 5. More on naming expressions; restricting scope of variables; some useful OCaml functions (operators, I/O); a structure of an OCaml program; examples (Fibonacci numbers fib.ml, and a dictionary dict.ml). Read Chapter 3 in Introduction to Objective Caml, do all exercises, in particular Exercise 3.8 as it will be part of your assignment.
  • Feb 3. Basic data types in OCaml (primitive and container); working with OCaml; function definition and application; naming expressions (variable definition). Read Chapter 2, and the begining of Chapter 3 in Introduction to Objective Caml. Do Exercise 2.1.
  • Nov 4. Characteristic features of functional programming languages in general, and ML and OCaml in particular. High-level intro to lambda-calculus. The information on lambda calculus is available in this paper. Please read Sections 1-9, and do exercises in Section 8. Properties of ML and OCaml are described in Chapter 1 of Introduction to Objective Caml.
  • Oct 28. Examples and exercises on lists, arithmetic and cut. Here are the programs that we worked on in the class: ins_sort.pl, merge_sort.pl, authors.pl.
  • Oct 23. Uses of cut; fail; Prolog arithmetic. Prolog programs we saw in the class: intersect.pl, print_intersection.pl, length.pl, fact.pl. For more information on cut and fail: Section 5.1 of Logic, Programming and Prolog (2nd ed), do Exercises 5.1, 5.2; Section 9.1 of Prolog Programming: A First Course, do Exercise 9.1; Section 10 of Learn Prolog Now!, do Exercises 10.1-10.3, and the practical session. For more information on arithmetic: Section 5 of Learn Prolog Now!, do Exercises 5.1-5.3, and the practical session.
  • Oct 21. More on negation-as-failure. Anonymous variables. Cut. The lecture notes for this lecture are here. For more information and exercises on cut: Section 5.1 of Logic, Programming and Prolog (2nd ed), do Exercises 5.1 and 5.2. Section 10.1 of Learn Prolog Now!, do Exercise 10.1.
  • Oct 16. More on Prolog lists. lshift/2 and perm/2. Negation as failure. Project. See Section 7.2 of Logic, Programming and Prolog (2ed) for information on lists. Do exercises 7.6-7.9. For negation as failure, read Sections 7.1 and 7.2 of Prolog Programming. A First Course and Chapter 8 of An introduction to logic programming through Prolog. Do exercise 8.1.
  • Oct 7. Prolog lists. The lecture notes for this lecture are here. More information on lists is in Section 7.2 of Logic, Programming and Prolog (2ed) (see Resources section for full references). Here are the example programs we did in the class: is_member.pl, insert_elem.pl, append.pl. Make sure to do exercises for today's lecture.
  • Oct 3. Resolution search tree; answer; stanard Prolog; Prolog lists. The lecture notes for this lecture are here. Information on lists is available from these sources: Section 7.2 of Logic, Programming and Prolog (2ed), Section 3.2 of Programming in Prolog and Section 4 of Learn Prolog Now! (see Resources section for full references).
  • Sep 25. Robinson's unification algorithm examples; resolution for predicate logic; resolution search tree example. The lecture notes for this lecture are here. Chapter 7 of An introduction to logic programming through Prolog has additional information of search trees (see Resources section for full references).
  • Sep 23. Conversion of predicate logic formulas to logic programming clauses; substitutions; unification; Robinson's unification algorithm. The lecture notes for this lecture are here. Additional explanations can be found in Section 4.1 of The Art of Prolog, and in Chapter 2 of From Logic Programming to Prolog (see Resources section for full references).
  • Sep 18. Propositional resolution example; refutation trees; linear resolution; resolution for predicate logic: conversion to prenex normal form, skolemization. The lecture notes for this lecture are here.
  • Sep 16. Classification of clauses; propositional resolution rules; inconsistency; resolution refutation. The lecture notes for this lecture are here.
  • Sep 11. Common mistakes on the quiz. Proof by contradiction, started propositional resolution: conjunctive normal form, logic programming (LP) representation of problems as a set of clauses. The lecture notes for this lecture are here.
  • Sep 9. Prolog syntax: terms (atoms, numbers, variables, compound terms), clauses (facts, rules), goals. Logic quiz. Transcript of the Prolog session is here. Flight connection program is here. Information on Prolog syntax can be found in any of the Prolog books listed in the Resources section.
  • Sep 4. Introduction: programming paradigms (imperative, object-oriented, functional, logic), examples of OCaml and Prolog programs. Presentation on industrial applications of OCaml is here. Examples of industrial applications on Prolog are here. OCaml program I used for demo is here. Prolog demo is here, and the session transcipt is here.