Principles of Programming Languages [PLP-14]

Code 603AA - 9 Credits

LECTURER Andrea Corradini <andrea@di.unipi.it>

Timetable (second semester) Tuesday 9-11, Room Fib L1
Friday 11-13, Room Fib A1

Office hours Click here

Announcements

[June 30, 2015] The students who have taken the written exam of June 26 and those who are admitted to the oral exam are invited to come to Room "Sala Riunioni Ovest" of the Dipartimento di Informatica on Wednesday, July 1st, at 9:00, to see the corrections of the written proof and the to fix the date of the oral exams.
List of students currently admitted to the oral exam: AdmissionOralExam-Jul-02.pdf.
[June 15, 2015]Students having passed the mid-term exams can take the oral exams in the days after the next written proofs, i.e. on Friday, June 26 or on Friday, July 17, or also after the correction of the written proofs.
[June 14, 2015]The oral exams will start on Monday, June 15, at 9:30 in Aula B.
[June 10, 2015] All the students admitted to the oral exam (and also those wanting to see the errors in their written proofs) are invited to come to Room "Aula A" of Polo Fibonacci on Thursday, June 11, at 16:30, to fix the date of the oral exams. The oral exams will start on Friday, June 12 around lunchtime and will continue next Monday.
[June 9, 2015] I published on the Moodle platform the text of the written exam of June 4, the results, and the list of students admitted to the oral exam.
[June 2, 2015] The results of the second MidTerm Exam are published on the Moodle platform.
[May 25, 2015] As announced during the last lecture, the exams of the summer session (till July) are planned as follows:
1. [May 29, 2015] Second Midterm Exam
2. [June 4, 2015] Mutually exclusive options, to be declared at the start of the proof:
  1. First written exam;
  2. possibility of taking the Second Midterm Exam (only for students who did not take it on May 29);
  3. possibility of recovering the First Midterm Exam
3. [June 25, 2015] Mutually exclusive options, to be declared at the start of the proof:
  1. Second written exam;
  2. possibility of recovering the Second Midterm Exam (only for students who passed the First Midterm Exam) 29)
4. [July 16, 2015] Third written exam
In order to take an exam it is necessary to register at latest 48 hours before the proof at URL https://esami.unipi.it/esami/studentportal.php.
The oral exams will start, approximatively, after four working days following the written exam.
Passing both midterm exams or a (whole) written exam grants the student the right to take the oral exam not later than July 2015.
[March 10, 2015] Contrarily to what annouced earlier, the lectures of March 17 and March 20 will take place regularly.
[February 27, 2015] Because of missions abroad of the lecturer, there will be no lessons on Friday, March 6. The lecture will be recovered on Wednesday, March 11, at 4-6 pm.
[January 14, 2015] The results of the first mid-term exam are published on Moodle. To see the corrections, I will be available next Friday, January 16 at 4:30 pm in my office.
[January 11, 2015] The solutions to the exercises proposed for the mid-term exam are published on the Moodle platform.
[December 18, 2014] The text of the mid-term exam is published on the Moodle platform. Prompted by some students, here is the solution to Exercise 6 :01-2014-PLP-MidTerm-SolEx6.pdf. The solutions of the other exercises will be published in the next days.
[November 25, 2014] The first mid-term exam (a written proof) will be held on December 18 at 4 pm in Room A.
Registration is mandatory: register at URL https://esami.unipi.it/esami/studentportal.php before Dec. 12, 2014.
Send an email to the lectured if you have any problem when registering.
[November 17, 2014] For additional teaching material visit the MOODLE site at https://elearning.di.unipi.it/moodle/course/index.php?categoryid=3. Ask the lecturer the password for guest access.
[November 10, 2014] The course starts today.

Evaluation criteria

The final grade is based on a written exam (possibly substituted by two mid-term exams) and on an oral proof.

Information for students enrolled before Academic Year 2014/15

Students enrolled in A.Y. 2013/14 or before have, in their study plan, the course "Principles of Programming Languages - Code 379AA - 12 Credits", taught in the past years by Prof. Marco Bellia. They can either

Take the exam with Prof. Bellia, for 12 credits, based on the original syllabus. For dates of written proofs see https://esami.unipi.it/esami/
Take the exam with Prof. Corradini, for 9 credits, and ask for an additional task to cover the remaining 3 credits. The first session will be next June.
Change the study plan, replacing the 12 credits course (code 379AA) with the 9 credits course (code 603AA), and take the exam with Prof. Corradini, starting from next June.

The current course started in November 2014 and will run till May 2015. Students intending to take the exam in the summer session are strongly invited to attend the rest of the course.

Textbooks

[ALSU] Compilers: Principles, Techniques, and Tools
by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, 2^nd edition
[Scott] Programming Language Pragmatics
by Michael L. Scott, 3^rd edition
[GM] Programming Languages: Principles and Paradigms
by Maurizio Gabbrielli and Simone Martini
[Mitchell] Concepts in Programming Languages
by John C. Mitchell
Warning: Chapters 5-7 on Haskell are not in the printed book

Course Schedule

N.	DATE	Topics	Slides	Notes
1	Nov. 10, 2014	Introduction Abstract Machines, Interpretation and Compilation	PLP-01.pdf	[GM], Chapter 1; [Scott], Chapter 1 (section 1-4 to 1-6).
2	Nov. 13, 2014	Structure of Compilers Overview of simple Front-End: Predictive Parsing, Translation Schemes	PLP-02.pdf	[ALSU], Chapter 2.
3	Nov. 17, 2014	Structure of Compilers Overview of simple Front-End: Lexical Analysis, Static Check, Intermediate Code Generation	PLP-03.pdf	[ALSU], Chapter 2.
4	Nov. 20, 2014	Lexical analysis Regular expressions and definitions, Implementing critical parts of a lexer	PLP-04.pdf	[ALSU], Chapter 3.
5	Nov. 24, 2014	Lexical analysis Designing a lexer generator Finite state automata	PLP-05.pdf	[ALSU], Chapter 3.
6	Nov. 27, 2014	From Regular Expression to DFA, directly Minimization of DFA's Exercises on lexical analysis	PLP-06.pdf	[ALSU], Chapter 3.
7	Dec. 1, 2014	Exercises on Lexical analysis	Proposed exercises: ES-PLP-2014-01-lexer.pdf	See the (non-marked) exercises proposed in [ALSU], Chapter 3, concerning the topics presented in class.
8	Dec. 4, 2014	Top-Down Parsing	PLP-07.pdf	[ALSU], Chapter 4.
9	Dec. 11, 2014	Bottom-Up Parsing	PLP-08.pdf	[ALSU], Chapter 4.
10	Dec. 15, 2014	LR parsing: Ambiguous grammars and Error detection; Exercises on parsing	PLP-09.pdf	[ALSU], Chapter 4.
11	Dec. 18, 2014	First Midterm Exam *The text of the exam is published on the Moodle platform*	Where? Room A When? 4 pm	It is necessary to register at URL https://esami.unipi.it/esami/studentportal.php before Dec. 12, 2014. The exam will be about the material presented during the lessons and covered by Chapter 1 of [GM], Chapter 1 (sec. 1-4 to 1-6) of [Scott], and Chapters 2, 3 and 4 of [ALSU], with the exception of Sections 4.7.5, 4.7.6 and 4.9.
12	Tue, Feb. 24, 2015 9-11 am Room L1	Syntax-Directed Translation I	PLP-10.pdf	[ALSU], Chapter 5.
13	Fri, Feb. 27, 2015 11-13 am Room A1	Syntax-Directed Translation II Parser generators: YACC/BISON	PLP-11.pdf	[ALSU], Chapter 5.
14	Tue, Mar. 3, 2015 9-11 am Room L1	Intermediate Code Generation I Intermediate representations; Three address statements and their implementations; Syntax-directed translation to three address statements; Handling local names and scopes with symbol tables.	PLP-12.pdf	[ALSU], Chapter 6.
15	Tue, Mar. 10, 2015 9-11 am Room L1	Intermediate Code Generation II Declarations of (multi-dimensional) arrays; Access to elements of arrays; Logical and relational expressions; Flow-of-control statements with backpatching lists.	PLP-13.pdf	[ALSU], Chapter 6.
16	Wed, Mar. 11, 2015 4-6 pm Room: L1	Static Analysis Checking Static versus Dynamic Checking; Type checking; Type conversion and coercion.	PLP-14.pdf	[ALSU], Chapter 6.
17	Fri, Mar. 13, 2015 11-13 am Room: A1	Exercises on Syntax-Directed Definitions and Translation Schemes	Proposed exercises: ES-PLP-2014-02-syntax-directed.pdf	[ALSU], Chapters 5 and 6.
18	Tue, Mar. 17, 2015 9-11 am Room L1	Code Generation I	PLP-15.pdf Proposed Homework	[ALSU], Chapter 8. Command line calculator with Flex/Lex and Yacc/Bison - Lex specification: calc.l; Yacc specification: calc.y; Dot representation of the parser FSA: parser.dot; Simple makefile: Makefile; dot can be found at http://www.graphviz.org/.
19	Fri, Mar. 20, 2015 11-13 am Room A1	Code Generation II	PLP-16.pdf	[ALSU], Chapters 8 and part of 9.
20	Tue, Mar. 24, 2015 9-11 am Room L1	Concepts of Programming Languages: An Introduction	PLP-17.pdf	[Scott] Chapter 1, Sections 1-1 to 1-3.
21	Fri, Mar. 27, 2015 11-13 am Room A1	Bootstrapping, Names and Binding Times	PLP-18.pdf	[Scott] Chapter 3, [GM] Chapter 4.
22	Tue, Mar. 31, 2015 9-11 am Room L1	Object allocation and Scoping rules	PLP-19.pdf	[Scott] Chapter 3, [GM] Chapters 4 and 5.
23	Thu, Apr. 16, 2015 2-4 pm Room L1	More on scopes, their implementation and closures	PLP-20.pdf	[Scott] Chapter 3, [GM] Chapters 4 and 5.
24	Fri, Apr. 17, 2015 11-13 am Room A1	Control flow: Expression evaluation, Structured flow, Selection statements	PLP-21.pdf	[Scott] Chapter 6, [GM] Chapter 6.
25	Tue, Apr. 21, 2015 9-11 am Room L1	Control flow: Iteration, Iterators and Recursion	PLP-22.pdf, up to page 32.	[Scott] Chapter 6, [GM] Chapter 6.
26	Fri, Apr. 24, 2015 11-13 am Room A1	Continuation-passing style Type systems	PLP-22.pdf, pages 33-36, PLP-23.pdf.	[Scott] Chapter 7, [GM] Chapter 8. Type systems; Type safety; Type checking [Equivalence, compatibility and coercion]; Primitive and composite types [Discrete and scalar types; tuples and records]
27	Tue, Apr. 28, 2015 9-11 am Room L1	Composite types	PLP-24.pdf, up to page 36.	[Scott] Chapter 7, [GM] Chapter 8. Composite Types: Arrays, Unions, Pointers. Value model vs. reference model of variables.
28	Wed, Apr. 29, 2015 4-6 pm Room C1	Composite types Type inference Parameter Passing	PLP-24.pdf, pages 36-43 PLP-25.pdf PLP-26.pdf, up to page 13	[Mitchell] Chapter 6: pages 118-136 (Type inference) [Scott] Section 8.3 (Parameter Passing) [GM] Sections 7.1 and 7.2 (Parameter Passing)
29	Tue, May 5, 2015 9-11 am Room L1	Parameter Passing Introduction to Haskell	PLP-26.pdf PLP-27.pdf, up to page 16	[Scott] Section 8.3 (Parameter Passing) [GM] Sections 7.1 and 7.2 (Parameter Passing) [Mitchell] Chapter 5 (Introduction to Haskell) The GHC compiler for Haskell can be downloaded at http://www.haskell.org/platform An introductory tutorial of Haskell and additional documentation about the languafe can be found at http://www.haskell.org/
30	Thu, May 7, 2015 4-6 pm Room L1	Introduction to Haskell Type classes in Haskell	PLP-27.pdf PLP-28.pdf, up to page 25	[Mitchell] Chapter 7 (Type classes in Haskell)
31	Tue, May 12, 2015 9-11 am Room L1	Type classes in Haskell The Maybe Monad	PLP-28.pdf PLP-29.pdf, up to page 12	[Mitchell] Chapter 7 (Type classes in Haskell) A very short tutorial on Monads: http://www.idryman.org/blog/2014/01/23/yet-another-monad-tutorial/
32	Fri, May 15, 2015 11-13 am Room A1	The IO Monad of Haskell	PLP-29.pdf	Reading material about Haskell Monads: [PeytonJohnes2008], up to page 18 (on the Moodle platform) https://wiki.haskell.org/Monads_as_containers https://wiki.haskell.org/Monads_as_computation A list of tutorials on Monads: https://wiki.haskell.org/Monad_tutorials_timeline
33	Tue, May 19, 2015 9-11 am Room L1	Lambda expressions and Stream API in Java 8	PLP-30.pdf	Reading material: http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html http://docs.oracle.com/javase/tutorial/collections/streams/index.html
34	Fri, May 22, 2015 11-13 am Room A1	Exercises	Proposed exercises: ES-PLP-2014-03-ProgLang-Various.pdf
35	Tue, May 26, 2015 9-11 am Room L1	Exercises	Proposed exercises: ES-PLP-2014-04-ProgLang-Various.pdf
36	May 29, 2015	Second Midterm Exam *The text of the exam is published on the Moodle platform*	Where? Room Fib-C When? 11 am	It is necessary to register at URL https://esami.unipi.it/esami/studentportal.php before May 27, 2015. The midterm exam will be about the material presented during the lessons of the second semester, and covered by the following chapters: Chapters 4.9, 5, 6, 8 (excluded 8.10 and 8.11), 9.1 of [ALSU] Chapters 3, 6, 7, 8.3 of [Scott] Chapters 4, 5, 6, 8, 7.1, 7.2 of [GM] Chapters 5, 6, 7 of [Mitchell] (PDFs to be downloaded from the Moodle platform, not from the printed book) Java 8: Lambda expressions and streams http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html http://docs.oracle.com/javase/tutorial/collections/streams/index.html

LECTURER	Andrea Corradini `<andrea@di.unipi.it>`
Timetable (second semester)	Tuesday 9-11, Room Fib L1 Friday 11-13, Room Fib A1
Office hours	Click here