Logo EPFL
LAMP
Ecole Polytechnique Fédérale de Lausanne
Type Systems
English only
 MENU
Lectures: Wednesday 13:15-15:00, room INM 203
Lab: Wednesday 15:15-17:00, room INF 119
  Goals

The study of type systems and of programming languages, from a type-theoretic perspective, has important applications in software engeneering, language design, high-performance compilers, and security. In this course the student will learn the basic principles of type systems as they a appear in modern programming languages. The acquired knowledge will be sufficient to design small type systems, but it will also sharpen the student's awareness of typeful programming as such. The latter is an indispensable task when programming in strongly typed languages.

  • simple types, lambda-calculus
  • normalization, references, exceptions
  • subtyping
  • recursive types
  • polymorphism
  • bounded quantification
  • advanced features of the Scala type system
Lecturer: Dr. Sebastian Maneth, stairsBC360, phone31226
Assistant: Burak Emir, stairsINR320, phone36867
Course schedule
Date 13:15-15:00, INM203 (Lecture) 15:15-17:00, INF119 (Lab)
20.10.04 1 Introduction, Arithmetic Expressions, Induction, Evaluation
Read: TAPL Ch 1 - 4
[ slides, 4 on 1, 6 on 1 ]
Arithmetic Expressions [Description/Errata/Solution]
27.10.04 2 (untyped) Lambda-Calculus
Read: TAPL Ch 5 - 7
[ slides, 4 on 1, 6 on 1 ]
de Bruijn terms, Call-by-Value evaluation [Description/Partial Solution/Tips]
03.11.04 3 Simply Typed Lambda-Calculus
Read: TAPL Ch 8 - 10
[ slides, 4 on 1, 6 on 1 ]
Simply Typed Lambda Calculus with Let [Description/Tips]
10.11.04 4 Extensions, Normalization
Read: TAPL Ch 11 - 14
[ slides, 4 on 1, 6 on 1 ]
"Buffer" session [Description]
17.11.04 5 Subtyping
Read: TAPL Ch 15 - 17
[ slides, 4 on 1, 6 on 1 ]
Records and Subtyping [Description]
24.11.04 6 Objects, Classes, and Featherweight Java
Read: TAPL Ch 18 - 19
[ slides, 4 on 1, 6 on 1 ]
Assignment: FJ
1.12.04 7 Featherweight Java
Read: TAPL Ch 19
[ slides, 4 on 1, 6 on 1 ]
Assignment: FJ
8.12.04 8 Type Reconstruction, Let-Polymorphism
Read: TAPL Ch 22
[ slides, 4 on 1, 6 on 1 ]
Assignment: FJ
15.12.04 9 Systems F and F-sub
Read: TAPL Ch 23,26
[ slides, 4 on 1, 6 on 1 ]
Written Assignment
22.12.04 10 System F-sub
Read: TAPL Ch 28
[ slides, 4 on 1, 6 on 1 ]
Discussion on written assignment
12.01.05 11 FGJ = FG + Generics
Read: FJ paper, GJ paper
[ slides, 4 on 1, 6 on 1 ]*
Type Reconstruction
19.01.05 12 Introduction to Scala's Type System
Read: Scalabale Component Abstraction paper, Expression Problem paper
[ slides: Overview ]
[ slides: Paper 1 ]
[ slides: Paper 2, 4 on 1, 6 on 1 ]
Assignment: FGJ
26.01.05 13 Featherweight Scala
[ [UPDATED] slides(PDF), 2 on 1(PS), 4 on 1(PS) ]
Assignment: FGJ
02.02.05 14 Featherweight Scala (cont.d)
[ [UPDATED] slides(PDF), 2 on 1(PS), 4 on 1(PS) ]
Assignment: FGJ

The course is accompanied by (written and programming) exercises. Students are allowed and encouraged to work in groups of two (both, for the programming and the written exercises). We plan two have 1-2 written assignments and one programming assignment which have to be turned in. The result will make up one third of your grade.

  Exam

The oral exam will be on 07.02.2005 between 8:00 and 13:00. It will cover the lecture notes (slides) and the corresponding information that can be found in the TAPL book and the articles linked from this page. Your final grade will be made up from the result of the oral exam (1/2) and from the result of the assignments (1/2).

Please register for a 20 minute time slot for your individual exam, by sending an email to Yvette.Dubuis@epfl.ch or by signing up with her in person (room INR328).

Course book

NEW:Cardelli and Wegner's On Understanding Types, Data Abstraction and Polymorphism is a very readable survey on type system features.

What follows are some facts that you might useful or interesting. You do not need them for the course, but should read them if you wonder why lambda calculus is considered a programming language.

  • Although the lambda calculus is so small, it very simple to extend it and define programming languages. Peter Landin has described this in his famous paper on "The next 700 Programming Languages".
  • The fact that imperative operations like assignment and sequencing are missing from the calculus does not mean that you cannot do it. You can get an idea how for instance from Phil Wadler's "Essence of Functional Programming" and Simon Peyton Jones, Phil Wadler: "Imperative Functional Programming".
  • If you want to learn more about the lambda calculus, the standard reference is Henk Barendregt's book "The Lambda Calculus: Its Syntax and Semantics". There is an online summary and a copy in the IC library.