[kepler-dev] Re: zero-length arrays

[Edward A Lee]

Prolog is not a concurrent language (at least, not
in the sense that separate threads of control share references
to the same objects)...

The immutability of tokens is essential to our concurrent MoCs...

The map higher-order function could, of course, be implemented more
efficiently because of the knowledge that intermediate results will
have only one thread referencing them...  But how should the software
infrastructure support this?  If ArrayToken has public methods that
modify the array, then users (e.g. Tobin) will happily use those
methods in actors, and break _all_ of our concurrency models.
We'll start to get questions about why the result of an execution
seems to depend on the phase of the moon...  :-)

Edward

At 02:06 AM 8/12/2004 -0700, Bertram Ludaescher wrote:

>Tobin:
>
>Great observation with the one minute exec time for the "expensive
>concat" vs the more efficient version.
>
>I'm still surprised at the need to create a copy for C when doing
>   C := concat(A,B).
>
>In Prolog, for example, and I think also in Lisp, when you do
>   C := concat(A,B)
>(here syntax = abstract)
>
>then you create a copy ONLY of the first of the two lists, the second
>list is untouched. The reason that this is correct is because lists
>are represented as linked lists. So you can reuse all of B, but not A
>(since the last list pointer in A is NIL, and rewiring it to point to
>B would invalidate all references to A; cf. how the unsafe "nconc"
>works in Lisp vs the clean "append").  For A you have to make a fresh
>copy and let its last pointer be a pointer to the start of B.
>
>All this is declarative (no side effects), neat and halfway efficient
>(only A is copied not B).
>
>If the default implementation of arrays/lists in Java is consecutive
>memory cells (as opposed to linked lists) then I'm not surprised at
>the extra overhead...
>
>Note (for experts only ;-) -- in Prolog there is a way to get
>declarative (a la append, not a la destructive nconc) and very
>efficient O(1) list append! It's using a "trick" called "difference
>lists". I'm not sure whether Haskell et al have a similar O(1)
>append...
>
>Bertram
>
>PS here is the trick for O(1) append:
>http://cblpc0142.leeds.ac.uk/~paul/prologbook/node180.html
>
>
>
> >>>>> "TF" == Tobin Fricke <tobin at splorg.org> writes:
>TF>
>TF> On Wed, 11 Aug 2004, Shawn Bowers wrote:
> >> Isn't this last point just an implementation detail? Ultimately, a list
> >> is the "abstract" data structure, and array is just a common programming
> >> language implementation for a list-like structure.  The more general
> >> construct is really "collection" for which bags (mult-sets), sets, and
> >> lists are specific types of collections.
>TF>
>TF> That's completely true.  But the underlying implementation determines the
>TF> efficiency of operations on the structure, and therefore the algorithms
>TF> that you'll choose to use.
>TF>
>TF> Java strings are sort of "array-like" in that, to concatenate two strings,
>TF> you have to make a new string of the desired length and copy the original
>TF> strings into that.  If you want to concatenate a large number of strings,
>TF> it takes an incredibly long time, since all these intermediate copies are
>TF> floating around.  Try this:
>TF>
>TF>     sum( map( function(x:int)(x.toString), [1:1:10000].toArray ) )
>TF>
>TF> It takes about a minute (!) to execute in the stock Ptolemy.  I added
>TF> special code to handle the case of sum({string}) by using a StringBuffer
>TF> to accumulate the intermediate results (a "list-like" implementation), and
>TF> the execution time was reduced to approximately one second.
>TF>
>TF> Having an 'ordered collection' data type where appending is expensive
>TF> makes a lot of things difficult, notably just about any lisp idiom.  But
>TF> it's possible that the right avenue IS just to create a decent set of
>TF> built-in primitives, so that these expensive implementations are not
>TF> necessary, and therefore avoid language creep.
>TF>
> >> Also, it isn't clear to me that an empty record is a useful structure,
> >> whereas I definately see how an empty array (or more specifically an empty
> >> list) is useful.
>TF>
>TF> That's a good point.  But I don't think we'd want to rule out empty
>TF> records entirely... who knows when they might be useful?  (Also, the empty
>TF> record is a good type signature of "a record of some kind.")
>TF>
>TF> But it seems that Ptolemy allows empty records: 
>intersect({foo=0},{bar=0}) !
>TF>
>TF> Also seems like a good reason to allow empty records.
>TF>
>TF> Tobin
>TF> _______________________________________________
>TF> kepler-dev mailing list
>TF> kepler-dev at ecoinformatics.org
>TF> http://www.ecoinformatics.org/mailman/listinfo/kepler-dev
>_______________________________________________
>kepler-dev mailing list
>kepler-dev at ecoinformatics.org
>http://www.ecoinformatics.org/mailman/listinfo/kepler-dev

------------
Edward A. Lee, Professor
518 Cory Hall, UC Berkeley, Berkeley, CA 94720
phone: 510-642-0455, fax: 510-642-2739
eal at eecs.Berkeley.EDU, http://ptolemy.eecs.berkeley.edu/~eal