Hmm...
It looks like Hsu might have originally been trying to represent the
tree introduced on page 55 of his presentation. But that's difficult
in dyalog apl with scalar values as the nodes (because scalars have
"infinite depth" and thus cannot be further nested by themselves). The
initial illustration on page 61 seems to confirm this idea.
But, also, on that page, he's labelling the vector 0 1 2 1 2 3 2 1 2 3
3 2 3 3 2 as "type information", without any elaboration. And ...
that's not necessarily contradictory, but it's curious.
Anyways... it looks like that "depth vector in record format" was a
representation of the depth information described on that page 61.
And, it looks like 'ast' is a sort of encoding of that information. So
I guess it's sort of like a transpose of the tree, though I'm not sure
if that mechanism would be robust enough to represent arbitrary trees.
Meanwhile, there are some APL symbols which I do not recognize the
significance of in ∊ 0 {(⊢,(⍺+1)∇⊣)/⌽⍺,1↓⍵} y
⊢ ∇ and ⊣
Still, from your dv, I presume that these roughly correspond to J's ] $: and [
But, also, looking at the result, it's sort of like the leftmost value
is zero and each time you go one deeper you get a +1 and each time you
go one across you get +1 but that that stops if there's more than one
in a row at the same level. So it's awkward for me to think about this
mechanism from a "first principles" approach, because I don't feel
like I am seeing the whole picture.
I tried to investigate your dv like this:
N=:0
dv =: {{
if. 20 < N=: N+1 do. throw. end.
echo y
([echo) (];(>:x) dv [)/\ |.x;}.y
}}
t=:'.'
ast=:t;(t;t);(t;(t;t);t);(t;(t;t;t);(t;t;t);t)
But with these definitions, 0 dv ast crashes J.
I changed the definition of dv to
dv =: {{
if. 0=#y do. x return. end.
(];(>:x) dv [)/\ |.x;}.y
}}
And 0 dv ast still crashes J.
I changed the definition of dv to
dv =: 4 :0
if. 0=#y do. x return. end.
(];(>:x) dv [)/\ |.x;}.y
)
and ran it under j807, and I got a stack error.
So I threw in a better guard condition, and now I get a result, but it
doesn't look right (it's huge):
dv =: 4 :0
if. 0=#;<S:0 y do. x return. end.
(];(>:x) dv [)/\ |.x;}.y
)
Looking back at the original, it's using / not \ so I changed this to
dv =: 4 :0
if. 0=#;<S:0 y do. x return. end.
(];(>:x) dv [)/ |.x;}.y
)
And, now I get something close to Hsu's result:
;<S:0]0 dv ast
0 1 2 1 2 1 2 1 2 1 2 1 2
But it's not quite the same.
Possibly there's something about how u/ in dyalog apl works with
nested arrays that's the issue?
So I fiddled with dv just a bit more:
dv =: 4 :0
if. 1= #y do. y=.;y end.
if. 0=#y do. y return. end.
(];(>:x) dv [)/ |.x ;}.y
)
And that's closer
;<S:0]0 dv ast
0 1 2 1 2 3 2 1 1 2 2 1 2 2 1
but it's still not the same.
Anyways.. I am not prepared to go further here, because there's too
many things which I do not understand for me to reasonably guess the
missing pieces.
Thanks,
--
Raul
On Sun, May 23, 2021 at 7:16 PM Raoul Schorer <[email protected]> wrote:
>
> Hi Raul,
>
> What I am trying to do is a prerequisite to tree processing as in [1]. This
> page shows parent vectors built manually, but in Dr. Hsu's thesis [2] those
> are derived from the depth vector describing the tree, itself derived from
> the tree in "record format" ( p.66 of the pdf in [2] ). The purpose is fast
> manipulation of trees by total ordering of nodes in 2D space using 2 simple
> vectors (a. parent vector and b. left sibling vector), and the APL sentence
> I showed (p.73 in [2]) is the initial step in that process.
> Now, of course this cannot work as a literal translation from APL to J
> since the APL sentence designed for a nested APL array has to be adapted to
> the J boxed array model. That's what I am trying to do.
>
> I had your
>
> ;@(+L:0 L.)L:1^:_ L.L:0 ast
>
> as
>
> # S:1@{:: ast
>
> which yields the same answer less efficiently, but indeed that's not the
> desired result since it doesn't use the same tree model.
>
> I've been trying quite hard, but I'm completely stumped.
>
> [1] https://code.jsoftware.com/wiki/User:Devon_McCormick/Tree
> [2] caution, big file!
> https://scholarworks.iu.edu/dspace/bitstream/handle/2022/24749/Hsu%20Dissertation.pdf?sequence=1&isAllowed=y
>
> On Mon, May 24, 2021 at 12:42 AM Raul Miller <[email protected]> wrote:
>
> > The "no base case" phrase might mean that there's some infinite loop
> > transformation mechanism in the language.
> >
> > That said, I also don't understand that result.
> >
> > Here's the example value 'ast' represented in J:
> >
> > t=:'.'
> > ast=:t;(t;t);(t;(t;t);t);(t;(t;t;t);(t;t;t);t)
> >
> > And, here's the corresponding "depth vector in record format" mapped
> > back onto the corresponding positions in ast:
> >
> > 0;(1;2);(1;(2;3);2);(1;(2;3;3);(2;3;3);2)
> >
> > So either this result is wrong, or 'depth' in this context does not
> > have a simple relationship with 'depth' as we know it in J.
> >
> > Here's J's idea of the depths of each of the boxes:
> >
> > ;@(+L:0 L.)L:1^:_ L.L:0 ast
> > 1 2 2 2 3 3 2 1 2 2 2 2 2 2 1
> >
> > We could treat the top level box as depth 0 easily enough
> > <: ;@(+L:0 L.)L:1^:_ L.L:0 ast
> > 0 1 1 1 2 2 1 0 1 1 1 1 1 1 0
> >
> > But obviously that's still different from that "depth vector in record
> > format".
> >
> > Anyways... color me confused.
> >
> > Is there a simple way of describing the purpose of that "depth vector
> > in record format"?
> >
> > Thanks,
> >
> > --
> > Raul
> >
> > On Sun, May 23, 2021 at 2:35 PM Raoul Schorer <[email protected]>
> > 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:
> > >
> > > 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.
> > >
> > > An attempt at a partial litteral translation as:
> > >
> > > 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?
> > >
> > >
> > > Thanks,
> > >
> > > Raoul
> > > ----------------------------------------------------------------------
> > > 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
