Планкалкюль

(Перенаправлено з Plankalkul)

Планкалкюль (нім. Plankalkül — числення планів) — перша у світі мова програмування високого рівня, створена німецьким інженером Конрадом Цузе в 1943-45 році і вперше опублікована в 1948 році.

Планкалкюль
Парадигма Процедурна
Дата появи 1948
Творці Конрад Цузе
Розробник Конрад Цузе
Основні реалізації Plankalkül-Compiler Вільний університет Берліна в 2000
Під впливом від Begriffsschrift[de][1]
Вплинула на Superplan[en] Гайнца Рутисгаузера[en]

Історія ред.

В справі створення обчислювальних машин Цузе був самоуком, і розробляв їх без знання про інші механічні машини, що існували на той час. Для опису логічних схем Цузе винайшов свої власні діаграми і систему нотації, яку він назвав комбінаторикою умов (нім. Bedingungskombinatorik). У 1938-му, після закінчення роботи над Z1, Цузе з'ясував, що числення, яке він незалежно вигадав, уже існує і називається пропозиційним численням.[2] Проте Цузе мав на меті дещо виразніше (пропозиційне числення не повне за Тюрінгом і не здатне описувати навіть прості арифметичні обчислення[3]). Тому в травні 1939-го року він описав свій задум розробити те, що невдовзі стане "Численням планів".[4] У своєму нотатнику Цузе залишив такий запис:

  Пів року поступового вступу до формальної логіки. Я перевідкрив там багато моїх попередніх думок. (Комбінаторика умов = логіка висловлень; вчення про інтервали = теорія ґраток). Зараз я планую створення "Числення планів". Для цього треба роз'яснити ряд понять.
Оригінальний текст (нім.)
Seit etwa einem halben Jahr allmähliches Einführen in die formale Logik. Viele meiner früheren Gedanken habe ich dort wieder gefunden. (Bedingungskombinatorik = Aussagenlogik; Lehre von den Intervallen = Gebietenkalkül). Ich plane jetzt die Aufsetzung des 'Plankalküls'. Hierzu sind eine Reihe von Begriffen zu klären.
 

— Конрад Цузе, запис в нотатнику[2]


 
Табличка на будинку в Гінтерштайні[de] в якому Цузе працював над розробкою Plankalkül

Працюючи над своєю докторською дисертацією, Цузе розробив першу відому формальну систему запису алгоритмів[5], здатну описати розгалуження і цикли[6][7] У 1942-му році він почав писати на Plankalkül програму гри в шахи.[8] У 1944-му році Цузе зустрічався з німецьким логіком і філософом Гайнріхом Штольцом[en], який висловив захоплення тим, як Цузе застосував числення.[9] У 1945-му році Цузе описав Plankalkül в однойменній книжці[10], проте поразка Німеччини в Другій світовій війні завадила йому опублікувати рукопис[6].

Оригінальний опис мови вражає виразними конструкціями і схожістю на сучасні мови, тому складається враження, що вона створена набагато пізніше 1945-го року. Єдиними на час створення Plankalkül працюючими комп'ютерами були ENIAC та Harvard Mark I, жоден з яких не використовував компілятор чи транслятор, а ENIAC треба було перепрограмовувати на кожну нову задачу, переставляючи з'єднання кабелів.[11]

Хоча більшість комп'ютерів Цузе було знищено під час бомбардувань, йому вдалося врятувати один.[12] У травні 1945 Конрад Цузе зі своїм релейним комп'ютером Z4 переїхав із Берліна в альпійське село Гінтерштайн[de].[13] Не маючи змоги продовжувати конструювання комп'ютерів, учений перейшов до суто теоретичних досліджень і присвятив час розробці високорівневої моделі програмування і необхідної для цього мови.[6] У 1948-му році він опублікував статтю в Archiv der Mathematik[en] та виступив із доповіддю на щорічній зустрічі GAMM.[14]

Робота у відриві від інших фахівців Європи і США призвела до того, що лише незначна частина його роботи стала відомою. Повністю роботу Цузе було видано лише в 1972 році.

Сам Цузе не створив жодних програмно-апаратних засобів під реалізацію розробленої ним мови. Перший компілятор мови Планкалкюль (див. Plankalkül 2000) було створено у Вільному університеті Берліна тільки в 2000 році[15], через п'ять років після смерті Конрада Цузе.

Опис ред.

Планкалкюль мала низку особливостей, притаманних сучасним мовам програмування високого рівня:

Типи даних ред.

Єдиним примітивним типом даних у Plankalkül є булевий (в авторській термінології нім. Ja-Nein-Werte, так-ні значення). Він позначається ідентифікатором  . Всі інші типи є композитними і будуються з примітивного за допомогою «масивів» і «записів». Так, послідовність із восьми біт (яку в сучасній термінології можна вважати байтом) позначається як  , а булева матриця розміром   на   —  .[16]

Допускається також скорочена форма запису   замість  .[16]

Допустимими значеннями типу   є   і  . Послідовність із 4 біт можна записати, наприклад, як L00L, але коли вона позначає числа, можна використовувати десяткове позначення 9.[16]

Запис із двох компонентів   і   записується як  .[16]

Тип (нім. Art) у Plankalkül складається з трьох елементів: структури і її складових (нім. Struktur), прагматичного змісту (нім. Typ) і можливого обмеження (нім. Beschränkung) для значень типу.[16]

Конрад Цузе наводить багато прикладів із шахової теорії[17]:

  булеве значення (біт)
  послідовність із n біт
    координата дошки
    клітинка дошки (наприклад L00, 00L позначає e2 в алгебраїчній нотації)
    фігура (наприклад 00L0 — білий король)
    фігура на дошці (наприклад, L00, 00L; 00L0 — білий король стоїть на клітинці e2)
    стан дошки (розташування фігур, послідовний опис стану всіх 64 клітинок дошки)
    ігрова ситуація (  — розташування фігур,   — чий хід,   — можливість здійснити кожну з 4 рокіровок, A2 — дані про клітинку на яку можна робити взяття на проході

Ідентифікатори ред.

Ідентифікатор — це буква за якою йде число.[16] Ідентифікатори для змінних бувають таких видів[18]:

  • вхідні дані (нім. Eingabewerte, Variablen) — їх позначають буквою V;
  • проміжні дані (нім. Zwischenwerte) — позначають буквою Z;
  • константи (нім. Constanten) — позначають буквою С;
  • вихідні дані (нім. Resultatwerte) — позначають буквою R.

Конкретна змінна певного типу унікально ідентифікується за номером, який записується під нею.[16] Наприклад:

 ,  ,   і т. ін.

Програми і підпрограми позначаються буквою P. Наприклад  ,  .[16]

Результат роботи підпрограми   збережений нею в змінну   доступний для інших підпрограм в змінній  , і читання цієї змінної також передбачає виклик відповідної підпрограми.[17]

Доступ до компонентів даних ред.

Plankalkül дає змогу отримати доступ до окремих елементів змінної, використовуючи «індекс компоненти» (нім. Komponenten-Index). Якщо програма, наприклад, отримує на вхід у змінній   значення типу   (ігрова ситуація), то   — дає стан дошки,   — фігуру на i-тій клітинці, а   j-тий біт і-тої фігури.[17]

У сучасних мовах програмування це відповідає нотації V0[0], V0[0][i], V0[0][i][j] (хоча для доступу до окремого біта в сучасних мовах програмування зазвичай використовують бітові маски).

Двовимірний синтаксис ред.

Через те що тип змінної, її номер та індекси компонентів записуються один над одними, для запису кожної інструкції в Plankalkül потрібно кілька рядків.

У першому рядку завжди вказано тип змінної, далі — номер змінної, позначений буквою V (нім. Variablen-Index), далі індекси підкомпонентів, позначені K (нім. Komponenten-Index), а потім індекс структури (нім. Struktur-Index), позначений літерою S, який описує тип змінної. Тип не обов'язково вказувати, але Цузе зазначає що це полегшує читання і розуміння програми.[19]

В рядку   типи   і   можна скорочувати до   і   відповідно. [19]

Приклади:

  змінна V3 — це список з   пар значень типу  
  Можна також не наводити рядок K, якщо він порожній. Тому цей запис еквівалентний наведеному вище.
  Значення восьмого біта (7), першої (нульової) пари, і-того елементу змінної V3, має булевий тип ( ).

Індексом може бути не тільки константа, а й інша змінна; це позначається за допомогою ліній, що вказують, у який індекс компонентів треба підставити значення змінної:

  Z5-тий елемент змінної V3. Еквівалентно виразу V3[Z5] в сучасних мовах програмування.[19]

Присвоєння ред.

Цузе ввів у своє числення невідомий для математики символ — присвоєння (нім. Ergibt-Zeichen), « ». Саме використання поняття присвоєння означає перехід від математичного мислення до інформатики.[20]

Цузе писав, що запис

 

аналогічний більш традиційній для математики рівності:

 

Прийнято вважати, що Конрад Цузе спочатку використовував для присвоєння символ  , і почав використовувати   під впливом Гайнца Рутисгаузера[en].[19] Кнут і Пардо вважають що Конрад Цузе завжди писав  , а   впровадили видавці твору «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben».[20] На конференції ALGOL 58[en] у Цюріху учасники з європи пропонували використати для оператора присвоєння символ, впроваджений Цузе, але американська делегація наполягла на :=.[19]

Також варто звернути увагу на те, що змінна для результату операції присвоєння, на відміну від більшості сучасних мов, записується справа від оператора.[20] Перше присвоєння значення змінній вважається оголошенням.[19]

Оператори ред.

Зліва від оператора присвоєння записується вираз (нім. Ausdrücke), що описує значення, яке треба присвоїти змінній. Вирази можуть використовувати арифметичні оператори, булеві оператори й оператори порівняння (  і т.п).[21]

Булеві оператори застосовуються до типу  [22]:

  •   - заперечення
  •   - диз'юнкція
  •   - кон'юнкція
  •   - обернення
  •   - заперечення виняткової диз'юнкції[en]
  •   - виняткова диз'юнкція


Операція піднесення до степеня позначається подібно до операції індексування - за допомогою ліній[23]:

 

Виклик підпрограм ред.


Опис програми ред.

Plankalkül 2000 ред.

Для мови Plankalkül важко написати компілятор чи редактор, тому що вона використовує незвичну для сучасних мов двовимірну нотацію, а також опис мови містить деякі логічні суперечності. Тому команда дослідників Вільного університету Берліна під керівництвом Рауля Рохаса розробила підмножину мови Plankalkül та компілятор для неї, яку вони назвали "Plankalkül 2000".[15]


Примітки ред.

  1. https://web.stanford.edu/class/cs208e/cgi-bin/main.cgi/static/lectures/17-ProgrammingEarlyDays/EarlyProgrammingLanguages.pdf
  2. а б Rojas та ін., 2004, с. 3.
  3. Why is propositional logic not Turing complete?. 
  4. Hellige, 2004, с. 216.
  5. Knuth та Pardo, 1976, с. 9.
  6. а б в Giloi, 1997, с. 17-24.
  7. Hellige, 2004, с. 56.
  8. Hellige, 2004, с. 216-217.
  9. Petzold, 1992.
  10. Zuse, 1945.
  11. Rojas та ін., 2000, с. 3.
  12. Zuse, Konrad. The Plankalkül. (англ.) — München/Wien: R. Oldenbourg Verlag, 1989. — P.5 — 244 p. — (Berichte der Gesellschaft für Mathematik und Datenverarbeitung; Nr. 175) — ISSN 0533-9480 — ISBN 3-486-21288-5.
  13. Bauer та Wössner, 1972, с. 678.
  14. Hellige, 2004, с. 89.
  15. а б Rojas та ін., 2000, с. 2.
  16. а б в г д е ж и Bauer та Wössner, 1972, с. 679.
  17. а б в Bauer та Wössner, 1972, с. 680.
  18. Zuse, 1945, с. 10.
  19. а б в г д е Bauer та Wössner, 1972, с. 681.
  20. а б в Knuth та Pardo, 1976, с. 14.
  21. Bauer та Wössner, 1972, с. 682.
  22. Zuse, 1945, с. 49.
  23. Zuse, 1945, с. 45.

Література ред.

Посилання ред.