Newsgroups: comp.lang.apl
Path: utzoo!utgpu!news-server.csri.toronto.edu!torsqnt!jtsv16!blister!itcyyz!yrloc!rbe
From: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
Subject: Re: implementing J
Message-ID: <1991Apr21.162659.9338@yrloc.ipsa.reuter.COM>
Reply-To: rbe@yrloc.ipsa.reuter.COM (Robert Bernecky)
Organization: Snake Island Research Inc, Toronto
References: <19APR91.08155946@uc780.umd.edu>
Date: Sun, 21 Apr 91 16:26:59 GMT

In article <19APR91.08155946@uc780.umd.edu> cs450a03@uc780.umd.edu writes:
>
>Problem:  building a list of length n from n scalar operations is O(n
>squared), rather than O(n)
>
>There would be a tradeoff there--for some things this could really
>waste time.  Also note that this is similar to using APL's indexed
>assignment assignment to build arrays, although indexed assignment
>takes advantage of being able to estimate storage requirements ahead
>of time.

The way that I originally implemented function rank at I.P. Sharp, way
back in the dark ages around 1980 or so, was as follows:

Build an array of pointers the size of the frame. Call the function to which
rank applied once per element in that frame, building an array of the cell
contents for each call. This went through all the primitive function
conformability checking, storage management, etc. for each call. Pricey,
but general, it worked, and was easier than modifying 300 thousand lines
of assembler code. When all the cells had been processed, COPY all those
cell results (which had been attached to the above array, ala BOX), to a NEW
array, which held the logically flattened result.

The special casing for catenate and other verbs I mentioned in my previous
message consisted largely of removing the above sort of silliness, and
placing a new outer loop around the primitive's loops, after conformability
checks had been done. 

Both of these techniques were chosen because of the huge amount of code
which not only made assumptions about data structures, but also made
assumptions about space "near" data structures. FOr example: "I know
I can set the rank and type of the result at the same time, because
I KNOW they are adjacent cells in the same word", and "I KNOW I can
index off the end of this array when storing into it, because storage
management ensures that I have about 32 bytes of slop off the end of ANY
just-allocated array".

The last one was a killer. Still is. These sorts of assumptions are nasty
because they do NOT exist in visbibly in the code -- they just lurk there,
waiting to strike at the unwary. These are the sorts of coding tricks which
can kill.           

But I digress. The way we got around it allocated storage once, and
built the cell results in situ. (Situ is located near Cleveland, somewhere).


Robert Bernecky      rbe@yrloc.ipsa.reuter.com  bernecky@itrchq.itrc.on.ca 
Snake Island Research Inc  (416) 368-6944   FAX: (416) 360-4694 
18 Fifth Street, Ward's Island
Toronto, Ontario M5J 2B9 
Canada