State Machines

I've been enthralled with state machines lately. It's become unhealthy. I don't remember if it started by playing around with lex and yacc, or if it was when I found Mongrel2 and read this post. But from that point on, I've been obsessed with finite state machines, parsers, regular expressions.

Recently, when after a stack overflow question pushed me into hand coding another state machine based parser, I read this blog post, which introduced a method of implementing state machines that I hadn't seen before. I'm sure it's not new. In fact it probably dates back to the era of machine code. But it was new to me, and I like it better than tables or nested conditionals. The basic idea is to break out the code for each state into its own function and then use a function pointer to track the state instead of an enum and switch.

Of course, I couldn't leave well enough alone. I thought I could do one better if I returned the new function pointer instead of storing it in a reference parameter. As it happens, C is a little funny about returning a pointer to a function with the same signature as the function doing the returning... something to do with infinitely recursive type definitions I guess. So the best I could come up with was a struct containing just the function pointer. That doesn't add too much syntactically when calling the functions, and modern compilers optimize it to just returning the function pointer in a register, but returning them becomes a little more unwieldy. You either need to define const structs somewhere (which is no better than enums), declare and define a local struct to be returned (more lines in each function), or restrict to C99 and use compound literals. If you can think of a better way to tackle this, please let me know. Here is how those three look in code.

typedef struct _state state;
struct _state
{
    state (*func)(char);
};

state init(char);
state final(char);

#if CONST
const state INIT = {init};
const state FINAL = {final};
#endif

state
init(char input)
{
#if LOCAL
    state next;
#endif

    switch(input)
    {
#if CONST

    case 'a':
        return FINAL;
    default:
        return INIT;

#elif LOCAL

    case 'a':
        next.func = final;
        return next;
    default:
        next.func = init;
        return next;

#elif C99

    case 'a':
        return (state){final};
    default:
        return (state){init};

#endif;
    }
}

Here's an example of a simple rpn calculator. I decided to go the route of using const structs, even though it pollutes the global namespace. I did this mainly because it maintains C89 compatibility while requiring less typing than locals or the original design of saving to a reference parameter.

#include <stdio.h>
#include <stack.h>

typedef struct state_ state;

struct state_
{
    state (*func)(char);
};

state initial(char);
state number(char);

const state INITIAL = {initial};
const state NUMBER = {number};
const state END;

state
initial(char input)
{
    int a;

    if(input == 'p')
    {
        printf("%i\n", pop());
        return INITIAL;
    }
    else if(input == '+')
    {
        a = pop();
        *top() += a;
        return INITIAL;
    }
    else if(input == '*')
    {
        a = pop();
        *top() *= a;
        return INITIAL;
    }
    else if(input >= '0' && input <= '9')
    {
        ungetc(input, stdin);
        push(0);
        return NUMBER;
    }
    else
    {
        return END;
    }
}

state
number(char input)
{
    if(input >= '0' && input <= '9')
    {
        *top() *= 10;
        *top() += input - '0';
        return NUMBER;
    }
    else
    {
        ungetc(input, stdin);
        return INITIAL;
    }
}

int
main(void)
{
    int ch;
    state s = INITIAL;

    while((ch = getchar()) != EOF && s.func)
    {
        s = s.func(ch);
    }

    return 0;
}