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
