How to modify list within a list by reference?

[itistoday]

I'm trying to create a tree class using the data-type macro Lutz introduced. The class is created like so:

Code: Select all

(data-type (tree data children))

data can be anything, and children is a list of other trees. So say I want to define a function (or macro, don't know which) called tree:add-child that takes a tree node and a child node and adds the child to the parent node's children list. How do I do this without copying data? I just want to update the list inside the parent without having to duplicate and replace it.

If the data is an integer, then an example of a node containing 2 leaf nodes is this:

Code: Select all

(tree 0 ((tree 1 ()) (tree 2 ())))

Also, I do not want this to be a solution involving creating a context for every object, because I want to be able to refer to these things anonymously and in general that's not a very elegant solution as it requires that you have a naming scheme for your context symbols (like tree1, tree2, etc...).

Any help is much appreciated!

[itistoday]

On a similar note, how would one implement something like a binary search tree in newLISP without having to generate named contexts? It doesn't seem ... possible.

[cormullion]

binary trees? - i think this code is something to do with them. But don't ask me to explain it - I don't understand a word - or a leaf - of it... I sometimes collect stuff I don't understand for a rainy day... :)

Code: Select all

;;---------------------------------------------------------------------------
;; Labeled binary trees.
;;---------------------------------------------------------------------------

(define (make-TREE label left right)
  (list 'labeled-binary-tree label left right))

(define (is-TREE x) 
  (and (list? x) (= (first x) 'labeled-binary-tree)))

(define (TREE-label tree) (tree 2))

(define (TREE-left tree) (tree 3))

(define (TREE-right tree) (tree 4))

(define (set-TREE-label tree value) 
  (nth-set (tree 2) value))

;;---------------------------------------------------------------------------
;; Display the contents of a binary tree in depth-first order.
;;---------------------------------------------------------------------------

(define (TREE-display tree)
  (cond ((null? tree))
        (true (print (TREE-label tree))
           (TREE-display (TREE-left tree))
           (TREE-display (TREE-right tree)))))

;;---------------------------------------------------------------------------
;; Find the binary subtree with the specified label.
;;---------------------------------------------------------------------------

(define (find-subtree tree label)
  (cond ((null? tree) nil)
        ((= label (TREE-label tree)) tree)
        (true (or (find-subtree (TREE-left tree) label)
               (find-subtree (TREE-right tree) label)))))

;;---------------------------------------------------------------------------
;; Build a depth 3 binary tree labeled according to depth-first traversal.
;;---------------------------------------------------------------------------

(define (make-depth-3-binary-tree )
  (make-TREE 1 (make-TREE 2 (make-TREE 3 '()'())
                            (make-TREE 4 '()'()))
               (make-TREE 5 (make-TREE 6 '()'())
                            (make-TREE 7 '()'()))))

;;---------------------------------------------------------------------------
;; Build a depth n binary tree labeled according to depth-first traversal.
;;---------------------------------------------------------------------------

(define (make-binary-tree n)
  (make-depth-n-binary-tree n 1))

(define (make-depth-n-binary-tree depth root-label)
  (cond ((= depth 0) '())
        (true (make-TREE root-label 
                      (make-depth-n-binary-tree (- depth 1)
                                                (+ root-label 1))
                      (make-depth-n-binary-tree (- depth 1)
                                                (+ root-label
                                                   (exp 2 (- depth 1))))))))

[Lutz]

Also, I do not want this to be a solution involving creating a context for every object, because I want to be able to refer to these things anonymously and in general that's not a very elegant solution as it requires that you have a naming scheme for your context symbols

Read chapter "17. Object-Oriented Programming in newLISP" in the latest development version 9.2.8 manual.

This chapter introduces you to FOOP (Functional Object Oriented Programming), a way to to OO in newLISP using anonymous objects. In FOOP objects are created using normal lists, only methods for a specific object class are collected in a class context, but objects itself can be anonymous.

See also this page http://newlisp.org/index.cgi?page=newLISP-FOOP which explains why FOOP was developed.

To program a binary tree, no OO is required at all, as the program Cormullion posted, shows.

If you are new to newLISP, I recommend to get acquainted with the functional way of programming first, as it is the main paradigm in newLISP and an important ingredient (the F ;-) ) in FOOP.

Lutz

[itistoday]

Thanks for your replies and the binary tree example, but I'm still worried that it won't work the way I want. For example, what will this do:

Code: Select all

(set-TREE-label (find-subtree tree 5) 2000)

Will that update what's in the tree itself, or will that only update a copy of what was in the tree?


Edit: I'm trying to test this on my own but I'm getting nil ... e.g. this prints out nil:

Code: Select all

(set 'my-tree (make-depth-3-binary-tree))
(println (find-subtree my-tree 3))

(I fixed the problem, see below)

[itistoday]

OK, I fixed the problem, the code had a bug in the indexing, it should be:

Code: Select all

(define (TREE-label tree) (tree 1)) 
(define (TREE-left tree) (tree 2)) 
(define (TREE-right tree) (tree 3)) 
(define (set-TREE-label tree value) 
  (nth-set (tree 1) value))

And also, I was right, this method does not allow you to easily modify the data inside the tree... Here's an example of what I want to do:

Code: Select all

(set 'my-tree (make-depth-3-binary-tree))
(set-TREE-label (find-subtree my-tree 3) 2000)

(println "3: " (find-subtree my-tree 3))
(println "2000: " (find-subtree my-tree 2000))

I want that to print:

Code: Select all

3: nil
2000: (labeled-binary-tree 2000 () ())

But instead it does the opposite because nothing was changed. So my question is ... how do you do this in newLISP without jumping through crazy hoops or copying large amounts of data? Or similarly, as I asked in the first post, how do you add children to an already existing tree without copying the entire thing or generating a million contexts? (and with those you've got to deal with the overhead of newLISP's red-black tree for symbol lookup).

[cormullion]

Hi, itistoday! I don't understand your tree stuff, and I don't know what application you're working on, but I don't understand why it's not possible to use normal newlisp list operators on your trees.

Here's an example I do understand. Say I have the periodic table in XML, and I've converted it to SXML:

Code: Select all

...(ATOM ((STATE "SOLID")) (NAME "Gold") (ATOMIC_WEIGHT "196.9665") 
 (ATOMIC_NUMBER "79") 
 (OXIDATION_STATES "3, 1") 
 (BOILING_POINT ((UNITS "Kelvin")) "3130")...

Now suppose I want add another field - say the Latin name for Gold. First get a reference:

Code: Select all

(set 'gold-ref (ref "Gold" sxml))
;-> (0 8 2 1)

To find its parent:

Code: Select all

(sxml (chop gold-ref))
;-> (NAME "Gold")

To replace it with a new sublist containing both English and Latin names (ie (NAMES (ENGLISH "Gold") (LATIN "Aurum")) ):

Code: Select all

(nth-set (sxml (chop gold-ref)) (list 'NAMES (list 'ENGLISH (sxml gold-ref)) (list 'LATIN "Aurum")))

Now the list is :

Code: Select all

... (ATOM ((STATE "SOLID")) (NAMES (ENGLISH "Gold") (LATIN "Aurum")) 
 (ATOMIC_WEIGHT "196.9665") 
 (ATOMIC_NUMBER "79") ...

What I don't know is whether this does any of the copying or affects that red/black overhead (?) you're concerned about.

[Lutz]

Use LISP's list structure to model the binary tree directly (many ways to do this):

(set 'tree '(a (b (ba bb)) (c (ca (caa cab)) (cb cc))))

When you recursevely walk down the tree comparing nodes and leaves remember the indices, i.e.

a -> 0

bb -> 1 1 1

ca -> 2 1 0

then use 'push', pop' and 'nth-set' to insert, delete or modify nodes.

A tree build like the above, uses much less memory then a tree build with an object oriented model where you have to store left and right pointers to other nodes.

After all this is LISP, where the list is a flexible data structure, able to represent any kind of tree or other complex data structure ;-)

newLISP is unique how it can work on nested lists, like above tree. It has functions like 'push', 'pop', 'net-set' and 'ref', which all can take multiple indices or index vectors (indices in a list) and 'push', 'pop', 'net-set' can change the data ther are working on.

Lutz

ps: cormullion and I posted at the same time, his is a good example how to modify nested lists with 'nht-set' and make lookups with 'ref'

[itistoday]

Thank you both! Using 'ref' and 'nth-set', that's what I was looking for! Coming from far-away lands that always had references, I'm not used to this method of mutably modifying things.

Thanks again!

[itistoday]

Is it possible for there to be a hypothetical built-in function called 'unsafe-ref' that returned an internal reference (pointer) to something? Then you'd be able to do things like this without having to walk down the tree/list twice (once to find the indices, and once again for nth-set to follow them back down to update the node). It would also add greater flexibility to what newLISP could do I think... at the cost of potential crashes. :-p

[cormullion]

Are you thinking about speed? The need for speed...?! :) I wonder how big your lists are going to be... What's the application, out of interest?

[itistoday]

Are you thinking about speed? The need for speed...?! :)

Oh... why yes, most definitely. :)

I wonder how big your lists are going to be... What's the application, out of interest?

It's for my artificial intelligence final class project. I was originally planning on using a tree, but since I ran out of time I decided to go with a simpler method... Essentially I wrote a program in newLISP that tried its best to eliminate as many pieces as possible from a ChainShot game.

If you haven't heard of ChainShot, and you have a Mac, you can download a free version of it here: http://www.wonderwarp.com/otis/. Here's a screenshot of a typical board mid-game:



The game works like this: the player clicks on blocks, and if the block that they click on has any pieces around it (above, below, left or right) that are of the same color, then all of the pieces that are adjacent to those and are the same color will be eliminated (including the block that was clicked on). Then any pieces above those will fall down, and if an entire column is eliminated then any columns to the right of that will be slid over to the left to eliminate all gaps. The game ends when there are no possible moves left.

As you can imagine (if I had time to go with the tree version of the algorithm) the tree would get really big for a 20x20 board. As it turned out I wasn't able to do that because I didn't know how to do that quickly in newLISP, and because I came up with an alternate algorithm that was faster to implement and worked pretty well to boot. I also made it multi-"threaded" using newLISP's 'fork' function. :)

Usually it did a pretty darn good job of solving them in a reasonable amount of time (under a minute), especially if the boards were less than size 20x20.

[Lutz]

Perhaps you are looking for is some sort of associative data access. A way to access a piece of information via a key pointing to a data-value. This is what binary-trees are used for in 99% of the cases.

newLISP has bult-in very fast associative data access by usage of contexts/namespaces, which internally are binary trees (the red-black kind of optiized binary tree.

Here is short chapter in the manual with examples, which might help you:

http://newlisp.org/downloads/newlisp_manual.html#hash

Lutz

[itistoday]

Perhaps you are looking for is some sort of associative data access. A way to access a piece of information via a key pointing to a data-value. This is what binary-trees are used for in 99% of the cases.

Well actually the binary tree was just an example, the original tree that I had in mind was like the one I gave in the first post, where it could have an arbitrary number of children. The main thing I wanted to be able to do was to quickly add/remove children from it.

newLISP has bult-in very fast associative data access by usage of contexts/namespaces, which internally are binary trees (the red-black kind of optiized binary tree.

Here is short chapter in the manual with examples, which might help you:

http://newlisp.org/downloads/newlisp_manual.html#hash

Lutz

Yeah I've read that, those are cool, but not exactly what I needed for this project. I still think you should consider adding the 'unsafe-ref' function (or something like it). :-D

[Fanda]

I implemented a simple memory allocation hack:

Code: Select all

;; Simple memory allocation hack ;-)
;;

(context 'memory)

(if (not n)
  (set 'n 0))

(define (memory:new)
  (inc 'n)
  (sym (string "p" n)))


(set 'EMPTY-FIELD 'VOID)

(define (memory:delete ptr)
  (set ptr EMPTY-FIELD))

(define (memory:write ptr data)
  (if (!= (eval ptr) EMPTY-FIELD)
    (set ptr data)
    (throw-error (string "Memory field " ptr " does not exist!"))))

(define (memory:read ptr)
  (if (!= (eval ptr) EMPTY-FIELD)
    (eval ptr)
    (throw-error (string "Memory field " ptr " does not exist!"))))

(context MAIN)

Use it like this:

Code: Select all

;; *** Demo ***

;; p = malloc(sizeof(int));
(set 'p (memory:new))     ; => memory:p1

;; *p = 10;
(memory:write p 10)       ; => 10

;; x = *p;
(set 'x (memory:read p))  ; => 10

;; free(p);
(memory:delete p)         ; => memory:VOID

;; access error
(memory:read p)
=>
user error : Memory field p1 does not exist!
called from user defined function memory:read

Or create binary trees:

Code: Select all

;; * Binary tree *

; btree -> (data left-btree right-btree)

(define (btree-create-leaf ptr v)
  (set ptr (memory:new))
  (memory:write (eval ptr) (list v nil nil)))

(define (btree-add ptr v)
  (let (p nil ind 0)
    (if (< v (first (memory:read ptr)))
      (set 'ind 1)
      (set 'ind 2))

    (if (!= ((memory:read ptr) ind) nil)
      (btree-add ((memory:read ptr) ind) v)
      (begin
        (btree-create-leaf 'p v)
        (memory:write ptr (set-nth ((memory:read ptr) ind) p))))))


; fill it with numbers
(set 'numbers (randomize (sequence 1 10)))

(btree-create-leaf 'btree (first numbers))

(dolist (x (rest numbers))
  (btree-add btree x))

Walk through:

Code: Select all

> numbers
(4 8 1 2 6 10 9 7 5 3)
> btree
memory:p1
> (memory:read btree)
(4 memory:p3 memory:p2)
> (memory:read 'memory:p3)
(1 nil memory:p4)
> (memory:read 'memory:p2)
(8 memory:p5 memory:p6)

> (memory:read 'memory:p4)
(2 nil memory:p10)

> (memory:read 'memory:p5)
(6 memory:p9 memory:p8)
> (memory:read 'memory:p6)
(10 memory:p7 nil)

Using this approach, code readability goes down to... lets say... C/C++ ;-)))

Fanda

[cormullion]

Essentially I wrote a program in newLISP that tried its best to eliminate as many pieces as possible from a ChainShot game.

Nice project. Perhaps you could add a GUI to it one day..!

[itistoday]

I implemented a simple memory allocation hack:

Wow, that's pretty neat. It's still doing a context-like trick by using named symbols for the pointers, and evaluating a pointer takes log(n) time (b/c of the red-black tree), but that's still a really cool trick. Thanks for sharing!

Using this approach, code readability goes down to... lets say... C/C++ ;-)))

Well, almost, it's kinda difficult to make newLISP that bad. ;-)

[itistoday]

Essentially I wrote a program in newLISP that tried its best to eliminate as many pieces as possible from a ChainShot game.

Nice project. Perhaps you could add a GUI to it one day..!

Yeah, I think I might actually, once I finish all my finals for school. Then if there's time I might enter it into the '07 newLISP competition. :-D