Cells compared to Flow-Based Programming

Frank Buss wrote:

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

Ah - your question is more clear to me now.

In fact, *neither* implementation is preemptive. The embedded kernel *can*
use different interrupts to "stack" a few levels of code, but we found in
practice that it was better to attach all code to the same interrupt level
and to eschew "priorities".

I see that what I didn't say is that the workstation kernels were used for
simulation or simply for allowing us to program in the reactive paradigm -
the true multi-processing aspects did not concern us on the workstation
implementations.

If I were to write a multi-cpu / multi-core implementation, I would place
one kernel on each cpu - i.e. one independent thread on each cpu (which is
the best that you can do with any approach - you can never have more than
one cpu per cpu, and you only waste cpu cycles by layering fake "processes"
onto a cpu). [If this previous sentence doesn't make sense, wait for an
example...]

> Maybe some example code could help, how you would write the telegram

Good suggestion. I'll cobble something together.

pt

> > 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?
> From: Paul Tarvydas <tarvy...@visualframeworksinc.com>
> The difference is : synchronization.

Synchronization is good if you need to be sure data is available
before you try to process from it. Now you can beg the question by
setting up a continuation or callback where something will use the
data whenever it finally becomes available, but still there must be
some kind of synchronization between availability of the data and
activation of the callback or continuation.

> A function/procedure passes a message, then returns a set of
> values. All the while that the function/procedure is running, the
> caller is stalled waiting for an answer (the return), even if it
> doesn't really care about the answer.

Wrong, if you have multi-processing in the first place, with the
essential primitives: Fork Join and PollStatus. There's no need for
message passing. There's only need for first-class handles on
processes with primitives for doing those three essential
primitives with them.

If you need to invoke two tasks, and you won't need either result
before calling the other, then you FORK your process, and invoke
each task from a different thread. Then at the point where you need
*both* final results to be somehow combined, that's where you JOIN
the two threads. If you can operate either with or without a
particular result, but having it is better than not having it, you
can poll the process that produces that result to see if it's
gotten to that point yet, and if so use the result, else go on
without it.

> In message passing (event sending, as I prefer to call it), the
> caller does not wait for a response.

In forked threads, only the sub-caller that needs the result for
further computation waits for it, the other sub-caller that if off
doing something else at the same time does *not* wait for it. How
is the multi-threaded procedural paradigm any different from the
message-passing paradigm, except that the multi-threaded procedural
paradigm has a better view of dependencies via the Join and Poll
primitives? (I envision a boolean-vector Poll interface: When
activing a process that you'll need to poll later to learn of
completion of various milestones, you pass it a boolean vector that
you have a handle on, all bits initially FALSE, and you set it to
turn on various elements when the corresponding milestones are
completed. The interface between the sub-process and the boolean
vector allows turning on bits but not turning off bits, so once a
bit is on you won't be stabbed in the back by the sub-process
changing its mind later. The vector is actualy extra-boolean,
which might be implemented by a NULL pointer that can *once* be set
to a non-NULL return value.)

> You cannot do that with function calls unless you invent
> cumbersome extraneous baggage (e.g. an rtos or an event loop or the
> utterly insane concept of rpc's).

Well if you have a single-threaded procedural system, then indeed
you can't fork threads, so you need to explicitly run an event
loop, and make sure each emulated thread pauses at frequent
intervals to avoid hogging the CPU. On the Macintosh under System
6, the system did something like that. Applications could be paused
only at specific points where the application did a system call. If
any application ran a tight loop that didn't do even one system
call the whole time, it'd lock the machine until it finished. In
other systems, CPU clock interrupts are enabled, forcing every
application to be interruptable at regular intervals (except during
critical sections of code when interrupts are disabled; an
application that hung inside a critical section forever would
likewise hang the CPU, but that's less likely than using the Mac
way.) On systems with virtual machines, there's no need for user
applications to disable interrupts at all, because if the
application is inside an application-level critical section the
system can nevertheless interrupt the virtual machine and save its
entire state and run another application for a while.

But IMO this is moot because modern procedural languages (on modern
operating systems such as Linux) support multiple threads with
operating-system support to automatically timeshare the various
threads. No event loop is needed there.

> In reactive programming, NOTHING is synchronized unless the
> programmer makes it so.

OK, at this point I gotta look up that jargon on Google/WikiPedia:

<http://www-sop.inria.fr/meije/rp/>
Nice menu of implementations of the idea, but no overall definition.

<http://www-sop.inria.fr/meije/rp/generalPresentation/index.html>
OK, this is more what I need to get started with understanding the idea.
Reactive Programming considers software systems whose behaviors
basically consist in reacting to activations. These systems are often
called reactive systems. System reactions, also called instants, can
take various forms, for example sequences of successive phases, or
oscillations eventually leading to stabilization. ...

Is that a good explanation of what you're talking about?

I think my proposed feedback-loop methodology for finding narrower
and narrower nested interval-arithmetic approximates to fixed
points of iterators (usually some form of Newton's method) would
fit into that paradigm. It can run in a single process, always
chosing the sub-call that is most likely to result in narrowing the
parent interval, although in close calls it would be nice to be
able to fork the process and narrow both input intervals at the
same time and whichever returns first would get first chance to
narrow the parent interval.

* The possibility to dynamically create and run new components
during execution eases the programming task, as it does not impose
a system to have a static maximum number of running components.
That sounds exactly like the Fork (Split) primitive of ordinary
multi-processing, which works fine within the procedural-programming style.

The basic idea of Reactive-C was to propose a programming style close
to C, in which program behaviors are defined in terms of reactions to
activations. Reactive-C programs can react differently when activated
for the first time, for the second time, and so on. Thus a new
dimension appears for the programmer: the logical time induced by the
sequence of activations, each pair of activation/reaction defining one
instant.
I see a possible problem or two: What if the 'program' is still
running from a earlier activation when somebody already tries to
activate it a second time. Does the second attempt **HANG** until
the processing from the first activation has completed, or is the
second attempt bundled into an activation record and put into a
queue so that the activator does't need to wait until that second
activation is complete? What if two processes each try to activate
a third process at exactly the same time? Is it a race condition as
to which activation is processed first? What if two processes try
to do the **first** activation of a third process? Which of them is
allowed to get *FIRST* priviledge and which is relegated to getting
only *SECOND* activation? Or does an attempted *FIRST* activation
always start a new instance of the program, so that if two attempts
occur at the same time then two instances are started and they run
as separate processes, with each first-activator having a handle
only on the process that *it* activated?

<http://en.wikipedia.org/wiki/Reactive_programming>
... in an imperative programming setting, a: = b + c would
mean that a is being assigned the result of b + c in the instant the
expression is evaluated. In reactive programming it could instead mean
that we set up a dynamic data-flow from b and c to a. whenever the
value of c or b is changed, then a is automatically updated.

That's actually the inverse of my interval-arithmetic proposal, and
for that purpose it seems inferior because it performs excessive
computation that nobody needs yet and might never need.

Consider for example Newton's method for interval arithmetic:
We set up a starting interval which isolates one zero
(x-axis-crossing-point) of a function narrow enough that Newton's
method applied to that interval will approximately double the
number of signifant digits (square the error fraction).
Then we hook Newton's method to feed that interval back to itself,
so that each time Newton's method is called that interval is made
square as accurate.

By my method, anybody who needs that value checks if it's already
accurate enough, and if so just uses the current interval, else it
specifies a recursive call to Newton's method then upon return
checks again to see if it's accurate enough now. Anyone just
wanting "more" accuracy will unconditionally call Newton's method
once.

By reactive programming, once the feedback loop is activated, the
Newton's method process will run endlessly
(because its input has changed, it will be run, which changes its
output, which feeds back to its input, causing its input to be
changed again, causing it to be activated again, and so on and so
on and so on),
repeatedly squaring the accuracy, thus repeatedly doubling the
amount of storage needed to hold the more-accurate result. Program
size grows exponentially in just this one component even if nobody
really need more than twenty or thirty significant digits here.
Within seconds the working set for this one proceess exceeds actual
5 gigabytes of RAM, throwing virtual memory for the whole system
into thrashing, and then eventually the system crashes because it
has run out of available 500 gigabytes swap space.

Was it McCarthy who stated that the only important thing about a
program is what output it produces, that nothing should be computed
unless it will affect output? My interval arithmetic
lazy-evaluation evaluate-only-as-much-as-neededwould seem to
satisfy McCarthy's. statement, whereas reactive programming would
seem to violate it. The difference is between McCarthy's
output-driven processing and reactive programming's input-driven
processing. McCarthy (and I) do only as much computing as needed to
produce the required output. Reactive programming does all
computing that is allowed by the input, which may be horrendously
more orders of magnitude than is cost effective for required
output. Is that a correct comparison??

Now there's one disadvantage of the extreme McCarthy/Maas idea,
latency. If we wait until somebody asks for something before it's
computed, there may be a delay before it's available, whereas if we
pre-compute something in anticipation that somebody might ask for
it, then ideally it's already available for immediate return
whenever somebody finally does ask for it. It seems silly to sit
idle waiting for somebody to ask something, if the computer can
predict likely things somebody might want and use idle cycles to
pre-compute them and stage them for immediate retrieval. So perhaps
a slight variation of my proposed idea would be to use idle cycles
to (starting from the top) shrink the intervals just a little bit
more than previously asked for. Still, each level in the network
leading toward output is interval-shruken only a little bit at a
time, and after a reasonable amount of interval-shrinkage occurs
maybe it's better to have idle cycles than to fill up all of memory
computing more and more accurate results that are less and less
likely to actually be wanted.

> In call-return programming (functional, procedural, etc)
> EVERYTHING is synchronized - always.

Only in single-thread programming. Everything in a given thread is
synchronized to its caller and anything it calls, but separate
threads don't need to be synchronized except at the point where a
JOIN is needed to merge results from different threads.

> People are currently wracking their brains trying to figure out
> how to program multi-core cpu's. They think that it's a hard
> problem. But only because they cannot think outside of the
> call-return box.

I think you're getting into strawman territory now.

Call-return, to top-down lazy-traverse a network of data
dependencies (including Newton's method etc. feedback loops), seems
to me quite sufficient for interval arithmetic and other
data/processing.

Machine interupts for device events (mouse click etc.), or a
background clock-driven device poll loop, either of which then does
a call-return to the appropriate event-handler for the appropriate
widget, seem sufficient to handle GUIs. (Ok, I'll admit that *some*
of the event handling is done asynchronously, where one widget
passes an activation to another widget and doesn't wait for a done
signal before either doing something else or going idle to wait
another local event. But at least it waits for the activated widget
to reply as to whether the activation was accepted or not??)

CGI (or PHP, JSP, RMI etc.) to connect clients to servers, together
with a call-return linkage to a relational database to manage all
persistent data, seems sufficient to handle
multi-machine-across-network applications.

Now maybe that doesn't cover all possible computer applications,
but it covers more than you seem to admit.

As to your derogatory implications that people who write software
don't assure their customers that the software will work: Would you
be willing to hire me to work for you, on the condition that we
block+fund the work according to use cases, and you don't pay me
for a particular use case until and unless it works as specified
(and all previously-paid use cases within the same application
continue to work, interoperating with the new use case)?

Paul Tarvydas <tarvydas@visualframeworksinc.com> wrote:
+---------------
| 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.
+---------------

To some extent IBM's PARS (Programmed Airline Reservation System)
[later broken into APPS and ACP ("Airline Control Program"), the
latter later renamed TCP ("Transaction Processing Facility")]
used many of the same principles, see:

http://en.wikipedia.org/wiki/Airlines_Control_Program
http://www.blackbeard.com/tpf/tpfhist.htm

[For many years Bank of America and other banks used TPF to run
the centralized part of their ATM applications.]

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

That's what was nice about @SERVICE: you just stuck it in someplace
where you already needed a CLA [which happens a lot in PDP-8 code,
since there is no LOAD -- you have to clear (CLA) then add (TAD)],
and if there was no pending interrupt request then it was "free".
[Well, nearly; it cost 3 cycles instead of true CLA's 1 cycle.]

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

Well, much of our code *was* state machines, with the edges sometimes
being new events and sometimes being just the continuations resulting
from the required @SERVICE points [recall that I said at least one was
mandatory in every indefinite-length loop].

+---------------
| An RTOS had been bought in, but we eventually ignored it,
| since all of the real code was written below the RTOS.
+---------------

Heh! Our WSCHED *was* the "RTOS", if you're going to use those terms.
Someday I should do a full write-up of WSCHED, but here are some
salient points:

- The "Bus Window" MMU redefined the first 64 words of each PDP-8
"field" [4 kwords] as being virtual memory: 8 pages (we called
them "chunks") of 8 words each. The virtual mapping for each field
was the *same*, so if you put some data into the virtually-addressed
area and did a cross-field subroutine call the data was still there
in the same relative locations in the target field, which made
cross-field calls *much* faster. *Only* the first 64 words of
each field were virtual; all other addresses remained as before.

- The "page table" was thus itself an 8-word chunk and by software
convention was always mapped into the first virtual page (loc. 0-7)
[trivially done by having word 0 of each page table contain the
page number of that page table itself], so that you could change
the currently-active mappings for locations #o10-#o77 by depositing
the new mappings directly into locations 1-7. [The MMU snooped such
stores and copied them into its TLB automagically.]

- This 8-word chunkiness was pervasive throughout the data structures
of the system. *All* dynamic data was organized in chunk-sized pieces,
and linked lists were constructed by having word 7 of a chunk contain
the chunk (page) number of the next chunk in the list. If a chunk in
such a list was currently mapped in (virtual) locations #o70-77, one
could remap those locations to the next chunk in the list with only
two instructions [assuming the AC was clear, almost always the case] --
"TAD 77 ; DCA 7". That took word 7 of the current chunk and slammed it
into the 7th mapping of the current page table. Et voila!

- The application (data communications) layer of WSCHED was organized
around the MMU as a sort of "software crossbar" between some input
device (say, UART#73) and some output device (say, network trunk #5
logical channel #17). Virtual pages 1-3 were owned by the "source",
while pages 4-6 were owned by the "destination". [Page 7 was universally
a "scratch" page, mainly used as a temp for linked-list traversals,
as above.] A reverse mapping -- flipping the roles of "source" and
"destination" always existed at a fixed place in the "destination"
area, so one could flip roles in two instructions -- "TAD 46; WENABL".

[Aside: When an device was not "connected" in the software crossbar,
by convention it was mapped to itself. This meant that one could
create a crossbar connection with only a six load/store pairs to
swap the "destination" mappings of the two devices, whereupon they
were suddenly "connected" as above.]

- Associated with each multi-unit device controller was a vector of
page tables (called "contexts") for the units of that controller.
So all you had to do to process some input was add the unit number
of the interrupting device to the base of the page tables for that
controller and "light the context" with a WENABL instruction, then
call the "source" input-handling subroutine whose address was at
a fixed address in the "context" (virtual area).

Anyway, not to go on *too* long [though I probably have already!],
the point being that scheduled-task control blocks were built out
of these same "chunks". When you ran a task (or a continuation from
an @SERVICE) you simply "lit its context" and then did a subroutine
return into the saved PC stored *in* the context [at yet another
fixed location in the now-active virtual memory]. Input-data-driven
"software crossbar" data flow, event-driven, state-driven, or timed
scheduled tasks -- all of these models co-existed within WSCHED and
all used the *same* dispatch mechanism! The whole thing meshed together
*quite* nicely, thank you very much. ;-} ;-}


-Rob

p.s. I have replicated the WSCHED style a number of times over the
years in various embedded network applications, except using "source"
and "destination" base or index registers (now that CPUS *have* such
things -- the PDP-8 didn't!) instead of a special-purpose MMU [starting
with the Zilog Z-80, in which we used the X & Y registers for "source"
and "destination"]. The "software crossbar" style is still quite useful,
as is the interrupt-off "very-light-weight RTOS" style.

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

> From: George Neuner <gneuner2/@/comcast.net>
(compared to hardware designers
> few developers know how to formally proof software and even fewer
> bother to do it except when the results will be published.

Given that it's not even possible to proof hardware, because
quantum mechanics and small impurities in materials production and
variation in physical assembly actions all make the properties of a
hardware device impossible to prove within bounds, and anything
proven from such an assumption would then be GIGO. At best
statistical estimates of success rate and MTBF (Mean Time Between
Failure) can be predicted on the basis of experience. Accordingly
complaining that software isn't formaly proofed seems an unfair
complaint in this hardware-vs-software discussion.

Perhaps a more appropriate metaphor would be the legal system, of
adversarial contestants, one to show evidence for something, the
other to find flaws in the evidence leading to reasonable doubt. In
the software contest, perhaps each unit (function, method, etc.)
can be specified per initial state assumed, D/P process that
occurs, and final state claimed if the initial state was within
spec. The person claiming a unit is "working" could post a demo of
the unit for testing, by both automated test rigs (some written by
an adversary) and manual/interactive attempts to make the unit
fail. If the unit has withstood a reasonable time period of such
testing, then it can be trusted. With formal specs for starting
state and final state, automated verification of matching states of
output from one unit to input of another unit, and automated
management of a whole network of such dependencies, simple
connections of the specs between units can be used to prove that
combinations would work too, without needing to test each
combination. (Maybe you're saying that the overall system for
managing such analysis of multi-unit software isn't available "off
the shelf" for popular programming languages, so it's not worth
people bothering to even try that methodology except if they're
going to publish the result in a scholarly ournal?)

> It's also the case that some popular programming languages have
> features that impede easy analysis.

It's not necessary to *use* such difficult-to-analyze features, you
know? If the parse tree for the software is readily available, as
it *is* for Lisp (and has been since the very start nearly fifty
years ago), it's possible to automatically analyze the software to
check what features it uses and warn if any difficult-to-analyze
feature is used, and not exactly where it's used. Then anyone
wishing to prove that the different individually-tested units can
be proven to work together, can attempt to modify the code (if
necessary) to eliminate use of any difficult-to-analyze feature,
and if successful then apply whatever multi-unit-analyzer software
is available. Have you investigated that idea to see how feasible
it might be? (Note that different features might cause difficulty
with different methods of multi-unit analysis, so a different
difficult-code detector might be needed for a different
multi-unit-analysis tool.)

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

Back to that metaphor: Software is nearly *always* assembled from
low-level units that come from a catalog, namely the "Principles of
Operation" manual for the CPU when writing machine/assembly
language code, or the "API documentation" when writing code in a
higher-level language. For example, we have the Common Lisp
Hyper-Spec <http://www.isr.ist.utl.pt/library/docs/HyperSpec/Front/>
and the JavaDoc <http://java.sun.com/j2se/1.4.2/docs/api/index.html>
as "catalogs" of what API units are available for use (and
well-tested and believed to be working) in our application-level
software.

> Software developers, OTOH, do invent ad-hoc symbolism and
> accompanying predicate systems every time they write a program

All within the framework provided by the API (or Principles of
Operation) manual. Nothing is invented do novo except *intentions*
of use of some existing type of data. Even new classes in CLOS or
Java are sub-classes of an existing class, with well-specified
technology for introducing specific features within the general
capability. provided by the API. Application programmers do *not*
delve deep into the underlying machine language to defeat the
restrictions of the API, much less modify the hardware to generate
new machine language instructions to take advantage of.
So I believe here you're making much ado about nothing.

> usually under-specified, almost always incomplete,

Now *this* is a valid point. During rapid prototyping, both true
R&D to explore what's easy to accomplish via new algrithms, and
trying to understand user requirements by quickly implementing what
you think the user wants to see if that's what the user really
wants before fixing the design too firmly, it's actualy an
advantage to keep specs flexibie and ambiguous and be willing to
change them as you learn new things about what's doable or what the
user wants respectively. Only later after you think you really do
have it right (new algorithm "works" in a useful way, or user is
happy with the way your prototype demo works), *then* is the time
to write up the formal specs and make sure the specs match what the
user (or researcher) wants accomplished and also make sure the
software satisfies the specs. If formal specs aren't written up at
this time, or the specs are substantially incomplete, I agree the
programmer has been negligent, and if the supervisor/manager of the
pragrammer fails to take the time to review the specs, that person
is negligent. (In a single-person project, such as I've been doing
while unemployed, it'd be nice to find a peer to review my specs,
but alas the one time recently I posted some specs for review
nobody bothered to say anything except a vague remark that my specs
are incomplete, without bothering to tell me what aspect of them is
allegedly incomplete, so I've gotten no feedback to improve my
specs.)

As a regular practice, I put documentation at the front of each
function definition and in front of or alongside each global
declaration. I use semicolon comments instead of CL documentation
strings, because it's easier to format them, and because I don't
have to include them each time I copy-and-paste a modified function
definition from the local edit buffer across a dialup modem into
the remote Unix shell where CMUCL is running. But if I ever were to
make any of my code public
(if anybody ever wanted it and were willing to somehow pay me for
my work, either with money or a job offer or public accolades),
I'd be glad to convert my semicolon-comments into a documentation
string that is retrievable by (DESCRIBE <symbolThatNamesTheFunction>).
In that per-function documentation I state what global situation if
anything is assumed, then what each parameter is supposed to be,
then what the function does (and in some cases *how* it does it),
and finally what side effects
(either globally, or locally within a passed data structure)
and/or return value(s) there is/are. It's all in English of course,
nothing formal that could be automatically verified, but I'd be
glad to convert it to any formal specification langyage anyone
wants if they are willing to pay me for that work.

> rarely coverage tested and limited to "expected" inputs.

Personally, I test my code for both expected cases and out-of-bounds
values (with type/range checking of parameters whenever it seems reasoanble).
In particular, when developing line at a time, I test each error message
itself *as*if* that condition had occurred before I test the conditional
(when SomethingWrong (error ...)) or (unless EverythingGood (error ...)).
I find that mistakes in composing the error message and parameters
to it, usually missing parameters or ugly formatting, are very very
common, and getting them fixed before I move on is best practice.

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

How about a syntax-free development and archival system, which
automatically lists which known programming languages support any
given module and offers a menu for converting the syntax-free
software to whichever of the known programming languages the user
wishes to express it in (port it to)? I've proposed this idea
several times recently, but nobody else has expressed any serious
interest.

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

If you like my syntax-free idea, would volunteer to offer me
emotional support for my idea and also brainstorm with me to work
out the details of the design and also perform beta tests on any
code I write to implement the idea per our agreed-upon design?

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

Except that when a merge happens the new owner convenient forgets
any promises made by the previous company. For example, I opened an
account with Northern California Savings, because they had a
wonderful commercial on TV with a chain of dominos representing a
person's life time, which comes to an end at the end of the domino
chain, plus the fact they offered me free cheque printing for the
lifetime of the account. They were bought by Great Western Savings,
which honored the promise, which was later bought by Washington
Mutual which refused to honor the promise, started charging me for
cheque printing.

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

Back to that metaphor: I'd be glad to replace any unit of software
that after sale fails to perform as I claimed, given that the
underlying Common Lisp system and underlying operating system
aren't at fault.
(A nice thing about software is that if a whole batch of copies of
a software unit all fail, only one replacement needs be provided,
and can then be simply copied to replace all the other copies that
were also faulty. It's not like a food recall or chip recall where
massive quantities of defective product must be physically returned
to the manufacturer who then must recycle or land-fill etc.)

> Component software is a great idea but intractably hard in practice.

Do you mean that setting up formal specs for *all* the functions in
Common Lisp or *all* the classes/methods in Java etc. is
intractably hard (I would agree there), or that even doing formal
specs for a relatively well-behaved subset is intractably hard
(I might disagree with you if that's what you mean, but I'd need
to see you clearly state what you are saying before I post formal
rebuttal).

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

Is any decent-sized subset of the Java 1.3 or 1.4 API suitable?

> Neither is .NET, or Corba, or COM or anything I've yet seen.

How about a subset of Common Lisp??

> From: Frank Buss <f...@frank-buss.de>
> 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.

No, you only need a state parameter for each continuation that has
internal state, and probably that would be inside the continuation
anyway so you don't have to add anything new after you already have
the continuation (except the persistent handle on that continuation).

And you don't need anything maintained in the main function except
handles on continuations that are directly kept by the main
function. Other continuation handles can be kept elsewhere, in
whichever *other* continuation needs to keep it available for local
use. And return values can contain handles on other continuations,
which are immediately passed as parameters to other continuations,
so many handles don't need to actually be kept anywhere long.
For many D/P applications the main function needn't deal with
continuations at all. It just calls a function to do input
processing, then passes the return value (a record containing a
continuation for further input processing and the accumulated input
data so-far) to the function that does the main processing, then
passes the return value from it to the function that does output
generation (report writing). During debugging it might be written as:
(defun main (sysargs)
(prog (inrec outrec)
(setq inrec (process-input sysargs))
(setq outrec (main-processing inrec))
(generate-output outrec)
(return 0)
))
After debugging it might be collapsed to:
(defun main (sysargs)
(generate-output (main-processing (process-input sysargs)))
0
)
Deep inside the three functions that are called would be all the
code that explicitly instantiates continuations and steps them as
needed and builds a record containing a handle on the continuation
and later code that picks fields out of the passed record.

> 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 [sic]
> with a DSL and some macros. The result would be a cooperative
> system like Paul Tarvydas described.

Sure, a package to add another layer of API to support a DSL for
this sort of thing, within an existing programming language such as
CL or Java, would be reasonable.

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

Hopefully you think about *both* data and processes. Without data
there's nothing to process, but without processes there's just
static data sitting there like a Web page that nobody ever loads
into a browser.

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

Repeating myself, concentrating on just the front, or rear, wheel
of a bicycle, at the expense of the other, isn't a good way to
maintain a bicycle. Likewise concentrating on only data and
ignoring processing is likewise only half correct. A bicycle needs
both wheels, neither is more important, and data-processing
software needs both data and processing.

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

I actually debug my mostly-procedural code that way, working from
input forward to output, except that I develop my code bottom-up
instead of haywire of network connectionsas much as possible. But
my "dataflow" software actually is somewhat like you describe, but
again all in a procedural paradigm: I have a separate function to
make sure each control point in the data flow is not just generated
but in fact up to date with respect to any earlier-in-flow data
that it depends on.
(And when I make an incompatible change in some algorithm for
producing some particular data, I "hardware" a timestamp in that
control point so that any output that was computed before the
incompatible change is automatically regarded as "out of date",
forcing it and any data depending on it to be recomputed the next
time such data is requested. Here's an actual example:
;... set date1 and date2 to UT timestamps of the two inputs ...
(setq insym (make-symbol "LABELS+PHPROPS")) ;make JOIN of the two inputs
(length (setf (get insym ATA) ...))
(setf (get insym ATE)
(max date1 date2 3419829547 ;When GR installed to replace 01
3419834222 ;When closure bug fixed
3419916361 ;When mustkeep flag eliminated
))
)
So the haywire (graph) of dataflow is effected by the call
relationships between these various data control-points.
It would be relatively trivial to automatically process my function
definitions to trace calls of one function by another and thereby
build the actual data-flow graph as an explicit set of links, which
could then be printed in some graphical form
(that last part is more difficult, similar to automatic circuit
layout, if you want to minimize the number of wires that cross so
that the output will be visually legible).

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

Agreed. The rather trivial code to analyse the call pattern of the
functions representing the data control points, or alternately a
formal representation of the data-flow graph whereupon the function
definitions for control points are generated automatically, would
then support detecting any data loops that either are flat-out
disallowed or cause for concern that they are stable.
(With my time-stamped control points, loops must be flat-out
disallowed. With my proposed interval-arithmetic dataflow, loops
are very common, and stability must be guaranteed, i.e. don't set
up a Newton's method loop until after the zero of the function has
been narrowed enough that Newton's method is immediately provably
strictly nested output-subIntervalOf-input. Before stability has
been achieved, a more complicated algorithm that uses
divide-and-conquer would sit in that dataflow control point, to be
replaced by Newton's method after stability has been achieved.)

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

Common Lisp fuctions don't have OWN variables. Only lexical
closures (and CLOS objects) do. So what you do is write (for each
"class" of function-with-OWN-state) just one (1) FUNCTION that makes
reference to an external state record, and then each time you want
to instantiate it with separate OWN state you create a lexical
closure that contains that external state-record inside it. Doh!!

If you need more than one function sharing the same OWN state, it's
trivial to build a closure containing all those functions sharing a
single lexical variable containing the shared state. So for example
For exmaple, if you have five related functions that share an
external state, and you want to make three instances of that
set-of-five, with each set having its own separate persistent
state, you make three closures each of which has one lexical
variable and five functions.

(Are there any newbies reading this thread who are intrigued by what
I'm saying but would need me to compose a worked-out example of
such a thing before they would really understand? For example,
five functions referencing a vector of two numeric values, which do:
- Use the current first value (and the current second value
before the call) to compute a new second value, which is
returned.
- Use the current first value (and the current second value
before the call) in a different way to compute a new second
value, which is returned.
- Use the current first value (and the current second value
before the call) in yet a different way to compute a new
second value, which is returned.
- Replace the first value.
- Print the current state on the stdout.
The constructor for this closure (actually a vector of
intertwined closures) of course sets initial values for both.)

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

Does the blind person have some kind of braile-like feely "screen"
as display device, so that by feeling the "screen" with the fingers
the traces of the "wires" connecting between nodes could be
followed, and the pseudo-braile icons at each node could be felt to
identify each of them? Indeed such a BGUI would seem a good match
for a blind person who doesn't like listening to vocalized source
code syntax so much.

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

I strongly disagree in the case where the handle points to a
massive database of which the requestor will traverse only a very
small part that it needs and ignore the rest. Lazy/incremewntal-FTP
as is done with RMI/SOUP or whatever seems a better design. Of
course you can add an extra layer of query language, sort of like
how SQL works, whereby you specify in the query exactly what parts
of the data record you really need, and *only* those particular
fields are returned in on-the-fly-created records within the result
set. If you do that, then indeed transmitting immediately *all* the
fields that were requsted, instead of just a handle to them, would
be optimal.

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

Hmmm, is the claim that GC doesn't work across a network, not even
the most modern generational GC algorithms, so it's best to scrap
the whole idea of GC for such cross-machine references and revert
to C-style malloc/free or C++-style new/delete? I don't approve of
that idea. What if system A requests system B to reserve a resource
and give system A handle to it, intending to tell system B to
delete it sometime later. But system A crashes, or the application
unexpectedly quits, etc., so the DELETE command is never
transmitted, so system B holds onto the resource indefinitely?
Maybe better for system B, when in need of a local GC, to ask
system A "which of these handles are you still maintaining", and
hold onto any that system A says it still is maintaining, and GC
the rest (unless somebody else has them). If system A doesn't
respond within a reasonable time (20 minutes?), go ahead and assume
A has crashed and won't be holding onto *any* stale pointers any
longer. Summary of my proposal: For local references, do the usual
mark and sweep. For remote references, keep explicit info about
which remote machines *might* still have a reference, and query
them whenever there are no longer any local references. Since
dealing with remote references has a lot more overhead than local
references anyway, we can afford the luxury of an EQ-hash-table to
keep track of which objects might have remote references and what
machines might have those references, with a single bit in each
object to tell whether there *might* be an entry in the
EQ-hash-table worth checking during GC. A separate EQUAL-hash-table
would provide the reverse mapping, so that when it's necessary to
query a remote host about a particular reference, *all/most* of the
currently believed-active references to my machine can be inquired
about in a single network datagram, and if the query times out then
*all* such references from that host can be deleted (from the hash
tables) en masse leaving them available for GC if nobody else has
handles on them.

> From: Kaz Kylheku <kkylh...@gmail.com>
> 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.

I suffered a similar disaster a couple years ago when I tried to
write a system consisting of several mutually recursive functions
that explored a very large virtual space to generate a suitable
random element of it with continuations for never exploring the
same randomly-chosen part of the space again after it had been
exhausted. After I abandoned the project, I realized that what I
should have done is code each piece of "business logic" as a
standalone function that takes a starting state and returns a final
state, and then have a very simple toplevel recursive main program
that called the appropriate business-logic function at each step in
the recursive exploration. So if I ever find time/energy/mood to do
it again, I'll refactor all the existing code per the new design,
test each business-logic function by itself, and expect success at
long last?

> If you've ever debugged a communication protocol, you know what I mean.

I did, but it was a simple two-party point-to-point protocol, which
was easy to debug. Something like IP, with multiple levels of
domain name servers, caches containing records with expiration
dates, multiple subnets with gateways and routers, would probably
illustrate your point fine.

> You're going to end up with silly abstraction inversions.
> Programmers will want simple function calls, and they will
> emulate them by defining information packet types which are like
> functions.

*Real* programmers will think in terms of state vectors and
processing steps which change that state. :-)

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

Hey, I think that's a great advertising gimmic. Instead of giving
in to the turds that complain they want executables, we can brag
with the "sound bite" that with Common Lisp most applications
achieve 99% re-use of code, without needing to make copies of that
re-used code on the disk!! Most people just accept sound bites
without checking the devil in the details, so this may be the way
to make Common Lisp more generally popular. (Java can make the same
claim, but let's keep this advertising-gimmick secret to ourselves,
OK?) Common Lisp applications are so small relative to their power
that they can be transmitted from place to place over the InterNet
in a fraction of a second.

All we need to actually *do*, as opposed to just talking, is build
a Lisp-based Web browser (or a Lisp-based plug-in for existing Web
browsers) which supports Lisp applets just the same as how Java
applets are already supported. If we can make flashy animations
that are just a click away in a Web browser, which show an
advertising banner identifying them as using Common Lisp technology
(the same as my cellphone has a banner advertising that it uses
Java in the cartoony games that come with it), maybe people will
get curious what is this wonderful technology that is better than
JavaScript or Java applets.

Well one other thing that might be useful is making Common Lisp
more modular, so that only a barebones kernel of it need be
downloaded initially, and additional pieces are automatically
downloaded only as needed later.

Hey, wouidn't it be fun to implement a downloadable replacement for
the usual Web browsers, such that if somebody clicks on our
download link their current Web browser downloads it and installs
it as a plug-in, but then our CL-plug-in completely takes over the
browser so that none of the original browser is ever run again, and
the user doesn't see any change in performance except that spam
pop-ups are better regulated (avoided) and other subtle factors are
better than with the original browser?

> From: Ken Tilton <kennytil...@optonline.net>
> Make new datatypes, not new languages.

I agree. And furthermore they don't need to be actual new datatypes.
New intentions on old datatypes work fine too.
(And in a sense, you really can't invent new datatypes within Lisp
or Java, you can only make new sub-classes of existing classes.
The closest you can get to a brand-new datatype is when you
directly sub-class STANDARD-CLASS or java.lang.Object respectively.)

Once you have a truly generic datatype, such as nested lists with
sufficient types of atomic constituents, you can emulate any
intentional datatype you want. Several common methodologies exist:
- Have the intention of the data known a priori by the functions
you call to accept the data as input.
- Store the intentional type of the data in the CAR of the head
cell of each "object", with the CDR pointing to the actual data.
- Use an uninterned symbol as the header of each separate "object",
with the property list containing the intentional tag(s) and the
value cell holding the actual value. This has the advantage that
an object can be "of multiple types" i.e. satisfy multiple
interfaces, merely by having multiple type-tags in the property
list.
- Define STRUCT or CLOS classes, sigh, do you really need to do that?

Your suggestion for an example is a good one. I hope this helps :-).

Here is a pseudo-code mockup of the Telegram problem in VF. I just now
invented the pseudo-code syntax and I have left out non-pertinent details
(hopefully, I didn't insert too many blunders) - I simply want to talk
about the simple low-level mechanisms of what happens (use a fixed font to
view the pseudo-code). (If I were doing this with the actual tool, the
parts would appear on a "schematic" diagram and their insides would be
drawn as state diagrams. I'm guessing that pseudo-code will make this
discussion easier, esp. on non-graphical nntp).

For simplicity of discussion, I've skipped over issues like multiple
whitespace characters, pin typing, etc.

There are four "code" parts and one "schematic" part (which organizes the
parts and specifies their interconnection). Discussion below.

part Reader:
input pins: char, eof
output pins: out-char, open

initially:
send DesiredFileName to open
goto idle

state idle:
on char:
send char to out-char
quit
on eof:
goto done
end state

state done:
quit
end state

end part

part Tokenizer:
input pins: in-char
output pins: word

initially:
buffer = allocate()
goto waiting-for-chars

state waiting-for-chars:
on inchar and not whitespacep (inchar):
appendchar (buffer, char)
quit
on inchar and whitespacep (inchar):
send buffer to word
buffer = allocate()
quit
end state
end part

part ReCompose:
input pins: word
output pins: record

initially:
recbuff = allocate()
goto waiting-for-words

state waiting-for-words:
on word:
when (length(word) + length(recbuff) + 1) > DesiredRecordLength:
send recbuff to record
recbuff = allocate()
end
append (recbuff, word)
append (recbuff, Space)
quit
end state
end part

part WriteSeq:
input pins: record
output pins:

initially:
goto waiting-for-records

state waiting-for-records:
on record:
write (file, record)
quit
end state
end part

schematic Telegram:
parts
rdr : Reader
tok : Tokenizer
recomp : ReCompose
wr : WriteSeq

nets:
wire <filesystem>.char to rdr.char
wire rdr.open to <filesystem>.open
wire rdr.outchar to tok.inchar
wire tok.word to recomp.word
wire recomp.word to wr.record
end schematic


This is just a straight-forward network of four parts cascaded together.

I have imagined a "event driven" file system. After a file is opened, the
file systems sends one "ready" event every time a character is ready to be
read from the file. It sends a different "eof" event when the file has
been exhausted. (I discuss how to map a "normal" "pull" type file system
onto this software, below).

I included a "quit" statement as syntactic sugar only to remind us that
execution of action code stops at that point.


Loose details of operation:

1) The system wakes up, all the parts are instantiated and the initially
code is executed for each part. The state variable for each part is set to
appropriate start state (again, done explicitly here for expository
purposes).

1a) If the start-up generated any events, they are processed. In our case,
an open event is sent to the filesystem (allow me to skip over the details
of how this communication with the filesystem works).

2) The system goes live - it simply goes to a wait mode until something
happens.

3) The file system sends a character to the Reader.

An input event [char,<character-value>] is placed on the input queue of
Reader.

(By this I mean: an event id identifying the 'char' pin and a single
character as the data, e.g. ('char . #\P) or similar).

4) The kernel sets Reader's busy flag and activates Reader.

5) Reader pops one event from its input queue and cases on its state (idle)
and executes code (if any) that pertains to the input event (char).

In this case, the incoming character is simply sent out as an event on
output pin "out-char". This causes the event [out-char, <character-value>]
to be placed on the output queue of Reader.

The action code sequence quits.

The busy flag of Reader is set to false (it is no longer busy).

6) The kernel then delivers the event from the output queue to its
destination(s). The event [out-char, <character-value>] is moved and
converted to [in-char, <character-value>] on the input queue of the
Tokenizer.

Minor detail: the event is converted from an "output" event to an "input"
event by changing the output pin name (or index) to an input pin name (or
index). If an output goes to more than one input pin, clones of the event
are placed in each receivers' input queues with the appropriate input pin
names.

Now, Reader has no events on its input queue and Tokenizer has one event on
its input queue.

7) Tokenizer sets its busy flag to true, then cases on the incoming event.
It either stuffs the character into the buffer and goes back to idle, or it
sends the buffer and allocates a new buffer.

Then it quits. Its busy flag is set to false. If it generated an output
event, then the event would be delivered (to ReCompose) - i.e. a chain
reaction of events on down the line.

8) The rest of the events continue in the same manner as described above.

At some point, the file system sends another character to Reader and the
whole process repeats. When the file system sends an "eof" event, Reader
goes into its "done" state and nothing else happens (this is a toy example,
after all).

Is it sufficient to stop the description at this point?


Detail: It is not obvious in this example, but the "busy" flag BLOCKS
preemption / reentrancy. A part must finish what it is doing before
looking for more work.

I haven't covered the case where the file system sends bursts of "ready"
events faster than the software can handle them. There are two more cases:

1) Ready events show up while Reader is still busy. In this case, the
[char,<...>] event is placed (in order) on the input queue of Reader. When
Reader reaches its "quit" statement, it becomes re-activated if there is
more (/ new) work in its input queue.

2) Ready events show up while Reader is not busy, but some part further down
the chain is still busy. In this case, the chain proceeds to execute and
stops when it hits the part which is busy, leaving an input event in its
queue and simply "returning" (RTI). This is an example of stacked,
partial-preemption. The busy part is temporarily preempted by the incoming
interrupt. Its execution state remains on the stack and Reader gets the
CPU (scribbling on the stack above the saved state, similar to what happens
with CALL/RETURN). When this new chain of events withers and quits, the
stack is popped (RTI) and the interrupted part resumes from where it left
off.

The embedded kernel and the workstation kernel are essentially the same,
except that the embedded kernel needs to have IRQ-OFF's placed in the
correct places, whereas this doesn't matter in a "dumb" workstation
version.

Does this description give a better overview of what happens and how the
equivalent of "processes" are implemented inexpensively?

pt


ps. Suppose we wanted to do this with a "normal" file system - a "pull"
system - or we wanted to simulate the system on a workstation before
committing it to an embedded system.

We can add a simple feedback loop to the Reader part. Every time it reads a
character from the file, it also sends itself a "go" event - which causes
it to read another character, and so on.

This particular feedback loop might cause the Reader part to read the whole
file - it depends on the scheduling policy within the kernel (whether
Reader continues until its input queue is empty, or whether Tokenizer gets
to run before Reader gets another chance).

If we wanted to explicitly write the code so that it keeps queue levels down
to a minimum, we can add "synchronization" handshakes to the code. The
part furthest down the chain to consume an event is responsible for telling
the Reader to "go" and read another character.

I think that the code would look like this (I can't test it, since it is
pseudo code):


part Reader:
input pins: go
output pins: out-char, loopback

initially:
file = open (DesiredFile)
send true to loopback ;; once - and never again
goto idle

state idle:
on go:
if eof(file)
goto done
end
c = getc(file)
send c to out-char
quit
end state

state done:
end state

end part

part Tokenizer:
input pins: in-char
output pins: word, request

initially:
buffer = allocate()
goto waiting-for-chars

state waiting-for-chars:
on inchar and not whitespacep (inchar):
appendchar (buffer, char)
send true to request
quit
on inchar and whitespacep (inchar):
send buffer to word
quit
end state
end part

part ReCompose:
input pins: word
output pins: record, request

initially:
recbuff = allocate()
goto waiting-for-words

state waiting-for-words:
on word:
if (length(word) + length(recbuff) + 1) > DesiredRecordLength:
send recbuff to record
recbuff = allocate()
else
send true to request
end
append (recbuff, word)
append (recbuff, Space)
quit
end state
end part

part WriteSeq:
input pins: record
output pins: request

initially:
goto waiting-for-records

state waiting-for-records:
on record:
write (file, record)
send true to request
quit
end state
end part

schematic Telegram:
parts
rdr : Reader
tok : Tokenizer
recomp : ReCompose
wr : WriteSeq

nets:
wire rdr.outchar to tok.inchar
wire tok.word to recomp.word
wire recomp.word to wr.record
wire (rdr.loopback, tok.request, recomp.request, wr.request) to rdr.go
end schematic


To me, this is a great feature (others may disagree). The engineer gets to
control the design at very low levels, yet the design intent is clear
(because he does the above with diagrams).


pps. I also glossed over memory management, because we lispers like not to
have to think about that. But, let's say that we wanted to tighten the
design up to use statically allocated buffers. Each part would send its
data (e.g. a word) in a buffer to the next part in the chain. When that
part is finished with the buffer, it "returns" the buffer by sending it
back on a recycle wire. Again, the recycle wires would be explicitly drawn
on the schematic and visible to everyone.

On Sun, 01 Jun 2008 22:31:41 -0700,
m6d01a9.3.calrobert@spamgourmet.com (Robert Maas,
http://tinyurl.com/uh3t) wrote:

>> From: George Neuner <gneuner2/@/comcast.net>
>(compared to hardware designers
>> few developers know how to formally proof software and even fewer
>> bother to do it except when the results will be published.
>
>Given that it's not even possible to proof hardware, because
>quantum mechanics and small impurities in materials production and
>variation in physical assembly actions all make the properties of a
>hardware device impossible to prove within bounds, and anything
>proven from such an assumption would then be GIGO. At best
>statistical estimates of success rate and MTBF (Mean Time Between
>Failure) can be predicted on the basis of experience. Accordingly
>complaining that software isn't formaly proofed seems an unfair
>complaint in this hardware-vs-software discussion.

You clipped what I responded to which was a lament that software
couldn't be analyzed like hardware.

In any event, proofs begin with a set of postulates assumed to be
true. A software proof usually starts from the assumption that the
execution hardware will perform as spec'd.


>Perhaps a more appropriate metaphor would be the legal system, of
>adversarial contestants, one to show evidence for something, the
>other to find flaws in the evidence leading to reasonable doubt. In
>the software contest, perhaps each unit (function, method, etc.)
>can be specified per initial state assumed, D/P process that
>occurs, and final state claimed if the initial state was within
>spec.

It's not a bad idea but


>The person claiming a unit is "working" could post a demo of
>the unit for testing, by both automated test rigs (some written by
>an adversary) and manual/interactive attempts to make the unit
>fail. If the unit has withstood a reasonable time period of such
>testing, then it can be trusted. With formal specs for starting
>state and final state, automated verification of matching states of
>output from one unit to input of another unit, and automated
>management of a whole network of such dependencies, simple
>connections of the specs between units can be used to prove that
>combinations would work too, without needing to test each
>combination. (Maybe you're saying that the overall system for
>managing such analysis of multi-unit software isn't available "off
>the shelf" for popular programming languages, so it's not worth
>people bothering to even try that methodology except if they're
>going to publish the result in a scholarly ournal?)

I'm saying that most developers simply don't know how to proof
software. Testing is not proofing. Automatic proofing tools would
certainly help - but any possible tool is limited by the halting
problem and so there will always be code that the tool cannot prove
correct. And the tool would have to be simple enough for code-monkeys
to use and have warnings they could understand.

[Incidently, I'm not excepting myself. I *did* know how to write a
proof at one time, and even had to do so professionally for some
medical device software I once worked on. But I haven't done a
software proof in well over a decade and I doubt I could sit down and
do one now without methodology research.]


>> It's also the case that some popular programming languages have
>> features that impede easy analysis.
>
>It's not necessary to *use* such difficult-to-analyze features, you
>know?

Of course. However, a language with imperative features is inherently
more difficult to analyze than a language without them. The entire
point of some standard compiler transformations is to "functionalize"
the code and make it somewhat easier to analyze.

But even so, there are no "functional" CPUs ... all are imperative.
So, by rights, to prove the software, you have to prove both that the
source correctly implements the intent of the program under the
semantics of the source language, and also that the imperative
translation implements identical intent under the semantics of the
assembler language.

A good compilers is very hard to write - over the years I've been
involved with two projects.


>If the parse tree for the software is readily available, as
>it *is* for Lisp (and has been since the very start nearly fifty
>years ago), it's possible to automatically analyze the software to
>check what features it uses and warn if any difficult-to-analyze
>feature is used, and not exactly where it's used. Then anyone
>wishing to prove that the different individually-tested units can
>be proven to work together, can attempt to modify the code (if
>necessary) to eliminate use of any difficult-to-analyze feature,
>and if successful then apply whatever multi-unit-analyzer software
>is available. Have you investigated that idea to see how feasible
>it might be? (Note that different features might cause difficulty
>with different methods of multi-unit analysis, so a different
>difficult-code detector might be needed for a different
>multi-unit-analysis tool.)

With imperative languages, it's a lot harder than it sounds - there
are myriad special cases where a potentially unsafe construct is
suitably constrained and therefore not being used in a dangerous
manner. If you simply reported any use of the unsafe construct,
developers would start ignoring the warnings. You have to do a lot of
work to sort out what is dangerous from what looks like it might be
dangerous.


>> 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.
>
>Back to that metaphor: Software is nearly *always* assembled from
>low-level units that come from a catalog, namely the "Principles of
>Operation" manual for the CPU when writing machine/assembly
>language code, or the "API documentation" when writing code in a
>higher-level language. For example, we have the Common Lisp
>Hyper-Spec <http://www.isr.ist.utl.pt/library/docs/HyperSpec/Front/>
>and the JavaDoc <http://java.sun.com/j2se/1.4.2/docs/api/index.html>
>as "catalogs" of what API units are available for use (and
>well-tested and believed to be working) in our application-level
>software.

True, but not relevant. The discussion is about component (re)use of
off-the-shelf software by different authors, possibly written using
different languages.

Paul made an analogy to hardware, but to be similar, software
components must be in some immutable form that can be executed but not
modified by the developer.


>> Software developers, OTOH, do invent ad-hoc symbolism and
>> accompanying predicate systems every time they write a program
>
>All within the framework provided by the API (or Principles of
>Operation) manual. Nothing is invented do novo except *intentions*
>of use of some existing type of data.


That is exactly what I'm talking about. The semantics of the platform
are not relevant. The program has its own symbology and semantics.
The hardware may see an integer value, say 42, but nothing constrains
the program to treat 42 as a number - it can be a symbol representing
anything that is meaningful to the problem domain.

The logic and semantics defined on the unique symbology of the program
is *always* ad-hoc.


>Application programmers do *not* delve deep into the underlying
>machine language to defeat the restrictions of the API, much less
>modify the hardware to generate new machine language instructions
>to take advantage of. So I believe here you're making much ado
>about nothing.

It's only necessary to use data in a way that's inconsistent with its
nominal appearance. Like using 42 to mean

1 - open silo doors
0 - detach fuel line
1 - spin up gyros
0 - retract gantry
1 - start ignition
0 - deny recall


>> 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.
>
>How about a syntax-free development and archival system, which
>automatically lists which known programming languages support any
>given module and offers a menu for converting the syntax-free
>software to whichever of the known programming languages the user
>wishes to express it in (port it to)? I've proposed this idea
>several times recently, but nobody else has expressed any serious
>interest.

I honestly have no idea what a "syntax-free" development system would
even look like. There is no such animal as a syntax free language and
back-translation from a language neutral IR to any particular high
level language more often than not produces garbage.

Java and .NET have the right idea - secure managed environments, a
common low level distribution format and compilation to native code at
load time (or alternatively at install time). It's the current
implementations of the idea(s) that are lacking.


>> Historically "warrant" was limited to the lifetime of the giver.
>> However, companies have (potentially) unlimited lifetimes.
>
>Except that when a merge happens the new owner convenient forgets
>any promises made by the previous company. For example, I opened an
>account with Northern California Savings, because they had a
>wonderful commercial on TV with a chain of dominos representing a
>person's life time, which comes to an end at the end of the domino
>chain, plus the fact they offered me free cheque printing for the
>lifetime of the account. They were bought by Great Western Savings,
>which honored the promise, which was later bought by Washington
>Mutual which refused to honor the promise, started charging me for
>cheque printing.

Those promises were not warrants (or guarantees) ... they were simply
corporate policies and as such were subject to change.

In many countries, an acquiring company must uphold obligations of the
acquired company. A warrant, however, is not an obligation or
responsibility - it is just an assumption of authority. The acquiring
company can choose not to assume authority over products or services
of the acquired company that they don't like. In that case the
orphaned products and services generally die unless someone else
assumes them.


>> Component software is a great idea but intractably hard in practice.
>
>Do you mean that setting up formal specs for *all* the functions in
>Common Lisp or *all* the classes/methods in Java etc. is
>intractably hard (I would agree there), or that even doing formal
>specs for a relatively well-behaved subset is intractably hard
> (I might disagree with you if that's what you mean, but I'd need
> to see you clearly state what you are saying before I post formal
> rebuttal).

I mean exactly what I said previously. To recap: For software to be
componentized, it must become like IC hardware - an immutable
black-box deliverable which can only be executed according to its
specified interface. It must be impossible or at least unfeasibly
hard to tamper with the deliverable. It must be plug and play at
least on all the popular platforms and usable from any language or
development system that runs on those platforms.

That could be achieved now, but it would be nearly impossible to get
everyone to agree on an appropriate common delivery and management
system.


>> 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.
>
>Is any decent-sized subset of the Java 1.3 or 1.4 API suitable?

No.

Ignoring Java's deficiencies as a source language, the JVM is not a
good execution platform for languages whose features differ
significantly from Java. Advanced languages features not found in
Java can be implemented on the JVM with varying degrees of difficulty,
but their performance is frequently poor (see SISC for an example).
Sun, as yet, has shown no inclination to expand the JVM to accommodate
other languages. The delivery format is not externally tamper-proof
and reflection allows runtime discovery and manipulation of objects in
ways the designer did not intend.

The same is true of .NET although its VM makes a bit more of an effort
to accommodate languages that Microsoft doesn't promote - for example,
..NET (as of version 2) directly supports tail recursion.

COM and Corba are ok but components are not hardware neutral like
bytecode files nor are they immune to tampering.


>> Neither is .NET, or Corba, or COM or anything I've yet seen.
>
>How about a subset of Common Lisp??

No. Lisp has no non-source external format for code. The whole point
of component software is to use it as is and prevent modifications
that might affect the reliability of the code.


George
--
for email reply remove "/" from address

FYI, the latest issue of DDJ contains an article (and a reference to a
book) about event-based programming:

http://www.ddj.com/architect/208801141

pt