Kaz Kylheku <kkylheku> writes:

<snip>
>
> I worked on some projects which incorporated these FBP concepts, and
> realized it's a mess. FBP sounds good on paper, but it's
> ``impossible'' to debug.
>
> If something goes wrong---for instance, a process obtains bad data
> from somewhere---you don't have a useful call trace. The top of your
> thread called some ``getmessage'' function, which pulled the bad
> message from a queue where it was deposited by another thread that has
> since gone on to do other things.
>
<snip>
>
> The nice thing about functions is that the caller is suspended until
> the function returns, and the caller synchronously collects the return
> value. You can set breakpoints, single-step the entire process if
> necessary, and view the activation chain.
>

I agree that this does create some issues and doesn't
necessarily fit well with traditional debugging paradigms, but I'm not
sure it follows that therefore it is a bad paradigm/methodology.

Given the developments in multi-core hardware, threads, multi processor
systems, distributed systems, greater use of network based services
etc, I think the whole model of software as largely synchronous function
calls may be too limiting a paradigm for how we design, write and debug
software. We probably need to develop new techniques in the same way we
had to develop new techniques in how we structure and debug software as
our software and the problems they addressed became more omplex and
unstructured spaghetti code showed its limitations as complexity
increased.

I wouldn't argue that this is the one and only paradigm for softwrre
development, but it may be, for a certain class of problems, a better
paradigm even if it creates a need to approach debugging from a new
direction.

> A reuse rate of 97% means that you really don't have a new project.
> You just tweaked something in the existing project and /called/ it a
> new project.

Making a statement of a reuse rate of x% is meaningless without details
of how much requirements differ, so I agree that it doesn't mean
anything. However, for the same reasons, you can't also state that it wasn't a new project
either.


> If your ``new'' project has 97% of the code of the ``old'' one, you've
> only done a minimal amount of new work. This could only be because the
> requirements have only changed in a trivial way.
>

Thats just an assumption. It is possible the claims are true and the
projects had very different requirements and the approach does provide
this type of advantage. Without details of how long the original project
took and to what extent the requirements differ, you can't really make
any concise statement based on just the amount of reuse. It is possible
the original project took 10 times as long to develop as it would have
taken with a different approach and at the end, there was such a lot of
code,, libraries and black boxes that you could solve any problem with
just 3% extra coding (that 3% could take another 4 years of course - it
is all relative).



> Or it could also be that 97% of your effort was spent in developing
> infrastructure whose details are irrelevant to the problem domain. If
> Common Lisp is 99 times bigger than the average program you write,
> then each time you write a new program, you can claim 99% reuse. :)

Exactly. This doesn't say anything about the approach, only about the
lack of sufficient information to make a call.

Tim

Frank Buss wrote:

> For an embedded system with interrupts this sounds like it is not too
> difficult, but how did you do this with Lispworks in Windows? I assume you
> don't create 1M threads, which would be really slow.

Short answer: I write a kernelette (or a class) that shepherds events from
output queues to input queues between parts. The existence of the
kernelette "maps" call-return semantics into an input-driven (reactive)
paradigm. Then it all just works. The components are so cheap that you
can have 10,000's of them lying around.

Longer answer: It really is as simple as above, but I suspect that you want
me to elucidate further :-).

It's a cheezy form of cooperative multi-tasking, where each "thread"
promises to "get in and get out quickly". (From what I've read, stackless
python is similar).

Each part has an input queue (of pending incoming events), an output queue,
a busy flag, some code (either hierarchically more networks of parts, or
state diagrams, or textual code), some state and local data and an entry
point called by the kernelette to begin processing the input queue. When
called, the part processes an (or all[*]) input event(s) and possibly
produces output events, which are queued on the output queue. On exit, the
output queue is processed (the events are delivered to their destinations
using the wiring tables) and a chain reaction of input-event processing
occurs.

That's it in a nutshell. This allows you to write "completely"
encapsulated[+] reactive components that communicate via events and don't
need their own (often preallocated) stacks (like in fully preemptive
multi-processing). As you can see, the cost of these components is more
like the cost of an "object" rather than a (full-blown) "process". You can
have 10,000's of these things lying around, since they don't consume cpu
until they are activated. Activation is cheaper than a full-blown context
switch (pop queue, case on "pin" index).

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.

pt

[*] Whether a part eats one event at a time or loops through all events is a
scheduling decision. It matters most when tuning embedded systems.

[+] Total encapsulation is achieved only if the internal action (textual)
language is controlled / integrated into the system. You can use an
off-the-shelf language, like CL, for the code snippets, but you have to
promise to play nice.

Tim X wrote:

> Given the developments in multi-core hardware, threads, multi processor
> systems, distributed systems, greater use of network based services
> etc, I think the whole model of software as largely synchronous function
> calls may be too limiting a paradigm for how we design, write and debug
> software. We probably need to develop new techniques in the same way we
> had to develop new techniques in how we structure and debug software as
> our software and the problems they addressed became more omplex and
> unstructured spaghetti code showed its limitations as complexity
> increased.

I agree, but note that you are overlooking the idea of re-using "old"
techniques. Reactive programming enables the borrowing of well-worn
techniques from the hardware world:

- unit test / test circuits - reactive programming makes unit test very
easy - create a stimulus unit that sends events into the unit, create an
observer that watches the outputs of the reactive unit and compares them
with expected values ; it's easier in the reactive paradigm because
input-driven code doesn't implicitly drag along large libraries of hidden
stuff that it's dependent upon

- test probes - "tap" watchpoints into the reactive circuit and observe
values over time (have the Cells people tried this?)

- back-to-back testing - use two copies of the same component, copy 1 drives
inputs into copy 2, copy 2 sends its responses back to copy 1

- techniques for handling race conditions

- reuse of "patterns" that don't naturally occur to people when thinking in
the call-return paradigm, e.g. "daisy chain" for resource management,
multiplex / demultiplex for load balancing.

pt

Paul Tarvydas wrote:
> Tim X wrote:
>>
>
> I agree, but note that you are overlooking the idea of re-using "old"
> techniques. Reactive programming enables the borrowing of well-worn
> techniques from the hardware world:
>
> - unit test / test circuits - reactive programming makes unit test very
> easy - create a stimulus unit that sends events into the unit, create an
> observer that watches the outputs of the reactive unit and compares them
> with expected values ; it's easier in the reactive paradigm because
> input-driven code doesn't implicitly drag along large libraries of hidden
> stuff that it's dependent upon
>
> - test probes - "tap" watchpoints into the reactive circuit and observe
> values over time (have the Cells people tried this?)

defobserver? :) That is a normal part of programming with Cells, eg, how
a widget color attribute triggers a redraw event when it takes on a new
color. Observers are generic in Standard Cells (via a GF specialized on
slot name, instance, new-value, old-value, and the kitchen sink) but in
my toy RDF implementation observers accidentally became Cell-specific.
Not sure that matters here. Anyway, yeah, ready and available for
debugging and other kinds of program analysis.

kt
[..]

Sohail Somani wrote:
> Ken Tilton wrote:
>
>> Yep. I went into final approach about six weeks ago, committed to
>> doing the absolute minimum to have something in folks' hands by, oh,
>> July 1. It's a lot more fun programming when I can get to something
>> tricky and just say f**k it, they'll live. :)
>> If you want to put your mouth where your foot is:
>
> [..]
>
> That is my official invitation to you.
>

I have reconsidered. How do I accept? (Help a dinosaur.) I gather any
blog entry should be tagged 30day. Anything else?

kt

Ken Tilton wrote:
>> Sohail Somani wrote:
>
> I have reconsidered. How do I accept? (Help a dinosaur.) I gather any
> blog entry should be tagged 30day. Anything else?

Yep.

I've added your feed to the aggregate feed:
http://feeds.feedburner.com/30dayers

If you tag your posts with "30day" it should show up here:

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.

An initial post declaring that you are throwing your hat in the ring
would get other people caught up on what you are up to. I'm sure you
will draw much interest with your.. interesting... writing style :-)

Best of luck!

Sohail

Sohail Somani wrote:
> Ken Tilton wrote:
>>
>>
>> Sohail Somani wrote:

>>> That is my official invitation to you.
>>>
>>
>> I have reconsidered. How do I accept? (Help a dinosaur.) I gather any
>> blog entry should be tagged 30day. Anything else?
>
> Yep.

Err that is, no you should not need to do anything else.

Another reason I got fired from customer support.

Kidding.

Sohail Somani wrote:
> Ken Tilton wrote:
>>
> Yep.
>
> I've added your feed to the aggregate feed:
> [..]
>
> If you tag your posts with "30day" it should show up here:
>
> [..]
>
> 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

kt
[..]

George Neuner wrote:

> On Thu, 29 May 2008 11:26:53 -0400, Paul Tarvydas
> <tarvydas> 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.

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.

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).

>>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 but simply

[If that's true, why was my National Semiconductor catalogue from the
late '70's so much thinner than one from the '80's?]

> 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.

>>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").

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?

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.

>>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.

pt

Ken Tilton wrote:
>> Sohail Somani wrote:
>> [..]
>>
>> 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:
>
> [..]

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 ;-)

Sohail Somani wrote:
> Ken Tilton wrote:
>>
>
> 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

Ken Tilton wrote:
>> Sohail Somani wrote:
>
> 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.

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.

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

>George Neuner wrote:
>
>> On Thu, 29 May 2008 11:26:53 -0400, Paul Tarvydas
>> <tarvydas> 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