Hi!
I've just finished my first LISP program as part of an assigment in my
AI class, and I would be very happy to hear some comments on the
programming style I used -- i.e. if it's LISPy or not, stuff that I
could improve, etc. The program itself is pretty basic, but coming from
a Java-background I just want to make sure I don't start going down that
"Programming in Lisp, thinking in Java"-way. The program does what it's
supposed to do, btw., so I'm not asking for help on my assignment :)
Also, if somebody knows a good resource for that topic I'd love to hear
about it (I've been using "Practical Common Lisp" as my major resource).
Thanks in advance for any pointers and hints!
Regards, Florian
;;;; *** Predicate logic routines ***
;;;; The two main routines are get-rid-of-imp (which replaces implications
;;;; by equivalent sentences) and move-neg-inwards (which reduces the
;;;; scope of negations). See the bottom of the code for examples/tests.
(defun symb-p (symbol sentence)
"Checks if the given sentence starts with the given symbol. Returns nil
for atomic sentences."
(cond
((atom sentence) nil)
(t (equal symbol (first sentence)))))
(defun negate (sentence)
"Negates the given sentence"
`(not ,sentence))
(defun get-rid-of-imp (sentence)
"Replaces all implications (imp a b) in sentence by (or (not a) b)"
(cond
((atom sentence) sentence)
((symb-p 'imp sentence) (get-rid sentence))
(t (cons (first sentence) (mapcar #'get-rid-of-imp (rest sentence))))))
(defun get-rid (sentence)
"Replaces a top-level implication"
`(or ,(neg-and-get-rid (second sentence)) ,(get-rid-of-imp (third
sentence))))
(defun neg-and-get-rid (subsentence)
"Negates the given subsentence after applying get-rid-of-imp on it"
(negate (get-rid-of-imp subsentence)))
(defun move-neg-inwards (sentence)
"Reduces the scope of negations in the given sentence as much as
possible"
(cond
((atom sentence) sentence)
((symb-p 'not sentence) (move-neg sentence))
(t (cons (first sentence) (mapcar #'move-neg-inwards (rest
sentence))))))
;;; Reducing the scope of negations in move-neg is done using
;;; the following rules:
;;; (not (not a)) ---> a
;;; (not (and a b) ---> (or (not a) (not b))
;;; (not (or a b) ---> (and (not a) (not b))
;;; (not (forall x a)) ---> (exists x (not a))
;;; (not (exists x a)) ---> (forall x (not a))
(defun move-neg (sentence)
"Moves a top-level negation inwards"
(let ((s2 (second sentence)))
(cond
((atom s2) sentence)
(t (case (first s2)
(not (move-neg-inwards (second s2)))
(and `(or ,(neg-and-move (second s2)) ,(neg-and-move (third s2))))
(or `(and ,(neg-and-move (second s2)) ,(neg-and-move (third s2))))
(forall `(exists ,(second s2) ,(neg-and-move (third s2))))
(exists `(forall ,(second s2) ,(neg-and-move (third s2)))))))))
(defun neg-and-move (subsentence)
"Negates the given sentence after applying move-neg-inwards on it"
(negate (move-neg-inwards subsentence)))
;;; ** Test runs **
;; Test inputs
(setf s1 '(forall x (forall y (imp (and (p x) (q y)) (r x y)))))
(setf s2 '(not (not (or (not (not a)) (not b)))))
;; Test runs
(setf r1 (get-rid-of-imp s1))
(setf r2 (move-neg-inwards (get-rid-of-imp s1)))
(setf r3 (move-neg-inwards s2))
;; Correct results
(setf c1 '(forall x (forall y (or (not (and (p x) (q y))) (r x y)))))
(setf c2 '(forall x (forall y (or (or (not (p x)) (not (q y))) (r x y)))))
(setf c3 '(or a (not b)))
(format t "Test 1: ~a~%" (equal r1 c1))
(format t "Test 2: ~a~%" (equal r2 c2))
(format t "Test 3: ~a~%" (equal r3 c3))
From: Kent M Pitman
Subject: Re: Request for comments on LISP-newbie style
Date:
Message-ID: <ur6cpv4qa.fsf@nhplace.com>
Florian Brucker <····@torfbold.com> writes:
> (defun symb-p (symbol sentence)
Prefer full words. They are easier to remember and not as many possible
misspellings. Every word has only one correct spelling and (too) many
abbreviations. A better name might be starts-with. Some people would use
the -p but I probably wouldn't bother in this case.
> "Checks if the given sentence starts with the given symbol. Returns nil
> for atomic sentences."
> (cond
> ((atom sentence) nil)
Unless you plan to have improper lists as sentences, I'd use NULL here.
(Are these really sentences or expressions.)
Btw, this indentation style is pretty non-standard. Unless you were
out of room horizontally, I'd say start the first clause on the same
line as the cond.
> (t (equal symbol (first sentence)))))
If the value of symbol will be a symbol, just use EQ. There is no
practical advantage of using EQUAL unless you plan to allow other
kinds of objects that require it. And EQ will often compile "inline",
saving a function call.
> (defun get-rid-of-imp (sentence) ..)
Possible better names: transform-implication or expand-implication.
Don't use names that aren't graceful to read. Try to make names say
or hint what they do.
> (defun get-rid (sentence)
Get rid of what?
> "Replaces a top-level implication"
Ah. transform-implication-toplevel, or whatever.
> (defun neg-and-get-rid (subsentence) ...)
negate-and-expand-implication
> (defun move-neg-inwards (sentence) ...)
simplify-negation-inward [I'm not a big fan of "inwards"]
or simplify-negation-recursively.
> (defun move-neg (sentence) ...)
simplify-negation-toplevel.
> (defun neg-and-move (subsentence)
> "Negates the given sentence after applying move-neg-inwards on it"
> (negate (move-neg-inwards subsentence)))
Couldn't quite figure out what this one is supposed to accomplish.
Didn't try running the code. But give it a name that talks about
its purpose.
The point of all of this is that when your read code with funny names,
you have to read those functions to know what they do. But when you
read code with GOOD names, the names will tell you what the function
is doing. There's a difference between reading something like:
(defun restate-negatively (exp)
(cond ((intersectionp exp)
(negate (intersect* (mapcar #'negate (rest exp)))))
...))
and
(defun dbl-neg (x)
(cond ((check-intrsc x)
(inv (intrsc-from-ls (mapcar #'inv (cdr x)))))
...))
The former is something you might have half a chance of understanding
without doc, but the latter is something for which you have to read the
code and even then you're not sure. Yet they have the same shape.
It will sometimes take slightly more space, but not a lot more, and
the readability should convince you right away.
Hi Kent!
Kent M Pitman wrote:
>> (defun symb-p (symbol sentence)
>
> Prefer full words. They are easier to remember and not as many possible
> misspellings. [...]
Sounds reasonable.
>> "Checks if the given sentence starts with the given symbol. Returns nil
>> for atomic sentences."
>> (cond
>> ((atom sentence) nil)
>
> Unless you plan to have improper lists as sentences, I'd use NULL here.
> (Are these really sentences or expressions.)
"sentence" refers to a sentence in predicate calculus. I'm allowed to
assume that the input are sentences, not just expressions. Can you
explain how I you would use NULL there? NULL tests whether an object is
nil, right? What I want to do is to make sure the given sentence is
list. The only other way I can imagine to check that would be using listp.
> Btw, this indentation style is pretty non-standard. [...]
OK.
>> (t (equal symbol (first sentence)))))
>
> If the value of symbol will be a symbol, just use EQ. [...]
OK.
>> [...] Try to make names say or hint what they do. [...]
Yes, I normally try to do so. In this case, some of the names were
required by the assignment.
Thanks a lot for your input!
Regards,
Florian
On Apr 28, 3:21 pm, Florian Brucker <····@torfbold.com> wrote:
Hi. Some comments, as requested.
> (defun symb-p (symbol sentence)
> "Checks if the given sentence starts with the given symbol. Returns nil
> for atomic sentences."
> (cond
> ((atom sentence) nil)
> (t (equal symbol (first sentence)))))
This function is not that useful. Note that in all places where you
have used this function, you already have an ATOM check. So half of
the job done here is unnecessary. The rest is nothing but pulling out
the first element of a list and comparing it to a symbol. That's
hardly worth making into a function.
A function has a ``distraction cost'' associated with it: the cost of
being distracted to read and internalize the function when reading and
maintaining the code. So the payoff from the function has to be
greater than the cost.
> (defun negate (sentence)
> "Negates the given sentence"
> `(not ,sentence))
Again, this function is too trivial to bother making into a function.
It's actually easier for a code maintainer to understand the
expression `(not ,x) than (negate x), because any Lisp programmer can
be expected to know backquote, but nobody knows what your NEGATE
function does without reading it.
Ironically, `(not ,sentence) is fewer characters to type than (negate
sentence).
Defining functions for everything is good if you can reasonably
anticipate a major representational change. And even then, there has
to be a lot invested in the use of those functions to make it
worthwhile.
In Computer Science, they drill it into student's heads to
functionally abstract everything, but the big reason for that is the
use of systems programming languages, in which almost nothing is
simple and requires a function.
> (defun get-rid-of-imp (sentence)
> "Replaces all implications (imp a b) in sentence by (or (not a) b)"
> (cond
> ((atom sentence) sentence)
> ((symb-p 'imp sentence) (get-rid sentence))
So here we could just write:
(cond
((atom sentence) sentence)
((eq (first sentence) 'imp) (get-rid sentence))
...)
And as Kent Pitman noted, (starts-with sentence 'imp) would be a lot
clearer than SYMB-P. Names don't mean anything to the machine, but
they make a lot of difference. STARTS-WITH is so self-explanatory that
the cost of being distracted by it is a lot smaller compared to SYMB-
P. The name SYMB-P resembles SYMBOLP, which tests whether an object is
a symbol.
> (defun get-rid (sentence)
> "Replaces a top-level implication"
> `(or ,(neg-and-get-rid (second sentence)) ,(get-rid-of-imp (third
> sentence))))
What validates that the sentence is an implication?
Ah, I see that this is just a helper to GET-RID-OF-IMP. But it also
calls
that function.
In fact, GET-RID-OF-IMP is basically a validating wrapper which
detects sentences which are implications and then calls this
function.
This is pointless, because the logic here is too small to be worth
factoring out into a helper function (not to mention that it's called
only once). You've created needless confusion by mutually recursing
among two functions, when it can just be rolled into one:
(defun get-rid-of-imp (sentence)
"Replaces all implications (imp a b) in sentence by (or (not a)
b)"
(cond
((atom sentence) sentence)
((eq (first sentence) 'imp)
`(or (not ,(get-rid-of-imp (second sentence)))
,(get-rid-of-imp (third sentence))))
(t (cons (first sentence)
(mapcar #'get-rid-of-imp (rest sentence))))))
If you do need to break some main function into helpers, you can use
naming to that effect. E.g.
(defun implications-to-ors (sentence) ...)
(defun implications-to-ors-helper (sentence) ...)
Now several things are very clear: the purpose of these functions,
their close relationship, as well as the idea that the helper is
subordinate to the main one---i.e. the one without the -HELPER suffix
is the entry point, the interface to the implication reducer.
> (defun neg-and-get-rid (subsentence)
> "Negates the given subsentence after applying get-rid-of-imp on it"
> (negate (get-rid-of-imp subsentence)))
You can just write `(not ,(get-rid-of-imp x)) instead of (neg-and-get-
rid x).
> (defun move-neg-inwards (sentence)
> "Reduces the scope of negations in the given sentence as much as
> possible"
> (cond
> ((atom sentence) sentence)
> ((symb-p 'not sentence) (move-neg sentence))
> (t (cons (first sentence) (mapcar #'move-neg-inwards (rest
> sentence))))))
There is a possible bug here. You're assuming that if the form
anything other than (NOT ...) then you can recursively process it by
applying MOVE-NEG-INWARDS on the arguments.
This is a big assumption which limits the kinds of operators you can
support in your logical sentence language. You're assuming that all
logical operators are cast in the same mould: they have a symbol in
the first position (a reasonable assumption), and logical expressions
in all of the remaining positions (a possibly bogus assumption).
In fact you already have operators which break this rule, such as
(forall x y). The X is not a logical expression, but a predicate
variable.
Consider these cases:
(get-rid-of-imp '(forall (imp a b) (not x)))
(move-neg-inwards '(forall (not y) (not x)))
Since FORALL is not equal to NOT, and not equal to IMP, what happens?
These functions blindly do a MAPCAR on the rest of the sentence. The
first argument of FORALL is treated as a sentence and some
transformations are accidentally done to it!
Arguably, these sentences are not well-formed. However, robust
software does not silently accept bad input and produce output.
All of your recursive walkers have to be sensitive to the semantics of
each of your possible operators. The recursive walkers have to
identify each operator and understand in which positions that operator
has sub-sentences that are to be recursively processed.
> ;;; Reducing the scope of negations in move-neg is done using
> ;;; the following rules:
> ;;; (not (not a)) ---> a
> ;;; (not (and a b) ---> (or (not a) (not b))
> ;;; (not (or a b) ---> (and (not a) (not b))
> ;;; (not (forall x a)) ---> (exists x (not a))
> ;;; (not (exists x a)) ---> (forall x (not a))
>
> (defun move-neg (sentence)
> "Moves a top-level negation inwards"
> (let ((s2 (second sentence)))
> (cond
> ((atom s2) sentence)
> (t (case (first s2)
> (not (move-neg-inwards (second s2)))
> (and `(or ,(neg-and-move (second s2)) ,(neg-and-move (third s2))))
> (or `(and ,(neg-and-move (second s2)) ,(neg-and-move (third s2))))
> (forall `(exists ,(second s2) ,(neg-and-move (third s2))))
> (exists `(forall ,(second s2) ,(neg-and-move (third s2)))))))))
See, here your recursive walker is sensitive to the forms being
processed. It is smart enough to avoid applying NEG-AND-MOVE to the
first argument of a FORALL or EXIST. It knows that only the second
argument is a logical expression, and that nothing is to be done to
the first argument. Unfortunately, NEG-AND-MOVE is not that smart
because it only understands NOT, and blindly treats everything else
with MAPCAR.
Another thing: what happens here if none of the cases match? You might
want to use ECASE instead of CASE. If none of the operators matches,
it means that the sentence contains syntax which your recursive walker
doesn't understand. An error should be signaled, but CASE just returns
NIL.
If you ever introduce new operators, it will be easy to find the
places where you forgot to handle them, if those places consistently
blow up with a condition rather than silently return some incorrect
transformation.
My last remark about handling syntax recursively is that this type of
code benefits from the use of a pattern matcher macro. The reasons
is that it's clumsy to manually pull apart and analyze the expression
with FIRST, SECOND, REST, etc. I can't recommend one, though. :)
Imagine you had a construct like this imaginary MATCH-SYNTAX:
(defun move-negation-in (sentence)
(match-syntax sentence
((not (not ?x)) (move-negation-in x))
((not (and ?x ?y)) `(or ,(move-negation-in `(not ,x))
,(move-negation-in `(not ,y))))
((not (forall ?x ?p)) `(exists ,x ,(move-negation-in `(not ,p))))
...))
The MATCH-SYNTAX macro would handle the matching between the input
sentence and the patterns, and automatically pull out subexpressions
into variables.
The code becomes quite a bit nicer.
This the ``real'' way of simplifying the handling of syntax, which is
another reason why SYMB-P is not all that helpful. If it's a chore to
be writing and reading things like (eq (first sentence) 'forall),
pattern matching with destructuring is the way to go.
> (defun neg-and-move (subsentence)
> "Negates the given sentence after applying move-neg-inwards on it"
> (negate (move-neg-inwards subsentence)))
Bug? It seems like here you want to apply the NOT to the subsentence
to produce a negated sentence, and /then/ apply MOVE-NEG-INWARDS to
the resulting sentence! The MOVE-NEG-INWARDS function checks for the
presence of that NOT, and then calls MOVE-NEG. Since here you are
adding a NOT onto the sentence, you can skip MOVE-NEG-INWARDS call
directly into MOVE-NEG:
(defun neg-and-move (subsentence)
(move-neg (negate subsentence)))
Now the operations are actually done in the order implied by the name
of the function. Neg, then move.
I'd still roll this all into MOVE-NEG instead of using a little
function. In the big CASE, rather than this:
(and `(or ,(neg-and-move (second s2)) ,(neg-and-move (third s2))))
how about:
(and `(or ,(move-neg `(not ,(second s2)))
,(move-neg `(not ,(third s2)))))
It's longer, but you can see what is going on. The AND is becoming an
OR with inverted inputs, and this newly applied NOT is being pushed
into them recursively.
The recursion is made plain, since MOVE-NEG function is just calling
itself, instead of calling some helper which calls another helper
which calls into MOVE-NEG.
> ;;; ** Test runs **
>
> ;; Test inputs
> (setf s1 '(forall x (forall y (imp (and (p x) (q y)) (r x y)))))
> (setf s2 '(not (not (or (not (not a)) (not b)))))
You might want to begin with simpler tests. Your code must handle the
base induction cases. For instance, GET-RID-OF-IMP has to be
demonstrated to correctly work on the induction base cases: an atom
like P, and the simplest implication (IMP P Q). If these don't work,
there is no point in trying something complex.
Hi Kaz!
Kaz Kylheku wrote:
>> (defun symb-p (symbol sentence)
>> "Checks if the given sentence starts with the given symbol. Returns nil
>> for atomic sentences."
>> (cond
>> ((atom sentence) nil)
>> (t (equal symbol (first sentence)))))
>
> This function is not that useful. Note that in all places where you
> have used this function, you already have an ATOM check. So half of
> the job done here is unnecessary. The rest is nothing but pulling out
> the first element of a list and comparing it to a symbol. That's
> hardly worth making into a function.
My heavy use of functions was most of the time a try to reduce the
complexity of each part. The syntax is all new to me and so things get
quite complicated for me quite fast. I guess when I've done some more
Lisp I won't need to take everything apart as I did right now. This
applies also to most of your other comments (nevertheless all of them
are of course appreciated!).
>> (defun move-neg-inwards (sentence)
>> "Reduces the scope of negations in the given sentence as much as
>> possible"
>> (cond
>> ((atom sentence) sentence)
>> ((symb-p 'not sentence) (move-neg sentence))
>> (t (cons (first sentence) (mapcar #'move-neg-inwards (rest
>> sentence))))))
>
> There is a possible bug here. You're assuming that if the form
> anything other than (NOT ...) then you can recursively process it by
> applying MOVE-NEG-INWARDS on the arguments.
>
> This is a big assumption which limits the kinds of operators you can
> support in your logical sentence language. You're assuming that all
> logical operators are cast in the same mould: they have a symbol in
> the first position (a reasonable assumption), and logical expressions
> in all of the remaining positions (a possibly bogus assumption).
>
> [...]
>
> Arguably, these sentences are not well-formed. However, robust
> software does not silently accept bad input and produce output.
I should have mentioned that I can assume that the input are well-formed
sentences and that I made use of that assumption (quite heavily). In a
more general setting you're of course right.
> [...]
> Another thing: what happens here if none of the cases match? You might
> want to use ECASE instead of CASE. If none of the operators matches,
> it means that the sentence contains syntax which your recursive walker
> doesn't understand. An error should be signaled, but CASE just returns
> NIL.
Didn't know about ECASE, thanks for the pointer.
> [...] My last remark about handling syntax recursively is that this type
> of code benefits from the use of a pattern matcher macro.
Of course. I thought about writing one my own, but decided it was
overkill for the assignment and too complicated for a first Lisp program.
>> (defun neg-and-move (subsentence)
>> "Negates the given sentence after applying move-neg-inwards on it"
>> (negate (move-neg-inwards subsentence)))
>
> Bug? It seems like here you want to apply the NOT to the subsentence
> to produce a negated sentence, and /then/ apply MOVE-NEG-INWARDS to
> the resulting sentence! [...]
You're right. An example where my code fails is (NOT (AND (NOT B) C))
which produces (OR (NOT (NOT B)) (NOT C)) due to the bug you noticed.
> You might want to begin with simpler tests. [...]
These tests weren't meant to be full-blown unit-tests -- basically they
are required by the assignment. But as the bug you spotted shows some
simpler tests would've been a good idea (I did *some* simple tests, but
obviously not enough).
Thanks for all the comments!
Regards,
Florian
Congrats to your first lisp program!
Kent already pointed out a few good points. I have just one more thing
(which really is a matter of taste I guess): You use backquote syntax
heavily, where I'd just go with (list ...) and normal quotes, which I
find clearer. I tend use special syntax only when there is a clear
advantage (as for example in macros where it heavily improves
readability), but again it is just a matter of taste.
Two examples:
> (defun negate (sentence)
> "Negates the given sentence"
> `(not ,sentence))
I would have written (list 'not sentence)
> (defun get-rid (sentence)
> "Replaces a top-level implication"
> `(or ,(neg-and-get-rid (second sentence)) ,(get-rid-of-imp (third
> sentence))))
(list (neg-and-get-rid (second sentence)) (get-rid-of-imp (third
sentence))))
For the testing part, I'd write a macro like
(with-assert-result ((forall x (forall y (imp (and (p x) (q y)) (r x
y)))) :message "Test 1")
(get-rid-of-imp s1))
The definition would be
(defmacro with-assert-result ((asserted-result &key (test 'equal)
(message "Test") &body body)
"Executes body and compares the result with asserted-result using test"
`( ...))
Implement it if you like :-)
Have fun with you future lisp adventures.
Peter
Hi Peter!
Peter Hildebrandt wrote:
> Congrats to your first lisp program!
Thanks! Feels good to get to know a new language, especially one that's
not so similar to the ones I used before.
> Kent already pointed out a few good points. I have just one more thing
> (which really is a matter of taste I guess): You use backquote syntax
> heavily, where I'd just go with (list ...) and normal quotes, which I
> find clearer.
I'm still not used to all the parantheses and thus have a hard time to
actually tell whether something is readable or not. But as you said,
it's a matter of taste, and I found style-guides suggesting either way.
> For the testing part, I'd write a macro like [...]
That sounds like a nice idea. Will find its way into my program.
> Have fun with you future lisp adventures.
Thanks, and thanks for your tips!
Regards,
Florian
Florian Brucker <····@torfbold.com> writes:
> Hi!
>
> I've just finished my first LISP program as part of an assigment in my
> AI class, and I would be very happy to hear some comments on the
> programming style I used -- i.e. if it's LISPy or not, stuff that I
> could improve, etc. The program itself is pretty basic, but coming
> from a Java-background I just want to make sure I don't start going
> down that "Programming in Lisp, thinking in Java"-way. The program
> does what it's supposed to do, btw., so I'm not asking for help on my
> assignment :)
>
> Also, if somebody knows a good resource for that topic I'd love to
> hear about it (I've been using "Practical Common Lisp" as my major
> resource).
I think this is very nice work for a first Lisp program. If you're
interested in "thinking in Lisp", you might pick up a copy of Norvig's
Paradigms of AI Programming. In a couple of chapters he looks at
simplification of mathematical expressions, and it should map easily
onto problems like the one you've just solved. For example:
> ;;; Reducing the scope of negations in move-neg is done using
> ;;; the following rules:
> ;;; (not (not a)) ---> a
> ;;; (not (and a b) ---> (or (not a) (not b))
> ;;; (not (or a b) ---> (and (not a) (not b))
> ;;; (not (forall x a)) ---> (exists x (not a))
> ;;; (not (exists x a)) ---> (forall x (not a))
Imagine you have a pattern matcher (or unifier) that will take a
pattern, with variables, and do the right thing given some input. For
example,
CL-USER> (pat-match '(not (not ?a)) '(not (not (and (p x) (q y)))))
((?A . (AND (P X) (Q Y))))
That is, the variable ?A is associated with the appropriate value in
an alist of bindings. You can then imagine making your commented
rules above explicit,
(((not (not ?a)) -> ?a)
((not (and ?a ?b)) -> (or (not ?a) (not ?b)))
. . .)
and doing the variable substitutions with sublis.
Hi Rob!
> I think this is very nice work for a first Lisp program. If you're
> interested in "thinking in Lisp", you might pick up a copy of Norvig's
> Paradigms of AI Programming. [...]
Uh, thanks. Glad to hear I'm not totally off the road :) I will take a
look at Norvig's text, too.
> Imagine you have a pattern matcher (or unifier) that will take a
> pattern, with variables, and do the right thing given some input. [...]
I thought about something like that, but then decided that it was
overkill for the assignment and a bit to advanced for a first Lisp
program. But I like the idea, and now that I got my first Lisp program
written it's time for something harder, anyway :)
Thanks for your input!
Regards,
Florian