Tuesday, March 22, 2011

Demonstrating a Time Leak in Arrowized FRP

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.

1. "Functional Reactive Programming, continued" Nilsson, Henrik and Courtney, Antony and Peterson, John, Haskell '02

Edited for forgotten citation

4 comments:

1. 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.

2. It's actually in my reading schedule for my FRP independent study this quarter. Thanks!

3. I 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:

integral :: 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

4. 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.

Also 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.

Comments are moderated. I will try to get to them quickly. Off-topic or obscene comments, name-calling, and destructive criticism will all vanish into the void.

Disagree with me all you want, but keep it respectful towards me and everyone else.