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
