Principles of Programming Languages [PLP-16]

Code 603AA - 9 Credits

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

Timetable Monday 11-13, Room Fib N1
Thursday 16-18, Room Fib C1
Friday 14-16, Room Fib C1

Office hours Click here
To fix a date, send an email to <andrea@di.unipi.it>

Announcements

[January 20, 2016] Text and proposed solutions of the Second Mid-Term Exam of December 19, 2016, and of the First Final Exam of January 19, 2017 are published on the Moodle page of the course at https://elearning.di.unipi.it/course/view.php?id=52.

[January 14, 2016] Detailed syllabus of the course: PLP-2016-SYLLABUS.pdf.

[January 11, 2017] You can find HERE the results of the second mid-term exam of December 19.

[December 7, 2016] There will be an extra class of PLP on Monday, October 12, form 14 to 16 in Room C1.

[November 27, 2016] You can find HERE the results of the first mid-term exam of November 4.

[October 14, 2016] There will be an extra class of PLP on Monday, October 17, form 14 to 16 in Room L1.

[October 5, 2016] Because of a mission abroad, I will not be in Pisa on Friday, October 7 and Monday, October 10. Therefore after the class of tomorrow, Thursday 6, the course will continue on Thursday, October 13.

[September 30, 2016] There will be an extra class of PLP on Monday, October 3, form 14 to 16 in Room L1.

[September 27, 2016] For additional teaching material visit the MOODLE page at https://elearning.di.unipi.it/course/view.php?id=52. Ask the lecturer the password for guest access to the site.

[September 19, 2016] The course starts today. Students who missed the opportunity to take the Preliminary test that was proposed in the first two lectures, are kindly invited to contact the lecturer.

Tutoring

For any question concerning the contents of the course, you can contact (besides the lecturer) also the PhD student Lillo Galletta <galletta@di.unipi.it>. Send him an email to fix a date, possibly anticipating the topic to be discussed.

Evaluation criteria

The final grade is based on a written exam (possibly substituted by two mid-term exams [beginning of November; mid December]) and on an oral proof. The text of some past written exams with corresponding solutions are available on the Moodle page of the course. The oral exam will cover topics chosen from the Syllabus of the course.

Textbooks

Detailed syllabus of the course: PLP-2016-SYLLABUS.pdf.

[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	TOPIC	SLIDES	NOTES
1	Sep. 19, 2016	Presentation of the course Preliminary test	Slides: PLP-2016-01.pdf
2	Sep. 22, 2016	Languages and Abstract Machines Compilation and interpretation schemes Cross compilation and bootstrapping	Slides: PLP-2016-02.pdf	[GM], Chapter 1; [Scott], Chapter 1 (sections 1-4 to 1-6).
3	Sep. 26, 2016	Cross compilation and bootstrapping Overview of a syntax-directed compiler front-end (Context-Free) Grammars, Chomsky hierarchy; Parse trees; Ambiguity, associativity and precedence.	Slides: PLP-2015-03.pdf	[ALSU], Chapter 2.
4	Sep. 29, 2016	Overview of a syntax-directed compiler front-end Lexical analysis; Intermediate code generation; Static checking	Slides: PLP-2016-04.pdf	[ALSU], Chapter 2.
5	Sep. 30, 2016	Lexical analysis: Implementing critical parts of a scanner Tokens, lexeme and patterns; Languages and operations on them; Regular expressions and definitions; Transition diagrams; Code of a simple lexical analyzer; Lexical errors.	Slides: PLP-2016-05.pdf	[ALSU], Chapter 3.
6	Oct. 3, 2016	Towards generation of Lexical Analyzers Nondeterministic Finite State Automata (NFA); From Regular Expressions to NFA; Simulating a NFA; Determinization; Minimization; The Lex-Flex lexical analyzer generator	Slides: PLP-2016-06.pdf	[ALSU], Chapter 3.
7	Oct. 3, 2016	Exercises on the topics presented so far, in particular on grammars and languages, Regular Expressions, Finite State Automata, Lexical Analysis.	Proposed exercises: ES-PLP-2016-01-lexer.pdf	You are invited to continue solving the exercises at home. If you have doubts about the text or want to discuss a solution with me, send me an email.
8	Oct. 6, 2016	From DFAs to Regular Expressions and backwards From a DFA to a right-linear grammar; CF Grammars as continuous transformations on languages; Generated language as least fixed-point of a grammar; REs as solutions of least-fixed points equations. Introduction to Parsing Left-Recursion Elimination; Left Factoring; Top-Down Parsing; LL(1) grammars,	Slides: PLP-2016-07.pdf, up to page 29.	[ALSU], Chapters 3, 4.
9	Oct. 13, 2016	Top-Down Parsing Predictive, Recursive-Descent Parsing; Table directed parsing; Error recovery during top-down parsing. Bottom-up Parsing Shift-reduce parsing; Handles; Shift/Reduce and Reduce/Reduce conflicts; LR(0) items.	Slides: PLP-2016-07.pdf, all. PLP-2016-08.pdf, up to page 20.	[ALSU], Chapter 4.
10	Oct. 14, 2016	Bottom-up Parsing LR(0) automaton and LR(0) parsing table, SLR parsing; LR(1) items, automaton and canonical parsing table; LALR parsing tables; LR parsing with ambiguous grammars;	Slides: PLP-2016-08.pdf, all; PLP-2016-09.pdf, up to page 8.	[ALSU], Chapter 4.
11	Oct. 17, 2016	Bottom-up Parsing LR parsing with ambiguous grammars; Error recovery in LR parsing Parser generators: yacc/bison Handling ambiguous grammars in yacc/bison	Slides: PLP-2016-09.pdf, all.	[ALSU], Chapter 4.
12	Oct. 17, 2016	Exercises on Parsing	Proposed exercises: ES-PLP-2016-02-parser.pdf	You are invited to continue solving the exercises at home. If you have doubts about the text or want to discuss a solution with me, send me an email.
13	Oct. 20, 2016	Syntax-Directed Translation	Slides: PLP-2016-10.pdf	[ALSU], Chapter 5.
14	Ott. 21, 2016	Intermediate Representations Syntax-directed translation to Three Address Code Translation of expressions and statements Translation of short-circuit boolean expressions Translation of conditionals and iteration	Slides: PLP-2016-11.pdf, up to page 25.	[Scott] Chapter 6.5, [ALSU] Chapter 6.
15	Oct. 24, 2016	Use of backpatching lists. Code generation and Optimization; Control-Flow Graphs.	Slides: PLP-2016-11.pdf, all. PLP-2016-12c.pdf, up to page 24.	[ALSU] Chapter 6 and 8.
16	Oct. 27, 2016	Local vs. Global Optimization, DAG Based Optimization, Peephole Optimization and other techniques. Introduction to the LLVM compiler infrastructure.	Slides: PLP-2016-12c.pdf, all [slides on target machine addressing modes modified - November 7]. PLP-2016-13-LLVM.pdf.	[ALSU] Chapter 8 To install LLVM, start visiting http://clang.llvm.org/get_started.html. In order to display the Control Flow Graphs you need dot to be installed on your computer.
17	Oct. 28, 2016	Exercises	Proposed exercises: ES-PLP-2016-03-syntax-directed.pdf	You are invited to continue solving the exercises at home. If you have doubts about the text or want to discuss a solution with me, send me an email.
--	Nov. 4, 2016	First Midterm Exam The text is on the Moodle page of the course.	Where? Room B When? 2 pm	It is necessary to register at URL https://esami.unipi.it/esami2/index.php before Nov. 2, 2016. The exam will be about the material presented during the lectures up to and including Lessons 14 and 15 on "Syntax-Directed Translation to Intermediate Representation", (slides PLP-2016-11). This is covered by Chapter 1 of [GM], Chapter 1 (sec. 1-4 to 1-6) of [Scott], and Chapters 2, 3 (excluding Sec. 3.9), 4 (excluding Sec. 4.7.5 and 4.7.6), 5 and 6 (excluding Sections 6.3, 6.4.3, 6.4.4, 6.5, 6.7.4 and 6.8) of [ALSU].
19	Nov. 7, 2016	Code generation. Next-use information in basic blocks; A simple algorithm for code generation; Local allocation of registers: Global allocation of registers via graph coloring; Instruction selection with tree translation schemata; Optimal register allocation for expressions using Ershov numbers.	Slides: PLP-2016-14.pdf	[ALSU] Chapter 8.
20	Nov. 10, 2016	Global, Machine Independent Optimization; Data Flow Analysis. Liveness; Available Expressions, Very Busy Expressions, Reachable Definitions.	Slides: PLP-2016-15.pdf	[ALSU] Chapter 9.
21	Nov. 11, 2016	The Dataflow Framework for Global Analysis	Slides: PLP-2016-16b.pdf [fixed wrong definitions of semilattices in pages 9 and 10 - November 14]	[ALSU] Chapter 9.
22	Nov. 14, 2016	Loops in Control Flow Graphs Region Based Analysis Symbolic Analysis	Slides: PLP-2016-17.pdf	[ALSU] Chapter 9.
23	Nov. 17, 2016	Programming Languages and Abstraction Names and Bindings Scopes and Static Scoping Memory Management	Slides: PLP-2016-18.pdf	[Scott] Chapter 3, [GM] Chapter 4 and 5.
24	Nov. 18, 2016	Exercises	Proposed exercises: ES-PLP-2016-04-optimization.pdf	You are invited to continue solving the exercises at home. If you have any doubt about the text or want to discuss a solution with me, send me an email.
25	Nov. 21, 2016	Static Scoping Declarations and Definitions; Modules Local symbol tables during compilation Syntax-Directed Translation of three-address code in Scope LeBlanc & Cook data structure and lookup function	Slides: PLP-2016-19.pdf	[Scott] Chapter 3, [ALSU] Section 2.7, [GM] Chapter 4 and 5.
26	Nov. 24, 2016	Dynamic Scoping and its implementation Shallow and deep binding Functions returning procedures and retention Object Closures Type Systems Type Errors	Slides: PLP-2016-20.pdf Slides: PLP-2016-21.pdf, up to page 8.	[Scott] Sections 3.6 and 7.1, [GM] Sections 4.3, 5.5 and 8.1.
27	Nov. 25, 2016	Type checking Equivalence, compatibility and coercion Primitive and composite types Discrete and scalar types Tuples and records, Arrays, Array allocation	Slides: PLP-2016-21.pdf , up to page 48.	[Scott] Sections 7.2-4, [GM] Sections 8.2-6, [ALSU] Section 6.3. After finishing the current topic, I intend to dedicate some lessons to Haskell. You may start playing with an introductory tutorial of Haskell at http://www.haskell.org/, where you can find also a complete documentation about the language.
28	Nov. 28, 2016	Array allocation and layout; Generating intermediate code for array declaration and access; Strings; Disjoint unions; Variant and discriminated records; Algebraic data types and active patterns; Java classes as union types; Value Model and Reference Model of variables; Pointers; Techniques for avoiding dangling pointers; Pointers and Recursive Types; Pointers and Arrays in C.	Slides: PLP-2016-21.pdf	[Scott] Chapter 7, [GM] Chapter 8, [ALSU] Chapter 6.
29	Dec. 1, 2016	Functional programming languages; Introduction to Haskell; Lazyness; Towards Type Classes in Haskel; Generic Polimorphisms vs. Overloading.	Slides: PLP-2016-22.pdf, up to page 45.	[Scott] Chapter 10, [GM] Chapter 11, [Mitchell] Chapter 5 (Introduction to Haskell), Chapter 6 (Type Systems, Type Inference, and Polymorphism) and Chapter 7 (Type classes in 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/ Basic definitions related to lambda-calculus can be found in these pages of the draft monograph Models of Computation by Roberto Bruni and Ugo Montanari.
30	Dec. 2, 2016	Type Classes in Haskell; Constructor Classes; Monads and the Maybe Monad; Monads as Containers and as Computations.	Slides: PLP-2016-22.pdf, all. PLP-2016-23.pdf, till page 15.	[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/
31	Dec. 9, 2016	Exercises on Static/Dynamic Scoping, Deep/Shallow Binding, Type errors, Evaluation order, Allocation of Arrays.	Proposed exercises: ES-PLP-2016-05-scopes.pdf	You are invited to continue solving the exercises at home. If you have any doubt about the text or want to discuss a solution with me, send me an email.
32	Dec. 12, 2016, morning	Haskell: the IO Monad; Type inference in ML/Haskell	Slides: PLP-2016-23.pdf, all. PLP-2016-24.pdf.	Reading material about Haskell Monads: [PeytonJohnes2008], up to page 18 (on the Moodle page) https://wiki.haskell.org/Monads_as_containers https://wiki.haskell.org/Monads_as_computation [Mitchell] Chapter 6: pages 118-136 (Type inference)
33	Dec. 12, 2016, afternoon	Control Structures: Iterators, Recursion and Continuation Passing Style; Lambda expressions in Java 8	Slides: PLP-2016-25.pdf PLP-2016-26.pdf, till page 16.	http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html
34	Dec. 15, 2016	The Stream API in Java 8 Exercise on Data-Flow Analysis	Slides: PLP-2016-26.pdf, all.	http://docs.oracle.com/javase/tutorial/collections/streams/index.html
35	Dec. 16, 2016	Exercises on Haskell and Functional Programming Languages.	ES-PLP-2016-06-functional.pdf
--	Dec. 19, 2016	Second Midterm Exam The text and proposed solutions are on the Moodle page of the course.	Where? Room A1 When? 11 am	It is necessary to register at URL https://esami.unipi.it/esami2/index.php before Dec. 16, 2016. The exam will be about the material presented during the lectures from Lesson 16 ("Control-Flow Graphs", "Local and Global Optimization", slides PLP-216-12c) up to Lesson 33, slides PLP-2016-25 ("Iterators, Recursion and Continuation Passing Style"). The midterm exam will NOT include questions about Monads and Java 8 (Lambda expressions and Stream API).

LECTURER	Andrea Corradini `<andrea@di.unipi.it>`
Timetable	Monday 11-13, Room Fib N1 Thursday 16-18, Room Fib C1 Friday 14-16, Room Fib C1
Office hours	Click here To fix a date, send an email to `<andrea@di.unipi.it>`