umbrella.tex

\subsection{Getting wet}

In the \q{same-fringe?} program, the coroutines for the two trees
report back to one managing coroutine, which takes care to call
them alternately, as many times as needed. The two tree
coroutines don't interact with each other. Let’s now explore a
scenario where all the managed coroutines can resume each other:
i.e., the managing coroutine is hands-off and doesn't micromanage
the dispatching at all, simply reporting the final result when
the work is done.

An absent-minded Professor F~\cite{nahin:dice} wants to conserve
fossil fuel and get some exercise in the bargain. He decides to
walk to work in the morning and back home in the evening, and he
plans to stick to this routine for five years. The walk is short
enough that if the weather is clear when he sets out he will make
it to his destination without threat of rain.  But if it is
raining, which it can be with a certain probability
\q{*rain-prob*}, he can’t go out without an umbrella.

\scmfilename umbrella.scm

\scmdribble{
(define *rain-prob* 0.4)
(define *max-num-walks* (* 365 2 5)) ;2 walks/day for 5 years
}

\n To prepare for this, Prof F decides to keep an umbrella at
both home and office. Unfortunately, the smart prof is also
absent-minded, so if the weather is clear, he invariably neglects
to take an umbrella along, so there is a possibility that when it
does rain, both his umbrellas are at the other place and he is
stranded. How many walks can he hope to make before being
stranded?

We can model each location (home, office) as a coroutine that
keeps track of the number of umbrellas it has.  Each walk is
simulated by one location resuming the other.  The resumption's
arguments include whether Prof F is carrying an umbrella (i.e.,
it is raining) and the number of walks so far (including the
current one). When Prof F gets stranded, one of the location
coroutines resumes the manager coroutine with the number of walks
achieved.

The two location coroutines are just two instances of the same
kind, and as such can be generated by a single procedure. We will
have this procedure take the other location and the walk-manager
as parameters.

\scmdribble{
(define make-location-cor
  (lambda (other-location-cor manager-cor)
    (coroutine v
      (let ((num-umbrellas 1))
        (let loop ((umbrella? (car v))
                   (walks-so-far (cadr v)))
          (when umbrella?
            (set! num-umbrellas (+ num-umbrellas 1)))
          (cond ((>= walks-so-far *max-num-walks*)
                 (resume manager-cor walks-so-far))
                ((< (random) *rain-prob*)
                 (cond ((> num-umbrellas 0)
                        (set! num-umbrellas
                          (- num-umbrellas 1))
                        (apply loop
                          (resume other-location-cor
                                  (list #t
                                        (+ walks-so-far 1)))))
                       (else
                         (apply loop
                           (resume manager-cor walks-so-far)))))
                (else
                  (apply loop
                    (resume other-location-cor
                            (list #f (+ walks-so-far 1)))))))))))
}

\n Each location starts off with one umbrella (\q{num-umbrellas =
1}). Each resumption to the location (whether at the start, or
after a walk from the other location) comes with the following
info: Whether an umbrella arrived with the latest walk, and the
tally of the walks achieved so far. The former causes the
location to update its \q{num-umbrellas}. Next, the location uses
\q{random} to figure out if it’s raining. If it is, it further
checks if has an umbrella to spare. If so, it resumes the other
location, sending the umbrella; if not, it resumes the manager
with the \q{walks-so-far}. If it isn’t raining, it resumes the
other location without an umbrella.

(There is another, not very probable, possibility: The
\q{walks-so-far} have reached the maximum, in which case, the
location in question resumes the manager with that number. We
need this to avoid an experiment that takes forever.)

The managing coroutine starts off one of the location coroutines,
say the home. Since it refers to the home coroutine, we’ll use a
coroutine-genertor procedure for it too, taking the home
coroutine as paramter:

\scmdribble{
(define make-manager-cor
  (lambda (home-cor)
    (coroutine dummy-init-arg
      (resume home-cor (list #f 0)))))
}

\n All it does is start off the professor at his home, and waits
until one of the locations resumes it when the prof has stranded
himself.

To start off the process, we need to actually generate the three
coroutines, and link them together.

\verbwrite{
(define umbrella-trial
  (lambda (rain-prob)
    (when (number? rain-prob) (set! *rain-prob* rain-prob))
    ;...
}

\scmdribble{
(letrec ((home-cor (make-location-cor
                     (lambda (v) (office-cor v))
                     (lambda (v) (manager-cor v))))
         (office-cor (make-location-cor
                       (lambda (v) (home-cor v))
                       (lambda (v) (manager-cor v))))
         (manager-cor (make-manager-cor
                        (lambda (v) (home-cor v)))))
  ;...
}

\n Note that we use lambda-wrapping, so the argument coroutines have
a chance to be created before being used.

The body of the letrec then runs the manager

\scmdribble{
   ;...
   (manager-cor 'start-the-ball-rolling)
   )
}

\verbwrite{
  ;...
  )
}

This should give the number of walks the prof manages before
getting stranded. We'd like to run this simulation multiple
times, plus we'd like to vary the rain probability.\f{We could,
if we wanted, vary the maximum number of walks too, in the same
way. While we’ve used globals \q{*rain-prob*} and
\q{*max-num-walks*} here to avoid complicating the presentation
of the code, ideally these parameters should be lexically visible
only to the body of \q{umbrella-trial}, with the definitions of
the coroutine-generators moving into \q{umbrella-trial}’s body so
they can access these parameters.} Let's wrap the \q{letrec} inside a
procedure that takes these parameters and returns a thunk that
can be run as one trial.

\q{
(define umbrella-trial
  (lambda (rain-prob)
    (lambda ()
      (when (number? rain-prob) (set! *rain-prob* rain-prob))

      ; the letrec expression goes here
      )))
}

\n We can now call, say

\q{
((umbrella-trial 0.4))
}

\n and this will output the number of walks before strandedness.

To estimate the expected value of the achieved walks,
we can use the \q{monte-carlo} procedure we’ve already defined in
chapter~\ref{rec}:

\q{
(monte-carlo (umbrella-trial 0.4))
}

\n You will find that Prof F gets stranded in a matter of mere
days, way before the 5-year goal he set himself.  What do you
think the result will be if the probability of rain is 0 or 1?
What if it is a little more than 0 or a little less than 1? Well,
you don’t have to puzzle over it. Just call \q{monte-carlo} on
\q{umbrella-trial} with the appropriate argument!