Thomas Baruchel invited comments on his code at
http://baruchel.thomas.free.fr/code/ogf.lsp
1)You are creating a name-space by adopting a naming
convention and typing many characters on your keyboard. The
code distinguishes the functions add, diff, and degree that
work on polynomials from functions that work on different
kinds of things that also have a claim to those names. It
makes that distinction by using long names.
polynomial-add, polynomial-diff, polynomial-degree.
Common Lisp offers two alternative tools.
First is the package system.
(defpackage "POLYNOMIAL"
(:use "CL"))
(in-package "POLYNOMIAL")
Then you can use much shorter names: add, diff, degree.
Export them from your package.
Some other code will only use `add' to add polynomials. It can
use the POLYNOMIAL package, and refer to the function as
`add'.
Other code will use `add' to add ploynomials and to add other
things. It can use package qualifiers: polynomial:add, ideal:add,..
Second is the object system
You could define a polynomial class that wraps your lists of
coefficients and make add a generic function. Then, instead
of
(defun add (p q) ...)
the code is
(defmethod add ((p polynomial)(q polynomial)) ...)
which still lets you use add for other kinds of things by
defining
(defmethod add ((i ideal)(j ideal)) ...)
2)The choice of data structure that represents polynomials
is implicit in you code. It needs to be explicit in a
comment block.
The issue is partly one of documentation. You are throwing
away information as you code. You have decided how you want
to represent polynomials, you have the idea in your head, but
rather than write it down immediately, you retain it in your
head and let it guide your coding. When you come back to it,
or when reviewers read it, we have to back calculate the
representation from the code. This is much harder that
writing down the decision at the time you take it.
The more important issue is of upfront design. What are you
going to do about the zero polynomial? The representation
that flows naturally from recursive structures is the empty
list. You have chosen '((0 0)).
Consequently much of your code is structured as a wrapper,
such as polynomial-make, on a recursive function, such as
polynomial-make0, with the wrapper converting the nil to
((0 0)). You end up with
(let ((p (polynomial-make0 l 0)))
(if (null p) *polynomial-null* p)))
(let ((d (polynomial-diff0 p)))
(if (null d) *polynomial-null* d)))
Could you make all that stuff go away by using nil instead
of ((0 0))? Failing to write down the reason is crippling,
because when you come back to it later you will naturally
assume that there is a reason that you have forgotten and
end up stuck code whose rational you can no longer
reconstruct.
Either write
;;; I need to use ((0 0)) for the zero poly, not nil
;;; To see why consider the case of ...
Or write
;;; Do I use ((0 0)) or nil for the zero poly? I'm just
;;; guessing ((0 0)) today, and will come back to this issue
;;; once I have some working code to refactor.
If you go for ((0 0)) then you need to normalise the raw
representations that drop out of your recursive functions.
You want a function for this so that you can replace
(let ((d (polynomial-diff0 p)))
(if (null d) *polynomial-null* d)))
with
(normalise (polynomial-diff0 p))
3)You've taken a perfectly competent high level language and
reduced it to assembler :-)
Look at
(t (let ((p0 (cadar p)) (q0 (cadar q)))
(cond
((< p0 q0) (cons (car p) (polynomial-add0 (cdr p) q)))
car is C.A.R
C ontents of the
A ddress part of the
R egister
cdr is C.D.R
C ontents of the
D ecrement part of the
R egister
The charm is of car and cdr is as reminders that first and
rest or head and tail do not cut it. The names should refer
to the semantics of the application, not the pointer
manipulations of the computer.
(cadar p) is take the address part, that is the first term
then the decrement part (no larger meaning)
then the address part, that is order of the term.
So we want to define
(defun lowest-order-term (poly)
(car poly))
(defun exponent (term)
(cadr term))
Then write
(t (let ((first-exponent-p (exponent (lowest-order-term p)))
(first-exponent-q (exponent (lowest-order-term q))))
(cond
((< first-exponent-p first-exponent-q)
(cons (lowest-order-term p)
(add (rest p) q))
...
Look at
(defun polynomial-add (p q)
(cond
((= 0 (caar p)) q)
((= 0 (caar q)) p)
(t (let ((r (polynomial-add0 p q)))
(if (null r) *polynomial-null* r)))))
This should be
(defun polynomial-add (p q)
(cond
((zero-poly-p p) q)
((zero-poly-p q) p)
(t (normalise (polynomial-add0 p q)))))
Notice that your code makes a huge commitment to cancelling
zero coefficients. If you make any mistake with this you are
completely screwed, because the formula (= 0 (caar p)) is
taking as zero any polynomial for which the coefficient of
the lowest order term is zero. So you really want to write
(defun zero-poly-p (p)
(if (= 0 (caar p))
(if (endp (cdr p))
t
(error "Merde! Zero coefficient in ~A" p))
nil))
If you don't abstract, by replacing (= 0 (caar p)) with
zero-poly-p, you cannot do this kind of defensive
programming.
4)The degree of the zero polynomial is usually taken to be
minus-infinity.
You could do this in CL, defining
(defun add-degrees (n m)
(if (or (eql n 'minus-infinity)
(eql m 'minus-infinity))
'minus-infinity
(+ n m)))
etc. You don't actually use polynomial-degree, but it is
probably worth sticking as close as you can to the text
books if you extend the code further.
Alan Crowe
Edinburgh
Scotland
Le 09-10-2005, Alan Crowe <····@cawtech.freeserve.co.uk> a �crit :
> The issue is partly one of documentation. You are throwing
> away information as you code. You have decided how you want
> ...
I thank you very much for your long answer; you did look very
carefully at my code, and I will follow most of your advices
(as I already took care of previous advices).
Thank you very much to you and to the other who answered to my
questions.
Cordially,
--
Thomas Baruchel
write to baruchel at the host called bluebottle dot com
�crire � baruchel chez l'h�te nomm� bluebottle point com
http://baruchel.thomas.free.fr/