New implementation of FSM using functions returning pointers tofunctions of the same type!

Discussion in 'C Programming' started by Eric des Courtis, Mar 10, 2008.

  1. Hi Everyone,

    Before I go into details I would like to thank Svillen Ranev my
    professor for solving the "How to define, declare and call a function
    returning function pointers of the same type?" question I had asked in
    the context of my compilers class.

    The problem is this:
    a function foo
    foo()
    taking as parameter a char
    foo(char)
    returning a pointer
    *foo(char)
    to a function (of the same type)
    (*foo(char))()
    taking char
    (*foo(char))(char)
    returning a pointer
    *(*foo(char))(char)
    to a function
    (*(*foo(char))(char))()
    taking char
    (*(*foo(char))(char))(char)
    and so on.....
    This goes on forever.

    It can be solved by simply recursing once and stopping there.
    Naturally this generates a warning and usually the C compiler will
    assume a int return type for the last return type effectively breaking
    the recursion. To void warnings heavy casting is required, technically
    speaking the compiler only need to correctly resolve the first return
    type in order to generate valid output code.

    So how does one make a finite state machine using this?
    Like this... (This source is also available on my home machine at
    http://clockwork.no-ip.org/ericdevice3.c)

    /* This is a sample of Eric's device (Finite Automaton
    Implementation)
    * Copyright (C) 2008 Eric des courtis
    *
    * This program is free software: you can redistribute it and/or
    modify
    * it under the terms of the GNU General Public License as published
    by
    * the Free Software Foundation, either version 2 of the License, or
    * (at your option) any later version.
    *
    * This program is distributed in the hope that it will be useful,
    * but WITHOUT ANY WARRANTY; without even the implied warranty of
    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    * GNU General Public License for more details.
    *
    * You should have received a copy of the GNU General Public License
    * along with this program. If not, see <http://www.gnu.org/licenses/
    >.

    */

    #include <stdio.h>
    #include <stdlib.h>

    #define NOAS 0
    #define ASWR 1
    #define ASNR 2

    #define EOS '\0'
    #define CRLF '\n'

    #define NO_TOKEN 0
    #define HELLO_TOKEN 1
    #define BOB_TOKEN 2
    #define NUMBER_TOKEN 3
    #define ERROR_TOKEN 4

    /* For casting */
    #define SFP(a) ((void *(*(*)(char))(char))a)
    #define STP(a) ((void *(*(*(*)(char))(char))(char))a)

    /* For definition and declaration */
    #define SF(f,t,v) void *(*(*f(t v))(t))(t)
    #define PSF(n,t) void *(*(*(*n)(t))(t))(t);

    struct token{
    int type;
    } tok;

    static int acceptstate = NOAS;

    static SF(state0, char,);
    static SF(state1, char,);
    static SF(state2, char,);
    static SF(state3, char,);
    static SF(state4, char,);
    static SF(state5, char,);
    static SF(state6, char,);
    static SF(state7, char,);
    static SF(state8, char,);
    static SF(state9, char,);
    static SF(error_state, char,);

    static PSF(state, char);

    int main(void)
    {
    char c = 0;
    static char *token_name[] = {
    "NO TOKEN?",
    "HELLO TOKEN",
    "BOB TOKEN",
    "NUMBER TOKEN",
    "ERROR TOKEN"
    };

    printf("Eric's device Example Copyright (C) 2008 Eric des Courtis\n"
    "This program comes with ABSOLUTELY NO WARRANTY.\n"
    "This is free software, and you are welcome to redistribute it
    \n"
    "under certain conditions.\n");


    tok.type = NO_TOKEN;
    state = state0;

    do{
    do{
    if(acceptstate != ASWR){
    c = (char)getchar();
    if(c == CRLF) continue;
    }
    state = STP(state(c));
    }while(acceptstate == NOAS);
    printf("%s found\n", token_name[tok.type]);
    }while(c != EOS && c != EOF);

    return 0;
    }

    static SF(state0, char, a)
    {
    acceptstate = NOAS;
    switch(a){
    case 'h':
    return SFP(state1);
    case 'b':
    return SFP(state6);
    }
    if(a >= '0' && a <= '9')
    return SFP(state9);
    return SFP(error_state);
    }

    static SF(state1, char, a)
    {
    acceptstate = NOAS;
    if(a == 'e')
    return SFP(state2);
    return SFP(error_state);
    }

    static SF(state2, char, a)
    {
    acceptstate = NOAS;
    if(a == 'l')
    return SFP(state3);
    return SFP(error_state);
    }

    static SF(state3, char, a)
    {
    acceptstate = NOAS;
    if(a == 'l')
    return SFP(state4);
    return SFP(error_state);
    }

    static SF(state4, char, a)
    {
    acceptstate = NOAS;
    if(a == 'o')
    return SFP(state5);
    return SFP(error_state);
    }

    static SF(state5, char, a)
    {
    acceptstate = ASWR;
    tok.type = HELLO_TOKEN;
    return SFP(state0);
    }

    static SF(state6, char, a)
    {
    acceptstate = NOAS;
    if(a == 'o')
    return SFP(state7);
    return SFP(error_state);
    }

    static SF(state7, char, a)
    {
    acceptstate = NOAS;
    if(a == 'b')
    return SFP(state8);
    return SFP(error_state);
    }

    static SF(state8, char, a)
    {
    acceptstate = ASWR;
    tok.type = BOB_TOKEN;
    return SFP(state0);
    }

    static SF(state9, char, a)
    {
    acceptstate = NOAS;
    if(a >= '0' && a <= '9')
    return SFP(state9);

    acceptstate = ASWR;
    tok.type = NUMBER_TOKEN;
    return SFP(state0);
    }

    static SF(error_state, char, a)
    {
    acceptstate = ASWR;
    tok.type = ERROR_TOKEN;
    return SFP(state0);
    }

    I decided to call this thing Eric's Device!

    Cheers!

    Eric des Courtis
    Eric des Courtis, Mar 10, 2008
    #1
    1. Advertising

  2. Eric des Courtis

    Ben Pfaff Guest

    Re: New implementation of FSM using functions returning pointers to functions of the same type!

    Eric des Courtis <> writes:

    > So how does one make a finite state machine using this?


    This is in the FAQ.

    1.22: How can I declare a function that can return a pointer to a
    function of the same type? I'm building a state machine with
    one function for each state, each of which returns a pointer to
    the function for the next state. But I can't find a way to
    declare the functions.

    A: You can't quite do it directly. Either have the function return
    a generic function pointer, with some judicious casts to adjust
    the types as the pointers are passed around; or have it return a
    structure containing only a pointer to a function returning that
    structure.

    More details at: http://c-faq.com/decl/recurfuncp.html
    --
    char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
    =b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
    2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
    Ben Pfaff, Mar 10, 2008
    #2
    1. Advertising

  3. On Mar 10, 1:53 pm, Ben Pfaff <> wrote:
    > Eric des Courtis <> writes:
    >
    > > So how does one make a finite state machine using this?

    >
    > This is in the FAQ.
    >
    > 1.22: How can I declare a function that can return a pointer to a
    > function of the same type? I'm building a state machine with
    > one function for each state, each of which returns a pointer to
    > the function for the next state. But I can't find a way to
    > declare the functions.
    >
    > A: You can't quite do it directly. Either have the function return
    > a generic function pointer, with some judicious casts to adjust
    > the types as the pointers are passed around; or have it return a
    > structure containing only a pointer to a function returning that
    > structure.
    >
    > More details at:http://c-faq.com/decl/recurfuncp.html
    > --
    > char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    > ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
    > =b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
    > 2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}


    Thanks I did not know it existed!

    It looks like a dirty hack in any case. The function does not really
    return int!!! So why doesn't the C language allow you to simply
    declare a function returning a pointer to a function of the same type?
    For example a function of type (*(*f())())() can only return itself it
    does not make sense to have to return int to break the recursion!
    While K&R doesn't go into that amount of detail I think it is one of
    the most fundamental flaws of the C language and/or C compilers.

    Does anyone think that (*(*f())())() does not fully describe this
    function? After all this type of function cannot return anything else
    then a pointer to itself!

    Is this a flaw of the language or one of the implementation of C
    compilers?

    Eric des Courtis
    Eric des Courtis, Mar 10, 2008
    #3
  4. Eric des Courtis

    Ben Pfaff Guest

    Re: New implementation of FSM using functions returning pointers to functions of the same type!

    Eric des Courtis <> writes:

    > It looks like a dirty hack in any case. The function does not really
    > return int!!! So why doesn't the C language allow you to simply
    > declare a function returning a pointer to a function of the same type?


    Probably because it's not a very important use case. In cases
    where you want to do it, you can use one of the available
    workarounds.
    --
    Ben Pfaff
    http://benpfaff.org
    Ben Pfaff, Mar 10, 2008
    #4
  5. In article <>,
    Eric des Courtis <> wrote:

    >Does anyone think that (*(*f())())() does not fully describe this
    >function? After all this type of function cannot return anything else
    >then a pointer to itself!


    In finite state work, it could easily return a pointer to a
    -different- function of the same general class.

    Or declarations of that variety could be used with pseudo
    co-routines.
    --
    "Tired minds don't plan well. Sleep first, plan later."
    -- Walter Reisch
    Walter Roberson, Mar 10, 2008
    #5
  6. On Mar 10, 2:44 pm, Ben Pfaff <> wrote:
    > Eric des Courtis <> writes:
    >
    > > It looks like a dirty hack in any case. The function does not really
    > > return int!!! So why doesn't the C language allow you to simply
    > > declare a function returning a pointer to a function of the same type?

    >
    > Probably because it's not a very important use case. In cases
    > where you want to do it, you can use one of the available
    > workarounds.
    > --
    > Ben Pfaffhttp://benpfaff.org


    You are probably right, still it would be nice to see gcc compile this
    without hacks or errors. This is my first time posting on comp.lang.c
    I wish I would of known about this sooner.

    I guess my program is yet another work around, if this variant doesn't
    already exist.

    Eric des Courtis
    Eric des Courtis, Mar 10, 2008
    #6
  7. On Mar 10, 2:57 pm, -cnrc.gc.ca (Walter Roberson)
    wrote:
    > In article <>,
    > Eric des Courtis <> wrote:
    >
    > >Does anyone think that (*(*f())())() does not fully describe this
    > >function? After all this type of function cannot return anything else
    > >then a pointer to itself!

    >
    > In finite state work, it could easily return a pointer to a
    > -different- function of the same general class.

    You are correct what I meant was "After all this type of function
    cannot return anything else then a pointer to its own type!" rather
    then "After all this type of function cannot return anything else then
    a pointer to itself!"
    >
    > Or declarations of that variety could be used with pseudo
    > co-routines.

    Agreed.
    > --
    > "Tired minds don't plan well. Sleep first, plan later."
    > -- Walter Reisch


    Eric des Courtis
    Eric des Courtis, Mar 10, 2008
    #7
  8. Eric des Courtis

    Ben Pfaff Guest

    Re: New implementation of FSM using functions returning pointers to functions of the same type!

    Eric des Courtis <> writes:

    > On Mar 10, 2:44 pm, Ben Pfaff <> wrote:
    >> Eric des Courtis <> writes:
    >>
    >> > It looks like a dirty hack in any case. The function does not really
    >> > return int!!! So why doesn't the C language allow you to simply
    >> > declare a function returning a pointer to a function of the same type?

    >>
    >> Probably because it's not a very important use case. In cases
    >> where you want to do it, you can use one of the available
    >> workarounds.

    >
    > You are probably right, still it would be nice to see gcc compile this
    > without hacks or errors. [...]


    It's not a matter of simply making C accept such a construct,
    because there is no syntax to express a recursive function type
    in C. You would first have to invent a syntax for it. What
    syntax do you have in mind? Perhaps you could implement support
    for it in GCC yourself; after all, GCC source code is freely
    available.
    --
    "It wouldn't be a new C standard if it didn't give a
    new meaning to the word `static'."
    --Peter Seebach on C99
    Ben Pfaff, Mar 10, 2008
    #8
  9. On Mar 10, 7:21 pm, Ben Pfaff <> wrote:
    > Eric des Courtis <> writes:
    >
    > > On Mar 10, 2:44 pm, Ben Pfaff <> wrote:
    > >> Eric des Courtis <> writes:

    >
    > >> > It looks like a dirty hack in any case. The function does not really
    > >> > return int!!! So why doesn't the C language allow you to simply
    > >> > declare a function returning a pointer to a function of the same type?

    >
    > >> Probably because it's not a very important use case. In cases
    > >> where you want to do it, you can use one of the available
    > >> workarounds.

    >
    > > You are probably right, still it would be nice to see gcc compile this
    > > without hacks or errors. [...]

    >
    > It's not a matter of simply making C accept such a construct,
    > because there is no syntax to express a recursive function type
    > in C. You would first have to invent a syntax for it. What
    > syntax do you have in mind? Perhaps you could implement support
    > for it in GCC yourself; after all, GCC source code is freely
    > available.
    > --
    > "It wouldn't be a new C standard if it didn't give a
    > new meaning to the word `static'."
    > --Peter Seebach on C99


    That's not a bad idea.

    Eric
    Eric des Courtis, Mar 11, 2008
    #9
  10. On Mar 10, 7:21 pm, Ben Pfaff <> wrote:
    > Eric des Courtis <> writes:
    >
    > > On Mar 10, 2:44 pm, Ben Pfaff <> wrote:
    > >> Eric des Courtis <> writes:

    >
    > >> > It looks like a dirty hack in any case. The function does not really
    > >> > return int!!! So why doesn't the C language allow you to simply
    > >> > declare a function returning a pointer to a function of the same type?

    >
    > >> Probably because it's not a very important use case. In cases
    > >> where you want to do it, you can use one of the available
    > >> workarounds.

    >
    > > You are probably right, still it would be nice to see gcc compile this
    > > without hacks or errors. [...]

    >
    > It's not a matter of simply making C accept such a construct,
    > because there is no syntax to express a recursive function type
    > in C. You would first have to invent a syntax for it. What
    > syntax do you have in mind? Perhaps you could implement support
    > for it in GCC yourself; after all, GCC source code is freely
    > available.

    How about not changing the syntax but handling the exception in the
    compiler?
    In other words (*(*f())())() does not assume an int return type. It
    assumes the return type of a function that returns a function pointer
    of the same type OR it could ignore the return type after it recurses
    once on the return value.

    Eric

    > --
    > "It wouldn't be a new C standard if it didn't give a
    > new meaning to the word `static'."
    > --Peter Seebach on C99
    Eric des Courtis, Mar 11, 2008
    #10
  11. Re: New implementation of FSM using functions returning pointers to functions of the same type!

    Ben Pfaff <> writes:

    > Eric des Courtis <> writes:
    >
    >> It looks like a dirty hack in any case. The function does not really
    >> return int!!! So why doesn't the C language allow you to simply
    >> declare a function returning a pointer to a function of the same type?

    >
    > Probably because it's not a very important use case. In cases
    > where you want to do it, you can use one of the available
    > workarounds.


    Perhaps more to the point, the reason it isn't a very important case
    is that an FSM routine usually needs to pass around the FSM's internal
    state as well, which requires the separate structure anyway. So the
    usual "workaround" is more appropriate.

    That's my own experience, anyway...
    Lowell Gilbert, Mar 11, 2008
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Carl Cerecke
    Replies:
    2
    Views:
    831
    Carl Cerecke
    Jan 25, 2006
  2. Polomora

    Nested FSM implementation

    Polomora, Aug 21, 2006, in forum: C Programming
    Replies:
    6
    Views:
    408
    EventHelix.com
    Sep 9, 2006
  3. WittyGuy

    FSM implementation

    WittyGuy, Jul 12, 2005, in forum: C++
    Replies:
    3
    Views:
    467
    WittyGuy
    Aug 4, 2005
  4. Replies:
    2
    Views:
    537
  5. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    667
Loading...

Share This Page