View source for Courses/CcmpTylaLogIng2016 (Ing1 students)

__NOTOC__

This page contains the log of the topics of
* the [[CMP1-Course|Compiler Construction Course 1 (CMP1)]],
* the [[CMP2-Course|Compiler Construction Course 2 (CMP2)]], and
* the [[TYLA-Course|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 [[Epita/THL-Course|Formal Languages Lecture (THL)]].




== CMP1 ==

=== Lecture 1: 2013-12-09 (Grp. B & A), 2 hours: Introduction to the Tiger Project ===

# Introduction to The Tiger Project.  See the lecture notes: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/tiger-project-intro.pdf tiger-project-intro.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/tiger-project-intro-handout.pdf tiger-project-intro-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/tiger-project-intro-handout-4.pdf tiger-project-intro-handout-4.pdf].
## Ressources (http://www.lrde.epita.fr/~tiger/).
### Assignments (http://www.lrde.epita.fr/~tiger/assignments.html).
### Appel's books.
### Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~tiger/tiger.html).
### <tt>epita.cours.compile</tt>.
## 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 (<tt>cpp</tt>, <tt>cc1</tt>, <tt>as</tt>, <tt>ld</tt>).
## Width of a compiler (granularity of compiled entities).
## Tiger Compiler pipeline (front end only)
## 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.

=== Lecture 2: 2013-12-16 (Grp. B & A), 2 hours: Introduction to the Tiger Project (cont.), Architecture of <tt>tc</tt> (tasks), Autotools ===

# Introduction (cont.)
## Other compilation strategies.
## The Tiger Compiler pipe (annotated with tools and steps).
### Front-end: TC-0 - TC-3 (mandatory part), TC-4 - TC-5 (optional part).
### Back-end: TC-6 - TC-9  (optional part).
## Misc: students should overcome Make, <tt>Makefiles</tt> and seperate compilation, etc.
# Architecture of the Tiger Compiler (<tt>tc</tt>).
## Modules: <tt>parse</tt>, <tt>ast</tt>, <tt>bind</tt>, etc.
### Pure libraries providing actual services.
### Tasks (non-pure services) using a declarative system: Development Tools, section 1 (<tt>tc</tt> Tasks).  See the lecture notes: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/dev-tools.pdf dev-tools.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/dev-tools-handout.pdf dev-tools-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/dev-tools-handout-4.pdf dev-tools-handout-4.pdf].
#### Command-line options.
#### Declaration of dependencies.
#### Actual computations delegated to pure libraries.
## Driver (<tt>tc.cc</tt>).
### 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.
### Workflow computed by the task manager from the options passed to the driver, triggering corresponding tasks and their dependencies ( la Make).
### Error management: catches exceptions (including <tt>misc::error</tt>) and displays error messages.
# Autoconf and Automake
## History: Unix, Unices, configuration systems (<tt>imake</tt>, <tt>configure</tt>), portability issues (broken tools, broken/missing functions, libraries, etc.).
## Generating <tt>configure</tt> with Autoconf
### The choice of (a subset of) the Bourne Shell for portability reasons.
### Generating to encapsulate tests, simplify, shorten and reuse shell script bits.
### Using the M4 macro language.
### Autotools Diagram: Autoconf.
## Generating <tt>Makefile</tt> (s) with Automake and <tt>configure</tt>.
### Generating to simplify and shorten portable <tt>Makefile</tt> bits.
### Substituting variables (<tt>@VAR@</tt>) in <tt>Makefile.in</tt> using <tt>configure</tt> (BTW: variables listed in <tt>configure --help</tt>).
### Completing the Autotools diagram: Automake.
### Developer side vs User side.
## A word on <tt>aclocal</tt>.
## Hands-on example.
### A simple program.
#### Writing <tt>hello-world.cc</tt>.
#### Adding <tt>Makefile.am</tt>.
#### Running <tt>autoscan</tt>.
#### Adjusting <tt>config.scan</tt> to create <tt>config.ac</tt> (initializing Automake, avoiding <tt>autoheader</tt>).
#### Running <tt>alocal</tt>, <tt>automake -a -c</tt> (and installing helpers) and <tt>autoconf</tt>.
#### Running <tt>./configure</tt>.
#### Running <tt>make</tt>.
#### Running <tt>./hello-world</tt>.

=== Lectures 3 : 2014-02-17 (Grp. A & B), 2 hours: Autotools (cont.), Development Tools ===

# Autoconf and Automake (cont.)
## Hands-on example (cont.)
### Adding a (static) library.
#### Writing the client (<tt>hello.cc</tt>) and the library (<tt>greet.hh</tt> and <tt>greet.cc</tt>).
#### Adjusting <tt>Makefile.am</tt> (<tt>lib_LIBRARIES</tt> vs <tt>noinst_LIBRARIES</tt>), and <tt>configure.ac</tt> (<tt>AC_PROG_RANLIB</tt>).
#### Updating by running <tt>make</tt> (and not the Autotools).
#### Compiling the client (<tt>hello</tt>) by adjusting <tt>Makefile.am</tt> (in particular, link to <tt>libgreet.a</tt> using <tt>hello_LDADD</tt>).
#### Running <tt>make</tt> again.
#### Running <tt>./hello</tt>.
### Adding tests.
#### <tt>TESTS</tt> in <tt>Makefile.am</tt> and <tt>make check</tt>.
#### Compiling test-only (not installed) programs: <tt>check_PROGRAMS</tt>.
### Distributing.
#### <tt>make dist</tt>.
#### <tt>make distcheck</tt>.
#### Don't forget to adjust the arguments of <tt>AC_INIT</tt> in <tt>configure.ac</tt>.
### Installing.
#### <tt>make install</tt>.
#### <tt>configure --prefix</tt>, <tt>$prefix</tt>, <tt>$bindir</tt>, <tt>$libdir</tt>, etc. and <tt>bin_</tt>, <tt>lib_</tt> prefixes of primaries (<tt>PROGRAMS</tt>, <tt>LIBRARIES</tt>, etc.).
#### <tt>make uninstall</tt> (careful, very limited).
## Misc.
### Generating tests with <tt>configure</tt> (e.g. so that they can find <tt>$srcdir</tt>).
### Changing variables (e.g. <tt>CXXFLAGS</tt>) at the configuration step (<tt>=./configure CXXFLAGS</tt>...=; global) or at the build step (<tt>=make CXXFLAGS</tt>...=; local).
### <tt>autoheader</tt> and <tt>config.h</tt>: getting rid of limitations of using <tt>-D</tt> options to pass options to the compiler.
### Pros and cons of using multiple <tt>Makefile</tt> s in a multi-directory project.
### <tt>srcdir</tt> vs <tt>builddir</tt>, running <tt>configure</tt> from a directory other than the source dir.
# Development Tools.  See the lecture notes: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/dev-tools.pdf dev-tools.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/dev-tools-handout.pdf dev-tools-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/dev-tools-handout-4.pdf dev-tools-handout-4.pdf].

=== Lecture 4: 2014-02-21 (Grp. A & B), 2 hours: Scanner and Parser Hints ===

# Additional details and hints about the scanner and the parser: The Scanner and the Parser.  See the lecture notes: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/scanner.pdf scanner.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/scanner-handout.pdf scanner-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/scanner-handout-4.pdf scanner-handout-4.pdf].
## Symbols (light-weight, shared and non-mutable strings used to represent identifiers).
## Extra information (in addition to tokens/terminals) passed between the scanner and the parser.
### Semantic values.
### Locations.
## Various improvements on the scanner and the parser.
### Error recovery by deletion (using the <tt>error</tt> symbol).
### Pure (reentrant) parser and scanner.

=== Lecture 5: 2014-02-24 (Grp. A & B), 2 hours: Abstract Syntax ===

* Abstract Syntax, up to basic Visitors (sec. 2.3, p. 51).  See the lecture notes, [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/ast.pdf ast.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/ast-handout.pdf ast-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/ast-handout-4.pdf ast-handout-4.pdf].

=== Lecture 6: 2014-02-25 (Grp. B & A), 2 hours: Abstract Syntax (in place of TYLA) ===

* Abstract Syntax, up to the end. See the lecture notes, [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/ast.pdf ast.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/ast-handout.pdf ast-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/ast-handout-4.pdf ast-handout-4.pdf].

=== Lecture 7: 2013-03-04 (Grp. B & A), 2 hours: Names, Identifiers and Bindings ===

* Names, Identifiers and Bindings. See the lecture notes, [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/names.pdf names.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/names-handout.pdf names-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/names-handout-4.pdf names-handout-4.pdf].


== CMP2 ==

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

# Types. See the lecture notes (sections 1 and 2): [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/type-checking.pdf type-checking.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/type-checking-handout.pdf type-checking-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/type-checking-handout-4.pdf type-checking-handout-4.pdf].
# Some details on the implementation of types and type-checking within the Tiger Compiler.
## Hierarchy of types (<tt>src/type/</tt>)
### <tt>src/type/README</tt>.
### Implementing atomic types: singletons.
### Resolving aliased types: <tt>Named</tt> and <tt>actual()</tt>.

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

# 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}): [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/intermediate.pdf intermediate.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/intermediate-handout.pdf intermediate-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/intermediate-handout-4.pdf 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): [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/intermediate.pdf intermediate.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/intermediate-handout.pdf intermediate-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/intermediate-handout-4.pdf intermediate-handout-4.pdf].
* Canonization (Linearization). See the lecture notes (section 4.2, up to slide 100): [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/intermediate.pdf intermediate.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/intermediate-handout.pdf intermediate-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/intermediate-handout-4.pdf 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): [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/intermediate.pdf intermediate.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/intermediate-handout.pdf intermediate-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/intermediate-handout-4.pdf intermediate-handout-4.pdf].
* Microprocessors, Instruction Selection. See the lecture notes: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/instr-selection.pdf instr-selection.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/instr-selection-handout.pdf instr-selection-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/instr-selection-handout-4.pdf 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: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/liveness.pdf liveness.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/liveness-handout.pdf liveness-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/liveness-handout-4.pdf 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: [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/regalloc.pdf regalloc.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/regalloc-handout.pdf regalloc-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/regalloc-handout-4.pdf 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:
** [http://llvm.org/devmtg/2012-11/Gregor-Modules.pdf Modules] (e.g. a module system for the C language family), by Douglas Gregor (Apple) at the [http://llvm.org/devmtg/2012-11/ 2012 LLVM Developers' Meeting].
** [https://github.com/boostcon/cppnow_presentations_2013/blob/master/thu/concepts-lite.pdf?raw=true Concepts Lite: Constraining Template Arguments with Predicates], by Andrew Sutton, Bjarne Stroustrup and Gabriel Dos Reis (Texas A&M University) at [http://cppnow.org/ C++Now 2013].


== TYLA ==

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

# History of Computing.  See the lecture notes, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/history.pdf history.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/history-handout.pdf history-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/history-handout-4.pdf history-handout-4.pdf].
# History of Programming Languages: FOTRAN, Algol (section 1.1 and 1.2).  See the lecture notes, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/early-languages.pdf early-languages.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/early-languages-handout.pdf early-languages-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/early-languages-handout-4.pdf 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, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/early-languages.pdf early-languages.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/early-languages-handout.pdf early-languages-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/early-languages-handout-4.pdf early-languages-handout-4.pdf].
* Object-Oriented History: Simula, Smalltalk-72, Smalltalk-76. See the lecture notes, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/object.pdf object.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/object-handout.pdf object-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/object-handout-4.pdf 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, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/object.pdf object.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/object-handout.pdf object-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/object-handout-4.pdf object-handout-4.pdf].
* Subprograms (sections 1 and 2). See the lecture notes, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/subprograms.pdf subprograms.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/subprograms-handout.pdf subprograms-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/subprograms-handout-4.pdf 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, [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/slides/tyla/subprograms.pdf subprograms.pdf], [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts/tyla/subprograms-handout.pdf subprograms-handout.pdf] and [https://www.lrde.epita.fr/~akim/ccmp/lecture-notes/handouts-4/tyla/subprograms-handout-4.pdf 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.
*** <tt>loop.hs</tt> (lazy evaluation, terminates)
*** <tt>loop.ml</tt> (strict evaluation, does not terminate)
*** <tt>loop-lazy.ml</tt> (local/partial lazy evaluation, terminates)

<tt>loop.hs</tt>:
<pre>
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)
</pre>

<tt>loop.ml</tt>:
<pre>
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)
;;
</pre>

<tt>loop-lazy.ml</tt>:
<pre>
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))
;;
</pre>

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

# 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 &#8866; ("tee" or "turnstile") is the symbol meaning "yields" or "proves"): <math>\frac{\Gamma\vdash\alpha:Int \quad \Gamma\vdash\alpha:Int}{\Gamma\vdash\alpha+\beta:Int} </math>
## Examples of type rules: addition of 2 integers, if-then-else, if-then, addition of 3 integers, comparison of two variables, etc.
## Type inference
### <tt>(''a'' ? ''b'' : ''c'') > 0</tt>
### <tt>(''a'' ? ''b'' : ''f''(''b'')) > 0</tt>
### <tt>(''a'' ? ''b'' : ''f''(''c'')) > 0</tt>
# Generic Programming (sections 1, 2 and 3). See the lecture notes, [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/tyla/generic.pdf generic.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/tyla/generic-handout.pdf generic-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/tyla/generic-handout-4.pdf generic-handout-4.pdf].
# Genericity in Haskell.  See the lecture notes (in section 2.3): [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/ccmp/intermediate.pdf intermediate.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/ccmp/intermediate-handout.pdf intermediate-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/ccmp/intermediate-handout-4.pdf 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 ===

# Generic Programming (sections 4). See the lecture notes, [http://www.lrde.epita.fr/~tiger/lecture-notes/slides/tyla/generic.pdf generic.pdf], [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts/tyla/generic-handout.pdf generic-handout.pdf] and [http://www.lrde.epita.fr/~tiger/lecture-notes/handouts-4/tyla/generic-handout-4.pdf generic-handout-4.pdf].
# More on GP, concepts and links between GP and OOP.
## OOP vs OOP
### OOP: two levels: Interfaces and classes (compile time), instances (run time).
### GP: three levels: Concepts (documentation/design time), models/types (compile time) and instances (run time).
### Single algorithm "instantiation"/compilation (OOP) vs several (GP).
#### 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).
#### No or little compile-time optimization (OOP, cost of <tt>virtual</tt>) vs opportunities for compile-time optimizations (GP).
### Constraint through interface inheritance (OOP) vs lack of explicit constraint (classic GP) or implicit/explicit concept checking (C++ concept proposal)
## Solutions/proposal to add/express GP constraints in C++:
### Boost Concept Checking Library (BCCL)
### "Concepts" proposals
### "Concepts light" proposal
### By Mixing OOP and GP
#### The Curiously Recurring Template Pattern (CRTP).  Mixing two kinds of relations between a base class (top) and a derived class (bottom), in opposite ways:
##### Inheritance (top-down).
##### Parameter passing (bottom-up).
#### Using abstractions (<tt>Abstraction&lt;T&gt;</tt>) to constrain algorithms.
##### Static knowledge of the exact type of the argument
##### Static conversion to exact type (instead of <tt>dynamic_cast</tt> in traditional OOP)
##### Implementing static dispatch based on abstractions.