boggle.lisp: feedback welcome

[Jason S. Cornez]

What follows is the basis for a simple boggle program. I wrote it as
an exercise in learning Common Lisp (especially the LOOP macro.) This
was done for my own benefit, not as part of any class.

I am interested in feedback about my Common Lisp style with this code.
So far, I am not concerned about performance, but if you feel
declarations would improve the style, feel free to comment.

Thank you,
-Jason

;;; boggle.lisp
;;; Copyright 2001, Jason Cornez
;;; Everyone is freely given the right to do anything with this code.
;;; This is not guaranteed to do anything.
;;; If somehow you find it useful and copy it, please give credit.
;;;
;;; Description:
;;; Boggle is a game whose physical incarnation consists of 16 dice
;;; containg letters on each side. "Qu" is shown together on a single
;;; side. The boggle box is shaken so that the dice become randomly
;;; arranged in a 4 x 4 grid. The object is to find as many words as
;;; possible starting with any letter and choosing consecutive letters
;;; such that they are adjacent in any direction to the preceeding
;;; letter. In addition, each die may only be used once per word.
;;; There is a three minute timer. Scoring is one point for 3 or 4
;;; letter words and an additional point for each additional letter in
;;; longer words. "Qu" is counted as 2 letters, even though it is on
;;; a single die.
;;;
;;; Status:
;;; So far the game has no real user interface, no timer, and no way
;;; for more than one player to interact (since there is no
;;; interface). What does exist are the boggle dice and the ability
;;; to shake a box, to pretty-print the box, and then to validate and
;;; score words against the box. Ultimately, the above listed missing
;;; components should be added and perhaps also a check for words in
;;; some dictionary. This was written for fun as an exercise, so none
;;; of those are high priorities.

(in-package "user")

;; The 16 boggle dice
(defconstant +boggle-dice+ (make-array '(16 6) :initial-contents
'((#\T #\Y #\E #\L #\R #\T)
(#\N #\H #\N #\L #\R #\Z)
(#\E #\G #\N #\W #\H #\E)
(#\U #\N #\H #\I #\M #\Q)
(#\D #\R #\Y #\V #\L #\E)
(#\K #\S #\F #\F #\A #\P)
(#\J #\B #\O #\O #\B #\A)
(#\X #\I #\D #\R #\E #\L)
(#\S #\T #\I #\T #\Y #\D)
(#\O #\T #\W #\O #\T #\A)
(#\O #\S #\C #\A #\H #\P)
(#\E #\E #\G #\N #\A #\A)
(#\T #\M #\I #\O #\U #\C)
(#\S #\O #\I #\S #\T #\E)
(#\W #\R #\E #\T #\H #\V)
(#\U #\I #\E #\N #\E #\S))))

(defun shake-boggle-box ()
"Return a 4x4 array of characters representing a shaken boggle box."
(let ((dice (make-array 16))
(box (make-array '(4 4))))

;; fill dice with 0 to 15
(loop for i from 0 to 15
do (setf (aref dice i) i))

;; shuffle the dice, so we can't choose same one twice
(loop for i from 0 upto 15
for rand = (random 16) do
(psetf (aref dice i) (aref dice rand)
(aref dice rand) (aref dice i)))

;; fill the box with the dice, choosing a random side for each
(loop for i from 0 to 15 do
(setf (row-major-aref box i)
(aref +boggle-dice+ (aref dice i) (random 6))))

box))

(defun pprint-boggle-box (box)
"Pretty print a boggle box as 4 rows or 4 evenly spaced characters."
(loop for i from 0 to 3 do
(princ " ")
(loop for j from 0 to 3 do
(princ (aref box i j))
(if (char-equal (aref box i j) #\Q)
(princ "u ") ; after "Q" print "u"
(princ " ")))
(fresh-line)))

(defun score-word (word box)
"Calculate the score of the word for the given boggle box."
(cond ((< (length word) 3)
(values 0 :Too-Small))
((valid-word-p word box)
(values (max 1 (- (length word) 3)) :OK))
(t
(values 0 :Not-Found))))

(defun valid-word-p (word box)
"Return true if the word exists in the boggle box."
;; for each die in the box, see if the word can start from there
;; exit immediately if the word is found
(loop for i from 0 to 3 do
(loop for j from 0 to 3
when (valid-word-from-p word box i j '()) do
(return-from valid-word-p t))))

(defun valid-word-from-p (word box x y already-used)
"Recursively try to find word in box starting at location x, y. Keep
track to make sure each location is only used once."
(let ((first (elt word 0)) ; first letter of word
(rest (subseq word 1)) ; rest of word
(index (+ x (* 4 y))) ; unique index of current die
(neighbors '())) ; list of neighbors of current
die

;; if the die has been used or its letter doesn't match, return nil
(when (or (member index already-used)
(char-not-equal first (aref box x y)))
(return-from valid-word-from-p nil))

;; if on a "Q" and it is followed by "u" in word, skip searching
;; for the "u" since it is included on the "Q" die.
(when (and (char-equal #\Q first)
(char-equal #\u (elt rest 0)))
(setq rest (subseq rest 1)))

;; if there is no more left to the word, we found it! return t
(when (= (length rest) 0)
(return-from valid-word-from-p t))

;; compute list of neighbors. wrapping around edges not allowed.
(loop for i from (max 0 (1- x)) to (min 3 (1+ x)) do
(loop for j from (max 0 (1- y)) to (min 3 (1+ y)) do
(unless (and (= i x) (= j y))
(push (list i j) neighbors))))

;; for each neighbor, test the rest of the word remembering where
;; we've been. exit immediately upon success
(loop for (i j) in neighbors
when (valid-word-from-p rest box i j (cons index already-used))
return t)))

(defun score-words (word-list box)
"Sum the scores of a list of words for a boggle box."
(loop for word in word-list
sum (score-word word box)))

[Kent M Pitman]

ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) writes:

> I am interested in feedback about my Common Lisp style [...]

> (in-package "user")

You're using an outdated dialect. ANSI CL specifies "CL-USER".

You're also using lowercase, which suggests you're in an implementation
that, in violation of both the old and new standards (cltl1 and ansi cl),
your implementation is ignoring case in string-quoted package names.
That's non-conforming; don't learn to rely on it. It is normal for
an implementation to case-translate symbol names, so foo:bar is ok to
name a symbol "BAR" in the package "FOO". But it's not reasonable to
assume that (intern "bar" "foo") will find this same symbol since the
case-translation occurs before the call to INTERN, and INTERN is not
defined to do further case translation.

It's possible that your implementation is not case-translating but just
has a "helpful" extra nickname of "user" on the "USER" package; again
this is bad because it encourages you to rely on the use of lowercase
package names, which you should not. If you want to write your package
names in lowercase (and I am in a distinct minority by not recommending
this), you sould write (in-package :user).

> ;; The 16 boggle dice
> (defconstant +boggle-dice+ (make-array '(16 6) :initial-contents
> '((#\T #\Y #\E #\L #\R #\T)
> (#\N #\H #\N #\L #\R #\Z)
> (#\E #\G #\N #\W #\H #\E)
> (#\U #\N #\H #\I #\M #\Q)
> (#\D #\R #\Y #\V #\L #\E)
> (#\K #\S #\F #\F #\A #\P)
> (#\J #\B #\O #\O #\B #\A)
> (#\X #\I #\D #\R #\E #\L)
> (#\S #\T #\I #\T #\Y #\D)
> (#\O #\T #\W #\O #\T #\A)
> (#\O #\S #\C #\A #\H #\P)
> (#\E #\E #\G #\N #\A #\A)
> (#\T #\M #\I #\O #\U #\C)
> (#\S #\O #\I #\S #\T #\E)
> (#\W #\R #\E #\T #\H #\V)
> (#\U #\I #\E #\N #\E #\S))))

I recommend putting the value on the next line and not wasting the huge
block of space to its left.

(defconstant +boggle-dice+
(make-array ...))

By the way, there is no requirement that your initial-contents array have
the same element type as the target array, just a compatible one. So

(defconstant +boggle-dice+
(make-array '(16 6)

:initial-contents '("TYELRT" "NHNLRZ" ...)))

is sufficient.

> (defun shake-boggle-box ()
> "Return a 4x4 array of characters representing a shaken boggle box."
> (let ((dice (make-array 16))
> (box (make-array '(4 4))))
>
> ;; fill dice with 0 to 15
> (loop for i from 0 to 15
> do (setf (aref dice i) i))

Expect implementations to change size. Did you not learn from Big Boggle,
or whatever the 5x5 one is? This implementation will not generalize.

(defun shake-boggle-box ()
"Returns an NxN array of ..."
(let* ((n *boggle-box-size*)
(n^2 (* n n))
(dice (make-array n^2))
(box (make-array (list n n))))

;; fill dice ...
(loop for i below n^2

do (setf (aref dice i) i))

...etc. ))

> (defun pprint-boggle-box (box)
> "Pretty print a boggle box as 4 rows or 4 evenly spaced characters."
> (loop for i from 0 to 3 do

constants like 3 here seem ill motivated. You really mean "for i below 4"
and then it'd be more obvious you want for i below *boggle-box-size*.
It's building in constants like this that made fixing the Y2K bug so
painful.

> (princ " ")
> (loop for j from 0 to 3 do
> (princ (aref box i j))
> (if (char-equal (aref box i j) #\Q)
> (princ "u ") ; after "Q" print "u"

Duplicate evaluation of (aref box i j) should be replaced by a variable.

Note you're assuming (by use of char-equal) that the aref will result in
a character. If that's so, you might as well use the more efficient
write-char rather than princ on the previous line.

But you should also abstract it out.

(defun show-die (box i j stream)
(let ((ch (aref box i j)))
(write-char ch stream)
(when (eql ch #\Q)
(write-char #\u stream))))

then call show-die instead of princ. This has other advantages.

> (defun score-word (word box)
> "Calculate the score of the word for the given boggle box."
> (cond ((< (length word) 3)
> (values 0 :Too-Small))
> ((valid-word-p word box)
> (values (max 1 (- (length word) 3)) :OK))
> (t
> (values 0 :Not-Found))))

I'd say you shouldn't compute (length word) more than once. Put it in a
variable on first use in case you awnt to refer to it again as in the
second clause.

> (defun valid-word-from-p (word box x y already-used)
> "Recursively try to find word in box starting at location x, y. Keep
> track to make sure each location is only used once."
> (let ((first (elt word 0)) ; first letter of word

I'm not much of a fan of ELT because it has to always do a runtime
check to see if it's got a list or a sequence. If you know you've got
one or the other (and I think you do), use NTH or AREF. Also, I'm
ESPECIALLY not a fan of ELT because it encourages people to pass lists
in places where you will be doing indexed references, which can turn
an O(1) situation into an O(n) situation without intending to.

> (rest (subseq word 1)) ; rest of word
> (index (+ x (* 4 y))) ; unique index of current die

There's that wired number 4. Symbolic constants.

> ;; if on a "Q" and it is followed by "u" in word, skip searching
> ;; for the "u" since it is included on the "Q" die.
> (when (and (char-equal #\Q first)
> (char-equal #\u (elt rest 0)))
> (setq rest (subseq rest 1)))

Funny, now I'll have to go check my set. Is there a "U" in boggle? Can it
be used after a Qu? Hmm... It's sad if it can't.

In any case, this kind of stuff is not very general. I'd make it table
driven. I bet there are other letter combinations in other languages that
are problematic like Qu in English and that require this same treatment.
Don't make it necessary to recompile your program to accomodate
internationalization.

> ;; if there is no more left to the word, we found it! return t
> (when (= (length rest) 0)

Doing NULL is better here if you have a list. The reason is that if you
give a 10-length list to LENGTH, it will take it ten steps to get the number
10 that it will only use for comparing to zero. Then the next time it will
take 9 steps. Then 8. So to traverse a 10-length list, you'll do
10+9+8... or approximately n^2/2 steps rather than n steps, that is
O(n^2) rather than O(n) to do this final test.

None of my comments address anything to do with the algorithmic structure
of your stuff--I'm just commenting on the superficial style.

[Chris Riesbeck]

Some general programming style points, that aren't
that specific to Lisp... but I want to say that this
code was more readable than 90% of what my students
give me the first time.

In article <m1lelw0...@au-bon-pain.lcs.mit.edu>,

ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) wrote:

>I am interested in feedback about my Common Lisp style with this code.

>(defun shake-boggle-box ()

> "Return a 4x4 array of characters representing a shaken boggle box."
> (let ((dice (make-array 16))
> (box (make-array '(4 4))))
>
> ;; fill dice with 0 to 15
> (loop for i from 0 to 15
> do (setf (aref dice i) i))
>
> ;; shuffle the dice, so we can't choose same one twice
> (loop for i from 0 upto 15
> for rand = (random 16) do
> (psetf (aref dice i) (aref dice rand)
> (aref dice rand) (aref dice i)))
>
> ;; fill the box with the dice, choosing a random side for each
> (loop for i from 0 to 15 do
> (setf (row-major-aref box i)
> (aref +boggle-dice+ (aref dice i) (random 6))))
>
> box))

Break long functions into smaller ones. Let function names
do your documentation for you, and localize variable scope
as much as possible. Minimize sequences of side effects
like assignment.

General rule of thumb: if it needs an inline comment,
it should be a function call.

And pass more parameters!

(defun shake-boggle-box (rows cols dice-max)
(make-shuffled-box rows cols
(make-dice-set (* rows cols) dice-max)))

(defun make-shuffled-box (rows cols dice-set)
...)

(defun make-dice-set (num-dice max-value)
...)

valid-word-from-p being even longer, is more of a challenge
and more in need of restructuring, preferrably into a
simple combination of AND's and OR's.

More on that tomorrow, if someone doesn't beat me to it.

[Duane Rettig]

Kent M Pitman <pit...@world.std.com> writes:

> This is what really started early on putting me off to using AND as a
> general-purpose conditional, even though it was heavily done by other
> AI lab people (including numerous of the LispM designers).

I view the AND clause as a loose contraction for WHEN or IF - for example,
"When the food is ready and I'm hungry I'll get the food" can either be
stated as

(when (and (ready food)
(hungry me))
(get food))

or

(and (ready food)
(hungry me)
(get food))

It is most useful, though, for its step-wise termination capability; if any
of the individual steps fail, the rest of the procedure is ignored. Thus it
is also a contraction for "If doing step1 succeeds, then if doing step2
succeeds, then if doing step3 succeeds ...")

> You'd see
> these (NOT (TERPRI))'s and you'd say "Geez, what is the programmer thinking?
> Putting NOT around that isn't going to keep it from TERPRI'ing."
> I could *almost* understand it being used in this case:
>
> (AND FOO BAR) ;gee, i wonder why it's not working
>
> gets edited to:
>
> (AND (PRINT 'FOO) (PRINT FOO) (NOT (TERPRI)) ;debugging info - remove later
> FOO
> (PRINT 'BAR) (PRINT BAR) (NOT (TERPRI)) ;debugging info - remove later
> BAR)
>
> but even then it was just an accident waiting to happen if you didn't
> remember to complement the return value of TERPRI.

Terpri's return value is not of concern in an AND situation; it is a
clause one would always want to "succeed". Thus, I use an "oh, by the way"
clause, (PROGN ... T) and I would have written the above as

(AND (PROGN (PRINT 'FOO) (PRINT FOO) (TERPRI) T) ;debugging info - remove later
FOO
(PROGN (PRINT 'BAR) (PRINT BAR) (TERPRI) T) ;debugging info - remove later
BAR)

> Hmm. :( I'm so anal about this kind of stuff [...]

I don't think it's ever anal to be careful about how you communicate to
other programmers your intent. Programming is not telling a computer
what to do; any more than it is telling other programmers what you
told the computer to do.

--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 du...@Franz.COM (internet)

[Kent M Pitman]

Duane Rettig <du...@franz.com> writes:

> Kent M Pitman <pit...@world.std.com> writes:
>
> > This is what really started early on putting me off to using AND as a
> > general-purpose conditional, even though it was heavily done by other
> > AI lab people (including numerous of the LispM designers).
>
> I view the AND clause as a loose contraction for WHEN or IF - for example,
> "When the food is ready and I'm hungry I'll get the food" can either be
> stated as
>
> (when (and (ready food)
> (hungry me))
> (get food))
>
> or
>
> (and (ready food)
> (hungry me)
> (get food))
>
> It is most useful, though, for its step-wise termination capability; if any
> of the individual steps fail, the rest of the procedure is ignored. Thus it
> is also a contraction for "If doing step1 succeeds, then if doing step2
> succeeds, then if doing step3 succeeds ...")

Stylistically, I just don't buy this. It's the wrong level of abstraction.
I'd have no trouble with
(defmacro trying (&body forms) `(and ,@forms))
though.

> Terpri's return value is not of concern in an AND situation; it is a
> clause one would always want to "succeed". Thus, I use an "oh, by the way"
> clause, (PROGN ... T) and I would have written the above as
>
> (AND (PROGN (PRINT 'FOO) (PRINT FOO) (TERPRI) T) ;debugging info - remove later
> FOO
> (PROGN (PRINT 'BAR) (PRINT BAR) (TERPRI) T) ;debugging info - remove later
> BAR)

I agree this is better, though here something to remind you that it's a
debugging form would be nice. I often find myself wishing there were a
debug-print which was like print but that warned you when you compiled
it that it was still in the code...

> > Hmm. :( I'm so anal about this kind of stuff [...]
>
> I don't think it's ever anal to be careful about how you communicate to
> other programmers your intent. Programming is not telling a computer
> what to do; any more than it is telling other programmers what you
> told the computer to do.

We're definitely in agrement here.

[Lieven Marchand]

Kent M Pitman <pit...@world.std.com> writes:

> > What about something like
> >
> > (AND (ODDP X) (LIST X))
>
> Geez, I *hate* that use of AND. In my Revised Maclisp Manual, I had a
> published style rule acknowledging this was sometimes done, but saying
> it was questionable. I do think the analagous OR is ok, but mostly
> because it reads well in English while the AND is not meaningful in
> english. One never says "I'll go get the food is ready and the food."
> However, one does say "I'll go get the food or the drink." so I don't
> mind (or food drink) for non-boolean value, where I do mind (and x y)
> for non-boolean value.

Think of it as a simplified form of the anaphoric and I'm quite fond
of.

(AAND (READY *FOOD*) (COOK IT) (SERVE IT))

which translates nicely into English.

--
Lieven Marchand <m...@wyrd.be>
Glaðr ok reifr skyli gumna hverr, unz sinn bíðr bana.

[Jason S. Cornez]

Kent M Pitman <pit...@world.std.com> writes:

> ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) writes:
>

> > The latest incarnation follows.
>
> About the only thing I have to say at this point is that the code looks
> very unabstract in all its accesses to specific representations. I sort
> of doubt that if I were playing with it, I'd want multi-d arrays.
> I'd hide a lot of the open calls to aref, array-dimension, and make-array
> behind abstractions so that the code that is doing the "business" part
> of boggle isn't doing lisp data allocation.

OK, this program now demonstrates my first experience with CLOS. While
I understand that methods do not belong to classes (like in Java, etc.),
it seems somewhat arbitrary as to what should be a method and what a
function in some cases (like get-neighbors). I guess this goes back to
my original question about style.

Thanks again for the suggestions. I agree with the direction that has
been suggested for my program which follows. Obviously I've been
motivated enough to follow up, but I should note that this goal of this
program was to learn LOOP and some issues like abstraction were
intentionally avoided. Now, other than leaving "word" as a string,
everything else is more abstract, and yes, even better.

-Jason

;;; boggle.lisp
;;; Copyright 2001, Jason Cornez
;;; Everyone is freely given the right to do anything with this code.
;;; This is not guaranteed to do anything.

;;; If somehow you find this useful and copy it, I appreciate you
;;; giving credit, but doing so is not required, just polite.

;;;
;;; Description:
;;; Boggle is a game whose physical incarnation consists of 16 dice
;;; containg letters on each side. "Qu" is shown together on a single
;;; side. The boggle box is shaken so that the dice become randomly
;;; arranged in a 4 x 4 grid. The object is to find as many words as
;;; possible starting with any letter and choosing consecutive letters
;;; such that they are adjacent in any direction to the preceeding
;;; letter. In addition, each die may only be used once per word.
;;; There is a three minute timer. Scoring is one point for 3 or 4
;;; letter words and an additional point for each additional letter in
;;; longer words. "Qu" is counted as 2 letters, even though it is on
;;; a single die.
;;;
;;; Status:
;;; So far the game has no real user interface, no timer, and no way
;;; for more than one player to interact (since there is no
;;; interface). What does exist are the boggle dice and the ability
;;; to shake a box, to pretty-print the box, and then to validate and
;;; score words against the box. Ultimately, the above listed missing
;;; components should be added and perhaps also a check for words in
;;; some dictionary. This was written for fun as an exercise, so none
;;; of those are high priorities.

(in-package "CL-USER")

(defvar *boggle-box-size* 4)
(defvar *sides-per-die* 6)
(defvar *min-word-size* 3)
(defvar *first-letter-in-alphabet* #\A)
(defvar *letters-in-alphabet* 26)
(defvar *helper-letters* '((#\Q . #\u))
"Alist containing entries of the form (LETTER . helper)")

;; A class representing a single die (from a set of dice)
(defclass die ()
((sides :reader sides :initarg :sides :type string)))

(defmethod roll ((die die))
(aref (sides die) (random *sides-per-die*)))

(defun create-die (&optional (side-count *sides-per-die*))
(let ((sides (make-array side-count
:element-type 'base-char :fill-pointer 0)))
(with-output-to-string (s sides)
(loop for i below side-count do
(write-char (code-char (+ (char-code *first-letter-in-alphabet*)
(random *letters-in-alphabet*))) s)))
(make-instance 'die :sides sides)))

;; A class representing a set of dice
(defclass dice-set ()
((size :reader size :initform 16 :initarg :size)
(how-many :accessor how-many :initform 0)
(dice :accessor dice)))

(defmethod initialize ((set dice-set))
(setf (dice set) (make-array (size set)))
(setf (how-many set) 0)
set)

(defun create-dice-set (size)
(let ((dice-set (make-instance 'dice-set :size size)))
(initialize dice-set)))

(defmethod add-die ((set dice-set) (die die))
(cond ((< (how-many set) (size set))
(setf (aref (dice set) (how-many set)) die)
(incf (how-many set)))
(t (error "Dice set is full."))))

(defmethod shuffle ((set dice-set))
"Shuffle the dice so each occurs once, and be try to be fair."
(with-slots ((dice dice) (size size)) set
(loop for i from (1- size) downto 1 do
(rotatef (aref dice i) (aref dice (random (1+ i))))))
set)

(defmethod get-die ((set dice-set) i)
(aref (dice set) i))

;; A class representing an n x n box containing some configuration of
;; a boggle dice-set
(defclass boggle-box ()
((size :reader size :initform 4 :initarg :size)
(capacity :accessor capacity)
(box :accessor box)))

(defmethod initialize ((box boggle-box))
(let ((n (size box)))
(setf (box box) (make-array (list n n) :element-type 'base-char))
(setf (capacity box) (* n n)))
box)

(defun create-boggle-box (&optional (size 4))
(let ((box (make-instance 'boggle-box :size size)))
(initialize box)))

(defmethod random-fill ((box boggle-box) (set dice-set))
"Fill the box with the dice, choosing a random side for each."
(loop for i below (capacity box) do
(setf (row-major-aref (box box) i)
(roll (get-die set i))))
box)

(defmethod get-letter ((box boggle-box) i j)
(aref (box box) i j))

(defmethod index ((box boggle-box) i j)
(+ i (* (size box) j)))

(defmethod get-neighbors ((box boggle-box) x y)
"Compute list of neighbors for position (x y) of box.
Wrapping around edges not allowed."
(let ((n (size box)))
(loop
with min-x = (max 0 (1- x))
with max-x = (min (1- n) (1+ x))
with min-y = (max 0 (1- y))
with max-y = (min (1- n) (1+ y))
for i from min-x to max-x nconc
(loop for j from min-y to max-y

unless (and (= i x) (= j y))

collect (list i j)))))

;; The 16 standard boggle dice
;; In general, it would be nice to generate the dice, but here, I've
;; actually just written down the letters found on physical Boggle
;; dice I own, not knowing what algorithm was used to generate them.
(defconstant +boggle-dice+
(let ((dice-set (create-dice-set 16))
(standard-set '("TYELRT" "NHNLRZ" "EGNWHE" "UNHIMQ"
"DRYVLE" "KSFFAP" "JBOOBA" "XIDREL"
"STITYD" "OTWOTA" "OSCAHP" "EEGNAA"
"TMIOUC" "SOISTE" "WRETHV" "UIENES")))
(loop for die in standard-set do
(add-die dice-set (make-instance 'die :sides die)))
dice-set))

;; While the standard boggle dice above were probably designed to
;; produce good boggle games by having an intentionally less-than-
;; random distribution of letters, the dice set produced by this
;; function is entirely (pseudo) random. In fact, some letters may
;; not be present at all...
(defun make-boggle-dice-set (count)
"Generate a new boggle dice set with any number of dice."
(let ((dice-set (create-dice-set count)))
(loop repeat count do
(add-die dice-set (create-die)))
dice-set))

(defmethod shake-boggle-box ((box boggle-box) (dice-set dice-set))
"Return box full of scrambled dice from dice-set."
(let ((n (size box)))
(when (< (size dice-set) (capacity box))
(error "Not enough dice to fill a ~S x ~S box." n n)))

(random-fill box (shuffle dice-set)))

(defun pprint-boggle-box (box &optional (stream *standard-output*))
"Pretty print a boggle box as n rows of n evenly spaced characters."
(loop
with n = (size box)
for i below n do
(write-char #\space stream)
(loop for j below n do
(show-die box i j stream)
(write-char #\space stream))
(fresh-line)))

;; function inspired by comments from Kent Pitman
(defun helper-letter (letter &optional following)
"Return the helper letter associated with letter or #\Space
if the letter has no helper. If following is provided,
return false iff following doesn't match the helper."
(let* ((u_letter (char-upcase letter))
(assoc (assoc u_letter *helper-letters*))
(helper (if assoc (cdr assoc) #\space)))

(unless (and following (char/= (char-downcase following) helper))
helper)))

;; The following function based on a suggestion by Kent Pitman

(defun show-die (box i j stream)

(let* ((letter (get-letter box i j))
(helper (helper-letter letter)))
(write-char letter stream)
(write-char helper stream)))

(defun score-word (word box)
"Calculate the score of the word for the given boggle box."

(let ((word-length (length word)))
(cond ((< word-length *min-word-size*)

(values 0 :Too-Small))
((valid-word-p word box)

(values (max 1 (- word-length *min-word-size*)) :OK))
(t
(values 0 :Not-Found)))))

(defun valid-word-p (word box)
"Return true if the word exists in the boggle box."

(loop
with n = (size box)
for i below n thereis
(loop for j below n thereis
(valid-word-from-p word box i j))))

;; inspired by comments from Chris Riesbeck
(defun rest-of (word)
"Strip first letter and helper letter from word and return the rest."
(if (and (> (length word) 1) (helper-letter (aref word 0) (aref word 1)))
(subseq word 2)
(subseq word 1)))

(defun valid-word-from-p (word box x y &optional (already-used '()))
"Recursively try to find word in box starting at location (x y).

Keep track to make sure each location is only used once."

(let* ((first (aref word 0)) ; first letter of word
(rest (rest-of word))
(remaining (length rest))
(index (index box x y)))

(cond

;; if the die has been used or its letter doesn't match, return nil

((or (member index already-used)
(char-not-equal first (get-letter box x y))) nil)

;; if there is no more left to the word, we found it! return t

((= remaining 0) t)

;; Otherwise, for each neighbor, test the rest of the word

;; remembering where we've been. exit immediately upon success

(t (loop for (i j) in (get-neighbors box x y) thereis
(valid-word-from-p rest box i j (cons index already-used)))))))

[Joe Marshall]

ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) writes:

> ;; A class representing a set of dice
> (defclass dice-set ()
> ((size :reader size :initform 16 :initarg :size)
> (how-many :accessor how-many :initform 0)
> (dice :accessor dice)))
>
> (defmethod initialize ((set dice-set))
> (setf (dice set) (make-array (size set)))
> (setf (how-many set) 0)
> set)
>
> (defun create-dice-set (size)
> (let ((dice-set (make-instance 'dice-set :size size)))
> (initialize dice-set)))

I'm a little uncomfortable with having a special `create' function
that is different from the function that instantiates the object.
It is just too tempting to call (make-instance 'dice-set) directly and
end up with an invalid object.

Of course, optimizing my comfort is probably not a consideration.

-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----

[Chris Riesbeck]

In article <sfwy9u5...@world.std.com>, Kent M Pitman
<pit...@world.std.com> wrote:

>Duane Rettig <du...@franz.com> writes:
>>
>> I don't think it's ever anal to be careful about how you communicate to
>> other programmers your intent. Programming is not telling a computer
>> what to do; any more than it is telling other programmers what you
>> told the computer to do.
>
>We're definitely in agrement here

Could someone rephrase for me what Duane said here? From
the first sentence, I would've thought the next sentence
would be "Programming is not just telling a computer what to
do, it's also telling other programmers what you told it to do."

But I parse both of the above clauses as saying the exact opposite.

[Jason S. Cornez]

Joe Marshall <j...@content-integrity.com> writes:

>
> I'm a little uncomfortable with having a special `create' function
> that is different from the function that instantiates the object.
> It is just too tempting to call (make-instance 'dice-set) directly and
> end up with an invalid object.
>
> Of course, optimizing my comfort is probably not a consideration.
>

I don't disagree with you one bit. How do I go about constructing the
object so that it automatically gets initialized? I don't know much
about CLOS. Can I specify a constructor?

-Jason

[Duane Rettig]

Chris Riesbeck <ries...@ils.nwu.edu> writes:

Well, I should have left off the semicolon (I guess it's a nasty
habit from lanuguages past :-).

In the interest of communicating intent, (although not with any
intention of being precise), I will rephrase what I said loosely
in the form of pseudo-lisp:

(not (> (match-definition (setq it 'programming)
(tell computer what-to-do))
(match-definition it
(tell programmers
(tell computer what-to-do)))))

[Tim Bradshaw]

Chris Riesbeck <ries...@ils.nwu.edu> writes:

>
> Break long functions into smaller ones. Let function names
> do your documentation for you, and localize variable scope
> as much as possible. Minimize sequences of side effects
> like assignment.
>

I don't want to start a huge war over what is obviously sensible
advice in general, but I kind of disagree with this in the case here.

Partly I don't think the function was really that long, but also I
think that if you are writing very short global functions which are
only ever being called from one place then it's a sign of something a
bit wrong, and I think your proposed split was an example of that.
Every function like that is an invitation for someone else to start
calling it which then means you can't change it so easily, and so on.

What I tend to do, if I do have things that would be nice as
functions, is to use FLET / LABELS inside a bigger function, which
gives you the abstraction, but avoids the globaness.

Of course this is all very much a matter of opinion, and virtually any
position is not defensible when pushed even slightly too far (mine
probably being less defensible than most). I guess, really I just
have a feeling that the original function was OK and this split-up
function is just a little bit too split-up. On the other hand, like
you said, the code is a lot better than a lot of beginner code, and if
it was given to me (either version) in a course I was teaching I'd be
quite pleased.

--tim

[Kent M Pitman]

Erik Naggum <er...@naggum.net> writes:

> * Chris Riesbeck <ries...@ils.nwu.edu>

> > Break long functions into smaller ones. Let function names do your
> > documentation for you, and localize variable scope as much as possible.
> > Minimize sequences of side effects like assignment.
>

> These are all good advice for Scheme, but not for Common Lisp.

>
> > General rule of thumb: if it needs an inline comment, it should be a
> > function call.
>

> Again, this is good in Scheme, but not in Comon Lisp.

I'm a bit middling between Tim's advice (which appears to agree with yours,
Erik) and Chris's advice. I sort of think either of these rules of thumb
is equally good and that this is mostly personal taste. I think in situations
like this it's good for people to hear conflicting ideas on this as a guard
against becoming dogmatic--they should be forced merely to think hard about
what to do and why.

In the spirit of that, could you maybe expand on why you think these rules
are or should be different for Scheme vs CL? I don't see this particular
issue splitting on language lines. I don't know if I would have said this
particular function was too long, for example, but I mostly agree with
Chris's stated rules about letting function calls replace comments, etc.

Anyway, the "why" is more important to me than the "what" here, so without
being contentious I'd just love to hear some reasons...

[Chris Riesbeck]

In article <nkj7l1r...@tfeb.org>, Tim Bradshaw <t...@tfeb.org>
wrote:

>Chris Riesbeck <ries...@ils.nwu.edu> writes:
>
>>
>> Break long functions into smaller ones. Let function names
>> do your documentation for you, and localize variable scope
>> as much as possible. Minimize sequences of side effects
>> like assignment.
>

>Partly I don't think the function was really that long, but also I
>think that if you are writing very short global functions which are
>only ever being called from one place then it's a sign of something a
>bit wrong, and I think your proposed split was an example of that.
>Every function like that is an invitation for someone else to start
>calling it which then means you can't change it so easily, and so on.

Definitely a concern, but that's what namespaces -- and
in many languages -- classes are for. To organize related
functions into separate clusters with controlled export.

The big problem in code is maintenance, and the big problem
in maintenance is figuring out what code is doing what.

Small functions support maintenance several ways:

- hooks for tracing
- centralized responsibility
- limited variable sharing
- documentation via their names and arguments
- easy scanning of code (the "short attention span"
reader)

I've not found a better alternative to functions.
Comments don't work for all kinds of reasons.

>What I tend to do, if I do have things that would be nice as
>functions, is to use FLET / LABELS inside a bigger function, which
>gives you the abstraction, but avoids the globaness.

I used to use local functions a lot, in Lisp and Pascal, but
no more. You lose traceability and easily skimmed function
bodies.

>I guess, really I just
>have a feeling that the original function was OK and this split-up
>function is just a little bit too split-up. On the other hand, like
>you said, the code is a lot better than a lot of beginner code, and if
>it was given to me (either version) in a course I was teaching I'd be
>quite pleased.

Full agreement here. That function looked fine to me too.
In an XP shop, it wouldn't be smelly enough to need refactoring.

BUT many people would think it had to be as long as it
was, and that's not true either. What I showed was how
I would've naturally structured the code, separating out
the two tasks of "generating N random dice" and "put N
things randomly in a box," which not only shortened the
code in any one function, but made it easy to see how
various parameters fit together.

[Chris Riesbeck]

In article <31936494...@naggum.net>, Erik Naggum <er...@naggum.net>
wrote:

>* Chris Riesbeck <ries...@ils.nwu.edu>

>> Break long functions into smaller ones. Let function names do your
>> documentation for you, and localize variable scope as much as possible.
>> Minimize sequences of side effects like assignment.
>

> These are all good advice for Scheme, but not for Common Lisp.

I'm not a Scheme programmer, I'm a Common Lisp programmer.

The above is based on 30 years of Lisp programming, and
a decade helping dozens of Lisp application developers
debug or maintain large Macintosh Common Lisp applications.

It's not based on some notion of functional purity,
or trying to support complex reasoning about programs.
It's about supporting long-term maintenance and extension.

Exactly what about "shuffle the box" as "randomly arrange a m x n
box of randomized dice," i.e.,

(defun shake-boggle-box (rows cols dice-max)
(make-shuffled-box rows cols
(make-dice-set (* rows cols) dice-max)))

do you find not Common Lisp, or reasonable here?

>> General rule of thumb: if it needs an inline comment, it should be a
>> function call.
>

> Again, this is good in Scheme, but not in Comon Lisp.

Disagree here too. It's not even a Scheme rule. It
applies in Java, C, and C++.

[Larry Kramer]

Erik Naggum wrote:
>
> * Chris Riesbeck <ries...@ils.nwu.edu>

> > Break long functions into smaller ones. Let function names do your
> > documentation for you, and localize variable scope as much as possible.
> > Minimize sequences of side effects like assignment.
>

> These are all good advice for Scheme, but not for Common Lisp.
>

> > General rule of thumb: if it needs an inline comment, it should be a
> > function call.
>

> Again, this is good in Scheme, but not in Comon Lisp.

I'm going to have to come down on Chris' side on this one, and I've
never programmed in Scheme, only in Common Lisp (and other pre Common
Lisp dialects).

First of all let me say that I agree with Kent's comments that
the function should be better parameterized, but just taking
shake-boggle-box as it stands it could be better written as:

(defun shake-boggle-box ()
"Return a 4x4 array of characters representing a shaken boggle box."
(let ((dice (make-array 16))
(box (make-array '(4 4))))

(initialize-dice dice)
(shuffle-dice dice)
(fill-box box dice)
box))

As someone who has had to maintain large Common Lisp programs I
feel very strongly about this. It is much easier to maintain
code (even if it's ones own code) if each "thought" is abstracted
as a separate function. Just glancing at shake-boggle-box, above,
I know exactly what's going on. The dice are being
initialized, they're being shuffled, and the box is being filled
from the dice.

Now, if shake-boggle-box is not working correctly somehow, and
I suspect it has to do with the initialization of the dice,
I need only drill down further and see what's going on in
initialize-dice. Until proven otherwise, I don't even need to
worry about how shuffle-dice and fill-box work.

My argument would be stronger if the called functions above
returned meaningful results (although I'm not saying they
necessarily should), as then it would be possible to simply
trace them, check the inputs and outputs, and get a good
idea as to whether they're behaving according to design.

One of the main benefits of well-written Lisp code is that
it reads like English, thus obviating the need for wordy
comments.

Larry

[Erik Naggum]

* Chris Riesbeck <ries...@ils.nwu.edu>

> Break long functions into smaller ones. Let function names do your
> documentation for you, and localize variable scope as much as possible.
> Minimize sequences of side effects like assignment.

These are all good advice for Scheme, but not for Common Lisp.

> General rule of thumb: if it needs an inline comment, it should be a
> function call.

Again, this is good in Scheme, but not in Comon Lisp.

#;Erik
--
"Hope is contagious" -- American Cancer Society
"Despair is more contagious" -- British Farmers Society

[Kent M Pitman]

Chris Riesbeck <ries...@ils.nwu.edu> writes:

>
> In article <sfwzoem...@world.std.com>, Kent M Pitman

> <pit...@world.std.com> wrote:
>
> >Chris Riesbeck <ries...@ils.nwu.edu> writes:
> >

> >> (defun valid-word-from-p (word box x y &optional already-used)
> >
> >IMO, stylistically, this should be
> >
> >(defun valid-word-from-p (word box x y &optional (already-used '()))
> >
> >since already-used defaults to nil, not to ().
> >[That these two are eq is just incidental. :-]
>
> I could be talked into this but isn't it a bit Scheme-ish to
> distinguish nil and '()?

Ohmigod! I've been accused of behaving in a Scheme-like way. Must change
behavior instantly. Can't bear stigma! ... :-)

Actually, it's the influence of my on-and-off colleague over the years,
Jonathan Rees, that I make this distinction, so probably there really is
some Scheme influence there. But on the other hand, my concern is not at
all to prepare for these being distinct quantities--rather to document
explicitly for other readers of my program whether I intend to do listy
things to the NIL, in which case I use '(), or whether I intend to do
boolean things, in which case I use NIL, or whether I intend to do symbolic
things, in which case I use 'NIL.

> Certainly you should never swap uses of NOT and NULL,

Funny that I'm a touch more forgiving on that in practice, though in
principle I agree with you.

> but NIL as both false and the
> empty list and the "usual suspect" for a default hasn't
> been something I've been telling my students to keep
> separate. Should I?

I think so. It's certainly consistent with telling them that NOT vs NULL
matters.

I think the other thing that guides my distaste for this is the use of
(DEFUN FOO NIL ...) or (PROG NIL ....) or (LET NIL ...). Those feel
structurally wrong to me, though obviously they are representationally
correct. I strongly prefer (DEFUN FOO () ...), (PROG () ...) and
(LET () ...). And I think it's consistent to make this distinction in
regards to evaluable NILs.

[Tim Bradshaw]

* Chris Riesbeck wrote:
> In article <nkj7l1r...@tfeb.org>, Tim Bradshaw <t...@tfeb.org>
> wrote:

> Definitely a concern, but that's what namespaces -- and
> in many languages -- classes are for. To organize related
> functions into separate clusters with controlled export.

I've always thought that a function with a bunch of smaller, local
functions inside is really quite close to some of the things that
methods-in-classes languages do with class definitions -- it defines a
little bit of functionality which is incredibly private.

--tim

[Chris Riesbeck]

In article <sfwzoem...@world.std.com>, Kent M Pitman
<pit...@world.std.com> wrote:

>Chris Riesbeck <ries...@ils.nwu.edu> writes:
>
>> (defun valid-word-from-p (word box x y &optional already-used)
>
>IMO, stylistically, this should be
>
>(defun valid-word-from-p (word box x y &optional (already-used '()))
>
>since already-used defaults to nil, not to ().
>[That these two are eq is just incidental. :-]

I could be talked into this but isn't it a bit Scheme-ish to

distinguish nil and '()? Certainly you should never
swap uses of NOT and NULL, but NIL as both false and the

[Duane Rettig]

Chris Riesbeck <ries...@ils.nwu.edu> writes:

> In article <nkj7l1r...@tfeb.org>, Tim Bradshaw <t...@tfeb.org>
> wrote:
>
> >What I tend to do, if I do have things that would be nice as
> >functions, is to use FLET / LABELS inside a bigger function, which
> >gives you the abstraction, but avoids the globaness.
>
> I used to use local functions a lot, in Lisp and Pascal, but
> no more. You lose traceability and easily skimmed function
> bodies.

For tracability, it depends upon what the implementation you are
using offers:

CL-USER(1): (compile (defun foo (a)
(flet ((bar (x y) (+ x y)))
(bar a 10))))
FOO
NIL
NIL
CL-USER(2): (trace ((flet foo bar)))
((FLET FOO BAR))
CL-USER(3): (foo 40)
0: ((FLET FOO BAR) 40 10)
0: returned 50
50
CL-USER(4): (fdefinition '(flet foo bar))
#<Function (FLET FOO BAR)>
CL-USER(5):

[Ray Blaak]

Erik Naggum <er...@naggum.net> writes:

> * Chris Riesbeck <ries...@ils.nwu.edu>
> > Break long functions into smaller ones. Let function names do your
> > documentation for you, and localize variable scope as much as possible.
> > Minimize sequences of side effects like assignment.
>
> These are all good advice for Scheme, but not for Common Lisp.

Do you care to explain this assertion?

This is good advice for any language, in my not-so-humble opinion. It
essentially is saying: make the code readable and understandable in its own
right, and minimize surprise and the possibility of unintended consequences.

How could this not be good for CL?

> > General rule of thumb: if it needs an inline comment, it should be a
> > function call.

I would say this depends on the comment, and the complexity/readability of the
code being commented.

--
Cheers, The Rhythm is around me,
The Rhythm has control.
Ray Blaak The Rhythm is inside me,
bl...@infomatch.com The Rhythm has my soul.

[Chris Riesbeck]

In article <m1lelw0...@au-bon-pain.lcs.mit.edu>,
ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) wrote:

>(defun valid-word-p (word box)
> "Return true if the word exists in the boggle box."
> ;; for each die in the box, see if the word can start from there
> ;; exit immediately if the word is found
> (loop for i from 0 to 3 do
> (loop for j from 0 to 3
> when (valid-word-from-p word box i j '()) do
> (return-from valid-word-p t))))

Except for the hard-wired 4x4 box size, this looks fine to
me. You don't need the return-from though, and you should
drop the ;; comment on how the code works, since the code
says that just fine. Also, I'm dropping the explicit '()
for reasons to be seen shortly.

So I get

(defun valid-word-p (word box)
"Return true if the word exists in the boggle box."

(loop for i from 0 to 3 thereis
(loop for j from 0 to 3 thereis

(valid-word-from-p word box i j))))

I have a very different structure though, for the function
called, valid-word-from-p. The logic of that function in
English is very similar to the above -- basically, look
to see if the rest of the word works at some neighbor
of i,j. But code doesn't look like that at all. The logic
is lost in all the checking and variable setting up front. So
turn it around. Put the logic on top. Bury the details
of checking locations and "Qu" in subfunctions.

Using exactly the same algorithm, I get these functions.
valid-word-from-p checks for immediate success or failure,
and defers to a separate search function for the hard part.

(defun valid-word-from-p (word box x y &optional already-used)
(and (not (member (get-index x y) already-used))
(char-equal (aref box x y) (char word 0))
(or (= (length word) 1)
(find-neighbor-p (advance word) box x y
(cons (get-index x y) already-used)))))

find-neighbor-p is the searcher, and looks very much like your
valid-word-p. I got rid of the loop building the list of locations,
which both shortens the code and reduces consing. And I
used thereis again instead of return-from.

(defun find-neighbor-p (word box x y already-used)
(loop for i from (max 0 (1- x)) to (min 3 (1+ x)) thereis
(loop for j from (max 0 (1- y)) to (min 3 (1+ y)) thereis
(and (or (/= i x) (/= j y))
(valid-word-from-p word box i j already-used)))))

Finally, functions do the grungy bits, e.g., turning x,y into
some integer index and advancing to the next letter.

(defun get-index (x y)

(+ x (* 4 y)))

(defun advance (word)
(if (and (char-equal #\Q (char word 0))
(> (length word) 1)
(char-equal #\u (char word 1)))

(subseq word 2)
(subseq word 1)))

Kent's comments apply here about hard-wiring Qu in.
If the dice can hold more than one letter, why not use
strings for them to begin with, and write 2 general functions,
(match word die) and (advance word die) to capture the
matching and advancing logic.

For comparison, here's the original valid-word-from-p.

[Kent M Pitman]

Chris Riesbeck <ries...@ils.nwu.edu> writes:

> (defun valid-word-from-p (word box x y &optional already-used)

IMO, stylistically, this should be

(defun valid-word-from-p (word box x y &optional (already-used '()))

since already-used defaults to nil, not to ().
[That these two are eq is just incidental. :-]

In truth, I usually even put an explicit init like:

&optional (foo nil)

when I plan to use FOO without discriminating between its initialized
and uninitialized [null] value. I write instead

&optional foo

when the argument has an expected type such that supplying nil or not
supplying it means "I didn't pass anything". In this latter case, I
usually have something like

(unless foo (setq foo ...initialization code...))

shortly after to "finish" the initialization part.

[Jorgen 'forcer' Schaefer]

Joe Marshall <j...@content-integrity.com> writes:

> My rule of thumb is to ignore rules of thumbs: it is usually
> better to think about such things then to blindly follow
> general rules.

One of my favorite phrases on programming:

The novice doesn't know the rules, and creates monstrosities.
The practitioner follows the rules, and creates good works.
The master understands when to break the rules, and creates wonders.

Greetings,
-- Jorgen

--
((email . "for...@mindless.com") (www . "http://forcix.cx/")
(irc . "forcer@#StarWars (IRCnet)") (gpg . "1024D/028AF63C"))

[Joe Marshall]

Kent M Pitman <pit...@world.std.com> writes:

> Erik Naggum <er...@naggum.net> writes:
>
> > * Chris Riesbeck <ries...@ils.nwu.edu>
> > > Break long functions into smaller ones. Let function names do your
> > > documentation for you, and localize variable scope as much as possible.
> > > Minimize sequences of side effects like assignment.
> >
> > These are all good advice for Scheme, but not for Common Lisp.
> >
> > > General rule of thumb: if it needs an inline comment, it should be a
> > > function call.
> >
> > Again, this is good in Scheme, but not in Comon Lisp.
>
> I'm a bit middling between Tim's advice (which appears to agree with yours,
> Erik) and Chris's advice. I sort of think either of these rules of thumb
> is equally good and that this is mostly personal taste.

My rule of thumb is to ignore rules of thumbs: it is usually better

to think about such things then to blindly follow general rules.

I wouldn't have the audacity to attempt to speak for Erik, but I'd bet
that the differences between he and Chris are more of degree rather
than kind. Surely Erik is not proposing that smaller functions should
be combined to create larger ones, function names should not reflect
their purpose, variables ought to be global, and assignments used in
preference to binding.

Obviously functions that take up pages and pages of the screen ought
to be broken into smaller units if it makes sense to do so. Obviously
one shouldn't use a global variable if the scope is quite limited.
Scheme hackers are, however, more inclined to break even short
functions into smaller parts, and they tend to treat side effects as
if they were a contagious disease. Common Lisp hackers are less anal
about these things.

[Kent M Pitman]

Ray Blaak <bl...@infomatch.com> writes:

> Erik Naggum <er...@naggum.net> writes:
>
> > * Chris Riesbeck <ries...@ils.nwu.edu>
> > > Break long functions into smaller ones. Let function names do your
> > > documentation for you, and localize variable scope as much as possible.
> > > Minimize sequences of side effects like assignment.
> >
> > These are all good advice for Scheme, but not for Common Lisp.
>
> Do you care to explain this assertion?
>
> This is good advice for any language, in my not-so-humble opinion. It
> essentially is saying: make the code readable and understandable in its own
> right, and minimize surprise and the possibility of unintended consequences.

Might as well super-generalize. In the writing of the ANSI CL spec (which
I hasten to say was never really "completed" but rather was "gotten to a
certain level of quality through successive approximation passes" so may not
illustrate all of my "conclusions" throughout the document), I came upon a
useful theory of how to tell if a paragraph had a purpose or was in the write
place: name every paragraph. In effect (whether it showed up in the final
result or not--in practice, it did, but I don't think that's a necessary
thing), the giving of the name forces one to ask the question "why is this
here?" and the looking at the name forces one to say "does this look right?"
and "is it in the right place?". In effect, I had rediscovered outlining,
just "after the fact". I think, in essence, that function names create a
kind of (hypertexted) outline for a program. And when there is a lot of
unnamed bushiness, it's easy to start doing things that are off-topic or
ill-placed or that violate levels of abstraction (since no abstraction has
been named).

> How could this not be good for CL?
>
> > > General rule of thumb: if it needs an inline comment, it should be a
> > > function call.
>
> I would say this depends on the comment, and the complexity/readability
> of the code being commented.

I wrote (and wrote up, though it's not yet webbed) a hypertext system back
in 1984. I didn't realize it was hypertext until after-the-fact when I did
some research on similar systems and started to piece it all together. In
the process of so doing, I ran across some nice work by Randy Trigg (at
U of Maryland, I think) where he identified various kinds of link types in
documents. Effectively, there are varying kinds of motion poeple do in a
document, both vertical and horizontal. Vertical motion is motion through
an outline--expanding/contracting and up/down. Horizontal motion is
cross-reference information, such as footnotes, and often wants a
different kind of interface than vertical motion, since it typically swaps
you into a different context space rather than moving you locally in a
pre-existing one. I mentio this all because it seems to me that if function
boundaries are hypertext outline points, they correspond to the vertical
motion through a program. And if comments are one-to-one with them, then
one needs to explain why some comments would be retained. Going back to
Randy's work, and reasoning by analogy, I'll guess that comments really
break down into two distinct classes also--those that are "about structure"
(substitutes for function boundaries) and those that are "reference" in
nature (perhaps offering justification links, algorithmic references, etc.)
Those I would say probably don't need function boundaries. But it would
explain why Chris might have a rule that is often productive that says to
look for comments asa possible place to divide functions--because that's
probably one large class of comments.

[Janne Rinta-Manty]

Jason S Cornez 2001-03-14T19:20:25Z:

> I am interested in feedback about my Common Lisp style with this

> code. So far, I am not concerned about performance, but if you feel
> declarations would improve the style, feel free to comment.

Well, this isn't a Lisp style issue, but about the shuffling part of
the program:

> ;; shuffle the dice, so we can't choose same one twice
> (loop for i from 0 upto 15
> for rand = (random 16) do
> (psetf (aref dice i) (aref dice rand)
> (aref dice rand) (aref dice i)))

If you want each permutation to be equally probable, select a die to a
place only once:

(loop for i from 15 downto 1
for rand = (random (1+ i)) do

(psetf (aref dice i) (aref dice rand)
(aref dice rand) (aref dice i)))

--
Janne Rinta-Mänty

[Bernhard Pfahringer]

In article <m2n1ambshn.fsf...@news.helsinki.fi>,

>
>(loop for i from 15 downto 1
> for rand = (random (1+ i)) do
> (psetf (aref dice i) (aref dice rand)
> (aref dice rand) (aref dice i)))
>

I prefer rotatef over psetf were appropriate:

(loop for i from 15 downto 1
for rand = (random (1+ i)) do

(rotatef (aref dice i) (aref dice rand)))

cheers, Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer Dept. of Computer Science, University of Waikato
http://www.cs.waikato.ac.nz/~bernhard +64 7 838 4041
--------------------------------------------------------------------------

[Jason S. Cornez]

Thanks everybody. I've received lots of great feedback. I've
incorporated much of the advice I've received but also made a few
judgment calls. I feel the code shows marked improvement.

The latest incarnation follows.
-Jason

(in-package "CL-USER")

;; The 16 standard boggle dice

;; In general, it would be nice to generate the dice, but here, I've
;; actually just written down the letters found on physical Boggle
;; dice I own, not knowing what algorithm was used to generate them.
(defconstant +boggle-dice+

(make-array '(16 6) :initial-contents

'("TYELRT" "NHNLRZ" "EGNWHE" "UNHIMQ"
"DRYVLE" "KSFFAP" "JBOOBA" "XIDREL"
"STITYD" "OTWOTA" "OSCAHP" "EEGNAA"
"TMIOUC" "SOISTE" "WRETHV" "UIENES")))

;; While the standard boggle dice above were probably designed to

;; produce good boggle games by having an intentionally less-than-
;; random distribution of letters, the dice set produced by this
;; function is entirely (pseudo) random. In fact, some letters may
;; not be present at all...
(defun make-boggle-dice-set (count)
"Generate a new boggle dice set with any number of dice."

(let ((dice-set (make-array (list count *sides-per-die*))))
(loop for die below count do
(loop for side below *sides-per-die* do
(setf (aref dice-set die side)
(code-char (+ (char-code *first-letter-in-alphabet*)
(random *letters-in-alphabet*))))))
dice-set))

(defun shake-boggle-box (n dice-set)
"Return an n x n array of characters representing a shaken boggle box."
(let* ((n^2 (* n n))
(dice (make-array n^2 :initial-contents
(loop for i below n^2 collect i)))
(box (make-array (list n n))))

(when (< (array-dimension dice-set 0) n^2)

(error "Not enough dice to fill a ~S x ~S box." n n))

;; shuffle the dice so each occurs once, and be fair (Janne Rinta-Manty)
(loop for i from (1- n^2) downto 1 do
(rotatef (aref dice i) (aref dice (random (1+ i)))))

;; fill the box with the dice, choosing a random side for each
(loop for i below n^2 do
(setf (row-major-aref box i)
(aref dice-set (aref dice i) (random *sides-per-die*))))

box))

(defun pprint-boggle-box (box &optional (stream *standard-output*))
"Pretty print a boggle box as n rows of n evenly spaced characters."
(loop

with n = (array-dimension box 0)

for i below n do
(write-char #\space stream)
(loop for j below n do
(show-die box i j stream)
(write-char #\space stream))
(fresh-line)))

;; function inspired by comments from Kent Pitman
(defun helper-letter (letter &optional following)
"Return the helper letter associated with letter or #\Space
if the letter has no helper. If following is provided,
return false iff following doesn't match the helper."
(let* ((u_letter (char-upcase letter))

(helper (case u_letter
(#\Q #\u) ; UPCASE downcase (convention)
;; ...add more here...
(otherwise #\space))))

(unless (and following (char/= (char-downcase following) helper))
helper)))

;; The following function based on a suggestion by Kent Pitman
(defun show-die (box i j stream)

(let* ((letter (aref box i j))

(helper (helper-letter letter)))
(write-char letter stream)
(write-char helper stream)))

(defun score-word (word box)
"Calculate the score of the word for the given boggle box."
(let ((word-length (length word)))
(cond ((< word-length *min-word-size*)
(values 0 :Too-Small))
((valid-word-p word box)
(values (max 1 (- word-length *min-word-size*)) :OK))
(t
(values 0 :Not-Found)))))

(defun valid-word-p (word box)

"Return true if the word exists in the boggle box."
(loop

with n = (array-dimension box 0)

for i below n thereis

(loop for j below n thereis

(valid-word-from-p word box i j))))

(defun get-neighbors (x y n)
"Compute list of neighbors for position (x y) in an n x n grid.
Wrapping around edges not allowed."
(loop

with min-x = (max 0 (1- x))
with max-x = (min (1- n) (1+ x))
with min-y = (max 0 (1- y))
with max-y = (min (1- n) (1+ y))
for i from min-x to max-x nconc
(loop for j from min-y to max-y

unless (and (= i x) (= j y))

collect (list i j))))

;; inspired by comments from Chris Riesbeck
(defun rest-of (word)
"Strip first letter and helper letter from word and return the rest."

(if (and (> (length word) 1) (helper-letter (aref word 0) (aref word 1)))

(subseq word 2)
(subseq word 1)))

(defun valid-word-from-p (word box x y &optional (already-used '()))

"Recursively try to find word in box starting at location (x y).

Keep track to make sure each location is only used once."

(let* ((first (aref word 0)) ; first letter of word
(rest (rest-of word)) ; rest of word
(remaining (length rest))
(n (array-dimension box 0)) ; size of box
(index (+ x (* n y)))) ; unique index of current die

(cond

;; if the die has been used or its letter doesn't match, return nil

((or (member index already-used)
(char-not-equal first (aref box x y))) nil)

;; if there is no more left to the word, we found it! return t

((= remaining 0) t)

;; Otherwise, for each neighbor, test the rest of the word

;; remembering where we've been. exit immediately upon success

(t (loop for (i j) in (get-neighbors x y n) thereis

[Dorai Sitaram]

In article <zoenm4...@content-integrity.com>,

I only have a comment about one element in that list of
rules, viz, the advisability of breaking up a long
(global) function into many small (global) ones. I am
surprised to hear that Scheme usage favors breakage and
CL doesn't. I would have thought that if there
was a difference, it would be the other way around.
(Indeed, stereotypical Schemer purity-addiction should
manifest itself as the urge to lexically hide as much
as possible instead of using up global variable names.)

I remember in the Lisp1 v Lisp2 thread, there seemed to
be mutual agreement that Scheme usage favors deeply
nested lexical procedures (eg, because of the use of TR
local procedures for loops, Scheme implementations
_have_ to optimize for local procedures, possibly
leading to dire and industrially unacceptable
pessimization of other areas) and that CL didn't have
this problem. The reason that a CL implementation of
an algorithm didn't suffer relative to the Scheme
implemenation was because the CL style would avoid the
use of nested lexical procedures. Or so seemed the
consensus at the time.

--d

[Chris Riesbeck]

So, as I understand it,

Kent is strict about '() versus NIL
and (DEFUN FOO () ...) vs (DEFUN FOO NIL ...)
less so about NOT vs NULL

I've been strict about NOT vs NULL
and also (DEFUN FOO () ...) vs (DEFUN FOO NIL ...)
but not '() versus NIL

where "strict" means "what I usually do for good reason, but
don't you dare generate a compiler error for violating it."

For me, NOT vs NULL is much more important than NIL
versus '(). I think it's because I place so much stress
on using function names to express code intent. Ditto for
variable names, but less so on the actual constants, e.g.,
I also get less hung up on using 2 vs 2.0 to initialize
a double in C.

What about something like

(AND (ODDP X) (LIST X))

i.e., code meant to return a list of something, possibly empty.
Should it be

(IF (ODDP X) (LIST X) '())

[Kent M Pitman]

Chris Riesbeck <ries...@ils.nwu.edu> writes:

> For me, NOT vs NULL is much more important than NIL
> versus '(). I think it's because I place so much stress
> on using function names to express code intent.

An interesting insight!

This may indeed be a good rule for teaching--always good to know the rules
when you start out to keep you in check. But sometimes I feel a need to
break various rules, and ultimately in dynamically typed language with
lots of generic functions running around, I think knowing the type of
something tells you more than seeing what function is operating on it, so
I do look more to the data itself. The type dictates how much you can pun,
for example; if you know someone did :test '< (for example), you know you
have a symbol you can put properties on or print; but if all you know is
that it's a funcallable, then you're stuck only being able to funcall it.
So in practice, the expert programmer trying to squeeze the last mile out
of his/her code needs to be type-aware, not just function-aware. And
that's why I focus more on the type. But also, separate from the issue
of how to exploit the values, there's the other issue of how to restrict
the use. When I write '(), I'm declaring the set of operations I plan to
do on it. In a separate thread, I just included this definition:

(defun sorted-position (item list &key (less-test #'<) (equal-test #'=))
(loop with prev = nil
for position from 0
for tail on list
for elt = (first tail)
when (or (funcall less-test item elt) (funcall equal-test item elt))
do (return (values position prev))
do (setq prev tail)
finally (return (values position prev))))

In this case, PREV is taking on a false value because it doesn't yet have
a tail. (Like the result of MEMBER when it fails; that result is NIL, not (),
because if the result were a list, it would have a car that was the element
being searched for.) By declaring PREV to be NIL, I'm saying that this
variable will take on, like the return values of MEMBER, "either false or
a cons"; *not* "a list" (which is "either the empty list or a cons").

> Ditto for
> variable names, but less so on the actual constants, e.g.,
> I also get less hung up on using 2 vs 2.0 to initialize
> a double in C.

Hmm. :( I'm so anal about this kind of stuff that I still sometimes have
(and enjoy) the lingering effect of reading Brian Smith's 3lisp PhD, where
he makes a separate data type for numerals from numbers, and you have to
quote numerals, so '3 evaluates to 3. I don't do this for numbers in
math, but I do it for numbers when I'm constructing code. e.g.,
(list '+ '1 a)
or
(defmacro foo (&optional (x '3)) ...)
since these are cases where the number is not being used for numberness
but structureness.

Jonathan Rees and I have had many discussions about proper style on this
kind of thing, and I'm pretty sure he agrees with me on this.

It also sometimes keeps you from getting confused about nesting level
in cases like:
(defmacro foo (&optional (x ''a) (y ''3)) ...)
or so it seems to me.

> What about something like
>
> (AND (ODDP X) (LIST X))
>
> i.e., code meant to return a list of something, possibly empty.
> Should it be
>
> (IF (ODDP X) (LIST X) '())

Geez, I *hate* that use of AND. In my Revised Maclisp Manual, I had a
published style rule acknowledging this was sometimes done, but saying
it was questionable. I do think the analagous OR is ok, but mostly
because it reads well in English while the AND is not meaningful in
english. One never says "I'll go get the food is ready and the food."
However, one does say "I'll go get the food or the drink." so I don't
mind (or food drink) for non-boolean value, where I do mind (and x y)
for non-boolean value.

I definitely also think the IF has the virtue of making you think about
whether you meant () or NIL. I bet you meant NIL, though only the
surrounding code would say for sure. e.g., in a MAPCAN you might have
meant (), since something akin to NCONC will be used on the result,
but in
(LET ((ENTRY (ASSOC 'FOO *MY-ALIST*)))
(AND ENTRY (CDR ENTRY))) ;bad bad bad
it's a lot less clear. Often I'd think this was getting NIL as the
alternative, and
(LET ((ENTRY (ASSOC 'FOO *MY-ALIST*)))
(IF ENTRY (CDR ENTRY) NIL))
would make that clearer. At least it makes you think about it. Once
in a while, you see
(AND X (PRINT X))
and I *really* dislike that. Doing
(IF X (PRINT X))
is better because it shows there is no alternative. Doing
(WHEN X (PRINT X))
is also ok with me since it shows there is a Kripke-like "necessarily true"
claim that not only is there no alternative, but there is little
likelihood there would be any other possible universe. (Usually such
claims are weak, because other universes can be surprising, but I still
find a probabilistic claim of this kind useful.)

Btw, just to gross you out utterly, PRINT in Maclisp used to return T
rather than the argument (for fear the argument was a register-allocated
number, so it wouldn't have to heap-cons it just to return its value),
and for reasons I don't know, but suspect were just poor coordination in
design, TERPRI returned NIL. Anyway, one occasionally saw

(AND (PRINT 'FOO:) ; colon was alphabetic in maclisp
(NOT (TERPRI))
(PRINT FOO-VALUE))

or even worse

(AND (PRINT 'FOO:) ; colon was alphabetic in maclisp
(NOT (TERPRI))
(PRINT FOO-VALUE)
(TERPRI)) ;relies on being last in series and having no value
;consumer outside the AND.

This is what really started early on putting me off to using AND as a
general-purpose conditional, even though it was heavily done by other
AI lab people (including numerous of the LispM designers). You'd see
these (NOT (TERPRI))'s and you'd say "Geez, what is the programmer thinking?
Putting NOT around that isn't going to keep it from TERPRI'ing."
I could *almost* understand it being used in this case:

(AND FOO BAR) ;gee, i wonder why it's not working

gets edited to:

(AND (PRINT 'FOO) (PRINT FOO) (NOT (TERPRI)) ;debugging info - remove later
FOO
(PRINT 'BAR) (PRINT BAR) (NOT (TERPRI)) ;debugging info - remove later
BAR)

but even then it was just an accident waiting to happen if you didn't
remember to complement the return value of TERPRI.

(And don't forget that to debug an OR, you had to flip the values the
other way. (TERPRI) but (NOT (PRINT ...)).)

[Kent M Pitman]

ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) writes:

> Thanks everybody. I've received lots of great feedback. I've
> incorporated much of the advice I've received but also made a few
> judgment calls. I feel the code shows marked improvement.
>
> The latest incarnation follows.

About the only thing I have to say at this point is that the code looks
very unabstract in all its accesses to specific representations. I sort
of doubt that if I were playing with it, I'd want multi-d arrays.
I'd hide a lot of the open calls to aref, array-dimension, and make-array
behind abstractions so that the code that is doing the "business" part
of boggle isn't doing lisp data allocation.

It should be possible for someone who speaks nothing about lisp datatypes
to read the part that explains how the boggle game part works by understanding
only really basic control (like function call, variables, and iteration)
and a set of boggle-accessors. Collecting your constructors and accessors
separately will give a more abstract look to that part of the code, and will
give you greater flexibility to change the representation later if you
need to because the parts that will be affected by the change are isolated
in one place where it's easier to understand the effects of such a change
than merely "the whole program will be affected".

Also, I think both Chris and I noted that your special casing of the
"Qu" should be isolated in some way so that it is "data driven" rather
than "procedurally embedded" (if those term is not meaningful to you,
do ask; those are important concepts in any language, but especially
in Lisp since it allows things to be data driven that cannot be in
other languages, so the issue comes up more often).

I'm not going to try do these change, but will leave it as an exercise
to you if you're interested.

You're right, though, your program does look improved even for as much
as you've done already. But if you have the patience to do another
pass, you may yet be surprised by how much better it can be made. It
is now more robust against certain numeric parametric changes, but
it is still not robust against representational changes. Both kinds of
robustness are important.

[Tim Bradshaw]

* Jason S Cornez wrote:
> I don't disagree with you one bit. How do I go about constructing the
> object so that it automatically gets initialized? I don't know much
> about CLOS. Can I specify a constructor?

Yes, you can, or rather you can define something a bit more useful.
You can define methods (almost always after methods) on
INITIALIZE-INSTANCE. The first argument is the object being
initialized, and the other arguments are all the initargs you gave to
MAKE-INSTANCE. You can specify other keyword args as well.

In the case of an after method (I'm not sure if it is legal to
override the main method), all the initialisations given in the class
definition will have been done, and you can then do any further ones
that might be needed.

Again, if you're defining an after method, the usual CLOS mechanisms
cause all the applicable methods to run in most-specific-last order,
so all the methods on superclasses get a chance to do their thing.

This is kind of a rough description and is probably misleading
invarious places -- you should look at the hyperspec to see what
really happens!

--tim

[Jason Kantz]

ja...@au-bon-pain.lcs.mit.edu (Jason S. Cornez) writes:

> How do I go about constructing the object so that it automatically
> gets initialized?

(defclass dice-set ()
((size :reader size :initform 16 :initarg :size)
(how-many :accessor how-many :initform 0)
(dice :accessor dice)))

(defmethod initialize-instance :after ((dice-set dice-set) &rest initargs)
(setf (dice dice-set) (make-array (size dice-set)))
(setf (how-many dice-set) 0))

[Kent M Pitman]

Jason Kantz <ja...@kantz.com> writes:

Actually, instead of &rest initargs you should just use &key with only the
keys after it you plan to use, or no keys after the &key if you plan to use
none.