building trees in j

Table of Contents

1 basic tree building operations

emit
splice some items into the current node
node
start a new node
done
finish a node (returning to the previous one)
drop
remove the last item
goto
go back to a node created earlier

2 a simple tree-builder implementation

The tree is a rank 1 array of parent indices (where _1 indicates root/null)

Here is a straightforward imperative definition of our primitives: 

tree =: $0   NB. stores the links to parents.
data =: $0   NB. stores the actual data items.
path =: $0   NB. the stack of parent nodes.
here =: _1   NB. the current parent node.

emit =: monad define "0
  tree =: tree, here
  data =: data, y
  tree
)

node =: monad define "_
  emit y
  path =: path, here
  here =: <: # tree
  tree
)

done =: monad define "_
  here =: {: path
  path =: }: path
  emit y
  tree
)

drop =: monad define "_
  data =: }: data
  tree =: }: tree
)

goto =: monad define "_
  path =: path, here
  here =: y
  tree
)

These verbs all return the tree as a convention, both to to make tracing simpler and to allow easy use in gerunds. (See s-expression parser, below).

3 queries

upfrom =: 3 : 'if. y=_1 do. _1 else. y{tree end.'"0
dnfrom =: 3 : 'if. 0=#y do. $0 else. I. +./"2 tree ="1 0 ;y end.'"1
above =: (_1 -.~ }.)&(upfrom f.^:a:)"0
below =: 13 : '; }. dnfrom each ^:a: < y'
depth =: #@above
treet =: 3 : '(i.#tree),.tree,.data' NB. tree table :)
index =: 3 : '(i.#tree)'

4 an example tree

reset =: verb define
  tree =: path =: data =: $ >: here =: _1
)
tree0 =: verb define
  emit i. 5
  node''
  emit 44 45 46
  done''
  emit 5 6
  node''
  emit 60 61 62
  done''
  goto 4
  emit 44
  done''
  goto data i. 61
  emit 610 611
  done''
)

5 in action

   reset''

   tree0''

   treet''
 0 _1   0
 1 _1   1
 2 _1   2
 3 _1   3
 4 _1   4
 5  4  44
 6  4  45
 7  4  46
 8 _1   5
 9 _1   6
10  9  60
11  9  61
12  9  62
13  4  44
14 11 610
15 11 611

   upfrom data i. 610
11
   data {~ upfrom data i. 610
61
   data {~ upfrom data i. 610 61
61 6
   data {~ above data i. 610
61 6
   data {~ below 4
44 45 46 44

6 TODO s-expression parser

Parsing lisp-style s-expressions is simply a matter of mapping each character to a corresponding tree builder routine: 

rsx =: (node`done`emit)@.('()' & i.)"0  NB. 'read s-expression'

In this version, every character is mapped to its own node, but it should be easy to update this to use j's sequential machine primitive to break the input into tokens first. (TODO) 

   NB. the trace is a large ugly matrix that shows the
   NB. tree at each step of the parse.
   trace =. rsx'(banana (creme (pie)))' [ reset''

   tree
_1 0 0 0 0 0 0 0 0 8 8 8 8 8 8 8 15 15 15 8 0 _1

   data
(banana (creme (pie)))

   NB. the characters grouped by parent:
   tree</.data
┌──┬─────────┬────────┬───┐
│()│banana ()│creme ()│pie│
└──┴─────────┴────────┴───┘

   NB. show depth of each character node graphically:
   |:(data ,~"0 1  '_' #~ "0 >:) depth index''
______________________
 ____________________
         ___________
                ___
(banana (creme (pie)))

7 maybe later

type =: $0   NB. a type marker for each node in the tree.
tags =: $.$0 NB. sparse array holding meta data about nodes.

8 treebuild.ijs

This code is maintained as a literate program with org-babel for emacs. You can retrieve it in any of three formats: 

<<builder>>
<<queries>>
<<example>>
<<rsx>>

9 references

Tree structure is based on:

Other helpful links: