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:

L ::= [L ... L]

Examples of lists are

[]: the empty list
[[]]: the singleton list containing [] as its only element
[ [] [[]] ]: the list of length two containing the lists from the previous examples as elements.

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:

head L: returns the first element of list L, with the convention that head [] = [].
tail L: returns the remaining elements of L, with the convention that head [] = [].
H . T: returns the list with head H and tail T.

Program Syntax

The syntax of WHILE programs is specified by the following grammar.

P ::= { C1 ; ... ; Cn }
C ::= V = E | while V do P
E ::= V | L | V . V' | hd V | tl V
V ::= any sequence of symbols

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:

If not already present on your system, install the ghc compiler (or equivalent) available from the GHC page or through your OS package distribution system. (Search for package name ghc, or similar.)
Download the WHILE interpreter while-v0.0
Compile it with the command "ghc --make while-v0.0.hs". (The parsec parser combinator library is part of the standard ghc distribution, and should not require the installation of additional packages.)
The while interpreter expects a WHILE program on the standard input, and an input argument on the command line. Download (or type) the reverse.wh program, and try it out running the command "while <reverse.wh [010111]", where "while" is the name of the executable produced by ghc. You should get as a result the list [111010].
Alternatively, you can run the interpreter directly from source with the command "runghc while-v0.0.hs <reverse.wh [010111]".

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

{
  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.

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].