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
