anhinga_anhinga (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
anhinga_anhinga) wrote2015-12-27 06:28 pm
anhinga_anhinga) wrote2015-12-27 06:28 pm
Dataflow programming and linear models of computation
https://www.youtube.com/watch?v=fEWcg_A5UZc
More on linear models of computation:
https://github.com/anhinga/fluid contains open source code, demo videos, and links to the reference paper and other preprints written by our group on this topic.
We finally have a model of computation which allows us to continuously deform programs and, moreover, to represent large classes of programs by matrices of real numbers.
We consider classes of computations which admit taking linear combinations of execution runs. Two well known large classes of computations with this property are probabilistic sampling and generalized animation. Both allow for enough higher-order constructions to make us believe that limiting consideration to either of these two classes is not a restriction of generality compared to general-purpose computations.
Since both probabilistic sampling and generalized animation represent stream-based computing architecture, it is natural to consider dataflow programming in this context. We experimented with several different dataflow architectures (the animation above demonstrates the first of the architectures we considered).
We eventually obtained the following solution. If one takes a countable number of built-in stream transformers of one's choice (usually, one takes a finite number of those, and then considers a countable number of copies of each), one can then take each input to be a countable sum of all outputs.
The way to think about this is to say that the set of built-in transformers defines a language, and the coefficients in the countable sums define a program in that language. So a program is defined by a countable-sized matrix; usually one requires that only a finite number of those coefficients are non-zero in order to fit all this into a finite machine.
Then one can change the program in a continuous fashion by continuously changing the matrix coefficients. Because a countable-size matrix has a countable number of matrix elements, one can compute the matrix elements themselves via the streams of real numbers computed by the program itself, thus enabling a variety of higher-order mechanisms (the continuous version of self-modifying code).
no subject
https://www.youtube.com/watch?v=KZHQxdZUlSU
https://www.youtube.com/watch?v=rulK7l4jS-o
https://www.youtube.com/watch?v=-pFil1_GEA4
These were implemented using the third of the architectures we considered (which was based on the matrix representation mentioned in the post).
no subject
no subject
Вообще говоря, эта область любит отрицательные вероятности. С практической точки зрения можно обойтись без них (правда, с некоторыми потерями), но концептуально связь с квантовой теорией здесь очень тесная (обсуждение и ссылки в секции 1.2 статьи).
Дальше, в статье есть "математическая начинка" (секция 4, фактически это вторая статья, связанная с первой пока что скорее исторически и мотивационно, и помещенная в тот же текст в надежде, что связи со временем станут глубже; а так это две независимые статьи (всё, что до и после секции 4, и секция 4)). И там есть пространство стрелок, и связанный с ним мотив инволюции, и архитектура вычислений с инволюциями, и "моральная" связь с квантовыми алгоритмами там очень сильная (секции 4.1, 4.5, 4.14).
Категорная часть комментария, которая есть у меня, состоит в том, что в контексте обогащенных категорий пространство стрелок (domain of arrows) очень сильно связано с профункторами (дистрибьюторами), и это тема крайне богатая, с большим потенциалом.
no subject
как только рассматриваем формулу для их композиции, так они уже появляются...
no subject
linear operator corresponding to the program if random < α then P else Q is a linear combination of
the linear operators corresponding to programs P and Q with coefficients α and 1−α.
Это звучит очень похоже на то, что было у меня здесь: Тогда конструкция if-else точно есть в Set(относительно декартова произведения), вроде бы присутствует в Vect (относительно тензорного), во всяком случае для конечномерных, и в Top вроде тоже есть (гомотопия, относительно произведения топ. пространств), но кажется в Top не может быть while.
no subject
В контексте денотационной векторной семантики, есть статья Dexter Kozen, Semantics of probabilistic programs (it seems that scholar.google.com points to its free download), откуда это изначально ко мне пришло. Там линейные операторы на пространстве знакопеременных мер, и, что касается Scott topology, то обычный Scott domain подвероятностных мер вложен в положительных конус этик векторных пространств, и семантика while там аккуратно сделана через неподвижные точки, в обычной манере для топологий Скотта.
В контексте экспериментов с synchronous dataflow (которые по сути есть операционная векторная семантика), ситуация в чем-то похожа на обычную машину фон Неймана. Машина описывается программой "while(true) {рабочий шаг}", только здесь за рабочий шаг прокручивается весь огромный "арифмометр", ассоциированный с графом dataflow. Поскольку рабочий шаг имеет сложность "близкую к фиксированной", как и в машине фон Неймана приходится выражать while через if. Но в машине фон Неймана это делается условным переходом контроля исполнения, а здесь это делается по сути "условным перенаправлением потоков по графу dataflow".
Работа со списками действительно похожа, интересно было бы посмотреть подробнее...
no subject