www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Yield from function?

reply Profile Anaysis <PA gotacha.com> writes:
I need to yield from a complex recursive function too allow 
visualizing what it is doing.

e.g., if it is a tree searching algorithm, I'd like to yield for 
each node so that the current state can be shown visually.

I realize that there are several ways to do this but D a yield 
version without additional threads would be optimal. I don't need 
concurrency or speed, just simple.
Jan 30 2017
next sibling parent pineapple <meapineapple gmail.com> writes:
On Monday, 30 January 2017 at 11:03:52 UTC, Profile Anaysis wrote:

 I need to yield from a complex recursive function too allow 
 visualizing what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield 
 for each node so that the current state can be shown visually.

 I realize that there are several ways to do this but D a yield 
 version without additional threads would be optimal. I don't 
 need concurrency or speed, just simple.


You may be able to use Generator in std.concurrency for this: 
https://dlang.org/phobos/std_concurrency.html#.Generator

You could also rephrase your algorithm as a range, which would 
not involve concurrency but may be unintuitive to implement. In 
this case you would likely have to use a stack or queue rather 
than a recursive function.

Is it an option to just accumulate the information regarding your 
algorithm in a separate data structure and then analyze it after 
the algorithm is complete, or has recorded some number of entries?
Jan 30 2017
prev sibling next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/30/2017 03:03 AM, Profile Anaysis wrote:

 I need to yield from a complex recursive function too allow visualizing
 what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield for each
 node so that the current state can be shown visually.


I used tree iteration as a Generator example here:

   http://ddili.org/ders/d.en/fibers.html

It's in the code where the function 'byNode' appears. (The example 
builds on an earlier tree iteration code in the same chapter.)

Ali
Jan 30 2017
next sibling parent reply cym13 <cpicard openmailbox.org> writes:
On Monday, 30 January 2017 at 18:48:10 UTC, Ali Çehreli wrote:

 On 01/30/2017 03:03 AM, Profile Anaysis wrote:

 I need to yield from a complex recursive function too allow


 visualizing

 what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield


 for each

 node so that the current state can be shown visually.


 I used tree iteration as a Generator example here:

   http://ddili.org/ders/d.en/fibers.html

 It's in the code where the function 'byNode' appears. (The 
 example builds on an earlier tree iteration code in the same 
 chapter.)

 Ali


BTW the alias to avoid a name conflic on "Generator" isn't 
necessary anymore with the last version of phobos (as shipped 
with DMDv2.073.0). However it's still conflicting with the latest 
version of LDC available on my system (1.0.0, based on 
DMDv2.070.2) so maybe letting it be in the example a bit longer 
is appropriate. Otherwise I believe you'll agree that removing it 
would make it easier for the beginners.
Jan 30 2017
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/30/2017 02:04 PM, cym13 wrote:

 On Monday, 30 January 2017 at 18:48:10 UTC, Ali Çehreli wrote:



   http://ddili.org/ders/d.en/fibers.html





 BTW the alias to avoid a name conflic on "Generator" isn't necessary
 anymore [...] Otherwise I believe you'll agree
 that removing it would make it easier for the beginners.


Thanks for letting me know. I can't update the book to 2.073 for other 
reasons like some changes made to ddoc anyway. :-/ (And 'scope' function 
parameter, etc.)

Ali
Jan 30 2017
prev sibling parent reply Profile Anaysis <PA gotacha.com> writes:
On Monday, 30 January 2017 at 18:48:10 UTC, Ali Çehreli wrote:

 On 01/30/2017 03:03 AM, Profile Anaysis wrote:

 I need to yield from a complex recursive function too allow


 visualizing

 what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield


 for each

 node so that the current state can be shown visually.


 I used tree iteration as a Generator example here:

   http://ddili.org/ders/d.en/fibers.html

 It's in the code where the function 'byNode' appears. (The 
 example builds on an earlier tree iteration code in the same 
 chapter.)

 Ali


I tried your lambda based fib example and it works as 
expected(using a function)

But when I try the class version it crashes without a call stack 
or any info(somewhere in the fiber module and an access 
violation).

import std.stdio, std.concurrency, core.thread;

class Search : Fiber
{
     this() { super(&start); }
     int res = 0;
     void start()
     {			
	Fiber.yield();
         res = 1;
     }
}

void main()
{

	auto search = new Search();

	search.call(); writeln(search.res);
	search.call(); writeln(search.res);
	search.call(); writeln(search.res); // crashes after 3rd 
call(first two work fine)
}


Any ideas what why it is crashing like this?
Jan 30 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/30/2017 08:12 PM, Profile Anaysis wrote:

 import std.stdio, std.concurrency, core.thread;

 class Search : Fiber
 {
     this() { super(&start); }
     int res = 0;
     void start()
     {
     Fiber.yield();
         res = 1;
     }
 }

 void main()
 {

     auto search = new Search();

     search.call(); writeln(search.res);
     search.call(); writeln(search.res);
     search.call(); writeln(search.res); // crashes after 3rd call(first
 two work fine)
 }


That's because the fiber is not in a callable state. (You can check with 
search.state.) Here is one where the fiber function lives (too) long:

import std.stdio, std.concurrency, core.thread;

class Search : Fiber
{
     this() { super(&start); }
     int res = 0;
     void start() {
         while (true) {
             Fiber.yield();
             ++res;
         }
     }
}

void main()
{
     auto search = new Search();

     foreach (i; 0 .. 5) {
         search.call();
         writeln(search.res);
     }
}

Ali
Jan 30 2017
next sibling parent Profile Anaysis <PA gotacha.com> writes:
On Tuesday, 31 January 2017 at 06:32:02 UTC, Ali Çehreli wrote:

 On 01/30/2017 08:12 PM, Profile Anaysis wrote:

 [...]


 That's because the fiber is not in a callable state. (You can 
 check with search.state.) Here is one where the fiber function 
 lives (too) long:

 import std.stdio, std.concurrency, core.thread;

 class Search : Fiber
 {
     this() { super(&start); }
     int res = 0;
     void start() {
         while (true) {
             Fiber.yield();
             ++res;
         }
     }
 }

 void main()
 {
     auto search = new Search();

     foreach (i; 0 .. 5) {
         search.call();
         writeln(search.res);
     }
 }

 Ali


Thanks.
Jan 31 2017
prev sibling parent reply Profile Anaysis <PA gotacha.com> writes:
On Tuesday, 31 January 2017 at 06:32:02 UTC, Ali Çehreli wrote:

 On 01/30/2017 08:12 PM, Profile Anaysis wrote:

 import std.stdio, std.concurrency, core.thread;

 class Search : Fiber
 {
     this() { super(&start); }
     int res = 0;
     void start()
     {
     Fiber.yield();
         res = 1;
     }
 }

 void main()
 {

     auto search = new Search();

     search.call(); writeln(search.res);
     search.call(); writeln(search.res);
     search.call(); writeln(search.res); // crashes after 3rd 
 call(first
 two work fine)
 }


 That's because the fiber is not in a callable state. (You can 
 check with search.state.) Here is one where the fiber function 
 lives (too) long:

 import std.stdio, std.concurrency, core.thread;

 class Search : Fiber
 {
     this() { super(&start); }
     int res = 0;
     void start() {
         while (true) {
             Fiber.yield();
             ++res;
         }
     }
 }

 void main()
 {
     auto search = new Search();

     foreach (i; 0 .. 5) {
         search.call();
         writeln(search.res);
     }
 }

 Ali


Just curious, how can I use start() recursively?

I would like to iterate over a recursive structure and yield for 
each "solution". I could use a stack to store the values but the 
whole point of the fiber was to avoid that.


void start() {
    while (true) {
       Fiber.yield();
       ++res;
    }
}


Seems I can't create start with a parameter and non-void return 
type. This seems to make it about useless to use a fiber 
recursively because no pushing and popping on the stack occur.

class Search : Fiber
{
     this() { super(&start); }
     bool End = false;

     int res = 0;

     void start() {
         while (!End) 		
		{
			
			int Foo(int x)
			{
				Fiber.yield();
				if (x < 10)
				{
					res = Foo(x++);
					return res;
				}
				else
					return x;
				
			}
			
			
         }
     }


void main()
{

	auto search = new Search();
	foreach (i; 0 .. 5)
	{
          search.call();
          writeln(search.res);
	}


	search.End = true;
}


My goal is simple, to yield a solution at each step in the 
recursive process.

Maybe I can use another fiber using the lambda syntax?
Jan 31 2017
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/31/2017 03:00 AM, Profile Anaysis wrote:


 Just curious, how can I use start() recursively?


[...]

 Seems I can't create start with a parameter and non-void return type.


Options:

- The class can maintain state

- You can start the fiber with a delegate;

     int local;
     double state;
     () => foo(local, state)

Other than the entry point, there is no requirement in what you can do. 
The following code yields inside a recursive function:

import std.stdio, std.concurrency, core.thread;

class Search : Fiber
{
     int state;

     this(int state) {
         this.state = state;
         super(&start);
     }
     int res = 0;
     void start() {
         recursive(state);
     }

     void recursive(int s) {
         if (s == 0) {
             return;
         }
         res = s;
         Fiber.yield();
         recursive(s - 1);
     }
}

void main()
{
     auto search = new Search(42);

     foreach (i; 0 .. 5) {
         search.call();
         writeln(search.res);
     }
}

Ali
Jan 31 2017
parent Profile Anaysis <PA gotacha.com> writes:
On Tuesday, 31 January 2017 at 11:31:28 UTC, Ali Çehreli wrote:

 On 01/31/2017 03:00 AM, Profile Anaysis wrote:


 [...]


 [...]

 [...]


 return type.

 Options:

 [...]


Thanks again!
Jan 31 2017
prev sibling next sibling parent reply TheFlyingFiddle <kurtyan student.chalmers.se> writes:
On Monday, 30 January 2017 at 11:03:52 UTC, Profile Anaysis wrote:

 I need to yield from a complex recursive function too allow 
 visualizing what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield 
 for each node so that the current state can be shown visually.

 I realize that there are several ways to do this but D a yield 
 version without additional threads would be optimal. I don't 
 need concurrency or speed, just simple.


If you don't want to use fibers then an alternative to yeilds is 
to use callbacks during iteration.

Example:
struct Tree(T)
{
    T value;
    Tree!(T)[] children;
}

void iterDepth(T)(Tree!(T) tree, void delegate(Tree!T) cb)
{
     cb(tree);
     foreach(child; tree.children)
     {
         iterDepth(child, cb);
     }
}

unittest
{
     auto tree = ... //Make the tree somehow
     iterDepth(tree, (node)
     {
         writeln(node.value);
     });
}

Callbacks have their set of problems but it's one of the simpler 
ways to do this.
Jan 30 2017
parent Profile Anaysis <PA gotacha.com> writes:
On Monday, 30 January 2017 at 22:34:11 UTC, TheFlyingFiddle wrote:

 On Monday, 30 January 2017 at 11:03:52 UTC, Profile Anaysis 
 wrote:

 I need to yield from a complex recursive function too allow 
 visualizing what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield 
 for each node so that the current state can be shown visually.

 I realize that there are several ways to do this but D a yield 
 version without additional threads would be optimal. I don't 
 need concurrency or speed, just simple.


 If you don't want to use fibers then an alternative to yeilds 
 is to use callbacks during iteration.

 Example:
 struct Tree(T)
 {
    T value;
    Tree!(T)[] children;
 }

 void iterDepth(T)(Tree!(T) tree, void delegate(Tree!T) cb)
 {
     cb(tree);
     foreach(child; tree.children)
     {
         iterDepth(child, cb);
     }
 }

 unittest
 {
     auto tree = ... //Make the tree somehow
     iterDepth(tree, (node)
     {
         writeln(node.value);
     });
 }

 Callbacks have their set of problems but it's one of the 
 simpler ways to do this.


This can't be easily because it requires the callback to contain 
the main program(if it depends on the results). Since I am 
already in a multi-threaded environment it would not be easy to 
marshal the data around.

If I run it in it's own thread then it won't block but seems like 
a lot of work for a simple thing.
Jan 30 2017
prev sibling parent Ivan Kazmenko <gassa mail.ru> writes:
On Monday, 30 January 2017 at 11:03:52 UTC, Profile Anaysis wrote:

 I need to yield from a complex recursive function too allow 
 visualizing what it is doing.

 e.g., if it is a tree searching algorithm, I'd like to yield 
 for each node so that the current state can be shown visually.

 I realize that there are several ways to do this but D a yield 
 version without additional threads would be optimal. I don't 
 need concurrency or speed, just simple.


Sounds like opApply (external iteration) may well be the way to 
go.
It is a great tool to separate (possibly complex) iteration logic 
from (possibly complex) instance processing logic.
Here is a random recipe: 
https://www.sociomantic.com/blog/2010/06/opapply-recipe

An example:

-----
import std.stdio;

class Node {
	int value;
	Node left, right;
	this (int value_) {value = value_;}
}

struct InOrderViewer {
	Node root;
	int opApply (int delegate (Node) process) {
		void recur (Node cur) {
			if (cur is null) return;
			recur (cur.left);
			process (cur); // use return value here to allow break in 
foreach
			recur (cur.right);
		}
		recur (root);
		return 0;
	}
}

void main () {
	auto v1 = new Node (1);
	auto v2 = new Node (2);
	auto v3 = new Node (3);
	auto v4 = new Node (4);
	auto v5 = new Node (5);
	v2.left = v1;
	v2.right = v5;
	v5.left = v3;
	v3.right = v4;

	foreach (node; InOrderViewer (v2)) {
		writeln (node.value ^^ 2); // 1 4 9 16 25
	}
}
-----

Ivan Kazmenko.
Jan 31 2017