Забег на асимптотику.

[thesz]

Посмотрев на асимптотически интересные результаты работы регулярных выражений, решил вспомнить былое и собрать похожее на потоковых процессорах.

Comments

[beroal]

решил вспомнить былое и собрать похожее на потоковых процессорах
Ну, раньше это называлось автомат. Вход и выход есть.

[thesz]

Не совсем.

Потоковые процессоры могут получать несколько значений, не создавая на выходе ничего. И наоборот: выдавать несколько, не получив ничего.

По-моему, это чуть шире.

PS
Они были придуманы в качестве ответа на проблемы ввода-вывода с помощью ленивых списков.

[_slw]

Потоковые процессоры могут [...] выдавать несколько, не получив ничего.

это как? у них что, клоки есть?

[thesz]

Наоборот. Абстрактные автоматы выглядят тактируемыми (на один входной символ - один выходной и один переход в другое состояние), у потоковых процессоров я могу сделать несколько выходных элементов на один входной: I (\n -> O (n+1) (O (n-1) N)). Получаем один элемент, выдаём два.

И наоборот: I (\a -> I (\b -> O (a+b) N)). Ждём два, выдаём сумму.

[nivanych]

Казалось бы, а причём тут комонады?
Комонады тут совершенно непричём!
А кто может сказать, почему? ;-)