One of the motivations for expressing FRP (Functional Reactive Programming) as signal functions is to avoid time leaks [1].
A time leak is a situation in which a value is dependent on past values for an arbitrary time interval, and they are not evaluated as they are produced, thus, suddenly forcing a value may take an arbitrary amount of time. This occurs in the following pathological example in Haskell with Yampa, but should be true in the general case for continuation-based signal function implementations in non-strict languages:
{-# LANGUAGE Arrows #-}
module Main where
import Data.Time.Clock
import Data.IORef
import FRP.Yampa
import System.Random
alt :: SF a b -> SF a b -> SF a (Event ()) -> SF a b
alt sf1 sf2 sfEv = proc inp -> do
outPair <- sf1 &&& sf2 -< inp
evt <- sfEv -< inp
swappedEvt <- accum (arr fst) -< evt `tag` (arr swap >>>)
rSwitch (arr fst) -< (outPair, swappedEvt)
average = proc inp -> do
inpIntegral <- integral -< inp
t <- time -< inp
returnA -< inpIntegral / t
leak = (time &&& after 30 ()) >>> alt (constant 0) (arr fst >>> average) (arr snd)
main = do
t <- getCurrentTime
timeRef <- newIORef t
let init = return ()
sense = (\_ -> do
t' <- getCurrentTime
t <- readIORef timeRef
let dt = realToFrac (t' `diffUTCTime` t)
writeIORef timeRef t'
return (dt, Nothing)
)
actuate = (\_ x -> do
print x
return $ snd x > 60
)
reactimate init sense actuate (leak &&& time)
Since the integral (within the average function) is dependent on all past values, and the average function is part of the network from the beginning, but its output is not required until 30 seconds into evaluation, it builds up an extremely long sequence of thunks. On my machine, one can observe the behavior as at the 30 second mark the program pauses for a short time and then trips a stack overflow, caused by running out of stack space for the chain of evaluations.
- "Functional Reactive Programming, continued" Nilsson, Henrik and Courtney, Antony and Peterson, John, Haskell '02
Edited for forgotten citation
You may be interested in checking out "Safe Functional Reactive Programming through Dependent types" where the authors created an arrowized FRP system that disallows all programs that introduce a space or time leak.
ReplyDeleteIt's actually in my reading schedule for my FRP independent study this quarter. Thanks!
ReplyDeleteI noticed this in some of my programs, too. My solution was to make integral more strict. My version of integral is the same as in the Yampa library, except for the two strictness annotations on the arguments to integralAux:
ReplyDeleteintegral :: VectorSpace a s => SF a a
integral = SF {sfTF = tf0}
where
igrl0 = zeroVector
tf0 a0 = (integralAux igrl0 a0, igrl0)
integralAux !igrl !a_prev = SFTIVar {sfTF' = tf}
where
tf dt a = (integralAux igrl' a, igrl')
where
igrl' = igrl ^+^ realToFrac dt *^ a_prev
To correct David's comment (sorry), note that "Safe Functional Reactive Programming through Dependent types" (of which I am an author) doesn't address the issues of space and time leaks. It does define a total FRP language, so termination is guaranteed (or more specifically, each sample step is guaranteed to terminate), but there are no efficiency promises. Whether leaks are avoided depends on which host language is used. If a strict language, then it would be leak-free, if a lazy language, then it would not be.
ReplyDeleteAlso note that the Safe FRP paper has been superseded by my thesis ("Towards Safe and Efficient Functional Reactive Programming") which contains an improved version of the Safe FRP work (if you'll pardon the advertising), so I'd suggest you look at that rather then the paper.
If you're not aware of it, you may want to look at "Real-Time FRP", a paper by Wan, Taha and Hudak, which addresses placing time and space bounds on FRP programs.