%TOPIC%

From LRDE


This page contains the log of the topics of

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



CMP 1

Lectures 1 & 2: 2009-12-07 (Grp. B) & 2009-12-08 (Grp. A), 3 hours: Introduction to the Project, Development Tools (%roland%)

  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/~akim/ccmp/).
      1. Assignments (http://www.lrde.epita.fr/~akim/ccmp/assignments.html).
      2. Appel's books.
      3. Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~akim/ccmp/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 pipe (line, function, compilation unit).
    8. 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.
    9. The Tiger Compiler pipe (annotated with tools and steps).
      1. Front-end: TC-0 - TC-5 (mandatory part).
      2. Back-end: TC-6 - TC-9 (optional part).
    10. Misc: students should overcome Make, Makefiles and seperate compilation, etc.
  2. Development Tools, section 1 (tc Tasks). See the lecture notes:

dev-tools.pdf, dev-tools-handout.pdf and dev-tools-handout-4.pdf.

Lectures 3 & 4: 2009-12-14 (Grp. B) & 2009-12-15 (Grp. A), 3 hours: Development Tools (%roland%)

  1. Development Tools, sections 2 and 3. See the lecture notes:

dev-tools.pdf, dev-tools-handout.pdf and dev-tools-handout-4.pdf.

    1. The Autotools diagram.
    2. configure 's options (--help, --prefix, etc.) and variables (CXX, CXXFLAGS, etc.).
    3. Source dir vs build dir; what do srcdir, top_srcdir and top_builddir mean?
    4. CONFIG_SITE
    5. The GNU Coding Standards.
    6. Other useful tools
      1. ccache
      2. distcc

Lectures 5 & 6: 2010-01-04 (Grp. B) & 2010-01-05 (Grp. A), 3 hours: Abstract Syntax (%roland%)

  1. Abstract Syntax. See the lecture notes,

ast.pdf, ast-handout.pdf and ast-handout-4.pdf (sections 1, 2 and 3, except pages 68-76 for Grp. A)

Lectures 7 & 8: 2010-01-11 (Grp. B) & 2010-01-12 (Grp. A), 3 hours, Abstract Syntax (cont.) & Names, identifiers and bindings (%roland%)


CMP 2

Lecture 1: 2010-02-05: 1.5 hour, Type-checking (%roland%)

Lecture 2: 2010-02-26: 1.5 hour, Type-checking & Intermediate languages (%roland%)

  1. Types. See the lecture notes (up to the end):

type-checking.pdf, type-checking-handout.pdf and type-checking-handout-4.pdf.

  1. 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().
  2. 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."

    1. Using symbols (where ||- ("tee" or "turnstile") is the symbol meaning "yields" or "proves"):

%TABLE{tableborder="0" tablerules="rows" cellpadding="3" cellspacing="3" databg="none"}%

Γ |- α : Int    Γ |- β : Int
Γ |- α + β : Int
    1. Examples of type rules: addition of 2 integers, if-then-else, if-then, addition of 3 integers, comparison of two variables, etc.
    2. Type inference
      1. (a_ ? _b : _c_) > 0
      2. (a_ ? _b : f_ (_b)) > 0
      3. (a_ ? _b : f_ (_c)) > 0
  2. Intermediate languages. See the lecture notes (up to page 13):

intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.

Lecture 3: 2010-03-19: 1.5 hour, Intermediate languages (%roland%)

Lecture 4: 2010-03-26: 1.5 hour, Canonization, Microprocessors (%roland%)

Lecture 5: 2010-04-23: 1.5 hour, Instruction Selection, Liveness Analysis (%roland%)


Lecture 6: 2010-04-30: 1.5 hour, Liveness Analysis, Register Allocation (%roland%)


Lecture 7: 2010-06-02: 1.5 hour, Register Allocation (%roland%)

Lecture 8: 2010-06-02: 1.5 hour, Techniques used within the Tiger Compiler (%roland%)

  • Using the internal extensible array of C++ streams: std::ios_base::xalloc, std::ios_base::iword, std::ios_base::pword.
  • Extending the xalloc mechanism: TC's misc::xalloc<StoredType>.
  • Template instantiation models: implicit (automatic) vs explicit instanciation. Exported template definitions (export keyword).
  • Program Transformation in a Nutshell:
    • Applications (optimization, translation, desugaring, etc.).
    • Abstract vs Concrete syntax.
    • Hand-made node instantiation vs TWEAST-based construction.
    • Matching and building patterns.
      • Using the language's built-in pattern matching feature (OCaml, etc.)
      • Using multimethods
        • Other uses of multimethods (intersections of shapes, etc.)
      • By extending the principle of Visitor.
    • Traversal strategies.
      • Using visitors.
      • Using visitor combinators.


TYLA

Lectures 1 & 2: 2010-05-25: 3 hours, Suprograms, Object Oriented History: Simula (%roland%)

Lectures 3 & 4: 2010-06-01: 3 hours, History of Computing and Programming Languages (%akim%)

Lectures 5 & 6: 2010-06-08: 3 hours, History of Programming Languages, Object Oriented History (%roland%)

Lectures 7 & 8: 2010-06-10: 3 hours, Dynamic Dispatch in Object-Oriented Languages, Generic Programming (%roland%), Growing a Language by Guy Steele


-- %roland% - 11 Jun 2010

Retrieved from "https://www.lrde.epita.fr/index.php?title=Courses/CcmpTylaLogIng2012&oldid=8215"