将时间建模为惰性数字

Question

我正在尝试在Haskell中编写一个交互式,实时的音频合成内容,而我迫切需要"懒惰的数字"来表示时间.

事情就是这样:我的程序基于"信号"的概念,这些信号由"信号处理器"转换.但与Faust或ChucK等其他类似项目不同,我希望使用严格纯粹的功能,并且能够明确地获取时间.

我们的想法是,可以在Haksell中表达纯粹的"懒惰流处理器",并且由于懒惰的评估,它将以交互式,实时的方式工作.

例如,我可以将"midi信号"表示为音符变化事件流:

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

这一切在非交互模式下都能很好地工作,但是当我想实时玩它时,我遇到了一个很大的障碍:在任何一个时间点,输出信号都取决于下一次输入的时间事件.所以我的合成引擎实际上会停止直到下一个事件.

让我解释一下:当我的声卡要求输出信号的样本时,懒惰的评估器遍历我的信号处理器的依赖图,并最终要求输入一个输入(midi)信号.但是,让我们说输入信号在本地看起来像这样:

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

当我需要在1.5时计算输出(音频)信号时,我需要这样的东西:

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

...当我评估"notesAt input 1.5"时,它必须在返回之前计算"2> 1.5".但事件(2,NoteOff 42)将不会再发生0.5秒!所以我的输出依赖于将来会发生的输入事件,从而停止.

我把这种效应称为"矛盾的因果关系".

我已经考虑过如何处理这个问题很长一段时间了,我得出结论,我需要的是某种形式的数字,这将允许我懒洋洋地评估"a> b".让我们说:

bar :: LazyNumber
bar = 1 + bar

foo :: Bool
foo = bar > 100

...然后我希望"foo"评估为True.

请注意,你可以使用Peano数字,它实际上是有效的.

但为了提高效率,我想代表我的数字:

data LazyNumber = MoreThan Double | Exactly Double

...这需要是可变的工作,即使LazyNumbers上的每个函数(例如">")都是纯粹的......

在这一点上,我有点迷茫.所以问题是:是否有可能实现有效的惰性数字来表示交互式实时应用程序中的时间？

编辑

有人指出,我正在做的事情有一个名称:功能反应式编程.Edward Amsden撰写的"功能反应编程概述"是一篇很好的介绍.这是一个摘录:

大多数FRP实现(包括迄今为止的所有信号函数实现)都屈服于由于"基于拉"的实现而不对事件发生的连续重新评估,其中系统连续地重新采样FRP表达式以用于输出.关于Reactive(第3.1和4.4节)的工作旨在解决Classic FRP的这个问题,但是尚未探索将此工作扩展到信号函数,并且发生时间比较的简单操作依赖于程序员检查并且可能难以证明身份以保持参考透明度.

这似乎是问题的核心:我的"虚拟事件"方法和DarkOtter的提议属于"对事件不发生的持续重新评估"类别.

作为一个天真的程序员,我说"让我们使用懒惰的数字,让我们让foo/bar示例工作"./我挥手.与此同时,我将看看YampaSynth.

另外,在我看来,就像我正在尝试做的那样,使线性时间的数字"懒惰"与使(实数)数字"懒惰"在精度方面密切相关(参见Exact Real Arithmetic).我的意思是,我们希望从严格纯粹的上下文中使用可变对象(事件时间的下限与实数的间隔),给定满足某些规律以确保我们"保留参照透明度".更多的握手,抱歉.

Answer 1

您可以做一些像这样的事情来实现(大致)最大延迟,我认为它可能已经在一些FRP程序中完成了.我认为这个想法与你建议的类似,有类似的类型:

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

您可以为此定义各种方便的实例,例如comonad,但您所说的关键位是您必须使用某种方法,尽管IO进程正在等待下一个midi事件发生,但它随着时间和事件的懒惰承诺,立即产生你的一对.事件仍然只有在实际事件发生时才可用,但是时间应该被捏造,以便在一些最大延迟之后它的一部分总是可用.即,它等待100毫秒,然后如果事件发生,懒惰的thunk变为(大100毫秒(thunk)),然后下一个thunk以相同的方式操作.这允许您根据需要懒洋洋地交错.

我在旧版本的FRP库中看到过类似的东西,使用了MVars和unsafeDupablePerformIO的组合.你的想法是,你有一个你的IO monad等待线程推送的MVar来发信号通知值,你输入的thunk使用unsafeDupablePerformIO从MVar读取(这应该是线程安全的,并且是幂等的,所以它应该是安全的我认为).

然后,如果等待的线程认为它太长,你只需创建另一个MVar并伴随thunk进行下一位,然后将你的(大(100ms)(thunk))值推入旧的值,这允许在懒惰中进行评估部分继续.

它并不完美,但它应该意味着你只需要等待,比如100ms而不是500ms.

如果你不想搞乱时间表示,我想你总是可以让midi事件流成为(时间,可能事件)的流,然后确保生成的任何内容每x至少插入一次事件x女士.

编辑:

我在这里做了一个简单的例子:https://gist.github.com/4359477