Оккам (язык программирования)

Оккам (англ. Occam) — процедурный язык параллельного программирования высокого уровня, разработанный в начале 1980-х годов группой учёных Оксфордского университета под руководством Дэвида Мэя (англ. David May) по заданию британской компании Inmos^[англ.] в рамках работ по созданию транспьютеров. Назван в честь английского философа XIV века Уильма Оккама, принцип которого, известный как бритва Оккама, избран девизом проекта.

Между языком Оккам и транспьютерами существует непосредственная связь: Inmos-транспьютеры спроектированы так, чтобы объекты и конструкции Оккама реализовывались в их системе команд наиболее эффективным и естественным образом, и чтобы транспьютер фактически являлся «кремниевой реализацией» языка. Долгое время Inoms утверждала, что транспьютерам не требуются низкоуровневые ассемблеры, так как её вполне заменяет высокоуровневый Оккам, синтаксически похожий на Паскаль или Си.

В основе языка лежит теория взаимодействующих последовательных процессов (CSP, communicating sequential processes), разработанная Энтони Хоаром — формализм для описания соответствующей вычислительной модели, достаточно выразительный, чтобы на нём можно было записывать и доказывать теоремы, и достаточно мощный и однозначный, чтобы являться языком программирования (известно несколько реализаций). Согласно концепции сначала вводится множество элементарных событий (алфавит), затем из них конструируются процессы, причём из только что описанных процессов можно строить новые. Процессы, протекающие параллельно, обмениваются информацией, используя безбуферный обмен информацией типа «рандеву» между парой (и только парой) процессов посредством специального объекта — канала. При взаимодействии тот участник обмена, который обратился к каналу первым, ожидает готовности партнёра (точки рандеву); при наступлении последней инициируется обмен. Использование общей для нескольких параллельных процессов памяти в теории взаимодействующих последовательных процессов не допускается.

Базовым понятием языка является вычислительный процесс; основной характеристикой процесса является то, что он может быть начат и завершён. В языке определено несколько простых процессов: процесс присваивания, процессы ввода и вывода через канал (обозначаются символами ? и !), формальные процессы 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       : 

(Символ -- означает начало комментария до конца строки, а символ «точка» (.) — может быть в Оккаме частью идентификатора и не несёт никакой специальной нагрузки. Символ «двоеточие» (:) имеет значение «конец описания». Оккам чувствителен к регистру символов в идентификаторах.)

Стал одним из первых практических языков (наряду с ABC), реализовавшим идеи ISWIM и включивших отступы в синтаксис (правило отступов^[англ.]), таким образом, с помощью отступов указывается область действия конструкторов и отпадает необходимость использования операторных скобок и обеспечивается вынужденная стандартизация оформления текстов:

     SEQ        proc1()        PAR          proc21()          proc22()        proc3() 

В этом фрагменте сначала будет выполнен процесс proc1, затем будут параллельно исполняться proc21 и proc22, и лишь после завершения самого длительного из них стартует proc3. Если сдвинуть вызов proc3 на уровень вправо, то порядок вычислений меняется:

     SEQ        proc1()        PAR          proc21()          proc22()          proc3() 

Здесь proc3 стартует одновременно с proc21 и proc22.

Язык входил в состав среды разработки транспьютеров Inmos — TDS (transputer development system), были выпущены реализации Occam 1.0, Occam 2.0 и Occam 2.1. После поглощения компании и сворачивания разработок по транспьютерному проекту разработчиками языка в частном порядке была опубликована спецификация Occam 3. Позже группа энтузиастов осуществила реализацию языка Occam 2.5, представлявшего собой Occam 2.1 c некоторыми нововведениями из Occam 3. Последний же в полном объёме реализован не был.

Развитие языка шло в сторону добавления новых типов данных, высокоуровневых понятий и средств, облегчающих программирование. При этом философия языка не пересматривалась.

Существуют реализации Оккама для нетранспьютерных архитектур, в основном, любительские.

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

• Джоунз Г. Программирование на языке Оккам / Пер. с англ. Л. В. Шабанова, под ред. Ю. Г. Дадаева. — М.: Мир, 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

В статье есть список источников, но не хватает сносок. Без сносок сложно определить, из какого источника взято каждое отдельное утверждение. Вы можете улучшить статью, проставив сноски на источники, подтверждающие информацию. Сведения без сносок могут быть удалены. (13 ноября 2009)