Hello,
I am pretty much a newbie to lisp and I wrote a code for the resolution
of CNF's (conjunctive normal forms). I would like to know how
good/bad/ugly the code actually is and in what ways can it be made
better.
code :
;;; Solves CNF forms
;;; the macro resolve-list takes as input a list of the form
;;; ((expr1) (expr2) (expr3) ... )
;;; where each expr is of the the form ( var1 or var2 or ... not varN
...or varK )
(defpackage :cnf
(:use :common-lisp)
(:export 'resolve-list))
(in-package :cnf)
;;; function seperate-parts.
;;; Seperate parts splits the expression into variables that are
negated and those that
;;; are not negated.
(defun seperate-parts (expr1)
"Seperates the negated variables and the non-negated variables"
(let ((list-v ())
(list-vneg ())
(next ()))
(dolist (iter expr1)
(cond
((eq 'or iter) ())
((eq 'not iter) (setf next t))
(t (if next
(progn
(push iter list-vneg)
(setf next ()))
(push iter list-v)))))
(values list-v list-vneg)))
;;; function resolve-pair
;;; uses basic laws of logic to resolve 2 boolean expressions
containing only
;;; or's or not's.
(defun resolve-pair (expr1 expr2)
"Resolves a pair of conjunctive expressions"
(let ((list1 ())
(list2 ())
(nlist1 ())
(nlist2 ()))
(multiple-value-bind (lst nlst)
(seperate-parts expr1)
(setf list1 lst)
(setf nlist1 nlst))
(multiple-value-bind (lst nlst)
(seperate-parts expr2)
(setf list2 lst)
(setf nlist2 nlst))
;; rem-list is the list of variables that cancel out due to
negation.
;; allp-list is the list of variables that are not negated and can
occour in the final expression
;; alln-list is the list of variables that are negated and can
occour in the final expression
;; red-list1 is the pretty version of allp-list with the or's in
place
;; red-list2 is the pretty version of alln-list with the or's and
not's in place.
(let* ((rem-list (union (intersection list1 nlist2)
(intersection list2 nlist1)))
(allp-list (remove-if #'(lambda (x) (if (member x rem-list)
t nil))
(union list1 list2)))
(alln-list (remove-if #'(lambda (x) (if (member x rem-list)
t nil))
(union nlist1 nlist2)))
(red-list1 ())
(red-list2 ()))
(dolist (pitm allp-list)
(push pitm red-list1)
(push 'or red-list1))
(nreverse red-list1)
(dolist (pitm alln-list)
(push 'not red-list2)
(push pitm red-list2)
(push 'or red-list2))
;; since there is an extra or/not at the end.. which comes
as the first element..
;; we can skip it and hence only the cdr of the list is
returned.
(cdr (concatenate 'list (nreverse red-list1) (nreverse
red-list2))))))
(defmacro resolve-list (exprlist)
"resolves an entire set of infix expressions of the form
((expr1) (expr2) .... (exprn))"
`(reduce #'resolve-pair ,exprlist))
;;(end-package :cnf)
Cheers,
Vishnu Vyas.
I don't use Lisp much for this sort
of problem now because pattern
matching makes this simpler. Here
is a Qi (www.lambdassociates.org)
solution that you can adapt
for Lisp. Qi runs under Lisp.
Its easier if you treat a clause as a
list of literals. Here is the code for
propositional resolution with factoring
thrown in.
(define resolve
Clause1 Clause2 -> (resolve-help Clause1 Clause1 Clause2))
(define resolve-help
[] _ _ -> none!
[P | Ps] Clause1 Clause2 -> (union (remove P Clause1)
(remove (complement P) Clause2))
where (element? (complement P) Clause2)
[_ | Ps] Clause1 Clause2 -> (resolve-help Ps Clause1 Clause2))
(define complement
[~ P] -> P
P -> [~ P])
Examples:
(resolve [P] [[~ P]]) ==> [] (the empty clause)
(resolve [P Q] [[~ P] Q]) ==> [Q]
(resolve [P Q R] [R]) ==> none! (no resolvent)
Mark
hmm.. qi seems interesting (so is the entire IFPE idea) but my basic
idea was to see what people think about the *lisp* code and in the
process learn how to write better *lisp* code.
regards
Vishnu Vyas
vishnuvyas wrote:
> hmm.. qi seems interesting (so is the entire IFPE idea) but my basic
> idea was to see what people think about the *lisp* code and in the
> process learn how to write better *lisp* code.
>
> regards
> Vishnu Vyas
Ok, fair enough. You can actually generate the
Lisp code from the program I gave.
1. Put it in a file called resolve.txt.
2. Load Qi and tell Qi to dump the Lisp.
Qi 2005, Copyright (C) 2001-2005 Mark Tarver
version 6.3
(0-) (dump "resolve.txt")
resolve
resolve-help
complement
Real time: 0.0100144 sec.
Run time: 0.0100144 sec.
Space: 184768 Bytes
loaded
(1-)
You get an output file resolve.txt.lsp
Its machine-generated Lisp which is a bit on the
CONSy-CARry-CDRry line; but it's legal and works.
Replace (qi::wrapper (element? (complement (CAR V11)) V13)
by (MEMBER (complement (CAR V11)) V13 :TEST 'EQUAL)
and qi::f_error by your chosen error message to port.
(DEFUN resolve (V1 V2) (resolve-help V1 V1 V2))
(DEFUN resolve-help (V11 V12 V13)
(COND ((NULL V11) 'none!)
((AND (CONSP V11) (qi::wrapper (element? (complement (CAR V11))
V13)))
(LET* ((V14 (CAR V11)))
(THE LIST
(union (THE LIST (remove V14 V12))
(THE LIST (remove (complement V14) V13))))))
((CONSP V11) (resolve-help (CDR V11) V12 V13))
(T (qi::f_error 'resolve-help))))
(DEFUN complement (V18)
(COND
((AND (CONSP V18) (EQ '~ (CAR V18)) (CONSP (CDR V18)) (NULL (CDR (CDR
V18))))
(CAR (CDR V18)))
(T (CONS '~ (CONS V18 NIL)))))
Mark
From: Marco Antoniotti
Subject: Re: Request for comments on this code and ways to improve it.
Date:
Message-ID: <Wnv5f.33$pa3.17629@typhoon.nyu.edu>
Mark Tarver wrote:
> I don't use Lisp much for this sort
> of problem now because pattern
> matching makes this simpler.
Shameless plug.
http://common-lisp.net/project/cl-unification
Cheers
--
Marco
Note that MULTIPLE-VALUE-BIND allows you to define the local variables
you want, so you don't really need to do (LET ((list1 ...) ) ... (SETF
list1 ...)) Instead, you could do:
(mulitpile-value-bind (list1 nlist1)
(separate-parts list) ...
etc.
As a general rule, when you find yourself using SETF or SETQ on
variables, there's probably a simpler way to set the values.
Will
"vishnuvyas" <··········@gmail.com> writes:
> Hello,
>
> I am pretty much a newbie to lisp and I wrote a code for the resolution
> of CNF's (conjunctive normal forms). I would like to know how
> good/bad/ugly the code actually is and in what ways can it be made
> better.
>
> code :
> ;;; Solves CNF forms
> ;;; the macro resolve-list takes as input a list of the form
> ;;; ((expr1) (expr2) (expr3) ... )
> ;;; where each expr is of the the form ( var1 or var2 or ... not varN
> ...or varK )
>
> (defpackage :cnf
> (:use :common-lisp)
> (:export 'resolve-list))
>
> (in-package :cnf)
>
> ;;; function seperate-parts.
> ;;; Seperate parts splits the expression into variables that are
> negated and those that
> ;;; are not negated.
>
> (defun seperate-parts (expr1)
> "Seperates the negated variables and the non-negated variables"
>
> (let ((list-v ())
> (list-vneg ())
> (next ()))
>
> (dolist (iter expr1)
> (cond
> ((eq 'or iter) ())
> ((eq 'not iter) (setf next t))
> (t (if next
> (progn
> (push iter list-vneg)
> (setf next ()))
> (push iter list-v)))))
> (values list-v list-vneg)))
Opinions on this vary a little, but I personally find the visual
structure to be sufficient for seperating the parts of functions like
the above: I'd lose the blank lines, they detract from readability
once you're used to reading Lisp.
The above function looks okay, although some of the variable names
(iter? list-...?) are a little weird. For what it's worth, I'd have
written that as either:
(defun seperate-parts (expr)
(let (v vneg)
(labels ((next () (if (null expr)
(return-from seperate-parts (values v vneg))
(pop expr))))
(tagbody
loop
(let ((item (next)))
(case item
(or nil)
(not (go not))
(t (push item v))))
(go loop)
not
(push (next) vneg)
(go loop)))))
or:
(defun seperate-parts (expr)
(loop for item = (pop expr)
if (eql item 'or) do (values)
else if (eql item 'not)
collect (pop expr) into vnot
else collect item into v
while expr
finally (return (values v vnot))))
> (nreverse red-list1)
This line does not do what you think it does! In the implementation you're
using, I'm guessing it happens to reverse the list in-place; what the function
does is reverse the list you give it, possibly destoying the original in the
process. You should *never* use it without using the resulting value. The
idiom is (setf foo (nreverse foo)). Once NREVERSE has gone over the list that
FOO was bound to, the list is garbage.
That said, I'd have written this function like this:
(defun resolve-pair (expr1 expr2)
(labels ((xform (list pre post)
(loop for (item . morep) on list
if morep nconc (nconc (when pre (list pre))
(list item)
(when post (list post)))
else collect item)))
(multiple-value-bind (list1 nlist1) (seperate-parts expr1)
(multiple-value-bind (list2 nlist2) (seperate-parts expr2)
(let* ((remove (union (intersection list1 nlist2)
(intersection list2 nlist1)))
(allp (set-difference (union list1 list2) remove))
(alln (set-difference (union nlist1 nlist2) remove)))
(nconc (xform allp nil 'or)
(list 'or)
(xform alln 'not 'or)))))))
Using multiple-value-bind and local helper functions is very idiomatic Common
Lisp. And in general, there's no reason to build your results backwards --
there's almost always a way to build them up naturally. If you really prefer
DOLIST to LOOP (which is certainly natural when first coming to Lisp), google
comp.lang.lisp for macros called things like WITH-COLLECTORS.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
>Thomas F. Burdick worte
>(defun seperate-parts (expr)
> (loop for item = (pop expr)
> if (eql item 'or) do (values)
> else if (eql item 'not)
> collect (pop expr) into vnot
> else collect item into v
> while expr
> finally (return (values v vnot))))
I like this definition of seperate-parts more than the previous one
using tagbody. Seems clearer too..
> (defun resolve-pair (expr1 expr2)
> (labels ((xform (list pre post)
> (loop for (item . morep) on list
> if morep nconc (nconc (when pre (list pre))
> (list item)
> (when post (list post)))
> else collect item)))
> (multiple-value-bind (list1 nlist1) (seperate-parts expr1)
> (multiple-value-bind (list2 nlist2) (seperate-parts expr2)
> (let* ((remove (union (intersection list1 nlist2)
> (intersection list2 nlist1)))
> (allp (set-difference (union list1 list2) remove))
> (alln (set-difference (union nlist1 nlist2) remove)))
> (nconc (xform allp nil 'or)
> (list 'or)
> (xform alln 'not 'or)))))))
>
Hmm.. doesn't always seem to generate the correct answer.. (missing
not's) I guess it has something to do with the way xform works.
> (loop for (item . morep) on list
> if morep nconc (nconc (when pre (list pre))
> (list item)
> (when post (list post)))
> else collect item)))
The last element will make morep null and hence the pre will never
come..
i guess it can be fixed by changing else., this works so far for me
else nconc (nconc (when pre (list pre))
(list item))
regards
Vishnu Vyas
"vishnuvyas" <··········@gmail.com> writes:
> >Thomas F. Burdick worte
> >(defun seperate-parts (expr)
> > (loop for item = (pop expr)
> > if (eql item 'or) do (values)
> > else if (eql item 'not)
> > collect (pop expr) into vnot
> > else collect item into v
> > while expr
> > finally (return (values v vnot))))
>
> I like this definition of seperate-parts more than the previous one
> using tagbody. Seems clearer too..
I agree, but wanted to give the other for a LOOP-free example
> The last element will make morep null and hence the pre will never
> come..
> i guess it can be fixed by changing else., this works so far for me
Whoops, you're right -- I admit to only testing that it worked on one
input :-)
Peter Seibel's Practical Common Lisp has a very good chapter on LOOP,
in case you want to learn more about it: http://www.gigamonkeys.com/book/
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
> Thomas F. Burdick wrote
>Whoops, you're right -- I admit to only testing that it worked on one
>input :-)
This is the final form which seems to work for me..
(flet
; xform is a formatting function which is used to take a list
; of symbols and convert them into a list of symbols padded
; appropriately with the pre and post symbols.
((xform (list pre post)
(let ((x (car (last list))))
(loop for item in list
if (eql item x) nconc (nconc (when pre (list pre))
(list item))
else nconc (nconc (when pre (list pre))
(list item)
(list post))))))
But I am still looking for more points on Lisp style, making code more
efficient, etc..
Regards
Vishnu
From: Thomas A. Russ
Subject: Re: Request for comments on this code and ways to improve it.
Date:
Message-ID: <ymizmp325r4.fsf@sevak.isi.edu>
"vishnuvyas" <··········@gmail.com> writes:
>
> (flet
> ; xform is a formatting function which is used to take a list
> ; of symbols and convert them into a list of symbols padded
> ; appropriately with the pre and post symbols.
> ((xform (list pre post)
> (let ((x (car (last list))))
> (loop for item in list
> if (eql item x) nconc (nconc (when pre (list pre))
> (list item))
> else nconc (nconc (when pre (list pre))
> (list item)
> (list post))))))
>
> But I am still looking for more points on Lisp style, making code more
> efficient, etc..
OK, I'm not always a fan of NCONC, even though LOOP usually arranges to
do it in a way that is not particularly inefficient. But I think
multiple collect clauses would be a lot simpler.
Then there is the common problem of how to do something different for
the first or last item of a list. I prefer to handle the special case
at the front of the list, so that you don't have to traverse the list to
find the last element, as in calling LAST. Also, this particular code
assumes that there are no repeated objects in the list, so if you tried
in on a list of '(a b c d b f b) you would get a nasty surprise
My take:
(xform (list pre post)
(loop for first-p = t then nil
for item in list
unless first collect post
when pre collect pre
collect item))
Even though the structure is transformed, this still collects things in
the following order:
[pre] item post [pre] item post [pre] item
| | |
where the "|" notes the iteration boundaries, since collection of "post"
is not done the first time through the loop.
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> "vishnuvyas" <··········@gmail.com> writes:
> >
> > (flet
> > ; xform is a formatting function which is used to take a list
> > ; of symbols and convert them into a list of symbols padded
> > ; appropriately with the pre and post symbols.
> > ((xform (list pre post)
> > (let ((x (car (last list))))
> > (loop for item in list
> > if (eql item x) nconc (nconc (when pre (list pre))
> > (list item))
> > else nconc (nconc (when pre (list pre))
> > (list item)
> > (list post))))))
> >
> > But I am still looking for more points on Lisp style, making code more
> > efficient, etc..
You traverse the list twice here, once just to find the last item. A
computationally simpler (and in my opinion easier to follow) way to
accomplish the same thing is the (item . morep) destructuring I used.
It also works if you have repeated elements in the list, unlike the
code above.
> OK, I'm not always a fan of NCONC, even though LOOP usually arranges to
> do it in a way that is not particularly inefficient. But I think
> multiple collect clauses would be a lot simpler.
Why do you think that an implementation that didn't keep a tail
pointer for nconc would do so for collect? Much like mapcan, this is
a perfectly valid way of collecting varying numbers of items.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
From: Thomas A. Russ
Subject: Re: Request for comments on this code and ways to improve it.
Date:
Message-ID: <ymivezq243r.fsf@sevak.isi.edu>
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> > OK, I'm not always a fan of NCONC, even though LOOP usually arranges to
> > do it in a way that is not particularly inefficient. But I think
> > multiple collect clauses would be a lot simpler.
>
> Why do you think that an implementation that didn't keep a tail
> pointer for nconc would do so for collect? Much like mapcan, this is
> a perfectly valid way of collecting varying numbers of items.
True.
But the original code also had calls to the NCONC function, which can't
keep the same tail pointer....
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ wrote:
> But the original code also had calls to the NCONC function, which can't
> keep the same tail pointer....
I guess, keeping tail pointer is not really required there because
nconc simply builds a (max of) 3 element list with 3 simpler lists..
Cheers
Vishnu
···@sevak.isi.edu (Thomas A. Russ) writes:
> ···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > > OK, I'm not always a fan of NCONC, even though LOOP usually arranges to
> > > do it in a way that is not particularly inefficient. But I think
> > > multiple collect clauses would be a lot simpler.
> >
> > Why do you think that an implementation that didn't keep a tail
> > pointer for nconc would do so for collect? Much like mapcan, this is
> > a perfectly valid way of collecting varying numbers of items.
>
> True.
>
> But the original code also had calls to the NCONC function, which can't
> keep the same tail pointer....
As vishnuvyas mentioned, the lists the NCONC function is constructing
are at most 3 elements long, so even if that were true, it wouldn't
matter. But in a single call to NCONC, of *course* it can keep a tail
pointer. NCONCing n lists should be linear to the length of the
result, regardless of the size of n. Any implementation of NCONC that
doesn't have that property is unforgivably bad.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
From: Thomas A. Russ
Subject: Re: Request for comments on this code and ways to improve it.
Date:
Message-ID: <ymioe5i1quq.fsf@sevak.isi.edu>
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> As vishnuvyas mentioned, the lists the NCONC function is constructing
> are at most 3 elements long, so even if that were true, it wouldn't
> matter. But in a single call to NCONC, of *course* it can keep a tail
> pointer. NCONCing n lists should be linear to the length of the
> result, regardless of the size of n. Any implementation of NCONC that
> doesn't have that property is unforgivably bad.
Yes, but calling nconc inside loops still has the potential to give you
N^2 running times if used to accumulate values inappropriately:
(defun flatten (list-of-lists)
(let ((result ()))
(dolist (one-list list-of-lists)
(setf result (nconc result one-list)))
result))
This is just an example of bad algorithm design, and using NCONC rather
than APPEND will only save some consing. It still gives up the
algorithmic performance.
I was trying to make a point about the importance of looking at the
whole algorithm design rather than trying to micro-optimize a small
piece while failing to notice larger, more important problems. (NB
this latter criticism is not directed at you).
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ wrote:
> I was trying to make a point about the importance of looking at the
> whole algorithm design rather than trying to micro-optimize a small
> piece while failing to notice larger, more important problems. (NB
> this latter criticism is not directed at you).
Point taken. I did that mistake of doing an O(n^2) algorithm where an
O(n) algorithm could have sufficed (with my previous version of xform),
so probably I won't do it again.
Cheers,
Vishnu
···@sevak.isi.edu (Thomas A. Russ) writes:
> ···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
>
> > As vishnuvyas mentioned, the lists the NCONC function is constructing
> > are at most 3 elements long, so even if that were true, it wouldn't
> > matter. But in a single call to NCONC, of *course* it can keep a tail
> > pointer. NCONCing n lists should be linear to the length of the
> > result, regardless of the size of n. Any implementation of NCONC that
> > doesn't have that property is unforgivably bad.
>
> Yes, but calling nconc inside loops still has the potential to give you
> N^2 running times if used to accumulate values inappropriately:
[snip]
Yes, of course.
> This is just an example of bad algorithm design, and using NCONC rather
> than APPEND will only save some consing. It still gives up the
> algorithmic performance.
>
> I was trying to make a point about the importance of looking at the
> whole algorithm design rather than trying to micro-optimize a small
> piece while failing to notice larger, more important problems. (NB
> this latter criticism is not directed at you).
Then you might want to read the code you respond to more carefully:
the nconcs in the code where you decided to try to make this point do
not fall into the class you were trying to warn against. As a matter
of fact, the code was written *in response to* algorithmically
inefficient code, as an example of how to write such a thing linearly.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
From: Thomas A. Russ
Subject: Re: Request for comments on this code and ways to improve it.
Date:
Message-ID: <ymimzky22de.fsf@sevak.isi.edu>
···@conquest.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Then you might want to read the code you respond to more carefully:
> the nconcs in the code where you decided to try to make this point do
> not fall into the class you were trying to warn against. As a matter
> of fact, the code was written *in response to* algorithmically
> inefficient code, as an example of how to write such a thing linearly.
Actually I did look at the code carefully.
The original code had NCONC appearing both as the loop collection
keyword, and as function calls to produce the lists that the loop
collection keyword was collecting:
> > (loop for item in list
> > if (eql item x) nconc (nconc (when pre (list pre))
> > (list item))
> > else nconc (nconc (when pre (list pre))
> > (list item)
> > (list post))))))
So the inner NCONC runs down the list once, and then the outer one has
to also traverse the list once again. Now assuming that Loop is smart
(it usually is), that still doubles the amount of list traversals
compared to a more clever collection strategy that only runs down each
list element once.
--
Thomas A. Russ, USC/Information Sciences Institute