Courses/CcmpTylaLogIng2016 (Ing1 students)

This page contains the log of the topics of

• the Compiler Construction Course 1 (CMP1),
• the Compiler Construction Course 2 (CMP2), and
• the Typology of Programming Languages Course (TYLA)

for Ing1 students of class EPITA 2016 (i.e., from December 2013 to June 2014). The topic was started with the Formal Languages Lecture (THL).

CMP1

Lecture 1: 2012-11-21 (Grp. B) & 2012-11-22 (Grp. A), 2 hours: Introduction to the Project

1. The Tiger Project. See the lecture notes: tiger-project-intro.pdf, tiger-project-intro-handout.pdf and tiger-project-intro-handout-4.pdf.
   1. Ressources (http://www.lrde.epita.fr/~tiger/).
      1. Assignments (http://www.lrde.epita.fr/~tiger/assignments.html).
      2. Appel's books.
      3. Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~tiger/tiger.html).
      4. epita.cours.compile.
   2. Goals (C++, OO, DP, Management, Several Iterations, Testing, Documenting, Maintaining, Fixing, Understanding Computers, English).
   3. Non goals (Compiler Construction).
   4. Rules of the Game.
      1. No copy between groups.
      2. Tests are part of the project (test cases and frameworks should not be exchanged).
      3. Fixing mistakes earlier is better.
      4. Work between groups is encouraged as long as they don't cheat.
   5. Tests.
      1. Tests matter.
      2. Rules.
         1. A bug => a test.
         2. A suspicious behavior => one or several tests to isolate it.
         3. Don't throw away tests!
         4. Don't exchange tests! (bis repetita).
   6. C Compilation model (cpp, cc1, as, ld).
   7. Width of a compiler (granularity of compiled entities).
   8. Tiger Compiler pipeline (front end only)
   9. Compilers handling multiple input (sources languages) and multiple outputs (target assembly languages/processors).
      1. The case of GCC.
      2. Factoring the compiler components: intermediate representation(s).
      3. Front-end and back-ends.
   10. Other compilation strategies.
   11. The Tiger Compiler pipe (annotated with tools and steps).
       1. Front-end: TC-0 - TC-3 (mandatory part), TC-4 - TC-5 (optional part).
       2. Back-end: TC-6 - TC-9 (optional part).
   12. Misc: students should overcome Make, Makefiles and seperate compilation, etc.

Lecture 2: 2012-12-10 (Grp. B & A), 2 hours: Scanner and Parser Hints

1. Additional details and hints about the scanner and the parser: The Scanner and the Parser. See the lecture notes: scanner.pdf, scanner-handout.pdf and scanner-handout-4.pdf.
   1. Symbols (light-weight, shared and non-mutable strings used to represent identifiers).
   2. Extra information (in addition to tokens/terminals) passed between the scanner and the parser.
      1. Semantic values.
      2. Locations.
   3. Various improvements on the scanner and the parser.
      1. Error recovery by deletion (using the error symbol).
      2. Pure (reentrant) parser and scanner.

Lectures 3 and 4: 2013-02-04 (Grp. A) & 2013-02-08 (Grp. B), 4 hours: Architecture of tc (tasks), Autotools, Development Tools, Abstract Syntax

1. Architecture of the Tiger Compiler (tc).
   1. Modules: parse, ast, bind, etc.
      1. Pure libraries providing actual services.
      2. Tasks (non-pure services) using a declarative system: Development Tools, section 1 (tc Tasks). See the lecture notes: dev-tools.pdf, dev-tools-handout.pdf and dev-tools-handout-4.pdf.
         1. Command-line options.
         2. Declaration of dependencies.
         3. Actual computations delegated to pure libraries.
   2. Driver (tc.cc).
      1. Instantiates a tasks manager, used to record all existing tasks at start-up and later compute the steps to performe according to the dependencies of the invoked tasks.
      2. Workflow computed by the task manager from the options passed to the driver, triggering corresponding tasks and their dependencies ( la Make).
      3. Error management: catches exceptions (including misc::error) and displays error messages.
2. Autoconf and Automake
   1. History: Unix, Unices, configuration systems (imake, configure), portability issues (broken tools, broken/missing functions, libraries, etc.).
   2. Generating configure with Autoconf
      1. The choice of (a subset of) the Bourne Shell for portability reasons.
      2. Generating to encapsulate tests, simplify, shorten and reuse shell script bits.
      3. Using the M4 macro language.
      4. Autotools Diagram: Autoconf.
   3. Generating Makefile (s) with Automake and configure.
      1. Generating to simplify and shorten portable Makefile bits.
      2. Substituting variables (@VAR@) in Makefile.in using configure (BTW: variables listed in configure --help).
      3. Completing the Autotools diagram: Automake.
      4. Developer side vs User side.
   4. A word on aclocal.
   5. Hands-on example.
      1. A simple program.
         1. Writing hello-world.cc.
         2. Adding Makefile.am.
         3. Running autoscan.
         4. Adjusting config.scan to create config.ac (initializing Automake, avoiding autoheader).
         5. Running alocal, automake -a -c (and installing helpers) and autoconf.
         6. Running ./configure.
         7. Running make.
         8. Running ./hello-world.
      2. Adding a (static) library.
         1. Writing the client (hello.cc) and the library (greet.hh and greet.cc).
         2. Adjusting Makefile.am (lib_LIBRARIES vs noinst_LIBRARIES), and configure.ac (AC_PROG_RANLIB).
         3. Updating by running make (and not the Autotools).
         4. Compiling the client (hello) by adjusting Makefile.am (in particular, link to libgreet.a using hello_LDADD).
         5. Running make again.
         6. Running ./hello.
      3. Adding tests.
         1. TESTS in Makefile.am and make check.
         2. Compiling test-only (not installed) programs: check_PROGRAMS.
      4. Distributing.
         1. make dist.
         2. make distcheck.
         3. Don't forget to adjust the arguments of AC_INIT in configure.ac.
      5. Installing.
         1. make install.
         2. configure --prefix, $prefix, $bindir, $libdir, etc. and bin_, lib_ prefixes of primaries (PROGRAMS, LIBRARIES, etc.).
         3. make uninstall (careful, very limited).
   6. Misc.
      1. Generating tests with configure (e.g. so that they can find $srcdir).
      2. Changing variables (e.g. CXXFLAGS) at the configuration step (=./configure CXXFLAGS...=; global) or at the build step (=make CXXFLAGS...=; local).
      3. autoheader and config.h: getting rid of limitations of using -D options to pass options to the compiler.
      4. Pros and cons of using multiple Makefile s in a multi-directory project.
      5. srcdir vs builddir, running configure from a directory other than the source dir.
3. Development Tools. See the lecture notes: dev-tools.pdf, dev-tools-handout.pdf and dev-tools-handout-4.pdf.
4. Abstract Syntax, up to basic Visitors (sec. 2.3, p. 51) and except AST Generators (p. 613), Tagging the Abstract Syntax Tree (p. 22), Processing and Dispatching (p. 3638), Multimethods (p. 4042). See the lecture notes, ast.pdf, ast-handout.pdf and ast-handout-4.pdf.

Lecture 5: 2013-02-20 (Grp. A & B), 2 hours: Abstract Syntax

• Abstract Syntax. See the lecture notes, ast.pdf, ast-handout.pdf and ast-handout-4.pdf.

Lecture 6: 2013-02-27 (Grp. A & B), 2 hours: Names, Identifiers and Bindings

• Names, Identifiers and Bindings. See the lecture notes, names.pdf, names-handout.pdf and names-handout-4.pdf.

CMP2

Lecture 1: 2013-03-11 (Grp. A & B), 2 hours: Type-checking

1. Types. See the lecture notes (sections 1 and 2): type-checking.pdf, type-checking-handout.pdf and type-checking-handout-4.pdf.
2. Some details on the implementation of types and type-checking within the Tiger Compiler.
   1. Hierarchy of types (src/type/)
      1. src/type/README.
      2. Implementing atomic types: singletons.
      3. Resolving aliased types: Named and actual().

Lecture 2: 2013-04-25 (Grp. A & B), 2 hours: Intermediate languages

1. Intermediate languages. See the lecture notes (up to section 4.1 (included), except dynamic allocation, non-local variables & static link, calling conventions, Ix, translation of complex expressions, proper explanation of frame::{Access,Frame} vs translate::{Access,Level}): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.

Lecture 3: 2013-05-02 (Grp. A & B), 2 hours: Intermediate languages, Canonization (Linearization)

• Intermediate languages (dynamic allocation, non-local variables & static link, calling conventions, Ix, translation of complex expressions, proper explanation of frame::{Access,Frame} vs translate::{Access,Level}). See the lecture notes (remaining sections up to section 4.1): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.
• Canonization (Linearization). See the lecture notes (section 4.2, up to slide 100): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.

Lecture 4: 2013-05-06 (Grp. A & B), 2 hours: Canonization (Basic Blocks, Traces), Microprocessors, Instruction Selection

• Canonization (Basic Blocks, Traces). See the lecture notes (up to the end): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.
• Microprocessors, Instruction Selection. See the lecture notes: instr-selection.pdf, instr-selection-handout.pdf and instr-selection-handout-4.pdf.
• Examples of MonoBURG input files from the Tiger Compiler (Tree to MIPS).

Lecture 5: 2013-05-30 (Grp. A & B), 2 hours: Liveness Analysis, Register Allocation

• Liveness Analysis. See the lecture notes: liveness.pdf, liveness-handout.pdf and liveness-handout-4.pdf.
• Register Allocation: Coloring by Simplification, Spilling, Coalescing, Precolored Nodes, Caller- and Callee-Saved Registers, Implementation, Alternatives to Graph Coloring. See the lecture notes: regalloc.pdf, regalloc-handout.pdf and regalloc-handout-4.pdf.

Lecture 6: 2013-06-13 (Grp. A & B), 2 hours: Selected Topics About the Future of Languages and Compilation

• Two presentations about languages and compilation:
  • Modules (e.g. a module system for the C language family), by Douglas Gregor (Apple) at the 2012 LLVM Developers' Meeting.
  • Concepts Lite: Constraining Template Arguments with Predicates, by Andrew Sutton, Bjarne Stroustrup and Gabriel Dos Reis (Texas A&M University) at C++Now 2013.

TYLA

Lecture 1: 2013-02-27 (Grp. B & A), 2 hours: History of Computing and Programming Languages

1. History of Computing. See the lecture notes, history.pdf, history-handout.pdf and history-handout-4.pdf.
2. History of Programming Languages: FOTRAN, Algol (section 1.1 and 1.2). See the lecture notes, early-languages.pdf, early-languages-handout.pdf and early-languages-handout-4.pdf.

Lecture 2: 2013-03-06 (Grp. B & A), 2 hours: History of Programming Languages, Object-Oriented History

• History of Programming Languages. See the lecture notes, early-languages.pdf, early-languages-handout.pdf and early-languages-handout-4.pdf.
• Object-Oriented History: Simula, Smalltalk-72, Smalltalk-76. See the lecture notes, object.pdf, object-handout.pdf and object-handout-4.pdf.

Lecture 3: 2013-03-13 (Grp. B & A), 2 hours: Object-Oriented History, Subprograms

• Object-Oriented History: Smalltalk-80, C++. See the lecture notes, object.pdf, object-handout.pdf and object-handout-4.pdf.
• Subprograms (sections 1 and 2). See the lecture notes, subprograms.pdf, subprograms-handout.pdf and subprograms-handout-4.pdf.

Lecture 4: 2013-03-20 (Grp. B & A), 2 hours: Subprograms, Some Traits of Functional Programming Languages

• Subprograms. See the lecture notes, subprograms.pdf, subprograms-handout.pdf and subprograms-handout-4.pdf.
  • In-depth explanation of the example of the numerical differentiation in Haskell.
• Some Traits of Functional Programming Languages.
  • Currying, partially applied functions, closures.
  • Pure vs impure languages.
  • Lazy vs strict evaluation, equational reasoning, infinite lists.
    • loop.hs (lazy evaluation, terminates)
    • loop.ml (strict evaluation, does not terminate)
    • loop-lazy.ml (local/partial lazy evaluation, terminates)

loop.hs:

main =
  let y = 0
		loop z = if z > 0 then z else loop z
		f x	 = if y > 8 then x else -y
  in
	 f (loop y)

loop.ml:

let y = 0 in
let rec loop z = if z > 0 then z else loop z in
let	  f x	 = if y > 8 then x else -y in
f (loop y)
;;

loop-lazy.ml:

let y = 0 in
let rec loop z = if z > 0 then z else loop z in
let	  f x	 = if y > 8 then (Lazy.force x) else -y in
f (lazy (loop y))
;;

Lecture 5: 2013-03-25 (Grp. B & A), 2 hours: Type-checking, Generic Programming

1. Sequent Calculus
   1. In English: "If alpha is of type Int in the context Gamma and beta is of type Int in the context Gamma, then alpha + beta is of type Int in the context Gamma."
   2. Using symbols (where ⊢ ("tee" or "turnstile") is the symbol meaning "yields" or "proves"): ${\frac {\Gamma \vdash \alpha :Int\quad \Gamma \vdash \alpha :Int}{\Gamma \vdash \alpha +\beta :Int}}$
   3. Examples of type rules: addition of 2 integers, if-then-else, if-then, addition of 3 integers, comparison of two variables, etc.
   4. Type inference
      1. (a ? b : c) > 0
      2. (a ? b : f(b)) > 0
      3. (a ? b : f(c)) > 0
2. Generic Programming (sections 1, 2 and 3). See the lecture notes, generic.pdf, generic-handout.pdf and generic-handout-4.pdf.
3. Genericity in Haskell. See the lecture notes (in section 2.3): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.

Lecture 6: 2013-03-26 (Grp. A & B), 2 hours: Genericity in C++, the Standard Template Library (STL) and Template Metaprogramming, OOP vs GP

1. Generic Programming (sections 4). See the lecture notes, generic.pdf, generic-handout.pdf and generic-handout-4.pdf.
2. More on GP, concepts and links between GP and OOP.
   1. OOP vs OOP
      1. OOP: two levels: Interfaces and classes (compile time), instances (run time).
      2. GP: three levels: Concepts (documentation/design time), models/types (compile time) and instances (run time).
      3. Single algorithm "instantiation"/compilation (OOP) vs several (GP).
         1. 1-time compiling/loose coupling between compiled algorithms and data structures (OOP) vs many-time compiling/strong coupling between compiled algorithms and data structures (GP).
         2. No or little compile-time optimization (OOP, cost of virtual) vs opportunities for compile-time optimizations (GP).
      4. Constraint through interface inheritance (OOP) vs lack of explicit constraint (classic GP) or implicit/explicit concept checking (C++ concept proposal)
   2. Solutions/proposal to add/express GP constraints in C++:
      1. Boost Concept Checking Library (BCCL)
      2. "Concepts" proposals
      3. "Concepts light" proposal
      4. By Mixing OOP and GP
         1. The Curiously Recurring Template Pattern (CRTP). Mixing two kinds of relations between a base class (top) and a derived class (bottom), in opposite ways:
            1. Inheritance (top-down).
            2. Parameter passing (bottom-up).
         2. Using abstractions (Abstraction<T>) to constrain algorithms.
            1. Static knowledge of the exact type of the argument
            2. Static conversion to exact type (instead of dynamic_cast in traditional OOP)
            3. Implementing static dispatch based on abstractions.