История языка Balsa

[vak]

Вначале было слово
Вначале была статья Тони Хоара "Communicating Sequential Processes" 1978 года. Да, сэр Хоар - тот самый, который разработал язык Алгол-60 и получил за это Тьюринговскую премию. В статье он описывает некий вариант языка программирования с концепцией существенного параллелизма. Он не ставил задачу полностью определить язык, так только, набросал несколько идей с высоты своего гения. Насколько я знаю, никто так и не сделал реальный язык програмирования, но математикам идея понравилась, и они часто используют нотацию Хоара в своих статьях для рассуждения о параллельных процессах.

Пример программы в нотации Хоара: решето Эратосфена.

[SIEVE(i:1..100)::
  p,mp:integer;
  SIEVE(i-l)?p;
  print!p;
  mp := p; comment mp is a multiple of p;
 *[m:integer; SIEVE(i-l)?m ->
   *[m > mp -> mp := mp + p];
    [m = mp -> skip
    []m < mp -> SIEVE(i + l)!m
] ]
||SIEVE(0)::print!2; n:integer; n := 3;
    *[n < 10000 -> SIEVE(1)!n; n := n + 2]
||SIEVE(101)::*[n:integer; SIEVE(100)?n -> print!n]
||print::*[(i:0..101) n:integer; SIEVE(0?n --> ...]
]

Гении не ходят в одиночку. В 1985 году в Калифорнийском технологическом институте Алан Мартин обнаружил, что такой язык замечательно преобразуется в асинхронные цифровые схемы. Его статья "Compiling Communicating Processes into Delay-Insensitive VLSI Circuits" стала отправной точкой для многочисленных последователей. Мартин не изобретал язык, его увлекала исключительно возможность построения схем. Но главное - он распахнул дверь в огромную неисследованную область. Забегая вперед, стоит упомянуть, что два года назад Калтех отмечал 25-летие первого в мире асинхронного процессора, созданного под руководством профессора Алана Мартина.

Мощная бронебойная сила подошла в виде голландского математика Kees van Berkel из университета Eindhoven. В своей основополагающей работе 1993 года "Handshake circuits: an asynchronous architecture for VLSI programming" (ранний вариант в виде PDF) он досконально математически исследовал всю область асинхронных цифровых цепей и элементарных составных компонентов. Осталось дело за практиками. По ходу дела ван Беркель доопределил язык, унаследованный от Хоара, и назвал его Tangram. Вот к примеру простейший компонент типа буфер:

(a?W & c!W) · |[ x, y: var W | a?x; #[(a?y || c!x); (a?x || c!y)] ]|

Он преобразуется в следующую схему:


Идею Танграма подхватила фирма Philips. В недрах её исследовательского отделения была разработана коммерческая реализация тулчейна, а в 2003 отпочкована в виде отдельной фирмы. Первым продуктом компании был асинхронный процессор 80с51. В 2006 году был разработан асинхронный процессор с архитектурой ARM. По слухам, большинство чипованных кредитных карт и биометрических паспортов в мире сделано на процессорах этой фирмы. По каким-то причинам в 2009 году Филипс решил закрыть этот бизнес. Фирма Handshake Solutions внезапно канула в небытие вместе со всем софтом.

Но технология не умерла, нет: на помощь пришли британцы. С конца 90-х в университет Манчестера разрабатывался альтернативный вариант реализации идей ван Беркеля: упомянутый в предыдущем посте язык Balsa. Хотя работа и остановилась несколько лет назад, исходные тексты вполне доступны. Имеется описание языка и софта. Язык сильно ушёл от Хоара и стал вполне читабельным. Показанный выше буфер на Бальсе выглядит так:

type word is 8 bits

procedure buffer (input a: word; output c: word) is
local
    variable x, y: word
begin
    a -> x;
    loop
        a -> y || c <- x;
        a -> x || c <- y
    end
end

Comments

[ircicq.livejournal.com]

В 90-х был популярен Occam.
Он ведь тоже для асинхронных схем.

[evol-of-sorrow.livejournal.com]

Турбо балсаль :-)

[kondybas.livejournal.com]

Ну, хорошо, а как всю эту асинхронную ботву можно применить в этих наших существенно параллельных энторнетиках?

[spamsink.livejournal.com]

25-летие первого в мире асинхронного процессора

МИКРОпроцессора, конечно, потому что просто процессоры бывали асинхронные как минимум 50 лет назад.

[mtve.livejournal.com]

очень круто!

[codedot.livejournal.com]

Я несколько лет занимаюсь системами/сетями взаимодействия (interaction nets/interaction systems), в основном, в связи с λ-исчислением. Я заметил, что Вас заинтересовал подкласс interaction systems, называемый hard interaction systems, hardware-применения которых обычно называют как clockless computation и/или handshake technology. В своих поисках мне попались несколько статей, из них в своем архиве у меня лежат три из них. Я подумал, что они Вас могут заинтересовать:

Arjan Bink and Mrk de Clercq, Handshake Solutions, and Richard York, ARM. ARM996HS Synthesizable CPU with Clockless Technology (2006);
Denis Bechet, Sylvain Lippi. Universal Boolean Systems (2008);
Denis Bechet, Sylvain Lippi. Hard combinators (2008).

Я положил все три документа в виде PDF на Dropbox:

https://www.dropbox.com/sh/mv6a1x9lql6y3wg/AAAdSDegYkE7wRRSBFsWfOTra

[sir66.livejournal.com]

В свое время вроде много писалось про то, что подобные схемы хорошо порождаются при использовании функциональных языков. Вроде все получалось очень красиво. Эта тема совсем заглохла?

[juan_gandhi]

Пай-калкулюс же.