Translate Haskell into English Manually

Have you ever tried to learn Haskell (haskell.org) and hit a brick wall? Have you tried to read the main tutorial, "A Gentle Introduction to Haskell" (www.haskell.org/tutorial), and found it to be about as gentle as a Pan Galactic Gargle Blaster (en.wikipedia.org/wiki/Pan_Galactic_Gargle_Blaster)? Did you have to learn about monads before you could even write your first non-trivial Haskell program? Have you noticed that unless you already know Haskell, it's even less readable than Shakespeare? Have you searched for an example of a nontrivial Haskell program only to find you can't understand it?

In Expert C Programming: Deep C Secrets (which, by the way, is a must read for anyone who ever uses the letter C), Peter van der Linden teaches the reader how to write a small program that translates C-type declarations into English. It's a great little exercise. It's beautiful because it works without relying on powerful tools like Lex and Yacc, yet it's still small enough to be written in a couple hours. I've read stories about people writing Pascal compilers in Haskell, and there's even a version of Perl 6 written in Haskell (www.pugscode.org).

In my last article (www.linuxjournal.com/article/8850), I gave readers an introduction to monads and why they should care about them as well as Haskell in general. (Note: several readers of my last article wondered why I was interested in Haskell in contrast to other excellent languages such as OCaml, Dylan or Common Lisp. Currently, I'm fascinated by Haskell because it is a purely functional programming language, and because it has lazy evaluation. As strange as it might sound, I'm fascinated by Haskell because it's harder for me to wrap my head around than those other languages.) If you still don't believe that Haskell is worthy of attention, read what Tim Sweeney, the founder of Epic, the video game company that created Unreal, said about it at beust.com/weblog/archives/000375.html. Sweeney feels that Haskell may be the gateway to "The Next Mainstream Programming Language". Because video game developers are often on the cutting edge of our field simply out of necessity, his comments are noteworthy.

In this two-part series, starting with Peter van der Linden's exercise, my hope is to give readers a glimpse of the Zen of Haskell, without requiring that they already be Haskell converts. In this first part, I start by reviewing the C version, and I explain why translating imperative code into Haskell isn't an easy thing to do. I finish by explaining the concept of a parse pipeline.

Let's start by reviewing the C version:

/* Translate C type declarations into English.

   This code was taken from "Expert C Programming: Deep C Secrets", p. 84.
   [sic: weird whitespace inconsistencies]

   Compiling: gcc cdecl.c -o cdecl
   Usage: echo -n "int *p;" | ./cdecl */

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define MAXTOKENS 100
#define MAXTOKENLEN 64

enum type_tag { IDENTIFIER, QUALIFIER, TYPE };

struct token {
    char type;
    char string[MAXTOKENLEN];
};

int top=-1;
struct token stack[MAXTOKENS];
struct token this;

#define pop stack[top--]
#define push(s) stack[++top]=s

enum type_tag classify_string(void)
/* figure out the identifier type */
{
    char *s = this.string;
    if (!strcmp(s,"const")) {
	strcpy(s,"read-only");
	return QUALIFIER;
    }
    if (!strcmp(s,"volatile")) return QUALIFIER;
    if (!strcmp(s,"void")) return TYPE;
    if (!strcmp(s,"char")) return TYPE;
    if (!strcmp(s,"signed")) return TYPE;
    if (!strcmp(s,"unsigned")) return TYPE;
    if (!strcmp(s,"short")) return TYPE;
    if (!strcmp(s,"int")) return TYPE;
    if (!strcmp(s,"long")) return TYPE;
    if (!strcmp(s,"float")) return TYPE;
    if (!strcmp(s,"double")) return TYPE;
    if (!strcmp(s,"struct")) return TYPE;
    if (!strcmp(s,"union")) return TYPE;
    if (!strcmp(s,"enum")) return TYPE;
    return IDENTIFIER;
}

void gettoken(void) /* read next token into "this" */
{
    char *p = this.string;

    /* read past any spaces */
    while ((*p = getchar()) == ' ' ) ;

    if (isalnum(*p)) {
	/* it starts with A-Z,0-9 read in identifier */
	while ( isalnum(*++p=getchar()) );
	ungetc(*p,stdin);
	*p =  '\0';
	this.type=classify_string();
	return;
    }

    if (*p=='*') {
	strcpy(this.string,"pointer to");
	this.type = '*';
	return;
    }
    this.string[1] = '\0';
    this.type = *p;
    return;
}

/* The piece of code that understandeth all parsing. */
read_to_first_identifier() {
    gettoken();
    while (this.type!=IDENTIFIER) {
	push(this);
	gettoken();
    }
    printf("%s is ", this.string);
    gettoken();
}

deal_with_arrays() {
    while (this.type=='[') {
	printf("array ");
	gettoken(); /* an number or ']' */
	if (isdigit(this.string[0])) {
	    printf("0..%d ",atoi(this.string)-1);
	    gettoken();	/* read the ']' */
	}
	gettoken(); /* read next past the ']' */
	printf("of ");
    }
}

deal_with_function_args() {
    while (this.type!=')') {
	gettoken();
    }
    gettoken();
    printf("function returning ");
}

deal_with_pointers() {
    while ( stack[top].type== '*' ) {
	printf("%s ", pop.string );
    }
}

deal_with_declarator() {
    /* deal with possible array/function following the identifier */
    switch (this.type) {
    case '[': deal_with_arrays(); break;
    case '(': deal_with_function_args();
    }

    deal_with_pointers();

    /* process tokens that we stacked while reading to identifier */
    while (top >= 0) {
	if (stack[top].type == '(' ) {
	    pop;
	    gettoken(); /* read past ')' */
	    deal_with_declarator();
	} else {
	    printf("%s ",pop.string);
	}
    }
}

main()
{
    /* put tokens on stack until we reach identifier */
    read_to_first_identifier();
    deal_with_declarator();
    printf("\n");
    return 0;
}

Notice the stack of tokens and what the various functions do. By and large, I'll follow this closely in the Haskell version, so that the two versions can be compared. Again, notice that Lex and Yacc aren't used. Haskell has no shortage of powerful parsing libraries, but I've decided not to use any of them. After all, if I used a powerful parsing library in the Haskell version, trying to compare the C version to the Haskell version would be like trying to compare apples to peach cobbler.

Last of all, notice that the C version uses global variables for the token stack and so forth. It also prints output wherever convenient. This makes it easy to code, but it doesn't make it easy to translate to Haskell. This is the biggest difference between the C version and the Haskell version. After all, in a purely functional programming language like Haskell, a function can only take inputs and produce outputs. It can't update global state (there are no global variables), and it can't just print a string whenever it is convenient. However, staying purely functional has benefits that are hard to match in an imperative language. For instance, Haskell is lazy and non-strict. It evaluates expressions in whatever order it feels is necessary and only as necessary. For instance, it does not evaluate the arguments to a function until they're actually used in the function--you can pass 1/0 to a function, and as long as the function never uses that parameter, there will be no error. This style of programming can be hard to wrap your head around when you're coming from an imperative and/or object-oriented background. (The tutorial that really helped me finally understand "the Haskell way" was the "Haskell Tutorial for C Programmers" (www.haskell.org/~pairwise/intro/intro.html.)