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

[Eric des Courtis]

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

 

[Ben Pfaff]

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

 

[Eric des Courtis]

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 1utchar(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

 

[Ben Pfaff]

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.

 

[Walter Roberson]

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.

 

[Eric des Courtis]

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. 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]

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.

Eric des Courtis

 

[Ben Pfaff]

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.

 

[Eric des Courtis]

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.

That's not a bad idea.

Eric

 

[Eric des Courtis]

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

 

[Lowell Gilbert]

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