www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Recursive typedef

reply Markus Dangl <danglm in.tum.de> writes:
Hello,

I'm trying to write a function like that:

typedef ParseFn function(char[] s) ParseFn;

i.E. a function that returns a pointer to a new function of equal type. 
DMD gives me the error "circular reference of typedef ParseFn". Of 
course i could be using a "void *" as return type, but there must be a 
better (typesafe) way... Has anyone tried this before?
Oct 05 2006
next sibling parent reply BCS <BCS pathlink.com> writes:
Markus Dangl wrote:
 Hello,
 
 I'm trying to write a function like that:
 
 typedef ParseFn function(char[] s) ParseFn;
 
 i.E. a function that returns a pointer to a new function of equal type. 
 DMD gives me the error "circular reference of typedef ParseFn". Of 
 course i could be using a "void *" as return type, but there must be a 
 better (typesafe) way... Has anyone tried this before?

yes, just last night (and a few months back) Going by way of void* is what I did for a function IIRC this works =typedef void* function() State; =State foo() { return cast(State)&foo; } delegate are a bit worse =struct state { state delegate() use; } = =struct sam ={ = state bar() = { = state ret; = ret.use = &this.bar; = return ret; = } =} But it does make for a cool state machine!!! State at = &seed; while(null !is at) at = cast(State)at(); or state at = &seed; while(null !is at.use) at = cast(state)at.use();
Oct 05 2006
parent reply Markus Dangl <danglm in.tum.de> writes:
BCS schrieb:
 But it does make for a cool state machine!!!
 
 State at = &seed;
 while(null !is at) at = cast(State)at();
 
 or
 
 state at = &seed;
 while(null !is at.use) at = cast(state)at.use();

That's exactly what i use it for - it's almost functional programming :)
Oct 05 2006
next sibling parent Markus Dangl <danglm in.tum.de> writes:
It works easily when i use classes (just as a workaround):

interface ParseFn
{
     ParseFn opCall(char[]);
}

class Example : ParseFn
{
     ParseFn opCall(char[] s)
     {
         if (s == "")
             return null;
         else
             return this;
     }
}

int main(char[][] args)
{
     ParseFn parser = new Example();
     while (parser !is null)
     {
         char[] s;
         s = din.readLine();
         parser = parser(s);
     }

     return 0;
}
Oct 05 2006
prev sibling parent reply BCS <BCS pathlink.com> writes:
Markus Dangl wrote:
 BCS schrieb:
 
 But it does make for a cool state machine!!!

 State at = &seed;
 while(null !is at) at = cast(State)at();

 or

 state at = &seed;
 while(null !is at.use) at = cast(state)at.use();

That's exactly what i use it for - it's almost functional programming :)

One interesting things about the delegate form is that it can be used to make an *infinite* state machine. struct state { state delegate(Stream) next; } struct nest { nest* root; state scan(Stream ins) { nest* tmp; state ret; if(ins.eof && root !is null) throw new Error("invalid"); switch(ins.getc) { case '{': tmp = new nest; tmp.root = this; ret.next = &tmp.scan; return ret; case '}': if(root is null) throw new Error("invalid"); ret.next = &root.scan; return ret; default: ret.next = &this.scan; return ret; } } }
Oct 05 2006
parent reply Markus Dangl <danglm in.tum.de> writes:
BCS schrieb:
 One interesting things about the delegate form is that it can be used to 
 make an *infinite* state machine.

So, in principle you are using a stack, the current struct "nest" is your top of the stack, "{" leads to pushing a new element on the top, "}" pops the top element and returns the execution of the previous state machine. In theory, such a machine is infinite, but as you're limited by your computer's memory anyway you might as well use a "size_t" and count the parens directly ;) But the functional style just looks cool and it's very flexible!
Oct 05 2006
parent BCS <nothing pathlink.com> writes:
== Quote from Markus Dangl (danglm in.tum.de)'s article
 BCS schrieb:
 One interesting things about the delegate form is that it can be
 used to make an *infinite* state machine.

your top of the stack, "{" leads to pushing a new element on the top, "}" pops the top element and returns the execution of the previous state machine. In theory, such a machine is infinite, but as you're limited by your computer's memory anyway you might as well use a "size_t" and count the parens directly ;) But the functional style just looks cool and it's very flexible!

Oh yah is it flexable. Add a few more types of nesting {}, (), [] <>, <%%> or maby have it behave differently inside of "{(<" than inside of "{<[". But that is just getting silly.
Oct 05 2006
prev sibling parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Markus Dangl wrote:

 but there must be a better (typesafe) way... Has
 anyone tried this before? 

If your approach would be possible, then also recursive types as formal parameters of functions would be possible. I tried for the latter case, but that was out of academic interest only. It did not work and I investigated that no further. I do believe that there cannot be a typesafe way to define a type that is recursive in itself, but I have not tried to prove that.
Oct 05 2006
parent Markus Dangl <danglm in.tum.de> writes:
Karen Lanrap schrieb:
 I do believe that there cannot be a typesafe way to define a type 
 that is recursive in itself, but I have not tried to prove that.
 

I think i remember something similar about recursive function types from one of my lectures... ("a->b->a" is not possible because "(a=>b)=>a" cannot be proven or sth like that) But this is a workaround: --- interface ParseFn { ParseFn opCall(char[]); } --- I don't really understand why this makes such a big difference for the type system, because it seems really equivalent.
Oct 05 2006