Presentation on Pipes and Filters

[Humberto Madeira]

InfoQ has a new presentation by Ian Cooper on the Pipes and Filters architectural style.

http://www.infoq.com/presentations/pipelines-events

The presenter refers to MS LINQ as an example of the pull-style and the Rx (Reactive Extensions) Framework as an example of push-style

LINQ seems closer to FBP, but with some significant elements missing (although it seemed to me that it could probably be extended in such a way as to make up the difference)

--Bert

[co...@ccil.org]

Humberto Madeira scripsit:

> The presenter refers to MS LINQ as an example of the pull-style and the Rx
> (Reactive Extensions) Framework as an example of push-style
>
> LINQ seems closer to FBP, but with some significant elements missing
> (although it seemed to me that it could probably be extended in such a way
> as to make up the difference)

FBP is both push-style and pull-style: components pull when they read
and push when they write, the same as the filesystem API. This is also
true of proper Unix pipes and filters.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org
We are lost, lost. No name, no business, no Precious, nothing. Only empty.
Only hungry: yes, we are hungry. A few little fishes, nassty bony little
fishes, for a poor creature, and they say death. So wise they are; so just,
so very just. --Gollum

[Kenneth Kan]

This may be just a semantic discord, but this push/pull debate has such a mental strain on many folks (myself included) so it'd be nice if someone could help clarify this for me.

When you say it's "both push and pull", do you really mean it's *neither* push nor pull? Say you have `A -> B`. `A` sending an IP to `B` doesn't really effect `B` in any way. `B` can choose to read from the connection now, read later, or never at all (even when the connection is not full). Likewise, `B` blocking because there's nothing in the connection doesn't "invoke" `A` for more data in any way; in fact, `A` does not even know `B` is waiting on data from it. Contrast this from a push system, where `B` would be "invoked" when there's data (basically conventional imperative programming), and from a pull system, where `A` would keep "invoking" upstream subroutines for more data until things run out (basically lazily evaluated languages).

I know; I know that when implementing an FBP system, we have to throw some theories out the window to make it work under the hood, but when reasoning about FBP programs, I think FBP renders pull vs push irrelevant. Am I on the right track here?

[Paul Tarvydas]

On 15-03-15 01:20 PM, Kenneth Kan wrote:

This may be just a semantic discord, but this push/pull debate has such a mental strain on many folks (myself included) so it'd be nice if someone could help clarify this for me.

When you say it's "both push and pull", do you really mean it's *neither* push nor pull? Say you have `A -> B`. `A` sending an IP to `B` doesn't really effect `B` in any way. `B` can choose to read from the connection now, read later, or never at all (even when the connection is not full). Likewise, `B` blocking because there's nothing in the connection doesn't "invoke" `A` for more data in any way; in fact, `A` does not even know `B` is waiting on data from it. Contrast this from a push system, where `B` would be "invoked" when there's data (basically conventional imperative programming), and from a pull system, where `A` would keep "invoking" upstream subroutines for more data until things run out (basically lazily evaluated languages).

I know; I know that when implementing an FBP system, we have to throw some theories out the window to make it work under the hood, but when reasoning about FBP programs, I think FBP renders pull vs push irrelevant. Am I on the right track here?

Hi Ken,

Yes, I think that you're on the right track.

I would rephrase this as "components are asynchronous". 

Components produce or consume when they feel like it.

If a component produces too much output, it blocks.

If a component tries to read input when there is none, it blocks.

Does that make it any more clear?

You are probably correct.  We, here, are using the terms push and pull in a non-conventional manner, that may be misleading.  For us, these terms do not involve any kind of "demand".  Decoupled asynchrony is what we're talking about.

pt

On Thursday, March 5, 2015 at 3:34:31 PM UTC-5, John Cowan wrote:

Humberto Madeira scripsit:

> The presenter refers to MS LINQ as an example of the pull-style and the Rx
> (Reactive Extensions) Framework as an example of push-style
>
> LINQ seems closer to FBP, but with some significant elements missing
> (although it seemed to me that it could probably be extended in such a way
> as to make up the difference)

FBP is both push-style and pull-style: components pull when they read
and push when they write, the same as the filesystem API.  This is also
true of proper Unix pipes and filters.

--
John Cowan          http://www.ccil.org/~cowan        co...@ccil.org
We are lost, lost.  No name, no business, no Precious, nothing.  Only empty.
Only hungry: yes, we are hungry.  A few little fishes, nassty bony little
fishes, for a poor creature, and they say death.  So wise they are; so just,
so very just.  --Gollum

--
You received this message because you are subscribed to the Google Groups "Flow Based Programming" group.
To unsubscribe from this group and stop receiving emails from it, send an email to flow-based-progra...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kenneth Kan]

Yes, it does. Thank you Paul for the explanation.

I see FBP as being just like any packet-routing network, with determinism added to the protocol (as individual node blocks rather than just keep on going). I suggest that going forward we tweak or even just drop the push/pull dichotomy altogether, as it primes most programmers to think in a certain direction that may not be so in line with FBP.

[John Cowan]

Kenneth Kan scripsit:

> When you say it's "both push and pull", do you really mean it's *neither*
> push nor pull? Say you have `A -> B`. `A` sending an IP to `B` doesn't
> really effect `B` in any way. `B` can choose to read from the connection
> now, read later, or never at all (even when the connection is not full).
> Likewise, `B` blocking because there's nothing in the connection doesn't
> "invoke" `A` for more data in any way; in fact, `A` does not even know `B`
> is waiting on data from it.

Exactly right, with two exceptions:

1) If A terminates, then B can still read packets until the connection is
empty, but after that the framework supplies an "end of input" packet
(like EOF when reading from a file system).

2) If B terminates, then when A tries to write to it, A is killed, which
allows orderly shutdown of a whole pipeline when the final component
decides for its own internal reasons that it doesn't need any more.

But I was speaking from the viewpoint of the component, not the framework.
When reading, a component thinks it is pulling from its upstream partner,
and when writing, a component thinks it is pushing to its downstream
partner, whatever actually happens..

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org

Do what you will / this Life's a Fiction
And is made up of / Contradiction. --William Blake

[Kenneth Kan]

Thanks for the clarification. That makes a lot of sense. Just wanted to make sure that point is clear as most tend to associate push/pull as a characteristic of the program at the network level.

[Ged Byrne]

Here we have another neat aspect of FBP. By default connectors PUSH until back pressure changes them to PULL.

Imagine we have 3 components in a simple pipeline connected by bounded buffers with a capacity of 2.

US-->Y->Z->DS

X is receiving packets from an upstream component that generates an incrementing number every second.

Z is pushing to a downstream component that can only accept 1 packet every 10 seconds.

Here is what happens in the first 15 seconds after system start up.

Second. Activity.
1. US Pushes to Y pushes to Z pushes to DS. Downstream now blocks for 10 seconds.

US-__->X-__>Y->DS (1)

2. US pushes to Y pushes to Z. Z attempts to push but is blocked

US-__->X-__>Y(2)->DS (1)

3. US pushes to Y pushes to Z where it waits in the queue.

US-__->X-_3>Y(2)-DS (1)

4. US pushes to Y pushes to Z where it waits in the queue.

US-__->X-43>Y(2)-DS (1)

5. US pushes to X pushes to Y which attempts to push to Z's queue and blocks.

US-__->X(5)-43>Y(2)-DS (1)

6. US pushes to X pushes to Y where it waits in the queue.

US-_6->X(5)-43>Y(2)-DS (1)


7. US pushes to X pushes to Y where it waits in the queue.

US-76->X(5)-43>Y(2)-DS (1)

8. US pushes to X pushes to Y and blocks.

US(8)-76->X(5)-43>Y(2)-DS (1)

9. Nothing happens. The system is blocked.

US(8)-76->X(5)-43>Y(2)-DS (1)

10. DS pulls the next item from its queue. Y is unblocked and pulls from X which unblocks and pulls from downstream.

US(9)-87->X(6)-54>Y(3)-DS (12)

Nothing happens for another 10 seconds, when DS pulls again.

US(A)-98->X(7)-65>Y(4)-DS (123)


As you can see from the above, the pipeline is initially push but back pressure causes it to become pull. This makes FBP systems self balancing. The designer does not worry about push and pull but can tweak buffer sizes if necessary.

Contrast this with the tendency in modern code to make connections appear unbounded. When something goes wrong the consequences can be hidden until the illusion of infinity is broken.

However, it does show why FBP is not ideal for the UI. It isn't acceptable for a UI to block when the system is busy.

Command lines work this way. there's a keyboard buffer. If the system is blocking your keystrokes go to the buffer. If the buffer is full then your keys are rejected with a beep.

Regards,



Ged

--

You received this message because you are subscribed to the Google Groups "Flow Based Programming" group.

To unsubscribe from this group and stop receiving emails from it, send an email to flow-based-programming+unsubscri...@googlegroups.com.

[Kenneth Kan]

Right. I'm with you on that, but that applies to a UI "engine", which works more like UDP than FBP packets. And that model would make sense as we don't want back pressure in this case. Though, my thoughts are that you could use FBP is handle everything else. The setup is basically having a monolithic component that handles all the rendering and you feed IPs from the various processes, each of which represents an on-screen object/component/area. The monolithic component (i.e. the rendering engine) would drop IPs as needed and should, if possible, be given the highest priority by the system. Do you think that model makes sense?

[Paul Morrison]

Yes I think that sounds like a very promising approach!  

The discussion of push/pull was interesting too!  I had never understood why people insist on describing FBP as either push or pull!

John, one of my quibbles:  I haven't used a special IP for end of stream since AMPS - the problem this caused was that, when you have a many-to-one connection, all of these special IPs somehow have to be dropped except the last one.  I actually don't remember how or when I did this!

Since AMPS the rule has been that a process closes down when all immediate upstream processes have closed down and all upstream connections are empty.  IMO actually a simpler mental model!

Regards,

Paul

On Mar 16, 2015 11:33 PM, "Kenneth Kan" <ken...@gmail.com> wrote:

Right. I'm with you on that, but that applies to a UI "engine", which works more like UDP than FBP packets. And that model would make sense as we don't want back pressure in this case. Though, my thoughts are that you could use FBP is handle everything else. The setup is basically having a monolithic component that handles all the rendering and you feed IPs from the various processes, each of which represents an on-screen object/component/area. The monolithic component (i.e. the rendering engine) would drop IPs as needed and should, if possible, be given the highest priority by the system. Do you think that model makes sense?

--

You received this message because you are subscribed to the Google Groups "Flow Based Programming" group.

To unsubscribe from this group and stop receiving emails from it, send an email to flow-based-progra...@googlegroups.com.

[co...@ccil.org]

Paul Morrison scripsit:

> John, one of my quibbles: I haven't used a special IP for end of stream
> since AMPS - the problem this caused was that, when you have a many-to-one
> connection, all of these special IPs somehow have to be dropped except the
> last one. I actually don't remember how or when I did this!

I built them into JavaFBP if you haven't removed them since, and the
reason is to make components like Concatenate possible: read all the IPs
from one input port in an array, then all the IPs from the next, etc.
Without explicit EOS, that can't be done.

> Since AMPS the rule has been that a process closes down when all immediate
> upstream processes have closed down and all upstream connections are
> empty. IMO actually a simpler mental model!

What about the backwards kill? You still need that for a component
like Head, which transmits the first N IPs from its input port and
copies them to its output port and then shuts down. (N comes from an
IIP, of course). Once Head has terminated, its predecessor needs to
terminate too, or it'll wait forever.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org

Tautology is something that is tautological. --Francois-Rene Rideau

[Sam Watkins]

On Tue, Mar 17, 2015 at 02:03:56PM -0400, co...@ccil.org wrote:
> What about the backwards kill? You still need that for a component
> like Head

Of course, UNIX has these features: EOF and SIGPIPE.

Sam

[Paul Morrison]

On Mar 17, 2015 2:04 PM, <co...@ccil.org> wrote:
>
>
> I built them into JavaFBP if you haven't removed them since, and the
> reason is to make components like Concatenate possible: read all the IPs
> from one input port in an array, then all the IPs from the next, etc.
> Without explicit EOS, that can't be done.

>
> > Since AMPS the rule has been that a process closes down when all immediate
> > upstream processes have closed down and all upstream connections are
> > empty.  IMO actually a simpler mental model!

I don't have a problem with Concatenate!  Receive will return a null pointer when the upstream processes of that array element have all closed down, and the connection is empty.  It works fine!  I haven't seen an EOS IP for years - sorry, John!

>
> What about the backwards kill?  You still need that for a component
> like Head, which transmits the first N IPs from its input port and
> copies them to its output port and then shuts down.  (N comes from an
> IIP, of course).  Once Head has terminated, its predecessor needs to
> terminate too, or it'll wait forever.

Right!  The close input port method does that.

Regards,

Paul
>
> --

[John Cowan]

Sam Watkins scripsit:

> Of course, UNIX has these features: EOF and SIGPIPE.

You bet. :-)

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org

While staying with the Asonu, I met a man from the Candensian plane,
which is very much like ours, only more of it consists of Toronto.
--Ursula K. Le Guin, Changing Planes

[co...@ccil.org]

Paul Morrison scripsit:

> I don't have a problem with Concatenate! Receive will return a null
> pointer when the upstream processes of that array element have all closed
> down, and the connection is empty. It works fine! I haven't seen an EOS
> IP for years - sorry, John!

In that case, the null pointer is simply a different representation of EOS.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org

Adam [...] did not want the apple for the apple's sake, he wanted it only
because it was forbidden. The mistake was not forbidding the serpent;
then he would have eaten the serpent. --Mark Twain

[Paul Morrison]

Not the same, John.  You said 'the framework supplies an "end of input" packet'  - my implementations simply return null from "receive" - no special IP is created.

Regards,

Paul