From: ma005
Subject: Loop problem
Date: 
Message-ID: <dd262bc0.0405240043.3376fdaa@posting.google.com>
Hello,
i have a problem with a lisp-function.

(defun closed (list1 list2)
     (setq el-list (car list1))
     (cond ((equal list1 nil) nil)
           ((closed_test list2 el-liste) T)
           (T (loop (setq y (closed (cdr list1) (append list2 (list
(car el-list)))))
                    (setq el-list (cdr el-list)
                    (when (or (equal el-list nil) y) (return y))) )))

list1 is a list of lists. list2 contains just elements. the function
should traverse a tree and make some comparing, if there are an
element and its negative. for easy testing, you could replace the
closed_test with a simple member test i think.
it works, when initialised with arguments in list2 for these. but
list2 should be a dummy when initialised and build up itself. the
function does work for the left side, but not further.
an example:

(closed '((a b c) (d e -c)) '(dummy)))

does testing, recursion with (add a to el-list), (rest of list1),
testing - neg,
go back, next loop with recursion: (add b to el-list), (rest of
list1), ..

-> but that step never happens .. why? it goes up the tree with the
neg results from the last step (list1 nil), but the level above list1
isn't nil anymore and the result is not positive either .. so there
should come the next action of the loop.

looks very confusing, hope you get the point and can help me.
thanks in advance,

martin adam

From: Kenny Tilton
Subject: Re: Loop problem
Date: 
Message-ID: <cpnsc.55193$mX.19847711@twister.nyc.rr.com>
ma005 wrote:

> Hello,
> i have a problem with a lisp-function.
> 
> (defun closed (list1 list2)
>      (setq el-list (car list1))
>      (cond ((equal list1 nil) nil)
>            ((closed_test list2 el-liste) T)
>            (T (loop (setq y (closed (cdr list1) (append list2 (list
> (car el-list)))))
>                     (setq el-list (cdr el-list)
>                     (when (or (equal el-list nil) y) (return y))) )))
> 
> list1 is a list of lists. list2 contains just elements. the function
> should traverse a tree and make some comparing, if there are an
> element and its negative. for easy testing, you could replace the
> closed_test with a simple member test i think.

You /think/? :) You might have better luck if you provided full working 
(albeit poorly) examples rather than leaving it to folks to fill in 
these small missing pieces. The above has an undeclare el-list and a 
missing parens after the second (setq el-list...), and rather than guess 
at how to replace closed_test, do so. el-liste? y?

> it works, when initialised with arguments in list2 for these. but
> list2 should be a dummy when initialised and build up itself. the
> function does work for the left side, but not further.
> an example:
> 
> (closed '((a b c) (d e -c)) '(dummy)))

Great. What output do you expect? where do you expect it? in el-list? as 
the function return value?

> 
> does testing, recursion with (add a to el-list), (rest of list1),
> testing - neg,
> go back, next loop with recursion: (add b to el-list), (rest of
> list1), ..
> 
> -> but that step never happens .. why? it goes up the tree with the
> neg results from the last step (list1 nil), but the level above list1
> isn't nil anymore and the result is not positive either .. so there
> should come the next action of the loop.

This bit is more helpful in that it is very specific about what you 
expect to have happen, but I am afraid I cannot quite follow it.

> 
> looks very confusing, hope you get the point and can help me.
> thanks in advance,


Confusing, indeed. I played with it for a while and the longer I played 
the more I realized that I had no idea what results were expected.

I think you can probably sort it out your self if you put in some print 
diagnostics and stare at the output. Or at least you will have a more 
specific question. I cleaned up the code and added some print's:

(defun closed (list1 list2 &aux el-list)
   (print `(entry ,list1 ,list2))
   (setq el-list (car list1))
   (cond ((equal list1 nil) (print '(exit 1 nil)) nil)
     ((member list2 el-list) (print '(exit 2 t)) t)
     (T (loop (let ((result (closed (cdr list1)
                              (append list2 (list
                                             (car el-list))))))
                (setq el-list (cdr el-list))
                (when (or (equal el-list nil) result)
                  (print `(exit 3 ,result)) (return result)))))))

Most important, /do/ tell us what output you expected from the example.

Bon chance, kenny

-- 
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: ma005
Subject: Re: Loop problem
Date: 
Message-ID: <dd262bc0.0405250120.62fb722d@posting.google.com>
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<·······················@twister.nyc.rr.com>...
> ma005 wrote:
> 
> > Hello,
> > i have a problem with a lisp-function.
> > 
> > (defun closed (list1 list2)
> >      (setq el-list (car list1))
> >      (cond ((equal list1 nil) nil)
> >            ((closed_test list2 el-liste) T)
> >            (T (loop (setq y (closed (cdr list1) (append list2 (list
> > (car el-list)))))
> >                     (setq el-list (cdr el-list)
> >                     (when (or (equal el-list nil) y) (return y))) )))
> > 

> You /think/? :) You might have better luck if you provided full working 
> (albeit poorly) examples 

yes i do think. you can use the member-function instead of
closed_test, this would just be a bit trivial for the function itself.
the whole thing is part of an algorithm for the sat-problem. so the
closed_test just tests, if the "not" of the elements of a list is in
another list.

i have no internet access at home, so i noted everything and didn't
want to note too much. thats also the reason for the simple var names
here and the missing parenthesis.

everything works fine, when list2 isn't a dummy. el-list is
instanciated later.
rather than leaving it to folks to fill in 

a better explanation now:

list1 - contains list.
list2 - is a list

algorithm:
1)el-list = first list of list1
2)if list1 empty - stop
3)if neg-elements of list2 are in el-list - stop
4)recursion ..
   [now it goes down as much steps as list1 has as number of lists]
   [if no success, then we have termination cond 2) -> level up]
5)y gets the value nil [no-success case]
6)remove first element of el-list (which should contain as much
arguments
                                  as numbers of lists in list1)
7)when el-list is empty now or y = T - stop
8) proceed at 4) with the smaller el-list

but theres a problem somewhere, steps 6-8 seem to be never executed. i
dont
know, if its a problem at the bottom or a problem with the termination
condition but for me it looks fine. 

example 2:
(closed '((a1 a2 a3) (a2 -a3 a4) (a1 a2 -a4)) '(dummy))
should do the following:
1. run: 
        el-list is (a1 a2 a3)
        no termination ->
  2. run: (closed '((a2 -a3 a4) (a1 a2 -a4)) '(dummy a1))
          el-list is (a2 -a3 a4)
          no termination ->
    3. run: (closed '((a1 a2 -a4)) '(dummy a1 a2))
            el-list is (a1 a2 -a4)
            no termination ->
      4. run: (closed '() '(dummy a1 a2 a1))
              el-list is NIL (i suppose)
              termination, cause list1 = NIL -> back to 3.run
            y = nil
            el-list is (a2 -a4)
            no termination (y not T, el-list not NIL) -> loop
      5. run: (closed '() '(dummy a1 a2 a2))
          ...
      6. run: (closed '() '(dummy a1 a2 -a4))
          ...
            termination, cause el-list = NIL
          y = nil  
          el-list is (a2 -a4)??
 
i'm too confused now, have to make it in my head. this is what is
supposed
to happen, but does not. there are no 5. and 6. runs.
the last level of the recursion seems useless, but that is not that
important i think. the comparisons are made earlier, so it should
work. but i think that is another problem, not the actual.

thx in advance. martin adam
From: Kenny Tilton
Subject: Re: Loop problem
Date: 
Message-ID: <O7Hsc.60225$mX.20160974@twister.nyc.rr.com>
ma005 wrote:

> Kenny Tilton <·······@nyc.rr.com> wrote in message news:<·······················@twister.nyc.rr.com>...
> 
>>ma005 wrote:
>>
>>
>>>Hello,
>>>i have a problem with a lisp-function.
>>>
>>>(defun closed (list1 list2)
>>>     (setq el-list (car list1))
>>>     (cond ((equal list1 nil) nil)
>>>           ((closed_test list2 el-liste) T)
>>>           (T (loop (setq y (closed (cdr list1) (append list2 (list
>>>(car el-list)))))
>>>                    (setq el-list (cdr el-list)
>>>                    (when (or (equal el-list nil) y) (return y))) )))
>>>
> 
> 
>>You /think/? :) You might have better luck if you provided full working 
>>(albeit poorly) examples 
> 
> 
> yes i do think.

I was not making a stupid joke, I was saying "don't ask us to find out 
if it works, find out yourself and then post code using "member" so you 
do not even have to go into the issue of substituting for closed_test.

You can use hyphens for closed-test, btw.

  you can use the member-function instead of
> closed_test,...


  this would just be a bit trivial for the function itself.
> the whole thing is part of an algorithm for the sat-problem. so the
> closed_test just tests, if the "not" of the elements of a list is in
> another list.
> 
> i have no internet access at home, so i noted everything and didn't
> want to note too much. thats also the reason for the simple var names
> here and the missing parenthesis.

OK.

> 
> everything works fine, when list2 isn't a dummy.

I do not understand what you mean. Just show the call which works. Less 
English, more code.


  el-list is
> instanciated later.
> rather than leaving it to folks to fill in 
> 
> a better explanation now:
> 
> list1 - contains list.

I think you mean "is a list of lists"

> list2 - is a list
> 
> algorithm:
> 1)el-list = first list of list1
> 2)if list1 empty - stop
> 3)if neg-elements of list2 are in el-list - stop
> 4)recursion ..
>    [now it goes down as much steps as list1 has as number of lists]
>    [if no success, then we have termination cond 2) -> level up]
> 5)y gets the value nil [no-success case]
> 6)remove first element of el-list (which should contain as much
> arguments
>                                   as numbers of lists in list1)
> 7)when el-list is empty now or y = T - stop
> 8) proceed at 4) with the smaller el-list
> 
> but theres a problem somewhere, steps 6-8 seem to be never executed. i
> dont
> know, if its a problem at the bottom or a problem with the termination
> condition but for me it looks fine. 
> 
> example 2:
> (closed '((a1 a2 a3) (a2 -a3 a4) (a1 a2 -a4)) '(dummy))
> should do the following:
> 1. run: 
>         el-list is (a1 a2 a3)
>         no termination ->
>   2. run: (closed '((a2 -a3 a4) (a1 a2 -a4)) '(dummy a1))
>           el-list is (a2 -a3 a4)
>           no termination ->
>     3. run: (closed '((a1 a2 -a4)) '(dummy a1 a2))
>             el-list is (a1 a2 -a4)
>             no termination ->
>       4. run: (closed '() '(dummy a1 a2 a1))
>               el-list is NIL (i suppose)
>               termination, cause list1 = NIL -> back to 3.run
>             y = nil
>             el-list is (a2 -a4)
>             no termination (y not T, el-list not NIL) -> loop
>       5. run: (closed '() '(dummy a1 a2 a2))
>           ...
>       6. run: (closed '() '(dummy a1 a2 -a4))
>           ...
>             termination, cause el-list = NIL
>           y = nil  
>           el-list is (a2 -a4)??
>  
> i'm too confused now, have to make it in my head. this is what is
> supposed
> to happen, but does not. there are no 5. and 6. runs.
> the last level of the recursion seems useless, but that is not that
> important i think. the comparisons are made earlier, so it should
> work. but i think that is another problem, not the actual.

I still cannot follow you, but those SETQs to undeclared el-list and y 
make me nervous. Do you mean for those to be global or local? Does your 
compiler give you a warning when you compile this code? I am concerned 
that they are being treated as globals when you do not want them to be. 
But, again, I am not sure if you want them to be global.

I cleaned up your code, made el-list and y local as a guess, added a 
print statement which shows depth, got this:

(defun closed (list1 list2 &optional (depth 0))
   (declare (optimize (speed 2) (safety 3) (space 1) (debug 3)))
   (format t "~&~v,4tenter l1=~a, l2=~a" (* depth 4) list1 list2)
   (let ((el-list (car list1)))
     (cond
      ((equal list1 nil) nil)
      ((member list2 el-list) T)
      (T (loop
           (let ((y (closed (cdr list1)
                      (append list2
                        (list (car el-list)))
                      (1+ depth))))
             (setq el-list (cdr el-list))
             (when (or (equal el-list nil) y)
               (return y))))))))

(closed '((a1 a2 a3) (a2 -a3 a4) (a1 a2 -a4))
   '(dummy))

0[1]: (CLOSED ((A1 A2 A3) (A2 -A3 A4) (A1 A2 -A4)) (DUMMY))
     enter l1=((A1 A2 A3) (A2 -A3 A4) (A1 A2 -A4)), l2=(DUMMY)
     enter l1=((A2 -A3 A4) (A1 A2 -A4)), l2=(DUMMY A1)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A1 A2)
             enter l1=NIL, l2=(DUMMY A1 A2 A1)
             enter l1=NIL, l2=(DUMMY A1 A2 A2)
             enter l1=NIL, l2=(DUMMY A1 A2 -A4)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A1 -A3)
             enter l1=NIL, l2=(DUMMY A1 -A3 A1)
             enter l1=NIL, l2=(DUMMY A1 -A3 A2)
             enter l1=NIL, l2=(DUMMY A1 -A3 -A4)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A1 A4)
             enter l1=NIL, l2=(DUMMY A1 A4 A1)
             enter l1=NIL, l2=(DUMMY A1 A4 A2)
             enter l1=NIL, l2=(DUMMY A1 A4 -A4)
     enter l1=((A2 -A3 A4) (A1 A2 -A4)), l2=(DUMMY A2)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A2 A2)
             enter l1=NIL, l2=(DUMMY A2 A2 A1)
             enter l1=NIL, l2=(DUMMY A2 A2 A2)
             enter l1=NIL, l2=(DUMMY A2 A2 -A4)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A2 -A3)
             enter l1=NIL, l2=(DUMMY A2 -A3 A1)
             enter l1=NIL, l2=(DUMMY A2 -A3 A2)
             enter l1=NIL, l2=(DUMMY A2 -A3 -A4)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A2 A4)
             enter l1=NIL, l2=(DUMMY A2 A4 A1)
             enter l1=NIL, l2=(DUMMY A2 A4 A2)
             enter l1=NIL, l2=(DUMMY A2 A4 -A4)
     enter l1=((A2 -A3 A4) (A1 A2 -A4)), l2=(DUMMY A3)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A3 A2)
             enter l1=NIL, l2=(DUMMY A3 A2 A1)
             enter l1=NIL, l2=(DUMMY A3 A2 A2)
             enter l1=NIL, l2=(DUMMY A3 A2 -A4)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A3 -A3)
             enter l1=NIL, l2=(DUMMY A3 -A3 A1)
             enter l1=NIL, l2=(DUMMY A3 -A3 A2)
             enter l1=NIL, l2=(DUMMY A3 -A3 -A4)
         enter l1=((A1 A2 -A4)), l2=(DUMMY A3 A4)
             enter l1=NIL, l2=(DUMMY A3 A4 A1)
             enter l1=NIL, l2=(DUMMY A3 A4 A2)
             enter l1=NIL, l2=(DUMMY A3 A4 -A4)
  0[1]: returned NIL
NIL

Is that better?

kenny

-- 
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: ma005
Subject: Re: Loop problem
Date: 
Message-ID: <dd262bc0.0405252334.4c3a43fe@posting.google.com>
i thank you and joe marshall. i will look at it now (when i'm at home)
and maybe respond this afternoon.


> I was not making a stupid joke, I was saying "don't ask us to find out 
> if it works, find out yourself and then post code using "member" so you 
> do not even have to go into the issue of substituting for closed_test.
> 

you are right. but my first thought was, you guys see the code, see
the mistake - in a tenth of a second. :D

> You can use hyphens for closed-test, btw.

how does this work? my lisp-exp. is from a course at the university
some time ago (the work is still for this course to get my note). and
we almost ever setq-ed free variables. my compiler (clisp for windows)
doesn't say anything about that.

> > everything works fine, when list2 isn't a dummy.
> 
> I do not understand what you mean. 

(closed '(xxxx) '(a1 a2)) tests correct for the elements a1 and a2.
but it should test itself and build that list correctly.

> I still cannot follow you, but those SETQs to undeclared el-list and y 
> make me nervous. Do you mean for those to be global or local? Does your 
> compiler give you a warning when you compile this code? I am concerned 
> that they are being treated as globals when you do not want them to be. 
> But, again, I am not sure if you want them to be global.

i definitely want them local. but i thought they were - i thought
wrong, i think now.

> I cleaned up your code, made el-list and y local as a guess, added a 
> print statement which shows depth, got this:
> 
> (defun closed (list1 list2 &optional (depth 0))
>    (declare (optimize (speed 2) (safety 3) (space 1) (debug 3)))
>    (format t "~&~v,4tenter l1=~a, l2=~a" (* depth 4) list1 list2)
>    (let ((el-list (car list1)))
>      (cond
>       ((equal list1 nil) nil)
>       ((member list2 el-list) T)
>       (T (loop
>            (let ((y (closed (cdr list1)
>                       (append list2
>                         (list (car el-list)))
>                       (1+ depth))))
>              (setq el-list (cdr el-list))
>              (when (or (equal el-list nil) y)
>                (return y))))))))
> 
> (closed '((a1 a2 a3) (a2 -a3 a4) (a1 a2 -a4))
>    '(dummy))
> 
 ->NIL

i suppose it shouldn't be nil, but i will find out. but it looks very
helpful.

many thanks,
martin adam
From: Pascal Costanza
Subject: Re: Loop problem
Date: 
Message-ID: <c8sqni$n9q$1@f1node01.rhrz.uni-bonn.de>
ma005 wrote:

> Hello,
> i have a problem with a lisp-function.
> 
> (defun closed (list1 list2)
>      (setq el-list (car list1))
>      (cond ((equal list1 nil) nil)
>            ((closed_test list2 el-liste) T)
>            (T (loop (setq y (closed (cdr list1) (append list2 (list
> (car el-list)))))
>                     (setq el-list (cdr el-list)
>                     (when (or (equal el-list nil) y) (return y))) )))

I don't quite understand what you are trying to do, but this codes 
contains a few problematic things.

- The variables el-list, el-liste (typo?) and y are not defined 
anywhere. Such so-called free variables are usually flagged by Common 
Lisp implementations, and many assume them to be global (special) 
variables. That's probably not what you want. When you want to introduce 
new local variables, you do that with let. For example:

(let ((el-list (car list1)))
   ...)

- There is a parenthesis missing in the second setq form inside the loop 
form. Are you using a Lisp-aware editor? If not, you should definitely 
do so.

- I think it's easier to describe a tree traversal with recursion 
instead of iteration. From your description, I think the intended 
functionality should be roughly as follows:

(defun closed (list1 list2)
   (cond ((null list1) nil)
         ((closed-test list2 list1) t)
         (t (or (closed (car list1))
                (closed (cdr list1))))))

Again, I am not quite sure what you are trying to achieve, so this 
probably doesn't do what you need, but maybe it gives the some hints how 
to improve your code.


Pascal

-- 
ECOOP 2004 Workshops - Oslo, Norway
*1st European Lisp and Scheme Workshop, June 13*
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
*2nd Post-Java Workshop, June 14*
http://prog.vub.ac.be/~wdmeuter/PostJava04/
From: Joe Marshall
Subject: Re: Loop problem
Date: 
Message-ID: <y8ngbmkm.fsf@ccs.neu.edu>
···········@gmx.de (ma005) writes:

> Hello,
> i have a problem with a lisp-function.
>
> (defun closed (list1 list2)
>      (setq el-list (car list1))
>      (cond ((equal list1 nil) nil)
>            ((closed_test list2 el-liste) T)
>            (T (loop (setq y (closed (cdr list1) (append list2 (list
> (car el-list)))))
>                     (setq el-list (cdr el-list)
>                     (when (or (equal el-list nil) y) (return y))) )))

You are SETQ'ing free variables.  Such behavior is undefined, but is
likely to modify the symbol value of the related symbol.  When you
make the recursive call to CLOSED, it will bash the value of el-list,
so when the call returns, (setq el-list (cdr el-list)) will not do
what you think it will.

Also, in this form:  (append list2 (list (car el-list))) you are using
APPEND to `cons on the far end of the list'.  This is a slow operation
and because you have put it in a loop, you have changed your algorithm
from linear to quadratic (never a good idea).

CLOSED appears to be a predicate (a function returning true or
false).  Conventionally, a predicate would be named "closed-p" or
"closed?".  The code appears to be manipulating sets of elements which
are represented as lists.  LIST1 is a list of sets, LIST2 is a set.
If LIST1 is empty (there are no sets), then CLOSED returns NIL.  If
list2 is closed_test within the first set in LIST1, then CLOSED
returns T.  Finally, if LIST2 is not closed_test within the first set
in LIST1, you incrementally add the elements of that first set to
list2 while simultaneously walking down the list of remaining sets.
If any are CLOSED, the answer is true.

(defun closed-p (list-of-sets set)
  (if (null list-of-sets)
      'NIL
      (do ((set-to-check    set                (extend (car elements-to-add) set))
           (elements-to-add (car list-of-sets) (cdr elements-to-add))
           (remaining-sets  list-of-sets       (cdr list-of-sets)))
          ((null remaining-sets) NIL)
        (when (closed_test set (car remaining-sets))
           (return 'T)))))

This, I *think* is what you were trying to get at.  The undefined
function EXTEND either conses the element on to SET if the order
doesn't matter, or uses APPEND if the order does matter.