This document presents the EPITA version of the Tiger project.  It was last updated May 28, 2003.

Copyright © 2000, 2001, 2002, 2003 Akim Demaille.

     Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover texts and with the no Back-Cover Texts.  A copy of the license is included in the section entitled ``GNU Free Documentation License.''

Nul n'est censé ignorer la loi.

Everything exposed in this document is expected to be known.

Compilation: Projects and Reports
*********************************

This document (split and beautiful (http://www.lrde.epita.fr/~akim/compil/reports/reports.html) or in one simple piece (http://www.lrde.epita.fr/~akim/compil/reports.html)) details the various tasks the ``Compilation'' students must complete.

It was last edited on May 28, 2003, using:

     [file 1.texi not included]
     [file 2.texi not included]

Introduction
************

This document presents the Tiger Project as part of the EPITA scholarship.  It aims at the implementation of a Tiger compiler (see Modern Compiler Implementation) in C++.  This project is quite different from most other EPITA projects, and has aims at several different goals, in different areas:

Several iterations
     This project is about the only one with which you will live for 9 months, with the constant needs to fix errors found in earlier stages. This also means that you have to design a test suite, and maintain it through out the project.  The test suite is an integral part of the project.

English
     English is the language for this project, starting with this very document, written by a French person, for French students. Nevertheless, it is impossible to be a good computer scientist with absolutely no fluency in English.  Any attempt to break the importance of English is wrong.  For instance, do not translate this document nor any other.  Ask support to the Yakas, or to the English team.

     By the past, some oral and written examinations were made in English. It may well be back some day.

Team
     The Tiger Compiler is a long project, running from January to September (and optionally further).  Each four person team is likely to experience nasty ``human problems''.  This is explicitly a part of the project: the team management is a task you have to address.  That may well include exclusion of lazy members.

Compiler
     The project aims at the implementation of a compiler, but this is a minor issue.  The field of compilers is a wonder place where most of computer science is concentrated, that's why this topic is extremely convenient as long term project.  But it is not the major goal, the full list of all these items is.

C++
     C++ is by no means an adequate language to study compilers (C would be even worse).  Languages such as Haskell (http://www.haskell.org), Ocaml (http://caml.inria.fr/index.html), Stratego (http://www.stratego-language.org) are much better suited (actually the latter is even designed to this end).  But, as already said, the primary goal is not to learn how to write a compiler: for an EPITA student, learning C++, Design Patterns, and Object Oriented Design is must more important.

Tarballs
********

There are a few mandatory requirements over the tarballs.

Given Tarballs
==============

The naming scheme for provided tarballs is different from the scheme you must follow (see Delivery).  Our naming scheme looks like 2004-tc-2.0.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-2.0.tar.bz2).  If we update the tarballs, they will be named 2004-tc-2.x.tar.bz2.  But your tarball must be named LOGIN-tc-2.tar.bz2, even if you send a second version of your project.

We also (try to) provide patches from one tarball to another.  For instance 2005-tc-1.0-2.0.diff.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-1.0-2.0.diff.bz2) is the difference from 2005-tc-1.0.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-1.0.tar.bz2) to 2005-tc-2.0.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-2.0.tar.bz2). You are encouraged to read this file as understanding a patch is expected from any Unix programmer.  Just run bzless 2005-tc-1.0-2.0.diff.bz2.

To apply the patch:

 1. go into the top level of your current tarball

 2. remove any file which name might cause confusion afterwards (find . -name '*.orig' -o -name '*.rej' | xargs rm)

 3. run bzcat 2005-tc-1.0-2.0.diff.bz2 | patch -p1

 4. look for all the failures (find . -name '*.rej) and fix them by hand once you understood why the patch did not apply

You might need to repeat the process to jump from a version X to X + 2 via version X + 1.

Given Test Cases
================

We provide a few test cases: you must write your own tests. Writing tests is part of the project.  Do not just copy test cases from other groups, as you will not understand why they were written.

The initial test suite is available for download at tests.tgz (http://www.lrde.epita.fr/~akim/compil/download/tests.tgz).  It contains the following directories:

good
     This programs are correct.

scan
     These programs have lexical errors.

parse
     These programs have syntax errors.

type
     These programs contain type mismatches.

Project Layout
==============

Here is the mandatory layout of the tarball:

AUTHORS
     In the top level of the distribution, there must be a file AUTHORS which contents is as follows:

          Fabrice Bardèche     <bardec_f@epita.fr>
          Jean-Paul Sartre     <sartre_j@epita.fr>
          Jean-Paul Deux       <deux_j@epita.fr>
          Jean-Paul Belmondo   <belmon_j@epita.fr>

     The group leader is the first in the list.  Do not include emails other than those of EPITA.  I repeat: give the 6_1@epita.fr address. Note that the file AUTHORS is automatically distributed, but pay attention to the spelling.

ChangeLog
     Optional.  The list of the changes made in the compiler, with the dates and names of the people who worked on it.  See the Emacs key binding C-x 4 a.

README
     Various free information.

argp/
     The command line parser we use.

src/
     All the sources are in this directory.

tests/
     Your own test suite.  You should make it part of the project, and ship it like the rest of the package.  Actually, it is abnormal not to have a test suite here.

src/tc
     Your compiler.

src/tc.cc
     Main entry, option processing.  Called, the driver.

src/misc/
     Convenient C++ routines.

     misc/contract.hh
          A useful improvement over cassert.

     misc/set.hh
          A wrapper around std::set that introduce convenient operators (operator+ and so forth).

     misc/timer.cc, misc/timer.hh
          A class that makes it possible to have timings of the compilation process, as when using --time-report with gcc, or --report=time with bison.  It is used in the Task machinery, but can be used to provide better timings (e.g., separating the scanner from the parser).

src/tasks/
     A generic scheme to handle the components of our compiler, and their dependencies.

src/symbol/
     Namespace symbol:

     symbol.hh
          The handling of the symbols.

     table.hh
          The handling of generic symbol tables, i.e., it is independent of functions, types and variables.

src/ast/
     Namespace ast.  The abstract syntax.

src/parse/
     Namespace parse: parsetiger.yy, scantiger.ll, libparse.hh which prototypes what tc.cc needs to know about the module parse.

src/type/
     Namespace type.  Type checking.

     libtype.hh
          The interface for the driver.

     types.hh
          The definition of all the types.  You are free to use whatever layout you wish (several files); we have a single types.hh file.

     type-entry.hh
          Definitions of type::TypeEntry, type::VarEntry, and type::FunEntry, used in type::TypeEnv to associate data to types, variables, and functions (obviously).

     type-env.hh
          The types environment, comprising three symbol tables: types, functions, and variables.

src/translate/
     Namespace translate.  Translation to intermediate code translation.  It includes:

     libtranslate.hh
          The interface.

     libtranslate.cc
          The compiled module.

     translation.hh
          Helping routines to perform the translations.  For instance, it contains Exp *simpleVar (const Access &access, const Level &level), Exp *callExp (const temp::Label &label, std::list<Exp *> args) etc. which are routines that produce some Tree::Exp.

     translate-visitor.hh
          Implements the class TranslateVisitor which performs the IR generation thanks to translation.hh.  It must not be polluted with translation details: it is only coordinating the AST traversal with the invocation of translation routines.  For instance, here is the translation of a ast::SimpleVar:

               virtual void visit (const SimpleVar& e)
               {
                 const Access &access = _env.var_access_get (e.name_get ());
                 _exp = simpleVar (access, *_level);
               }

Delivery
========

Each group must provide a tarball, made via make distcheck.  All the information about the delivery per se is given on the Yaka's
Delivery Page (http://etudiant.epita.fr:8000/~yaka/doc/rendus.html).

If bardec_f is the head of your group, the tarball must be bardec_f-tc-N.tar.bz2 where N is the number of the ``release'' (see Package Name and Version).  The following commands must work properly:

     $ bunzip2 -cd bardec_f-tc-N.tar.bz2 | tar xvf -
     $ cd bardec_f-tc-N
     $ export CC=GCC-3.2
     $ export CXX=G++-3.2
     $ ./configure
     $ make
     $ cd src
     $ ./tc /tmp/test.tig
     $ cd ..
     $ make distcheck

where GCC-3.2 and G++-3.2 are the name of the GNU C and C++ Compiler 3.2 executables.

Your tarball must be done via make distcheck (see Making a Tarball). Any tarball which is not built thanks to make distcheck (this is easy to see: they include files we don't want, and don't contain some files we need...) will be penalized with at least ### tarball_not_clean.

Code Sanity
===========

The code you deliver must be clean.  In particular, when some code is provided, and you have to fill in the blanks denoted by FIXME: Some code has been deleted..  Sometimes you will have to write the code from scratch.

In any case, dead code and dead comments must be removed.  You are free to leave comments spotting places where you fixed a FIXME:, but never leave a fixed FIXME: in your code.  Nor any irrelevant comment.

The official compiler for this project, is GNU C++ Compiler, 3.2 or higher.

Evaluation
**********

Some stages are evaluated only by a program, and others are evaluated both by humans, and a program.

Automated Evaluation
====================

Each stage of the compiler will be evaluated by an automatic corrector. As soon as the tarball are delivered, the logs are available on http://www.lrde.epita.fr/~akim/compil, in the directory corresponding to your class and stage. For instance, 2004 students ought to read http://www.lrde.epita.fr/~akim/compil/2004/4/bardec_f-tc-4.log.

We stress that automated evaluation enforces the requirements: you must stick to what is being asked.  For instance, for T3 it is explicitly asked to display something like:

     var /* escaping */ i : int := 2

so if you display any of the following outputs

     var i : int /* escaping */ := 2
     var i /* escaping */ : int := 2
     var /* Escapes */ i : int := 2

be sure to fail all the tests, even if the computation is correct.

If you find some unexpected errors (your project does compile with the reference compiler, some files are missing, your output is slightly incorrect etc.) immediately send a new tarball to yaka@epita.fr with [Tiger] as prefix of the subject. This corresponds to ### patch.

Do not wait for the final marks to be computed, this is extremely irritating, and doomed to failure.  You must understand that (i) you increase our workload, and (ii) anyway this is the wrong approach, the Tiger Compiler is a big project which must be continuously improved.

If, anyway, you send a tarball to fix your problems long after the initial date, you will be flagged as ### super_late, which impact on the mark is quite bad...

During the Examination
======================

When you are defending your projects, here are a few rules to follow:

Don't talk
     Don't talk unless you are asked to: when a person is asked a question, s/he is the only one to answer.  You must not talk to each other either: often, when one cannot answer a question, the question is asked to another member.  It is then obvious why the members of the group shall not talk.

Don't touch the screen
     Don't touch my display!  You have nice fingers, but I don't need their prints on my screen.

Tell the truth
     If there is something the examiner must know (someone did not work on the project at all, some files are coming from another group etc.), say it immediately, for, if we discover that by ourselves, you will be severely sanctioned.

Learn
     It is explicitly stated that you can not have worked on a stage provided this was an agreement with the group.  But it is also explicitly stated that you must have learned what was to be learned from that compiler stage, which includes C++ techniques, Bison and Flex mastering, object oriented concepts, design patterns and so forth.

Complain now!
     If you don't agree with the notation, say it immediately.  Private messages about ``this is unfair: I worked much more than bardec_f but his grade is better than mine'' are thrown away.

Conversely, there is something I wish to make clear: I, Akim, and the other examiners, will probably be harsh (maybe even very harsh), but this does not mean I disrespect you, or judge you badly.

You are here to defend your project and knowledge, I'm here to stress them, to make sure they are right.  Learning to be strong under pressure is part of the exercise.  Don't burst into tears, react!  Don't be shy, that's not the proper time: you are selling me something, and I will never buy something from someone who cries when I'm criticizing his product.

You should also understand that human examination is the moment where we try to evaluate who, or what group, needs help.  We are here to diagnose your project and provide solutions to your problems.  If you know there is a problem in your project, but you failed to fix it, tell it to the examiner!  Work with her/him to fix your project.

Human Evaluation
================

The point of this evaluation is to measure:

the quality of the code
     How clean it is, amount of code duplication, bad hacks, standards violations (e.g., stderr is forbidden in proper C++ code) and so forth.  It also aims at detecting cheaters, who will be severely punished (mark = -42).

the knowledge each member acquired
     While we do not require that each member worked on a stage, we do require that each member (i) knows how the stage works and (ii) has perfectly understood the (C++, Bison etc.) techniques needed to implement the stage.

In results in an evaluation file (LOGIN-tc-STAGE.eval, e.g., bardec_f-tc-2.eval), structured as follows.

The format is free, except some lines starting with specific markers, when they are at the first column.  The first marker is *, used to denote the login of the group head:

     * bardec_f
     ----------------------------------------
     2002-03-07: T2 par akim
     tc-check: Summary:
     tc-check: == Testing ./tc --parse-trace -l --ast-display ==
     Successes: 177/177

     Suppléments:
     - --stdin pour parser stdin.
     - Le parser fait attention à ses leaks, même sur les Symbol.
     - --gcc-ast
     - ChangeLog
     - Ne meurt pas quand on lui donne un répertoire en entrée.

     Le code est joli, et en 80 col !
     Plutôt que des listes vides, passent 0.

As you can see, the person who evaluated is allowed to put whatever comment comes to her mind.  Specific features, specific failures, explanations to help the students to fix their project should be included.  Each time an entry is made, there should be the date, and who wrote it (2002-03-07: T2 par akim).

Then, the mark of the project, aka, the note of the group:

     ### Note T2 = 20

and optionally:

### late
     The code was delivered reasonably late (the same day).

### super_late
     More than one day.

### patch
     Within 24 hours from the first delivery date, the group submitted another (hopefully) fixed tarball.

### super_patch
     Before the second delivery date, the group submitted another tarball.

### not_compile
     It doesn't compile, and the examiner had to change the code.

### tarball_not_clean
     Clear enough: bad name, bad content etc.

### cheater
     The group has cheated.  The examiner is then asked to write as many details as possible, and to flag the group as cheaters.  The mark is likely to be negative, and exclusion from EPITA is possible.

### reevaluation
     The group had a mark < 8, and is now being reexamined.

### bonus
     The group has implemented additional features, such as XML output etc. and the project works properly.  We do not care about extra features on top of a broken project.

     Important note to the examiners: Note field.

     The examiner should not take (too much) the automated tests into account to decide the mark.  This is because the mark is computed later, taking this into account, so don't do it twice.  Similarly, a very nice project, which is super late, shall be flagged as super late, but should have a good ## Note entry.

     Important note to the examiners: broken tarballs.

     If you fixed the tarball (### not_compile, or ### tarball_not_clean or whatever modification, you must run make distcheck again, and replace the tarball they delivered with the new one.  Do not keep the old tarball, do not install it in a special place: just replace the first tarball with it, but say so in the eval file.

     The rationale is simple: only tarballs pass the tests, and every tarball must be able to pass the tests.  If you don't do that, then someone else will have to do it again.

The next bits is the evaluation of each member of the group:

     ----------------------------------------
     ## bardec_f:100:120
     Parser, locations, scanner.  A pratiquement e'crit tout T2.

     ##sartre_j:100:40
     AST, Visitor
     Pourtant ne comprend rien au Visitor.  Se fout de ma gueule.

     ##deux_j:80:80
     Pas de problème C++.
     FIXME: Sa note de T1 est à revoir (resoutenance).

     ##belmon_j:100:100
     Actions, les delete dans le parser.
     A implémenté la sortie en AST compatible avec GCC.

The formalism is ## LOGIN:BONUS1:BONUS2.  If the stage is T2, then BONUS1 refers to a bonus on T1, and BONUS2 on T2.  For T4, it covers T3 and T4, and so forth.

The values can be ``negative'' (80, 60, 40, 0), or positive if a member deserves it (100, 120, or even more if justifiable).

There should be information about who did what.

Marks Computation
=================

Because the Tiger Compiler is a project with stages, the computation of the marks depends on the stages too.  To spell it out explicitly:

     A stage is penalized by bad results on tests performed for previous stages.

It means, for instance, that a T3 compiler will be exercised on T1, T2, and T3.  If there are still errors on T1 and T2 tests, they will pessimize the result of T3 tests.  The older the errors are, the more expensive they are.

As an example, here are the formulas to compute the global success rate of T3 and T5:

     global-rate-T3 := rate-T3 * (+ 2 * rate-T1
     			     + 1 * rate-T2) / 3
     global-rate-T5 := rate-T5 * (+ 4 * rate-T1
     			     + 3 * rate-T2
     			     + 2 * rate-T3
     			     + 1 * rate-T4) / 10

Because a project which fail half of the time is not a project that deserves half of 20, the global-rate is elevated to 1.7 before computing the mark:

     mark-T3 := roundup (power (global-rate-T3, 1.7) * 20 - malus-T3, 1)

where roundup (X, 1) is X rounded up to one decimal (roundup (15, 1) = 15, roundup (15.01, 1) = 15.1).

When the project is also evaluated by a human, power is not used.  Rather, the success rate modifies the mark given by the examiner:

     mark-T2 := roundup (eval-T2 * global-rate-T2 - malus-T2, 1)

Reevaluation
============

It happens that some groups have big problems with their project.  Here is how to solve these issues.

But first of all, you must know that cheating, stealing another group's project, is not a solution, because:

  * you won't learn.  Do not forget that the Tiger Compiler is only an exercise: having a good grade is less important than understanding and being efficient when you will be hired by a company.

  * we will certainly notice you are not able to answer our questions.

  * when we find cheaters, they pay it very severely (### cheater).

Because the Tiger Compiler is a long project, you continuously have to improve it, but marks starting from 8 to higher are definitive. If your mark is less than 8, can be re-examined: you must provide a better tarball, and in the case of human evaluated stages, another audition will be made.

This new audition will be flagged as ### reevaluation.  It cannot be better than 12/20, even if your project is excellent: a good project out of date cannot be judged better than a reasonable good project on time.

Pay attention that when providing an updated tarball for reexamination of stage N, it must follow the naming scheme of stage N, even if the contents goes further.  For instance, it is perfectly valid to ask for a T2 reevaluation with a compiler that implements T4, but the tarball must be bardec_f-tc-2.tar.bz2.

You have to ask for a reevaluation, we will not look after you.

Compiler Stages
***************

The compiler will be written in several steps, described below.

T0, Naive Scanner and Parser
============================

This section has been updated for EPITA-2005.

T0 is a weak form of T1: the scanner and the parser are written, but there is a set of simplifications:

the hierarchy
     We don't need several directories, you can program in the top level of the package.

the build
     The GNU Build System is not used: there is no need for Autoconf, Automake etc.

no driver
     The driver is reduced to its simplest form:

          int
          main (int argc, const char *argc[])
          {
            assert (argc == 1);
            yyin = fopen (argv[1]);
            assert (yyin);
            return !!yyparse ();
          }

     i.e., there is no support for options at all.

SCAN, PARSE
     There is no support for options, but that does not mean that you cannot use the tracing/debugging features from Flex/Bison.  It is required that you bind tracing to the environment variables SCAN and PARSE.  I.e., running

          PARSE=1 ./tc foo.tig

     will set yydebug to 1, which causes the traces of the parsing to be displayed.

YYPRINT
     There is no requirement to implement YYPRINT support.

yylval
     All the values are supported: strings, integers and even symbols. Nevertheless, symbols are returned as plain strings for the time being: the class symbol::Symbol is to be implemented in T1.

T0 Code to Write
----------------

You must write

scantiger.ll
     The scanner.

parsetiger.yy
     The parser, and maybe main if you wish.

tc.cc (optionally)
     The driver, i.e., main.  Putting it into parsetiger.yy is OK in T0.

Makefile
     This file is mandatory.  Running make must build the binary tc.

The requirements on the tarball are the same as usual, see Tarballs.

T1, Scanner and Parser
======================

T1 delivery is Friday, February 14th 2003 at noon.

This section is updated for EPITA-2005.

Scanner and parser are properly running, but the abstract syntax tree is not built yet.  Differences with T0 include:

GNU Build System
     Autoconf, Automake are used.

Options, Tasks
     The compiler supports basic options via in the Task module.

locations
     The locations are computed are properly reported in the error messages

T1 Samples
----------

The only information the compiler will give is about lexical and syntax errors.

If there are no errors, the compiler shuts up, and exits successfully:

     /* an array type and an array variable */
     let
       type  arrtype = array of int
       var arr1 : arrtype := arrtype [10] of 0
     in
       arr1[2]
     end
     File 3: test01.tig

     [file 4.texi not included]

If there are lexical errors, the exit status is 2, and a an error message is output on the standard error output.  Note that its format is standard: file, (precise) location, and then the message.

     1
      /* This comments starts at /* 2.2 */
     File 5: unterminated-comment.tig

     [file 6.texi not included]

If there are syntax errors, the exit status is set to 3:

     let var a : nil := ()
     in
       1
     end
     File 7: type-nil.tig

     [file 8.texi not included]

If there are errors which are non lexical, nor syntactic (Windows will not pass by me):

     [file 9.texi not included]

The option --parse-trace, which relies on Bison's %debug directive, and the use of YYPRINT, must work properly:

     $ cat foo.tig
     a + "a"
     $ ./tc --parse-trace foo.tig
     Starting parse
     Entering state 0
     Reading a token: Next token is 258 (ID a)
     Shifting token 258 (ID), Entering state 2
     Reading a token: Next token is 270 (PLUS)
     Reducing via rule 74 (line 318), ID  -> varid
     state stack now 0
     Entering state 16
     Reducing via rule 34 (line 196), varid  -> lvalue
     state stack now 0
     Entering state 13
     Next token is 270 (PLUS)
     Reducing via rule 33 (line 192), lvalue  -> exp
     state stack now 0
     Entering state 12
     Next token is 270 (PLUS)
     Shifting token 270 (PLUS), Entering state 30
     Reading a token: Next token is 257 (STRING a)
     Shifting token 257 (STRING), Entering state 1
     Reducing via rule 15 (line 151), STRING  -> exp
     state stack now 0 12 30
     Entering state 65
     Reading a token: Now at end of input.
     Reducing via rule 27 (line 182), exp PLUS exp  -> exp
     state stack now 0
     Entering state 12
     Now at end of input.
     Reducing via rule 1 (line 106), exp  -> program
     state stack now 0
     Entering state 159
     Now at end of input.
     Shifting token 0 ($), Entering state 160
     Now at end of input.
     $ echo $?
     =>0

Note that (i), it cannot see that the variable is not declared nor that there is a type checking error, since type checking... is not implemented, and (ii), the output might be slightly different, depending upon the version of Bison you use.  But what matters is that one can see the items: ID a, STRING a.

T1 Given Code
-------------

Some code is provided: 2005-tc-1.0.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-1.0.tar.bz2).  It contains:

src/common.hh
     Used throughout the project.

src/tc.cc
     The compiler driver (option handling etc.).

src/parse/scantiger.ll
     The scanner.

src/parse/parsetiger.yy
     The parser.

src/ast/position.hh
     Keeping track of a point (cursor) in a file.

src/ast/location.hh
     Keeping track of a range (two cursors) in a (or two) file.

T1 Code to Write
----------------

Be sure to read Flex and Bison documentations and tutorials, see Flex & Bison.

src/scantiger.ll
     The scanner must be completed.  It must be able to read strings, identifiers etc.  Strings and identifiers will be stored as C++ std::string.  See the following code for the basics.

          ...
          \"          yylval->str = new std::string (); BEGIN STATE_STRING;

          <STATE_STRING>{ /* Handling of the strings.  Initial " is eaten. */
               \" {
                 BEGIN INITIAL;
                 return STRING;
               }
          ...
               \\x[0-9a-fA-F]{2}  {
                 yylval->str->append (1, strtol (yytext + 2, 0, 16));
               }
          ...
          }

     The locations are tracked.

src/parsetiger.yy
     The grammar must be complete, but do not implement actions.  You have to implement support for --parse-trace (see T1 Samples).  Pay special attention to the display of strings and identifiers.

     Bison will certainly complain because of a type clash for some actions. For instance, if you have given a type to STRING, but none to exp, then it will choke on:

          exp: STRING;

     because it actually means

          exp: STRING { $$ = $1; };

     which is not type coherent.  So write this instead:

          exp: STRING {};

src/ast/position.hh
     The class ast::Position is completed.

src/ast/location.hh
     The class ast::Location must be completed.

src/symbol/symbol.hxx
     The class symbol::Symbol keeps a single copy of identifiers, so that (i) we save space, and (ii) symbol comparison is fast.  The file src/symbol/symbol.hh describes the interface of the class symbol::Symbol, but the implementation is to be written in src/symbol/symbol.hxx.

T1 FAQ
------

Options
     The first version of argp we used (1.1) was buggy: on ./tc foo.tig -A, it considered -A was a file, not an option.  This bug is now fixed.  The patch is from Niels Möller:

          diff -u -r1.16 -r1.17
          --- argp-parse.c        18 Feb 2001 22:40:03 -0000      1.16
          +++ argp-parse.c        4 Feb 2003 19:52:30 -0000       1.17
          @ -1021,6 +1021,8 @
          	  *arg_ebadkey = 1;
          	  if (parser->first_nonopt != parser->last_nonopt)
          	    {
          +             exchange(parser);
          +
          	      /* Start processing the arguments we skipped previously. */
          	      parser->state.next = parser->first_nonopt;

     Go into argp/, run patch -p0, paste the patch, type CTRL-d.

T2, Building the Abstract Syntax Tree
=====================================

This section was last updated for EPITA-2005 on 2003-02-25.

2005-T2 delivery is Friday, March 14th 2003 at noon.

At the end of this stage, the compiler can build abstract syntax trees of Tiger programs and pretty-print them.  The parser is equipped with error recovery.

T2 Samples
----------

Here are a few examples of expected features.

The parser builds abstract syntax trees that can be output by a pretty-printing module:

     /* define a recursive function */
     let
       /* calculate n! */
       function fact (n : int) : int =
         if  n = 0
           then 1
           else n * fact (n - 1)
     in
       fact (10)
     end
     File 10: simple-fact.tig

     [file 11.texi not included]

The output from your pretty-printer must be valid Tiger code, and be equivalent to the input.

By valid, we mean that any Tiger compiler must be able to parse with success your output.  Pay attention to the banners such as == Abstract...: you should use comments: /* == Abstract... */.  Pay attention to special characters too.

     print ("\"\x45\x50ITA\n\"")
     File 12: string-escapes.tig

     [file 13.texi not included]

By equivalent, we mean that except for syntactic sugar, the output and the input are equal.   Syntactic sugar refers to &, |, unary -, and in some cases if then:

     1 = 1 & 2 = 2
     File 14: 1s-and-2s.tig

     [file 15.texi not included]
     [file 16.texi not included]
     [file 17.texi not included]

For loops must be properly displayed, i.e., although we use a ast::VarDec for the index of the loop, you must not display var:

     /* valid let and for */
     let
     	var a := 0
     in
     	for i :=0 to 100 do (a :=a+1; ())
     end
     File 18: for-loop.tig

     [file 19.texi not included]

Notice too that parentheses must not stack for free.  In fact, you must even remove them.

     % cat parens.tig
     (((0)))
     % ./tc -A parens.tig
     /* == Abstract Syntax Tree. == */
     0

As a result, anything output by tc -A is equal to what tc -A | tc -A - displays!

Another part of T2 is the improvement of your parser: it must be robust to some forms of errors.  Observe that on the following input:

     (
       1;
       (2, 3);
       (4, 5);
       6
     )
     File 20: multiple-parse-errors.tig

several parse errors are reported, not merely the first one:
     [file 21.texi not included]

Of course, the exit status still reveals the parse error.  Be sure that your error recovery does not break the rest of the compiler...

     [file 22.texi not included]

T2 Given Code
-------------

Some code is provided: 2004-tc-2.0.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-2.0.tar.bz2).  It contains:

escape.hh
     This file implements a means to output string while escaping non printable characters.  An example:

            cout << "escape (\"\111\") = " << escape ("\"\111\"") << endl;

     Understanding how escape works is required.

src/ast
     Implementation of the abstract syntax tree.  The file README gives an overview of the involved class hierarchy.

src/ast/location.hh, src/ast/position.hh
     These files are now simply forwarding the definitions of yy::Position and yy::Location as provided by Bison.

src/ast/visitor.hh
     Abstract base class of the compiler's visitor hierarchy.  Actually, it defines a class template GenVisitor, which expects an argument which can be either non_const_kind or const_kind.  This allows to define to parallel hierarchies: ConstVisitor and Visitor, similar to iterator and const_iterator.

     The understanding of the template programming used is not required at this stage as it is quite delicate, and goes far beyond your (average) current understanding of templates.

src/ast/default-visitor.hh
     Implementation of the DefaultVisitor class, which walks the abstract syntax tree, doing nothing.  It is mainly used as a basis for deriving other visitors.  Actually, just as above, there is a template, so that we have two different default visitors: DefaultVisitor<const_kind> and DefaultVisitor<non_const_kind>.

src/ast/print-visitor.hh
     Implementation of the PrintVisitor class, which performs pretty-printing in the tiger compiler.

src/symbol.*
     Implement this class if you hadn't during T1.  Understanding is required.

T2 Code to Write
----------------

What is to be done:

src/parse/scantiger.ll
     The scanner must now use symbol::Symbol instead of std::string for identifiers.  Of course, the parser must be adjusted too.

     The scanner must be updated to keep track of locations of tokens in Tiger programs.  To adjust your scanner, you are strongly encouraged to use YY_USER_ACTION, and also the yylex prologue:

          ...
          %%
          %{
            // Everything here is run each time yylex is invoked.
          %}
          "if"    return IF;
          ...
          %%
          ...

     Have a look at the scanner and parser chapters of this draft (http://www.lrde.epita.fr/~akim/compil/gnuprog2/).

src/parse/parsetiger.yy
     Implement error recovery.  There should be at least three uses of the token error.  Read the Bison documentation about it.

     The grammar must be changed to process declarations by chunks.  In Tiger, the following program is invalid:

          let function foo () = ()
              function foo () = ()
              var      foo    := 0
          in
            ()
          end

     while the following code is valid:

          let function foo () = ()
              var      foo    := 0
              function foo () = ()
          in
            ()
          end

     this is because declarations are cut in ``chunks'' of declarations of the same kind.  In the first example, there are two chunks: one chunk of two function declarations and one variable declaration.  In the second example: there are three chunks: one chunk containing only one function declaration, one with one variable declaration, and the third one, with a single function declaration again.

     The rule is ``a chunk cannot define twice the same name''.

     In order to implement this easily, you must adjust your grammar so that declarations are parsed by chunks.  Pay special attention to the implementation of ast::FunctionDecs, ast::VarDecs, and ast::TypeDecs (which are all implemented thanks to ast::AnyDecs): they are these chunks of declaration.  Therefore, an ast::LetExp uses a list of chunks.

src/ast
     The abstract syntax tree module must be completed.  Basically, this means there should remain no FIXME: anywhere in the code we gave. Several files are missing (fieldvar.hh nilexp.hh intexp.hh stringexp.hh callexp.hh assignexp.hh whileexp.hh breakexp.hh arrayexp.hh).  See src/ast/README for additional information on the missing classes.

src/ast/default-visitor.hh
     The DefaultVisitor class must be completed, and must be able to walk whole abstract syntax trees.  Do not forget that your DefaultVisitor must be a sound basis for your further work on the Tiger compiler.

src/ast/print-visitor.hh
     The PrintVisitor class must be written entirely.

T2 FAQ
------

bison
     Be sure to read its dedicated section: Flex & Bison.

escapes (escapes_get, etc.)
     These are place holders for T3.  You don't have to complete them. Actually, the easiest is probably just to comment these functions out. Or better yet: #if 0/#endif.

kinds (kind_get, etc.)
     Some of the ast components have features such as _kind, kind_get and so forth.  These are to be used only in T5, you don't have to complete them now.

T3, Computing the Escaping Variables
====================================

This section was updated for Tiger 2004.  The project will be taken on Friday, March 15th, at noon.

At the end of this stage, the compiler must be able to compute and display the escaping variables.  These features are triggered by the options --escapes-compute/-e and --escapes-display/-E.

Be sure to read the chapter ``Escapes'' in the lecture notes.

T3 Samples
----------

This example demonstrates the computation and display of escaping variables/formals.  Notice that by default, all variable must be considered as escaping, since it is safe to put a non escaping variable onto the stack, while the converse is unsafe.

     let
        var escaping := "I rule the world!"
        var not_escaping := "Peace on Earth for humans of good will."
        function print_escaping () =
           print (escaping)
     in
        (not_escaping; print_escaping ())
     end
     File 23: variable-escapes.tig

     [file 24.texi not included]

You are strongly encouraged to run your compiler on merge.tig and to study its output.  There is a number of silly mistakes that people usually do on T3: they are all easy to defeat when you do have a reasonable test suite, and once you understood that torturing your project is a good thing to do.

T3 Code To Write
----------------

ast::PrintVisitor
     Be sure to display the /* escaping */ flag where needed, and only where needed.  If you don't pay attention, you might display meaningless flags due to implementation details.

escapes::EscapesVisitor
     Write the class escapes::EscapesVisitor in src/escapes/escapes-visitor.hh.

     You are suggested to implement three additional classes:

     Definition
          An abstract class which is used to instantiate the template class symbol::Table into Table <Definition>.

           -- virtual void: escape_set (void)
               Sets the escape to true.

           -- Variable: int _depth
               Depth at which this object has been created.

           -- int: depth_get () const
               Returns the depth associated to this Definition object.

     VariableDefinition
          Inherits from Definition.  It has one additional attribute, a VarDec &.  The method escape_set is implemented, and when invoked, set the escapes flags of the corresponding VarDec.

     FormalDefinition
          Inherits from Definition.  To be designed by yourself.  Do not forget that the ast class used to register formals is used elsewhere, and it would be a pity that your implementation makes no difference...  Be sure to write a test that verifies that your implementation is not abused.  I have one such test...

Equip ast
     All the sites where variables and formals (i.e., the arguments of the functions being defined, not being used) are introduced must be equipped with the escape_get and escape_set methods.  Most probably the code was already given, and is using const_casts; try to use mutable instead.

     Modify the code so that each definition of an escaping variable/formal is preceded by the comment /* escaping */ if the flag display_escapes_p is true.  See the item ``Driver'' for an example.

T3 FAQ
------

Dwarf errors
     It appears that at EPITA, the linker is unable to read the output of G++ 3.2 when given -ggdb.  So don't pass it.

T4, Type Checking
=================

This section was last updated for EPITA-2005 on 2003-04-08.

2005-T4 delivery is Friday, April 25th 2003 at noon.

At the end of this stage, the compiler type checks Tiger programs. Clear error messages are required.

T4 Samples
----------

Type checking is optional, invoked by --types-check or -T:

     1 + "2"
     File 25: int-plus-string.tig

     [file 26.texi not included]
     [file 27.texi not included]

When there are several type errors, it is admitted that some remain hidden by others.

     unknown_function (unknown_variable)
     File 28: unknowns.tig

     [file 29.texi not included]

Be sure to check the type of all the constructs.

     if 1 then 2
     File 30: bad-if.tig

     [file 31.texi not included]

Be aware that type and function declarations are recursive by chunks. For instance:

     let type one = { hd : int, tail : two }
         type two = { hd : int, tail : one }
         function one (hd : int, tail : two) : one
            = one { hd = hd, tail = tail }
         function two (hd : int, tail : one) : two
            = two { hd = hd, tail = tail }
         var one := one (11, two (22, nil))
     in
       print_int (one.tail.hd); print ("\n")
     end
     File 32: mutuals.tig

     [file 33.texi not included]

In case you are interested, the result is:

     [file 34.texi not included]
     [file 35.texi not included]

T4 Given Code
-------------

Some code is provided: 2005-tc-4.3.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-4.3.tar.bz2).  The transition from the previous versions can be done thanks to the following diffs: 2005-tc-2.1-4.0.diff (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-2.1-4.0.diff), 2005-tc-4.0-4.1.diff (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-4.0-4.1.diff), 2005-tc-4.1-4.2.diff (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-4.1-4.2.diff), 2005-tc-4.2-4.3.diff (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-4.2-4.3.diff).  It includes the following code:

src/type/libtype.hh
src/type/libtype.cc
     The interface of the Type module.  It exports a single procedure, type_check.

src/type/types.hh
     The definition of all the types.  The type type::Nil is given in full.

src/type/type-env.hh
     The environment used by the type::TypeVisitor.

T4 Code to Write
----------------

What is to be done.

symbol::Table< class Entry_T >
     Write the class template symbol::Table in src/symbol/table.hh which is a table of symbols dedicated to storing some data which type is Entry_T *.  In short, it maps a symbol::Symbol to an Entry_T * (that should ring a bell...).  You are encouraged to implement something simple, based on stacks (see std::stack or std::list) and maps (see std::map).

     symbol::Table is a class template as it is used by virtually all the AST visitors (e.g., escapes::EscapesVisitor, type::TypeVisitor, translate::TranslateVisitor etc.)

     symbol::Table must provide this interface:

      -- void: scope_begin ()
          Open a new scope.

      -- void: scope_end ()
          Close the last scope, forgetting everything since the latest scope_begin ().

      -- void: put (Symbol key, Entry_T & value)
          Associate VALUE to KEY in the current scope.

      -- Entry_T *: get (Symbol key) const
          If KEY was associated to some Entry_T in the open scopes, return the most recent insertion.  Otherwise return the empty pointer.

      -- void: print (std::ostream & ostr) const
          Send the content of this table on OSTR in a readable manner, the top of the stack being displayed last.

src/type/types.hh
     The Singletons type::String, type::Int, and type::Void are to be implemented.  Using templates would be particularly appreciated to factor the code between the four singleton classes.

     type::Named is almost entirely given.

     type::Array is even simpler than the four Singletons.

     type::Record is somewhat incomplete.

     Pay extra attention to the implementation of type::operator== (const Type& a, const Type& b), type::Type::assignable_to and type::Type::comparable_to.

src/type/type-entry.hh
     This file is really a empty nutshell, so we give it complete so that you concentrate on things that matter.  Nonetheless you will be asked questions on this file, so study it.

src/type/type-env.hh
     The constructor of type::TypeEnv must be completed: it must fill the environment with the definition of builtin types and functions.  See the Tiger Reference Manual.

     The handling of types is left as an example, you still have to implement the variables and functions support.

type::TypeVisitor
     Of course this is the most tricky part.  I hope there are enough comments in there so that you understand what is to be done.  Please, post your questions and help me improve it.

Tasks
     Each module FOO exports its tasks via the file FOO/FOO-tasks.hh.  You must clean up your code to use the latest sources for Tasks, and make sure that your configure.ac no longer includes FOO/libFOO.hh in src/modules.hh.

T4 Options
----------

These are features that you might want to implement in addition to the core features.

type::Error
     One problem is that type error recovery can generate false errors. For instance our compiler usually considers that the type for incorrect constructs is Int, which can create cascades of errors:

          "666" = if 000 then 333 else "666"
          File 36: is_devil.tig

          [file 37.texi not included]

     One means to avoid this issue consists in introducing a new type, type::Error, that the type checker would never complain about. This can be a nice complement to ast::Error.

T4 FAQ
------

Stupid Types
     One can legitimately wonder whether the following program is correct:

          let type weirdo = array of weirdo
          in
            print ("I'm a creep.\n")
          end

     the answer is "yes", as nothing prevents this in the Tiger specifications.  Note that this type is not usable though.

kinds (kind_get, etc.)
     Some of the ast components have features such as _kind, kind_get and so forth.  These are to be used only in T5, you don't have to complete them now.

The TypeVisitor is not a ConstVisitor
     One of the tasks of the type checking is to pass additional information to the translation.  For instance, since < is overloaded (for integers and strings), the translation needs to know the types of the arguments.  In a traditional compiler, type checking and translation would be performed simultaneously, but our Tiger Compiler, in order to simplify its architecture, has two different passes for each.  Hence, the TypeVisitor will have to leave notes on the AST for the TranslateVisitor, therefore it cannot be a const visitor once T5 implemented.  It can perfectly be const during T4.

T5, Translating to the High Level Intermediate Representation
=============================================================

This section was last updated for EPITA-2005 on 2003-05-15.

2005-T56 delivery is Friday, June 20th, at noon.

At the end of this stage the compiler translates the AST into the high level intermediate representation, HIR for short.  And, of course, all the errors of previous stages have been fixed.

T5 Samples
----------

T5 can be started (and should be started if you don't want to finish it in a hurry) by first making sure your compiler can handle code that uses no variables.  Then, you can complete your compiler to support more and more Tiger features.

T5 Primitive Samples
....................

This example is probably the simplest Tiger program.

     0
     File 38: 0.tig

     [file 39.texi not included]

You should then probably try to make more difficult programs with literals only.  Arithmetics is one of the easiest tasks.

     1 + 2 * 3
     File 40: arith.tig

     [file 41.texi not included]

You should use havm to exercise your output.

     [file 42.texi not included]
     [file 43.texi not included]

Unfortunately, without actually printing something, you won't see the final result, which means you need to implement calls.  Fortunately, you can ask havm for a verbose execution:

     [file 44.texi not included]

If you look carefully, you will find an sxp 7 in there...

Then you are encouraged to implement control structures.

     if 101 then 102 else 103
     File 45: if-101.tig

     [file 46.texi not included]

And even more difficult control structure uses:

     while 101
       do (if 102 then break)
     File 47: while-101.tig

     [file 48.texi not included]

T5 Optimizing Cascading If
..........................

Our compiler optimizes the number of jumps needed to compute nested if, using translate::Ix where a plain use of translate::Cx, Nx, and Ex is possible, but less efficient.

Consider the following sample:

     if 11 | 22 then print ("OK\n")
     File 49: boolean.tig

a naive implementation will probably produce too many successive cjump instructions:

     [file 50.texi not included]
     [file 51.texi not included]
     [file 52.texi not included]

If you carefully analyze the cause of this pessimization, it is related to the computation of an intermediary expression (the value of 11 | 22) which is later decoded as a condition.  A proper implementation will produce:

     [file 53.texi not included]
     [file 54.texi not included]
     [file 55.texi not included]

T5 Builtin Calls Samples
........................

But the game becomes more interesting when you implement function calls (which is easier than compiling functions).  print_int is probably the first builtin to implement:

     (print_int (101); print ("\n"))
     File 56: print-101.tig

     [file 57.texi not included]
     [file 58.texi not included]

Complex values, arrays and records, also need calls to the runtime system:

     let type list = { h: int, t: list }
         var list := list { h = 1, t = list { h = 2, t = nil } }
     in
       print_int (list.t.h); print ("\n")
     end
     File 59: print-list.tig

     [file 60.texi not included]
     [file 61.texi not included]
     [file 62.texi not included]

T5 Samples with Variables
.........................

Here is an example which demonstrates the usefulness of information about escapes: when escaping variables are not computed, they are all stored on the stack:

     let var a := 1
         var b := 2
         var c := 3
     in
       a := 2;
       c := a + b + c;
       print_int (c);
       print ("\n")
     end

     File 63: vars.tig

     [file 64.texi not included]

But once escaping variable computation implemented, we know none escape in this example, hence they can be stored in temporaries:

     [file 65.texi not included]
     [file 66.texi not included]
     [file 67.texi not included]

And finally, you should implement the declaration of functions:

     let function fact (i: int) : int =
         if i = 0 then 1
     	     else i * fact (i - 1)
     in
       print_int (fact (15));
       print ("\n")
     end

     File 68: fact15.tig

     [file 69.texi not included]
     [file 70.texi not included]
     [file 71.texi not included]

T5 Given Code
-------------

Some code is provided, see T6 Given Code.  It includes the following code:

src/temp/temp.hh
     So called temporaries are pseudo-registers: we may allocate as many temporaries as we want.  Eventually the register allocator will map those temporaries to either an actual register, or it will allocate a slot in the activation block (aka frame) of the current function.

src/temp/label.hh
     We need labels for JUMPs, for functions, strings etc.

src/tree
     The implementation of the intermediate representation.  The file README should give enough explanations to understand how it works.

     Reading the corresponding explanations in Appel's book is mandatory.

     It is worth noting that contrary to A. Appel, just as we did for ast, we use n-ary structures.  For instance, where Appel uses a binary SEQ, we have an n-ary SEQ which allows us to put as many statements as we want.

     To avoid gratuitous name clashes, what Appel denotes EXP is denoted SXP (Statement Expression), implemented in translate::Sxp.

     Please, pay extra attention to the fact that there are temp::Temp used to create unique temporaries (similar to symbol::Symbol), and tree::Temp which is the intermediate representation instruction denoting a temporary (hence a tree::Temp needs a temp::Temp).  Similarly, on the one hand, there is temp::Label which is used to create unique labels, and on the other hand there are tree::Label which is the IR statement to define to a label, and tree::Name used to refer to a label (typically, a tree::Jump needs a tree::Name which in turn needs a temp::Label).

src/frame/access.hh, src/frame/access.cc
     An Access is a location of a variable: on the stack, or in a temporary.

src/frame/frame.hh, src/frame/frame.cc
     A Frame knows only what are the ``variables'' it contains.

src/translate/access.hh, src/translate/access.cc
     Static link aware versions of level::Access.

src/translate/level.hh, src/translate/level.cc
     translate::Level are wrappers frame::Frame that support the static links, so that we can find an access to the variables of the ``parent function''.

src/translate/exp.hh
     Implementation of translate::Ex (expressions), Nx (instructions), Cx (conditions), and Ix (if) shells.  They wrap tree::Node to delay their translation until the actual use is known.

src/translate/level-entry.hh
     All the information that the environment must keep about variables and functions.

src/translate/level-env.hh
     The levels environment, containing LevelVarEntry's and LevelFunEntry's.  We don't need to store information related to types here.

src/translate/translation.hh
     This file contains functions used by the translate::TranslateVisitor to translate the AST into IR.  They handle all the unCx etc. magic.

src/translate/translate-visitor.hh
     The translate::TranslateVisitor which walks the AST and builds the IR tree.

T5 Code to Write
----------------

You are encouraged to try first very simple examples: nil, 1 + 2, "foo" < "bar" etc.  Then consider supporting variables, and finally handle the case of the functions.

Driver
     The driver must performs the translation when given --hir-compute, but displays the result iff the option -H was given.  Obviously, an input that has not been type-checked cannot be translated, so --hir-compute implies --types-check.

TypeVisitor
     The TranslateVisitor often needs additional type information to proceed, especially expression versus instruction.  Hence, you'll have to update the TypeVisitor to leave notes on the AST using kind_set and so forth.

src/translate/fragment.hh
     It implements translate::Fragment, an abstract class, translate::DataFrag to store the literal strings, and translate::ProcFrag to store the routines.

     There remains to implement translate::ProcFrag::print which outputs the routine themselves plus the glue code (allocating the frame etc.).

src/translate/level-env.hh
     Code is missing.  In particular, bear in mind that the initial environment is not empty...

src/translate/translation.hh
     There are many holes to fill.

src/translate/translate-visitor.hh
     There are holes to fill.

T5 Options
----------

This section documents possible extensions you could implement in T5.

T5 Bound Checking
.................

Implementing bound checking is quite simple: it consists in having the program die when the program accesses an invalid subscript in an array. For instance, the following code is ``succeeds'' with a non-bound-checking compiler.

     let type int_array = array of int
         var  size  := 2
         var  arr1  := int_array [size] of 0
         var  arr2  := int_array [size] of 0
         var  two   := 2
         var  m_one := -1
     in
       arr1[two]   := 3;
       arr2[m_one] := -1;

       print_int (arr1[1]);
       print ("\n");
       print_int (arr2[0]);
       print ("\n")
     end
     File 72: bound-violation.tig

     [file 73.texi not included]
     [file 74.texi not included]

When run with --bound-checking, have your compiler produce code that dies on such cases.

T5 Optimizing Static Links
..........................

Warning: this optimization is difficult to do it perfectly, and therefore, expect a big bonus.

In a first and conservative extension, the compiler considers that all the functions (but the builtins!) need a static link.  This is correct, but inefficient: for instance, the traditional fact function will spend almost as much time handling the static link, than its real argument.

Some functions need a static link, but don't need to save it on the stack.  For instance, in the following:

     let var foo := 1
         function foo () : int = foo
     in
       foo ()
     end

the function foo does need a static link to access the variable foo, but does not need to store its static link on the stack.

It is suggested to address these problems in the following order:

 1. Implement the detection of functions that do not need a static link (see exercise 6.5 in ``Modern Implementation of Compilers''), but still consider any static link escapes.

 2. Adjust the output of --escapes-display to display /* escaping sl */ before the first formal argument of the functions (declarations) that need the static link:

          $ tc -E fact.tig
          /* == Escapes. == */
          let
             function fact (/* escaping sl *//* escaping */ n : int) : int =
                if  (n = 0)
          	 then 1
          	 else  (n * fact ( (n - 1)))
          in
             fact (10)
          end

          $ tc -eE fact.tig
          /* == Escapes. == */
          let
             function fact (n : int) : int =
                if  (n = 0)
          	 then 1
          	 else  (n * fact ( (n - 1)))
          in
             fact (10)
          end

 3. Adjust your call and progFrag prologues.

 4. Improve your computation so that non escaping static links are detected:

          $ tc -eE escaping-sl.tig
          /* == Escapes. == */
          let
             var      toto := 1
             function outer (/* escaping sl */) : int =
               let function inner (/* sl */) : int = toto
               in inner () end
          in
            outer ()
          end

     Watch out, it is not trivial to find the minimum.  What do you think about the static link of the function sister below?

          let
             var      toto := 1
             function outer () : int =
               let function inner () : int = toto
               in inner () end
             function sister () : int = outer ()
          in
            sister ()
          end

T6, Translating to the Low Level Intermediate Representation
============================================================

This section was last updated for EPITA-2005 on 2003-05-15.

2005-T56 delivery is Friday, June 20th, at noon.

There will be no additional code: there is no ``holes'' to fill, you have to write the whole thing.  Consequently, you may start T6 as soon as you want.

At the end of this stage, the compiler produces low level intermediate representation: LIR.  LIR is a subset of the HIR: some patterns are forbidden.  This is why it is also named canonicalization.

T6 Samples
----------

There are several stages in T6.

T6 Canonicalization Samples
...........................

The first task in T6 is getting rid of all the eseq.  To do this, you have to move the statement part of an eseq at the end of the current sequence point, and keeping the expression part in place.

Compare for instance the HIR to the LIR in the following case:

     let function print_ints (a: int, b: int) =
         (print_int (a); print (", "); print_int (b); print ("\n"))
         var a := 0
     in
       print_ints (1,  (a := a + 1; a))
     end
     File 75: preincr-1.tig

One possible HIR translation is:

     [file 76.texi not included]

A possible canonicalization is then:

     [file 77.texi not included]

But please note the example above is simple because 1 commutes with (a := a + 1; a): the order does not matter. But if you change the 1 into a, then you cannot exchange a and (a := a + 1; a), so the translation is different. Compare the previous LIR with the following, and pay attention to

     let function print_ints (a: int, b: int) =
         (print_int (a); print (", "); print_int (b); print ("\n"))
         var a := 0
     in
       print_ints (a,  (a := a + 1; a))
     end
     File 78: preincr-2.tig

     [file 79.texi not included]

As you can see, the output is the same for the HIR and the LIR:

     [file 80.texi not included]
     [file 81.texi not included]

     [file 82.texi not included]
     [file 83.texi not included]

Be very careful when dealing with mem.  For instance, rewriting something like:

     call (foo, eseq (move (temp t, const 51), temp t))

into

     move temp t1, temp t
     move temp t, const 51
     call (foo, temp t)

is dead wrong: temp t is a subexpression: it is being defined here.  You should produce:

     move temp t, const 51
     call (foo, temp t)

Another danger is the handling of move (mem, ).  For instance:

     move (mem FOO, x)

must be rewritten into:

     move (temp t, FOO)
     move (mem (temp t), x)

not as:

     move (temp t, mem (FOO))
     move (temp t, x)

In other words, the first subexpression of move (mem (foo), ) is foo, not mem (foo).  The following example is a good crash test against this problem:

     let type int_array = array of int
         var tab := int_array [2] of 51
     in
       tab[0] := 100;
       tab[1] := 200;
       print_int (tab[0]); print ("\n");
       print_int (tab[1]); print ("\n")
     end
     File 84: move-mem.tig

     [file 85.texi not included]
     [file 86.texi not included]

You also ought to get rid of nested calls:

     print (chr (ord ("\n")))
     File 87: nested-calls.tig

     [file 88.texi not included]

In fact there are only two valid call forms: sxp (call (...)), and move (temp (...), call (...)).

Note that, contrary to C, the HIR and LIR always denote the same value.  For instance the following Tiger code:

     let var a := 1
         function a (t: int) : int =
            (a := a + 1;
     	print_int (t); print (" -> "); print_int (a); print ("\n");
     	a)
         var b := a (1) + a (2) * a (3)
     in
       print_int (b); print ("\n")
     end

should always produce:

     1 -> 2
     2 -> 3
     3 -> 4
     14

independently of the what IR you ran.  Note that it has nothing to do with the precedence of the operators!

In C, you have no such guarantee:

     #include <stdio.h>

     int _a = 1;
     int a (int t)
     {
       ++_a;
       printf ("%d -> %d\n", t, _a);
       return _a;
     }

     int main (void)
     {
       int b = a (1) + a (2) * a (3);
       printf ("%d\n", b);
       return 0;
     }

will always give the same result on all compilers and architectures.

T6 Scheduling Samples
.....................

Once you have canonicalized your eseq and call, you have to canonicalize cjumps: they must always be followed by their ``false'' label.  This goes in two steps:

 1. Split in basic blocks.

     A basic block is a sequence of code starting with a label, ending with a jump (conditional or not), and with no jumps, no labels inside.

 2. Build the traces.

     Now put all the basic blocks into a single sequence.

In the following, the result of the whole conversion is visible.

The following examples highlights the need for new labels: at least one for the entry point, and one for the exit point:

     1 & 2
     File 89: 1-and-2.tig

     [file 90.texi not included]

The following example contains many jumps.  Compare the hir to the lir:

     while 10 | 20 do if 30 | 40 then break else break
     File 91: broken-while.tig

     [file 92.texi not included]
     [file 93.texi not included]

T6 Given Code
-------------

Some code is provided: : 2005-tc-6.1.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-6.1.tar.bz2).  The transition from the previous versions can be done thanks to the following diffs: 2005-tc-4.3-6.0.diff (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-4.3-6.0.diff), 2005-tc-6.0-6.1.diff (http://www.lrde.epita.fr/~akim/compil/download/2005-tc-6.0-6.1.diff).

It includes most of the canonicalization.

T6 Code to Write
----------------

Everything you need.

T7, Instruction Selection
=========================

This section was last updated for EPITA-2004 on 2003-05-21.

At the end of this stage, the compiler produces the very low level intermediate representation: ASSEM.  This output is target dependent, and we aim at MIPS, as we use SPIM to run it.

T7 Samples
----------

The goal of T7 is straightforward: starting from LIR, generate the MIPS instructions, except that you don't have actual registers: we still heavily use Temps.  Register allocation will be done in a later stage, T9.

     1 + 2 * 3
     File 94: seven.tig

     [file 95.texi not included]

Please, note that at this stage, the control flow analysis and the liveness analysis are not performed yet, therefore the compiler cannot know what registers are really to be saved.  That's why in the previous output it saves "uselessly" all the callee-save registers on main entry.  The next stage, which combines control flow analysis, liveness analysis, and register allocation, will make it useless.  For your information, it results in:

     [file 96.texi not included]

A delicate part of this exercise is handling the function calls:

     let function add (x: int, y: int) : int = x + y
     in
       print_int (add (1, (add (2, 3)))); print ("\n")
     end
     File 97: add.tig

     [file 98.texi not included]

T7 Given Code
-------------

A lot of code is provided.  Actually, that's a real problem: since last year, the Tiger compiler has evolved a lot, and the integration of the new features will probably be painful.  The most striking difference with last year being the Task handling.

The additional code is provided in two different forms:

  - 2004-tc-7.5.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.5.tar.bz2), the whole tarball.

  - 2004-tc-5.3-7.0.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-5.3-7.0.diff), 2004-tc-5.3-7.3.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-5.3-7.3.diff), 2004-tc-5.3-7.4.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-5.3-7.4.diff), 2004-tc-5.3-7.5.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-5.3-7.5.diff), the differences with the latest tarball that was delivered.

  - 2004-tc-7.0-7.1.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.0-7.1.diff), 2004-tc-7.1-7.2.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.1-7.2.diff), 2004-tc-7.2-7.3.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.2-7.3.diff), 2004-tc-7.3-7.4.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.3-7.4.diff), 2004-tc-7.4-7.5.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.4-7.5.diff), the differences with previous versions of the 2004-tc-7 tarball.

There are two ways to continue the projects:

minor upgrade
     If you do not want to upgrade your 2004 compiler into the 2005 form, just copy the relevant files from the tarball.  See below.  Adjust your driver so that --inst-compute and --inst-display be recognized.  Of course, --inst-compute implies --lir-compute.

major upgrade
     You want to upgrade to the 2005 system.  Expect massive surgery... Contrary to the previous case, I would recommend starting from the tarball we delivered, and copy your files into there.  For a start, copy all the files that are not in the new tarball: it's probably not wrong.

          # Be in the new tarball before running this.
          for i in $(find .)
          do
            if test ! -f ../my-old-working-directory/$i; then
              cp $i ../my-old-working-directory/$i
            fi
          done

     And then, build it step by step.

Now, more information about the T7 code delivered:

src/assem
     This directory contains the implementation of the Assem language: yet another intermediate representation that aims at encoding an assembly language, plus a few need features so that register allocation can be performed afterwards.  Given in full.

src/codegen
src/codegen/mips
     The instruction selection per se split into a generic part, and a target specific (MIPS) part.  See below...

src/codegen/asm-fragments.hh
     Just as with translate::Fragment: aggregate some informations that must remain together, such as a frame::Frame and the instructions (a list of assem::Instr).  It is specialized in the following files:

src/codegen/mips/asm-fragments.hh
src/codegen/mips/asm-fragments.cc
     How MIPS (and SPIM) fragments are to be displayed.  In other words, that's where the (global) syntax of the target assembly file is selected.

src/codegen/asm-visitor.hh
     Fragments will require polymorphism.

src/codegen/mips/runtime.s
     The Tiger runtime in MIPS assembly language: print etc.

src/codegen/fragment.hh
src/codegen/mips/fragment.hh
     Files that select MIPS's asm-fragment.hh.  In the near future, these files will be replaced by dynamic selection of the target.

src/codegen/codegen.hh
     The abstract class codegen::Codegen which is the interface for all our back ends.

src/codegen/mips/codegen.hh
src/codegen/mips/codegen.cc
     Our real and only back end: a translator from LIR to ASSEM using the MIPS 2000 instruction set.  It is implemented as a maximal munch.  Of course, codegne::mips::Codegen derives from codegen::Codegen.

src/target/
     Some data on the back end.

T7 Code to Write
----------------

There is not much code to write: there is a single function whose implementation is not provided: Codegen::munchMove in src/codegen/mips/codegen.cc.

Be aware that you are not required to fill in the blanks in the following places, as they are needed during register allocation only:

  - Codegen::allocate_frame (src/codegen/mips/codegen.cc)

  - Codegen::rewrite_program (src/codegen/mips/codegen.cc)

  - strcmp (src/codegen/mips/runtime.s)

  - print_int (src/codegen/mips/runtime.s).  This is the easiest, as it's just a call to the appropriate ``syscall''.

  - substring (src/codegen/mips/runtime.s).  This one is quite delicate.

  - concat (src/codegen/mips/runtime.s).  As above.

T8, Liveness Analysis
=====================

This section is to be written for class 2004.

This section was last updated for EPITA-2004 on 2003-05-16.

T8 Samples
----------

     1 | 2 | 3
     File 99: ors.tig

     [file 100.texi not included]

     File 101: Main-Main-flow.dot

     [file 102.texi not included]

     File 103: Main-Main-liveness.dot

T8 Given Code
-------------

  - 2004-tc-8.0.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-8.0.tar.bz2), the whole tarball.

  - 2004-tc-7.5-8.0.diff (http://www.lrde.epita.fr/~akim/compil/download/2004-tc-7.5-8.0.diff), the differences with the latest tarball that was delivered.

T8 Code to Write
----------------

T9, Register Allocation
=======================

This section is to be written for class 2004.

This section was last updated for EPITA-2004 on 2003-04-07.

At the end of this stage, the compiler produces code that is runnable using SPIM.

T9 Samples
----------

T9 Given Code
-------------

T9 Code to Write
----------------

Tools
*****

This chapter aims at providing some helpful information about the various tools that you are likely to use to implement tc.  It does not replace the reading of the genuine documentation, nevertheless, helpful tips are given.  Feel free to contribute additional information.

Modern Compiler Implementation
==============================

The single most important tool for implementing the Tiger Project is the original book, Modern
Compiler Implementation in C/Java/ML (http://www.cs.princeton.edu/~appel/modern/), by Andrew W. Appel (http://www.cs.princeton.edu/~appel/), published by Cambridge University Press (New York, Cambridge).  ISBN 0-521-58388-8/.

It is not possible to finish this project without having at least one copy per group.  We provide a convenient mini Tiger Compiler Reference Manual (http://www.lrde.epita.fr/~akim/compil/tiger.html) that contains some information about the language but it does not cover all the details, and sometimes digging into the original book is required.  This is on purpose, by virtue of due respect to the author of this valuable book.

Several copies are available at the EPITA library.

There are three flavors of this book:

C
     The code samples are written in C.  I strongly recommend that you avoid this edition, as C is not appropriate to describe the elaborate algorithms involved: most of the time, the simple ideas are destroyed with longuish unpleasant lines of code.

Java
     The samples are written in Java.  This book is the closest to the EPITA Tiger Project, since it is written in an object oriented language. Nevertheless, the modelisation is very poor, and therefore, don't be surprised if the EPITA project is significantly different.  For a start, there is no Visitors at all.  Of course the main purpose of the book is compilers, but it is not a reason for such a poor modelisation.

ML
     This book, which is the ``original'', provides code samples in ML, which is a very adequate language to write compilers.  Therefore it is very readable, even if you are not fluent in ML.  I recommend this edition, unless you have severe problems with functional programming.

This book addresses many more issues than the sole Tiger Project as we implement it.  In other words, it is an extremely interesting book which provides insights on garbage collection, object oriented and functional languages etc.

There is a dozen copies at the EPITA library, but buying it is a good idea.

Pay extra attention: there are several errors in the books, some of which are reported on Andrew Appel's pages (C (http://www.cs.princeton.edu/~appel/modern/c/errata.html) Java (http://www.cs.princeton.edu/~appel/modern/java/errata.html), and ML (http://www.cs.princeton.edu/~appel/modern/ml/errata.html)), some which are not.

The GNU Build System
====================

Automake is used to facilitate the writing of power Makefile. Autoconf is required by Automake: we don't not address portability issues for this project.

You may read the Autoconf documentation (http://www.gnu.org/manual/autoconf/index.html), and the Automake
documentation (http://www.gnu.org/manual/automake/index.html).  Using info is pleasant: info autoconf on any properly set up system.  The Goat Book (http://sources.redhat.com/autobook/) covers the whole GNU Build System: Autoconf, Automake and Libtool.

Package Name and Version
------------------------

To set the name and version of your package, change the AC_INIT invocation.  For instance, T4 for the bardec_f group gives AC_INIT(bardec_f-tiger, 4).  Warning: Autoconf 2.53 smashes the underscores into dashes.  To workaround this misfeature, use:

     AC_INIT([bardec_f-tiger], 4, [bardec_f@epita.fr], [bardec_f-tiger])

Bootstrapping the Package
-------------------------

If something goes wrong, or if it is simply the first time you create configure.ac or a Makefile.am, you need to set up the GNU Build System.  The simplest invocation is:

     $ autoreconf -fvi

The various files (configure, Makefile.in, etc.) are created.  There is no need to run make distclean, or aclocal or whatever, before running autoreconf: it knows what to do.

Then invoke configure and make:

     $ ./configure CC=GCC-3.2 CXX=G++-3.2
     $ make

where GCC-3.2 and G++-3.2 are the name of the GNU C and C++ Compiler 3.2 executables.

Making a Tarball
----------------

Once the package autotool'ed (see Bootstrapping the Package), once you can run a simple make, then you should be able to run make distcheck to set up the package.

The mission of make distcheck is to make sure everything will work properly.  In particular it:

 1. creates the tarball (via make dist)

 2. untars the tarball

 3. configures the tarball in a separate directory (to avoid cluttering the source files with the built files).  Note that if you ran the top level configure with some options (e.g., ./configure CC=gcc-3.2 CXX=g++-3.2), then these options will not be taken into account here.  This means that running export CC=GCC-3.2; export CXX=G++-3.2 is a better way to make sure that these compilers will be used.

 4. runs make (and following targets) in paranoid mode.  This mode consists in forbidding any change in the source tree, because if, when you run make something must be changed in the sources, then it means something is broken in the tarball.  If, for instance, for some reason it wants to run autoconf to recreate configure, or if it complains that autom4te.cache cannot be created, then it means the tarball is broken!  So track down the reason of the failure.

 5. runs make check

 6. runs make dist again.

If you just run make dist instead of make distcheck, then you might forget to include some files in the distribution.  If you don't even run make dist, then not only some files might be missing, but you have no guarantee that the tarball will compile elsewhere (not to mention that we don't care about object files etc.).

Running make distcheck is the only means for you to check that the project will properly compile on our side.  Not running distcheck is like turning off the type checking of your compiler: you hide the errors, you avoid them, instead of actually getting rid of them.

At this stage, if running make distcheck does not create bardec_f-tc-4.tar.bz2, then something is wrong in your package. Do not rename it, do not create the tarball by hand: something is rotten and be sure it will break on the examiner's machine.

Flex & Bison
============

We use Bison 1.875a which is able to produce a C++ parser.  This Bison is unpublished, as the maintainers still have issues to fix. Nevertheless, it is usable, and perfectly functional for Tiger.  It is installed in ~akim/bin, under the name bison.  Be aware that Bison 1.875 produces buggy C++ parsers.

If you don't use this Bison, you will be in trouble.  If you are willing to work at home, use bison-1.875a.tar.bz2 (http://www.lrde.epita.fr/~akim/compil/download/bison-1.875a.tar.bz2).

The original papers on Lex and Yacc are:

Johnson, Stephen C. [1975].
     Yacc: Yet
     Another Compiler Compiler (http://epaperpress.com/lexandyacc/download/yacc.pdf). Computing Science Technical Report No. 32, Bell Laboratories, Murray hill, New Jersey.

Lesk, M. E. and E. Schmidt [1975].
     Lex: A Lexical
     Analyzer Generator (http://epaperpress.com/lexandyacc/download/lex.pdf). Computing Science Technical Report No. 39, Bell Laboratories, Murray Hill, New Jersey.

The following introduction guides can help beginners:

Thomas Niemann.
     A Compact Guide to Lex & Yacc (http://www.epaperpress.com/lexandyacc/index.html).

     An introduction to Lex and Yacc.

Collective Work
     Programming with
     GNU Software (http://www.lrde.epita.fr/~akim/compil/gnuprog2/).

     Contains information about Autoconf, Automake, Gperf, Flex, Bison, and GCC.

The Bison
documentation (http://www.lrde.epita.fr/~akim/doc/bison.html), and the Flex documentation (http://www.lrde.epita.fr/~akim/doc/flex.html) are available for browsing.

Doxygen
=======

We use Doxygen (http://www.doxygen.org/index.html) as the standard tool for producing the developer's documentation of the project.  Its features must be used to produce good documentation, with an explanation of the role of the arguments etc.  The quality of the documentation will be part of the notation.  Details on how to use proper comments are given in the Doxygen Manual (http://www.stack.nl/~dimitri/doxygen/manual.html).

The documentation produced by Doxygen must not be included, but the target html must produce the html documentation in the doc/html directory.

Appendices
**********

Glossary
========

activation block
     Portion of dynamically allocated memory holding all the information a (recursive) function needs at runtime.  It typically contains arguments, automatic local variables etc.  Implemented by the class frame::Frame (see T5).

stack frame
     See ``activation block''.

     [file fdl.texi not included]