Recursive function pointer type. How?

[GEOFFREY TOBIN, ELECTRONIC ENGINEERING]

Dear C experts,

A colleague posted the following request to aus.wanted.  I suggested
comp.lang.c, but as it hasn't (at my time of writing this) appeared
there, and as I'm also curious, I've taken the liberty to pass it on.
To get around copyright (:-), I've paraphrased parts of it.
(This also gives me the opportunity to claim that all mis-statements
herein are my own, not his.  Thus I can flame back, if I wish!)
Here goes.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
For a model of a small finite state machine, I want an ANSI C
definition for a type to be called 'state', which is a pointer to a
function returning type 'state'.

Conceptually, and in skeleton form:

	#include <stdio.h>
	typedef state (*state)();  /* Wrong, but conveys the intent */

	void
	machine (state s)
	{
		while (s != NULL)
			s = (*s)();  /* This is what we want */
	}

So each state in the machine is a function pointer.  The pointed-to
function performs some action, then returns the next state.

One way *around* the problem is to use "typedef void (* state) ();",
and cast the function return type, but I'd like to know whether
anyone can construct a 'state' type as in the "machine" function.
----------------------------------------------------------------------

I emailed him to ask why he didn't use data structures instead of
functions, to represent states, as this would allow the dynamic
creation of states.  He basically said no, the function idea is neater.
He added that each state's function prompts for, and reads, user
input to direct it to the next state.  (I reckon a switch statement
in a single next_state() function would suffice for a small FSM.
What do others recommend?)  I've had a glance at the "Dragon" book,
but I don't see anything in there that would satisfy our colleague's
firm request.

I also informed him that his type specification was circular, and that
there was necessarily either no such (non-vacuous) type or many.
He didn't appreciate this answer.  :-)

How many non-vacuous types in C satisfy our colleague's recursion?

I began to reflect on C's (usual) recursively-defined types.
On Vax/VMS 5.3, Vax C 3.1 accepts (without warnings):

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
typedef void * VP;          /* VP is an "undifferentiated" type */
typedef enum E * EP;        /* This isn't going to be recursive */
typedef struct S * SP;      /* But this is */
typedef union U * UP;       /* Ditto */

/* LATER, or in another source file, or nowhere: -) */

enum E {asparagus_ferns, benzene_rings, custard_apples, durians};
struct S {int apricot_seeds; float fairy_floss; SP superfluities;};
union U {unsigned int uglification; double bass; UP up_and_away;};
----------------------------------------------------------------------

It's interesting that C's approach to recursive types "resolves"
their specifications "by name".  By this I mean that:

	struct Y {struct Y * next;};
and
	struct Z {struct Z * next;};

have the same form, but are considered distinct types.
As we know, this is good for distinguishing similar implementations
(models) of logically unrelated ideas.

Hmm...the earlier (enum, struct, union) _pointer_ definitions are just
as circular (and "unresolved") as...

	typedef A * AP;
	/* Define A later, or in another file, or nowhere */

What our colleague wants is conceptually equivalent to:

	typedef F * FP;
	typedef FP  F();

I know that C is (read: "Ritchie, ANSI, et al, are") not arbitrary.
(Insert 1 pt smiley here.)  But C is non-uniform.  (And this fact
seems to be getting in our colleague's way - and mine, now. :-)

The prior pointer-typedefs that are accepted are those that use the
keywords "enum", "struct", and "union".  There are no other keywords
in C that share their syntax.  (Asbestos donned - too late, I fear.)

So, counterfactually speaking, if C had the reserved word "fun",
perhaps we could then write:

	typedef fun F * FP;
        /* Later, or in another file, or never: */
	FP fun F ();

or some other thing that would correspond to what we can already do
with structs and unions.

Come to think of it, *is* there any fundamental reason why a C-like
language could not accept

	typedef W (* W) ();
	typedef X (* X) ();

etc. as typedefs of legitimate types?

Our colleague wasn't satisfied with hypotheticals, as he had a client
waiting.  Also, for some reason, the moderators of comp.language.utopian
and sci.math.logic.of.comp.languages wouldn't accept my posting.

So, to return to the present reality, does any C programmer know how
to implement

	s = (*s)();

?  T'would be "jus t'elegant".

Yours sincerely,
Geoffrey Tobin