Transcript Slide 1

Functional Reactive Programming,
Resource Types, and Wormholes
Paul Hudak
Yale University
Department of Computer Science
haskell.cs.yale.edu
(Joint work with Dan Winograd-Cort)
New York Haskell Users Group
October 30, 2013
Background
• Time-varying quantities in a PL is due to Conal Elliott
(early work in C++ for animation)
• Fran: Functional Reactive Animation, by Elliott and Hudak:
FRP implemented in Haskell, showing elegance of higherorder functions, type classes, and so on.
• Yampa: at Yale; an arrow-based FRP in Haskell; avoided
insidious time- and space leaks; improved modularity.
• Since then, tons of new papers, both theoretical and
applied: FranTk, Frob, FVision, Reactive Banana, FPorter, …
• Antony Courtney: Fruit – a GUI based on Yampa
• Today will talk about a MUI (musical user interface)
implemented in Euterpea (Haskell library for computer
music).
Euterpea: Computer Music in Haskell
Why do this? After all, there are already many languages for
computer music…
Motivation:
• A required two-course computer-music sequence in the Computing and
the Arts major at Yale
• The use of modern, state-of-the-art PL ideas in a fun area
• To combine my research with my hobby
• To use music to teach (functional) programming
• To give composers powerful tools to enhance creativity
Last term, out of 20 students, 3 were Computing and the Arts majors, one
was a graduate student, and the rest were undergrads {mostly CS majors)
with an interest in computer music, or a desire to learn Haskell.
Euterpea
“Euterpea” is derived from “Euterpe”, who was
one of the nine Greek muses, or goddesses of
the arts, specifically the muse of music.
Signals and Signal Functions
• Signals are time-varying quantities.
• Conceptually they can be thought of as functions of
time:
Signal a = Time → a
• For example:
– a slider is a time-varying number
– a mouse is a time-varying cartesian coordinate
• For efficiency and modularity, we use arrows to
abstract away from signals, and instead use signal
functions. Conceptually:
SigFun a b = Signal a -> Signal b
• Haskell’s Arrow type class make this especially easy.
Key Idea
• This signal processing diagram:
y
sigfun
x
• is equivalent to this Euterpean code, using “arrow” syntax:
y <- sigfun -< x
• In turn this is part of a larger syntactic unit, called a proc. E.g.:
proc x -> do
y <- sf1 <- x
z <- sf2 <- y+1
return z*2
• By analogy to an anonymous function:
\ x ->
let
y = f1 x
z = f2 (y+1)
in z*2
Four Useful Functions
• To “lift” a function to a signal function:
arr :: (a → b) → SF a b
– Example: arr (+1) is a signal function that adds one to its
input
• To “lift” a constant to a constant signal function:
constA :: b → SF () b
– Example: constA 440 returns a steady value of 440
• To “compose” to signal functions:
(>>>) :: SF a b → SF b c → SF a c
(<<<) :: SF b c → SF a b → SF a c
– Example: constA 440 >>> arr (+1)
is the same as constA 441
Audio Example: Sine Wave
• From basic trigonometry:
sin(nωh) = 2 cos(ωh) sin((n-1) ωh) – sin((n-2) ωh)
where ω = 2πf
• We can derive a recurrence equation [Goertzel]:
y(0) = 0
y(1) = sin ωh
y(n) = c · y(n-1) - y(n-2)
• Diagrammatically:
where c = 2 (cos ωh)
init: sin ωh
z-1
init: 0
d1
z-1
*c
d2
-
y
Rendered in FRP
init: sin ωh
y(0) = 0
y(1) = sin ωh
y(n) = c · y(n-1) - y(n-2)
where c = 2 (cos ωh)
z-1
init: 0
d1
z-1
*c
sine :: Double -> SF () Double
sine freq =
let omh = 2*pi*freq/sr
d
= sin omh
c
= 2 * cos omh
in proc _ ->
do rec let y = c*d1-d2
d2 <- delay 0 -< d1
d1 <- delay d -< y
returnA -< y
d2
-
y
Physical Model of a Flute
sinA
lineSeg
5
lineSeg
envibr
env1
* 0.1
rand
1
×
flow
vibr
+
* breath
emb
+
Embouchure delay
sum1
delayt (1/fqc/2)
x
x – x3
+
lowpass
out
* amp
×
returnA
env2
* feedbk2
* feedbk1
Flute bore delay
flute
delayt (1/fqc)
bore
lineSeg
Flute Model in Euterpea
flute dur freq amp vfreq =
in proc () -> do
amp1 <- linseg … -< ()
amp2 <- linseg … -< ()
ampv <- linseg … -< ()
flow <- rand 1
-< amp1
vibr <- oscils vfreq -< 0.1 * ampv
rec
let feedbk = body * 0.4
body <- delay (1/freq) -< out
x <- delay (1/freq/2) -< breath*flow
+ amp1 + vibr + feedbk
out <- tone
-< (x - x*x*x + feedbk, 2000)
returnA -< out*amp*amp2
Flute Demo
• f0 and f1 demonstrate the change in the breath parameter.
f0 = flute 3 0.35 440 0.93 0.02
f1 = flute 3 0.35 440 0.83 0.05
• f2 has a weak pressure input so only plays the blowing noise.
f2 = flute 3 0.35 440 0.53 0.04
• f3 takes in a gradually increasing pressure signal.
f3 = flute 4 0.35 440
(lineSeg [0.53, 0.93, 0.93] [2, 2])
0.03
• Sequence of notes:
Events
• Signals are not enough… some things happen discretely.
• Events can be realized as a kind of signal:
data Maybe a = Nothing | Just a
type SEvent a = Maybe a
-- pre-defined in Haskell
• For example, MIDI events have type:
SEvent [MidiMessage]
where MidiMessage encodes standard MIDI messages such as
Note-On, Note-Off, etc.
• And a signal function over events would have type:
SF (SEvent T1) (SEvent T2)
This overall paradigm is often called
Functional Reactive Programming (FRP)
Musical User Interface (MUI)
• Design philosophy:
– GUI’s are important!
– The dataflow metaphor (“wiring together components”) is powerful!
– Yet graphical user interface programming is inefficient…
• Goal: MUI widgets using FRP
• The MUI arrow is called UISF
– UISF a b maps time-varying values (or event streams) of type a, to
those of type b
• Kinds of UISF signal functions:
–
–
–
–
Widget constructors
Widget transformers
I/O
Mediators
Widget Constructors
•
•
•
•
•
•
•
display
textbox
button
checkbox
radio
hSlider , vSlider
hiSlider , viSlider
:: Show a ⇒ UISF a ()
:: String → UISF String String
:: String → UISF () Bool
:: String → Bool → UISF () Bool
:: [String ] → Int → UISF () Int
:: RealFrac a ⇒ (a, a) → a → UISF () a
:: Integral a ⇒ a → (a, a) → a → UISF () a
(Run mui0 from Examples/MUI.hs)
MUI Transformers
•
•
•
•
title
:: String → UISF a b → UISF a b
withDisplay :: Show b ⇒ UISF a b → UISF a b
pad
:: (Int, Int , Int, Int ) → UISF a b → UISF a b
topDown, bottomUp, leftRight , rightLeft
:: UISF a b → UISF a b
• setLayout :: Layout → UISF a b → UISF a b
• makeLayout :: LayoutType → LayoutType → Layout
• data LayoutType = Stretchy { minSize :: Int }
| Fixed { fixedSize :: Int }
(Run mui2 from Examples/MUI.hs)
Mediators
• unique :: Eq a ⇒ UISF a (Event a)
-- generates an event whenever the input changes
• edge :: UISF Bool (Event ())
-- generates an event when input changes from False to True
• accum :: a → UISF (Event (a → a)) a
-- accum x starts with the value x , but then applies the function
-- attached to the first event to x to get the next value, and so on.
• mergeE :: (a → a → a) → Event a → Event a → Event a
-- mergeE f e1 e2 merges two event streams, using f to resolve
-- simultaneous events
• hold :: b → UISF (Event b) b
-- hold x begins as value x , but changes to the subsequent values
-- attached to each of its input events
• now :: UISF () (Event ())
-- creates a single event “right now”
(Run mui3, mui4 from Examples/MUI.hs)
Time and Timers
• time :: UISF () Time
-- Returns current time
-- Time is a type synonym for Double
• timer :: UISF (Time, Double) (SEvent ())
-- Emits events at given (dynamic) rate
(Run mui6 from Examples/MUI.hs)
Bifurcate Me, Baby!
Gary Lee Nelson
1995
Behind the Scene
• Consider the recurrence equation:
xn+1 = r * xn * (1 - xn)
Start with an initial population x0 and iteratively apply the
growth function to it, where r is the growth rate. For certain
values of r, the population stabilizes, but as r increases, the
period doubles, quadruples, and eventually leads to chaos.
It is one of the classic examples in chaos theory.
• In Euterpea: grow r x = r * x * (1-x)
• Let’s wrap it up in a MUI.
(Run bifurcate from Examples/MUI.hs)
Modular?
A program is a single signal function; it must thread all IO
actions through the same input and output.
MIDI synthesizer
electric piano
game
controller
run-time system
main program
(a signal function)
mouse
sound card
console I/O
MIDI instrument
printer
Maybe Not…
I/O bottleneck; no
transparency
MIDI synthesizer
I/O bottleneck; no
transparency
electric piano
game
controller
run-time system
main program
(a signal function)
mouse
sound card
console I/O
MIDI instrument
printer
Solution: Reify Real-World Objects
Expand main program to subsume virtualized IO devices!
MIDI synthesizer
electric piano
game
controller
run-time system
main program
(a signal function)
mouse
sound card
console I/O
MIDI instrument
printer
IO devices now treated just like other signal functions.
 As we have seen, can also virtualize virtual objects (widgets).

main program
MIDI synthesizer
electric piano
game
controller
sf1
sf2
sf3
sf4
mouse
sf5
sound card
sf6
sf7
console I/O
MIDI instrument
printer
A Problem: Resource Duplication
• Consider this code fragment:
() <- midiOut <- noteList1
() <- midiOut <- noteList2
is an output device, but there are two
occurrences -- what is the result?
Interleaving? Non-determinism?
• Likewise, here is an example of input:
midiSynth
notes1 <- midiIn <- ()
notes2 <- midiIn <- ()
is an input device. So do notes1 and notes2 return
the same result, or are they different?
midiIn
Solution: Resource Types
• Tag each virtualized object with a unique resource
type to prevent duplication.
midiOut :: SF (S MidiOut) MidiMsg ()
midiIn :: SF (S MidiIn) ()
MidiMsg
• The first argument to SF is a set of resource types;
S MidiOut and S MidiIn are singleton sets.
• With these types, the previous code fragments
will not type-check – resource types of composed
signal functions must be disjoint.
Resource Types
• A value of type
SF r a b
maps signals of type a into signals of type b, while
“consuming” the set of resources r.
• If sf1 :: SF r1 a b and sf2 :: SF r2 b c,
then in sf1 >>> sf2, r1 and r2 must be disjoint.
• In which case sf1 >>> sf2 :: SF (r1 U r2) a c.
• A restricted form of resource types can be implemented in
Haskell using higher-order types, type families, etc.
• The full version requires type features that don’t exist.
Effects in FRP
• How can we perform effects in the FRP
framework?
• Outside of FRP, we use monads:
– IO is useful for general I/O effects such as on realworld devices, but because we cannot escape it, it
is suboptimal for localized effects.
– ST is useful for mutable data structures, as it is
escapable after its localized effects:
runST :: (forall s. ST s a) -> a
The “phantom” type s provides the safety.
Performing Effects
• IO and ST are inherently different
– IO is for real-world objects that cannot be created
on the fly (e.g. printer, speaker, keyboard, etc.).
– ST is for mutable data structures that can be
allocated dynamically.
• Both types of effects require sequencing,
which the monadic structure provides.
Sequencing
• How can we do sequencing in FRP without
monads?
– Normal Haskell variables are time-invariant, but
FRP values are conceptually time-varying.
– Thus, the sequencing provided by monads can
be achieved in FRP by using the ordering of
events in an event stream.
• Indeed, we have seen this already with
midiIn and midiOut, using resource types to
ensure safety.
• But what about mutable data types?
Mutable Datatypes in FRP
• An example of a mutable data structure:
– Mutable array can be represented by a signal
functions that handle mutation requests:
(Event Request)
sfArray
(Event Response)
• Each sfArray will produce a new mutable array:
– We do not need resource types.
– We do not need a phantom type.
Mutable Datatype in FRP
• An even simpler mutable data structure
example would be a single cell of memory.
– The input would be the new value to store and the
output, the previous value in the cell:
init
– Essentially, this acts like a delay function. We call
it init in reference to our previous work on Causal
Commutative Arrows.
Splitting an Atom
• Let’s examine init more closely:
init
• What if we split the reading and writing?
Splitting an Atom
• Let’s examine init more closely:
blackhole
whitehole
• What if we split the reading and writing.
• We call this a wormhole.
– The blackhole is for writing
– The whitehole is for reading
Wormholes
• We can use wormholes as non-local, oneway communication channels.
SF 1
SF 2
Wormholes
• We can use wormholes as non-local, oneway communication channels.
SF 1
SF 2
Wormholes
• We can use wormholes as non-local, oneway communication channels.
whitehole
SF 2
blackhole
SF 1
Wormholes
• We can use wormholes as non-local, oneway communication channels.
𝑆𝐹1 = proc () → do
…
𝑑𝑎𝑡𝑎𝐹𝑟𝑜𝑚𝑆𝐹2 ← 𝑤ℎ𝑖𝑡𝑒ℎ𝑜𝑙𝑒 −≺ ()
…
𝑟𝑒𝑡𝑢𝑟𝑛𝐴 −
≺…
𝑆𝐹2 = proc () → do
…
__ ← 𝑏𝑙𝑎𝑐𝑘ℎ𝑜𝑙𝑒 −≺ 𝑙𝑜𝑐𝑎𝑙𝐷𝑎𝑡𝑎
…
𝑟𝑒𝑡𝑢𝑟𝑛𝐴 −≺ …
“Bottles”
• Composed and implemented by Donya Quick, a
grad student in CS
• Done entirely in Euterpea
• Demonstrates:
– High-level composition
• Notes, repetitions, structure
• Micro-tonal support
– Low-level signal processing
• Both “struck” bottle and “blown” bottle sounds,
using physical modeling
• Some additive synthesis as well
• Reverb and audio processing
Thank You!!
(any questions?)
For more information about Euterpea
and our PL research, see:
haskell.cs.yale.edu
Implementing Signals
• As “yet another abstraction”, arrows might seem
to introduce yet more computational overhead.
• But in fact arrows eliminate certain important
classes of space leaks.
• Furthermore, causal commutative arrows (CCA)
can improve performance dramatically:
– Any CCA expression can be normalized into an
expression with one loop and one vector of state
variables.
– This results in a factor of 50 improvement over
conventional implementation methods.
– Good enough for non-trivial real-time performance.