CSE 501: Implementation of Programming Languages

Milestone 1: Project Set-Up


Due: start of class on Monday Jan. 23


Task 1: Experiment with Diesel (to be done individually)

For small experimentation with simple Diesel code, the Diesel evaluator is a fine option.  First, you need to log on to a Linux machine, e.g., the departmental instructional server (attu), one of the departmental research cycle servers (recycle, bicycle, or tricycle), or (as a last resort) one of the WASP research project machines (crab, cocoon, crescent, veil, lagoon, swan, trifid, or helix).  Now, you can run the Diesel evaluator by executing /cse/courses/misc_lang/vortex/run-diesel.  At the Diesel> prompt, enter expressions you'd like to evaluate.  You can invoke any functions and instantiate any classes from the Diesel standard library.  You also can define your own classes, functions and methods, fields, and variables.  You can write Diesel code in separate files, and then evaluate the contents of those files using Diesel include declarations.  (Diesel mode for emacs is available here.)  The evaluator will perform typechecking of any expressions or declarations you enter.  It's even possible to redefine functions, methods, and fields; duplicate declarations of variables and classes will be ignored.

You should also look at the following manuals to get yourself familiar with Diesel:


Task 2: Get a copy of the Vortex tree, run Vortex, and compile a program in Vortex

The interpreter is useful for experimenting with small Diesel programs, but for larger programs (like Whirlwind), the Vortex compiler is the best tool. Vortex is a whole-program optimizing compiler for Diesel, as well as a number of other object-oriented languages like Cecil, Java, and C++.

First, each group needs to install a copy of the Vortex tree in a CVS repository, and then each group member needs to check out a copy of the Vortex tree from that repository. We will be using the vendor branch feature of CVS to get you set up. We will provide you with a tar file and each group will create a CVS repository with the contents of this tar file. Then each group will use their CVS repository to manage the development of their local code. If there are bug fixes that we wish to provide you with, we will give you a new tar file, and each group will import this tar file into their CVS repository. Instructions on how to do this are here.

Now that each student has a copy of Vortex, you can start experimenting. To compile a Diesel program using Vortex, follow these steps (look at the How to Use the Vortex Compiler manual for more information, or look at  $VORTEX_HOME/notes/QUICK-START-VORTEX; $VORTEX_HOME refers to the directory containing each student's copy of Vortex, e.g. /projects/instr/06wi/cse501/<group_name>/<user_name>/vortex):

  1. Create one (or more) files with Diesel code in some directory. Let's say the directory is MYDIR and the main file is called mytest.diesel .
  2. There is a lot of Diesel code to look at for examples, all under $VORTEX_HOME/Diesel/src.  You may want to start by browsing stdlib (sources for the standard library except the evaluator) and tests/{towers,towers.tst}.diesel (a Towers of Hanoi test program). The Whirlwind compiler source code is in the whirlwind subdirectory. The Diesel mode for emacs is here.

  3. In a shell window, cd to MYDIR
  4. Start Vortex by running run-vortex.
  5. At the Vortex> prompt, type lang Diesel to tell Vortex what source language to assume.
  6. Type typecheck mytest (or tc mytest) to typecheck your program. After doing program editing, you can do typecheck (or tc) again to typecheck only the files you changed or that had type errors previously, or fulltypecheck (or ftc) to retypecheck everything. Although Vortex does not require you to typecheck the code before compiling, it's always a good idea to typecheck first, since it will help you catch errors earlier.
  7. To compile your program, type make. If you later make changes to your program, just type tc and make again to recompile it. You generally should keep Vortex running while doing editing, compiling, and testing, so that Vortex will incrementally recompile your program rather than starting from scratch to recompile your program. (And see the instructions about saving and loading checkpoints, below.)  Note that you can compile programs and run them even if they contain type errors; this lets you test incomplete or partially broken programs, up to the point that you hit an error at run-time.
  8. Run your program by typing run at the Vortex> prompt. Alternatively, you can run the program by going to another shell, and running the executable MYDIR/gen/mytest. Hope it works!
  9. If your program doesn't work, you can diagnose problems using the debugger. Insert a call to the breakpoint() function wherever you want to suspend execution. When this call is executed, your program will give you the debugging prompt ( debug> ), and you can use the full capabilities of the Diesel debugger/evaluator to interact with your program. In particular, you can type in Diesel expressions and see their values; if suspended at a breakpoint, your expression can reference any of the local variables in scope of the suspended function/method. Moreover, you can type in (or paste) the functions/methods you want to add (or replace) to your program, and they will be available to you without recompiling the program. Similarly, you can add variable declarations. Press Ctrl-D to exit the debugger (or type help for more options).  The print_line method, which takes a string argument and prints it, followed by a newline, is another handy, low-tech debugging tool, analogous to C's printf.

    The way the evaluator prints out values is by sending them the print_string message. By convention, this message returns a string that's a printable representation of its argument, but does not print anything itself. The debugger prints that string out. So if you define new kinds of classes in your program, you may also want to define the print_string methods so they print out nicely. Here's an example:

    method print_string(p@pair[`A,`B]):string {
     "(" || p.first.print_string || "," || p.second.print_string || ")" } 

    Remember that the debug> prompt is provided by your running program (and this is the place to add new methods and evaluate expressions), while the Vortex> prompt is printed by the compiler, and you should only issue compiler commands (like make) at that prompt.

  10. You can type help at the Vortex prompt to get a list of commands that you can run.
  11. You can quit Vortex by typing quit or Ctrl-D at the Vortex prompt.
  12. Vortex allows you to save a checkpoint (the state of Vortex) to a file. Checkpointing is very important! Once Vortex has compiled a program, it has done a lot of work that you don't want to repeat (for example, parsing the files and compiling them). If you simply quit Vortex, and then run it again, Vortex will start everything from scratch. So before you quit Vortex, you should checkpoint the state of the compiler, so that you can restore it later. The command save will save the state of the compiler to the file mytest.db, assuming that the program being compiled is mytest. When you restart Vortex later, the command load mytest.db will restore the state of the compiler. Because you are sharing your machine with others, you should save and quit Vortex when you are done using it, and then restore the state later when need to run Vortex again. However, you can keep Vortex running while you debug and edit your program; you don't need to exit Vortex after each make. Vortex has incremental compilation: if you change a file in your source program, and type make or tc, it will reparse/retypecheck/recompile only those parts that have changed.
  13. There are several variations on the basic make command. The makeo2 command sets the optimization level to 2, and recompiles any files not at that optimization level. Prepending the letter p to any make command (for example pmakeo2) will perform the C compilation phase in parallel on several machines, assuming you have ssh configured to log you in transparently on all the research Linux machines listed above; much faster!. (Type help make for more details.)

    Turning on optimization doesn't preclude debugging; Vortex does work to try to preserve the illusion of unoptimized code in its debugger, even in the face of Vortex's reams of inlining.  However, in the face of optimization, not all functions/methods can have breakpoints set on them, and not all functions/methods can be replaced at the debug> prompt.  To avoid this problem, you can compile most of your program with optimization, and recompile without optimization those parts of your program that you want to debug heavily.  Better, see the manual below for information on how retain full debuggability for files even in the face of full optimization using (**debug**) pragmas.

You should look at the following manual for more details about how Vortex works:


Task 3: Compile Whirlwind (to be done individually)

You are now ready to compile Whirlwind. The source for Whirlwind is located in $VORTEX_HOME/Diesel/src/whirlwind. Vortex already has this directory in its source path list, so you can compile Whirlwind from any directory. Thus pick a directory where you want your generated C files and object files to be stored for the whirlwind program. Let's say you choose /projects/instr/06wi/cse501/<group_name>/<user_name>/ww. Now do:
% mkdir /projects/instr/06wi/cse501/<group_name>/<user_name>/ww
% cd /projects/instr/06wi/cse501/<group_name>/<user_name>/ww
% $VORTEX_HOME/run-vortex
Vortex> tc whirlwind
... lots of nice output ...
Vortex> load_profile /cse/courses/cse501/06wi/distributions/whirlwind.nCCP
... load in dynamic profile data about Whirlwind, for better optimization quality ...
Vortex> makeo2
... more reams of output ...
Vortex> save
... saves whirlwind.db, for later reference ...
Vortex> really_quit
%

Task 4: Compile a WIL program using Whirlwind (to be done individually)

The file $VORTEX_HOME/Diesel/src/whirlwind/notes/wil-ref.txt documents the WIL intermediate language.  Whirlwind test files written in WIL are in $VORTEX_HOME/Diesel/src/whirlwind/tests; the file test.wil is the root file that includes and runs all the tests.  Test out your Whirlwind compiler by compiling and running these tests.  Whirlwind already has the tests directory in its source path list, so you can compile test.wil from any directory. Thus, pick a directory where you want your generated C files and object files to be stored for the test program. Let's say you choose /projects/instr/06wi/cse501/<group_name>/<user_name>/test. Now do:
% mkdir /projects/instr/06wi/cse501/<group_name>/<user_name>/test
% cd /projects/instr/06wi/cse501/<group_name>/<user_name>/test
% /projects/instr/06wi/cse501/<group_name>/<user_name>/ww/gen/whirlwind
Whirlwind> makeo2 test
... lots of nice output ...
Whirlwind> save
... saves test.db, for later reference ...
Whirlwind> run
... output of the gen/test program, hopefully all successful ...
Whirlwind> really_quit
%
The makeo2 command compiles with optimization level 2. Anything above 0 will turn (Whirlwind) optimizations on.

Task 5: Implement propositional formulae in Diesel (to be done individually)

You will develop an implementation of propositional logic formulae in Diesel. Instructions for this task can be found here.

Task 6: Implement factorial in WIL (to be done individually)

Write the factorial function in WIL. You should start with the following file. To this file you should add:
  1. A factorial function. You can write it either recursively or iteratively.
  2. Some code in main that continually asks the user for a number n, and prints "n! = ..." until the number n entered by the user is -1.
You should not use any prim statements in the code that you add. Compile your program using Whirlwind, and test it out.

Deliverables

Each student should send an email to Craig and Marius by the beginning of class on Mon. Jan. 23 with the following attachments: