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