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

- Mondays at 10:15 in CB 2.6,
- Thursdays at 9:15 in CB 1.12,
- Fridays at 15:15 in EB 1.1.

Laboratories – one two-hour session for each student:

- Monday 29.2.16 at 10:15–12:05 in EB 0.9,
- Monday 29.2.16 at 16:15–18:05 in EB 0.9,
- Thursday 3.3.15 at 8.15–10.05 in EB 0.9,
- Friday 4.3.15 at 15.15–17.05 in 3E 3.1.

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

*PROLOG Programming for Artificial Intelligence*

Ivan Bratko

Addison Wesley

An online resource (with associated free textbook) is:

- Learn Prolog Now! by Patrick Blackburn, Johan Bos, and Kristina Striegnitz.

Lecture notes:

*An Introduction to Prolog Programming*

Ulle Endriss

Universiteit van Amsterdam

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:

*The Essence of Compilers*

Robin Hunter

Prentice Hall

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

*Compiler Construction Using Java, JavaCC, and Yacc*

Anthony J. Dos Reis

Wiley

A standard reference for compilers is:

*Compilers - Principles, Techniques and Tools*

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman

Prentice Hall

Another recommended textbook is:

*Introduction to Compiling Techniques: A First Course Using ANSI C, Lex, and Yacc*

J. P. Bennett

Mcgraw Hill

*25.4.16* The lecture on 29th April is cancelled.

*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:

- S → QNQ
- QN → QR
- RN → NNR
- RQ → NNQ
- N → a
- Q → ε

*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 {a^{2^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 {y^{n}ax^{n} | n ≥ 0} ∪ {z^{n}ax^{n} | n ≥ 0}.

Suggested exercises: 1) Is the language {x^{n}ay^{n} | n ≥ 0} ∪ {x^{n}az^{n} | 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.

In Endriss's lecture notes:

- Sections 1.1, 1.2.1, 1.2.2, 1.3.

In Bruscoli's Prolog Programming slides:

- Slides 1–22, 45, 47–51, 57–61, 69–70 74–81, 89.

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):

- Chapter 1.
- Chapter 2 up to Section 2.6; Section 2.8.
- Chapter 4 up to Section 4.3; compare Section 4.4 with our Prolog methods; Section 4.5.
- Chapter 5 up to Section 5.4.

This is a suggested exercise for the labs.

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.

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

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 @)