idiomatic lisp style, dealing with local variables

[ccc31807]

Okay, I'm now spending about an hour a day writing real lisp, enough so that the non-obvious questions come up. Below, I have copied four variables that I use, two functions, SUM-CDR and GOODNESS-1, and example executions for both players.

It adds up the cdr of each sublist depending on whether the player is 0 (alpha) or 1 (beta) and returns the difference between the number of pebbles possessed by that player and the total number of pebbles.

Question: Even to my unpracticed eye, this looks pretty awful. Any comments for improvements from a style perspective?

As always, thanks, CC.

--------------vars-----------------
(defparameter list-0 '((0 . 3)(1 . 3)(2 . 3)(3 . 3)(4 . 3)(5 . 3)))
(defparameter list-1 '((0 . 4)(1 . 0)(2 . 5)(3 . 0)(4 . 6)(5 . 3)))
(defparameter list-2 '((0 . 0)(1 . 0)(2 . 0)(3 . 6)(4 . 2)(5 . 10)))
(defparameter list-3 '((0 . 5)(1 . 5)(2 . 8)(3 . 0)(4 . 0)(5 . 0)))

-------------funcs-------------------
(defun sum-cdr (lst &optional (sum 0))
(cond
((null lst) sum)
(t
(incf sum (cdar lst))
(sum-cdr (cdr lst) sum))))

(defun goodness-1 (player board)
(let* ((len (length board))
(half (ash len -1))
(total-pebbles (sum-cdr board))
(alpha (subseq board 0 half))
(beta (subseq board half)))
(format t "board: ~a, player ~a~% total-pebbles ~a~%" board player total-pebbles)
(if (zerop player)
(- (sum-cdr alpha) (ash total-pebbles -1))
(- (sum-cdr beta) (ash total-pebbles -1)))))

-------------runs---------------------
; compilation finished in 0:00:00.083
"Compiled and loaded proj-31.lisp"
* (goodness-1 0 list-0)
board: ((0 . 3) (1 . 3) (2 . 3) (3 . 3) (4 . 3) (5 . 3)), player 0
total-pebbles 18
0
* (goodness-1 0 list-1)
board: ((0 . 4) (1 . 0) (2 . 5) (3 . 0) (4 . 6) (5 . 3)), player 0
total-pebbles 18
0
* (goodness-1 0 list-2)
board: ((0 . 0) (1 . 0) (2 . 0) (3 . 6) (4 . 2) (5 . 10)), player 0
total-pebbles 18
-9
* (goodness-1 0 list-3)
board: ((0 . 5) (1 . 5) (2 . 8) (3 . 0) (4 . 0) (5 . 0)), player 0
total-pebbles 18
9
* (goodness-1 1 list-0)
board: ((0 . 3) (1 . 3) (2 . 3) (3 . 3) (4 . 3) (5 . 3)), player 1
total-pebbles 18
0
* (goodness-1 1 list-1)
board: ((0 . 4) (1 . 0) (2 . 5) (3 . 0) (4 . 6) (5 . 3)), player 1
total-pebbles 18
0
* (goodness-1 1 list-2)
board: ((0 . 0) (1 . 0) (2 . 0) (3 . 6) (4 . 2) (5 . 10)), player 1
total-pebbles 18
9
* (goodness-1 1 list-3)
board: ((0 . 5) (1 . 5) (2 . 8) (3 . 0) (4 . 0) (5 . 0)), player 1
total-pebbles 18
-9
*

[WJ]

ccc31807 wrote:

> Okay, I'm now spending about an hour a day writing real lisp, enough so that the non-obvious questions come up. Below, I have copied four variables that I use, two functions, SUM-CDR and GOODNESS-1, and example executions for both players.
>
> It adds up the cdr of each sublist depending on whether the player is 0 (alpha) or 1 (beta) and returns the difference between the number of pebbles possessed by that player and the total number of pebbles.
>
> Question: Even to my unpracticed eye, this looks pretty awful. Any comments for improvements from a style perspective?
>
> As always, thanks, CC.
>
> --------------vars-----------------
> (defparameter list-0 '((0 . 3)(1 . 3)(2 . 3)(3 . 3)(4 . 3)(5 . 3)))
> (defparameter list-1 '((0 . 4)(1 . 0)(2 . 5)(3 . 0)(4 . 6)(5 . 3)))
> (defparameter list-2 '((0 . 0)(1 . 0)(2 . 0)(3 . 6)(4 . 2)(5 . 10)))
> (defparameter list-3 '((0 . 5)(1 . 5)(2 . 8)(3 . 0)(4 . 0)(5 . 0)))
>
> -------------funcs-------------------
> (defun sum-cdr (lst &optional (sum 0))
> (cond
> ((null lst) sum)
> (t
> (incf sum (cdar lst))
> (sum-cdr (cdr lst) sum))))
>

(defun sum-cdr (lst)
(apply #'+ (mapcar #'cdr lst)))

[Pascal J. Bourguignon]

ccc31807 <cart...@gmail.com> writes:

> Okay, I'm now spending about an hour a day writing real lisp, enough
> so that the non-obvious questions come up. Below, I have copied four
> variables that I use, two functions, SUM-CDR and GOODNESS-1, and
> example executions for both players.
>
> It adds up the cdr of each sublist depending on whether the player is
> 0 (alpha) or 1 (beta) and returns the difference between the number
> of pebbles possessed by that player and the total number of pebbles.
>
> Question: Even to my unpracticed eye, this looks pretty awful. Any
> comments for improvements from a style perspective?
>
> As always, thanks, CC.
>
> --------------vars-----------------
> (defparameter list-0 '((0 . 3)(1 . 3)(2 . 3)(3 . 3)(4 . 3)(5 . 3)))
> (defparameter list-1 '((0 . 4)(1 . 0)(2 . 5)(3 . 0)(4 . 6)(5 . 3)))
> (defparameter list-2 '((0 . 0)(1 . 0)(2 . 0)(3 . 6)(4 . 2)(5 . 10)))
> (defparameter list-3 '((0 . 5)(1 . 5)(2 . 8)(3 . 0)(4 . 0)(5 . 0)))

Always use stars around the names of special variables! (defvar and
defparameter).

> -------------funcs-------------------
> (defun sum-cdr (lst &optional (sum 0))
> (cond
> ((null lst) sum)
> (t
> (incf sum (cdar lst))
> (sum-cdr (cdr lst) sum))))

1- You can name your parameter list, no need to use abbreviations.

2- You should write a docstring to each function (and each definition in
general). In particular, the docstring must tell enough about the
purpose (the specifications) of the function so that we can check
whether it does what it must do (ie. whether there are bugs!).

3- This functions is a poor choice of a function because it is too
specific. You could take each accessor in CL and all the libraries,
and write a similar sum-something function. This is ludicruous.

Instead, use (or implement if it is missing) a generalized function.
Something like:

(reduce (function +) a-list :key (function cdr))

Oops! There is already reduce, you didn't have to write sum-cdr!

> (defun goodness-1 (player board)
> (let* ((len (length board))
> (half (ash len -1))

No. This is not C. (half (/ len 2))
Compilers are smart enough to optimize it if they deem it fit.

> (total-pebbles (sum-cdr board))

So, (reduce …)

> (alpha (subseq board 0 half))
> (beta (subseq board half)))

Now, the problem is that you're walking the list three times. (Once for
length, once for alpha and once for beta (even if for alpha it's only
n/2, it still counts as O(n)).

You could write a function that split the list in two in n steps.

> (format t "board: ~a, player ~a~% total-pebbles ~a~%" board player
> total-pebbles)

No. Unless it's for debugging, do not mix I/O (and in general, side
effects) with normal functions.

> (if (zerop player)
> (- (sum-cdr alpha) (ash total-pebbles -1))
> (- (sum-cdr beta) (ash total-pebbles -1)))))

See above.


Now since you're using sum-cdr thrice in this function, you could wrap
the reduce form in a function on the condition you're able to find it a
meaningful name, domain-wise. If you may need this function outside of
goodness-1, then you may keep a defun form, otherwise you could use flet
(or labels it if needed).


So, assuming it may be needed elsewhere:

;; Let's introduce some abstraction:

(defun make-hole (number pebbles)
"Return a new hole, identified by its number, and containing the
indicated number of pebbles."
(cons number pebbles))

(defun hole-number (hole)
"Return the number of the hole."
(car hole))

(defun pebbles-in-hole (hole)
"Return the number of pebbles in the hole."
(cdr hole))

;; And don't forget test cases:
(loop
:for pebbles :below 5
:do (assert (= pebbles (pebbles-in-hole (make-hole 0 pebbles)))))
(loop
:for number :below 5
:do (assert (= number (hole-number (make-hole number 0)))))



(defun count-pebbles (board)
"Return the total number of pebbles on the board.
BOARD: a list of holes."
(reduce (function +) board :key (function pebbles-in-hole)))

(assert (zerop (count-pebbles '()))) ; empty board has no pebbles
(assert (zerop (count-pebbles (list (make-hole 1 0))))) ; empty hole has no pebbles
(assert (= 1 (count-pebbles (list (make-hole 1 1) (make-hole 2 0)))))
(assert (= 1 (count-pebbles (list (make-hole 1 0) (make-hole 2 1)))))
(assert (= 2 (count-pebbles (list (make-hole 1 1) (make-hole 2 1)))))



(defun split-list-in-two (list)
"Return: a fresh list containing the first half of the element, and
the tail of the LIST that contains the other half."
(loop
:for hare = list :then (cddr hare)
:for turtle = list :then (cdr turtle)
:while hare
:collect (car turtle) :into first-part
:finally (return (values first-part turtle))))

(assert (equal (multiple-value-list (split-list-in-two '())) '(nil nil)))
(assert (equal (multiple-value-list (split-list-in-two '(1))) '((1) nil)))
(assert (equal (multiple-value-list (split-list-in-two '(1 2))) '((1) (2))))
(assert (equal (multiple-value-list (split-list-in-two '(1 2 3))) '((1 2) (3))))
(assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4))) '((1 2) (3 4))))
(assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4 5))) '((1 2 3) (4 5))))
(assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4 5 6))) '((1 2 3) (4 5 6))))
(assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4 5 6 7))) '((1 2 3 4) (5 6 7))))



(defun goodness-1 (player board)
"Return a goodness measure of the BOARD for the PLAYER."
(multiple-value-bind (alpha-part beta-part) (split-list-in-two board)
(- (count-pebbles (if (zerop player)
alpha-part
beta-part))
(/ (count-pebbles board) 2))))

(assert (= 0 (goodness-1 0 (list (make-hole 1 1) (make-hole 2 1)))))
(assert (= 1/2 (goodness-1 0 (list (make-hole 1 2) (make-hole 2 0) (make-hole 3 1) (make-hole 4 0)))))
(assert (= -1/2 (goodness-1 1 (list (make-hole 1 2) (make-hole 2 0) (make-hole 3 1) (make-hole 4 0)))))



Oh, and if you want some I/O:

(defun print-board (board)
(format t "board: ~a~% total-pebbles ~a~%" board (count-pebbles board))
(values))


(defparameter *list-3* '((0 . 5)(1 . 5)(2 . 8)(3 . 0)(4 . 0)(5 . 0)))

(print-board *list-3*)

board: ((0 . 5) (1 . 5) (2 . 8) (3 . 0) (4 . 0) (5 . 0))

total-pebbles 18


--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[WJ]

Pascal J. Bourguignon wrote:

>
> (defun split-list-in-two (list)
> "Return: a fresh list containing the first half of the element, and
> the tail of the LIST that contains the other half."
> (loop
> :for hare = list :then (cddr hare)
> :for turtle = list :then (cdr turtle)
> :while hare
> :collect (car turtle) :into first-part
> :finally (return (values first-part turtle))))
>
> (assert (equal (multiple-value-list (split-list-in-two '())) '(nil nil)))
> (assert (equal (multiple-value-list (split-list-in-two '(1))) '((1) nil)))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2))) '((1) (2))))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2 3))) '((1 2) (3))))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4))) '((1 2) (3 4))))

Did you invent the tortoise-hare technique?

[ccc31807]

On Tuesday, December 4, 2012 5:12:07 PM UTC-5, ccc31807 wrote:

Thank you for your tutorial. I feel that I owe you some tuition. If you were in the office next door, I would buy you a bottle of whiskey (a small bottle, that is,)

Now, all I've got to do is spend the time understanding what you wrote and applying it.

CC.

[WJ]

Pascal J. Bourguignon wrote:

> (defun split-list-in-two (list)
> "Return: a fresh list containing the first half of the element, and
> the tail of the LIST that contains the other half."
> (loop
> :for hare = list :then (cddr hare)
> :for turtle = list :then (cdr turtle)
> :while hare
> :collect (car turtle) :into first-part
> :finally (return (values first-part turtle))))
>
> (assert (equal (multiple-value-list (split-list-in-two '())) '(nil nil)))
> (assert (equal (multiple-value-list (split-list-in-two '(1))) '((1) nil)))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2))) '((1) (2))))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2 3))) '((1 2) (3))))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4))) '((1 2) (3 4))))
> (assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4 5))) '((1 2 3) (4 5))))

Paul Graham told you about LOOP, Pascal.

EMACS Lisp:

(defun split-list-in-half (turtle)
(let ((hare turtle) first-half)
(while hare
(push (pop turtle) first-half)
(pop hare) (pop hare))
(list (nreverse first-half) turtle)))

: (split-list-in-half '(Pascal petulantly pouts with protruding lips))
((Pascal petulantly pouts) (with protruding lips))

[WJ]

In newLISP, pushing to the end of the list is just as fast
as pushing to the start of the list. So no reverse is needed.

(define (split-list-in-half turtle , first-half)
(let (hare turtle)
(while hare
(push (pop turtle) first-half -1)
(pop hare) (pop hare))
(list first-half turtle)))

[WJ]

WJ wrote:

> WJ wrote:
>
> > Pascal J. Bourguignon wrote:
> >
> > > (defun split-list-in-two (list)
> > > "Return: a fresh list containing the first half of the element, and
> > > the tail of the LIST that contains the other half."
> > > (loop
> > > :for hare = list :then (cddr hare)
> > > :for turtle = list :then (cdr turtle)
> > > :while hare
> > > :collect (car turtle) :into first-part
> > > :finally (return (values first-part turtle))))
> > >
> > > (assert (equal (multiple-value-list (split-list-in-two '())) '(nil nil)))
> > > (assert (equal (multiple-value-list (split-list-in-two '(1))) '((1) nil)))
> > > (assert (equal (multiple-value-list (split-list-in-two '(1 2))) '((1) (2))))
> > > (assert (equal (multiple-value-list (split-list-in-two '(1 2 3))) '((1 2) (3))))
> > > (assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4))) '((1 2) (3 4))))
> > > (assert (equal (multiple-value-list (split-list-in-two '(1 2 3 4 5))) '((1 2 3) (4 5))))

Gauche Scheme:

(define (split-list-in-two xs)
(let ((hare xs) (first-part '()))
(while (pair? hare)
(push! first-part (pop! xs))
(pop! hare)
(when (pair? hare) (pop! hare)))
(values (reverse first-part) xs)))

[WJ]

(define (split-list-in-two xs)
(let loop ((xs xs) (hare xs) (first-part '()))
(if (pair? hare)
(loop (cdr xs) (drop* hare 2) (cons (car xs) first-part))
(values (reverse first-part) xs))))