hello again,
after that long time ..
first of all i have to say, that the solution of kenny tilton worked
fine.
i didn't try then joe marshall's (sorry).
but my real problem now is, that my whole conception doesn't work. so
i would like to ask you if you have any links (or lisp-programs) how
to do sat-tests on logic formulas in lisp?
thx,
Martin Adam
···········@gmx.de asked:
but my real problem now is, that my whole conception
doesn't work. so i would like to ask you if you have
any links (or lisp-programs) how to do sat-tests on
logic formulas in lisp?
I missed the thread first time through. Are you trying to do
something like this?
* (defvar logic '(and a b (or c d)) )
LOGIC
* (defmacro dyn-do-log-bits (var-list &body code)
(if var-list
`(dolist (,(car var-list) '(nil t))
(declare (special ,(car var-list)))
(dyn-do-log-bits ,(cdr var-list) ,@code))
(cons 'progn code)))
DYN-DO-LOG-BITS
* (dyn-do-log-bits(a b c d)
(format t "~{~:[0~;1~]~} ~A~%" (list a b c d)
(handler-bind ((warning #'muffle-warning))
(eval logic))))
0000 NIL
0001 NIL
0010 NIL
0011 NIL
0100 NIL
0101 NIL
0110 NIL
0111 NIL
1000 NIL
1001 NIL
1010 NIL
1011 NIL
1100 NIL
1101 T
1110 T
1111 T
NIL
Alan Crowe
Edinburgh
Scotland
Alan Crowe wrote:
> I missed the thread first time through. Are you trying to do
> something like this?
>
> * (defvar logic '(and a b (or c d)) )
>
> LOGIC
> * (defmacro dyn-do-log-bits (var-list &body code)
> (if var-list
> `(dolist (,(car var-list) '(nil t))
> (declare (special ,(car var-list)))
> (dyn-do-log-bits ,(cdr var-list) ,@code))
> (cons 'progn code)))
>
> DYN-DO-LOG-BITS
> * (dyn-do-log-bits(a b c d)
> (format t "~{~:[0~;1~]~} ~A~%" (list a b c d)
> (handler-bind ((warning #'muffle-warning))
> (eval logic))))
> 0000 NIL
> 0001 NIL
> 0010 NIL
> 0011 NIL
> 0100 NIL
> 0101 NIL
> 0110 NIL
> 0111 NIL
> 1000 NIL
> 1001 NIL
> 1010 NIL
> 1011 NIL
> 1100 NIL
> 1101 T
> 1110 T
> 1111 T
> NIL
i'm not sure, if i wanted that ;). but it looks fine. could you
explain, what the statements of your macro do (i'm a lisp-beginner)?
the result looks to me like a truth-table, but i would rather need a
faster algorithm.
but thanx alot.
Martin
I made some guesses.
1) You want to use the built in AND and OR on a formula you
type in interactively. For example:
* (eval (read))
(and (or nil t) t)
T
or adding a bit of polish
* (eval (progn
(format t "~&Enter a boolean formula: ")
(finish-output)
(read)))
Enter a boolean formula: (and t (not nil))
T
That is attractive because you use the AND and OR in the
language already, instead of writing your own interpreter
to interpret the formula.
2) You don't actually want to type in T and NIL
yourself. You are more interested in printing out a truth
table. Something like:
* (let ((both '(nil t)))
(dolist (a both)
(dolist (b both)
(dolist (c both)
(format t "~&~4A~4A~4A -> ~A" a b c (and a (or b c)))))))
NIL NIL NIL -> NIL
NIL NIL T -> NIL
NIL T NIL -> NIL
NIL T T -> NIL
T NIL NIL -> NIL
T NIL T -> T
T T NIL -> T
T T T -> T
That leaves two problems. 1)EVAL doesn't see lexical
variables. 2)coding gets tedious
(let ((form '(and a b))
(a t)
(b t))
(eval form))
only gets half way. FORM is accessed to obtain (and a b)
which is passed to EVAL.
EVAL then tries to evaluate (and a b) but cannot see A and
B.
One solution is
(defvar a)
(defvar b)
(let ((form '(and a b))
(a t)
(b t))
(eval form))
T
but the defvars haven't just made the bindings dynamic, they
have made the symbols dynamic. Every binding for A and B
until you quit the image is going to be dynamic, even inner
ones that you think are lexical.
So, quitting the image and restarting (to undo the effect of
the defvar's),
* (let ((form '(and a b))
(a t)
(b t))
(declare (special a b))
(eval form))
Warning: These variables are undefined:
A B
=> T
Now we've got a plan - tabulate the function we type in at
run time with a nest of dolists complete with special
declarations to pass the variables on to eval.
(let ((form (read)))
(dolist (a '(nil t))
(declare (special a))
(dolist (b '(nil t))
(declare (special b))
etc etc this gets real old, real quick.
(format ... (eval form))
Guess number three - you want plenty of variables, so you
will need a macro to type in the nest of dolists for you.
Well, in one rather peculiar way, macros are easier to write
than functions. Functions have to go all the way and finish
the job they start. Macroexpansions are resubmitted to the
macroexpander for further expanion. That is crucial. When you
write a macro that expands to something built-in to CL, that built-in
may itself be implemented as a macro. So if macros weren't
resubmitted everything would break horribly.
The surprising result of this is that macros don't have to
go all the way. They merely have to make progress.
A note on the name: DO-BITS is an OK name, but it suggests
to me 0 and 1, so I went for DO-LOG(ical)-BITS to suggest
nil and t. Also half the point of the macro is to make the
loop variables dynamic, so I put DYN at the front.
We want (dyn-do-log-bits (a b c .... x y z) code) to expand
to a nest of 26 DO-LISTs. One way is to write a macro that
actually builds that nest. I'm happy merely to make progress
(dyn-do-log-bits (a b c ... x y z) code) expands to
(dolist (a '(nil t))
(declare (special a))
(dyn-do-log-bits (b c d ... x y z) code))
The macroexpander will say "Oh I'm not finished yet." and
expand (dyn-do-log-bits ...) again
(dolist (a '(nil t))
(declare (special a))
(dolist (b '(nil t))
(declare (special a))
(dyn-do-log-bits (c d e ... x y z) code))
The macroexpander will say "Oh I'm not finished yet." and
expand (dyn-do-log-bits ...) again (and not get bored!)
All we need to be careful of is that
(dyn-do-log-bits () code)
expands to (progn code) or the macroexpander will never stop.
Take a look at
* (pprint (macroexpand-1 '(dyn-do-log-bits (a b c) code)))
(DOLIST (A '(NIL T)) (DECLARE (SPECIAL A)) (DYN-DO-LOG-BITS (B C) CODE))
which show the first step of macroexpansion.
Then look at
* (pprint (macroexpand '(dyn-do-log-bits (a b c) code)))
which shows what I said about built-ins being macros
finally, CMUCL offers
(pprint (walker:macroexpand-all '(dyn-do-log-bits (a b c) code)))
which produces lots of output, which you might want to leave
for later.
Today's guess is that you actually wanted a backtracking
search. It would look at (and (or a b)(not a))
First it would say,
"I'd better make the OR true, I'll set A=1"
next it would say
"I need the NOT to be true too"
"I need A=0"
"Merde! back to look at that OR again"
"B=1"
"A=0"
"Yeehaa!"
I've had a look at coding this,
http://alan.crowe.name/lisp/sat.txt but only got as far as a
greedy search for a solution, which is pretty useless
really. This problem is real computer science. It is hard,
much harder than playing about writing fill-the-template
macros. Good luck.
Alan Crowe
Edinburgh
Scotland