mutually-recursive types and an old puzzle

[Joe Buck <Joe dot Buck at synopsys dot COM>]

Richard Kenner's message about tree walking and mutually-recursive types
reminded me of an old puzzle, posed about 20 years ago by Chris Torek,
if I remember right.

The idea is to consider a representation of finite state machines based
on pointers to functions.  Let's assume, for C, that we have some
typedef called T to be filled in later.  Now, consider a simple two-state
FSM that switches state for an input of 1, and stays in the same state
for an input of 0.

We might consider writing this as

T state_0(int input) {
	return input ? &state_1 : &state_0;
}

T state_1(int input) {
	return input ? &state_0 : &state_1;
}

void driver() {
	int input;
	T state = &state_0;     
	while (1) {
		input = read_next_input();
		state = (*state)(input);
	}
}

and clearly this is extensible to more complex FSM's.  The key is
that we represent a state as the address of the next-state function
for that state.  I think this was based on a technique for fast
FSM's in assembly language that Chris had used.

OK, here's the problem: how should we define T?  It seems that T must be
the same type as "pointer to function returning T" (this was the K&R days,
where you could ignore the type of the argument list, but that doesn't
really change the puzzle any).  That is,

pointer to function returning pointer to function returning pointer to ...

It's a recursive type, and so cannot be declared in C.  As I recall,
people proposed various workarounds that relied on casts to allow this
sort of coding style.  Example: if we assume all pointers to functions
have the same representation, we can define T as a different pointer
to function type, and add some reinterpret_casts to make things come
out right.

Now, to try to make this little distraction relevant:

1) can this kind of thing be represented in Ada?
2) can this kind of thing be represented in GIMPLE?