ECSGRT@lure.latrobe.edu.au (GEOFFREY TOBIN, ELECTRONIC ENGINEERING) (03/13/91)
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 Tobinvolpe@camelback.crd.ge.com (Christopher R Volpe) (03/13/91)
In article <5144@lure.latrobe.edu.au>, ECSGRT@lure.latrobe.edu.au (GEOFFREY TOBIN, ELECTRONIC ENGINEERING) writes: |>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) ();", ^^^^ If the return value is void, there's nothing there to cast. I think you meant: "typedef void *(*state)()". |>and cast the function return type, but I'd like to know whether ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ this wouldn't be strictly conforming. |>anyone can construct a 'state' type as in the "machine" function. |>---------------------------------------------------------------------- This came up a while ago and I posted a solution. I don't know if this is exactly what you want, but it's as close as I could come up with. You can take advantage of the self referential abilities of structs to do what you want with functions without any typecasts, although it is debatable whether or not the following is any less kludgy (it does compile under gcc, though): typedef struct somestruct { struct somestruct (*field)(); } fp; fp f1(),f2(); fp f1() { fp dummy; dummy.field=f2; return dummy; } fp f2() { fp dummy; dummy.field=f1; return dummy; } void statemachine() { fp (*current)(); current = f1; while((current = (current)().field) != NULL) ; } =================== Chris Volpe G.E. Corporate R&D volpecr@crd.ge.com
volpe@camelback.crd.ge.com (Christopher R Volpe) (03/13/91)
In article <17534@crdgw1.crd.ge.com>, I wrote: |>In article <5144@lure.latrobe.edu.au>, ECSGRT@lure.latrobe.edu.au |>(GEOFFREY TOBIN, ELECTRONIC ENGINEERING) writes: |>|>and cast the function return type, but I'd like to know whether |> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |> this wouldn't be strictly conforming. I think I was mistaken here. This should be strictly conforming, since you're casting it to the type of the function that you're invoking with it. Sorry. ================== Chris Volpe G.E. Corporate R&D volpecr@crd.ge.com
volpe@camelback.crd.ge.com (Christopher R Volpe) (03/13/91)
In article <17534@crdgw1.crd.ge.com>, I wrote |>In article <5144@lure.latrobe.edu.au>, ECSGRT@lure.latrobe.edu.au |>(GEOFFREY TOBIN, ELECTRONIC ENGINEERING) writes: |>|>One way *around* the problem is to use "typedef void (* state) ();", |> ^^^^ |>If the return value is void, there's nothing there to cast. I think |>you meant: "typedef void *(*state)()". Oops. One other thing I forgot. You wouldn't want to return a "void *" if you're planning on casting that to a function pointer. Pointers to void are not compatible with pointers to functions. You at least need it to return a generic function pointer of some sort. Perhaps something like: "typedef void (*(*state)())()". I.e., state is a pointer to a function that returns a vanilla function pointer. ("Vanilla function pointer" means "pointer to function of unspecified arguments that returns nothing", but this is irrelevant since it will be cast to the proper function pointer type before invoking.) ================== Chris Volpe G.E. Corporate R&D volpecr@crd.ge.com
gwyn@smoke.brl.mil (Doug Gwyn) (03/14/91)
In article <5144@lure.latrobe.edu.au> ECSGRT@lure.latrobe.edu.au (GEOFFREY TOBIN, ELECTRONIC ENGINEERING) writes: >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. A type along those general lines is the best that one can do, as C does not fully support recursive types. It does support some use of incomplete types in recursive declarations where a structure (for example) contains a pointer to its own type, but these escapes do not help for declaring such recursive functions as in this example. (The basic problem is that there is no way to declare an incomplete type for use in the declaration that completes the type.) What your colleague is seeking is eminently reasonable, but in C a small amount of kludgery is required in implementing the idea. Here is an example of how one can obtain the desired behavior: typedef void (*state)(void); #define end_state ((state)0) /* "end state" indicator */ ... extern state st_001(void); /* typical state implementation */ state start(void) { /* "start state" implementation */ ... return (state)st_001; } ... int main(void) { register state s; for (s = (state)start; s != end_state; ) s = (*(state (*)())s)(); /* first "*" is optional */ return 0; }
gwyn@smoke.brl.mil (Doug Gwyn) (03/14/91)
In article <15461@smoke.brl.mil> gwyn@smoke.brl.mil (Doug Gwyn) writes: >(The basic problem is that there is no way to declare an incomplete >type for use in the declaration that completes the type.) Actually, another posting showed how to do that using a structure containing the function pointer as a member. I didn't like that kludgery as much, since it involved extra use of temporaries, but it was an interesting example.