FBP, Steam Engine Time and SQL Execution Plans

[Ged Byrne]

Hi all,

One of the ideas that jumped out from the book for me was that of
"Steam Engine Time." The idea that sometimes and idea's time has just
come and it pops up everywhere. The book lists so many other areas
where the principles of Flow Based Programming "pop up" independently.

I remember reading in the Steve Jobs book that he believed that
products should have an essence, something they want to be.

Personally I believe that Software has an essence and that essence is
Flow, and that FBP is the most advance description of that essence
that I've been able to find so far.

Greenspun's tenth law states: "Any sufficiently complicated C or
Fortran program contains an ad hoc, informally-specified, bug-ridden,
slow implementation of half of Common Lisp."

I disagree. I would say "Any piece of code is an ineffectively
described flow network. It was written in a language that lacks the
proper vocabulary by a developer who is unaware of the proper
principles." Given all of the things that get in the way, it is
remarkable how many good developers manage to get it right. Could it
be that the difference between the average programmer and the great
programmer (the "rockstar" or "10xer" as they have been called) is the
ability to see the flow?

I'd like to add another example to the pile: SQL.

SQL is a language for describing queries, not implementing them. An
RDBMS will then take that description and generate an execution plan.
You can see a picture of one created by SQL Server here:
http://sqlserverpedia.com/wiki/Examining_Query_Execution_Plans

Scroll down one page, just under the heading "Execution Plan Example."

Apart from a couple of differences, the execution plan is easily
recognisable as a Flow Network.

The diagram flows right to left instead of the usual left to right.
The IIPs pull the source data from the tables.

The components include Table Seek, Merged Sort and Nested Loops rather
than the familiar Collate, etc. The components Filter, Sort and
Enhance the data.

Instead of showing the ports it shows an aggregate view of the
estimated traffic. In the tool you can hover over the connection to
see the port details.

I'd be interested to hear your thoughts.

[Bob]

That's a great analogy, Ged.

You have expressed what I was dimly aware of while thinking about the AppKata example (in another thread).

Thank you.

[Ralf Westphal]

I agree there is always a flow hidden in an imperative program.
That we dont see it is due to horizontal and vertical distribution of
logic (expressions and control statements).
If you took the SRP really seriously you'd keep the logic just in the
leafs of the call tree. That would separate it from, well, the flows
in the call tree layers above it. Still, though, the flows would not
be easy to read. A 3GL is not good at encoding and depicting 2D
structures.

[Sam Watkins]

On Sun, Jan 22, 2012 at 01:21:08AM -0800, Ged Byrne wrote:
> I would say "Any piece of code is an ineffectively described flow
> network.

Hi Ged, welcome to the group.

I want to combine FBP ideas with some logic programming ideas:

- generic channels, where direction is not specified
- multi-mode components (e.g. split/join, add/sub, pow/root/log)
- inference, program as data (like Prolog rules / Lisp s-exps)
- handle IO, mutation and containers (perhaps like Haskell's monads)
- namespaces (maybe like Python)

and I want to write video games in it!

Sam

[Ged Byrne]

Hi Sam,

You're right, so much potential.

A generic channel without a specific direction.

That sounds fascinating, could you give me some background?

Thanks,


Ged

[Vladimir Sibirov]

Hi Sam,

Have a look at Go (golang), it has at least these:
- generic channels;
- can pass functions over channels (program as data);
- packages (like Python).

2012/1/23 Ged Byrne <ged....@gmail.com>:

[Vladimir Sibirov]

P.S.: the alternatives are Scala, Clojure and Erlang.

2012/1/23 Vladimir Sibirov <trust...@kodigy.com>:

[Dan]

Quote from Ged Byrne:

"I would say "Any piece of code is an ineffectively
described flow network.  It was written in a language that lacks the
proper vocabulary by a developer who is unaware of the proper
principles."  Given all of the things that get in the way, it is
remarkable how many good developers manage to get it right.  Could it
be that the difference between the average programmer and the great
programmer (the "rockstar" or "10xer" as they have been called) is the
ability to see the flow?"

Perfectly put. I fully agree, Ged. (Classic) code is an ineffectively description of a flow network, so why not describing the essence in the first place.

[Sam Watkins]

> Hi Sam,
>
> You're right, so much potential.
>
> A generic channel without a specific direction.
>
> That sounds fascinating, could you give me some background?

thanks for you interest, Ged.

I'll prepare some document with pictures to explain this, it's a bit
futile doing it with ascii art, or without graphs at all! You might
need to format this email in 'monospaced' font such as 'courier',
to read the low-budget ascii pictures. The following is fairly math
oriented...

The idea is that many operations have an inverse, as if you would run
them in reverse. For example, the inverse of adding 1 to a number is
subtracting 1. The inverse of 'square' is '+/- square root'. The
inverse of 'split' is 'join', and so on. There can also be 3-way
processes, and others.

So we can imagine a FBP process which could either add 1 or subtract 1,
depending what direction the packets (numbers) are flowing through it:

1 -> [ +1 ) -> 2

or, flowing 'backwards':

1 <- [ +1 ) <- 2

addition in general:

1 / \
| | x
2 |+|
| | 4
3 \ /

(this is meant to be a pointy-oval shaped operator!)

Given those four numbers as inputs, the output x would be 2: the numbers on
each side must add up to the same total (6). We can do any relation,
with plus and minus, using a single operator.

Similarly for multiply and divide:

9 [ ] 3
|*|
[ ] y

(this is meant to be a long rectangle!)

the output y = 3, because 3 * 3 = 9

We can do negation and reciprocal simply:

5 / \
|+|
x \ /

so, x = -5 ( 5 and x add to zero)

2 [ ]
|*|
y [ ]

so, y = 1/2 (2 and y multiply to give 1, the product of an empty list of numbers)

If attach a single port to + or *, we get the constants 0 and 1.

These two operators can cover all of rational arithmetic without any
extra symbols needed. Quite neat I think, compared to the normal set of
eight symbols in C for example: 0, 1, +, -, unary -, *, /, =.

The useful 'power' operator could be drawn as a process with 3 ports:
base, power and exponent, so that power = base^exponent. We can then
raise to the power, extract roots, and calculate logarithms using a
single symbol, depending on the pattern of inputs/outputs. Basic trig
can be done with a single a/r/cos/sin relation, which can also evaluate
the hypotenuse using Pythagores' theorem:

/|
r / |
/ | s
/___|
a c

Depending on the pattern of inputs, this can perform any of:

r = sqrt(c*c + s*s) i.e. r = hypot(c, s)
c = sqrt(r*r - s*s)
s = sqrt(r*r - c*c)
s = r * sin(a)
c = r * cos(a)
s = sin(a) (by omitting r, so I guess that is a multiplying edge, that is 1 by default)
a = arccos(c)
a = arcsin(s)

and several more.

I think it's handy to get all that (related) functionality bundled into
a single component.

Another component I looked at was for simple ballistics under constant
acceleration. A bunch of equations from the physics textbook condensed
down nicely to one simple multi-directional network.

We can get some computational efficiency by calculating sin and cos
together, if both are needed.

If you want 'tan(a)', can define that with a simple network:

/|
/ |
/ | s
/___| \
a c [ * ]
\.../ \
t

That just says t = sin(a) / cos(a).

A more general 'triangle' operator could calculate angles from lengths,
calculate area, etc; if you wish to do calculations about triangles!

When we put these flexible components together in graphs, they can
express mathematical relations consicely, and without need for any
equals sign or bias toward one variable or another.

Another useful relation, lisp's cons / head / tail,
it can be represented by a single symbol:

head [~~~~~~\
| cons | list
tail [______/

Constructing a list and extracting the head/tail can be done with the
same operator, it depends which way you feed stuff into it, you can
either feed in the list and get the head and tail as output, or you can
feed in the head and tail, to get the list as output. If you only want
the head of a list, don't connect the 'tail' port to anything (or mark
it as a 'discard' port).

More general list and set operations can be done with a more flexible
basic operator.

It's possible to build more complex networks that work in several
directions by combining such flexible 'multi-mode' components.

Dealing with strings, 'split' and 'join' are complementary and can be
combined.

A programmer could build a complex component which can parse text into
an internal parse tree/graph. The component, used in reverse, can
format the graph nicely for output as text again. This might be easier
than writing a separate parser and formatter.

Believe it or not, differential calculus requires only a single 'd'
(delta) operator in order to express differentiation, integration, and
ordinary differential equations.

We would need pattern matching and replacement rules, equivalence or
'implies' macros, to manipulate such equations, treating these networks
as data. This is also useful to manipulate regular algebraic equations,
and programs in general.

So, these are some ideas of what can be done with multi-mode operators.

Before running a particular program, it should perhaps work out what
direction everything will be flowing in, so that it can be executed more
efficiently or translated into an algorithm (perhaps C code).

Really this stuff is more like declarative logic programming than FBP,
but I am interested in using it for FBP, where operators can show how
streams are related to one another, with sequence and timing
constraints, etc.

thanks,

Sam

[Ged Byrne]

Sam,

Thanks for taking the time to explain.

I'm reminded of James Oddell's categories of business rules, which he
sepates as follows:

Rules
|--- Constraint Rules ("Conditions that restrict object structure
and behaviour"
|--- Stimulus / Response Rules
|--- Operation Constraint Rules
\--- Structure Constraint Rules
\--- Deriviation Rules ("Conditions for inferring or computing facts
from other facts")
|--- Inference Rules ("Execute derviation merely be
assessing available facts"
\--- Computation Rules ("Derive their results via
processing algorithms.")

http://books.google.co.uk/books?id=e2JtvBp7pm8C&lpg=PR1&dq=james%20odell&pg=PA101#v=onepage

The Constraint Rules are what OO is good at and in FBP apply to the
Information Packet. This is an underdeveloped area for FBP.

The Computation Rules derive an output for a given set of inputs using
a algorithm. In FBP this is provided by the processors. Computation
rules can only work in one direction.

The Inference Rules derive new rules based on the logic that one thing
implies another. Fortran did this.

It seems to me that your generic components would be adding inference
rules to FBP. Given a map of this inference rules, a given input and
a desired output it is possible to calculate a route between input and
output whenever possible.

What about situations where the operators are not commutative. For
example SQR and SQRT. 2 -> SQR -> 4 and -2 -> SQR -> 4? Perhaps
parallel flow networks could be derived for further refinement.

Given this style of processing, could we build an efficient flow based
Soduku solver, for example?

I've encountered these concepts elsewhere, but they have always been
abstract and difficult to grasp. It seems that thinking in terms of
networks makes it much more accessible.

Regards,


Ged

[Sam Watkins]

Ged Byrne wrote:
> I'm reminded of James Oddell's categories of business rules, which he
> sepates as follows:
>
> Rules
> |--- Constraint Rules ("Conditions that restrict object structure
> and behaviour"
> |--- Stimulus / Response Rules
> |--- Operation Constraint Rules
> \--- Structure Constraint Rules
> \--- Deriviation Rules ("Conditions for inferring or computing facts
> from other facts")
> |--- Inference Rules ("Execute derviation merely be
> assessing available facts"
> \--- Computation Rules ("Derive their results via
> processing algorithms.")
>
> http://books.google.co.uk/books?id=e2JtvBp7pm8C&lpg=PR1&dq=james%20odell&pg=PA101#v=onepage

Thanks, that looks like a good book. I read that section, or what
google will let me!

> The Constraint Rules are what OO is good at and in FBP apply to the
> Information Packet. This is an underdeveloped area for FBP.
>
> The Computation Rules derive an output for a given set of inputs using
> a algorithm. In FBP this is provided by the processors. Computation
> rules can only work in one direction.
>
> The Inference Rules derive new rules based on the logic that one thing
> implies another. Fortran did this.

This is interesting stuff. I think all of these types of rules can be
expressed as networks of logical operators.

Some operators can work on fancy types like streams, timed streams,
continuous variables, and other operators (including encapsulated
sub-nets).

> It seems to me that your generic components would be adding inference
> rules to FBP. Given a map of this inference rules, a given input and
> a desired output it is possible to calculate a route between input and
> output whenever possible.

That route-finding idea is what I have in mind.

> What about situations where the operators are not commutative. For
> example SQR and SQRT. 2 -> SQR -> 4 and -2 -> SQR -> 4? Perhaps
> parallel flow networks could be derived for further refinement.

Forking the network into parallel networks does sound like a good
approach for this, if it can be done efficiently. Thanks for the idea,
I had not thought of that. :)

An alternative might be to rewrite such networks into FBP programs,
without such uncertain or undetermined values. The computer could
have inference rules (for pattern substitution), to assist with this.
Or it could use a simple depth-first search, like Prolog and most regexp
libraries. This might be good to have for a last resort, but of course
it's not a very efficient way to search.

> Given this style of processing, could we build an efficient flow based
> Soduku solver, for example?

I'm not sure, I suppose so. With depth first search, we can build a
very inefficient one! We need some way guide the search, to tell it to
explore more determined and promising alternatives first. As far as I
know, prolog can only apply rules in order in a depth first search, with
the occasional 'cut'. It's not able to do something like an A* search.

Also, we need some way to apply an operator to each row and column:

nine_numbers in union(rows, columns, squares) => all_digits(nine_numbers)

We could also encode various sudoku 'solving rules' that can help to
find a solution.

At any point, a certain set of rules can be tried, or there is a set of
paths that can be followed. We need a way to guide this, maybe with a
priority queue and custom measures. It probably should also give up if
the number of solutions would be too great.

> I've encountered these concepts elsewhere, but they have always been
> abstract and difficult to grasp. It seems that thinking in terms of
> networks makes it much more accessible.

Yes, I'm keen on the graphical programming. Incidentally, there's no
reason why blind people could not do graphical programming: a graph is
not an inherently visual thing. They would just need to be able to feel
and manipulate the nodes and connections with a suitable 'touch and
feel' device; or using a speech interface, etc.

Sam

[Sam Watkins]

Vladimir Sibirov wrote:
> P.S.: the alternatives are Scala, Clojure and Erlang.
>
> 2012/1/23 Vladimir Sibirov <trust...@kodigy.com>:
> > Hi Sam,
> >
> > Have a look at Go (golang), it has at least these:
> > �- generic channels;
> > �- can pass functions over channels (program as data);
> > �- packages (like Python).

thanks Vladimir. Golang might be a good basis for implementing
an FBP system. My only concern is that it is not so portable as C,
but it would definitely be worthwhile to learn it.

Sam