Lisp languages have been around for years. They are all built on a simple syntax: everything is made of lists (or tuples). An expression is a list, as well as instructions, definitions and even control structures. The first item in the list is usually the function or the operation that will be applied to every subsequent element in the list. That is true for mathematical operations, too.

As an exemple, in a Lisp language (+ 1 2) will be evaluated by performing the operation + (addition) on the following operands, 1 and 2. The computed result being 1 + 2 = 3. Another exemple is for division:

(/ 4 2) will result in 4 / 2 = 2. Obviously, this time, the order of the operands matters, since division is not a commutative operation.

In this little tutorial we’ll see how to build a very basic interpreter for simple Lisp expressions, like mathematical operations as seen above.

Our interpreter will be a simple REPL (Read-Eval-Print Loop) that will run forever waiting for the user to enter an expression, then parsing and evaluating it, to finally print to computed result.

This is a sample input / output of what we’ll achieve:

> (+ 2 2)
-> 4
> (* 1 2 3)
-> 6
> (/ 6 2)
-> 3

Let’s start by creating the file lisp.c and putting the basic stuff for every C program:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {  
    return 0;
}

We want to read input from the user forever, until program execution is stopped by the user (CTRL+C interruption, mostly). A simple function will read the input:

char* read() {  
    char* expr = malloc(256);
    fgets(expr, 256, stdin);
    return expr;
}

We first allocate a string by creating a pointer to a 256 bytes space in memory (it is likely expressions won’t be as long as 256 characters). The function returns the pointer to the freshly allocated string.

We must now write the most important function of our little exercise: a function that evaluate the input string and compute the numeric result.

int eval(char* expr) {  
    return 0;
}

Let’s return 0 for the moment, which is the default result as long as we don’t have a computed result. Our main function now look like this:

int main(int argc, char* argv[]) {  
    while (1) {
        eval(read());
    }

    return 0;
}

We are going to manipulate the pointer that points to our expression string, moving it character by character, to read every operands in the list, until we hit the ) character.

The first character we should read is the ( opening the list. The next one is the operator that will be applied on the list items. For now, we’re going to implement only the basic operators:

#define OP_ADD '+'
#define OP_SUB '-'
#define OP_MUL '*'
#define OP_DIV '/'

int eval(char* expr) {  
    if (*(expr++) != '(') {
        printf("Error: must begin with a '(' \n");
        return 0;
    }

    char* op = *(expr++); // read the operator

    return 0;
}

The first thing we do is to check that the first character is indeed a (. Note that it wouldn’t be a problem if we didn’t have, but we want to make things clean.

We first check the value of the current character of the string with *expr, and then we increment the pointer to the next character of the string. we could have done this using the expr++ statement, but instead we can shorten this by writing it *(expr++). Note that we have to put the ++ operator AFTER expr so the pointer is incremented AFTER evaluated by the if statement.

The same thing is happening just few lines after, when we read the operator from the expression. We assign the pointed value to op and only after we increment again the string pointer.

Next step is to test the operator, and compute the right operation on the following read items from the list. For now, an acceptable solution is to define a compute_XXXX function for each operation. As we spoke before, a list of addition operands cannot be read the same way as a list of division operands, for example.

int eval(char* expr) {  
    // ...

    int result = 0;
    switch (op) {
        case OP_ADD:
            result = compute_add(expr);
            break;
        default: break;
    }

    return result;
}

The compute_add function will implement a simple algorithm:

While the current character read is not a closing parenthesis, we keep reading.
If the current character is a space, we increment the pointer to the next character, and skip the rest of the loop. Otherwise, we read the current character as an integer, add it to the result, then move the pointer to the next character.

int compute_add(char* expr) {

    int sum = 0;

    while (*expr != ')') {
        if (*expr == ' ') {
            expr++; continue;
        }

        int m = 0;
        sscanf(expr++, "%d", &m);
        sum += m;
    }

    return sum;
}

The function used for calculating a product, called compute_product, will be nearly the same as the previous one, except that we’re computing a product.

int compute_add(char* expr) {

    int product = 1; // 1 is neutral for product

    while (*expr != ')') {
        if (*expr == ' ') {
            expr++; continue;
        }

        int m = 0;
        sscanf(expr++, "%d", &m);
        product *= m;
    }

    return product;
}

The division is a little tricker thing to implement, since it is not commutative, and we only need two operands in a particular order (the dividend and the divider). In practice, Lisp languages will allow multiple operands, computing nested divisions according to the list order. But for the sake of simplicity, let’s restrain ourselves to a two-operand basis division.

The algorithm is slightly different: we need to skip each blank character until we hit the first digit (the dividend), then do it a second time to find the second digit (the divider), and finally divide the two. To skip every space character, we can use a simple while loop that never exits until it find another character:

while (*expr == ' ') {  
    ++expr;
}

In a more concise form:

while (*(++expr) == ' ');  

The rest of the function is straightforward, and it gives us the following:

int compute_div(char* expr) {  
    int m = 0;
    int n = 0;

    while(*(++expr) == ' ');

    // first value found
    sscanf(expr, "%d", &m);
    ++expr;

    while(*(++expr) == ' ');

    // second value found
    sscanf(expr, "%d", &n);

    return m / n;
}

I leave it to you for the substraction function, which is very similar to the previous one. In the end, our eval function has been modified:

    switch (op) {
        case OP_ADD:
            result = compute_add(expr);
            break;
        case OP_MUL:
            result = compute_product(expr);
            break;
        case OP_DIV:
            result = compute_div(expr);
            break;
        default:
            result = 0; // undefined operation
            break;
    }

We’re almost done. The last thing is just a breeze, we want to print the computed result to the user.

int main(int argc, char* argv[]) {  
    while (1) {
        printf("-> %d", eval(read()));
    }

    return 0;
}

You can now compile and run the program! Try typing some expressions in it, like (+ 2 2 2), (/ 4 2 ) or (* 1 2 3 )