Re: mutually-recursive types and an old puzzle

[llewelly at xmission dot com]

Joe Buck <Joe.Buck@synopsys.COM> writes:

> 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?

I don't know. But something similar can be represented in C++: see:

http://www.gotw.ca/gotw/057.htm