Transcript Arrows, FRP, and Functional Reactive Programming

Arrows, FRP, and Functional
Reactive Programming
Lecture slides from the
Oxford Summer School on Advanced Functional Programming
Paul Hudak
Yale University
Dept. of Computer Science
Copyright © Paul Hudak,
August 2002; all rights reserved.
August 2002
1
Acknowledgements
Thanks to:
The Yale Haskell Group, especially
Antony Courtney, Henrik Nilsson,
and John Peterson.
Grants from the National Science Foundation
(CCR9900957 and CCR-9706747) and
the Defense Advanced Research Projects Agency
(F33615-99-C-3013 and DABT63-00-1-0002).
August 2002
AFP Summer School Lectures
2
Embedded Domain-Specific Languages
FVision
FranTk
Fruit
Frob
Fran
Graphics, Robotics, GUIs, Vision
Specialized languages
Continuous behaviors
and discrete reactivity
FRP
Functional Programming
August 2002
Applications
AFP Summer School Lectures
Functions, types, etc.
(Haskell)
3
Embedded Domain-Specific Languages
FVision
FranTk
Fruit
AFrob
Fran
Graphics, Robotics, GUIs, Vision
Applications
Specialized languages
Arrowized FRP (AFRP)
Continuous behaviors
and discrete reactivity
Functional Programming
Functions, types, etc.
(Haskell)
August 2002
AFP Summer School Lectures
4
A Different Perspective
Fact: I used FRP to teach Yale’s Autonomous
Systems course. Students were able to quickly
write programs for real and simulated robots.
Problem: Some students wrote programs with
space and time leaks – and in many cases I was
unable to give them a good explanation of how to
rewrite the program to avoid these leaks.
Goal: I’d be happy to spend more time teaching
AFRP if it resulted in fewer space and time leaks.
Question: Can I teach you all how to program
simulated robots using AFRP in only three
lectures?
August 2002
AFP Summer School Lectures
5
Part I
Arrowized FRP (AFRP) Basics
August 2002
6
Functional Reactive Programming
FRP (functional reactive programming) is
the essence of several DSL’s:




Fran = 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.
August 2002
AFP Summer School Lectures
7
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.
August 2002
AFP Summer School Lectures
8
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).
August 2002
AFP Summer School Lectures
9
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)
August 2002
AFP Summer School Lectures
10
Differential Drive Mobile Robot
y
vl
θ
x
l
August 2002
vr
AFP Summer School Lectures
Our software
includes a robot
simulator. Its
robots are
differential drive,
and we refer to
them as simbots.
11
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.)
August 2002
AFP Summer School Lectures
12
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, this requiring “catching up” at a later time.)
Fran, Frob, and FRP all suffer from this problem
to some degree.
August 2002
AFP Summer School Lectures
13
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.
Use arrows to structure the composition operations
on SF, and domain-specific operations for standard
FRP concepts.
August 2002
AFP Summer School Lectures
14
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, an AFRP 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.
August 2002
AFP Summer School Lectures
15
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)
August 2002
AFP Summer School Lectures
16
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
August 2002
AFP Summer School Lectures
17
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
AFRP defines:
f *** g = (arr fst >>> f) &&& (arr snd >>> g)
August 2002
AFP Summer School Lectures
18
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)
August 2002
AFP Summer School Lectures
19
Graphical Depiction of Arrows
sf1
sf
sf2
sf1 >>> sf2
first sf
sf1
sf1
sf2
sf2
sf1 &&& sf2
sf1 *** sf2
August 2002
AFP Summer School Lectures
sf
arr sf
sf
loop sf
20
Exercise 1
Define:
• first in terms of just arr, (>>>), and (&&&).
• (***) in terms of just first, second, and (>>>).
• (&&&) in terms of just arr, (>>>), and (***).
August 2002
AFP Summer School Lectures
21
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.
August 2002
AFP Summer School Lectures
22
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 AFRP 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??
August 2002
AFP Summer School Lectures
23
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.
August 2002
AFP Summer School Lectures
24
>>>
>>>
>>>
&&&
>>>
&&&
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)
August 2002
AFP Summer School Lectures
25
Exercises 2 & 3
Define signal functions ySF and thetaSF in AFRP
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.
August 2002
AFP Summer School Lectures
26
Conditionals in AFRP
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 switch into another signal
function, and furthermore to start from time zero.
August 2002
AFP Summer School Lectures
27
AFRP Events
Events in AFRP 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 ())
generates an event stream whose events
correspond to the simbot getting stuck (which
happens when it runs into something).
August 2002
AFP Summer School Lectures
28
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
August 2002
AFP Summer School Lectures
29
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.
August 2002
AFP Summer School Lectures
30
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.
August 2002
AFP Summer School Lectures
31
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
August 2002
AFP Summer School Lectures
32
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.
August 2002
AFP Summer School Lectures
33
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))
August 2002
AFP Summer School Lectures
t
34
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 vel is recursively defined, which requires:


The use of the rec keyword
The use of a delayed switch (drSwitch)
August 2002
AFP Summer School Lectures
35
Exercise 6
Redefine vel using dSwitch instead of drSwitch,
and without using the rec keyword. (Hint: define
vel recursively instead of defining v recursively.)
August 2002
AFP Summer School Lectures
36
Part II
Programming Robots with AFRP
August 2002
37
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).
August 2002
AFP Summer School Lectures
38
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 { . . . }
August 2002
AFP Summer School Lectures
-----
virtual world
simbot A’s
simbot B’s
does the work
-- Square obstacle
-- Vertical wall
-- Horizontal wall
–- Ball
-- Simbot A robot
-- Simbot B robot
39
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 = ...
rcB rProps = case rpId rProps of
1 -> rcA1 rProps
2 -> rcA2 rProps
3 -> rcA3 rProps
-- controller for simbot A’s
-- controller for simbot B’s
-- (showing here how to deal
-- with multiple simbots)
rcA1, rcA2, rcA3 :: SimbotController
rcA1 = ...
; rcA2 = …
; rcA3 = …
August 2002
AFP Summer School Lectures
40
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
August 2002
AFP Summer School Lectures
41
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))
August 2002
AFP Summer School Lectures
42
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)
August 2002
AFP Summer School Lectures
43
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.)
August 2002
AFP Summer School Lectures
44
A Talking Simbot
A simbot that says “Ouch!!” and reverses its
direction everytime 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)
August 2002
AFP Summer School Lectures
45
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.
August 2002
AFP Summer School Lectures
46
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.
August 2002
AFP Summer School Lectures
47
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.
August 2002
AFP Summer School Lectures
48
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))
August 2002
AFP Summer School Lectures
49
Moving On
Controller to move 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.
August 2002
AFP Summer School Lectures
50
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.
August 2002
AFP Summer School Lectures
51
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.
August 2002
AFP Summer School Lectures
52
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))
August 2002
AFP Summer School Lectures
53
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.)
August 2002
AFP Summer School Lectures
54
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…
August 2002
AFP Summer School Lectures
55
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)]
August 2002
AFP Summer School Lectures
56