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.

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:

ps $$

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

PS1="\\u:\\w> "

to your .bashrc file.

Preparing for Using Nix

The software you will use in this course is deployed using 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, ...)

. /nix/etc/profile.d/nix.sh

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:

$ nix-env --help

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:

$ nix-channel --add http://catamaran.labs.cs.uu.nl/dist/stratego/channels/pt-software-stable

Next, update the channels you are subscribed to:

$ nix-channel --update

You can now have a look at the software that is available in this channel:

$ nix-env -qas

This will show a list of packages, all called pt-software. You can now install this software:

$ nix-env -i pt-software

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:

$ sglr --help
$ strc --help
$ stratego-shell --help
$ run-tiger --help

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:

$ strc --version

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 Nix manual, also available from the 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:

$ nix-channel --update 
$ nix-env -u pt-software

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 CUA Mode (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:

(add-to-list 'load-path "~/myemacs")
(require 'cua)
(CUA-mode t)

Now you can start GNU Emacs:

$ emacs

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 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 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:

• Tiger Language Reference Manual (by Prof. Stephen A. Edwards)
• 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.

$ run-tiger -i hello-world.tig

or

$ echo 'print("Hello world")' | run-tiger
$ echo 'printint(1 + 2)' | run-tiger

Try to implement some Tiger programs with control-flow, functions, and variables. An example of the factorial program:

let function fact(n : int) : int =
      if n < 1 then 1 else (n * fact(n - 1))
 in printint(fact(10))
end

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:

$ parse-tiger -i test.tig | pp-tiger

Again, you can also enter some Tiger code at the command-line:

$ echo "1 + 2" | parse-tiger | pp-tiger

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:

$ parse-tiger -i ... | Tiger-Desugar | pp-tiger

The tool Tiger-Ensugar re-adds the syntactic sugar. Try this by adding it to the pipline:

$ parse-tiger -i ... | Tiger-Desugar | Tiger-Ensugar | pp-tiger

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.