How do you implement a sorting algorithm (e.g. Bubble sort or Quicksort) in FBP?

[Dan]

Hi,
There are Sorting networks that solve the problem for a fixed number of values using a fixed sequence of comparisons and also they have FBP flavor. But these sorting networks do not solve the problem of sorting in general.
The main question is: how do you implement a FBP program (of fixed size) that sorts a given array of values using any sorting algorithm that we already know?
In other words, how do you translate the sorting algorithm from the classical imperative programming into FBP.
Regards,
Dan

[Ged Byrne]

Hi Dan,

In classical FBP you don't. A component would implement the sorting algorithm using classical imperative programming, or a functional style if desired, and that component would be wired into a flow graph.

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-progra...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Ged Byrne]

Here's an example: https://github.com/jpaulm/javafbp/blob/master/src/main/java/com/jpmorrsn/fbp/examples/networks/MergeSortDrop.java

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

[Dan]

Hi Ged,
It isn't strange that you just can't? Why FBP can not be used all the way through?
This raises another question: why not? Why you can not use FBP all the way through? What is so specific (or problematic) with a sorting algorithm (used here as an example) that can not be translated into a "pure" FBP program / algorithm?
Regards,
Dan

[Ged Byrne]

Did you look at Paul's example?

It uses a classic insertion sort and the execute method is 30 lines long.

  @Override

  protected void execute() {

    Packet p;

    int i = 0, j, k, n;

    Packet[] array = new Packet[9999];

    while ((p = inport.receive()) != null) {

      array[i] = p;

      //System.out.println("in: " + p.getContent());

      ++i;

    }

    //network.traceFuncs(this.getName() + ": No. of elements:" + i);

    j = 0;

    k = i;

    n = k; // no. of packets to be sent out

    while (n > 0) {

      String t = "\uffff";

      for (i = 0; i < k; i++) {

        if (array[i] != null) {

          String s = (String) array[i].getContent();

          if (s.compareTo(t) < 0) {

            j = i;

            t = (String) array[j].getContent();

          }

        }

      }

      //  if (array[j] == null) break;

      outport.send(array[j]);

      array[j] = null;

      --n;

    }

  }

Isn't it strange that you would want to make this more complicated rather than less?  Why would you do that?

Regards, 

Ged

[Paul Morrison]

I guess Dan asked about sorting within storage, and I agree with Ged - I don't see a need to have a more fine-grained network.  However, I suspect that, when it comes to sorting lots of data, an FBP network might be quite appropriate.  You would use something like the sort component Ged talks about to sort as much of the file as possible in storage - and then write the result out to disk to be later merged with other sorted chunks.  Typically you cycle through this process several times, resulting in larger and larger sorted portions, until eventually the whole file has been sorted.

Regards,

Paul

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

[co...@ccil.org]

Dan scripsit:

> This raises another question: why not? Why you can not use FBP all the way
> through? What is so specific (or problematic) with a sorting algorithm
> (used here as an example) that can not be translated into a "pure" FBP
> program / algorithm?

It's not that you can't, it's that as you get to smaller and smaller
grains, the inherent overhead of message passing swamps the advantages
of design. You could create a network to add two 32-bit integers
using single-bit packets, but the cost would be thousands of times
higher than just adding them with an ADD instruction. (At the
hardware level, there actually *is* such a network implementing
the instruction.)

The advantage of FBP as a paradigm, like the REST paradigm, is that it
seals off the components from one another. You can have a network of
components some of which are implemented in an imperative language
like Java, some in a functional language like Haskell, some in a pure
declarative language like Prolog. As long as there is access to the
simple FBP API, they'll all work together just fine.

--
John Cowan http://www.ccil.org/~cowan co...@ccil.org
De plichten van een docent zijn divers, die van het gehoor ook.
--Edsger Dijkstra

[Dan]

I want to highlight from the very beginning the ugliness of a potential FPB implementation due to the fact that most of the code is syntactic sugar as a direct consequence of using an imperative language in the first place but this does not make the FBP code less elegant.
Let's assume we have a FBP language where you can directly describe connections simply like in: A.out1 -> B.in1 and anything else we might need.
My main question was: why FBP can not be used down to the metal (microprocessor)?
I haven't said that I want to go even lower trying to simulate how the bits are shifted in the microprocessor (as a counterexample of John's remark). Anything that lies above the microprocessor is in either way a data flow program that uses in the end the microprocessor's instructions (code).
Even the imperative programs have the data flow but it is hidden beneath the control flow. I have to execute (in mind, eventually) the code to understand how the data flows. In (most of) FBP programs if data flow path is constant than it is easier to code, to understand and even to translate (compile) the program on a parallel hardware architecture.
I don't believe that FBP should be used at coarser granularity to wrap smaller objects and as a coordination program only. I believe that FBP concepts can be used at any level of granularity. This is a strong point.
Now let's go back to the sorting algorithms. I gave you this example because it is good for my case. Here not the granularity is the issue but something else. What is that?

Let's have a look to one of the most simple to write sorting algorithm implementations (http://www.sorting-algorithms.com/insertion-sort):

for i = 2:n,
       for (k = i; k > 1 and a[k] < a[k-1]; k--)
          swap a[k,k-1]
end

Trying to understand what the data flow is and also identifying the actors involved in the process we realize that these loops use array indexing. This can be perceived (in fact it is) a self-modifying code from FBP perspective because it is about connections from one cell to another that dynamically change during the execution. Any reference to a[k] is a connection that changes when k changes. When data swaps it "flows" from one cell to another via connections that change at each iteration.
A FBP programmer does not like to see his code changing at runtime but we have to face this: the connections change during the execution (in this specific algorithm) and a connection is perceived as part of the 'code' in FBP even if in this case 'data' changes. Data (connection) is code.
Now my question to you remains: what esential aspect prevents FBP to be used down to the finest granular level? (do not mention the mess of the imperative language you use for syntactic sugar in order to implement 'FBP like' programs)
The sorting algorithm above is using a single execution agent (thread). We can imagine more than one that can work in FBP style.
In order to implement the sorting algorithm above or any other one in FBP style you have to implement dynamic connections.
Just as a challenge, assuming you have a graceful FBP language at hand, how would you implement the exact algorithm above in FBP? (without being so verbose using an imperative language in order to simulate a declarative one).
Regards,
Dan

[Dan]

John Cowan: inherent overhead of message passing swamps the advantages
of design

Who is forcing you to implement the message passing with so much overhead? The problem resides, again, in the fact that you do not have a 'native' FBP language and you work without a FBP compiler. In the end (in the compiled code) message passing could be similar to allocating a parameter on a callstack. Instead you are forced to implement a FBP component (at a finer granularity) with an imperative language.
The fact that you have a proportional reduced cost when implementing coarser granular objects it does not mean you don't have an important overhead. It's cost is distributed differently to the bigger volume of functionality that resides beneath the big sized FBP component. The cost is there anyhow. I don't think that message passing is 'automatically' (unavoidable) an overhead. It depends on the implementation. Of course it is harder when you don't have the proper tools (FBP language, compiler, architecture).
In fact FBP architecture can reduce the overhead if it is implemented correctly. Having 'global' information you can do optimizations. For instance when you pass a parameter from one function to another when composing a lot of functions is such a case. The parameter is copied on the call stack several times even if it is not used in all the functions along the chain of calls but in the most inner one.
My conclusion is: you can not implement less granular components just because you don't have the right tools to do it (FBP language, FBP compiler) and not because there is any inherent overhead that you can not avoid. You can.

Regards,
Dan

vineri, 13 februarie 2015, 15:01:09 UTC+2, Dan a scris:

[co...@ccil.org]

Dan scripsit:

> My conclusion is: you can not implement less granular components just
> because you don't have the right tools to do it (FBP language, FBP
> compiler) and not because there is any inherent overhead that you can not
> avoid. You can.

Well, FBP programs are functional programs, and nobody yet has managed to
make a general-purpose functional programming language run as fast as C
except in artificial benchmarks. You're perfectly welcome to try, and
there's a rich reward waiting if you succeed.

As has often been said, everyone's entitled to their own opinions, but
not their own facts. People have been trying to optimize dataflow
programming languages (and hardware architectures) for decades now.

Google is your friend.

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

He made the Legislature meet at one-horse tank-towns out in the alfalfa
belt, so that hardly nobody could get there and most of the leaders
would stay home and let him go to work and do things as he pleased.
--H.L. Mencken's translation of the Declaration of Independence

[Dan]

John Cowan:
FBP programs are functional programs

FBP program (components) can have state. They are not necessarily functional programs. A functional component can change its behaviour due to its internal state changes. As long as a FBP functional component is not a pure function we are not discussing about FBP as being 'functional'. Parts of the FBP program are functional of course but state is between.
Handling of the state in functional language is like hiding the trash under the carpet. The state is there, you can not hide it. The guys that promotes the functional languages always try to neglect that they should handle the persistent state somewhere but not in their "pure" functions, somewhere outside of their "pure" world. They don't get dirty, maybe somebody else :-).
Functional languages can be deceiving. Moving most of the 'state' on the stack it doesn't mean it is stateless. It just mean that the state is associated with a certain call (that means instance) of a functional component and it is transient. There is state that needs to be persistent (to survive outside of a function call).
In FBP we perceive as transient data the messages (IPs) that travel from one component to another that are created by one emitter and consumed by a receptor. But there is also data that does not go anywhere, it remains there.
Using monads in functional languages like Haskell made possible to elegantly compose functions that were not composable and to use and move supplementary information (like logging, exceptions etc.) through the network instead of using (fixed) 'global' variables prone to errors. This kind of state (allocated on the stack) is transient but you can not make programs full of just transient data without any persistence at all. There is state that outlives the process that created it.

Regards,
Dan

vineri, 13 februarie 2015, 15:01:09 UTC+2, Dan a scris:

[co...@ccil.org]

Dan scripsit:

> FBP program (components) can have state.

"Functional" does not mean "pure functional". There are stateful
functional programming languages like ML, Pure, and Scheme.

But what I meant is that the network definition is pure functional,
even if there is state in the component implementation.

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

"The exception proves the rule." Dimbulbs think: "Your counterexample proves
my theory." Latin students think "'Probat' means 'tests': the exception puts
the rule to the proof." But legal historians know it means "Evidence for an
exception is evidence of the existence of a rule in cases not excepted from."

[Sam Watkins]

On Fri, Feb 13, 2015 at 05:39:42AM -0800, Dan wrote:
> It isn't strange that you just can't? Why FBP can not be used all the
> way through?

FBP can be used to implement a sort component.

Here is an FBP mergesort written in bash shell.

http://sam.nipl.net/code/mergesort

It uses recursion to create a FBP network right down to the lowest level
of the mergesort. This could be fast if implemented using electronic
circuitry, however in bash it is quite slow and impractical due to the
large number of processes that will be created, the overhead of IPC, the
slowness of bash, and the limited parallism offered by current
computers. (There are better designs for sorting quickly in circuitry.)

It would work better (on current computers) if we stop splitting into
more processes after we have enough processes to keeep all the cores
busy, and use a regular single-process sort after that. For an 8 core
system - split input into 8 parts, sort each part using a single process
(in parallel), merge by pairs (7x parallel).

Here's a program sort8 which does that:

text:
http://sam.nipl.net/code/net2sh/eg/sort8
graph:
http://sam.nipl.net/code/net2sh/g/eg/sort8.dot.png

perf. test, sorting 99171 words, a shuffled dictionary, on 8 cores:

regular GNU sort(1):
real 0m0.261s
user 0m0.256s
sys 0m0.004s

sort8:
real 0m0.123s
user 0m0.508s
sys 0m0.053s

It uses quite a lot more power but completes in less than half the time
compared to a regular single-process sort. Splitting the merge phase
like this makes it quicker compared to a single process merge.

In fact GNU sort(1) uses multiple threads for large files, but not in
this case.


Sam

[Matthew Lai]

On Sunday, 15 February 2015 10:08:01 UTC-5, Sam Watkins wrote:

It uses recursion to create a FBP network right down to the lowest level
of the mergesort.  This could be fast if implemented using electronic

circuitry, ...  (There are better designs for sorting quickly in circuitry.)

Care to elaborate on "sorting quickly in electronic circuitry"? i.e. please
point us to schematic diagram of a circuit that will implement this merge sort?

Thanks!

Yours,

Matt

[Paul Morrison]

A minor point on this, but not necessarily obvious  - sometimes you know from the application that you don't actually have to sort the whole file.  You just sort the part that has to be sorted, and Collate the result with the other parts of the file (split off earlier).  Because the sort doesn't output anything until it's completed, you will probably have to use a tool like the so-called "infinite queue" (a writer triggering a reader using automatic ports) to hold the other parts temporarily.  There is an example of this in http://jpaulmorrison.com/fbp/image010.jpg .

Cheers,

Paul

Sam

[Paul Morrison]

It looks like this topic has been pinned - is this necessary?  If not, could someone unpin it...?  (If I did it, I don't know how I did it!)

Thanks,

Paul M.

[Dan]

Solved.

Dan

[Simon Gauvin]

Hi Dan,

I'm new to the forum but thought I would introduce a new data flow programming language Vizwik (www.vizwik.com) to answer your question with an example of quick sort below:

There are two screen shots, one for the first set of cases, and one for the second set of cases in the blocks. Note that the two "partition" functions are just extra for teaching the whole theory and not necessary given that these are really implemented as native operations, leaving just the first Quicksort function as the solution. 

Cheers,

Simon

[Dan]

Hi Simon,

Thanks for sharing with us the link.
Does a program in vizwik answer my question? (i.e. sort a collection of elements using a fixed length program in a (data) flow style (declarative not imperative)
I have seen the pictures but it is not quite clear to me.

Regards,
Dan

[Simon Gauvin]

Hi Dan, 

I think it is a partial answer, as Vizwik is obviously data flow style, but the control structures in the language are imperative (conditional branch, iterators), therefore a mix of both. The algorithm sorts a collection of elements. However, I'm not sure what you mean by "fixed length program" so perhaps you could clarify?

Regards,
Simon

[Dan]

Almost all programs are of "fixed length" because they are not modifying themselves at run-time and they are fixed at compile time.
But what I had in mind was the Sorting networks that I have tried to avoid in my question. Why? Because their size depends on the input that has to be sorted. So I don't want a "program" (network in this case) that is of variable size (and various architectures) depending on the input. I want it fixed and flow based style.

Regards,
Dan

[Simon Gauvin]

Right, understand the difference, so yes, the vizwik code is fixed length, does not change size, and independent of the input size.

Best,

Simon

--
You received this message because you are subscribed to a topic in the Google Groups "Flow Based Programming" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/flow-based-programming/8Oh38HHeb_E/unsubscribe.
To unsubscribe from this group and all its topics, send an email to flow-based-progra...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

-------------------------
Simon Gauvin, CEO

Apps by Everyone
www.vizwik.com
@agoramobile

www.facebook.com/vizwik

blog.vizwik.com