walk tree iterator proposal

[Dmi]

Hi, Lutz!



Looking into rickiboy's comma-expand (and also into a few similar my own functions) I got an opinion, that it would be nice to have a hard-coded function for recursive tree iteration.



The main problems with such algorithms written in newlisp are:

1. Effective coding of tree-walk in newlisp needs two functions - external - as a dynamic variables holder and internal for recursive walk. When written, looks pretty ugly :-

2. The (if (list? item) (recursive-call item)) construct causes a multiple copying of a tested sublist (for passing as an argument). So for a list of depth of 10, each 10th-level element will be copied 10 times, each 9th-level sublist will be copied 9 times and so on. This makes the algorithm _incredible_ slow for a large deep lists.



Hardcoded version may behave like this:

(do-recursive (sym-val sym-pos sym-len sym-type lst) body)

that will behave like a dolist but

- the body is evaluated only for non-list items and for empty list items.

- sym-val is for a value (as in dolist)

- sym-pos is for current position in list tree (like for push and ref)

- sym-len is a length of a currently iterated sublist

- sym-type gets values '(), '(lambda) and '(lambda-macro) - empty ones - that will reflect the type of a sub-list, which item is currently processed.

Note, that in a body:

(= 0 (pos -1)) will reflect the beginning of a list.

(= sym-len (- (pos -1) 1) will reflect the last item of a sublist (but, probably, there could be another way)

Also It would be _very_ cool (imho) to have an ability in a body to "skip" a requested number of next items in a current sublist.



....something like this :-)

[Lutz]

Short term there will be no support for optimizing recursion, but did you explore passing lists by reference when packaged in a context? There is an example here: http://newlisp.org/downloads/newlisp_manual.html#pass_big">http://newlisp.org/downloads/newlisp_ma ... l#pass_big">http://newlisp.org/downloads/newlisp_manual.html#pass_big



This would avoid a lot of copying and speed things up for problems requiring complex deep level recursion.



What I am working on at the moment is a Prolog like unify function which will bring logic programming to newLISP in the next version. This will also help with some problem solutions otherwise written with recursions. unify works recursively  internally but that will be transparent to the user.



Lutz

[noah]

Hi, Lutz.



You wrote that you're adding a unify function. I studied formal logic quite a bit, and I've got an old reference on lisp that describes making unification work in lisp. I suspect your unification function will save its users some coding. Can you share an example of how you intend unify to work?



-Noah

[Dmi]

Hi, Lutz!

Unify is a big deal!



I've read pass_big. It's useful for a _big_ lists (as well as a dynamic scoping, I think), but not for _deep_ list problems.

I'll try to explain:

Code Select Expand

(define (recur-top lst)
  (let (res '()) ; dynamic scope result collector - for "pass_big"-like speedup
    (recur-func lst)
  res)

(define (recur-func lst)
  (dolist (l lst)
    (if (list? l) (recur-func l) (do-something-and-push-into-res))))

This is a common recursion technic. (Does anyone knows the better way?)

But here we have a problem: each time some _big_and_deep_ subpart of lts is copying when passed to recur-func, then it is copied by dolist and, finally, _each_ top level _beeg_and_deep_ sub-subpart is copied into l and, passed to recur-func and all starts again.



The short term of solving this is not much significant, I think. But till that time the deep lists will be a problem.



P.S. Also, probably, a few of the cell-pointer functions will be helpful here...

[Dmi]

I wrote some hack.

The functions are working with list by a cell pointers - no string/list data copying happens at all.



Practically it works. Is it quite legal?

Is there a place for some additional cleanup for safety?



Description:

If you want to iterate through a list, you call



(cell-get lst i)



and i now points to a first element of lst.



Then you call (cell-next i) to get the next one and inspect it by (cell-list?) - is it a list, and (cell-end?) - is the list finished.



If you encounter a list, you may save the curent position by



(cell-save i s)

(push s some-stack)



then descend into a sublist by



(cell-get i i)



If you reach an end of a sublist, for return to upper level you may do



(set 's (pop some-stack))

(cell-restore i s)



The code is:

Code Select Expand

(define-macro (cell-list? sym-cell)
  "(cell-list? sym-cell) - true if cell is list"
  (= 59 ((dump (eval sym-cell)) 1)))

(define-macro (cell-end? sym-cell)
  "(cell-end? sym-cell) - true if cell is beyond the end of a list"
  (= 256 ((dump (eval sym-cell)) 1)))

(define-macro (cell-get sym-lst sym-cell)
  "(cell-get sym-lst sym-cell) - assign first item of sym-lst to a sym-cell"
  (unless (list? (eval sym-lst))
   (throw-error "List expected"))
  (let (dmp (dump (eval sym-cell)))
    (cpymem (last (dump (eval sym-lst))) (first dmp) 16)))

(define-macro (cell-next sym-cell)
  "(cell-next sym-cell) - assign list-next element of sym-cell to a sym-cell"
  (let (dmp (dump (eval sym-cell)))
   (cpymem (dmp 2) (dmp 0) 16)))

(define-macro (cell-save sym-cell sym-storage)
  "(cell-save sym-cell sym-storage) - store sym-cell's dump into sym-storage's contents"
  (set sym-storage (dup " " 16))
  (cpymem (first (dump (eval sym-cell))) (address (eval sym-storage)) 16))

(define-macro (cell-restore sym-cell sym-storage)
  "(cell-restore sym-cell sym-storage) - restore sym-cell's dump from sym-storage's contents"
  (cpymem (address (eval sym-storage)) (first (dump (eval sym-cell))) 16))

and some working session:

Code Select Expand

> l
("cde" (12 13) "fgh" "ijk")
> (cell-get l t)
16
> t
cde
> (cell-next t)
16
> t
(12 13)
> (cell-save t s)
16
> (cell-get t t)
16
> t
12
> (cell-next t)
16
> (cell-end? t)
nil
> t
13
> (cell-next t)
16
> (cell-end? t)
true
> (cell-restore t s)
16
> t
(12 13)
> (cell-next t)
16
> t
fgh


If it is legal, then now it is possible to write a macro wrapper silmilar one I requested yesterday... Anyone can do it for it's own taste :-)

[Dmi]

Some additional notes:

- The cell-pointer symbol must be used read-only. Assigning anything to it will crunch your data.

- I suspect (but I'm not sure), that for a good sanity cell-pointer symbol also must be saved before first use with (cell-save) and then restored before releasing from stack with (cell-restore).

[newdep]

Im offshore for some weeks and im already missing the fun... ;-)



Did not read it all but if its about "deep" nested sorts/seeks of lists ..oww that

would be nice... But lutz can you tell a little more about the Unify ?



Regards, Norman

[Lutz]

Here is the long story: http://en.wikipedia.org/wiki/Unification">http://en.wikipedia.org/wiki/Unification



'unify' is implemented and will be released with development version 8.8.7 later this week.



In short 'unify' is some kind of logical comparison of list terms with logical binding of unbound variable to terms. 'unify' fails or succeeds depending on what you throw at it. It succeeds returning a list of variabe associations or an empty list, and it fails returning 'nil'.



A function is worth a 1000 words, so here is a snippet from the qa-dot file to test unify:

Code Select Expand


(define (test-unify)
    (and  
        (= (unify 'X 123)
             '((X 123)))
        (= (unify '(Int Flt Str Sym Lst) '(123 4.56 "Hello" s '(a b c)))
             '((Int 123) (Flt 4.56) (Str "Hello") (Sym s) (Lst '(a b c))))
        (= (unify 'A 'A)
             '())
        (= (unify '(A B "hello") '("hi" A Z))
             '((A "hi") (B "hi") (Z "hello")))
        (= (unify '(A B) '(B abc))
             '((A abc) (B abc)))
        (= (unify '(B A)
             '(abc B)) '((B abc) (A abc)))
        (= (unify '(A A C D)
             '(B C 1 C)) '((B 1) (A 1) (C 1) (D 1)))
        (= (unify '(D C A A) '(C 1 C B))
             '((D 1) (C 1) (B 1) (A 1)))
        (= (unify '(f A) '(f (a b c)))
             '((A (a b c))))
        (= (unify '(A f) '((a b c) f))
             '((A (a b c))))
        (= (unify '(f (g A)) '(f B))
             '((B (g A))))
        (= (unify '(p X Y a) '(p Y X X))
             '((Y a) (X a)))
        (= (unify '(p X Y) '(p Y X))
             '((Y X)))
        (= (unify '(q (p X Y) (p Y X))
             '(q Z Z)) '((Y X) (Z (p X X))))
        (= (unify '(f (g A) A) '(f B xyz))
             '((B (g xyz)) (A xyz)))
        (= (unify '(A (g abc)) '(B A))
             '((B (g abc)) (A (g abc))))
        ;; with additional environment list
        (= (unify '(A (B) X) '(A (A) Z) '((A 1) (Z 4)))
            ' ((A 1) (Z 4) (B 1) (X 4)))




'unify' takes 2 or (plus an optional environment list) terms and retuns an association list. From a logical point of view unification happens with all terms in parallel. Variables (in uppercase) are not actually bound (like with set) but a special form of 'expand' taking an association list of variables can be used to accomplish this.



'unify' is useful to write logic programming algorithms, i.e. in AI Artificial Intelligence apps. A typical application would be Expert Systems or any knowledge based system where knowledge can be encoded in logical rules.



The release 8.9.0 out in June will contain a small implementation of a PROLOG like language using 'unify' and 'expand'. This Prolog context will be useful to write rule based systems.



Lutz

[noah]

Hello.



Lutz, thanks for your input on unify. It's very interesting, and your mini-prolog language will be a great educational tool for me.



DMI, your code is very interesting. I'm not spending much time on my newlispzation of xpath, but your code might be helpful there. I'm still very new at lisp, and I'm also quite busy, but when I have some substantial application of the great code everyone posts here, I'll be sure to post it.



-Noah

[rickyboy]

Unify does rock -- even more so will an embedded Prolog in newLISP.  NNYC* Alex Burger has an embedded Prolog in his http://software-lab.de/down.html">Pico Lisp, which makes it very powerful.  A favorite application of his is combining Pilog queries with his persistent object mechanism to produce some very powerful DB queries.  See http://software-lab.de/tut.html#pilog">this for examples.



______

* NNYC = Not Necessarily Your Competitor  :-)