request for people to comment on my code
Marc Spitzer
object oriented common lisp and set to work on exercise 4.7.2, making
sure a list contains a valid roman numeral. It is not finished yet,
but I feel it is far enough along that it can picked apart by the more
knowledgeable people in this group. There is 1 unimplemented features,
keeping track of how many times I have seen a letter. One of my main
concerns is that I feel that I am making this more complex then it
needs to be, throwing code at a problem is not a good way to
program. One of my goals is to do this only using only what is
presented in OOCL through chapter 4, recursion, list & trees, basic
language constructs. I know that there are better ways to do this, I
read ahead, but using them would prevent me from learning what I
should be learning here.
Thank's for the help
marc
Here are some test runs:
* (check-roman '(m c m i))
T
* (check-roman '(m c m m))
NIL
* (check-roman '( m c m x c v i))
T
* (check-roman '( i i i ))
T
* (check-roman '( i i i i ))
T
* (check-roman '(v c))
NIL
*
And here is the code:
(defvar roman-number-a-list
'((I 1) (V 5) (X 10) (L 50) (C 100) (D 500) (M 1000)))
(defvar letter-count '((i 0) (v 0) (x 0) (l 0) (c 0) (d 0) (m 0)))
(defvar letter-max '((i 3) (v 1) (x 3) (l 1) (c 3) (d 1) (m 3)))
(defvar roman-next
'((I ( x v i)) (V (I)) (X (c l x v i)) (l (x v i)) (c ( m d c l x v i))
(d ( c l x v i)) (m (d c l x v i ))))
(defvar x-lt-y '(( c (x l v i)) (x ( v i))))
(defvar roman-order '( i v x l c d m))
(defun roman-char-value (roman)
(cadr (assoc roman roman-number-a-list )))
(defun good-pair (a b)
(cond ((and (equal a 'c) (or (equal b 'm) (equal b 'd)))
t)
((and (equal a 'x) (or (equal b 'c) (equal b 'd)))
t)
((and (equal a 'i) (or (equal b 'x) (equal b 'v)))
t)
(t nil)))
(defun good-third (first third)
(if (and (assoc first x-lt-y) (member third (cadr (assoc first x-lt-y))))
t
nil))
(defun roman-charp (char)
(assoc char roman-number-a-list))
(defun valid-roman ( first second third rest count)
(cond ((null first) t )
((and (roman-charp first) (null second))
t)
((and (not (roman-charp first)) (null second ))
nil)
((and (roman-charp first) (roman-charp second) (null third))
(cond ((>= (roman-char-value first) (roman-char-value second))
t)
((good-pair first second )
t)
(t nil)))
((and (roman-charp first)(roman-charp second)(roman-charp third))
(cond ((> (roman-char-value first)(roman-char-value second))
(valid-roman second third (car rest) (cdr rest) count))
((and (< (roman-char-value first) (roman-char-value second))
(good-third first third))
(valid-roman third (car rest) (cadr rest) (cddr rest) count))
((equal first second)
(valid-roman second third (car rest) (cdr rest) count))
(t nil)))
(t nil)))
(defun check-roman (roman-list)
(valid-roman (car roman-list) (cadr roman-list) (caddr roman-list)
(cdddr roman-list) letter-count ))
Kenny Tilton
I know you haven't focused on counting yet, but when you do:
> (defvar letter-count '((i 0) (v 0) (x 0) (l 0) (c 0) (d 0) (m 0)))
I am no expert, but if you plan on eventually incrementing those counts
it could be a problem that you are using a literal. Just initialize to
nil and add things to be counted as you come tot hem if they do not
already exist. And since it is a special variable, why pass it as an
argument?
I also noticed (equal a 'x) where EQl would have served.
Also, the roman-order is implicit in the roman-number-a-list (even if
that is not sorted you can looked at the associated values to decide
order.
But if what bothers you about the code is what bothers me, the algorithm
is the bigger issue. One big tip i would offer is to do it like this:
(defun check-roman (&rest rnums)
(dolist (rnum rnums)
...look at one character at a time...))
And try not to do it by hardcoding all OK cases; imagine the next
exercise will be to extend your solution to Roman Numerals 2002 which
uses two dozen letters. For example roman-next I believe can be
expressed by saying a an rnum can be <= the prior rnum or for the "IV"
stuff:
From: http://www.deadline.demon.co.uk/roman/1999.htm
"But one rule is never broken. The Romans strictly represented units,
tens, hundreds, and thousands as separate items in their numbers. That
is probably because the numerals represented numbers as they were
depicted on an abacus - a calculating machine using pebbles or beads
which were arranged from right to left in columns of units, tens,
hundreds, thousands etc. That means that 99 could be represented as XCIX
- 90+9 but never as IC. Similarly, 999 cannot be IM and 1999 cannot be
MIM. A consequence of this strict place rule is that an I can only be
used to the left of a V or an X; an X can only be used to the left of an
L or a C. And a C can only be
used to the left of a D or an M"
Sorry, I know you asked about Lisp specifically, but the hardcoding of
cases really jumped out at me.
kenny
clinisys
Marc Spitzer
> Do you want comments about the Lisp or about the algorithm?
anything, feel free
>
> I know you haven't focused on counting yet, but when you do:
>
>> (defvar letter-count '((i 0) (v 0) (x 0) (l 0) (c 0) (d 0) (m 0)))
>
> I am no expert, but if you plan on eventually incrementing those counts
> it could be a problem that you are using a literal. Just initialize to
> nil and add things to be counted as you come tot hem if they do not
> already exist. And since it is a special variable, why pass it as an
> argument?
>
The orignal reason was to pass around a copy that got changed and kept
the orignal redy for the next run.
> I also noticed (equal a 'x) where EQl would have served.
>
I have not realy figured out the equal,eq,eql,tree-equal,=,equalp to
the point of using it safely and equal seemed to cover all the cases I
needed.
> Also, the roman-order is implicit in the roman-number-a-list (even if
> that is not sorted you can looked at the associated values to decide
> order.
>
That was just a convienence thing for my first atempt, and that was
ugly.
> But if what bothers you about the code is what bothers me, the algorithm
> is the bigger issue. One big tip i would offer is to do it like this:
>
> (defun check-roman (&rest rnums)
> (dolist (rnum rnums)
> ...look at one character at a time...))
That is not introduced by chapter 4, so it would not be honest of me
to use it. It would also prevent me from learning what I should be
learning here by giving me the answer befor I figure out the
question, progn & unwind-protect & local varables fall into this
catagory also.
I just thought of something, a possible reason why scheme might be in
some small way better for teaching. You can not cheat as easily
because there is so much less to cheat with. But that a very BAD
reason when you think about it.
>
> And try not to do it by hardcoding all OK cases; imagine the next
> exercise will be to extend your solution to Roman Numerals 2002 which
> uses two dozen letters. For example roman-next I believe can be
> expressed by saying a an rnum can be <= the prior rnum or for the "IV"
> stuff:
>
> From: http://www.deadline.demon.co.uk/roman/1999.htm
>
Nice link. but I think adding dual coding schemes would be easy to do
in my version. if you see a reverse ordering in the number then check
if the count is greater then 0, or if it exists, and if count = 0 or
returns null then set count to max for the lower valued letter since
you cannot see any more of them. If the count is greater then 0 then
signal a syntax error. there is a case where this does not work, cmxc
or xcix or xxxix ... . But that is what roman numbers are all about.
Now the hard coding you are talking about is in, for example,
good-pair:
(defun good-pair (a b)
(cond ((and (equal a 'c) (or (equal b 'm) (equal b 'd)))
t)
((and (equal a 'x) (or (equal b 'c) (equal b 'l)))
t)
((and (equal a 'i) (or (equal b 'x) (equal b 'v)))
t)
(t nil)))
which could be rewritten as(untested):
(defvar fred '( (c (m d)) (x ( c l)) (i (x v))))
(defun bob ( first second)
( member second (cadr (assoc first fred))))
And looking at it now I can see your point, it looks simpler and
easier to maintain. And more lispy also.
> "But one rule is never broken. The Romans strictly represented units,
> tens, hundreds, and thousands as separate items in their numbers. That
> is probably because the numerals represented numbers as they were
> depicted on an abacus - a calculating machine using pebbles or beads
> which were arranged from right to left in columns of units, tens,
> hundreds, thousands etc. That means that 99 could be represented as XCIX
> - 90+9 but never as IC. Similarly, 999 cannot be IM and 1999 cannot be
> MIM. A consequence of this strict place rule is that an I can only be
> used to the left of a V or an X; an X can only be used to the left of an
> L or a C. And a C can only be
> used to the left of a D or an M"
>
> Sorry, I know you asked about Lisp specifically, but the hardcoding of
> cases really jumped out at me.
>
I am sure there are better ways to do it and I have forgotten most, if
not all, of them. I have gotten very rusty in the years I have been
doing SA work.
> kenny
> clinisys
Thanks for the help.
marc
Kenny Tilton
Marc Spitzer wrote:
>
> I have not realy figured out the equal,eq,eql,tree-equal,=,equalp to
> the point of using it safely and equal seemed to cover all the cases I
> needed.
<heh-heh> yeah, I feel the same way about EQ and EQL
> > But if what bothers you about the code is what bothers me, the algorithm
> > is the bigger issue. One big tip i would offer is to do it like this:
> >
> > (defun check-roman (&rest rnums)
> > (dolist (rnum rnums)
> > ...look at one character at a time...))
>
> That is not introduced by chapter 4, so it would not be honest of me
> to use it.
ok, don't use dolist. you can still look at the numerals one at a time.
in fact, the worked example re roman numerals in chapter four does
exactly that, using car-cdr recursion. i wager Slade expects you to use
that as a starting point for the exercise, just as he would not want you
using dolist.
btw, i should have made clear that rather than critique your approach in
bits and pieces, i am making a wild leap here. i think the discipline of
looking at just one roman numeral at a time will lead you to many of the
improvements i have in mind.
so bottom line, you are showing commendable respect for your teacher (in
the traditional martial arts sense) by limiting your repertoire to the
material presented so far. now extend that respect by emulating your
teacher's worked examples; they are no accident, nor is it an accident
that an exercise on roman numerals follows a worked example on roman
numerals.
kenny
clinisys
Marc Spitzer
>
>
> Marc Spitzer wrote:
>>
>> I have not realy figured out the equal,eq,eql,tree-equal,=,equalp to
>> the point of using it safely and equal seemed to cover all the cases I
>> needed.
>
> <heh-heh> yeah, I feel the same way about EQ and EQL
>
>> > But if what bothers you about the code is what bothers me, the algorithm
>> > is the bigger issue. One big tip i would offer is to do it like this:
>> >
>> > (defun check-roman (&rest rnums)
>> > (dolist (rnum rnums)
>> > ...look at one character at a time...))
>>
>> That is not introduced by chapter 4, so it would not be honest of me
>> to use it.
>
> ok, don't use dolist. you can still look at the numerals one at a time.
> in fact, the worked example re roman numerals in chapter four does
> exactly that, using car-cdr recursion. i wager Slade expects you to use
> that as a starting point for the exercise, just as he would not want you
> using dolist.
I just reread the example and it uses a 1 char look ahead to check if
x_current < x_next and if that is true it makes x_current negative. So
he is realy using 2 charaters. The thing that is confusing the hell
out of me is where/how do I keep the state information current in a
non hideous way?
>
> btw, i should have made clear that rather than critique your approach in
> bits and pieces, i am making a wild leap here. i think the discipline of
> looking at just one roman numeral at a time will lead you to many of the
> improvements i have in mind.
>
Well your guess is probably better then mine on this subject, at least
until I solve it.
> so bottom line, you are showing commendable respect for your teacher (in
> the traditional martial arts sense) by limiting your repertoire to the
> material presented so far. now extend that respect by emulating your
> teacher's worked examples; they are no accident, nor is it an accident
> that an exercise on roman numerals follows a worked example on roman
> numerals.
>
> kenny
> clinisys
Back to the salt mines.
marc
Kenny Tilton
> > Marc Spitzer wrote:
> I just reread the example and it uses a 1 char look ahead to check if
> x_current < x_next and if that is true it makes x_current negative. So
> he is realy using 2 charaters.
uh-oh, i just reread it myself, i think you also have to preserve the
conversion to decimal while /adding/ a validity test.
anyway, the lookahead does not change the principle; anytime you walk
through a list one thing at a time you will need surrounding context to
do the Right Thing. lookback is also common and easier. even if I do not
lookahead I can use future context by deferring, in this case, adding a
positive until I get a look at the next character. but I wager the
author did not want to get too fancy at this early stage, so he used
lookahead.
> The thing that is confusing the hell
> out of me is where/how do I keep the state information current in a
> non hideous way?
Looks like defvar is fair game, just initialize them all up front. I do
not think that is technically hideous as long as the rules say less
hideous stuff is out of bounds.
Which reminds me of the route description I once read for a rock climb:
"After exiting the corner, don't use the hand jam nearby on the slab,
that hold is on a different route."
kenny
clinisys
Marc Spitzer
>
>> > Marc Spitzer wrote:
>> I just reread the example and it uses a 1 char look ahead to check if
>> x_current < x_next and if that is true it makes x_current negative. So
>> he is realy using 2 charaters.
>
> uh-oh, i just reread it myself, i think you also have to preserve the
> conversion to decimal while /adding/ a validity test.
I got that one solved:
(defun roman-to-dec ( roman)
(if (valid-roman roman)
(make-dec(roman))
nil))
where make-dec is in the book as an example. I will admit that it
is not the fastest way, but in theory it should work.
>
> anyway, the lookahead does not change the principle; anytime you walk
> through a list one thing at a time you will need surrounding context to
> do the Right Thing. lookback is also common and easier. even if I do not
> lookahead I can use future context by deferring, in this case, adding a
> positive until I get a look at the next character. but I wager the
> author did not want to get too fancy at this early stage, so he used
> lookahead.
>
>> The thing that is confusing the hell
>> out of me is where/how do I keep the state information current in a
>> non hideous way?
>
> Looks like defvar is fair game, just initialize them all up front. I do
> not think that is technically hideous as long as the rules say less
> hideous stuff is out of bounds.
You do have a point.
>
> Which reminds me of the route description I once read for a rock climb:
> "After exiting the corner, don't use the hand jam nearby on the slab,
> that hold is on a different route."
>
> kenny
> clinisys
marc
Steven M. Haflich
Kenny Tilton wrote:
> I also noticed (equal a 'x) where EQl would have served.
EQ would also be sufficient.
In general, a compiler that is merely good can rewrite
calls to the several equality predicates when one of the
arguments is a constant, replacing EQUAL with EQL, and EQL
with EQ, when the stricter predicate is equivalent for the
constant value. Therefore, the one you choose should be the
one that is conceptually clearest for the human reader to
understand. I would choose EQ in this circumstance, since
I know very well that for symbols all the other equality
predicates are equivalent to EQ. However, a different
programmer thinking about the code in a different way
might make a different choice.
Software Scavenger
> sure a list contains a valid roman numeral. It is not finished yet,
The weather outside is frightful and the fire is so delightful and
since we have no place to go I wrote some roman numeral functions too.
With these you can use a string or list and validate roman or convert
decimal to roman. Not really a solution to your problem but might be
useful example of different approach.
First, a brief analysis:
mmmmmm ccc xxx iii
cd xl iv
dccc lxxx viii
cm xc ix
(Hope that analysis wasn't too verbose.)
;; Helper function tier-roman decides format e.g. IV vs IIII.
;; First 3 args tell which tier e.g. hundreds vs tens etc.
;; 4th arg tells how many e.g. IIII or XXXX is 4.
;; '(X V I 4) ==> '(I V)
;; '(X V I 7) ==> '(V I I)
;; '(C L X 7) ==> '(L X X)
(defun tier-roman (10sym 5sym 1sym n)
(flet ((ones (k) (loop repeat k collect 1sym)))
(case n
((0 1 2 3) (ones n))
(4 (list 1sym 5sym))
((5 6 7 8) (cons 5sym (ones (- n 5))))
(9 (list 1sym 10sym)))))
;; 2001 ==> '(M M I)
(defun integer-roman (integer)
(let* ((thousands (truncate integer 1000))
(hundreds (truncate (mod integer 1000) 100))
(tens (truncate (mod integer 100) 10))
(ones (mod integer 10)))
(nconc (loop repeat thousands collect 'm)
(tier-roman 'm 'd 'c hundreds)
(tier-roman 'c 'l 'x tens)
(tier-roman 'x 'v 'i ones))))
;; trim whatever from left end of list
;; 'M '(M M M X V I) ==> '(X V I)
(defun ltrim (elt list)
(loop while (eql (car list) elt) do (pop list))
list)
;; '(M X V I) ==> T
(defun valid-roman-symlist (list)
(setq list (ltrim 'm list))
(let ((lists (loop as i below 1000 collect (integer-roman i))))
(if (member list lists :test 'equal) t nil)))
;; #\x ==> 'X
(defun char-symbol (char)
(intern (make-string 1 :initial-element (char-upcase char))))
;; "MCXVI" ==> '(M C X V I)
(defun chars-symbols (string &optional (start 0) end)
(map 'list 'char-symbol (subseq string start end)))
;; "MXVI" ==> T
(defun valid-roman-string (string &optional (start 0) end)
(valid-roman-symlist (chars-symbols string start end)))
Marc Spitzer
> ma...@oscar.eng.cv.net (Marc Spitzer) wrote in message news:
<slrna2d2q...@oscar.eng.cv.net>...
>
>> sure a list contains a valid roman numeral. It is not finished yet,
>
> The weather outside is frightful and the fire is so delightful and
> since we have no place to go I wrote some roman numeral functions too.
> With these you can use a string or list and validate roman or convert
> decimal to roman. Not really a solution to your problem but might be
> useful example of different approach.
>
Thanks for the code, hopefuly I will know enough lisp to understand it soon.
> First, a brief analysis:
>
> mmmmmm ccc xxx iii
> cd xl iv
> dccc lxxx viii
> cm xc ix
>
> (Hope that analysis wasn't too verbose.)
not at all
This will be fun, as I learn more lisp I can understand more of
the code.
happy new year
marc
Martti Halminen
> One of my main
> concerns is that I feel that I am making this more complex then it
> needs to be, throwing code at a problem is not a good way to
> program. One of my goals is to do this only using only what is
> presented in OOCL through chapter 4, recursion, list & trees, basic
> language constructs.
I don't have the book handy (and I am too lazy to dig its contents from
the web...), so the following might not strictly fit in your goals.
Didn't bother testing them, either, so some bugs wouldn't surprise me.
- These comments mostly about Lisp, I hope what you are doing makes some
sense re roman numbers...
Some simple comments:
> * (check-roman '( m c m x c v i))
> (defvar roman-number-a-list
> '((I 1) (V 5) (X 10) (L 50) (C 100) (D 500) (M 1000)))
A very wide-spread style in CL programming is to always mark special
variables by naming them with asterisks around the name:
(defvar *roman-number-a-list* ...)
> (defvar letter-count '((i 0) (v 0) (x 0) (l 0) (c 0) (d 0) (m 0)))
If you introduce lists with '( ), the compiler is free to consider it
as a literal, and may for example use the same list cells everywhere
instead of a separate copy in each instance. Leads easily to interesting
aliasing bugs.
> (defvar roman-next
> '((I ( x v i)) (V (I)) (X (c l x v i)) (l (x v i)) (c ( m d c l x v i))
> (d ( c l x v i)) (m (d c l x v i ))))
You might try to learn to include a little documentation string in your
defvar forms, too. I first thought this was some kind of ordering
relation, instead of telling which letters may follow each other (if
this is what this means...)
> (defvar x-lt-y '(( c (x l v i)) (x ( v i))))
I'd rather do this as a function: how about for example:
(defun x-gt-y (x y) (member x (rest (member y *roman-order*))))
>
> (defvar roman-order '( i v x l c d m))
> (defun good-pair (a b)
> (cond ((and (equal a 'c) (or (equal b 'm) (equal b 'd)))
> t)
> ((and (equal a 'x) (or (equal b 'c) (equal b 'd)))
> t)
> ((and (equal a 'i) (or (equal b 'x) (equal b 'v)))
> t)
> (t nil)))
- When you are comparing symbols, it is safe to use EQ. I usually see
EQUAL as a sign that we might be comparing also lists, numbers etc.
- I'd have written this something like this:
(defun good-pair-p (a b)
(case a
(c (member b '(m d)))
(x (member b '(c d)))
(i (member b '(x v)))
(otherwise nil)))
> (defun roman-charp (char)
> (assoc char roman-number-a-list))
This could also be done for example by (member char *roman-order*), or
you could have a roman-char property defined on symbols, mostly a matter
of personal taste.
> (defun valid-roman ( first second third rest count)
As CL has separate namespaces for functions and variables, this is not
an error, but it is often clearer if you don't unnecessarily use the
names of commonly used CL functions for your variables. (It is nice to
have the capability, but it should not be overused.)
> (defun check-roman (roman-list)
> (valid-roman (car roman-list) (cadr roman-list) (caddr roman-list)
> (cdddr roman-list) letter-count ))
Your valid-roman function would be much clearer if you took the
roman-charp tests out from it:
(defun check-roman (roman-list)
(cond ((null roman-list) nil)
((= (length roman-list) 1) (roman-charp (first roman-list)))
;; In long lists length is inefficient here, endp might be
better.
((not (every #'roman-charp roman-list)) nil)
(T (valid-roman (first roman-list)
(second roman-list)
... ))))
- later on in calls like this some destructuring tricks
might be useful, too. Probably not in the first chapters of the book.
--
Marc Spitzer
> Marc Spitzer wrote:
>
>> One of my main
>> concerns is that I feel that I am making this more complex then it
>> needs to be, throwing code at a problem is not a good way to
>> program. One of my goals is to do this only using only what is
>> presented in OOCL through chapter 4, recursion, list & trees, basic
>> language constructs.
>
> I don't have the book handy (and I am too lazy to dig its contents from
> the web...), so the following might not strictly fit in your goals.
> Didn't bother testing them, either, so some bugs wouldn't surprise me.
> - These comments mostly about Lisp, I hope what you are doing makes some
> sense re roman numbers...
>
> Some simple comments:
>
>> * (check-roman '( m c m x c v i))
>
>
>> (defvar roman-number-a-list
>> '((I 1) (V 5) (X 10) (L 50) (C 100) (D 500) (M 1000)))
>
> A very wide-spread style in CL programming is to always mark special
> variables by naming them with asterisks around the name:
> (defvar *roman-number-a-list* ...)
Good point, I will clean that up
>
>
>> (defvar letter-count '((i 0) (v 0) (x 0) (l 0) (c 0) (d 0) (m 0)))
>
> If you introduce lists with '( ), the compiler is free to consider it
> as a literal, and may for example use the same list cells everywhere
> instead of a separate copy in each instance. Leads easily to interesting
> aliasing bugs.
>
I did not know that
>> (defvar roman-next
>> '((I ( x v i)) (V (I)) (X (c l x v i)) (l (x v i)) (c ( m d c l x v i))
>> (d ( c l x v i)) (m (d c l x v i ))))
>
> You might try to learn to include a little documentation string in your
> defvar forms, too. I first thought this was some kind of ordering
> relation, instead of telling which letters may follow each other (if
> this is what this means...)
>
yes it is.
>> (defvar x-lt-y '(( c (x l v i)) (x ( v i))))
>
> I'd rather do this as a function: how about for example:
> (defun x-gt-y (x y) (member x (rest (member y *roman-order*))))
>
That I did not think of, and it is much nicer way of solving the
problem.
>>
>> (defvar roman-order '( i v x l c d m))
>
>> (defun good-pair (a b)
>> (cond ((and (equal a 'c) (or (equal b 'm) (equal b 'd)))
>> t)
>> ((and (equal a 'x) (or (equal b 'c) (equal b 'd)))
>> t)
>> ((and (equal a 'i) (or (equal b 'x) (equal b 'v)))
>> t)
>> (t nil)))
>
> - When you are comparing symbols, it is safe to use EQ. I usually see
> EQUAL as a sign that we might be comparing also lists, numbers etc.
> - I'd have written this something like this:
> (defun good-pair-p (a b)
> (case a
> (c (member b '(m d)))
> (x (member b '(c d)))
> (i (member b '(x v)))
> (otherwise nil)))
>
>
that is cool, but it is introduced later in the book.
>> (defun roman-charp (char)
>> (assoc char roman-number-a-list))
>
> This could also be done for example by (member char *roman-order*), or
> you could have a roman-char property defined on symbols, mostly a matter
> of personal taste.
roman-order was something that was orignaly left over from
my first attempt, the method was much worse then this attempt.
>
>> (defun valid-roman ( first second third rest count)
>
> As CL has separate namespaces for functions and variables, this is not
> an error, but it is often clearer if you don't unnecessarily use the
> names of commonly used CL functions for your variables. (It is nice to
> have the capability, but it should not be overused.)
>
point taken
>
>> (defun check-roman (roman-list)
>> (valid-roman (car roman-list) (cadr roman-list) (caddr roman-list)
>> (cdddr roman-list) letter-count ))
>
> Your valid-roman function would be much clearer if you took the
> roman-charp tests out from it:
>
> (defun check-roman (roman-list)
> (cond ((null roman-list) nil)
> ((= (length roman-list) 1) (roman-charp (first roman-list)))
> ;; In long lists length is inefficient here, endp might be
> better.
> ((not (every #'roman-charp roman-list)) nil)
> (T (valid-roman (first roman-list)
> (second roman-list)
> ... ))))
> - later on in calls like this some destructuring tricks
> might be useful, too. Probably not in the first chapters of the book.
>
> --
Thanks for the help.
marc
Thomas F. Burdick
> In article <3C2A64B7...@kolumbus.fi>, Martti Halminen wrote:
> > Marc Spitzer wrote:
> >> (defun valid-roman ( first second third rest count)
> >
> > As CL has separate namespaces for functions and variables, this is not
> > an error, but it is often clearer if you don't unnecessarily use the
> > names of commonly used CL functions for your variables. (It is nice to
> > have the capability, but it should not be overused.)
>
> point taken
This is a style point, so everyone's entitled to his/her own opinion,
but I have no problem with code that uses FIRST, SECOND, THIRD, REST,
and COUNT as variables, and I do it all the time. I'll keep the rest
of a list in REST, the result of MEMBER in MEMBER, etc. So I'd say,
go with your own preference here.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Marc Spitzer
> ma...@oscar.eng.cv.net (Marc Spitzer) writes:
>
>> In article <3C2A64B7...@kolumbus.fi>, Martti Halminen wrote:
>> > Marc Spitzer wrote:
>
>> >> (defun valid-roman ( first second third rest count)
>> >
>> > As CL has separate namespaces for functions and variables, this is not
>> > an error, but it is often clearer if you don't unnecessarily use the
>> > names of commonly used CL functions for your variables. (It is nice to
>> > have the capability, but it should not be overused.)
>>
>> point taken
>
> This is a style point, so everyone's entitled to his/her own opinion,
> but I have no problem with code that uses FIRST, SECOND, THIRD, REST,
> and COUNT as variables, and I do it all the time. I'll keep the rest
> of a list in REST, the result of MEMBER in MEMBER, etc. So I'd say,
> go with your own preference here.
>
counter-point taken :)
marc
David Sletten
> I am trying to get back to learning lisp, so I got out my copy of
> object oriented common lisp and set to work on exercise 4.7.2, making
> sure a list contains a valid roman numeral. It is not finished yet,
> but I feel it is far enough along that it can picked apart by the more
> knowledgeable people in this group. There is 1 unimplemented features,
> keeping track of how many times I have seen a letter. One of my main
> concerns is that I feel that I am making this more complex then it
> needs to be, throwing code at a problem is not a good way to
> program. One of my goals is to do this only using only what is
> presented in OOCL through chapter 4, recursion, list & trees, basic
> language constructs. I know that there are better ways to do this, I
> read ahead, but using them would prevent me from learning what I
> should be learning here.
>
> Thank's for the help
>
> marc
>
I didn't spend a lot of time analyzing your code, but I am reading the
same book, so I'll show you my solution. It should meet the constraints
you seek to satisfy--namely it doesn't use features from later in the
book (except for the FORMAT call). (Oh, DEFCONSTANT and closures aren't
covered until chapter 5...) I based my logic on rules found on the web
site mentioned by others:
http://www.deadline.demon.co.uk/roman/intro.htm
;;;
;;; 4.7.2
;;;
(defconstant roman-numerals '((i 1)
(v 5)
(x 10)
(l 50)
(c 100)
(d 500)
(m 1000)))
;;;
;;; Accessor function.
;;;
(defun numeral-to-decimal (numeral)
(second (assoc numeral roman-numerals)) )
;;;
;;; Main function.
;;;
(defun roman-to-decimal (num-list)
(cond ((roman-filter num-list) nil)
(t (translate num-list))) )
;;;
;;; Translate a valid Roman numeral to decimal
;;;
(defun translate (num-list)
(cond ((null num-list) 0)
((and (rest num-list)
(< (numeral-to-decimal (first num-list))
(numeral-to-decimal (second num-list))))
(- (translate (rest num-list))
(numeral-to-decimal (first num-list))))
(t (+ (translate (rest num-list))
(numeral-to-decimal (first num-list)))) ) )
;;;
;;; Test validity of Roman numeral. Return T to indicate that it
;;; fails one of the tests below.
;;;
(defun roman-filter (num-list)
(cond ((or (adjacent-scale-error num-list)
(position-error num-list)
(sequence-error num-list))
(format t "~&Malformed roman numeral.~%")
t)
(t nil)) )
;;;
;;; Test whether elements to be subtracted are valid.
;;; A smaller value should not be less than one tenth of the value it
;;; precedes.
;;;
(defun adjacent-scale-error (num-list)
(cond ((null (rest num-list)) nil)
((< (* 10 (numeral-to-decimal (first num-list)))
(numeral-to-decimal (second num-list))) t)
(t (adjacent-scale-error (rest num-list)))) )
;;;
;;; Only one smaller value may appear to left of larger value.
;;; If a value is found that is less than or equal to the value on its
;;; right, then the auxiliary function is triggered. It continues to
examine
;;; the list. If it ever finds a larger value later in the list, then the
;;; number is malformed.
;;; Examples:
;;; XIIX -> bad
;;; XIII -> ok
;;; IXL -> bad
;;; Note: There is some inefficiency in the second example as the
first pair
;;; of I's trigger the aux function and later the second pair trigger it
;;; again.
;;;
(defun sequence-error (num-list)
(cond ((null (rest num-list)) nil)
((<= (numeral-to-decimal (first num-list))
(numeral-to-decimal (second num-list)))
(or (sequence-error-aux (rest num-list))
(sequence-error (rest num-list))))
(t (sequence-error (rest num-list)))) )
(defun sequence-error-aux (num-list)
(cond ((null (rest num-list)) nil)
((< (numeral-to-decimal (first num-list))
(numeral-to-decimal (second num-list)))
t)
((= (numeral-to-decimal (first num-list))
(numeral-to-decimal (second num-list)))
(sequence-error-aux (rest num-list)))
(t nil)) )
;;;
;;; Only I, X, C may appear to the left of a larger number.
;;;
(let ((ok-on-left '(i x c)))
(defun position-error (num-list)
(cond ((null (rest num-list)) nil)
((and (not (member (first num-list) ok-on-left))
(< (numeral-to-decimal (first num-list))
(numeral-to-decimal (second num-list)))) )) ) )
I should point out that your code identifies (m c m m) as invalid
whereas mine does not. I'll have to look at that. Also, if you are
curious, I've modified this code to run as a CGI program:
http://24.249.238.144/cgi-bin/roman-numerals
As far as the equality tests go, here's my understanding (hopefully one
of the experts will correct me if I'm wrong.):
The first distinction to be made is between type-specific tests and
general tests. For instance = only works with numbers, CHAR= only works
with characters and STRING= only works with strings. These are pretty
straightforward. The trickier ones are the general tests.
The strictest is EQ, which only returns T if two objects represent the
same address in memory. As a consequence a symbol is EQ to itself since
each symbol has a unique storage location. EQL is similar to EQ except
when dealing with floats, bignums, and characters. Depending on your
Lisp implementation these datatypes may be stored in individual
locations rather than in a single place. Thus, (EQ #\a #\a) may return T
or NIl, but (EQL #\a #\a) always returns T. Furthermore,
MOST-POSITIVE-FIXNUM is implementation defined. So two large integers
may be EQ in one Lisp where they are fixnums but only EQL in another
where they may be bignums. Due to these problems the question arises
'Why not always use EQL?'. The reason to use EQ is that it is a simpler
test and should therefore be more efficient where you know it's safe.
The rule of thumb for EQUAL is that two objects are EQUAL if they "are
printed the same." Thus (EQUAL '(A (B)) '(A (B))) is true. EQUALP takes
this one step further and ignores case for characters/strings and
ignores type for numbers. As a result, all of the following return T:
(EQUALP "Pung" "pung") (EQUALP 3 3.0) (EQUALP #\a #\A).
The basic rule to keep in mind with these general equality tests is that
the longer the name, the less strict the test is:
EQ -> EQL -> EQUAL -> EQUALP
(Thanks to Deborah Tatar and her book "A Programmer's Guide to Common Lisp")
A few more points to remember:
-EQL is the default test for many Lisp functions, e.g., MEMBER, ASSOC, ...
-Strings and characters have two sets of tests. One set (STRING=, ...)
is case-sensitive, the other (STRING-EQUAL, ...) isn't. If you use EQUAL
on 2 strings, Lisp actually uses STRING=. Likewise, EQUALP invokes
STRING-EQUAL. (This is chapter 6 of Slade's book.)
-= only works on numbers, but it works on any types of numbers: (= 3
3.0) => T
-I'm not 100% clear on TREE-EQUAL myself, but it appears to only differ
from EQUAL with args that aren't conses: (EQUAL "AB" "AB") => T
(TREE-EQUAL "AB" "AB") => NIL.
If you read this far I hope this helps.
David Sletten
Marc Spitzer
> Marc Spitzer wrote:
>
>> I am trying to get back to learning lisp, so I got out my copy of
>> object oriented common lisp and set to work on exercise 4.7.2, making
>> sure a list contains a valid roman numeral. It is not finished yet,
>> but I feel it is far enough along that it can picked apart by the more
>> knowledgeable people in this group. There is 1 unimplemented features,
>> keeping track of how many times I have seen a letter. One of my main
>> concerns is that I feel that I am making this more complex then it
>> needs to be, throwing code at a problem is not a good way to
>> program. One of my goals is to do this only using only what is
>> presented in OOCL through chapter 4, recursion, list & trees, basic
>> language constructs. I know that there are better ways to do this, I
>> read ahead, but using them would prevent me from learning what I
>> should be learning here.
>>
>> Thank's for the help
>>
>> marc
>>
>
>
> I didn't spend a lot of time analyzing your code, but I am reading the
> same book, so I'll show you my solution. It should meet the constraints
> you seek to satisfy--namely it doesn't use features from later in the
> book (except for the FORMAT call). (Oh, DEFCONSTANT and closures aren't
> covered until chapter 5...) I based my logic on rules found on the web
> site mentioned by others:
Thanks for the code, I will look at it when I solve the problem or
give up hope. My current idea is to let it stew in my head for a
while by doing some of the other problems in the chapter as a break.
The simple roman numerals are easy to do, all you would have to do is
have a current char and a count with a check against the max allowed
character run. I will try that one first and then I will be ready to
get medieval on the medieval roman numerals, perhaps.
marc
Erik Naggum
| I am trying to get back to learning lisp, so I got out my copy of object
| oriented common lisp and set to work on exercise 4.7.2, making sure a
| list contains a valid roman numeral.
I think this exercise shows that it was a bad idea to recurse only on the
elements/characters of the roman numeral. You also need to recurse on
the valid units and units-and-a-half (or half-units, depending on how you
look at them). If you use old-style roman numerals (format control
~:@R), there is one valid pattern: an optional unit-and-a-half followed
by no more than four units, but new-style (format control ~@R) is more
complex: one unit digit may be followed by the next larger unit or the
unit-and-a-half where old-style would have used four units. (That is, in
the old style, you need no look-ahead, but in new style, you need two: in
the number being parsed and in the list of units. Note that the largest
number representable in the old style is 4999, while the new style gives
up 3999, although many believe that a bar over the letters were used to
multiply it by 1000, making the largest numbers 4,999,999, and 3,999,999,
respectively, but such a bar is unavailable unless one wants to use
Unicode combining diacritics. Anyway, the history of this practice is
blurry and there are records of alternatives that used more letters than
MCXI for units and DLV for half-units, but they seem to have failed to
agree on the letters used.)
Anyway, since I have only skimmed the book, but think it has so far done
the reader a disservice by being very Schemish, both in naming the
function "roman-to-decimal" (as opposed to "roman-to-hexadecimal"?) and
in using recursion in the wrong way, I have toyed with an evil Scheme-
like solution to the problem. The function parse-failure could be
replaced by exploiting call-with-current-continuation, too. :)
(in-package :cl-user)
(defun parse-roman-digit-sequence (count roman start end digit unit half cont fail)
(cond ((< count 0) (funcall fail nil))
((= start end) 0)
((equalp (char roman start) (second unit))
(+ (first digit)
(parse-roman-digit-sequence
(1- count) roman (1+ start) end digit unit half cont fail)))
(t (funcall cont roman start end (cdr digit) (cdr unit) (cdr half) fail))))
(defun parse-old-roman-digit (roman start end digit unit half fail)
(cond ((= start end) 0)
((null digit) (funcall fail nil))
((equalp (char roman start) (first half))
(+ (* (first digit) 5)
(parse-old-roman-digit
roman (1+ start) end digit unit (cons nil (cdr half)) fail)))
(t (parse-roman-digit-sequence
4 roman start end digit unit half #'parse-old-roman-digit fail))))
(defun parse-new-roman-digit (roman start end digit unit half fail)
(cond ((= start end) 0)
((null digit) (funcall fail nil))
((and (< (1+ start) end)
(equalp (char roman start) (second unit))
(equalp (char roman (1+ start)) (first unit)))
(+ (* (first digit) 9)
(parse-new-roman-digit
roman (+ 2 start) end (cdr digit) (cdr unit) (cdr half) fail)))
((and (< (1+ start) end)
(equalp (char roman start) (second unit))
(equalp (char roman (1+ start)) (first half)))
(+ (* (first digit) 4)
(parse-new-roman-digit
roman (+ 2 start) end (cdr digit) (cdr unit) (cdr half) fail)))
((equalp (char roman start) (first half))
(+ (* (first digit) 5)
(parse-new-roman-digit
roman (1+ start) end digit (cons nil (cdr unit)) (cons nil (cdr half)) fail)))
(t (parse-roman-digit-sequence
3 roman start end digit unit half #'parse-new-roman-digit fail))))
(defun parse-roman-integer (roman &key (start 0) end old-style)
"Return the integer represented by the valid roman numeral, or nil.
Old-style uses four consecutive digits of a unit, while new-style
uses the next smaller unit before the unit or half-unit."
(setq end (or end (length roman)))
(when (< -1 start end (1+ (length roman)))
(flet ((parse-failure (value)
(return-from parse-roman-integer value)))
(funcall (if old-style #'parse-old-roman-digit #'parse-new-roman-digit)
roman start end '(1000 100 10 1) '(nil #\M #\C #\X #\I) '(nil #\D #\L #\V)
#'parse-failure))))
This was actually written in one pass, but damned if I can read it only a
day after it was written.
///
--
The past is not more important than the future, despite what your culture
has taught you. Your future observations, conclusions, and beliefs are
more important to you than those in your past ever will be. The world is
changing so fast the balance between the past and the future has shifted.
Coby Beck
"David Sletten" <slyt...@home.com> wrote in message
news:3C2A9A0B...@home.com...
> I should point out that your code identifies (m c m m) as invalid
> whereas mine does not. I'll have to look at that. Also, if you are
> curious, I've modified this code to run as a CGI program:
> http://24.249.238.144/cgi-bin/roman-numerals
>
I gave your page a whirl, cool! But I was wondering if things like iiiii and
xxxxxxxx are supposed to be valid? I didn't think so but have never poked into
roman numerals enough to write correct code. Your page accepts those inputs.
--
Coby
(remove #\space "coby . beck @ opentechgroup . com")
Marc Spitzer
> * Marc Spitzer
> | I am trying to get back to learning lisp, so I got out my copy of object
> | oriented common lisp and set to work on exercise 4.7.2, making sure a
> | list contains a valid roman numeral.
>
> I think this exercise shows that it was a bad idea to recurse only on the
> elements/characters of the roman numeral. You also need to recurse on
> the valid units and units-and-a-half (or half-units, depending on how you
> look at them). If you use old-style roman numerals (format control
> ~:@R), there is one valid pattern: an optional unit-and-a-half followed
> by no more than four units, but new-style (format control ~@R) is more
> complex: one unit digit may be followed by the next larger unit or the
> unit-and-a-half where old-style would have used four units. (That is, in
> the old style, you need no look-ahead, but in new style, you need two: in
> the number being parsed and in the list of units. Note that the largest
> number representable in the old style is 4999, while the new style gives
> up 3999, although many believe that a bar over the letters were used to
> multiply it by 1000, making the largest numbers 4,999,999, and 3,999,999,
> respectively, but such a bar is unavailable unless one wants to use
> Unicode combining diacritics. Anyway, the history of this practice is
> blurry and there are records of alternatives that used more letters than
> MCXI for units and DLV for half-units, but they seem to have failed to
> agree on the letters used.)
I did not know about the bar.
>
> Anyway, since I have only skimmed the book, but think it has so far done
> the reader a disservice by being very Schemish, both in naming the
> function "roman-to-decimal" (as opposed to "roman-to-hexadecimal"?) and
> in using recursion in the wrong way, I have toyed with an evil Scheme-
> like solution to the problem. The function parse-failure could be
> replaced by exploiting call-with-current-continuation, too. :)
That is over my head, for now. And I will look at the code after I
make at least 1 more attempt on my own. One of the annoying things
about this is I know there are things avalable to me in CL that would
make this much easier to do if they were in the subset of CL that has
been introduced so far.
Thanks for your time
marc
Marc Spitzer
No the longest repeating string of numerals is 3 or 4 depending on how you
define how the 9 and 4 numbers are handled, if you do it like I was taught
in school, 9 = IX and 4 = IV, then the longest run is 3. The other way,
9 = VIIII and 4 = IIII, give you a longest string of 4. The second way is
also much simpler to type check for. The 4 and 9 thing apply to each
power of ten.
> -- Coby (remove #\space "coby . beck @ opentechgroup . com")
marc
Marc Spitzer
The simple roman numerals were simple:
(defvar letter-max '((i 4) (v 1) (x 4) (l 1) (c 4) (d 1) (m 4)))
(defvar roman-number-a-list
'((I 1) (V 5) (X 10) (L 50) (C 100) (D 500) (M 1000)))
(defun roman-char-value (roman)
(cadr (assoc roman roman-number-a-list )))
(defun letter-max (char )
(cadr (assoc char letter-max )))
(defun roman-charp (char)
(assoc char roman-number-a-list))
(defun simple-check ( roman prev count )
(cond ((endp roman)
(if (roman-charp prev)
t
nil))
((eql prev (car roman))
(if (< count (letter-max (car roman)))
(simple-check (cdr roman) (car roman) (+ 1 count))
nil))
((> (roman-char-value prev) (roman-char-value (car roman) ))
(simple-check (cdr roman) (car roman) 0))
(t
nil)))
(defun simple-check-roman (roman)
(simple-check (cdr roman) (car roman) 0))
This was too simple. Time to declare victory for the night.
good night all
marc
Marc Spitzer
look at everybody else code.
thanks
marc
(defvar roman-number-a-list
'((I 1) (V 5) (X 10) (L 50) (C 100) (D 500) (M 1000)))
(defvar letter-max '((i 2) (v 1) (x 2) (l 1) (c 2) (d 1) (m 2)))
(defvar roman-order '( i v x l c d m))
(defun roman-char-value (roman)
(cadr (assoc roman roman-number-a-list )))
(defvar good-pair-list '( (i (v x )) (x (l c)) (c ( d m)) ) )
(defun good-pair (a b)
"reading from left to right a is first letter and b is second in the
roman numeral and a < b"
(member b (cadr (assoc a good-pair-list))))
(defun letter-max (char )
(cadr (assoc char letter-max )))
(defun roman-charp (char)
(assoc char roman-number-a-list))
(defvar max-next-legal-list '((i 1) (v 1) (x 10) (l 10)
(c 100) (d 100) (m 1000)))
(defun max-next (char)
(cadr (assoc char max-next-legal-list)))
(defun max-next-rev (char)
(1- (max-next char)))
(defun simple-check ( roman prev count max-value )
(cond ((endp roman)
(cond ((and (roman-charp prev)
(<= (roman-char-value prev) max-value))
t)
(( null prev)
t)
(t nil)))
((and (eql prev (car roman)) (<= (roman-char-value prev) max-value))
(if (< count (letter-max (car roman)))
(simple-check (cdr roman) (car roman) (+ 1 count) (max-next prev))
nil ))
((> (roman-char-value prev) (roman-char-value (car roman) ))
(simple-check (cdr roman) (car roman) 0 (max-next (car roman)) ))
((and (< (roman-char-value prev) (roman-char-value (car roman)))
(good-pair prev (car roman))
(<= (roman-char-value prev ) max-value))
(simple-check (cddr roman) (cadr roman) 0 (max-next-rev prev)))
(t
nil)))
(defun simple-check-roman (roman)
(simple-check (cdr roman) (car roman) 0 1000 ))
(defun roman-to-decimal ( roman)
"from the book "
(if (endp roman)
0
(+ (or
(and (cdr roman )
(< (roman-char-value (car roman))
(roman-char-value (cadr roman)))
(- (roman-char-value (car roman))))
(roman-char-value (car roman)))
(roman-to-decimal (cdr roman)))))
(defun check-&-convert (roman)
"type check and if valid convert to decimal"
(if (simple-check-roman roman)
(roman-to-decimal roman)
nil))