Simple tic-tac-toe GUI in Common Lisp: Avoid using Continuation Passing Style?

Question

I've made a simple Tic-Tac-Toe game in Common Lisp using the Ltk library.

One of the things I wanted to do was to support CPU vs CPU, human vs human, human vs CPU, and CPU vs human. Also, possibly multiple types of CPU algorithms. The ideal way to do this (for me at least) is to have a scheduler that gives control to Player 1, who chooses a move, and passes control back to the scheduler with the move he chose to make; the scheduler then passes control to Player 2, who chooses a move, and passes control back to the scheduler with the move he chose to make. And then the scheduler rotates back to Player 1. The job of the scheduler is also to update the GUI whenever a player makes a move, and to check whether the Game Over condition has been satisfied. Ideally, the way to implement this would be to use coroutines, but since Common Lisp doesn't support coroutines, I ended up using CPS.

I find the solution to be somewhat ugly. Is there a cleaner way of doing this?

(defun create-board ()
  (loop for i from 1 to 3 collect
        (loop for j from 1 to 3 collect nil)))

(defun at-position (i j board)
  (nth j (nth i board)))

(defun cpu-choose (board scheduler)
  (let ((choice-i (random 3))
        (choice-j (random 3)))
    (if (not (illegal-choice choice-i choice-j board))
        (funcall scheduler choice-i choice-j)
        (cpu-choose board scheduler))))

(defun illegal-choice (i j board)
  (at-position i j board))

(defun set-at-position (row-index col-index mat val)
  (loop for i from 0 to (length mat)
        for row in mat
        collect (loop for j from 0 to (length row)
                      for entry in row
                      collect (if (and (= i row-index) (= j col-index))
                                  val
                                  entry))))

(defun add-mark (choice board mark)
  (set-at-position (car choice) (cadr choice) board mark))

(defun wonp (current-symbol board)
  (let ((rows board)
        (columns (apply #'mapcar #'list board))
        (diagonal1 (list (at-position 0 0 board)
                         (at-position 1 1 board)
                         (at-position 2 2 board)))
        (diagonal2 (list (at-position 0 2 board)
                         (at-position 1 1 board)
                         (at-position 2 0 board))))
    (member t (mapcar (all-equal-to current-symbol) (cons diagonal1 (cons diagonal2 (append columns rows)))))))

(defun drewp (board)
  (and (not (wonp 'O board))
       (not (wonp 'X board))
       (every #'(lambda (row)
                  (not (member nil row)))
              board)))

(defun all-equal-to (current-symbol)
  (lambda (row)
    (every #'(lambda (v) (equal v current-symbol))
           row)))

(defun circular (items)
  (setf (cdr (last items)) items)
  items)

(defun human-choose (board scheduler)
  ;; pass to event handler
  nil)

(defun noughts-and-crosses (&key (players (list #'human-choose #'cpu-choose)))
  (with-ltk ()
    (let ((board (create-board))
          (buttons (make-array '(3 3) :initial-element nil))
          (scheduler-resume nil))
      (labels ((scheduler (board turns symbols)
               (let ((current-symbol (car symbols))
                     (current-player (car turns)))
                 (setf scheduler-resume #'(lambda (i j)
                                           (if (illegal-choice i j board)
                                               (scheduler board turns symbols)
                                               (progn
                                                 (setf board (set-at-position i j board current-symbol))
                                                 (setf (text (aref buttons i j)) (string current-symbol))
                                                 (cond ((wonp current-symbol board)
                                                        (do-msg (format nil "~A won!" current-symbol))
                                                        (return-from noughts-and-crosses))
                                                       ((drewp board)
                                                        (do-msg "Draw!")
                                                        (return-from noughts-and-crosses))
                                                       (t (scheduler board (cdr turns) (cdr symbols))))))))
                 (funcall current-player board scheduler-resume))))
        (loop for i from 0 to 2 do
              (loop for j from 0 to 2 do
                    (let ((this-i i)
                          (this-j j))
                      (setf (aref buttons i j) (make-instance 'button :text ""
                                                                      :command #'(lambda () (funcall scheduler-resume this-i this-j))))
                      (grid (aref buttons i j) i j))))
        (scheduler board
                   (circular players)
                   (circular '(X O)))))))

Answer 1

I've written quite a bit of code like what you post and now that I'm older (wiser is debatable, I'm sure) I've realized that there was one key tension in designs like this.

On the one hand you have the UI, which provides the illusion of real time, continuous operation (obviously when you drill all the way down, it's all interrupts and events co-opting a core somewhere, but that's not terribly important here). On the other you have the core game/simulation engine, which is fundamentally a state diagram.

The easiest way to resolve the tension is to keep the engine very pure and probably modeled after that implicit FSM. The only real event that moves a game of tic-tac-toe forward is the making of a move. So imagine your current game state is a simple p-list:

(:state :awaiting-naughts :board ((nil nil :x) (nil nil :o) ...) :errors nil)

Now further imagine that you had a function that accepted a symbol and coordinates and returned a new state.

(defun make-move (symbol x y game-state)
; 1. If game is over, return structure immediately unchanged.
; 2. Validate move.
;    a. If errors, return with error in :errors property and no change to state.
;    b. If valid, continue.
; 3. Modify state to account for move.
; 4. Check for win state and adjust answer as needed.
; 5. Return game state.
)

This function could validate the move and return a new state, indicating errors if they come up during validation.

At this point you have no UI and no user interaction, but the engine is encapsulated in one public function (give or take) and a single data structure.

The UI can then act as the orchestrator, taking input from the user via clicks and taps or invoking the AI (which can itself just be a function that takes the game state and returns the move it desires to make).

True continuation passing style, where the flow of execution is governed by returning functions accepting a single argument, seems like overkill for a tic-tac-toe engine. Simple data structures with functions seems like a more readable approach.