%TOPIC%
From LRDE
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 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%)
- The Tiger Project. See the lecture notes:
tiger-project-intro.pdf, tiger-project-intro-handout.pdf and tiger-project-intro-handout-4.pdf.
- Ressources (http://www.lrde.epita.fr/~akim/ccmp/).
- Assignments (http://www.lrde.epita.fr/~akim/ccmp/assignments.html).
- Appel's books.
- Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~akim/ccmp/tiger.html).
- epita.cours.compile.
- Goals (C++, OO, DP, Management, Several Iterations, Testing, Documenting, Maintaining, Fixing, Understanding Computers, English).
- Non goals (Compiler Construction).
- Rules of the Game.
- No copy between groups.
- Tests are part of the project (test cases and frameworks should not be exchanged).
- Fixing mistakes earlier is better.
- Work between groups is encouraged as long as they don't cheat.
- Tests.
- Tests matter.
- Rules.
- A bug => a test.
- A suspicious behavior => one or several tests to isolate it.
- Don't throw away tests!
- Don't exchange tests! (bis repetita).
- C Compilation model (cpp, cc1, as, ld).
- Width of a compiler pipe (line, function, compilation unit).
- Compilers handling multiple input (sources languages) and multiple outputs (target assembly languages/processors).
- The case of GCC.
- Factoring the compiler components: intermediate representation(s).
- Front-end and back-ends.
- The Tiger Compiler pipe (annotated with tools and steps).
- Front-end: TC-0 - TC-5 (mandatory part).
- Back-end: TC-6 - TC-9 (optional part).
- Misc: students should overcome Make, Makefiles and seperate compilation, etc.
- Ressources (http://www.lrde.epita.fr/~akim/ccmp/).
- 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%)
- Development Tools, sections 2 and 3. See the lecture notes:
dev-tools.pdf, dev-tools-handout.pdf and dev-tools-handout-4.pdf.
- The Autotools diagram.
- configure 's options (--help, --prefix, etc.) and variables (CXX, CXXFLAGS, etc.).
- Source dir vs build dir; what do srcdir, top_srcdir and top_builddir mean?
- CONFIG_SITE
- The GNU Coding Standards.
- Other useful tools
- ccache
- distcc
Lectures 5 & 6: 2010-01-04 (Grp. B) & 2010-01-05 (Grp. A), 3 hours: Abstract Syntax (%roland%)
- 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%)
- Symbols, Identifiers and Bindings. See the lecture notes, names.pdf, names-handout.pdf and names-handout-4.pdf.
CMP 2
Lecture 1: 2010-02-05: 1.5 hour, Type-checking (%roland%)
- Types. See the lecture notes (up to page 40): type-checking.pdf, type-checking-handout.pdf and type-checking-handout-4.pdf.
Lecture 2: 2010-02-26: 1.5 hour, Type-checking & Intermediate languages (%roland%)
- Types. See the lecture notes (up to the end):
type-checking.pdf, type-checking-handout.pdf and type-checking-handout-4.pdf.
- Some details on the implementation of types and type-checking within the Tiger Compiler.
- Hierarchy of types (src/type/)
- src/type/README.
- Implementing atomic types: singletons.
- Resolving aliased types: Named and actual().
- Hierarchy of types (src/type/)
- Sequent Calculus
- 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."
- 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 |
- Examples of type rules: addition of 2 integers, if-then-else, if-then, addition of 3 integers, comparison of two variables, etc.
- Type inference
- (a_ ? _b : _c_) > 0
- (a_ ? _b : f_ (_b)) > 0
- (a_ ? _b : f_ (_c)) > 0
- 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%)
- Intermediate languages. See the lecture notes (end of section 1 and sections 2 and 3): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.
Lecture 4: 2010-03-26: 1.5 hour, Canonization, Microprocessors (%roland%)
- Intermediate languages. See the lecture notes (section 4.1): intermediate.pdf, intermediate-handout.pdf and intermediate-handout-4.pdf.
- Microprocessors, MIPS. See the lecture notes (section 1 and beginning of section 2): instr-selection.pdf, instr-selection-handout.pdf and instr-selection-handout-4.pdf.
Lecture 5: 2010-04-23: 1.5 hour, Instruction Selection, Liveness Analysis (%roland%)
- Instruction Selection. See the lecture notes (up to the end): instr-selection.pdf, instr-selection-handout.pdf and instr-selection-handout-4.pdf.
- Samples of MonoBURG inputs from the Tiger Compiler.
- Liveness Analysis. See the lecture notes (section 1): liveness.pdf, liveness-handout.pdf and liveness-handout-4.pdf.
Lecture 6: 2010-04-30: 1.5 hour, Liveness Analysis, Register Allocation (%roland%)
- Liveness Analysis. See the lecture notes (up to the end): liveness.pdf, liveness-handout.pdf and liveness-handout-4.pdf.
- Register Allocation. See the lecture notes (up to section 2.1): regalloc.pdf, regalloc-handout.pdf and regalloc-handout-4.pdf.
Lecture 7: 2010-06-02: 1.5 hour, Register Allocation (%roland%)
- Register Allocation. See the lecture notes (up to the end): regalloc.pdf, regalloc-handout.pdf and regalloc-handout-4.pdf.
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%)
- Subprograms. See the lecture notes: subprograms.pdf, subprograms-handout.pdf and subprograms-handout-4.pdf.
- Object Oriented History: Simula. See the lecture notes: object.pdf, object-handout.pdf and object-handout-4.pdf.
Lectures 3 & 4: 2010-06-01: 3 hours, History of Computing and Programming Languages (%akim%)
- History of Computing. See the lecture notes: history.pdf, history-handout.pdf and history-handout-4.pdf.
- History of Programming Languages, up to Algol 60. See the lecture notes: early-languages.pdf, early-languages-handout.pdf and early-languages-handout-4.pdf.
Lectures 5 & 6: 2010-06-08: 3 hours, History of Programming Languages, Object Oriented History (%roland%)
- History of Programming Languages, up to the end. See the lecture notes: early-languages.pdf, early-languages-handout.pdf and early-languages-handout-4.pdf.
- Object Oriented History, up to the end (Smalltalk & C++). See the lecture notes: object.pdf, object-handout.pdf and object-handout-4.pdf.
Lectures 7 & 8: 2010-06-10: 3 hours, Dynamic Dispatch in Object-Oriented Languages, Generic Programming (%roland%), Growing a Language by Guy Steele
- Dynamic Dispatch in Object-Oriented Languages.
- The C++ approach (virtual function tables).
- The SmartEiffel approach (ids and switches/tests).
- Generic Programming. See the lecture notes: generic.pdf, generic-handout.pdf and generic-handout-4.pdf.
- Growing a Language by Guy L. Steele Jr., Sun Microsystems (invited talk at OOPSLA'98). See the online video and transcript.
-- %roland% - 11 Jun 2010