CSE 200: Computability and Complexity

WHILE programming language

This is a brief tutorial on how to write and run WHILE programs. Our version of the WHILE programming language is a variant (mostly a simplification) of the one described in Neil D. Jones' Computability and complexity: from a programming perspective, MIT Press, c1997. I assume basic computer literacy, and some familiarity with common commands and programs like "grep", the C preprocessor, etc. I do theoretical computer science, so you should know at least as much as me about this, and be able to follow. If you need help contact me or the TA.

Nested lists

The only data structures used in WHILE are (nested) lists, as defined by the following grammar: Examples of lists are For readibility, we use 0 and 1 as abbreviations for the lists [] and [[]] respectively, so we can write [0110] instead of [[][[]][[]][]]. However, we emphasize that these are just abbreviations, so that any list can be represented as a sequence of [ and ] symbols, and the elements of a list are always lists. The following operations can be performed on lists:

Program Syntax

The syntax of WHILE programs is specified by the following grammar. A WHILE program is a list of commands separated by semicolons ";" and enclosed in braces "{", "}". There are just two commands: assignments, and while loops. Variables are sequences of symbols. The expressions on the right hand side of assignments can be a variable symbol, a list constant, the head or tail of a variable, or the concatenation of two variables. We use the convetion that the input to the program is passed in variable X, and the output is also returned in the same variable. Here is a small program to compute the reverse of a list that illustrates most language features. Formatting (spaces, line breaks, etc.) do not affect the semantics of WHILE programs, but the program below is also a good example of how to properly use indentation to make the program more readable.
  Y = [];
  while X do {
    H = hd X;
    Y = H . Y;
    X = tl X;
  X = Y;
And now, let's run the program.

A WHILE interpreter

Here is a WHILE interpreter I wrote for the course. The interpreter is just about 120 lines of Haskell code (including the parser), so don't expect much from it, but it should be fairly easy to run, as long as you have a working Haskell compiler or interpreter on your computer. Here are some installation instructions written by the TA. I wrote and tested the interpreter using the Glasgow Haskell Compiler ghc, so I will refer to this compiler below, However, I expect the interpreter to work with pretty much any other current Haskell implementation, e.g., the Hugs system. Do the following: The current version of the interpreter includes a few convenient extensions over the basic WHILE language described above. This include Java style comments /*...*/ and //..., and compound expressions (e.g., (hd X) . (tl (tl X))) both in the right hand side of assignments, and tests in while loops. It also accepts "print X" instructions to print out the value of a variable (useful to debug WHILE programs), however this is not yet implemented in version while-v0.0 of the interpreter.

Other useful programs

while-v0.1.hs: this is a newer version of the interpreter. It supports the print instruction, but I appears that there is something wrong with it, probably a memory leak due to the lazy evaluation strategy of haskell.

runtime.whp: this is a modified version of the self interpreter. The main program (macro) is called Runtime, and on input a WHILE program P, input list L, and variable Result, sets Result to the running time P on input L (represented as a list of the for [000000] of length t.)

Macros and formatting guidelines

WHILE is not a real programming language. It is just a theoretical tool (like Turing machines) to study computability and complexity theory. In particular, WHILE has only minimal data and control structures. In practice, you may want to use values other than lists, use control structures other than "while" loops (e.g., if/then/else), and structure your program in a modular way. All this can be accomplished using macros. Here is a revised version of the reverse program that defines reverse as a macro, and then calls it in the main body of the program:
#define reverse(Z)     \
  Y = [];              \
  while Z do {         \
    Y = (hd Z) . Y;    \
    Z = tl Z;          \
  };                   \
  Z = Y


Notice the use of "\" at the end of each line. Also notice that "reverse(Z)" is defined as a sequence of commands separated (but not terminated) by ";", and not enclosed in braces. We wrote the reverse program this way so that you can pass the above program through the C preprocessor cpp.

You can download the program reverse.whp. I will use the convention that WHILE programs have filename extension ".wh", and WHILE programs with macros have filename extension ".whp". Programs with filenames ending in ".whp" need to be preprocessed before you can execute them with our WHILE interpreter.

Now perform macro substitution using the C preprocessor:
cpp -P reverse.whp
The output of the above command is exactly what you would expect:
{ Y = []; while X do { Y = (hd X) . Y; X = tl X; }; X = Y }
You can directly execute a ".whp" program with a command like
cpp -P reverse.whp | while [000111]
Now replace "reverse(X)" in the body of the above program with "reverse(X); reverse(X)", and you get an implementation of the identity function! Notice: the result after macro substitution is far less readable than the unpreprocessed program. When submitting code as part of your assignments you should submit the source program before preprocessing, and formatted with proper use of indentation and comments.

Standard library and Self Interpreter

Through the course, we will define and use several useful macros. You can find these macros in the WHILE Standard Library StdLib.whp, which I will keep updating as we define new macros. You can use the standard library in your programs by downloading StdLib.whp, and starting your programs with the line
#include "StdLib.wh"
The C preprocessor will take care of including the definitions from the standard library and expand the macros into WHILE programs that can be executed using the interpreter.

If you want to get a glimpse of the next lecture, here is some code whileSyntax.whp specifying how to encode WHILE programs as lists, and a self interpreter self.whp that can execute arbitrary WHILE programs. You can test the self interpreter using the example program selfExample.whp which is just the encoding of out list reversal program reverse.wh.

Test the programs using the command
cpp -P selfExample.whp | while [010111]
You should get as a result the reverse of the input list [111010].