Occam (Occam)
| Occam | |
|---|---|
| Класс языка | язык программирования, процедурный язык программирования, process-oriented programming language[вд] и язык, использующий отступы[вд] |
| Появился в | 1983 |
| Автор | David May[вд] |
| Разработчик | INMOS |
| Диалекты | occam-π (pi) |
| Испытал влияние | CSP |
| Повлиял на | Ease[англ.] |
Occam — процедурный язык параллельного программирования высокого уровня, разработанный в начале 1980-х годов группой учёных из Оксфорда под руководством Дэвида Мэя (англ. David May) по заданию английской компании INMOS Ltd. в рамках работ по созданию транспьютеров. Назван в честь английского философа XIV века Уильма Оккамского, а его сентенция, известная как бритва Оккама, является девизом проекта.
Между языком Оккам и транспьютерами существует непосредственная связь: INMOS-транспьютеры спроектированы так, чтобы объекты и конструкции Occam’а реализовывались в их системе команд наилучшим образом. Фактически, транспьютер является «кремниевой реализацией» языка Оккам. Долгое время INMOS утверждала, что транспьютерам не требуется система программирования типа «ассемблер», так как её вполне заменяет Occam.
Тем не менее, Оккам является типичным языком высокого уровня, синтаксически похожим на Паскаль или Си.
Теоретические основы
[править | править код]В основе языка лежит так называемая CSP-концепция (концепция взаимодействующих последовательных процессов), разработанная Энтони Хоаром. В сущности, CSP — это формализм для описания соответствующей вычислительной модели, достаточно выразительный, чтобы на нём можно было записывать и доказывать теоремы, и достаточно мощный и однозначный, чтобы являться языком программирования (известно несколько реализаций). Согласно CSP, сначала вводится множество элементарных событий (алфавит), затем из них конструируются процессы, причём из только что описанных процессов можно строить новые. Процессы, протекающие параллельно, обмениваются информацией, используя безбуферный обмен информацией типа «рандеву» между парой (и только парой) процессов посредством специального объекта — канала. При взаимодействии тот участник обмена, который обратился к каналу первым, ожидает готовности партнёра (точки рандеву); при наступлении последней инициируется обмен. Использование общей для нескольких параллельных процессов памяти в CSP не допускается.
Синтаксис и семантика
[править | править код]Базовым понятием языка Оккам является вычислительный процесс; основной характеристикой процесса является то, что он может быть начат и завершён. В языке определено несколько простых процессов: процесс присваивания, процессы ввода и вывода через канал (обозначаются символами ? и !), формальные процессы SKIP и STOP (первый завершается сразу же, второй — никогда), процессы чтения таймера и таймерной задержки. Все остальные процессы могут быть получены иерархическим построением (через ранее определённые). Для этой цели Оккам предоставляет набор конструкторов процессов: SEQ (определяет процесс последовательного выполнения процессов), PAR (определяет процесс параллельного выполнения процессов), а также конструктор условного процесса IF, циклического процесса WHILE, процесса выбора процессов ALT. При этом действует правило, согласно которому составной процесс типа SEQ или PAR считается выполненным, когда завершены все составляющие его процессы. Процессы могут быть поименованы и вызваны по имени с передачей параметров. Процессы SEQ, PAR, IF и ALT могут быть реплицированы (размножены) при помощи репликатора FOR. Процесс ALT (как и PAR) привносит в язык индетерминизм, так как считается, что при одновременном выполнении нескольких условий точно предсказать дальнейший ход событий невозможно.
пример:
Мультиплексор, бесконечно читающий из массива каналов in[] и передающий в общий канал out,
используя промежуточную переменную temp
WHILE TRUE
INT temp :
ALT i=0 FOR N
in[i] ? temp
out ! temp
пример:
Каскад параллельно работающих мультиплексоров.
На входе — массив из M*N каналов in[], на выходе — канал out.
Массив из M каналов ch[] используется для связи между мультиплексорами каскада:
PAR -- каскад параллельных мультиплексоров ввода
PAR i=0 FOR M -- M параллельных мультиплексоров, обрабатывающих по N каналов из in[] каждый
WHILE TRUE
INT temp :
ALT j=i*N FOR N
in[j] ? temp
ch[i] ! temp
WHILE TRUE -- корневой мультиплексор, читающий M промежуточных каналов ch[]
INT temp :
ALT i=0 FOR M
ch[i] ? temp
out ! temp
пример:
Процесс буферизации ввода-вывода.
Запуск процесса buffer( in, out, N) позволяет каналу out отстать от канала in
вплоть на N сообщений, которые будут буферизованы внутри процесса buffer:
PROC buffer( CHAN OF INT in, out, INT N)
CHAN OF INT in.wait, out.wait :
INT n : -- счётчик буферизованных значений
[N]INT buff :
SEQ
n:=0
PAR—input
INT i, any: -- i — указатель записи в буфер
SEQ
i:=0
WHILE TRUE
SEQ
WHILE n<(N-1)
SEQ
in ? buff[i]
n:=n+1
IF
n=1
out.wait ! any
TRUE
SKIP
i:=(i+1) MOD N
in.wait ? any—output
INT j, any: -- j — указатель чтения из буфера
SEQ
j:=0
WHILE TRUE
SEQ
out.wait ? any
WHILE n>0
SEQ
out ! buff[j]
n:=n-1
IF
n=(N-2)
in.wait ! any
TRUE
SKIP
j:=(j+1) MOD N
:
Изучая примеры, следует иметь в виду, что символ «два минуса» -- означает начало комментария до конца строки, а символ «точка» . может быть в Оккаме частью идентификатора и не несёт никакой специальной нагрузки. Символ «двоеточие» : имеет значение «конец описания». Оссам чувствителен к заглавным/строчным буквам в идентификаторах.
Интересной особенностью языка Occam является включение индентации (отступов, «лесенки») в его синтаксис. Это популярное и весьма выразительное средство выделения структуры в Оккаме является единственным способом указания области действия конструкторов. В ряду безусловных достоинств такого решения можно назвать уменьшение количества служебных символов при записи конструкции (отпадает необходимость в словах типа BEGIN-END или фигурных скобках) и вынужденная стандартизация оформления текстов, что повышает их читабельность.
Пример важности «лесенки»:
SEQ
proc1()
PAR
proc21()
proc22()
proc3()
здесь сначала будет выполнен процесс proc1, затем будут параллельно исполняться proc21 и proc22, и лишь после завершения самого длительного из них стартует proc3. Если сдвинуть вызов proc3 на уровень вправо, то порядок вычислений меняется:
SEQ
proc1()
PAR
proc21()
proc22()
proc3()
Здесь proc3 стартует одновременно с proc21 и proc22.
Версии и реализации
[править | править код]Официально, в составе TDS (Transputer Development System), компанией INMOS Ltd. были выпущены реализации Occam 1.0, Occam 2.0 и Occam 2.1. После покупки компании и сворачивания разработок по транспьютерному проекту, разработчиками Оккам в частном порядке была опубликована спецификация Occam 3. Позже группа энтузиастов осуществила реализацию языка Occam 2.5, представлявшего собой Occam 2.1 c некоторыми нововведениями из Occam 3. Последний же в полном объёме реализован не был.
Развитие языка Оккам шло в сторону добавления новых типов данных, высокоуровневых понятий и средств, облегчающих программирование. При этом философия языка не пересматривалась.
Существуют реализации Оккама для других, не-транспьютерных архитектур, в основном, любительские.
Известны также библиотеки, реализующие примитивы базовой для Оккама концепции CSP, что позволяет программировать в стиле Оккама на других языках.
Литература
[править | править код]- Джоунз Г. Программирование на языке Оккам / Пер. с англ. Л. В. Шабанова, под ред. Ю. Г. Дадаева. — М: Мир, 1989. — 208с.: ил. ISBN 5-03-001155-2
Ссылки
[править | править код]- The Occam Archive
- CSP
- Internet Parallel Computing Archive: Occam (Документация и реализации)
- The Transterpreter, «Транстерпретер», виртуальная occam-машина
- KRoC — Kent Retargettable occam Compiler, реализация Occam 2.5
- Учебник Occam
 | Для улучшения этой статьи желательно:
|
