[plt-scheme] Re: Continuations memory accumulation problem

On Mon, Mar 15, 2010 at 10:37 PM, Anthony Cowley <acowley at seas.upenn.edu> wrote:
> 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.

    Indeed I've (kind of) modularized my code in the following components:
    * a tiles structure: a simple 2D matrix that holds symbols
('robot-east 'baddie 'food etc...) to denote what is in each
particular cell (I'm assuming that no two objects can be inside the
same cell);
    * a world structure: holds a reference to the tiles, a list of
robots, and a list of observers (the observer design pattern from
OOP);
    * a robot structure: somehow tightly coupled with the world
structure as I store inside the position (exactly as you are
suggesting, spearate structure with x and y), direction (symbol 'east
'north etc), behaviour (control) function and continuation inside the
behaviour function;
    * a user-interface for the entire simulation that registeres
observers to the world structure; the user interface also receives a
function which takes as input a position and spits out a symbol
representing the tile in question;

    So in a sense, my vizualization is a function application over the
world. The only reason I use the observer pattern is to allow the
world to notify only the changes, and not regenerate the whole map
after each action. Thus the coupling between the user interface and
the world is reduced to only a function that gives tiles and a
callback (to know what has been updated) for efficiency reasons; (the
callback could just be removed if I replace the observer pattern with
a simple list of positions that have changed, but this doesn't work if
I have multiple independent views of the same world.)

    About a purely functional robot (one that only creates new robot
states and never alters them) would be ideal. Unfortunately the code
would be filled with a lot of `let`'s after each operation just to
capture a new state. Either that or a lot of small functions that
delegate one another. (Although I think I could just hide all these
state exchanges behind some syntax trickery.)

    (Don't get me wrong I like the purely functional programming
style, as I'm accustomed with Erlang where this is the only way, I
just don't think this suits best here.)

    (I forgot to mention the purpose of my simulator: I want to give
my students an assignment to program some AI for the robots and this
way introduce them to Scheme. Indeed that for the moment my robot is
not quite "functional style" but I try to take it one step at a time,
from "procedural, or OOP style" towards "functional style". That's why
my accent here is on the control programming and on the efficiency of
the entire simulation framework.
    The next step could be to ask them to pass private data structures
(like a map of what the robot has discovered, or a list of
bread-crumbs to be able to back-track) in a pure-functional style.)


> 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

    Thank you for this elaborate description. I'll take it into
consideration (not tomorrow :) as with the continuation code, but this
week-end when I have some spare time) and I'll come back with my
feedback... (I hope that by this week-end I've already made the
source-code publicly available.)

    Maybe it will be a nice (advanced) assignment to ask my students
to modify the source code (about 500 lines with a lot of spaces) to
implement purely functional world and robots. (I do have multiple
robots.)

    About the DSL, indeed such a thing emerges (this was another
assignment I wanted to give out).

    In fact for GNU Robots (my original source of inspiration) I've
created a couple of syntaxes like:
    * probabilistic case: (choose-random (0.5 (do-something)) (0.25
(do-something-else)) (else (again-something)))
    * higher-level robot controls: (turn-left-while (or feel-prize? feel-food?))


> 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.

    Indeed as stated in the beginning this is one of my todo's. (From
lack of time I've just put everything in one module.)
    I envisage the following modules:
    * world -- contains only the logic behind the world and robots
(core operations that update the environment (by update we could also
understand creating new states));
    * library -- contains the code that loads tiles (the map) and
other data-files (image files, etc.)
    * vizualization -- contains the source code that only displays the
update world;
    * dsl -- syntaxes and functions that build upon the core
operations and enrich the expressiveness;
    * proxies (could be implemented) -- allows to attach a local robot
to a remote world or the other way around;

    Is this modularization Ok? Do you see something different?

    Thanks again for your time,
    Ciprian.

    P.S.: If you want to take a peek at my code (no comments for now,
and the modularization is only visible through spacing) I've attached
the "robots.ss" module.


> --------------
>
> #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)))
-------------- next part --------------
A non-text attachment was scrubbed...
Name: robots.ss
Type: application/octet-stream
Size: 14422 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20100315/731a29ce/attachment.obj>