Transcript Yampa, Arrows, and Robots - Computer Science

Yampa, Arrows, and Robots
CS-429/529
Fall 2004
Paul Hudak
Yale University
Dept. of Computer Science
Copyright © Paul Hudak,
November 2002; all rights reserved.
November, 2002
1
Embedded Domain-Specific Languages
FVision
FranTk
Fruit
Frob
Fran
FAL
Graphics, Robotics, GUIs, Vision
Specialized languages
Continuous behaviors
and discrete reactivity
FRP
Functional Programming
November, 2004
Applications
CS-429/529
Functions, types, etc.
(Haskell)
2
Embedded Domain-Specific Languages
FVision
FranTk
Fruit
Frob
Fran
FAL
Graphics, Robotics, GUIs, Vision
Yampa (“Arrowized FRP”)
Functional Programming
November, 2004
CS-429/529
Applications
Specialized languages
Continuous behaviors
and discrete reactivity
(structured using arrows)
Functions, types, etc.
(Haskell)
3
Part I
Yampa Basics
November, 2002
4
Functional Reactive Programming
FRP (functional reactive programming) is
the essence of several DSL’s:




Fran/FAL = FRP + graphics engine + library
Frob
= FRP + robot controller + library
FranTk = FRP + Tk substrate + library
Fruit
= FRP + Java GUI/graphics + library
FRP has two key abstractions:


Continuous time-varying behaviors.
Discrete streams of events.
November, 2004
CS-429/529
5
Behaviors
Continuous behaviors capture any timevarying quantity, whether:



input (sonar, temperature, video, etc.),
output (actuator voltage, velocity vector, etc.), or
intermediate values internal to a program.
Operations on behaviors include:


Generic operations such as arithmetic, integration,
differentiation, and time-transformation.
Domain-specific operations such as edge-detection
and filtering for vision, scaling and rotation for
animation and graphics, etc.
November, 2004
CS-429/529
6
Events
Discrete event streams include user input as well as
domain-specific sensors, asynchronous messages,
interrupts, etc.
They also include tests for dynamic constraints on
behaviors (temperature too high, level too low, etc.)
Operations on event streams include:
 Mapping, filtering, reduction, etc.
 Reactive behavior modification (next slide).
November, 2004
CS-429/529
7
An Example from Graphics (Fran)
A single animation example that
demonstrates key aspects of FRP:
growFlower = stretch size flower
where size = 1 + integral bSign
bSign =
0 `until`
(lbp ==> -1 `until` lbr ==> bSign) .|.
(rbp ==> 1 `until` rbr ==> bSign)
November, 2004
CS-429/529
8
Differential Drive Mobile Robot
y
vl
θ
x
l
November, 2004
vr
CS-429/529
Our software
includes a robot
simulator. Its
robots are
differential drive,
and we refer to
them as simbots.
9
An Example from Robotics
The equations governing the x position of a
differential drive robot are:
The corresponding FRP code is:
x = (1/2) * (integral ((vr + vl) * cos theta)
theta = (1/l) * (integral (vr - vl))
(Note the lack of explicit time.)
November, 2004
CS-429/529
10
Time and Space Leaks
Behaviors in FRP are what we now call signals,
whose (abstract) type is:
Signal a = Time -> a
Unfortunately, unrestricted access to signals
makes it far too easy to generate both time and
space leaks.
(Time leaks occur in real-time systems when a
computation does not “keep up” with the current
time, thus requiring “catching up” at a later time.)
FAL, Fran, Frob, and FRP all suffer from this
problem to some degree.
November, 2004
CS-429/529
11
Solution: no signals!
To minimize time and space leaks, do not provide
signals as first-class values.
Instead, provide signal transformers, or what we
prefer to call signal functions:
SF a b = Signal a -> Signal b
SF is an abstract type. Operations on it provide a
disciplined way to compose signals.
The discipline comes from the use of arrows to
structure the composition of SF values.
Domain-specific operations provide standard FRP
functionality.
November, 2004
CS-429/529
12
Analogy to Monads
A Haskell IO program is a composition of actions,
or commands, in which the details of the state are
hidden from the user. It is “run” at the top level
by an interpreter that interfaces to the OS.
Analogously, a Yampa program is a composition of
signal functions in which the details of signals are
hidden from the user. It is “run” at the top-level
by a suitable interpreter.
The main difference is that monad composition
must be linear to ensure single-threadedness,
whereas arrow composition is not so constrained.
Indeed, arrows are a generalization of monads.
November, 2004
CS-429/529
13
Arrow Operators
Composition operations are best motivated by
“point-free” functional programming.
Consider:
g x = f2 (f1 x)
In a point-free style, using function composition:
g = f2 . f1
At the level of arrows, we need function lifting:
arr :: (a->b) -> SF a b
and composition:
(>>>) :: SF a b -> SF b c -> SF a c
to yield:
g’ = arr f1 >>> arr f2 = arr g
(note: (>>>) is actually reverse composition)
November, 2004
CS-429/529
14
Arrow Operators, cont’d
But linear composition is not good enough – we
want to “wire together” signal functions in
arbitrary ways.
For example, consider (using ordinary functions):
h x = (f1 x, f2 x)
To make this point-free, define:
(f1 & f2) x = (f1 x, f2 x)
And thus:
h = f1 & f2
Using an analogous operator (&&&) for signal
functions, we can write:
h’ = arr f1 &&& arr f2 = arr h
November, 2004
CS-429/529
15
Arrow Operators, cont’d
Now consider:
i (x,y) = (f1 x, f2 y)
Using (&) defined earlier:
i = (f1 . fst) & (f2 . snd)
Analogously, at the level of signal functions:
i’ = arr (f1 . fst) &&& arr (f2 . snd)
which is the same as:
i’ = (arr fst >>> arr f1) &&& (arr snd >>> arr f2)
= arr i
This “argument wiring” pattern is so common that
Yampa defines:
f *** g = (arr fst >>> f) &&& (arr snd >>> g)
November, 2004
CS-429/529
16
The Arrow Class
When do we have enough combinators?
In fact: arr, (>>>), and (&&&) form a universal set:
we can define all “wirings” with them alone. (E.g.,
note that (***) was defined in terms of them.)
However, this is not the only universal set. Hughes
chose a different set in defining his Arrow class:
class Arrow a where
arr :: (b -> c) -> a b c
(>>>) :: a b c -> a c d -> a b d
first :: a b c -> a (b,d) (c,d)
where first is analogous to:
firstfun f (x,y) = (f x, y)
November, 2004
CS-429/529
17
Graphical Depiction of Arrows
sf1
sf
sf2
sf1 >>> sf2
first sf
sf1
sf1
sf2
sf2
sf1 &&& sf2
sf1 *** sf2
November, 2004
CS-429/529
sf
arr sf
sf
loop sf
18
Instance of SF in Arrow
type Signal a = Time -> a
type Time = Double
newtype SF a b = SF (Signal a -> Signal b)
instance Arrow SF where
-- arr f = SF (\s -> \t -> f (s t))
-- arr f = SF (\s -> f . s)
-- arr f = SF ((.) f)
arr = SF . (.)
-- SF sf1 >>> SF sf2 = SF (\s -> sf2 (sf1 s))
SF sf1 >>> SF sf2 = SF (sf2 . sf1)
first (SF sf) = SF (\s -> \t ->
let (b,d) = s t
in (sf (\t -> b) t, d))
November, 2004
CS-429/529
19
Exercise 1
Define:
• first in terms of just arr, (>>>), and (&&&).
• (***) in terms of just first, second, and (>>>).
• (&&&) in terms of just arr, (>>>), and (***).
November, 2004
CS-429/529
20
Some Primitive Signal Functions
identity :: SF a a
identity = arr id
constant :: b -> SF a b
constant = arr . const
time :: SF a Time
time = constant 1 >>> integral
integral :: VectorSpace a => SF a a
< definition omitted >
arr2 :: (a->b->c) -> SF (a,b) c)
arr2 = arr . uncurry
Numeric and other functions achieved via lifting:
arr sin, arr cos, arr2 (+), arr2 (*), etc.
November, 2004
CS-429/529
21
A Larger Example
Recall this FRP definition:
x = (1/2) (integral ((vr + vl) * cos theta))
Assume that:
vrSF, vlSF :: SF SimbotInput Speed
theta
:: SF SimbotInput Angle
then we can rewrite x in Yampa like this:
xSF :: SF SimbotInput Distance
xSF = let v = (vrSF &&& vlSF) >>> arr2 (+)
t = thetaSF >>> arr cos
in (v &&& t) >>> arr2 (*) >>> integral >>> arr (/2)
Yikes!!! Is this as clear as the original code??
November, 2004
CS-429/529
22
Arrow Syntax
Using Paterson’s arrow syntax, we can instead write:
xSF' :: SF SimbotInput Distance
xSF' = proc inp -> do
vr <- vrSF -< inp
vl <- vlSF -< inp
theta <- thetaSF -< inp
i <- integral -< (vr+vl) * cos theta
returnA -< (i/2)
Feel better? 
Note that vr, vl, theta, and i are signal samples, and
not the signals themselves. Similarly, expressions to
the right of “-<” denote signal samples.
Read “proc inp -> …” as “\ inp -> …” in Haskell.
Read “vr <- vrSF -< inp” as “vr = vrSF inp” in Haskell.
November, 2004
CS-429/529
23
>>>
>>>
>>>
&&&
>>>
&&&
vrSF
Graphical Depiction
vr
xSF' :: SF SimbotInput Distance
xSF' = proc inp -> do
vr <- vrSF -< inp
vl <- vlSF -< inp
theta <- thetaSF -< inp
i <- integral -< (vr+vl) * cos theta
returnA -< (i/2)
+
vlSF
inp
>>>
thetaSF
vl
theta
*
integral
i
/2
cos
xSF = let v = (vrSF &&& vlSF) >>> arr2 (+)
t = thetaSF >>> arr cos
in (v &&& t) >>> arr2 (*) >>> integral >>> arr (/2)
November, 2004
CS-429/529
24
Exercises 2 & 3
Define signal functions ySF and thetaSF in
Yampa that correspond to the definitions of y
and theta, respectively, in FRP.
Rewrite these definitions using the arrow
syntax. Also draw their signal flow diagrams.
November, 2004
CS-429/529
25
Conditionals in Yampa
Consider:
sf = proc i -> do
x <- sfx -< i
y <- sfy -< i
b <- flag -< i
returnA -< if b then x else y
sf alternates between sfx and sfy depending on the
pointwise value of the Boolean signal function flag.
But this isn’t good enough: we sometimes want a
signal function to abandon one behavior and switch
into another, and furthermore to start from time
zero at the moment of transition.
November, 2004
CS-429/529
26
Yampa Events
Events in Yampa are isomorphic to the Maybe data
type in Haskell.
An event stream has type Signal (Event b).
At any point it time, it yield either nothing, or an
event carrying value of type b.
An event source is a signal function of type
SF a (Event b). For example:
rsStuck :: SF SimbotInput (Event ())
is a primitive signal function that generates an
event stream whose events correspond to the
simbot getting stuck (which happens when it runs
into something).
November, 2004
CS-429/529
27
Operations on Events
fmap :: (a->b) -> Event a -> Event b
tag :: Event a -> b -> Event b
lMerge, rMerge ::
Event a -> Event a -> Event a
never :: SF a (Event b)
now :: b -> SF a (Event b)
after :: Time -> b -> SF a (Event b)
repeatedly :: Time -> b -> SF a (Event b)
edge :: SF Bool (Event ())
Example of edge:
alarmSF :: SF SimbotInput (Event ())
alarmSF = tempSF >>> arr (>100) >>> edge
November, 2004
CS-429/529
28
Switching
Events induce switching via a family of switching
combinators. The simplest is:
switch :: SF a (b, Event c) -> (c -> SF a b) -> SF a b
Read “(sf1 &&& es) `switch` \e -> sf2” as:
“Behave as sf1 until the first event in es occurs, at which
point bind the event’s value to e and behave as sf2.”
For example:
xspd :: Speed -> SF SimbotInput Speed
xspd v = (constant v &&& rsStuck)
`switch` \() -> constant 0
xspd is initially v, but drops to zero when the simbot
gets stuck.
November, 2004
CS-429/529
29
Exercises 4 & 5
Rather than set the wheel speed to zero when
the robot gets stuck, negate it instead. Then
define xspd recursively so that the velocity gets
negated every time the robot gets stuck.
Let v :: SF SimbotInput Velocity represent the
scalar velocity of a simbot. If we integrate this
velocity, we get a measure of how far the simbot
has traveled. Define an alarm that generates an
event when either the simbot has traveled more
than d meters, or it has gotten stuck.
November, 2004
CS-429/529
30
Switching Semantics
Two questions arise about switching semantics:
 Does the switch happen exactly at the event time,
or infinitesimally after?
 Does the switch happen just for the first event,
or for every event in an event stream?
Different answers result in four different switchers:
switch, dSwitch ::
SF a (b, Event c) -> (c -> SF a b) -> SF a b
rSwitch, drSwitch ::
SF a b -> SF (a, Event (SF a b)) b
November, 2004
CS-429/529
31
Time to Start Over
Consider:
(time &&& rsStuck) `switch` const time
The two occurrences of time are different: the
second one yields zero at the time of the first
rsStuck event.
If this is changed to:
let evSF = rsStuck >>> arr (`tag` time)
in (id &&& evSF) >>> rSwitch time
or if you prefer:
proc inp -> do
e <- rsStuck -< inp
rSwitch time -< (inp, e `tag` time)
then the time restarts on every rsStuck event.
November, 2004
CS-429/529
32
Time to Continue
How do we get time to continue?
Instead of this:
proc inp -> do
0
e <- rsStuck -< inp
rSwitch time -< (inp, e `tag` time)
t
ev1
ev2
We do this:
proc inp -> do
0
t <- time -< inp
ev1
ev2
e <- rsStuck -< inp
rSwitch time -< (inp, e `tag` time >>> arr (+t))
November, 2004
CS-429/529
t
33
Recursive Signal Functions
Suppose incrVelEvs :: SF SimbotInput (Event ())
generates “commands” to increment the velocity.
Consider:
vel :: Velocity -> SF SimbotInput Velocity
vel v0 = proc inp -> do
rec e <- incrVelEvs -< inp
v <- drSwitch (constant v0)
-< (inp, e `tag` constant (v+1))
returnA -< v
Note that v is recursively defined, which requires:


The use of the rec keyword
The use of a delayed switch (drSwitch)
November, 2004
CS-429/529
34
Exercise 6
Redefine vel using dSwitch instead of drSwitch,
and without using the rec keyword. (Hint: define
vel recursively instead of defining v recursively.)
November, 2004
CS-429/529
35
Part II
Programming Robots with Yampa
November, 2002
36
The Big Picture
Our simulated robots (i.e. simbots) are controlled by a
controller of type:
type SimbotController =
SimbotProperties -> SF SimbotInput SimbotOutput
SimbotProperties specifies static properties of a
simbot (max speed, id number, etc).
SimbotInput is dynamic data into the controller from
the simbot; SimbotOutput is the data out of the
controller and into the simbot.
The three of these are instances of certain type
classes that provide different kinds of functionality
(see the paper for details).
November, 2004
CS-429/529
37
Running in a Virtual World
To run a controller:
runSim :: Maybe WorldTemplate ->
SimbotController ->
SimbotController ->
IO ()
type WorldTemplate = [ObjectTemplate]
data ObjectTemplate =
OTBlock { otPos :: Position2 }
| OTVWall { otPos :: Position2 }
| OTHWall { otPos :: Position2 }
| OTBall { otPos :: Position2 }
| OTSimbotA { otRId :: RobotId,
otPos :: Position2,
otHdng :: Heading }
| OTSimbotB { . . . }
November, 2004
CS-429/529
-----
virtual world
simbot A’s
simbot B’s
does the work
-- Square obstacle
-- Vertical wall
-- Horizontal wall
–- Ball
-- Simbot A robot
-- Simbot B robot
38
Top Level of Program
module MyRobotShow where
import AFrob
import AFrobRobotSim
-- AFrob library
-- the simulator
main :: IO ()
main = runSim (Just world) rcA rcB
world :: WorldTemplate
world = ...
rcA, rcB :: SimbotController
rcA = ...
-- controller for simbot A’s
rcB rProps = case rpId rProps of
1 -> rcA1 rProps
2 -> rcA2 rProps
3 -> rcA3 rProps
-- controller for simbot B’s
-- (showing here how to deal
-- with multiple simbots)
rcA1, rcA2, rcA3 :: SimbotController
rcA1 = ...
; rcA2 = …
; rcA3 = …
November, 2004
CS-429/529
39
A Detail about SimbotOutput
Brake both wheels:
ddBrake :: MR SimbotOutput
Set each wheel velocity:
ddVelDiff :: Velocity -> Velocity -> MR SimbotOutput
Set velocity and rotation:
ddVelTR :: Velocity -> RotVel -> MR SimbotOutput
Print message to console:
tcoPrintMessage :: Event String -> MR SimbotOutput
Then to merge the results:
mrMerge :: MR SimbotOutput -> MR SimbotOutput ->
MR SimbotOutput
mrFinalize :: MR SimbotOutput -> SimbotOutput
November, 2004
CS-429/529
40
Some Simple Robot Controllers
A stationary simbot:
rcStop :: SimbotController
rcStop _ = constant (mrFinalize ddBrake)
A moving but otherwise blind simbot:
rcBlind1 :: SimbotController
rcBlind1 _ = constant (mrFinalize $ ddVelDiff 10 10)
Or, better, one that goes ½ of the maximum speed:
rcBlind2 :: SimbotController
rcBlind2 rps =
let max = rpWSMax rps
in constant (mrFinalize $
ddVelDiff (max/2) (max/2))
November, 2004
CS-429/529
41
Running in Circles
Simbots cannot turn arbitrarily fast – it depends on
their speed. The maximum rotational velocity is:
where vmax is the max wheel speed, vf is the forward
velocity, and l is the distance between wheels.
rcTurn :: Velocity -> SimbotController
rcTurn vel rps =
let vMax = rpWSMax rps
rMax = 2 * (vMax - vel) / rpDiameter rps
in constant (mrFinalize $ ddVelTR vel rMax)
November, 2004
CS-429/529
42
Exercise 7
Link rcBlind2, rcTurn, and rcStop together in
the following way: Perform rcBlind2 for 2
seconds, then rcTurn for three seconds, and
then do rcStop. (Hint: use after to generate an
event after a given time interval.)
November, 2004
CS-429/529
43
A Talking Simbot
A simbot that says “Ouch!!” and reverses its
direction every time it gets stuck:
rcReverse :: Velocity -> SimbotController
rcReverse v rps =
beh `dSwitch` const (rcReverse (-v) rps)
where
beh = proc sbi -> do
stuckE <- rsStuck -< sbi
let mr = ddVelDiff v v `mrMerge`
tcoPrintMessage (tag stuckE "Ouch!!")
returnA -< (mrFinalize mr, stuckE)
November, 2004
CS-429/529
44
Exercise 8
Write a version of rcReverse that, instead of
knowing in advance what its velocity is, takes a
“snapshot” of the velocity, as described earlier,
at the moment the stuck event happens, and
then negates this value to continue.
November, 2004
CS-429/529
45
The Value of Feedback
The most effective controllers use feedback to
test the accuracy of the desired result.
The difference between the desired result and
the actual result is called the error.
A typical controller will feedback the error
proportionately, as its integral, as its derivative,
or as some combination of these three. (The most
general is thus called a PID (proportion/integral/
derivative) controller.
The field of control theory studies the issues of
accuracy, stability, and so on, of such systems.
November, 2004
CS-429/529
46
Heading in the Right Direction
A controller to head in a particular direction, using
proportionate feedback for accuracy:
rcHeading :: Velocity -> Heading -> SimbotController
rcHeading vel hd rps =
let rMax = 2 * (rpWSMax rps - vel) / rpDiameter rps
k=2
in proc sbi -> do
let he = normalizeAngle (hd - odometryHeading sbi)
rotV = lim rMax (k*he)
returnA -< mrFinalize (ddVelTR vel rotV)
Note the use of odometry: in this case, heading.
The parameter k is the proportionate gain of the system.
November, 2004
CS-429/529
47
Thinking Ahead …
Let’s rewrite rcHeading as:
rcHeading' :: Velocity -> Heading -> SimbotController
rcHeading' vel hd rps = proc sbi -> do
rcHeadingAux rps -< (sbi, vel, hd)
rcHeadingAux :: SimbotProperties ->
SF (SimbotInput,Velocity,Heading) SimbotOutput
rcHeadingAux rps =
let k = 2
in proc (sbi,vel,hd) -> do
let rMax = 2 * (rpWSMax rps - vel)/rpDiameter rps
he = normalizeAngle (hd - odometryHeading sbi)
rotV = lim rMax (k*he)
returnA -< mrFinalize (ddVelTR vel rotV))
November, 2004
CS-429/529
48
Moving On
Controller to move a simbot to a specific location:
rcMoveTo :: Velocity -> Position2 -> SimbotController
rcMoveTo vd pd rps = proc sbi -> do
let (d,h) = vector2RhoTheta
(pd .-. odometryPosition sbi)
vel = if d>2 then vd else vd*(d/2)
rcHeadingAux rps -< (sbi, vel, h)
Note the use of rcHeadingAux.
Also note how the simbot slows down as it approaches
its target, using positional odometry as feedback.
November, 2004
CS-429/529
49
Exercises 9, 10, and 11
9) rcMoveTo may behave a little bit funny once the
simbot reaches its destination, because a differential
drive robot is not able to maneuver well at slow
velocities. Modify rcMove so that once it gets
reasonably close to its target, it stops using rcStop.
10) Define a controller to cause a robot to follow a
sinusoidal path. (Hint: feed a sinusoidal signal into
rcHeadingAux.)
11) Define a controller that takes a list of points and
causes the robot to move to each point successively in
turn.
November, 2004
CS-429/529
50
Follow that Wall
To follow a wall, we use a range finder to sense
the distance to the wall.
It can be shown (for small deviations) that the
rotational velocity should be:
where r is the range-finder reading, d is the
desired distance, and Kp and Kd are the
proportionate and derivative gains, respectively.
November, 2004
CS-429/529
51
Wall Follower
This leads to:
rcFollowLeftWall ::
Velocity -> Distance -> SimbotController
rcFollowLeftWall v d _ = proc sbi -> do
let r = rfLeft sbi
dr <- derivative -< r
let omega = kp*(r-d) + kd*dr
kd = 5
kp = v*(kd^2)/4 -- achieves “critical damping”
returnA -< mrFinalize (ddVelTR v (lim 0.2 omega))
November, 2004
CS-429/529
52
Exercise 12
Enhance the wall-follower so that it can make left and
right turns in a maze constructed only of horizontal
and vertical walls. Specifically:
• If the simbot sees a wall directly in front, it should slow down
as it approaches, stopping at distance d from the wall. Then it
should turn right and continue following the wall which should
now be on its left. (This is an inside-corner right turn.)
• If the simbot loses track of the wall on its left, it continues
straight ahead for a distance d, turns left, goes straight for
distance d again, and then follows the wall which should again be
on its left. (This is an outside-corner left turn.)
November, 2004
CS-429/529
53
Your Mission
(Exercise 15, should you decide to accept it…)
Be a nerd and do all the exercises in the paper, or
Be cool and write a program to play Robocup Soccer!
To make it easier for you, we have set up the field
(world template) and a skeleton of the code to drop in
six controllers (three per team).
For example, you may write controllers for a
goalkeeper, striker, defender, etc.
But there is one other thing to tell you about first…
November, 2004
CS-429/529
54
Big Brother is Watching
Our simbots are equipped with one other device:
an animate object tracker that provides perfect
knowledge of the relative positions of the other
simbots and balls. Specifically:
aotOtherRobots ::
SimbotInput ->
[(RobotType, RobotId, Angle, Distance)]
aotBalls ::
SimbotInput -> [(Angle, Distance)]
November, 2004
CS-429/529
55