>A great example of purity of arrays (no admixture of types) allowing >transparency to the implementer (and speed of the result) is k (or kona >or...). Ragged arrays in arbitrary dimensions are perfectly transparent and >efficient there. Its implementation should be efficient too, as it clocks in >at about 100KB for the system.
greg ~krsnadas.org -- from: Roger Hui <[email protected]> to: Programming forum <[email protected]> date: 29 June 2013 11:14 subject: Re: [Jprogramming] Implementation of fill >The benchmark I posted before in this thread illustrates a difference between >a different representation and the current boxed arrays with special code >support. c=: 7 + 1e6 ?@$ 13 n=: +/c v=: ((i.n) e. 0,+/\ c) <;.1 a.{~97+n ?@$ 26 m=: >v ts 'i.~ v' 0.35258 1.25836e7 ts 'i.~ m' 0.235694 1.25837e7 >i.~v illustrates the fact that the i. primitive scans a boxed left argument to >see whether all the boxes contain the same kind of stuff, and uses a faster >algorithm if they do. vx=: 3 1 4 1 5 9;v ts 'i.~ vx' 0.708579 1.25837e7 >A slower algorithm is used for i.~vx because all the boxes do not contain the >same kind of stuff. >Usually, a negative result from the scan obtains pretty quickly. But you can >construct an argument where it finds out only at the end that it's not all the >same kind of stuff: vy=: 1|.vx ts 'i.~ vy' 0.734981 1.25837e7 >Because J does not have a different representation for boxes of all the same >kind of stuff, it can pick and choose which primitives to optimize for such >boxes (while paying the price of doing the scan every time it needs to know). >If you have a different representation (as I said before) you have to do work >in every primitive to support that representation. Alternatively, you can >maintain a flag with an array recording various properties that you are >interested in, but then you'd have to do the work to update that flag. -- from: Roger Hui <[email protected]> to: Programming forum <[email protected]> date: 29 June 2013 10:24 subject: Re: [Jprogramming] Implementation of fill >If you don't have to be compatible, you can do anything that is imaginable. >Disallowing fill is a possibility. >Having done both, I can tell you that designing a language is much harder than >implementing it. How do you debug a design, for example? >> On the other hand, how hard is it for the interpreter to recognized boxed >> arrays where the boxed items have the same rank (# @: $) and implement them >> as contiguous ragged arrays? (Perhaps the best solution if possible). >Of course it is possible, and it may even be "easy" depending on how much pain >you are willing to endure. Keep in mind that if you have a different >representation you have to handle that representation in every primitive. It >is as much implementation work as having a new datatype. With a new datatype >you also have language design work. >Lest I sound too discouraging, let me say that you should go ahead and do what >you think is right. I myself did lots of stuff and succeeded because I didn't >know that it was supposed to be hard. -- from: Michal D. <[email protected]> to: [email protected] date: 28 June 2013 21:17 subject: Re: [Jprogramming] Implementation of fill Oops, ravelWFill should be appendWFill =/ -- from: Michal D. <[email protected]> to: [email protected] date: 28 June 2013 21:15 subject: Re: [Jprogramming] Implementation of fill >So I have to clarify that this discussion is about a language similar to J but >not J itself, since obviously none of this stuff can be changed in J. >Maybe it makes sense to disallow fills altogether and instead result in an >error. How much expressive power is really lost since you usually want to box >the result anyways and might prevent errors (due to values being equal to >fills)? The problem with boxed arrays is that they are not contiguous in memory with all the corresponding performance concerns. Has any thought been given to a more fine grained shape representation for ragged arrays? Possibly compressed in some form like below: j=:1+i. ravelWFill =: ,&.< ]ragged=: (j 2 2) ravelWFill ((j 2) ravelWFill (j 3)) 1 2 0 3 4 0 1 2 0 1 2 3 ]shapeOfRagged=: (<2),(<(<2 2),(<(<2),(<2,3))) +-+-------------+ |2|+---+-------+| | ||2 2|+-+---+|| | || ||2|2 3||| | || |+-+---+|| | |+---+-------+| +-+-------------+ >On the other hand, how hard is it for the interpreter to recognized boxed >arrays where the boxed items have the same rank (# @: $) and implement them as >contiguous ragged arrays? (Perhaps the best solution if possible). Cheers, Mike >Ps. I will be away for the weekend but will eagerly read all responses when I >get back. -- from: Marshall Lochbaum <[email protected]> to: [email protected] date: 27 June 2013 08:21 subject: Re: [Jprogramming] Implementation of fill >1) Fills need to be as unobtrusive as possible. This means they need to keep >the original array intact, and look distinct from the rest of the array. >Filling the front of an array would change which elements are at which indices >by moving each element up a few indices. This makes it difficult to >consistently index the array, so that's out. Cycling the array is a bit more >reasonable, but it has a few problems. First, the cycled elements will look >like data, making it hard to distinguish where the fill has been added. >Second, doing a cycle fill multiple times is not equivalent to using one >larger fill: ]a=.i.4 0 1 2 3 8$6$a 0 1 2 3 0 1 0 1 8$a 0 1 2 3 0 1 2 3 >2) Yes, fills are a pain. In general, you should keep ragged data in boxes >rather than letting J concatenate it and fill out the shorter elements. I can >think of a few cases where fills are useful (working with polynomials, which >ideally are infinite lists where all but a finite number of elements are zero, >is one), but otherwise they will probably just damage your data. Marshall -- from: Michal D. <[email protected]> to: [email protected] date: 26 June 2013 23:00 subject: [Jprogramming] Implementation of fill Hi All, >I was wondering if any J implementors have some insight to share. >(1) Is there a reason why fills are put in the places they are? Are there any >alternatives that were also explored? One might imagine filling the front of >an array instead of the back, or cycling through the elements of the array >instead of inserting fills. >(2) They seem a little bit more tricky and unwieldy than I originally thought. >Would others agree? Cheers, Mike ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
