Re: Loop problem
From: Alan Crowe (alan_at_cawtech.freeserve.co.uk)
Date: 07/22/04
- Next message: Oli Schwarz: "type of hash-keys"
- Previous message: RobertMaas_at_YahooGroups.Com: "SOA = Service Oriented Architecture (was: Macro lambda list)"
- In reply to: ma005: "Re: Loop problem"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 22 Jul 2004 18:05:37 +0100
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
- Next message: Oli Schwarz: "type of hash-keys"
- Previous message: RobertMaas_at_YahooGroups.Com: "SOA = Service Oriented Architecture (was: Macro lambda list)"
- In reply to: ma005: "Re: Loop problem"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
