Principles of Programming Languages [PLP-15]

Code 603AA - 9 Credits

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

Announcements

  • [January 20, 2016] The oral exams of tomorrow will start at 9:00 in room A1. The following students are registered, in the given order: Ahnmad Alleboudy, Lampei Li, Matteo Busi, Thomas Alderighi. Each exam will take around 60 minutes.

    [NEXT ORAL EXAMS] Oral exams are scheduled for January 27, starting at 10:30 am and February 3, starting at 9 am. To register you must (1) send an email to the lecturer indicating the preferred date, and (2) register on https://esami.unipi.it/esami/studentportal.php for the written proof of February 12, indicating in the notes "Oral exam only". The latter is needed to guarantee that you filled in the evaluation of the course.

  • [January 19, 2016] The results of the written exam of January 14 will be published today in the late afternoon. Students interested in checking the corrections to their written proofs are invited to come to the office of the lecturer today at 6:30 pm.
  • [January 5, 2016] Detailed syllabus of the course: PLP-2015-SYLLABUS.pdf.

    [ORAL EXAMS] Oral exams are scheduled for January 12, 20 and 21, starting at 9:30 (the place will be commmunicated later). To register you must (1) send an email to the lecturer indicating the preferred date, and (2) register on https://esami.unipi.it/esami/studentportal.php for the written proof of February 12, indicating in the notes "Oral exam only". The latter is needed to guarantee that you filled in the evaluation of the course.

    [WRITTEN EXAMS] The next written exams are scheduled for January 14 and February 12. Registration on https://esami.unipi.it/esami/studentportal.php is mandatory.
    The written exam will consist of exercises on the following topics only:

  • [December 13, 2015] Important: Given that the topics covered in the second part of the course (since November 9) are mostly of conceptual and theoretical nature, I decided to cancel the second mid-term exam scheduled for December 18. The students who passed the first mid-term exam are admitted to the oral examination, which will cover all the topics presented along the course.
  • [October 15, 2015] The first mid-term exam (a written proof) will be held on November 2 at 9 am in Room A1.
    Registration is mandatory: register at URL https://esami.unipi.it/esami/studentportal.php before Oct. 31, 2015.
    Send an email to the lecturer if you have any problem when registering.
  • [September 27, 2015] 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 the site.
  • [September 25, 2015] 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.
  • [September 24, 2015] The course starts today.
  • [September 21, 2015] The course starts today.

    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.

    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

    Textbooks

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

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

    Reading material

    For the results described in slides 4-8 of PLP-2015-07.pdf (context free grammars as systems of equations over languages and regular expressions as least solutions of systems of linear equations) you may consult: For an introduction to Denotational Semantics, read

    Course Schedule

    N.
    DATE
    TOPIC
    SLIDES
    NOTES
    1
    Sep. 24, 2015
    		 Presentation of the course
    Abstract Machines
    Preliminary test     		Slides: PLP-2015-01.pdf [GM], Chapter 1;
    2
    Sep. 25, 2015
    		 Compilation and interpretation schemes
    Cross compilation and bootstrapping
    Structure of compilers     		Slides: PLP-2015-02.pdf [Scott], Chapter 1 (sections 1-4 to 1-6).
    3
    Sep. 28, 2015
    		 Overview of a syntax-directed compiler front-end
    (Context-Free) Grammars, Chomsky hierarchy; Parse trees; Ambiguity, associativity and precedence; Syntax-directed translation; Translation schemes; Predictive recursive descent parsing; Left factoring, elimination of left recursion.     		Slides: PLP-2015-03.pdf [ALSU], Chapter 2.
    4
    Oct. 1, 2015
    		 Overview of a syntax-directed compiler front-end
    Lexical analysis; Intermediate code generation; Static checking     		Slides: PLP-2015-04.pdf [ALSU], Chapter 2.

    5

    Oct. 2, 2015

    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-2015-05.pdf

    [ALSU], Chapter 3.

    6

    Oct. 5, 2015

    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-2015-06.pdf

    [ALSU], Chapter 3.

    7

    Oct. 8, 2015

    Exercises on the topics presented so far, in particular on grammars and languages, Regular Expressions, Finite State Automata, Lexical Analysis.

    Proposed exercises: ES-PLP-2015-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. 9, 2015

    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; From REs to DFAs directly.

    Slides: PLP-2015-07.pdf

    [ALSU], Chapter 3.

    9

    Oct. 12, 2015

    Introduction to Parsing
    Left-Recursion Elimination; Left Factoring; Top-Down Parsing; LL(1) grammars; Predictive, Recursive-Descent Parsing; Table directed parsing; Error recovery during top-down parsing.

    Slides: PLP-2015-08.pdf

    [ALSU], Chapter 4.

    10

    Oct. 15, 2015

    Bottom-up Parsing
    Shift-reduce parsing; Handle; Shift/Reduce and Reduce/Reduce conflicts; LR(0) items; LR(0)-automaton; LR(0) parsing table; Structure of parsing algorithm; Driver; SLR, LR(1) and LALR parsing tables.

    Slides: PLP-2015-09.pdf

    [ALSU], Chapter 4.

    11

    Oct. 16, 2015

    Bottom-up Parsing
    LR parsing with ambiguous grammars; Error recovery in LR parsing Parser generators: yacc/bison Handling ambiguos grammars in yacc/bison

    Slides: PLP-2015-10.pdf

    [ALSU], Chapter 4.

    12

    Oct. 19, 2015

    Exercises on Parsing

    Proposed exercises: ES-PLP-2015-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. 22, 2015

    Syntax-Directed Translation

    Slides: PLP-2015-11.pdf

    [ALSU], Chapter 5.

    14

    Oct. 23, 2015

    Programming Languages and Abstraction
    Names and Bindings

    Slides: PLP-2015-12.pdf

    [Scott] Chapter 3, [GM] Chapter 4.

    15

    Oct. 26, 2015

    Static and dynamic scope; Modules

    Slides: PLP-2015-13.pdf, up to page 26.

    [Scott] Chapter 3, [GM] Chapter 4 and 5.

    16

    Oct. 29, 2015

    Implementation of static and dynamic scope
    A light introduction to Denotationl Semantics

    Slides: PLP-2015-13.pdf, all
    PLP-2015-14.pdf

    [Scott] Chapter 3, [GM] Chapter 4 and 5.
    See R.D. Tennent: The denotational semantics of programming languages, Communications of the ACM, Volume 19 Issue 8, Aug. 1976

    17

    Oct. 30, 2015

    Exercises

    18

    Nov. 2, 2015

    First Midterm Exam

    Where? Room A1
    When? 9 am

    It is necessary to register at URL https://esami.unipi.it/esami/studentportal.php before Oct. 31, 2015.

    The exam will be about the material presented during the lectures up to and including Lesson 13 on "Syntax-Directed Translation". This is covered by Chapter 1 of [GM], Chapter 1 (sec. 1-4 to 1-6) of [Scott], and Chapters 2, 3, 4 and 5 of [ALSU], with the exception of Sections 4.7.5 and 4.7.6.

    19

    Nov. 9, 2015

    More on Denotationl Semantics
    Not 1-1 bindings: Aliases and overloading
    Shallow and deep binding

    Slides: PLP-2015-15.pdf

    [Scott] Chapter 3, [GM] Chapter 4 and 5.

    20

    Nov. 12, 2015

    Shallow and deep binding
    Functions returning procedures and retention
    Object Closures
    Control Flow: evaluation of expressions

    Slides: PLP-2015-16.pdf
    Slides: PLP-2015-17.pdf

    [Scott] Chapter 3 and 6.1, [GM] Chapter 7.2 and 6.1.

    21

    Nov. 13, 2015

    Value Model and Reference Model
    Structured and unstructured flow
    Sequencing and Selection
    Logically- and Enumeration-Controlled Iteration

    Slides: PLP-2015-18.pdf

    [Scott] Chapter 6.3-6.5, [GM] Chapter 6.2-6.4.

    22

    Nov. 16, 2015

    Logically- and Enumeration-Controlled Iteration
    Iterators
    Intermediate Code Generation
    Intermediate Representations
    Syntax-directed translation to Three Address Code

    Slides: PLP-2015-18.pdf
    Slides: PLP-2015-19.pdf.

    [Scott] Chapter 6.5, [ALSU] Chapter 6.

    23

    Nov. 19, 2015

    Syntax-directed translation to Three Address Code
    Handling names in local scopes
    Translation of declarations, expressions and statements in scope
    Translation of short-circuit boolean expressions
    Translation of conditionals and iteration
    Use of backpatching lists.

    Slides: PLP-2015-20.pdf

    [Scott] Chapter 6.5, [ALSU] Chapter 6.

    24

    Nov. 20, 2015

    Type systems, Type safety, Type checking
    Equivalence, compatibility and coercion
    Primitive and composite types
    Discrete and scalar types
    Tuples and records, Arrays

    Slides: PLP-2015-21.pdf

    [Scott] Chapter 7, [GM] Chapter 8, [ALSU] Chapter 6.

    25

    Nov. 23, 2015

    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; Pointers; Techniques for avoiding dangling pointers

    Slides: PLP-2015-22.pdf, up to page 40.

    [Scott] Chapter 7, [GM] Chapter 8, [ALSU] Chapter 6.

    26

    Nov. 26, 2015

    Pointers and Recursive Types; Pointers and Arrays in C. Control abstraction; Parameter Passing Modes and Mechanisms.

    Slides: PLP-2015-22.pdf, all.
    Slides: PLP-2015-23.pdf

    [Scott] Chapter 8, [GM] Chapter 7.

    27

    Nov. 27, 2015

    Data Abstraction; Obiect-Oriented Programming.

    Slides: PLP-2015-24.pdf

    [Scott] Chapter 9, [GM] Chapter 9-10.

    28

    Nov. 30, 2015

    Functional programming languages; Introduction to Haskell.

    Slides: PLP-2015-25.pdf

    [Scott] Chapter 10, [GM] Chapter 11, [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/

    29

    Dec. 3, 2015

    Type Classes in Haskel; Monads and the Maybe Monad.

    Slides: PLP-2015-26.pdf
    Slides: PLP-2015-27.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/

    30

    Dec. 4, 2015

    Monads as Containers and as Computations; the IO Monad; Recursion and Continuation Passing Style; Type inference in ML and Hskell.

    Slides: PLP-2015-27.pdf, all
    Slides: PLP-2015-28.pdf (recursion and continuations)
    Slides: PLP-2015-29.pdf (type inference)

    [Mitchell] Chapter 6: pages 118-136 (Type inference)
    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

    31

    Dec. 7, 2015

    Scripting Languages

    Slides: PLP-2015-30.pdf

    [Scott] Chapter 13.

    Students familiar with Java who are interested in the extensions to Java introduced in Java 8 may read the following slides about "Lambda expressions and Stream API in Java 8" :
    PLP-2015-30-Java8.pdf
    Additional reading material:
    http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html
    http://docs.oracle.com/javase/tutorial/collections/streams/index.html

    32

    Dec. 10, 2015

    Code generation, Optimization.

    Slides: PLP-2015-31.pdf

    [ALSU] Chapter 8.

    33

    Dec. 11, 2015

    Code generation, Optimization (2).

    Slides: PLP-2015-32.pdf

    [ALSU] Chapter 8 and 9.

    34

    Dec. 14, 2015

    Data Flow Analysis and Machine Independent Optimization.

    Slides: PLP-2015-33.pdf

    [ALSU] Chapter 9.

    Links