Center for ST
Assignment Getting Started
In this assignment you will install the software you need for the lab assignments of this course. Also, you will learn the basics of the Tiger language. This language is used in many of the examples and assignments during this course. Furthermore, you will learn how to use some of the tools of the Tiger compiler. After this session, you should have a comfortable working environment, so that you can immediately start with the real work in the next lab assignment. %TOC% ---++ Installation ---+++ Configuring a User-Friendly Shell (aka using =bash= instead of =ksh=) (This section is optional. Please ignore if your are perfectly comfortable using your current shell) Most of the time, we will be working in a terminal. Therefore, it is important that the shell you are using is user-friendly. For example, it is quite useful if pressing the =Delete= key actually deletes a character. For many users, =bash= is easier to use then the default shell on our Linux machines: =ksh= (Korn Shell). You can find out what shell you are using by typing: <verbatim> ps $$ </verbatim> You can also recognize the shell by its prompt: the usual prompt of =ksh= is a plain =$=. Bash usually shows the current user, directory, followed by a =>=. You can change the shell to bash by just entering the command =bash=. If you want to change your shell to bash forever, then add the line =bash= the end of the file =.profile=. From now, we will assume that you are using bash. If you Bash prompt is not =user:currentdir>=, then you can configure bash to use this prompt by adding the line <verbatim> PS1="\\u:\\w> " </verbatim> to your =.bashrc= file. ---+++ Preparing for Using Nix The software you will use in this course is deployed using [[Trace.Nix][Nix]]. Nix is already installed on the Linux machines. You can easily install Nix at home if you want to work on the assignments on your own computer. First, you have to prepare your account for using Nix. Please add the following line to =~/.bashrc= (create the file if it does not exist. =~= stands for your home directory, aka =$HOME=. You can edit =.bashrc= with any plain text editor you want (emacs, vi, gedit, ...) <verbatim> . /nix/etc/profile.d/nix.sh </verbatim> Now, start a new terminal, and start the bash shell (the default shell is =ksh=, which is not very user-friendly). Now you should be able to invoke the program =nix-env=, since the line you have just added to =.bashrc= adds the Nix installation directory to your path. Try if the tool indeed can be found using: <verbatim> $ nix-env --help </verbatim> This should print some information on how to use =nix-env=, which you can ignore for now. You are now ready to use Nix to install the required software. ---+++ Subscribe to the =pt-software= Channel The software you need during this course is available in a so called *Nix channel*. You can use this Nix channel to install all the software safely and quickly and it is easy to update your installation if new software is available. First, you have to subscribe yourself to this channel: <verbatim> $ nix-channel --add http://catamaran.labs.cs.uu.nl/dist/stratego/channels/pt-software-stable </verbatim> Next, update the channels you are subscribed to: <verbatim> $ nix-channel --update </verbatim> You can now have a look at the software that is available in this channel: <verbatim> $ nix-env -qas </verbatim> This will show a list of packages, all called =pt-software=. You can now install this software: <verbatim> $ nix-env -i pt-software </verbatim> After downloading some files, all the software for this course will be available. You can try this using one or more of the following commands: <verbatim> $ sglr --help $ strc --help $ stratego-shell --help $ run-tiger --help </verbatim> Unfortunately, =sglr= (part of the sdf2-bundle) and =strc= (part of Stratego/XT) are in fact already installed in =/usr=. Please check if your =PATH= is configured correctly by verifying the version of =strc= using: <verbatim> $ strc --version </verbatim> This should print 0.14 (*not* 0.11, which is the version of =strc= installed in =/usr=). For more information about using Nix and Nix channels, please consult the [[http://catamaran.labs.cs.uu.nl/dist/nix/nix-unstable-latest/manual/manual.html][Nix manual]], also available from the [[Trace.Nix][Nix]] website. ---+++ Update Before Every Session Before starting on your assignments, you should always check if we have updated or added software in the Nix channel. This is done using the following commands: <verbatim> $ nix-channel --update $ nix-env -u pt-software </verbatim> ---+++ Make GNU Emacs User Friendly (This section is optional. Please ignore if you already have a favourite editor for Linux) For some students this will be their first experience with a GNU/Linux system. If you are looking for a good editor, then GNU Emacs is a good choice, but of course you can use whatever editor you want. Unfortunately, GNU Emacs has some rough edges in its default configuration. In this section we will explain how to configure GNU Emacs to make it more user friendly First, many people are used to =Ctrl-cxv= and using =Shift= for selection. The CUA mode configures Emacs to use these key bindings. Download the [[http://www.cua.dk/cua.el][CUA Mode]] ([[http://losser.labs.cs.uu.nl/~mbravenb/cua.el][mirror]]) to a directory, for example =myemacs= or =.myemacs= (hidden). Next, edit the file =~/.emacs= to activate the CUA mode. Add the following lines the end of this file: <verbatim> (add-to-list 'load-path "~/myemacs") (require 'cua) (CUA-mode t) </verbatim> Now you can start GNU Emacs: <verbatim> $ emacs </verbatim> You can specify files that you want to open on the command-line, and you open files via the menu. Check if your =Ctrl-cxv= works and cry for help if it does not. Next, you might want to change the default font of GNU Emacs. You can do that by saving [[https://svn.cs.uu.nl:12443/repos/mbravenboer/config/.Xdefaults][this file]] to your home directory. ---++ Learn the Tiger Language The Tiger language is a small, imperative languages designed by Andrew Appel for his series [[http://www.cs.princeton.edu/~appel/modern/][Modern Compiler Implementation in Java/C/ML]]. We will use the Tiger language in this course to study program transformations. ---+++ Resources The Tiger Language Reference is part of the book of Andrew Appel, but fortunately some online documents also introduce the language: * [[http://www.cs.columbia.edu/~sedwards/classes/2002/w4115/tiger.pdf][Tiger Language Reference Manual]] (by Prof. Stephen A. Edwards) * [[http://www.lrde.epita.fr/~akim/compil/tiger.html][Tiger Language Reference Manual]] (by Akim Demaille) ---+++ Running Tiger Programs To learn the Tiger language, read one of these manual to learn the basics of the Tiger language. You can experiment with your own Tiger programs by executing them using the tool =run-tiger=, which is an interpreter for Tiger, implemented in Stratego. You can write your Tiger programs in a file, or just specify them on the command-line. <verbatim> $ run-tiger -i hello-world.tig </verbatim> or <verbatim> $ echo 'print("Hello world")' | run-tiger $ echo 'printint(1 + 2)' | run-tiger </verbatim> Try to implement some Tiger programs with control-flow, functions, and variables. An example of the factorial program: <verbatim> let function fact(n : int) : int = if n < 1 then 1 else (n * fact(n - 1)) in printint(fact(10)) end </verbatim> ---++ Using Components of the Tiger Compiler In this part of the assignment you will use some of components of the Tiger compiler to compose real program transformations. ---+++ Parsing and Pretty-Printing The Tiger compiler provides a Tiger parser and a Tiger pretty-printer. The =parse-tiger= tool parses a Tiger program and constructs an abstract syntax tree. The details of this tree are not important for now. The =pp-tiger= tool pretty-prints a Tiger abstract syntax tree back to an ordinary Tiger program. Example: <verbatim> $ parse-tiger -i test.tig | pp-tiger </verbatim> Again, you can also enter some Tiger code at the command-line: <verbatim> $ echo "1 + 2" | parse-tiger | pp-tiger </verbatim> ---+++ Desugaring and Ensugaring The tool =Tiger-Desugar= removes some syntax sugar from a Tiger program. Try to find out what this tool does by applying it in the following pipeline: <verbatim> $ parse-tiger -i ... | Tiger-Desugar | pp-tiger </verbatim> The tool =Tiger-Ensugar= re-adds the syntactic sugar. Try this by adding it to the pipline: <verbatim> $ parse-tiger -i ... | Tiger-Desugar | Tiger-Ensugar | pp-tiger </verbatim> ---+++ Type Checking The tool =Tiger-Typecheck= implements a type checker for Tiger. It should be applied after =Tiger-Desugar= and the result can pretty-printed with =pp-tiger=. Try to some valid and invalid Tiger programs and observe how this tool reports the errors. ---+++ Function Inlining =Tiger-Inline= is an optimization that inlines function bodies at the call-site. Again, this tool should be applied after Tiger-Desugar. Try to apply this tool to a program with functions. In which cases are functions not inlined? ---+++ Dead-code Elimination The tool =Tiger-Inline= does not actually remove the function definitions after inlining. The tool =Tiger-DeadFunElim= achieves this. Apply it after =Tiger-Inline= to cleanup the code. ---++ Submit You don't actually have to submit anything. If you have done this assignment well, then you will benefit from this while working on the next lab assignments.