occam

Occam
Парадигма	конкурентні обчислення, процедурне програмування і імперативне програмування
Дата появи	1983
Творці	David Mayd
Розробник	Inmosd
Під впливом від	Взаємодія послідовних процесів

Occam — мова паралельного програмування високого рівня, розроблена на початку 1980-х років групою вчених з Оксфорду під керівництвом Девіда Мея за завданням англійської компанії INMOS Ltd. в рамках робіт зі створення трансп'ютерів. Названий на честь англійського філософа XIV століття Вільяма Оккамського, а його сентенція, відома як бритва Оккама, є девізом проекту.

Між мовою Occam і трансп'ютерами існує безпосередній зв'язок: INMOS-трансп'ютери спроектовані так, щоб об'єкти й конструкції Occam реалізовувалися у їхній системі команд найкращим чином. Фактично, трансп'ютер є «кремнієвою реалізацією» мови Occam. Довгий час INMOS стверджувала, що трансп'ютерам не потрібна система програмування типу «Асемблер», оскільки її цілком замінює Occam.

Проте, Occam є типовою мовою високого рівня, синтаксично схожою на Паскаль та Сі.

В основі мови лежить так звана CSP (концепція комунікуючих послідовних процесів), розроблена Тоні Гоаром. По суті, CSP — це формалізм для опису відповідної обчислювальної моделі, досить виразний, щоб на ньому можна було записувати та доводити теореми, досить потужний і однозначний, щоб бути мовою програмування (відомо кілька реалізацій). Згідно CSP, спочатку вводиться безліч елементарних подій (алфавіт), потім з них конструюються процеси, причому з тільки що описаних процесів можна будувати нові. Процеси, які виконуються паралельно, обмінюються інформацією, використовуючи безбуферний обмін інформацією типу «Рандеву» між парою процесів за допомогою спеціального об'єкта — каналу. При взаємодії той учасник обміну, який звернувся до каналу першим, чекає готовності партнера (точки рандеву); при настанні останньої ініціюється обмін. Використання загальної для декількох паралельних процесів пам'яті в CSP не допускається.

Базовим поняттям мови Occam є обчислювальний процес; основною характеристикою процесу є те, що він може бути розпочатий і завершений. У мові визначено кілька простих процесів: процес привласнення, процеси введення і виведення через канал (позначаються символами «?» і «!»), формальні процеси SKIP і STOP (перший завершується відразу ж, другий — ніколи), процеси читання таймера і таймерної затримки. Всі інші процеси можуть бути отримані ієрархічною побудовою. Для цієї мети Occam надає набір конструкторів процесів: 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 частиною ідентифікатора і не несе ніякого спеціального навантаження. Символ «двокрапка»: має значення «кінець опису». Occam чутлива до великих/малих букв у ідентифікаторах.

Цікавою особливістю мови Occam є включення індентації (відступів, «драбинки») в його синтаксис. Цей популярний і вельми виразний засіб виділення структури в Occam є єдиним способом вказівки області дії конструкторів. В ряду безумовних переваг такого рішення можна назвати зменшення кількості службових символів при записі конструкції (відпадає необхідність в словах типу BEGIN-END, або фігурних дужках) і стандартизація оформлення текстів, що підвищує їх читабельність.

  Приклад важливості «драбинки»:
    SEQ
      proc1()
      PAR
        proc21()
        proc22()
      proc3()
  спершу тут буде виконаний процес proc1, потім буде паралельно виконуватися proc21 та proc22, 
  і після закінчення найбільш тривалого з них починається proc3. Якщо змістити виклик proc3 
 на рівень вправо, то proc3 починається одночасно з proc21 і proc22:
    SEQ
      proc1()
      PAR
        proc21()
        proc22()
        proc3()

Версії та реалізації

Офіційно у складі TDS (Transputer Development System), компанією INMOS Ltd. були випущені реалізації Occam 1.0, Occam 2.0 і Occam 2.1. Після покупки компанії і згортання розробок по трансп'ютерному проекту, розробниками Occam була опублікована специфікація Occam 3. Пізніше група ентузіастів здійснила реалізацію мови Occam 2.5, яка являла собою Occam 2.1 з деякими нововведеннями з Occam 3. Останній же в повному обсязі реалізований не був.

Розвиток мови Occam ішов у бік додавання нових типів даних, високорівневих понять і засобів, що полегшують програмування.

Існують реалізації Occam для інших (не трансп'ютерних архітектур), в основному, аматорські.

Відомі також бібліотеки, які реалізують примітиви базової для Occam концепції CSP, що дозволяє програмувати в стилі Occam на інших мовах.

Дивитись також

• OpenMP
• Parallel computing
• Трансп'ютер

Література

• Geraint Jones; Michael Goldsmith (2001). Programming in occam®2 (англ.). Архів оригіналу за 21 грудня 2018. Процитовано 24 червня 2019.

Посилання

• The Occam Archive
• CSP [Архівовано 1 лютого 2021 у Wayback Machine.]
• Internet Parallel Computing Archive: Occam (Документация и реализации)
• The Transterpreter, «Транстерпретер», виртуальная occam-машина [Архівовано 3 березня 2017 у Wayback Machine.]
• KRoC — Kent Retargettable occam Compiler, реализация Occam 2.5 [Архівовано 15 липня 2020 у Wayback Machine.]
• Учебник Occam