Время моделирования как ленивые числа

Я пытаюсь написать интерактивную, в реальном времени аудио-синтез в 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 (например, " > " ) будут чистыми...

В этот момент я немного потерялся. Итак, вопрос: возможно ли для внедрения эффективных ленивых номеров для представления времени в интерактивных приложения реального времени?

ИЗМЕНИТЬ

Было указано, что у меня есть имя: функциональное реактивное программирование. Хорошим введением является статья "Обзор функционального реактивного программирования" Эдварда Амсдена. Вот выдержка:

Большинство реализаций FRP, включая все реализации сигнальных функций на сегодняшний день, поддаются непрерывной переоценке события несоответствия из-за реализации "на основе тянуть", когда система непрерывно рецессирует выражение FRP для вывода. работа над Reactive (разделы 3.1 и 4.4) предназначена для решения этой проблемы для классического FRP, но расширение этой работы на сигнальные функции имеет еще не изучены, а простая операция времени появления сравнение зависит от проверенного программистом и, возможно, сложного чтобы доказать, что личность сохраняет ссылочную прозрачность.

Похоже, в этом суть проблемы: мой подход "фиктивных событий" и предложение DarkOtter попадают в категорию "непрерывная переоценка событий, не связанных с событиями".

Будучи наивным программистом, я говорю "давайте использовать ленивые числа, давайте сделаем пример foo/bar"./меня машет руками. Между тем, я посмотрю на YampaSynth.

Кроме того, мне кажется, что делать число "ленивым" относительно линейного времени, как я пытаюсь сделать, тесно связано с тем, что (реальные) числа "ленивы" относительно точности (cf Точная реальная арифметика). Я имею в виду, что мы хотим использовать изменяемые объекты (нижнюю границу для события-времени и интервал для реалов) из строго чистого контекста, учитывая определенные законы, которые должны быть выполнены, чтобы убедиться, что мы" сохраняем ссылочную прозрачность". Больше ручного, извините.

Ответ 1

Вы могли бы сделать что-то вроде этого, чтобы достичь (грубо) максимальной задержки, и я думаю, что это, возможно, уже было сделано в некоторых программах FRP. Я думаю, что эта идея будет похожа на то, что вы предложили, имея тип типа:

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

Вы можете определить для себя всевозможные удобные экземпляры, такие как comonad, но ключевой бит для того, что вы говорите, заключается в том, что у вас должен быть какой-то метод, при котором любой процесс ввода-вывода ожидает следующего события midi он сразу же дает вашу пару с ленивым promises времени и события. Событие по-прежнему станет доступным только тогда, когда произойдет реальное событие, но время должно быть испорчено, так что часть его всегда будет доступна после некоторой максимальной задержки. Я., он ждет 100 мс, а затем, если это событие произошло, ленивый удар становится (больше 100 мс (thunk)), где следующий thunk затем работает таким же образом. Это позволяет вам лениво чередовать вещи, как вы хотели.

Я видел что-то подобное в старой версии библиотеки FRP, используя комбинацию MVars и unsafeDupablePerformIO. Идея состоит в том, что у вас есть MVar, который ожидает ваш ожидающий поток ввода IO, чтобы сигнализировать о значении, а используемый вами thunk использует unsafeDupablePerformIO для чтения из MVar (который должен быть потокобезопасным и идемпотентным, поэтому он должен быть безопасным я думаю).

Затем, если ожидающий поток считает это слишком длинным, вы просто создаете еще один MVar и сопровождающий thunk для следующего бита, а затем вставляете в старое ваше значение (Greater (100ms) (thunk)), которое позволяет оценить в ленивой части продолжить.

Это не идеально, но это должно означать, что вам нужно будет подождать, скажем, 100 мс в будущем, а не 500 мс.

Если вы не хотите вмешиваться во временные представления, я полагаю, вы всегда можете просто сделать поток миди-событий потоком (время, возможно событие), а затем просто убедитесь, что все, что генерирует события вставки, по крайней мере один раз каждые x ms.

Изменить:

Я сделал простой пример такого подхода здесь: https://gist.github.com/4359477

Ответ 2

Используйте pipes, единственную поточную библиотеку, которая позволяет вам параметризовать запросы для большего ввода. Вы структурируете свой ленивый поток заметок в качестве сервера:

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

Там, все готово! Чтобы узнать больше об этом трюке, прочитайте учебник pipes в Control.Proxy.Tutorial.

Бонусные очки: вам не нужно использовать unsafePerformIO, но вы все равно сохраняете композиционное программирование. Например, если вы хотите взять первые 10 заметок, то вы просто выполните:

takeB_ 10 <-< notes

Если вы хотите сделать все заметки до заданного срока, вы просто выполните:

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

Обычно, когда люди говорят, что хотят чистоты, что они на самом деле означают, они хотят композиции.