Folks,
With the help of quite a few of you and some lengthy trial and error
process I have implemented card game processing using CPS in Lisp.
Please take a look at the "We have seen the enemy..." post at
http://wagerlabs.com
I welcome your comments here or in the blog and give special thanks to
Marco Baringer for his CPS transformer.
Joel
Joel Reymont wrote:
> With the help of quite a few of you and some lengthy trial and error
> process I have implemented card game processing using CPS in Lisp.
> Please take a look at the "We have seen the enemy..." post at
> http://wagerlabs.com
<http://wagerlabs.com/tech/>
> I welcome your comments here or in the blog and give special thanks to
> Marco Baringer for his CPS transformer.
--
Jens Axel Søgaard
Joel Reymont wrote:
> Folks,
>
> With the help of quite a few of you and some lengthy trial and error
> process I have implemented card game processing using CPS in Lisp.
> Please take a look at the "We have seen the enemy..." post at
> http://wagerlabs.com
>
> I welcome your comments here or in the blog and give special thanks to
> Marco Baringer for his CPS transformer.
>
> Joel
>
Great read, once I found it ;) I use FiveAM myself, along with UCW, but
it was cool to see the CPS transformer in another context. I'm playing
with an IRC bot right now and i can see a number of places where this
sort of thing could come in handy.
Down with the State-Machines! Only through Continuationism can the
Worker Threads gain their Freedom!
--
Drew Crampsie
drewc at tech dot coop
From: Wade Humeniuk
Subject: Re: Card game logic: state machines vs. threads vs. CPS
Date:
Message-ID: <fUxRd.2901$NN.252@edtnps89>
Joel Reymont wrote:
> Folks,
>
> With the help of quite a few of you and some lengthy trial and error
> process I have implemented card game processing using CPS in Lisp.
> Please take a look at the "We have seen the enemy..." post at
> http://wagerlabs.com
>
There are more choices than a state-machine or a CPS. Here is
an example from code which makes things look like linear synchronous
code. However it is accepting and processing events from an
asynchronous TCP connection. It is from an IVR app written
with PortusGroup. (Copyright PortusGroup and me Wade
Humeniuk). The way an event handler is invoked mimics handler-bind
and restart-bind. It is aptly called event-bind and works
much like its predecessors. The major difference between
handler-bind and event-bind is that event-bind can handle
events based on their type or value (the default is eql
but it is definiable by generic method) and it loops around retreiving
events and dispatching them to the handlers. The further benefit
of this method is that the implicit state transitions stay on the
stack allowing one to use unwind-protect, handler-bind, et. al.
to protect oneself from errors and clean-up properly.
(defun info-menu (appt)
(let ((directions
(cdr (find-if (lambda (office)
(search office (appt-location appt) :test #'string-equal))
*location-directions*
:key #'car)))
(key-timeout (make-instance 'patient-key-timeout))
(info-complete (make-instance 'player-completed))
(menu-complete (make-instance 'player-completed)))
(labels ((play-key-menu ()
(play '("For location and directions, press 1."
"For telephone and fax numbers, press 2."
"To end this call, press star or hang up."
(:pause 2.0))
:completion-callback (lambda () (send-event menu-complete))))
(play-info (info) (play info :completion-callback (lambda () (send-event
info-complete)))))
(play-key-menu)
(start-timer key-timeout 45.0)
(unwind-protect
(event-bind
(((value menu-complete) () (play-key-menu))
((value info-complete) () (start-timer key-timeout 45.0) (play-key-menu))
((value key-timeout) () (return-from info-menu nil))
(#\1 () (cancel-timer key-timeout) (play-info directions))
(#\2 () (cancel-timer key-timeout) (play-info *office-tel/fax-info*))
(#\* () (return-from info-menu nil))
(dropped () (return-from info-menu nil))
(key-pressed () nil)))
(cancel-timer key-timeout)))))
Wade
Wade,
Would you be able to share details of implementing that event-bind?
It's early in the morning and I just woke up but I don't grasp how your
code loops, accepts events and saves it's context. I assume multiple
people can use the IVR app at the same time, right?
I'm dying to compare apples with apples and think there must be a
function analogous to the one below that saves the state and allows
re-entry.
(defun/cc receive (game)
(let/cc k
;; save continuation
(setf (continuation game) k)
;; TODO: start a timer here
))
According to Marco, "WITH-CALL/CC' simply CPS transforms it's
body, so the continuation pass to `CALL/CC' is _not_ a real
continuation, but goes only as far back as the nearest lexically
enclosing `WITH-CALL/CC' form." This tells me that the the closure will
only capture the variables within my play function, below
(defmethod play ((self game))
(with-call/cc
(block done
;; start a new hand
(notify-new-round game)
...
This is fine with me as I think it will minimize the memory space per
closure.
My notify-new-round function sends each player a "ready?" request and
expects a response. If it receives a "ready" then the player is marked
accordingly and if a timeout or another event is received then they are
marked as not participating in the current game. This is the code:
(defmethod notify-new-round ((self game))
(broadcast self "Starting new round...")
(loop for seat across seats do
(send (player seat)
(make-cmd ready))
(let ((cmd (receive game)))
(setf (state seat)
(if (eq (car cmd) 'ready)
'playing
'sitting-out)))))
How would I implement the notify-new-round using your event binding
approach and how much memory does your context capture?
Thanks, Joel
From: Wade Humeniuk
Subject: Re: Card game logic: state machines vs. threads vs. CPS
Date:
Message-ID: <gFHRd.293$0h.212@clgrps13>
Joel Reymont wrote:
> Wade,
>
> Would you be able to share details of implementing that event-bind?
> It's early in the morning and I just woke up but I don't grasp how your
> code loops, accepts events and saves it's context. I assume multiple
> people can use the IVR app at the same time, right?
>
Event Bind is fairly simple. (yes, multiple people can
use the IVR at the same time, but only one person
per line (there is no way to distinguish who's who on
a conference call).
(defmacro event-bind (handlers &rest initforms)
(let* ((dummy-arg (make-symbol "DUMMY-ARG"))
(functional-handlers
(nreverse
(mapcar (lambda (handler)
(destructuring-bind (tag args &rest rest)
handler
(setf tag
(typecase tag
(symbol `(quote ,tag))
(cons
(destructuring-bind (qualifier form)
tag
(ecase qualifier
(value form))))
(character tag)))
(if args
`(push (make-event-handler :tag ,tag
:function (lambda ,args ,@rest))
*event-handlers*)
`(push (make-event-handler :tag ,tag
:function (lambda (,dummy-arg)
(declare (ignore ,dummy-arg))
,@rest))
*event-handlers*))))
handlers))))
`(let ((*event-handlers* *event-handlers*))
(declare (dynamic-extent *event-handlers*))
,@functional-handlers
,@initforms
(process-events))))
The function PROCESS-EVENTS is the one running around in a loop
invoking the functional-handlers for the incoming events. For the
IVR there is one process (thread) for each incoming call. In your
case you would have to write the process-events function that is
particularly suited for your application. For the IVR process-events
is:
(defun process-events ()
(loop for event = (mp:mailbox-read *internal-mailbox*)
do
(etypecase event
(time-event
(let ((timer (timer event)))
(when timer
(setf (current-time-event timer) nil
(timer event) nil)
(when *debug-stream* (debug-write (list 'timer-expired (type-of timer))
*server-stream*))
(invoke-event-handler timer))))
(event (invoke-event-handler event)))))
> I'm dying to compare apples with apples and think there must be a
> function analogous to the one below that saves the state and allows
> re-entry.
>
> (defun/cc receive (game)
> (let/cc k
> ;; save continuation
> (setf (continuation game) k)
> ;; TODO: start a timer here
> ))
>
Nope. When a major state transition takes place it
will probably be a function call (which probably has its
own event-bind). Re-entry happens when a sub-function
returns.
>
> My notify-new-round function sends each player a "ready?" request and
> expects a response. If it receives a "ready" then the player is marked
> accordingly and if a timeout or another event is received then they are
> marked as not participating in the current game. This is the code:
>
> (defmethod notify-new-round ((self game))
> (broadcast self "Starting new round...")
> (loop for seat across seats do
> (send (player seat)
> (make-cmd ready))
> (let ((cmd (receive game)))
> (setf (state seat)
> (if (eq (car cmd) 'ready)
> 'playing
> 'sitting-out)))))
>
Well with some modification it would not look like much different. You
have your events as some kind of lists. In the IVR system the incoming
sexp lists are converted to CLOS based events. Then events can be
inherited from one another, and event bind works better.
(defclass poker-room-event () ())
(defclass player-response (poker-room-event) ())
(defclass ready (player-response) ())
(defclass sitting-out (player-response) ())
(defun notify-new-round (game)
(broadcast game "Starting new round...")
(loop for seat across (seats game)
do
(setf (state seat)
(block response
(send (player seat) (make-cmd ready))
(event-bind
((ready () (return-from response 'ready))
(poker-room-event () (return-from response 'sitting-out))))))))
Wade
Wade,
Thanks for your explanation. I would claim that CPS is simpler and more
elegant, at least for applications like mine. Particularly given the
need to run process-events in various places.
I think the approach that you presented has many merits but it's an
inside out approach (grab events outside from the inside of the
function) whereas the CPS approach lets you feed events into the
function from the outside.
I will post more on the performance and memory usage I get with CPS
next week.
From: Wade Humeniuk
Subject: Re: Card game logic: state machines vs. threads vs. CPS
Date:
Message-ID: <xlIRd.4519$NN.2484@edtnps89>
Joel Reymont wrote:
> Wade,
>
> What did your SEXPs look like?
>
> Thanks, Joel
>
We kind of limited it to anything the reader can read
(no *read-eval*) and destructuring-bind can parse.
Wade