That seems like unnecessary overhead.
The results of a scan are constructed sequentially, so they can be
placed in memory sequentially. There's an issue where the region of
memory allocated for the result might be insufficient, but that could
be handled by reallocating with exponential growth on the estimate if
it turns out to be inadequate. (Start by calculating one result,
repeat until non-empty, multiply the size of that to be proportional
to the size of the argument to get the initial estimate ...)
That said, I haven't inspected this part of the current j-engine, so I
guess the implementation you suggested is also quite possible.
Thanks,
--
Raul
On Sun, May 30, 2021 at 12:18 PM Marshall Lochbaum <mwlochb...@gmail.com> wrote:
>
> None of the intermediate results are boxes, but I expect (i: <:@{:)\
> will create an array of boxed numbers first and then flatten it because
> it doesn't know in advance that (i: <:@{:) will just return numbers.
> That detail isn't important to me though: "without boxes" was just the
> easy term to use and not what I really meant to convey. I don't consider
> the i: solution to be array-based because it performs a number of
> function evaluations proportional to the length of the argument. pv_flat
> uses +/ and >./\, but treating these as individual operations (how J
> evaluates them), it uses a fixed sequence of array operations, with
> argument lengths proportional to the input size. Aaron's Key-based code
> falls somewhere between these two, as it calls a binary search for each
> depth level, with the total length of those searches proportional to the
> input length.
>
> These distinctions are vital to Co-dfns because they are what allows the
> code to run efficiently on a GPU with only a generic array runtime.
> True, you could implement (i: <:@{:)\ with *:^.n critical path or
> better, but then you are doing low-level GPU work, which Aaron says is
> no way to write a compiler.
>
> The "array-based" concept here does depend on what compound operations
> are supported. In BQN I ended up using only the scans +/\ >./\ ~:/\ and
> the reductions +/ and +./ (transliterated to J), except in the two
> places where I wasn't able to find an array-based method at all. So a
> basic set of operations consisting of primitive functions plus
> associative arithmetic scans and reductions seems natural.
>
> Marshall
>
> On Sun, May 30, 2021 at 08:12:09AM -0400, Raul Miller wrote:
> > First off, that's some interesting stuff.
> >
> > Second, though, the expression 0,}.(i: <:@{:)\depthvector does not use
> > boxing -- this expression probably has worse performance on
> > sufficiently long depth vectors than pv_flat, but the < character
> > there is <: which is decrement, not box.
> >
> > Thanks,
> >
> > --
> > Raul
> >
> > On Sat, May 29, 2021 at 11:50 AM Marshall Lochbaum <mwlochb...@gmail.com>
> > wrote:
> > >
> > > It's possible to convert depths to parent indices without boxes, by
> > > sorting a depth list with twice the input size. The idea is to list each
> > > depth twice, with the first instance representing it as a child entry,
> > > and the second, which is increased by one, representing it as a parent
> > > entry. After sorting, the parents and children for each depth are
> > > grouped together, so a child's parent is the most recent parent in the
> > > sorted list.
> > >
> > > The format of the grade result isn't particularly convenient. It has to
> > > be split with division and remainder by 2, where the quotient is the
> > > index in y and the remainder indicates if it is used as a parent.
> > > Besides that, there's a pattern >./\p*i.#p to get the index of the most
> > > recent 1 in p, and the rest is straightforward.
> > >
> > > pv_flat =: 3 : 0
> > > p =. 2| g2 =. /: ,y+/i.2
> > > g =. <.g2%2
> > > g /:~&:((-.p)&#) (>./\p*i.#p){g
> > > )
> > >
> > > When I built an array-based compiler for BQN I found that it tends to be
> > > simpler not to convert to trees explicitly, and instead to order by
> > > parenthesis (or other bracket) depth, which splits things into flat
> > > expressions where a closed parenthesis denotes a subexpression result.
> > > The paired parentheses serve the same purpose that the parent-child
> > > doubling does here, and the natural depth computation (+/\-/'()'=/s)
> > > automatically places open parentheses one higher than closed ones. Some
> > > further discussion at
> > > https://mlochbaum.github.io/BQN/implementation/codfns.html .
> > >
> > > Marshall
> > >
> > > On Wed, May 26, 2021 at 12:44:13AM +0200, Raoul Schorer wrote:
> > > > It is indeed very much worthy of note! I am currently making a little
> > > > library of all the tree manipulation idioms in Hsu's thesis, with the
> > > > final
> > > > goal of using them in an interpreter. It is therefore very useful to
> > > > have
> > > > the inverse of those transformations to reverse the encoded results into
> > > > more usual J language terms for trees (i.e. nested boxes), if only to
> > > > visualize the result and also make it available to the L. L: S: family
> > > > of
> > > > primitives.
> > > >
> > > > As for the depth -> parent vector transform, an almost literal
> > > > translation
> > > > of the thesis code is:
> > > >
> > > > pv =: monad define
> > > >
> > > > p =.i.@# y
> > > >
> > > > i =. (</. i.@#) y
> > > >
> > > > j =. ; 2 (0&{:: <@(<:@I.{[) 1&{::)\ i
> > > >
> > > > j (;}.i) } p
> > > >
> > > > )
> > > >
> > > >
> > > > which seems almost equivalent to your solution regarding time
> > > > complexity,
> > > > although yours seems ~25% better spacewise on preliminary tests.
> > > > Probably
> > > > because it avoids some intermediate result copying?
> > > >
> > > > I am sure Dr. Hsu would be extremely interested if someone came up with
> > > > more efficient solutions for all those transforms, as they are the
> > > > foundation of his Co-dfns compiler and are therefore used pervasively.
> > > >
> > > >
> > > > Cheers,
> > > >
> > > > Raoul
> > > >
> > > > On Tue, May 25, 2021 at 11:16 PM Raul Miller <rauldmil...@gmail.com>
> > > > wrote:
> > > >
> > > > > It's perhaps worth noting that you can convert a depth vector to a
> > > > > parent vector (except for the root element, which has no parent --
> > > > > though it's convenient to represent the root element as being its own
> > > > > parent) using (i: <:@{:)\
> > > > >
> > > > > For example:
> > > > > ast=:t;(t;t);(t;(t;t);t);<(t;(t;t;t);(t;t;t);t=.'.')
> > > > > dv=: 0, 1+ [:; [:dv&.> 1}.]
> > > > >
> > > > > 0,}.(i: <:@{:)\dv ast
> > > > > 0 0 1 0 3 4 3 0 7 8 8 7 11 11 7
> > > > >
> > > > > You can convert a parent vector back to a depth vector using:
> > > > > pv2dv=:{{
> > > > > (0,1+}.)@(y&{)^:_ y
> > > > > }}
> > > > >
> > > > > There might be more efficient approaches?
> > > > >
> > > > > Thanks,
> > > > >
> > > > > --
> > > > > Raul
> > > > >
> > > > > On Mon, May 24, 2021 at 8:57 AM Raul Miller <rauldmil...@gmail.com>
> > > > > wrote:
> > > > > >
> > > > > > Oops
> > > > > >
> > > > > > dv=: 0, 1+ [:; [:dv&.> 1}.]
> > > > > >
> > > > > >
> > > > > > Thanks,
> > > > > >
> > > > > >
> > > > > > --
> > > > > >
> > > > > > Raul
> > > > > >
> > > > > >
> > > > > > On Mon, May 24, 2021 at 8:40 AM Raoul Schorer
> > > > > > <raoul.scho...@gmail.com>
> > > > > wrote:
> > > > > >>
> > > > > >> Hi and thanks to all for helpting!
> > > > > >>
> > > > > >> Raul, I think you forgot to copy your working verb in your last.
> > > > > >> Ethejiesa, good catch and great insight! Your verb yields a domain
> > > > > error on
> > > > > >> J902, though.
> > > > > >>
> > > > > >> Cheers,
> > > > > >> Raoul
> > > > > >>
> > > > > >> On Mon, May 24, 2021 at 2:35 PM Raul Miller <rauldmil...@gmail.com>
> > > > > wrote:
> > > > > >>
> > > > > >> > Thank you, that makes sense.
> > > > > >> >
> > > > > >> > And, I also see that I built a faulty value for ast.
> > > > > >> >
> > > > > >> > Here's a fixed ast and a working depth vector verb:
> > > > > >> >
> > > > > >> > t=:'.'
> > > > > >> >
> > > > > >> > ast=:t;(t;t);(t;(t;t);t);<(t;(t;t;t);(t;t;t);t)
> > > > > >> >
> > > > > >> > ast
> > > > > >> >
> > > > > >> > +-+-----+-----------+---------------------+
> > > > > >> >
> > > > > >> > |.|+-+-+|+-+-----+-+|+-+-------+-------+-+|
> > > > > >> >
> > > > > >> > | ||.|.|||.|+-+-+|.|||.|+-+-+-+|+-+-+-+|.||
> > > > > >> >
> > > > > >> > | |+-+-+|| ||.|.|| ||| ||.|.|.|||.|.|.|| ||
> > > > > >> >
> > > > > >> > | | || |+-+-+| ||| |+-+-+-+|+-+-+-+| ||
> > > > > >> >
> > > > > >> > | | |+-+-----+-+|+-+-------+-------+-+|
> > > > > >> >
> > > > > >> > +-+-----+-----------+---------------------+
> > > > > >> >
> > > > > >> > dv ast
> > > > > >> >
> > > > > >> > 0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
> > > > > >> >
> > > > > >> >
> > > > > >> > (Apologies for any wonky formatting -- I am on a phone right
> > > > > >> > now.)
> > > > > >> >
> > > > > >> >
> > > > > >> > Thanks,
> > > > > >> >
> > > > > >> >
> > > > > >> > --
> > > > > >> >
> > > > > >> > Raul
> > > > > >> >
> > > > > >> > On Mon, May 24, 2021 at 2:47 AM ethiejiesa via Programming <
> > > > > >> > programm...@jsoftware.com> wrote:
> > > > > >> >
> > > > > >> > > Raoul Schorer <raoul.scho...@gmail.com> wrote:
> > > > > >> > > > Dear all,
> > > > > >> > > >
> > > > > >> > > > I am struggling with the translation of the following APL
> > > > > >> > > > dyad to
> > > > > J:
> > > > > >> > > >
> > > > > >> > > > ∊ 0 {(⊢,(⍺+1)∇⊣)/⌽⍺,1↓⍵} y
> > > > > >> > > >
> > > > > >> > > > which is the expression to yield a depth vector from a tree
> > > > > >> > > > in
> > > > > record
> > > > > >> > > > format (drawn from Dr. Hsu's thesis). Demo:
> > > > > >> > >
> > > > > >> > > Oh cool! I have been (very sparingly) messing about with Hsu's
> > > > > >> > > tree
> > > > > >> > > representation. For purely selfish reasons, I haven't looked
> > > > > >> > > at the
> > > > > >> > thesis,
> > > > > >> > > trying to figure out the representation myself. However, I have
> > > > > only got
> > > > > >> > > so far
> > > > > >> > > as figuring out an algorithm for non-recursively generating
> > > > > >> > > random
> > > > > depth
> > > > > >> > > vectors.
> > > > > >> > >
> > > > > >> > > > t ← '∘'
> > > > > >> > > > ast ← t (t t) (t (t t) t) (t (t t t) (t t t) t)
> > > > > >> > > > ∊ 0 {(⊢,(⍺+1)∇⊣)/⌽⍺,1↓⍵} ast
> > > > > >> > > > 0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
> > > > > >> > > >
> > > > > >> > > > In particular, I don't understand the control flow and
> > > > > >> > > > termination
> > > > > >> > > > condition for the recursion. Dr. Hsu says that this uses tree
> > > > > reduction
> > > > > >> > > > with no base case.
> > > > > >> > >
> > > > > >> > > Anyway, my APL is pretty sketchy, but it looks like the ast
> > > > > >> > representation
> > > > > >> > > there is something like this:
> > > > > >> > >
> > > > > >> > > 1) First element of list is node content,
> > > > > >> > > 2) Following nodes are child subtrees.
> > > > > >> > >
> > > > > >> > > So the algorithm should be conceptually simple. Replace the
> > > > > >> > > head
> > > > > atom
> > > > > >> > with
> > > > > >> > > the
> > > > > >> > > current depth, bump current depth, and then recurse over the
> > > > > >> > > child
> > > > > >> > > subtrees. I
> > > > > >> > > believe that the "base case" is taken care of by (/), since at
> > > > > >> > > the
> > > > > leaves
> > > > > >> > > it
> > > > > >> > > should be operating on atoms.
> > > > > >> > >
> > > > > >> > > > dv =. {{ (];(>:x) dv [)/\ |.x;}.y }}
> > > > > >> > > >
> > > > > >> > > > results in an infinite loop. What am I missing? Is there some
> > > > > kind of
> > > > > >> > > > implicit termination condition in the ∇ primitive?
> > > > > >> > >
> > > > > >> > > The main problem is the (x;}.y) part. The recursion depends on
> > > > > >> > > the
> > > > > fact
> > > > > >> > > that
> > > > > >> > > (⍺,1↓⍵) equals ⍺ at the leaves, but (x;}.<'anything') is the
> > > > > >> > > same
> > > > > thing
> > > > > >> > as
> > > > > >> > > (x;a:). Thus when y is a leaf, (x;}.y) turns into a tree!
> > > > > >> > >
> > > > > >> > > We can brute for a fix by replacing the (;) in (x;}.y) with
> > > > > >> > > (;`(<@[)@.(0=#@])):
> > > > > >> > >
> > > > > >> > > t=: '.'
> > > > > >> > > ast=: t;(t;t);(t;(t;t);t);<(t;(t;t;t);(t;t;t);t)
> > > > > >> > > f=: {{(],(>:x) f >@[)/ |. x ;`(<@[)@.(0=#@]) }.y}}
> > > > > >> > > 0 ;@f ast
> > > > > >> > > 0 1 2 1 2 3 2 1 2 3 3 2 3 3 2
> > > > > >> > >
> > > > > >> > > Hope that's somewhat comprehensible.
> > > > > >> > >
> > > > > ----------------------------------------------------------------------
> > > > > >> > > For information about J forums see
> > > > > http://www.jsoftware.com/forums.htm
> > > > > >> > >
> > > > > >> > ----------------------------------------------------------------------
> > > > > >> > For information about J forums see
> > > > > http://www.jsoftware.com/forums.htm
> > > > > >> >
> > > > > >> ----------------------------------------------------------------------
> > > > > >> For information about J forums see
> > > > > >> http://www.jsoftware.com/forums.htm
> > > > > ----------------------------------------------------------------------
> > > > > For information about J forums see http://www.jsoftware.com/forums.htm
> > > > >
> > > > ----------------------------------------------------------------------
> > > > For information about J forums see http://www.jsoftware.com/forums.htm
> > > ----------------------------------------------------------------------
> > > For information about J forums see http://www.jsoftware.com/forums.htm
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
