Transcript Functional Reactive Programming from First

Having Fun with Functions
How you can use functions to:
write interactive animation,
control robots, and
compose music.
Zhanyong Wan, Yale University
September, 2001
Acknowledgement:
Part of the slides provided by Paul Hudak
Roadmap
•  Programming languages research at Yale
• Introduction to Haskell
• Domain specific languages
• FRP
• Haskore
• Conclusions and video
USTC
September, 2001
2
Alan Perlis’ Epigrams in Programming
• A programming language is low level when its programs
require attention to the irrelevant.
• If a listener nods his head when you're explaining your
program, wake him up.
• Optimization hinders evolution.
• Once you understand how to write a program get someone
else to write it.
• The use of a program to prove the 4-color theorem will not
change mathematics - it merely demonstrates that the
theorem, a challenge for a century, is probably not important
to mathematics.
• There are two ways to write error-free programs; only the
third one works.
• A language that doesn't affect the way you think about
programming, is not worth knowing.
USTC
September, 2001
3
PL Research at Yale
• Faculty members (a partial list):
– Paul Hudak: functional programming (Haskell), domain
specific languages, language theory.
– John Peterson: functional programming (Haskell), domain
specific languages, compilation
– Zhong Shao: functional programming (ML), type theory,
compilation techniques, proof-carrying code.
– Carsten Schuermann: logical frameworks, theorem
proving, type theory, functional programming.
USTC
September, 2001
4
Having Fun at Yale
audio
• John Peterson
– Rock climbing
– Skiing
– Kayaking
• Paul Hudak
– Music
– Soccer coaching
– Skiing
– Rock climbing
– Kayaking
USTC
September, 2001
5
Roadmap
• Programming languages research at Yale
•  Introduction to Haskell
• Domain specific languages
• FRP
• Haskore
• Conclusions and video
USTC
September, 2001
6
Haskell by Examples
• Higher-order functions
– Functions are first-class values
In C, this would be
int max(int, int);
– Currying
• max :: (Int,Int)  Int
max (x,y) = if x > y then x else y
max(5,6)

6
• max :: Int  (Int  Int)
max x y = if x > y then x else y
max 5 6

6
• m5 :: Int  Int
m5 = max 5 <==>
m5 4
m5 6
USTC


m5 y = if 5 > y then 5 else y
5
6
September, 2001
7
Haskell by Examples
• Recursion
– sum [] = 0
sum (x:xs) = x + sum xs
– prod [] = 1
prod (x:xs) = x * prod xs
• Higher-order functions improve modularization
– Modularization is the key to successful programming!
• fold f a [] = a
fold f a (x:xs) = f x (fold f a xs)
• sum = fold (+) 0
• prod = fold (*) 1
• allTrue = fold (&&) True
• anyTrue = fold (||) False
USTC
September, 2001
8
Haskell by Examples
• Lazy evaluation
– Call-by-need
• f x y = if x > 0 then x else y
… f e1 e2 …
– Infinite data structures
• ones = 1 : ones

1 : 1 : 1 : 1 : 1 : …
• numsFrom n = n : numsFrom (n+1)
 n : n+1 : n+2 : n+3 : …
• squares = map (^2) (numsFrom 0)
 0 : 1 : 4 : 9 : 16 : 25 : 36 : …
• take 5 squares

[0, 1, 4, 9, 16]
• fib = 1 : 1 : zipWith (+) fib (tail fib) 
1 : 1 : 2 : 3 : 5 : 8 : 13 : …
(+) 1 : 2 : 3 : 5 : 8 : 13 : 21 : …
------------------------------------1 : 1 : 2 : 3 : 5 : 8 : 13 : 21 : 34 : …
USTC
September, 2001
9
Haskell by Examples
• Lazy evaluation
– Another powerful tool for improving modularity
• sort xs = …
take n xs = …
smallest n x = take n (sort x)
• Only practical for lazy languages
• Need-driven: no unnecessary computation
• No large intermediate data structure
USTC
September, 2001
10
Haskell by Examples
• Advanced type systems
– Polymorphic
• zipWith :: a,b,c. (abc)  [a]  [b]  [c]
– Type inference
• zipWith f [] _ = []
zipWith f _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
• a  [b]  c  [d]
refine 
a  [b]  [e]  [d]
refine 
(b  e  d)  [b]  [e]  [d]
rename 
(a  b  c)  [a]  [b]  [c]
USTC
September, 2001
11
Roadmap
• Programming languages research at Yale
• Introduction to Haskell
•  Domain specific languages
• FRP
• Haskore
• Conclusions and video
USTC
September, 2001
12
Animation in a General-Purpose Language
• Sketch of the code
(taken from Elliott’s Fran manual):
allocate and initialize window, various drawing surfaces and
bitmaps
repeat until quit:
get time ( t )
clear back buffer
for each sprite (back to front):
compute position, scale, etc. at t
draw to back buffer
flip back buffer to the screen
deallocate bitmaps, drawing surfaces, window
• Lots of tedious, low-level code that you have to write
yourself
• There is a better way!
USTC
September, 2001
13
We Need Domain Specificity
• A domain-specific language (or DSL) is a language that
precisely captures a domain semantics; no more, and no
less.
• Examples
– SQL, UNIX shells, Perl, Prolog
– FRP, Haskore
USTC
September, 2001
14
Advantages of DSL Approach
• Programs in the target domain are:
– more concise
– quicker to write
– easier to maintain
– easier to reason about
Contribute to higher
programmer productivity
Dominant cost in
large SW systems
Verification, transformation, optimization
These are the same arguments in favor of any highlevel language. But in addition:
– can often be written by non-programmers
Helps bridge gap between
developer and user
Total SW Cost
The Bottom Line
Conventional
Methodology
C2
Start-up
Costs
C1
DSL-based
Methodology
Software Life-Cycle
USTC
September, 2001
16
DSL’s Allow Faster Prototyping
Using the “Spiral Model” of Software Development
design
specify
build
test
build
Without DSL
USTC
specify
design
test
With DSL
September, 2001
17
Roadmap
• Programming languages research at Yale
• Introduction to Haskell
• Domain specific languages
•  FRP
• Haskore
• Conclusions and video
USTC
September, 2001
18
Reactive Programming
• Reactive systems
– Continually react to stimuli
– Environment cannot wait –
system must respond quickly
– Run forever
reactive
system
stimuli
• Examples
responses
environ
-ment
– Computer animation
– GUI
– Robotics
– Vision
– Control systems
– Real-time systems
USTC
September, 2001
19
Functional Reactive Programming
• Functional Reactive Programming (FRP)
– Focuses on model instead of presentation
– Continuous time domain
– Discrete time domain
– Recursion + higher-order functions
– Originally embedded in Haskell
behavior
time
• Continuous/discrete signals
– Behaviors: values varying over time
event
– Events: discrete occurrences
time
• Reactivity: b1 ‘until‘ ev -=> b2
• Combinators: until, switch, when, integral, etc
USTC
September, 2001
20
What Is FRP Good for?
• Applications of FRP
– Fran
[Elliott and Hudak]
Interactive animation
– Frob
[Peterson, Hager, Hudak and Elliott]
– FVision
[Reid, Peterson, Hudak and Hager]
– Frappé
[Courtney]
– FranTk
[Sage],
Fruit
Robotics
Vision
Java
[Courtney]
GUI
moveXY (sin time) 0 charlotte
charlotte = importBitmap “charlotte.bmp”
USTC
September, 2001
21
Basic Concepts
• Behaviors (Behavior a)
– Reactive, continuous-time-varying values
time :: Behavior Time
mouse :: Behavior Point2
• Events (Event a)
– Streams of discrete event occurrences
lbp
:: Event ()
• Switching
b1 `till` lbp -=> b2
• Combinators
– Behaviors and events are both first-class
• Passed as arguments
• Returned by functions
• Composed using combinators
USTC
September, 2001
22
Behaviors
• Time
time :: Behavior Time
• Input
mouse :: Behavior Point2
• Integration
integral :: Behavior Double
-> Behavior Double
(integral time)
• Constant behaviors
lift0 :: a -> Behavior a
(lift0 5)
USTC
September, 2001
23
Lifting
• Static value -> behavior
lift0 :: a -> Behavior a
lift1 :: (a -> b) -> Behavior a -> Behavior b
lift2 :: (a -> b -> c)
-> Behavior a -> Behavior b -> Behavior c
...
• Examples
lift1 sin time
time
 sin time
lift2 (+) (lift0 1) (lift1 sin time)
 1 + sin time
time
USTC
September, 2001
24
Simple Behaviors
demo
• Hello, world!
hello :: Behavior Picture
hello
= text $ lift0 "Hello, world!"
main1
= animate hello
• Interaction: mouse-following
main2
= animate $ moveTo mouse hello
• Time
main3
USTC
= animate $ text $ lift1 show time
September, 2001
25
Geometry in FRP
• 2-D
– Points
– Vectors
– Common shapes
• Circle, line, polygon, arc, and etc
– Affine transformations
• Rotation
• Translation
• Reflection
• Scaling
• Shear
• Composition of the above
• 3-D as well
USTC
September, 2001
26
Spatial Transformations
demo
• Spatial transformations -- dancing ball
ball
ball
:: Behavior Picture
= withColor red $ stretch 0.1 circle
wiggle, waggle ::
Behavior Double -> Behavior Double
wiggle omega = sin (omega*time)
waggle omega = cos (omega*time)
main4 om1 om2 = animate $
moveXY (wiggle om1) (waggle om2) $
moveTo mouse ball
USTC
September, 2001
27
Spatial Composition
demo
• Spatial composition -- dancing ball & text
main5
= animate $ moveTo mouse $
moveXY (wiggle 4) (waggle 4) ball `over`
moveXY (wiggle 7) (waggle 3) hello
USTC
September, 2001
28
Recursive Behaviors
• Damped motion of a mass dragged with a spring
d
pm
v
ks d
po
d = pm – po
a = ksd – kfv
v =  a dt
po =  v dt
-kf v
– Integral equations
– Recursive
USTC
September, 2001
29
Recursive Behaviors (cont’d)
demo
• FRP Code
main6
= animate $
moveTo po ball `over`
withColor blue (line mouseB po)
where
d = pm – po
a = ksd – kfv
v =  a dt
po =  v dt
ks
= 1
kf
= 0.8
d
= mouse .-. po
a
= ks *^ d – kf *^ v
v
= integral a
po
= vector2ToPoint2 $ integral v
– Declarative
– Concise
– Recursive
USTC
September, 2001
30
Switching
demo
• Switching of behaviors
color :: Behavior Color
color
= red `till` lbp -=> blue
mouseBall :: Behavior Picture
mouseBall
main7
= moveTo mouse $ stretch 0.5 circle
= animate $ withColor color mouseBall
• Recursive switching
cycle3 c1 c2 c3 = c1 `till` lbp
-=> cycle3 c2 c3 c1
main8
= animate $
withColor (cycle3 red green blue) mouseBall
USTC
September, 2001
31
Paddle Ball in 17 Lines
•
video
paddleball vel = walls `over` paddle `over` pball vel
walls = let upper = paint blue (translate ( 0,1.7) (rec 4.4 0.05))
left = paint blue (translate (-2.2,0) (rec 0.05 3.4))
right = paint blue (translate ( 2.2,0) (rec 0.05 3.4))
in upper `over` left `over` right
paddle = paint red (translate (fst mouse, -1.7) (rec 0.5 0.05))
pball vel =
let xvel = vel `stepAccum` xbounce ->> negate
xpos = integral xvel
xbounce = when (xpos >* 2 ||* xpos <* -2)
yvel = vel `stepAccum` ybounce ->> negate
ypos = integral yvel
ybounce = when (ypos >* 1.5
||* ypos `between` (-2.0,-1.5) &&*
fst mouse `between` (xpos-0.25,xpos+0.25))
in paint yellow (translate (xpos, ypos) (ell 0.2 0.2))
x `between` (a,b) = x >* a &&* x <* b
USTC
September, 2001
32
Crouching Robots, Hidden Camera
• RoboCup
– Team controllers written in FRP
– Embedded robot controllers written in C
(our goal: use FRP instead)
camera
Team A
controller
Team B
controller
radio
USTC
radio
September, 2001
33
A Point-tracking Control System
• Input
– xd, yd, d:
desired position & heading
– x, y, :
actual position & heading
• Output
– u:
forward speed
– v:
rotational speed
d
(xd,yd)
u
v
USTC
September, 2001

(x,y)
34
A Point-tracking System
u  ud  k1 z1
v  k 2θ d  θ  r1 z1  r2 z 2
θ  θ  θ d
ud  xd cos θ d  y d sin θ d
z 2  ( x  xd ) sin θ  ( y  yd ) cos θ
r2  ud sin θ / θ
USTC
u
= u_d - k1 * z1
v
= k2 * derivativeB theta_d – dTheta
- r1 * z1 - r2 * z2
dTheta = lift1 normalizeAngle $
theta - theta_d
z1  ( x  xd ) cos θ  ( y  yd ) sin θ
r1  ud (1  cos θ) / θ
video
u_d = derivativeB x_d * cos theta_d
+ derivativeB y_d * sin theta_d
z1
= (x – x_d) * cos theta
+ (y – y_d) * sin theta
z2
= (x – x_d) * sin theta
– (y – y_d) * cos theta
r1
= ifZ (abs dTheta <* 0.01) 0
(u_d*(1 - cos dTheta)/dTheta)
r2
= ifZ (abs dTheta <* 0.01) (-u_d)
(-u_d * sin dTheta / dTheta)
September, 2001
35
Roadmap
• Programming languages research at Yale
• Introduction to Haskell
• Domain specific languages
• FRP
•  Haskore
• Conclusions and video
USTC
September, 2001
36
Haskore
Motivation:
Traditional music notation has many limitations:
• Unable to express a composer’s intentions.
• Biased toward music that is humanly performable.
• Unable to express notions of algorithmic composition.
Haskore (“Haskell” + “Score”) is a library of Haskell
functions and datatypes for composing music.
USTC
September, 2001
37
Basic Haskore Structure
type Pitch = (PitchClass, Octave)
data PitchClass = Cf | C | Cs | Df | D | Ds | Ef | E | Es | Ff | F | Fs
| Gf | G | Gs | Af | A | As | Bf | B | Bs
type Octave = Int
data Music =
Note Pitch Dur
| Rest Dur
| Music :+: Music
| Music :=: Music
| Tempo Int Int Music
| Trans Int Music
| Instr IName Music
type Dur
= Float
type IName = String
type PName = String
USTC
--------
a note
a rest
sequential composition
parallel composition
scale the tempo
transposition
instrument label
-- in whole notes
September, 2001
38
Glove
by Tom Makucevich
with help from Paul Hudak
Composed using Haskore, a Haskell DSL,
and rendered using csound.
USTC
September, 2001
39
Roadmap
• Programming languages research at Yale
• Introduction to Haskell
• Domain specific languages
• FRP
• Haskore
•  Conclusions and video
USTC
September, 2001
40
Conclusions
video
• Haskell has changed the way many people think about
programming. It is worth knowing!
• Functional programming community have some good
ideas. Let’s start using them!
• Functional programming is fun!
• Check out our web-site!
– Haskell
http://haskell.org/
– FRP
http://haskell.org/frp/
– Haskore http://haskell.org/haskore/
– Hugs
http://haskell.org/hugs/
• Life at Yale is fun! (See the video)
USTC
September, 2001
41