[Jprogramming] Implementation of fill

[Raul Miller]

Yes, but keep in mind that K is optimized for one thing: time series
databases. It provides a different set of abstractions from J.  (J
gives flat namespaces, K gives you its tree. J arrays have rank, K
arrays do not. And... so on...)

It's a good language though, and of course you should feel free to use
it, if you are so inclined.

-- 
Raul

On Sat, Jun 29, 2013 at 6:37 PM, greg heil <gheil.j at gmail.com> wrote:
>>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 <rogerhui.canada at gmail.com>
> to: Programming forum <programming at jsoftware.com>
> 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 <rogerhui.canada at gmail.com>
> to: Programming forum <programming at jsoftware.com>
> 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. <michal.dobrogost at gmail.com>
> to: programming at jsoftware.com
> date: 28 June 2013 21:17
> subject: Re: [Jprogramming] Implementation of fill
>
> Oops, ravelWFill should be appendWFill =/
>
> --
>
> from: Michal D. <michal.dobrogost at gmail.com>
> to: programming at jsoftware.com
> 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 <mwlochbaum at gmail.com>
> to: programming at jsoftware.com
> 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. <michal.dobrogost at gmail.com>
> to: programming at jsoftware.com
> 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