[plt-scheme] Re: Continuations memory accumulation problem

On Mon, Mar 15, 2010 at 2:54 PM, Ciprian Dorin, Craciun
<ciprian.craciun at gmail.com> wrote:
> (define (control-robot! robot)
>
>        (when (feel-robot? robot 'baddie)
>                (zap-robot! robot))
[...]
>        (control-robot! robot))
>
>    If there is another better way to do it (without using threads or
> continuations, but also keeping the AI code simple) please let me
> know.

The way I would do this (and I have written quite a few robot
simulations in PLT Scheme!), is to first separate notions of robot
state from simulation output. Before defining the data structures,
decide if the simulator visualization can be a function from robot
state to an image. Hopefully it can, in which case the control-robot
function takes one robot structure, and computes a new one based on
sensor input and controller output. You can even do this purely to
leave the door open to further improvements that take advantage of
concurrency and/or rolling back actions.

If you really need actions that should be visualized or otherwise
reflected in the world state but have no obvious place in the robot
state, then you just provide an interface to the robot controller to
trigger these IO actions, and then you thread the world state through
each robot update function so that it can be altered by each robot
(you could do this via mutation if purity isn't required).

Here is one take on a purely functional simulator that operates under
the assumption that each robot executes its behavior loop
independently of the others. To eliminate that assumption, the
run-simulation function could change from a map to a fold in order to
enforce some sequencing on world-changing behaviors.

The key points here are that we abstract your linear chain of robot
behavior components into a fold over a list of behavior components and
that the simulator as a whole just computes a new list of robot states
from the previous one. Also note that we have established what is
effectively a DSL for robot behaviors with zap, grab, and wander.
These functions have robot-state implicitly threaded through them.

We do lose the explicit recursion in your control-robot function, but
there are various ways, such as your continuation approach, of getting
that element of your design back if it is really needed.

Anthony

P.S. I would encourage you to refactor this code into multiple modules
to better identify the key pieces. You can pretty much just identify
the lines at which this program could be broken into meaningful
modules, each of which will only be a handful of lines of code.

--------------

#lang scheme

;; 2D position
(define-struct pos (x y) #:transparent)

;; A robot has a position, a heading, and a list of transient actions.
(define-struct (robot pos) (θ action) #:transparent)

;; Add a transient action to a robot's state.
(define ((add-action a) r)
  (struct-copy robot r (action (cons a (robot-action r)))))

;; Move a robot straight ahead at unit velocity.
(define (move-ahead r)
  (make-robot (+ (pos-x r) (cos (robot-θ r)))
              (+ (pos-y r) (sin (robot-θ r)))
              (robot-θ r)
              (robot-action r)))

;; Choose a random new heading for a robot.
(define (assume-random-heading r)
  (struct-copy robot r (θ (* (random) 2 pi))))

;; The simulation world has an enemy and a food item.
(define enemy (make-pos 2 3))
(define food (make-pos 6 7))

;; Proximity predicate.
(define ((near? item dist) robot)
  (let ((dx (- (pos-x item) (pos-x robot)))
        (dy (- (pos-y item) (pos-y robot))))
    (< (sqrt (+ (* dx dx) (* dy dy))) dist)))

(define near-enemy? (near? enemy 5))
(define near-food? (near? food 2))

;; If the predicate evaluates to true when applied to a state value,
;; return the result of applying the action to that state value.
;; Otherwise, return the state value unchanged.
(define ((do-when pred? action) s) (if (pred? s) (action s) s))

;; If-then-else combinator for state modification.
(define ((do-if pred? then else) s) (if (pred? s) (then s) (else s)))

;; Zap a nearby enemy.
(define zap (do-when near-enemy? (add-action 'zap)))

;; Grab a nearby food item.
(define grab (do-when near-food? (add-action 'grab)))

;; Move ahead if otherwise unoccupied, but periodically pick a
;; random new heading.
(define wander (do-when (compose null? robot-action)
                        (do-if (λ (_) (= (random 10) 0))
                               assume-random-heading
                               move-ahead)))

;; Execute the behavior stack. A robot will zap a nearby enemy,
;; grab a nearby food item, or just wander around.
(define (simulate-robot r)
  (foldl (λ(f r) (f r)) r (list zap grab wander)))

;; Reset the robot's transient state.
(define (reset-action r) (struct-copy robot r (action '())))

;; Draw a robot, and reset its transient actions.
(define (viz r) (printf "~a~n" r) (reset-action r))

;; Run a simulation iteration.
(define (run-simulation robots)
  (map (compose viz simulate-robot) robots))

(define (test)
  (let ((robots (list (make-robot 3 3 pi '())
                      (make-robot 5 6 0 '())
                      (make-robot 12 11 (* pi 0.5) '()))))
    (run-simulation robots)))