Экземпляр ArrowCircuit для потоковых процессоров, которые могут блокировать

Класс Control.Arrow.Operations.ArrowCircuit это для:

Тип стрелки, который можно использовать для интерпретации синхронных схем.

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

data StreamProcessor a b = Get (a -> StreamProcessor a b) | 
                           Put b    (StreamProcessor a b) |
                           Halt

instance Category StreamProcessor where
    id = Get (\ x -> Put x id)
  
    Put c bc . ab = Put c (bc . ab)
    Get bbc . Put b ab = (bbc b) . ab
    Get bbc . Get aab = Get $ \ a -> (Get bbc) . (aab a)
    Get bbc . Halt = Halt
    Halt . ab = Halt

instance Arrow StreamProcessor where
    ...

getThroughBlocks :: [a] -> StreamProcessor a b -> StreamProcessor a b
getThroughBlocks ~(a : input) (Get f)   = getThroughBlocks input (f a)
getThroughBlocks _input       putOrHalt = putOrHalt

getThroughSameArgBlocks :: a -> StreamProcessor a b -> StreamProcessor a b
getThroughSameArgBlocks = getThroughBlocks . repeat

instance ArrowLoop StreamProcessor where
    loop Halt               = Halt
    loop (Put (c, d) bdcd') = Put c (loop bdcd')
    loop (Get f)            = Get $ \ b -> 
         let 
            Put (c, d) bdcd' = getThroughSameArgBlocks (b, d) (f (b, d))
         in Put c (loop bdcd')

instance ArrowCircuit StreamProcessor where
    delay b = Put b id

Я считаю, что это решение сработает для нас так: мы хотим, чтобы someArrowCircuit >>> delay b был someArrowCircuit задержан на один тик, а b приходил раньше, чем что-либо из него. Легко увидеть, что мы получаем то, что хотим:

someArrowCircuit >>> delay b
= someArrowCircuit >>> Put b id 
= Put b id . someArrowCircuit
= Put b (id . someArrowCircuit)
= Put b someArrowCircuit

Есть ли законы для такого класса? Если я не ошибся, записав delay вниз, как синхронный сосуществует с асинхронным?


functional-programming stream-processing typeclass haskell circuit
person Zhiltsoff Igor    schedule 19.10.2020    source источник
comment
Я почти уверен, что идея синхронности здесь заключается в том, что каждый ввод производит соответствующий вывод. Однако стрелка StreamProcessor не синхронна, а это значит, что вы не можете говорить об отсрочке на 1 тик. Например, если вы напишете delay a >>> someSP, совсем не понятно, что вывод задерживается на 1 тик. Если у someSP есть несколько дополнительных Get, он может быть полностью не задержан, а если он 20 Put на Get, то он может быть задержан на 20 тиков. (Примечание: функция getThroughBlocks вызывает беспокойство - здесь соблюдаются ли законы ArrowLoop?)   -  person DDub    schedule 15.01.2021
comment
@DDub извини, я тебя не совсем понял. Прежде всего, что мы хотим сделать delay a >>> someSP? someSP >>> delay a понятно - мы просто вставляем дополнительное значение, независимо от того, будет ли оно следовать Get, Put или Halt: arr ([0..] !!) ожидает i и возвращает i, тогда как arr ([0..] !!) >>> delay (-1) сначала выплевывает -1, а затем работает как обычно.   -  person Zhiltsoff Igor    schedule 15.01.2021
comment
@DDub Кроме того, что не так с getThroughBlocks? Вы говорите о getThroughSameArgBlocks в loop? Я не проверял определение ArrowLoop законов - какой из них выглядит шатким?   -  person Zhiltsoff Igor    schedule 15.01.2021
comment
delay a >>> someSP теоретически предоставит a данных за один тик для someSP. В синхронной схеме это позволило бы someSP вычислить выходную ценность одного тика. Имейте в виду, что arr для StreamProcessor действительно создает синхронную схему в силу того, что в ней точно чередуются Get и Put. Однако, если бы было 5 Put на Get, тогда результаты действительно были бы асинхронными по отношению к входам, и delay казался бы немного странным.   -  person DDub    schedule 15.01.2021
comment
Да, я про getThroughSameArgBlocks. Я не знаю, какой закон может нарушиться (если таковой имеется), но меня настораживает, что вы дублируете значения из входного потока.   -  person DDub    schedule 15.01.2021
comment
@DDub, как бы вы записали loop? Я тестировал свой фрагмент на процессорах с consts в качестве блоков - отлично работает. Я еще немного подумаю о тестировании и напишу еще один комментарий. Что касается delay, позвольте мне поспать на этом :). Моя электроника (или что там еще) довольно ржавая, так что я не сразу пойму. Спасибо!   -  person Zhiltsoff Igor    schedule 16.01.2021

Ответы (1)


arrow_upward
1
arrow_downward

Единственный известный мне закон, относящийся к ArrowCircuit, на самом деле относится к аналогичному классу ArrowInit из Причинно-следственные коммутативные стрелки, в которых говорится, что delay i *** delay j = delay (i,j). Я почти уверен, что ваша версия удовлетворяет этому (и выглядит вполне разумной реализацией), но это все же немного странно, учитывая, что StreamProcessor не синхронный.

В частности, синхронные схемы следуют схеме, когда один вход производит один выход. Например, если у вас есть Circuit a b и предоставлено значение типа a, вы получите один и только один результат b. Таким образом, задержка в один тик, которую вводит delay, представляет собой задержку одного выхода на один шаг.

Но с асинхронными схемами дела обстоят немного странно. Рассмотрим пример:

runStreamProcessor :: StreamProcessor a b -> [a] -> [b]
runStreamProcessor (Put x s) xs = x : runStreamProcessor s xs
runStreamProcessor _ [] = []
runStreamProcessor Halt _ = []
runStreamProcessor (Get f) (x:xs) = runStreamProcessor (f x) xs

multiplyOneThroughFive :: StreamProcessor Int Int
multiplyOneThroughFive = Get $ \x -> 
  Put (x*1) $ Put (x*2) $ Put (x*3) $ Put (x*4) $ Put (x*5) multiplyOneThroughFive

Здесь multiplyOneThroughFive производит 5 выходов на каждый вход, который он получает. Теперь рассмотрим разницу между multiplyOneThroughFive >>> delay 100 и delay 100 >>> multiplyOneThroughFive:

> runStreamProcessor (multiplyOneThroughFive >>> delay 100) [1,2]
[100,1,2,3,4,5,2,4,6,8,10]
> runStreamProcessor (delay 100 >>> multiplyOneThroughFive) [1,2]
[100,200,300,400,500,1,2,3,4,5,2,4,6,8,10]

Установка delay в другую точку схемы фактически заставила нас выдать другое количество результатов. В самом деле, кажется, что схема в целом претерпела задержку в 5 тиков вместо задержки в 1 тик. Это определенно было бы неожиданным поведением в синхронной среде!

person DDub    schedule 16.01.2021
comment
Короче говоря, если мы поместим delay a в конце серии композиций, мы получим эту фактическую «задержку в один тик», тогда как если она появится где-то посередине, это a может стать входом в некоторой асинхронной схеме. , что потребовало бы нескольких тиков для вывода. Я правильно понял ответ? - person Zhiltsoff Igor; 16.01.2021
comment
Да, это моя мысль. Непонятно, что это плохо! Но стоит отметить. - person DDub; 16.01.2021