Cells compared to Flow-Based Programming

Sohail Somani wrote:
> Ken Tilton wrote:
>
>>
>>
>> Sohail Somani wrote:
>>
>>> http://smuglispweeny.blogspot.com/fe.../30day?alt=rss
>>>
>>> The url immediately above is the feed I'm aggregating so if you make
>>> a post and it didn't show up, one of us screwed up.
>>
>>
>> Is a "tag" a "label"? It has been thirty seconds and I still do not see:
>>
>> http://smuglispweeny.blogspot.com/se...%20application
>
>
>
> Yikes. That is the ugliest URL ever. Anyway, in the interest of keeping
> the dinosaur old, I've adjusted the feed to pick up your interesting
> category name.
>
> It should be picked up sometime between now and July ;-)

Do I hear you saying "and /only/ 30day"?



kt


--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?do...93764413&hl=en
ECLM talk:
http://video.google.com/videoplay?do...42928&q=&hl=en

Ken Tilton wrote:
>
>
> Sohail Somani wrote:
>> Ken Tilton wrote:
>>> Is a "tag" a "label"? It has been thirty seconds and I still do not see:
>>>
>>> http://smuglispweeny.blogspot.com/se...%20application
>>
>> Yikes. That is the ugliest URL ever. Anyway, in the interest of
>> keeping the dinosaur old, I've adjusted the feed to pick up your
>> interesting category name.
>>
>> It should be picked up sometime between now and July ;-)
>
> Do I hear you saying "and /only/ 30day"?

I thought of all people, Lisp programmers would DWIM (do what I mean).

:-)

Paul Tarvydas wrote:

> Disadvantages: (a) no preemption, (b) you have to promise to get-in get-out
> quickly.
>
> Advantages: (c) you get to think and program in the reactive paradigm (which
> I claim is more appropriate for many modern problems), (d) you can build
> structured, hierarchical networks (using "schematics" - described in the
> papers), (e) you can draw and compile diagrams.

This concept helps to reduce the context switching overhead but it makes
programming harder, because the promise to get-in get-out quickly requires
additional process state variables, which could be implicit to the code
otherwise. E.g. when reading a file and sending out tokens, you just write
one loop with preemption, but with your concept you have to return and
store the last state after each send, if you can't send all the file
contents of a big file to the queue.

Another disadvantage is, that you don't utilize multi-core CPUs very well.
What do you think about using another concept: A thread group (not related
to Java thread groups), which groups some processes in its own thread, and
within each thread group the lightwight and cooperative threading is
running?

A thread group needs not to be running all the time: If no component is
active within a thread group, the system thread could be released to a
thread pool, to avoid creating and destroying system threads all the time.

Deciding which processes can be grouped should be easy. Processes like a
loop which reads a file, can be in its own thread (a thread group with one
process).

Thread groups could be compared with different clock domains in
electronics, or a thread group could be a group of components, which are
coupled by a bus like I2C to other component groups.

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

Robert Maas, http://tinyurl.com/uh3t wrote:

> This sounds like bullshit. What really is "message passing"?
> How is that any different from a function (procedure) being passed
> a message consisting of parameters and returning a message
> consisting of a set of return values?
> Surely two black boxes can't pass messages directly between them,
> because neither can possibly know of the other's existance. Some
> higher-level controller must decide which message is to be passed
> to which black box and then collect whatever return messages it
> produces and decide where to forward them next.

You are right, using a main function, which calls functions and other
functions with the returned values, could be one way to implement it and
with continuations even pseudo-multithreaded. Of course, the code would be
not very readable, because processes can have state and there can be
multiple instances of one process, so you have to maintain states in you
main function and add a state parameter for each function. And you have to
write a lot of code for the network of queues and processes. Looks like
this could be simplified with a framewirk with a DSL and some macros. The
result would be a cooperative system like Paul Tarvydas described.

> So I don't see how FBP is any different from procedural programming,
> where a main application calls the various subroutine components.

As Kenny wrote, everything is a Turing machine. The difference is the
higher level concept: With the same argument you could say, that you don't
see any difference from procedural programming and object oriented
programming. OO is just calling functions with a this pointer, and some
more logic to implement inheritance, polymorphism etc. The point is the
higher level concept of "objects". It is not important how to implement it,
e.g. like you can see in the object oriented framework GTK, which is
implemented in C, which doesn't know about classes.

Same with FBP: When designing a FBP program, you think about data, which is
processed by a network of processes.

I don't have experience with FBP, but I think one additional main
difference compared to structured programming is the focus on data instead
of tasks. In structured programming you have a problem, which you split in
simpler problems, until you can implement it as functions. In FBP it looks
like it is more data-oriented: You have some input data and some output
data and with the help of processes, you split the data to simpler streams,
which are fed to sub-networks and are merged together at the output.

> What if a procedure needs several different inputs from different
> sources before it will be ready to return some values?

In a real preemptive system this is no problem: e.g. if you need a value
from wire x and a value from wire y, first read a value from wire x, then
read a value from wire y, then process the values. Each read could block
until there is some data in the wire (but you have to be careful to avoid
deadlock problems).

> That's easy
> in procedural programming too: All you need is an OWN (static)
> variable that keeps the internal state from one call to the next,
> and a NULL type of return that is simply discarded, in a case where
> there are no return values yet.

Maybe this is possible for simple cases, but sounds a bit complicated and
not like intuitively understandable code. And what do you do if you need
multiple instances of processes? You could arrange static variables in
arrays and passing context information to the function which instance is
meant, but the code would become even more unreadable.

> This sounds like more bullshit. It's the GUI which is diagrammatic.
> The *actual* network definition is a connection list, which is
> somewhat hidden from view when using the GUI, but it's really there
> all the time, and it's quite apparent when writing "programs that
> write programs", as is often done in Lisp. It would be a royal
> pain, when writing a program that writes a FBP program, to need to
> convert all the details into a visual diagram (or mouse motions to
> draw a visual diagram) which is somehow fed back into the GUI.

That's true and the diagram is just one way to visualize it. In the book
the author wrote, that a blind person was happy to use the concept, because
it made work so much easier for him. It doesn't matter how you build or
visualize the network of connected processes.

> ... IPs traveling across a given connection
> (actually it is their "handles" that travel) constitute a "stream",
> which is generated and consumed asynchronously ...
>
> So that pretty much precludes running such a process on multiple
> CPUs connected across the InterNet? Or does a process on one
> machine owning a handle for data on another machine have a way to
> request that other machine to eventually send the actual data?

I think this is an implementation detail. When traveling to other machines
it sounds like a good idea to transfer the data to which the handle points,
as well. In the original FBP concept an outgoing connection feeds only one
incoming connection (but an incoming connection can be fed from multiple
outgoing connections) and you have to explicit destroy an IP. This
supercedes GC and there will be a one-to-one relation between a handle and
the associated data.

>> Anyone interested in implementing FBP in Lisp?
>
> Do you mean implement it in some particular vendor-supplied
> implementation of Lisp which happens to support multiple threads?
> Or somehow implement it in ANSI CL, somehow emulating threads by
> means of some sort of polling loop?

I think a mix of both would be nice, see my other posting today.

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

On Fri, 30 May 2008 17:48:59 -0400, Paul Tarvydas
<tarvydas@visualframeworksinc.com> wrote:

>George Neuner wrote:
>
>> On Thu, 29 May 2008 11:26:53 -0400, Paul Tarvydas
>> <tarvydas@visualframeworksinc.com> wrote:
>>
>>>Do you happen to know anything about hardware design? TTL, say. On a
>>>circuit board populated with TTL chips, are the chips all synchronized or
>>>are they asynchronous?
>>
>> TTL is not asynchronous in the manner that software people generally
>> use the term.
>> <snip>
>
>Maybe I don't follow what you mean.

Then let's try this.

In software, asynchronous does not mean "parallel" but rather means
"not sequential" and there is the notion of independence. It's based
on the ideas in Hoare's book, "Communicating Sequential Processes" - a
good read if you haven't already. An electronic version is at
http://www.usingcsp.com/cspbook.pdf.

My objection to your TTL reference was that, although it's true that
the components operate in parallel, the cascade logic itself is
sequential. Each basic block (NAND, NOR, etc.) represents a
sequential function. A connected web of blocks can only represent a
sequential function or an oscillating function (which is really just a
brawl of 2 or more sequential functions). Achieving non-sequential
logic as in the software model requires multiple webs with little or
no signal interaction between them.


>My point was that from the perspective of a single component, the arrival of
>inputs is not predictable - inputs can arrive at that component "at any
>time" in "any" order. The inputs to a chip do not all arrive at the "same"
>time like parameters to a subroutine do.

Ok. It was unclear to me that that is where you were going with the
argument.


>Furthermore, as you point out, one can calculate the propagation time for a
>signal through a circuit largely due to the fact that the components of the
>circuit are independent (unlike software, where subroutines depend, deeply,
>on other subroutines).
>
>A chip can be characterized before it is used in a circuit. Circuits made
>from pre-characterized chips are easier to design. Software built with
>subroutines does not work this way due to the tangle of dependencies (maybe
>it is theoretically possible, but I never see anyone doing that).

Software can be analyzed in a similar way (see Gries, Barendregt,
etc.). It's just that few developers know how to formally proof
software and even fewer bother to do it except when the results will
be published. It's also the case that some popular programming
languages have features that impede easy analysis.


>>>Do hardware people achieve better success rates in
>>>their designs than software people do in their designs?
>>
>> Yes. But the reason is because they don't invent new logic ...
>
>[If that's true, why was my National Semiconductor catalogue from the
>late '70's so much thinner than one from the '80's?]

Because the complexity of "standard" parts has been increasing. That
does not refute my argument that hardware developers simply combine
standard parts - all that's happened is that what was previously board
level macro circuitry has been proven useful enough to be integrated
into a standard IC.

I think you'll agree that the vast majority of hardware designers are
content to pick parts out of catalogs rather than do materials
chemistry to build senary logic gates.

Software developers, OTOH, do invent ad-hoc symbolism and accompanying
predicate systems every time they write a program - usually
under-specified, almost always incomplete, rarely coverage tested and
limited to "expected" inputs.


>> they reuse standardized components having known behaviors. Even when the
>> components are interconnected in novel ways, the behavior of the
>> result is predictable.
>
>Yes. My point is that this is a good model / goal for building software.

I agree.

The problem of standardized software components will be solved as soon
as everyone can agree on a common paradigm neutral, multi-language,
cross-platform, immutable, type safe, modular delivery system.

I don't see that happening in my lifetime (and I expect to live
another 30-40 years).


>>>Do chip designers offer some kind of guarantee that their chips will work
>>>as specified in the data sheets?
>>
>> No. They offer "warranty" ... which is a very different concept from
>> "guarantee".
>
>If I understand correctly, a warranty is time-limited, a guarantee is a
>statement of fact ("it will operate thusly").

Historically "warrant" was limited to the lifetime of the giver.
However, companies have (potentially) unlimited lifetimes.

There is a legal difference between "warranty" and "guarantee". A
warrant is a statement of authority to take action in matters related
to whatever is warranted. A guarantee is a promise of responsibility
for an obligation.


>What, then, is a data sheet and what is the purpose of the "test circuit"
>often supplied on a data sheet? What is the purpose of a truth table
>supplied in a data sheet?

A data sheet is just a piece of paper. The warranty that the data
sheet is a good faith description of the operation of a part and that
the company will replace parts that do not conform to the description
is what gives meaning to the data sheet.


>Every hardware designer I knew used data sheets as statements of operation
>(which I think is called a "guarantee"). They knew not to rely on
>non-specified behaviour and they knew to complain bitterly if the specified
>behaviour was not delivered.

If everyone jumped off a cliff would you do it too? Those designers
were relying on an incorrect understanding of the meaning of the
documents.


>>>Do software designers offer equivalent guarantees?
>>
>> No. But some select few do offer warranty.
>
>A software attempt at datasheets is the set of Java library reference
>manuals. In my experience they fall far short of the sort of utility that
>hardware datasheets provide(d). I claim that this is because software
>subroutines (classes, et al) are too wound together and too interdependent
>to allow a clean characterization of operation and behaviour as is possible
>for hardware. I think that using reactive software components and circuits
>built using reactive software components is a step in the "right"
>direction.

The best software "data sheets" I've seen were for Intel's Integrated
Performance Primitive libraries.

Component software is a great idea but intractably hard in practice.
Honestly I can't care much about the lacking in Java's documentation
because Java as it exists now is not a suitable candidate for a really
useful componentized software platform. Neither is .NET, or Corba, or
COM or anything I've yet seen.

George

--
for email reply remove "/" from address

Frank Buss wrote:

> This concept helps to reduce the context switching overhead but it makes
> programming harder, because the promise to get-in get-out quickly requires
> additional process state variables, which could be implicit to the code
> otherwise. E.g. when reading a file and sending out tokens, you just write
> one loop with preemption, but with your concept you have to return and
> store the last state after each send, if you can't send all the file
> contents of a big file to the queue.

I think that this analysis is based on a faulty base assumption. You seem
to assume that I have to build this in assembly language and that you get
to use a kernel plus a programming language suited for your paradigm.

At the assembler level, I think that I have to save less state than the
process-based method. Preemption requires that every cpu register be saved
on the stack and that the stack pointer be changed. My method needs to
save an index in a state variable. The rest of registers don't need to be
saved (because, (a) either the unit of work has been completed (getting
out) and only the "next state" needs to be saved, or (b) a hardware
interrupt has occurred and the hardware does (at least some of) the saving
for me).

Of course, you don't see that happening in a process-based system when you
use a kernel and a stack-based programming language.

Likewise, imagine that my method uses a kernel and an anti-stack-based
programming language. (Indeed, I do use a language suited to the
paradigm - it's even a graphical programming language).

Equally invisible work for the programmer in both cases. My method is more
efficient (because it has to save fewer registers) on bare hardware.

(This, in fact, was the driving factor for why we invented this method - we
needed to beat the performance of PLC's and RTOS kernels for an injection
molding controller).

(Aside: another analogy for VF is to think of a system of communicating
device drivers. Every component is a device driver. Some of them talk to
real hardware, some talk to other device drivers. All VF components
operate "below" the rtos (if you bother to install one)).

> Another disadvantage is, that you don't utilize multi-core CPUs very well.

Why do you say this? I would guess that we would do better on multi-core
CPU's. Either you misunderstand my method or I misunderstand how you
reached that conclusion (I'll hold off on commenting about the thread group
stuff until I understand your point).

pt

Paul Tarvydas wrote:

> I think that this analysis is based on a faulty base assumption. You seem
> to assume that I have to build this in assembly language and that you get
> to use a kernel plus a programming language suited for your paradigm.

My comments were meant to what you described about your Lisp
implementation. I think I understand the system on embedded hardware with
interrupts, but for the Lisp implementation you wrote that they are not
really threads, but you need a cooperative multitasking and every process
needs to get-in get-out quick. I interpreted "get-out" as returning from a
function call.

Maybe some example code could help, how you would write the telegram
problem with your Lisp implementation, maybe with single chars, like you
suggested.

>> Another disadvantage is, that you don't utilize multi-core CPUs very well.
>
> Why do you say this?

Because you wrote, that your Lisp implementation is not preemptive, which
implicits for me that you use a single thread for the scheduler, but maybe
I'm wrong.

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

George Neuner wrote:

> on the ideas in Hoare's book, "Communicating Sequential Processes" - a
> good read if you haven't already.

Both, CSP and Occam are referenced in my papers that I posted links to
earlier in this thread.

pt

Paul Tarvydas <tarvydas@visualframeworksinc.com> wrote:
+---------------
| At the assembler level, I think that I have to save less state than the
| process-based method. Preemption requires that every cpu register be saved
| on the stack and that the stack pointer be changed. My method needs to
| save an index in a state variable. The rest of registers don't need to be
| saved (because, (a) either the unit of work has been completed (getting
| out) and only the "next state" needs to be saved, or (b) a hardware
| interrupt has occurred and the hardware does (at least some of) the saving
| for me).
+---------------

This sounds similar to the approach I took when designing the kernel
of the "WSched" multi-tasking communications operating system for
the DEC PDP-8 [augmented with DCA's proprietary "Bus Window" MMU]
back at Digital Communications Associates (DCA) in Atlanta in 1972.

The entire O/S ran with interrupts *off*[1], but by fiat [enforced
during design reviews!] each task was required to execute one
"@SERVICE" macro[2] at *least* once every 200 machine cycles[3]
and at least once per trip through every data-dependent loop
[such as traversing an arbitrary-length linked list]. This ensured
that the scheduler ["event dispatcher" in modern parlence] got a
chance to re-prioritorize things at least every 200 cycles (~250 us)
if a new event had arrived from the outside world [such as a user-
typed character]. The *only* state preserved by the "@SERVICE" macro
was the current PC and the current "Bus Window" mapping ["page table
base pointer", in modern parlence].

Newly-arrived events were linked to the end of the list (task queue)
associated with their priority, and contained the PC of the task
responsible for servicing them. A task pre-empted by an "@SERVICE"
became an new "event" whose "task" was simply to return to the PC
after the "@SERVICE" which pre-empted it. Task scheduling was thus
trivial -- simply run the first task on the highest-priority non-empty
task queue. [There were only 3 or 4 priorities, hence only 3 or 4
task queues]

This design [plus the "Bus Window", which made manipulating the
8-word "chunks" which were the basic units of allocation *much*
easier] was *extremely* efficient -- average CPU consumption to
get a character into and *out* of the system was only ~100 us
(or ~83 cycles) -- and we were able to keep over a hundred local
user terminals plus several remote terminal-concentrator network
lines serviced using a cheap, "slow", little PDP-8... much to the
consternation of the competition [DEC themselves!] who were using
the more expensive, much faster, "obviously better" DEC PDP-11 CPU
for the same job. ;-}


-Rob

[1] Except that the "@SERVICE" macro[2] turned interrupts on for
exactly *one* instruction as a cheap way to poll the common bus
interrupt request line. It was cheaper even than testing for
"any interrupt" then conditionally calling the scheduler, since
the interrupt hardware did both the test & the "call" for us.

[2] Using the "8BAL" macro pre-processor [think "m4", but nicer syntax].
"@SERVICE" was defined as "ION; CLA; IOF", and tested whether
anyone was pulling on the Omnibus's interrupt request line. The
ION (Interupt ON) instruction had a one-cycle delay built into it
[for reasons having to do with the PDP-8's instruction set], which
was why the CLA (CLear Accumulator) was there, and "@SERVICE" was
thus *documented* to clear the AC [which was often needed on the
PDP-8 anyway].

[3] The DEC PDP-8's instuction set was very simple, and programmers
could trivially manually count machine cycles taken by instructions,
as there were only a handful of different cases: basic instructions
were one cycle; memory-reference added a cycle; indirection during
memory-reference added a cycle; "auto-incrementing" during indirection
added a cycle, and storing back into memory added a cycle. [The only
instruction that could do *all* of those was "ISZ @FOO", where "FOO"
was one of the eight same-page magic auto-incrementing locations
(locations #o10-#o17), and cost 5 cycles.]

Well, actually, on the PDP-8/e reading from memory took 1.2 us
and writing took 1.4 us, so technically there were *two* possible
cycle lengths, but we didn't need to be that precise and so didn't
bother with the difference. ;-}

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

Rob Warnock wrote:

> This sounds similar to the approach I took when designing the kernel

It wouldn't surprise me. I think that Paul Morrison says that FBP was used
in production in the '60's.

The meme has been around for a while. I think that it is increasing in
strength.

Our variant doesn't even need the @SERVICE call - everything tends to be
coded as state machines and the code snippets that are executed during
transitions/entries/exits are all very short.

Our original problem was that "polling" was way too inefficient. PLC's
(employing periodic polling) were being using on injection molding
machines, but a certain event ("cut-over") occurred in such a short time
span that polling strategies would completely miss the events. We had to
bolt fairly complicated code directly onto interrupts - then we discovered
that the code would be better-structured if we used state charts, then we
discovered that we might as well do all of the code that way, regardless of
whether it was bolted to an interrupt or to another piece (chain) of
software. An RTOS had been bought in, but we eventually ignored it, since
all of the real code was written below the RTOS.

pt