Modeling time as lazy numbers

Question

I am trying to write an interactive, realtime audio-synthesis thing in Haskell, and I'm in dire need of "lazy numbers" to represent time.

Here's the thing: my program is based on a notion of "signals" and these signals are transformed by "signal processors". But unlike other similar projects like Faust or ChucK, I would like to work with strictly pure functions and yet have explicit access to time.

The idea is that it's possible to express pure "lazy stream processors" in Haksell and because of lazy evaluation, that will work in an interactive, real-time fashion.

For example, I could represent a "midi signal" as a stream of note-changing events:

type Signal = [ (Time, Notes->Notes) ]

It all works very well in non-interactive mode, but when I want to actually play with it in real-time, I hit a big roadblock: at any one point in time, the output signal is dependent on the time of the next input event. So my synthesis engine actually stops until the next event.

Let me explain: when my soundcard asks for a sample of my output signal, the lazy evaluator walks the dependency graph of my signal processors and eventually asks for a piece of the input (midi) signal. But let's say the input signal looks locally like this:

input :: Signal
input = [ ..., (1, noteOn 42), (2, noteOff 42), ... ]

When I need to compute the output (audio) signal at time 1.5, I will need something like this:

notesAt :: Signal -> Time -> Notes
notesAt = notesAt' noNotes where
    notesAt' n ((st,sf):ss) t
            | st > t = n
            | otherwise = notesAt' (sf n) ss t

... and when I evaluate "notesAt input 1.5", it will have to compute "2 > 1.5" before returning. But the event (2, NoteOff 42) won't happen for another 0.5 seconds! So my output is dependent on an input event that will happen in the future and thus stops.

I call this effect "paradoxical causality".

I have thought about how to handle this for quite some time, and I have come to the conclusion that what I need is some form of numbers that will allow me to evaluate "a > b" lazily. Let's say:

bar :: LazyNumber
bar = 1 + bar

foo :: Bool
foo = bar > 100

... then I would like "foo" to evaluate to True.

Note that you can use Peano numbers for that and it actually works.

But in order to be efficient, I would like to represent my numbers like:

data LazyNumber = MoreThan Double | Exactly Double

... and this needs to be mutable to work, even though every function on the LazyNumbers (e.g. ">") will be pure...

At this point, I'm kind of lost. So the question is: Is it possible to implement efficient lazy numbers to represent time in interactive real-time applications?

EDIT

It has been pointed out that what I'm doing has a name: Functional Reactive Programming. The paper "A Survey of Functional Reactive Programming" by Edward Amsden is a good introduction. Here is an extract:

Most FRP implementations, including all signal function implementations to date, succumb to continuous re-evaluation of event non-occurrences due to a "pull-based" implementation where a system continuously resamples the FRP expression for output. The work on Reactive (Sections 3.1 and 4.4) purports to solve this problem for Classic FRP, but extending this work to signal functions has not yet been explored, and the simple operation of occurrence time comparison relies on a programmer-checked and arguably difficult to prove identity to retain referential transparency.

It seems this is the heart of the problem: my "dummy events" approach and DarkOtter's proposal fall in the "continuous re-evaluation of event non-occurrences" category.

Being a naïve programmer, I say "let's use lazy numbers, let's make the foo/bar example work". /me waves hands. Meanwhile, I'll take a look at YampaSynth.

Also, it seems to me that making numbers "lazy" with respect to linear time like I'm trying to do is closely related to making (real) numbers "lazy" with respect to precision (c.f. Exact Real Arithmetic). I mean, we want to use mutable objects (a lower bound for event-time vs. an interval for reals) from a strictly pure context, given certain laws to be satisfied to make sure that we "retain referential transparency". More handwaving, sorry.

Answer 1

You could do something a bit like this to achieve (roughly) a maximum latency, and I think it may have already been done in some FRP programs. I think this idea would be similar to what you suggested, having a type like:

data Improving n = Greater n (Improving n) | Exact n

You can define all sorts of handy instances for this, like comonad, but the key bit for what you're saying is that you would have to have some method whereby, while whatever IO process is waiting for the next midi event to occur, it immediately yields your pair, with the lazy promises of the time and event. The event will still only become available when the actual event occurs, but the time should be fudged so that a part of it will always become available after some maximum latency. I.e., it waits for say 100ms, and then if the event has occured, the lazy thunk becomes (Greater 100ms (thunk)) where the next thunk then operates in the same fashion. This allows you to lazily interleave things as you wanted.

I have seen something similar done in an older version of an FRP library, using a combination of MVars and unsafeDupablePerformIO. The idea is, that you have an MVar which your IO monad waiting thread pushes into to signal the value, and the thunk you put in uses unsafeDupablePerformIO to read from the MVar (which should be thread safe, and idempotent, so it should be safe to do I think).

Then, if the waiting thread thinks it's too long, you simply create another MVar and accompanying thunk for the next bit, and then push into the old one your (Greater (100ms) (thunk)) value, which allows the evaluation in the lazy part to continue.

It's not perfect, but it should mean that you would only have to wait, say 100ms into the future rather than 500ms.

If you don't want to mess around with time representations, I suppose you could always just make the stream of midi events a stream of (time, Maybe event), and then just ensure that whatever is generating inserts events at least once every x ms.

Edit:

I made a simple example of this approach here: https://gist.github.com/4359477

Answer 2

Use pipes, the only streaming library that lets you parametrize requests for more input. You structure your lazy stream of notes as a server:

notes :: (Proxy p) => MaxTime -> Server p MaxTime (Maybe Note) IO r
notes = runIdentityK $ foreverK $ \maxTime -> do
    -- time out an operation waiting for the next note
    -- deadline is the maxTime parameter we just received
    t <- lift $ getCPUTime
    note <- lift $ timeout (maxTime - t) $ getNote
    respond note

There, you're done! To learn more about this trick, read the pipes tutorial at Control.Proxy.Tutorial.

Bonus points: You don't need to use unsafePerformIO, yet you still keep compositional programming. For example, if you want to take the first 10 note, then you just do:

takeB_ 10 <-< notes

If you want to then take all notes up to a given deadline, you would just do:

query deadline = takeWhileD isJust <-< mapU (\() -> deadline) <-< notes

Usually when people say they want purity, what they really mean is they want compositionality.