Path: utzoo!attcan!utgpu!utstat!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!samsung!caesar.cs.montana.edu!ogccse!dinucci
From: dinucci@ogccse.ogc.edu (David C. DiNucci)
Newsgroups: comp.lang.visual,comp.lang.misc
Subject: Re: metaphor and programming
Message-ID: <5635@ogccse.ogc.edu>
Date: 15 Nov 89 18:38:56 GMT
References: <13770@orstcs.CS.ORST.EDU> <5623@ogccse.ogc.edu> <1989Nov15.063815.1949@brutus.cs.uiuc.edu>
Reply-To: dinucci@ogccse.UUCP (David C. DiNucci)
Organization: Oregon Graduate Center, Beaverton, OR
Lines: 75

Rather than citing specifics in previous articles on this subject, I'm going
to outline where I am coming from - parallel computation, and more generally,
parallel software engineering.  Functional (and dataflow) approaches have
been used in this arena for decades, but they have drawbacks which, in my
opinion, are caused by restricting the expression of functional composition
to a left-to-right textual string.

Drawback 1.  Functions return a single result.
    There is nothing hard about formalizing functions which return more
    than one result, and in fact, it is not hard to express such a function
    "call" in a textual fashion - consider a call to a routine (without side-
    effects) which alters the values of some of its arguments.  The problem
    comes in when trying to compose such functions.  Such a composition
    can simply not be expressed clearly in the linear, left-to-write
    fashion that we use when writing text.  Pictures handle this nicely,
    though.

Drawback 2.  Functions cannot specify in-out parameters
    Dataflow and Functional languages typically rely on single-assignment
    (or "zero-assignment") variables, tossing out the notion of "updating"
    an argument in place.  Again, it is not hard to formalize a form of
    function which allows this - consider Modula, etc, which declare
    routine arguments as in, out, or inout.  But even with a graphical form
    of composition addressing drawback 1, above, this adds new problems to
    composition.  A function can no longer simply await its "in" arguments
    before evaluating - a means of moving these inout arguments from one
    function evaluation to the next in an orderly fashion must be developed.
    Petri nets give us one model of how this can be done, by considering
    places as having a spot which can hold data which is completely
    independent of its token state, and each process has in, out, or inout
    permission to each of its places.

Drawback 3.  Indeterminacy, non-determinism
   (Although these actually mean different things, I will mis-use both to
   mean that the results of a computation may depend on timing relationships
   as well as its input data.)  In standard functional composition, the
   composition of two functions is another function.  Parallel programs which
   exhibit non-determinism are not functional.  Thus, if we assume that such
   programs should be expressible (which I wholeheartedly believe), a more
   powerful form of composition is needed.  Though tossing "oracle functions"
   and merge operations into functional and dataflow languages will sometimes
   suffice, I prefer a more natural one which says "hey, this result is
   up for grabs to the first function (on some list) that can evaluate with
   it".  Petri nets again give us this framework.

So, do the gains of using such a graphical representation balance the
losses?  In this world, one expresses their program graphically as this
petri-net-like network of functions (called an F-Net), then implements the
functions in their favorite language.  The individual functions are
essentially subroutines, except that they cannot maintain internal state
between invocations, and they explicitly declare when each of their return
values is ready.  They are not susceptible to the usual "parallel" problems -
from the programmer's point of view, each such function runs completely
independently, alone, and atomically, so their arguments will not change
out from under them.  These functions are never called explicitly,
but implicitly according to the current "token state" of its arguments
in the composition diagram (F-Net).

This brings me back to my initial point.  Stuff that can be better expressed
in a textual language (i.e. classical deterministic functional composition
of functions returning single results) should be expressed in such languages,
but a graphical language allows some freedom when this proves too restricting.

I would be interested in hearing criticisms of this approach.  For more
info, see COMPCON Spring 89 proceedings.  (With luck, I may have
something more up-to-date accepted soon.  Then there's my dissertation...
someday)

Dave

-- 
David C. DiNucci          Oregon Graduate Institution of Science & Tech.
                                       (Formerly Oregon Graduate Center)
CSNET: dinucci@cse.ogc.edu                    19600 N.W. Von Neumann Dr.
UUCP:  ..ucbvax!tektronix!ogccse!dinucci      Beaverton, Oregon  97006