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.


 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!


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