CM20214-20221–Advanced Programming Principles

This is my part of the course, that I teach with Paola Bruscoli. For Russell Bradford's part, go here.

Lectures and problem classes in Semester 2 (not running in the week starting on 29/2 because of labs):

Laboratories – one two-hour session for each student:

A Prolog textbook, which I suggest to buy and of which some copies are in the library, is:

An online resource (with associated free textbook) is:

Lecture notes:

Prolog Programming and Unification are slides by Paola Bruscoli that we will use in part.

A textbook on compilers, of which 17 copies are in the library, is:

Another textbook, for which the library has online access, is:

A standard reference for compilers is:

Another recommended textbook is:

News

25.4.16    The lecture on 29th April is cancelled.

Lectures, Problem Classes, Topics and Suggested Exercises

1.2.16–Lecture 1    Introduction. The sum-product riddle.
Suggested exercise: Install a Prolog interpreter on your computer.

4.2.16–Lecture 2    Example Prolog program.
Suggested exercise: Run the program we have seen in class with the suggested queries (see email).

5.2.16–Lecture 3    Procedure definitions and calls, success and failure, search tree, variable arguments.
Suggested exercise: Read Section 1.3 in Endriss's notes and produce the search tree for the `elephant´ program (see email) and the query 'is_bigger(X,Y)'.

8.2.16–Practical Class 1    Search tree for the 'elephant' program and the query 'is_bigger(X,Y)'.
Suggested exercise: What simple changes to the 'elephant' program make it loop on the query 'is_bigger(X,Y)?'.

11.2.16–Lecture 4    Function symbols, their arity, terms and sub-terms. Unification. The Martelli Montanari (MM) algorithm for unification.
Suggested exercise: Unify, by applying the MM algorithm, the terms f(X,Y) and f(g(Y),b); f(X,Y) and f(g(Y),g(X)); f(b,Y) and f(g(Y),b); f(X,g(Z),g(Z)) and f(h(Y),Y,g(h(X))).

12.2.16–Practical Class 2    Examples of Martelli-Montanari algorithm in action: unify f(X,Y,Z) and f(a,Z,h(a)); f(g(X),g(c),Y) and f(g(g(Y)),X,a); f(g(X),g(Z),Y) and f(g(g(Y)),g(X),Z); f(g(X),Y,h(Z)) and f(U,W,U); f(a,X,g(h(Y))) and f(Z,i(Z,W),g(W)); f(X,X,Y) and f(g(Y),g(g(Z)),g(a)). Exercise: Write a two-clause non-recursive Prolog program containing only once the atom "b" such that the solution to the query "?- a(X)." contains 1023 "b"s.

15.2.16–Lecture 5    Lists; the append and the palindrome programs on lists. Representing lists by difference lists.
Suggested exercise: Write a Prolog program that reverses a list.

18.2.16–Lecture 6    Type-checking, comparisons and arithmetic operators. The cut.
Suggested exercise: Write a Prolog program that removes repetitions from a list; for example, given [1,5,6,6,4,4,4,5,2,2,3,2] it would produce [1,5,6,4,5,2,3,2].

19.2.16–Practical Class 3    How to solve the coursework puzzle – 1st question. Controlling induction: a Prolog program that reverses a list and a query that makes it loop.
Suggested exercise: write a Prolog program that solves the first question of the coursework and use the marking program to check it.

22.2.16–Practical Class 4    Removing repetitions from a list. Bubblesort.
Suggested exercise: improve the given bubblesort program by conflating the 'sorted' check into one bubblesorting pass.

25.2.16–Lecture 7    The built-in \+ and the construction of negation using “!, fail”. Aggregation: the findall built-in.
Suggested exercise: write a program that generates a list of quadruples [ X , Y , X + Y , X * Y ] as specified in the coursework, using findall.

26.2.16–Practical Class 5    Complete solution to the coursework puzzle. How to generate its list of quadruples with findall. Introduction to the lab exercise. More efficient bubblesort.
Suggested exercise: try solving the lab exercise before going to the lab.

7.3.16–Lecture 8 and Practical Class    Introduction to the relation between languages, automata/tables and parsers. Program that recognises the language generated by the regular expression a(b*c + bd)*.
Suggested exercise: Write a program that generates a(b*c + bd)*.

10.3.16–Lecture 9 and Practical Class    Nondeterministic finite automata. Program that generates L = a(b*c + bd)*. Introduction to compilers.    Slides
Suggested exercise: Use negation to write a program that generates all the strings of L that do not contain an odd number of b's.

11.3.16–Lecture 10    Definition of grammar. Type 0 grammars.
Suggested exercise: Write a Prolog program that (recognises and) generates the language defined by the grammar:

14.3.16–Lecture 11    Solution to the exercise of Lecture 10. How to turn depth-first search into breadth-first search. Definition of Type 0, 1, 2 and 3 grammar.
Suggested exercise: Find a Type 1 grammar that generates {a2^n | n ≥ 0} and then write a Prolog program that generates the same language based on the grammar.

17.3.16–Lecture 12    Leftmost and rightmost derivations. Parse trees. Ambiguous grammars.
Suggested exercise: Find a regular grammar and a Prolog program that generate the language (+ | - | )digit*.digit digit* where digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

18.3.16–Lecture 13    Left, right and middle recursion. Characterisation of ambiguous grammars.
Suggested exercises: 2.3, 2.4 and 2.5 of the Hunter's textbook. Implement in Prolog all the grammars you see. Find an unambiguous Type 2 grammar for if-then-else with optional else.

4.4.16–Lecture 14    The parsing problem. Top-down parsing and introduction to LL(1) grammars. Definition of director set.
Suggested exercise: find a context-free grammar for xx*yy* that only requires one lookahead symbol to disambiguate production usage in top-down parsing.

7.4.16–Practical Class 6    Solutions to previously set exercises.

8.4.16–Practical Class 7    Solutions to all outstanding past exercises.

11.4.16–Lecture 15    Definition of LL(1) grammar. Removal of left recursion.
Suggested exercise: Read Section 4.4 in the Hunter's textbook.

14.4.16–Lecture 16    Examples of factorisation. Example of non-LL(1) language. Deterministic Prolog program that recognises {ynaxn | n ≥ 0} ∪ {znaxn | n ≥ 0}.
Suggested exercises: 1) Is the language {xnayn | n ≥ 0} ∪ {xnazn | n ≥ 0} an LL(1) language? 2) Can an LL(1) grammar be ambiguous? Why? 3) Read Section 4.6 in the Hunter's textbook.

15.4.16–Practical Class 8    Solutions to and tips about some exam questions of last year. Why any LL(1) grammar is unambiguous.

18.4.16–Lecture 17    Bottom-up parsing: introduction to the parse table.
Suggested exercise: Go through every detail of the example in Section 5.3 of the textbook, reproduced here.

21.4.16–Lecture 18    Bottom-up parsing: how to build a parse table.
Suggested exercise: Go through every detail of the example in Section 5.4 of the textbook, reproduced here.

22.4.16–Practical Class 9    Generating the SLR(1) table associated to a given grammar.

25.4.16–Practical Class 10    Solution to a past exam.

28.4.16–Practical Class 11    Example exam questions with solutions.

Material Covered and to Be Prepared for the Exam

In Endriss's lecture notes:

In Bruscoli's Prolog Programming slides:

Slide 14 in Bruscoli's Unification slides (note that the lowercase x's are variables). Use slides 5–9, 11 and 12 as a formal background to slide 14, but their content is not required for the exam.

In Hunter's The Essence of Compilers (or equivalent):

Laboratories

This is a suggested exercise for the labs.

Coursework

This is the coursework specification, the deadline is 16 March 2016 at 5pm. Feedback will be provided by email within three weeks from submission. You can use this template for the program and then grade your solution by following these instructions.

Submission page for CM20214: Moodle.

Submission page for CM20221: Moodle.

Past Exams

The papers for CM20221A are the same as those for CM20214.

Software

You can use, for example, SWI-Prolog, which is multi-platform and free.

Office Hours

When you want to talk to me, just send me an email and we'll arrange an appointment.

28.4.2016    Alessio Guglielmi    email (replace AT by @)