Binary tree in sysRPL challenge
manjo
I thought about how to implement
Binary tree (and variations) in sysRPL
Consider binary tree as fundamental structure to advanced decision-based
programming.
Can be base to AI and neural network simulatons as well.
anyone interested in the subject ?
(i'm not sure if i saw a demo program to build, analyse, traverse and delete
a binary tree)
manjo
Veli-Pekka Nousiainen
[VPN]
"manjo" <not-avail...@rocketmail.com> wrote in message
news:cnl95e$s18$1...@ls219.htnet.hr...
manjo
> [VPN]
why VPN ?
-is trinary tree a problem for you ? :-)
just think of third branching condition -and there you go
(if we speak of classic tree building method based on relation between tree
content and new input)
trees with multiple branching have (naturaly) far more complex decision
methods
-therefore they are excellent for neural-simulations
don't you just love trees ?
(both in nature and virtual)
immagine 3D scene organised in tree structure
2 ways subrtrees are connected to parrent wich is actualy object in front,
the object itself if a set of faces which are again organized in tree
structure perpaired for "painter's algorithm" (sorted by depth).
This could become a true mess :-) but it woul dbe interesting to see how it
would work :-)
manjo
Khanh-Dang
> I thought about how to implement
> Binary tree (and variations) in sysRPL
> anyone interested in the subject ?
I use lists as implementation of binary trees :
{ value subtree1 subtree2 }
It's not very fast, but maybe because I am using an "old" hp49 with UserRPL.
I think the best way is to store a tree within a library data :
LIBDAT SIZE
NODE_1 PtrToSubtreeLeft_1 PtrToSubTreeRight_1
...
NODE_n PtrToSubtreeLeft_n PtrToSubTreeRight_n
A special value (NULL for example) could be assigned to PtrToSubTree if
the node is a leaf (terminal node).
All the routines could easily be written is ASM. In fact, the dificulty
is that you have to program recursively and as the Saturn processsor has
a very poor return stack, you have to implement your own one. I don't
know about the ARM but I think it can handle return stack in RAM.
manjo
"Khanh-Dang" <k...@fr.invalid> wrote in message
news:419f733a$0$7241$8fcf...@news.wanadoo.fr...
I agre :
Saturn was not designed for recursions, on the other hand ARM has
excellent stack and stack dedicated instruction as well as stack dedicated
register.
sysRPL has great recursion abilities, and is somwhat faster than userRPL
your userRPL solution is great -by using lists you have it all done, memory
allocation, and
"addressing" by the item number.
nice work -this is great solution
can you think of a way to traverse binary tree in non-recursive manner ?
manjo
Khanh-Dang
> can you think of a way to traverse binary tree in non-recursive manner ?
What do you excatly mean by "traverse a binary tree" ? Does it mean to
give the list of all the tree's elements ?
If you chose to implement a binary tree by a recursive structure, such
as the one I gave in a post above : { value subtree1 subtree2 }, you
*have to* program with recursion, unless you have some other assumptions
about the tree.
Fo example, if you assume that your binary tree is complete (I don't
know if this is the good english word (in french : "arbre binaire
complet"), i.e. each node has two (not one, nor zero !) subtrees, apart
from the terminal nodes (the leaves), and all leaves must have the same
height+/-1 ("hauteur" in french). Then, you can acces an element
directly by calculating its memory address.
That's why you can then store all your elements in an array (it's called
a "heap" if I my memory is not deficient :). If you are considering an
element whose index in the array is k, then its subtrees (if they exist)
has as indexes : 2k+1 and 2k+2. Here, you can easily program without
recursion. *But* this involves that your binary tree is complete, which
is not always the case.
A very big and bad hack could be to always write a binary tree as
complete : you have to fill all the missing nodes by a constant
NULL_LEAF in the array. But as I've just said, this is a big hack
because it's not very memory efficient. For exemple, let's consider the
following integers-binary tree :
5
\
1
/ \
2 9
is equivalent to the following complete binary tree (the stars * stands
for NULL_LEAF) :
5
/ \
* 1
/ \ / \
* * 2 9
which can be stored in memory as the following array of integers :
[5 0 1 0 0 2 9]
if you choose 0 as the constant NULL_LEAF (that's mean you assume that 0
cannot be a value of your binary tree). Practically, you can choose
NULL_LEAF as infinite i.e. #fffff for a SysRPL bint.
As you can see, with this hack, you lost 3*sizeof(int) bytes in memory.
But it's fast, because accessing an element in an array is fast.
However, generally speaking, because of the recursive mathematical
definition of a tree, it's very difficult to avoid recursive
programming. In fact, I don't think this is possible.
And one more time, please excuse my bad english :)
Claudio Lapilli
"manjo" <not-avail...@rocketmail.com> wrote in message
news:cnl95e$s18$1...@ls219.htnet.hr...
It is a very interesting subject, of course.
Some time ago I wrote an expression evaluator that creates and manages a
dependency tree for a set of formulas. In the end it works like a
spreadsheet. I've been using it for a while for my work and it seems to be
reasonably stable.
Basically, I wrote a special STO function, that whenever you store a formula
into a variable, it stores the formula in a separate directory, evaluates
the formula end stores the result in the variable.
At the same time, it analyzes the formula and creates a dependency tree.
This way you can do:
4 'B' MySTO
5 'A' MySTO
'A+B' 'C' MySTO
And you will get a 9 stored in 'C' but the formula is saved in a different
variable.
Now if you do:
0 'A' MySTO
It will traverse the dependency tree and correctly update every variable
depending on A. In this example, C will be automatically recalculated to be
4.
The most tricky part is to avoid duplicate references and keep the order of
the dependencies in a mathematically correct order (specially when you purge
variables, for which I created a special purge too).
It's written in 100% SysRPL. You can get the sources if it "inspires" you :)
Claudio
manjo
i understand the theory matter you described here Khanh :-)
your choice of words is excellent, complete tree is exactly what you wanted
to say :-)
Great work Claudio, you're saying that you used tree structure to evaluate
mathematical expressions
(strings) in your spread sheet program.
Khannk - i by traversing the tree i ment going trough the nodes similar to
recursive way -it should allow you
to print out sorted contents of the tree. I think (i'm not sure if it's a
fact) that every recursive function can be made in (more or less complex)
non-recursive way.
So it is possible that non-recursive function may turn out to be very
complex, but still simpler (or faster) than implementing your own stack (in
Saturn ASM case).
manjo