search

flowbased / flow-based.org

Flow-based programming specification wiki
https://flow-based.org
163 stars 5 forks source link

Recursive graphs #18

Closed jpaulm closed 10 years ago

jpaulm commented 10 years ago

Can't visualize this! Do you have a concrete example?!

TIA

trustmaster commented 10 years ago

Well, recursive graphs is a wrong word here probably. It's recursive algorithms like factorial or tree search which this is about. There's also a bit about it in Matt's book, especially using different contexts for different calls instead of call stacks used in conventional programs.

oleksandr commented 10 years ago

BTW, that's an interesting problem - implementing recursion in FBP. As far as I see Matt is talking about the only way to implement a recursion in Data Flow - using "coloured tokens" - which is rather looping the output of the node to its input and issuing new IPs (tokens) with a certain flag/marker. Is that correct?

BTW, anybody cares to provide an FBP network that demonstrates recursion? Or is this considered harmful and lowered down to be incapsulated at the components level in the conventional programming language?

jpaulm commented 10 years ago

I could certainly see recursion within a component - however at the network level I just can't visualize it... but if someone can demonstrate it at the network level I'd love to see it!

Are there recursive programs that can't be converted to iterative? IMO factorial is almost as pretty done iteratively as recursively, so for me recursion is more of a curiosity than a necessary tool - but maybe that's just me!

Regards,

Paul

On Tue, Aug 12, 2014 at 4:20 PM, Oleksandr Lobunets < notifications@github.com> wrote:

BTW, that's an interesting problem - implementing recursion in FBP. As far as I see Matt is talking about the only way to implement a recursion in Data Flow - using "coloured tokens" - which is rather looping the output of the node to its input and issuing new IPs (tokens) with a certain flag/marker. Is that correct?

BTW, anybody cares to provide an FBP network that demonstrates recursion? Or is this considered harmful and lowered down to be incapsulated at the components level in the conventional programming language?

— Reply to this email directly or view it on GitHub https://github.com/flowbased/flowbased.org/issues/18#issuecomment-51971133 .

alfa256 commented 10 years ago

All recursive programs can be made with loops, but in functional languages recursion is not costly, so you can express programs in a nicer way. In FBP I would avoid recursive graphs but maybe functional programming folks know a trick or two about taking advantage of it. It might be a problem for graph portability, some systems will have trouble with heavy recursive graphs, and others won't, so that might be a thing to take into account, specially if you are spawning real threads for them.

2014-08-12 21:10 GMT-03:00 jpaulm notifications@github.com:

I could certainly see recursion within a component - however at the network level I just can't visualize it... but if someone can demonstrate it at the network level I'd love to see it!

Are there recursive programs that can't be converted to iterative? IMO factorial is almost as pretty done iteratively as recursively, so for me recursion is more of a curiosity than a necessary tool - but maybe that's just me!

Regards,

Paul

On Tue, Aug 12, 2014 at 4:20 PM, Oleksandr Lobunets < notifications@github.com> wrote:

BTW, that's an interesting problem - implementing recursion in FBP. As far as I see Matt is talking about the only way to implement a recursion in Data Flow - using "coloured tokens" - which is rather looping the output of the node to its input and issuing new IPs (tokens) with a certain flag/marker. Is that correct?

BTW, anybody cares to provide an FBP network that demonstrates recursion? Or is this considered harmful and lowered down to be incapsulated at the components level in the conventional programming language?

— Reply to this email directly or view it on GitHub < https://github.com/flowbased/flowbased.org/issues/18#issuecomment-51971133>

.

— Reply to this email directly or view it on GitHub https://github.com/flowbased/flowbased.org/issues/18#issuecomment-51994872 .

Phanta Rei. My FBP Blog: FlowBased http://flowbased.tk

oleksandr commented 10 years ago

I can't event picture the recursive graph in 2D/3D :) May be it's a concept transferred to FBP from the functional languages without an actual need. The term recursive graph is a miss-leading: I can imagine a recursive graph only as a graph, each of node of it is a graph to certain level of deepness. But this has a different name in FBP. I would suggest to drop this term.

alfa256 commented 10 years ago

You can achieve the same thing by plugging the outports to another process with the same component, so we should drop this item from the list.

jpaulm commented 10 years ago

Alex, I agree. Maybe we can just make sure the term "recursive" is not used in the wiki...?

Paul

On Wed, Aug 13, 2014 at 4:29 AM, Oleksandr Lobunets < notifications@github.com> wrote:

I can't event picture the recursive graph in 2D/3D :) May be it's a concept transferred to FBP from the functional languages without an actual need. The term recursive graph is a miss-leading: I can imagine a recursive graph only as a graph, each of node of it is a graph to certain level of deepness. But this has a different name in FBP. I would suggest for dropping this term.

— Reply to this email directly or view it on GitHub https://github.com/flowbased/flowbased.org/issues/18#issuecomment-52022190 .

trustmaster commented 10 years ago

When I was working on my thesis, I came across several papers which stated impossibility to implement recursive algorithms as one of the major drawbacks of Dataflow systems. Which isn't quite true, because recursive algorithms can be implemented with feedback loops. Bad news for dataflow systems which prohibit feedback loops though.

There are generally 2 ways to implement recursive algorithms in FBP:

  1. By converting them from recursive into iterative and using feedback loops, like Alfredo mentioned.
  2. By encapsulating the entire logic inside a component written in a conventional language, like Alex mentioned.

Both choices are legal, which of them is valid for a specific situation depends on the code itself. The rule of thumb is: encapsulate small subprograms without much impact on the outer world, visualize larger subprograms with impact on the outer world.

Is it still worth dropping the topic? :wink:

forresto commented 10 years ago

The example that made (1) make sense for me is parsing all of the files in a directory, looping child directories back.

alfa256 commented 10 years ago

This should be a sub item of Feedback Loops.

trustmaster commented 10 years ago

I agree with @alfa256

oleksandr commented 10 years ago

Feedback loop that is :+1:

jpaulm commented 10 years ago

Old computer joke: For definition of "loop", see "loop"...

On Wed, Aug 13, 2014 at 4:49 PM, Oleksandr Lobunets < notifications@github.com> wrote:

Feedback loop that is [image: :+1:]

— Reply to this email directly or view it on GitHub https://github.com/flowbased/flowbased.org/issues/18#issuecomment-52108747 .

jpaulm commented 10 years ago

Me again! Is this one closable?!