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