CSE 200: Computability and Complexity

WHILE programming language

This is a brief tutorial on how to write and run WHILE programs. I assume basic computer literacy, and some familiarity with common commands and programs like "grep", the C preprocessor, etc. I have never written a real program in C, so you should know at least as much as I do about this, and be able to follow. If you need help contact me or the TA.

Syntax

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 starting with an uppercase letter. Right hand sides of assignments and tests in while loops are expressions built up from variables starting from the empty list [] and variable names, using the constructor "." and destructors "hd" and "tl".

P ::= { C1 ; ... ; Cn }
C ::= Xi = E | while E do P
E ::= Xi | [] | E . E' | hd E | tl E

We use the convetion that the input to the program is passes 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 {
    Y = (hd X) . Y;
    X = tl X;
  };
  X = Y;
}

And now, let's run the program.

A WHILE interpreter

Here is a WHILE interpreter interp-v0.3.tgz written by William Matthews in python. It is assumed that you have a working python installation on your computer. Installation instructions for the interpreter:

Download and unpack interp-v0.3.tgz, e.g., using the command "tar -xzf interp-v0.3.tgz" on GNU/linux. This will create a directory "interp" with all necessary files into it.
Change directory "cd interp"
Try test program "prog1" running the command "./interp.py prog1 [[],[[]],[[[]]]]". Here interp.py is the name of the interpreter program, prog1 is the WHILE program to be executed, and "[[],[[]],[[[]]]]" is the input to be passed to the program in variable X.

Program "prog1" also illustrates various convenient features included in the interpreter. These include C-style comments /* e.g., this is a comment */ for documenting your programs, and a print instruction that you may find handy to debug your code. Now try out the reverse program. Type (or cut and paste) the above reverse program above, save it into file "reverse" and then run

./interp.py reverse  [[],[[]],[[[]]]]

As you may expect, this should output

Upon termination, X     =       [[[[]]], [[]], []]

WHILE programs 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

{
  reverse(X); 
}

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 reverse2

and get as a result a WHILE program that can be run by our simple interpreter. Well, not quite. The C preprocessor probably also produced some junk lines starting with "#". So, let's filter them out with

cpp reverse2 | grep -v \#

or, more easily (thanks) Kevin for pointing this out) run the preprocessor with the -P option

cpp -P reverse2

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; };

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

Through the course, we will defined and use several convenient macros. You can find these commands in the Standard Library, which will keep updating as we define new macros. At this point I only defined two constants for the boolean values true and false. You can use the standard library in your programs by loading the library into file "StdLib.wh", and starting your programs with the line #include "StdLib.wh". Again, the C preprocessor will take care to expand everything into bare WHILE programs that can be executed using the interpreter. Thanks to Sunsern for spotting a bug in an earlier version of the library.

Self Interpreter

In class, we formally defined the result of executing a WHILE program, and then constructed a self-interpreter, i.e., a program that on input the description of a WHILE program "P" and an input value x, outputs the result of running P on x. Here is the code of the interpreter self.wh, and a sample program selfExample.wh that illustrates the encoding of WHILE programs into lists, and the use of the self interpreter. You should use the encoding of WHILE programs as defined in self.wh in the homework assignments.