Планкалкюль

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

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

Історія

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

	Пів року поступового вступу до формальної логіки. Я перевідкрив там багато моїх попередніх думок. (Комбінаторика умов = логіка висловлень; вчення про інтервали = теорія ґраток). Зараз я планую створення "Числення планів". Для цього треба роз'яснити ряд понять. Оригінальний текст (нім.) 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.
— Конрад Цузе, запис в нотатнику

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

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

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

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

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

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

Опис

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

• операції присвоєння
• виклик підпрограм (але не рекурсію)
• умовні переходи
• цикли
• арифметику з рухомою комою
• масиви та ієрархічні структури даних
• оброблення винятків.^[]

Типи даних

Єдиним примітивним типом даних у Plankalkül є булевий (в авторській термінології нім. Ja-Nein-Werte, так-ні значення). Він позначається ідентифікатором ${\displaystyle S0}$. Всі інші типи є композитними і будуються з примітивного за допомогою «масивів» і «записів». Так, послідовність із восьми біт (яку в сучасній термінології можна вважати байтом) позначається як ${\displaystyle 8\times S0}$, а булева матриця розміром ${\displaystyle m}$ на ${\displaystyle n}$ — ${\displaystyle m\times n\times S0}$.

Допускається також скорочена форма запису ${\displaystyle S1\cdot n}$ замість ${\displaystyle n\times S0}$.

Допустимими значеннями типу ${\displaystyle S0}$ є ${\displaystyle 0}$ і ${\displaystyle L}$. Послідовність із 4 біт можна записати, наприклад, як L00L, але коли вона позначає числа, можна використовувати десяткове позначення 9.

Запис із двох компонентів ${\displaystyle \sigma }$ і ${\displaystyle \tau }$ записується як ${\displaystyle (\sigma ,\tau )}$.

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

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

${\displaystyle S0}$		булеве значення (біт)
${\displaystyle S1\cdot n}$		послідовність із n біт
${\displaystyle A1}$	${\displaystyle S1\cdot 3}$	координата дошки
${\displaystyle A2}$	${\displaystyle 2\times A1}$	клітинка дошки (наприклад L00, 00L позначає e2 в алгебраїчній нотації)
${\displaystyle A3}$	${\displaystyle S1\cdot 4}$	фігура (наприклад 00L0 — білий король)
${\displaystyle A4}$	${\displaystyle (A2,A3)}$	фігура на дошці (наприклад, L00, 00L; 00L0 — білий король стоїть на клітинці e2)
${\displaystyle A5}$	${\displaystyle 64\times A3}$	стан дошки (розташування фігур, послідовний опис стану всіх 64 клітинок дошки)
${\displaystyle A10}$	${\displaystyle (A5,S0,S1\cdot 4,A2)}$	ігрова ситуація (${\displaystyle A5}$ — розташування фігур, ${\displaystyle S0}$ — чий хід, ${\displaystyle S1\cdot 4}$ — можливість здійснити кожну з 4 рокіровок, A2 — дані про клітинку на яку можна робити взяття на проході

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

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

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

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

${\displaystyle {\begin{matrix}V\\0\end{matrix}}}$, ${\displaystyle {\begin{matrix}Z\\2\end{matrix}}}$, ${\displaystyle {\begin{matrix}C\\31\end{matrix}}}$ і т. ін.

Програми і підпрограми позначаються буквою P. Наприклад ${\displaystyle P13}$, ${\displaystyle P5\cdot 7}$.

Результат роботи підпрограми ${\displaystyle P13}$ збережений нею в змінну ${\displaystyle {\begin{matrix}R\\0\end{matrix}}}$ доступний для інших підпрограм в змінній ${\displaystyle {\begin{matrix}R17\\0\end{matrix}}}$, і читання цієї змінної також передбачає виклик відповідної підпрограми.

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

Plankalkül дає змогу отримати доступ до окремих елементів змінної, використовуючи «індекс компоненти» (нім. Komponenten-Index). Якщо програма, наприклад, отримує на вхід у змінній ${\displaystyle {\begin{matrix}V\\0\end{matrix}}}$ значення типу ${\displaystyle A10}$ (ігрова ситуація), то ${\displaystyle {\begin{matrix}V\\0\\0\end{matrix}}}$ — дає стан дошки, ${\displaystyle {\begin{matrix}V\\0\\0\cdot i\end{matrix}}}$ — фігуру на i-тій клітинці, а ${\displaystyle {\begin{matrix}V\\0\\0\cdot i\cdot j\end{matrix}}}$ j-тий біт і-тої фігури.

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

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

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

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

В рядку ${\displaystyle S}$ типи ${\displaystyle S0}$ і ${\displaystyle S1}$ можна скорочувати до ${\displaystyle 0}$ і ${\displaystyle 1}$ відповідно.

Приклади:

${\displaystyle {\begin{array}{r|l}&V\\V&3\\K&\\S&m\times 2\times 1\cdot n\end{array}}}$	змінна V3 — це список з ${\displaystyle m}$ пар значень типу ${\displaystyle S1\cdot n}$
${\displaystyle {\begin{array}{r|l}&V\\V&3\\S&m\times 2\times 1\cdot n\end{array}}}$	Можна також не наводити рядок K, якщо він порожній. Тому цей запис еквівалентний наведеному вище.
${\displaystyle {\begin{array}{r|l}&V\\V&3\\K&i\cdot 0\cdot 7\\S&0\end{array}}}$	Значення восьмого біта (7), першої (нульової) пари, і-того елементу змінної V3, має булевий тип (${\displaystyle S0}$).

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

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

Присвоєння

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

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

${\displaystyle {\begin{array}{r|lll}&Z+1&\Rightarrow &Z\\V&1&&1\\\end{array}}}$

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

${\displaystyle {\begin{array}{r|lll}&Z+1&=&Z\\V&1&&1\\K&i&&i+1\\\end{array}}}$

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

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

Оператори

Зліва від оператора присвоєння записується вираз (нім. Ausdrücke), що описує значення, яке треба присвоїти змінній. Вирази можуть використовувати арифметичні оператори, булеві оператори й оператори порівняння (${\displaystyle =,\neq ,\leq }$ і т.п).

Булеві оператори застосовуються до типу ${\displaystyle S0}$:

• ${\displaystyle {\begin{matrix}{\overline {V}}\\0\end{matrix}}}$ - заперечення
• ${\displaystyle {\begin{matrix}V&\lor &V\\0&&1\end{matrix}}}$ - диз'юнкція
• ${\displaystyle {\begin{matrix}V&\land &V\\0&&1\end{matrix}}}$ - кон'юнкція
• ${\displaystyle {\begin{matrix}V&\rightarrow &V\\0&&1\end{matrix}}}$ - обернення
• ${\displaystyle {\begin{matrix}V&\sim &V\\0&&1\end{matrix}}}$ - ^[en]
• ${\displaystyle {\begin{matrix}V&{\cancel {\!\sim \!\!}}&V\\0&&1\end{matrix}}}$ - виняткова диз'юнкція

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

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

Опис програми

Plankalkül 2000

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

Примітки

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 — .
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.

Література

• Zuse, Konrad (1945). (PDF). Архів оригіналу за 10 лютого 2012. {{}}: Cite має пустий невідомий параметр: |1= ()
• Zuse, Konrad (1948/49). «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben». Arch. Math. 1, pp. 441–449, 1948/49.
• Der Plankalkül. / Zuse, Konrad / Gesellschaft für Mathematik und Datenverarbeitung. / BMBW — GMD — 63 — 1972. — Nr.63.(нім.)
• ; Wössner, Hans (1972). (PDF) (англ.). Архів оригіналу (pdf) за 20 лютого 2009.(HTML версія)
• Knuth, Donald Ervin; Pardo, Luis Trabb (1976). (PDF). Stanford University, Computer Science Department. Архів оригіналу (PDF) за 12 вересня 2017. Процитовано 28 грудня 2017.
• Petzold, Hartmut (1992). Moderne Rechenkünstler. Die Industrialisierung der Rechentechnik in Deutschland. München: C.H. Beck Verlag.
• Giloi, Wolfgang (1997). Konrad Zuse's Plankalkül: The First High-Level "non von Neumann" Programming Language. IEEE Annals of the History of Computing. 19 (2). doi:10.1109/85.586068.
• Metropolis, Nicholas. History of Computing in the Twentieth Century. Elsevier. ISBN .
• Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike (2000). (PDF) (англ.). Архів оригіналу за 28 листопада 2002.
• Rojas, Raúl; Göktekin, Cüneyt; Friedland, Gerald; Krüger, Mike; Scharf, Ludmila (2004). (PDF). doi:10.1007/978-3-642-18631-8_9. Архів оригіналу (PDF) за 1 травня 2006.
• Hellige, Hans Dieter (ed.) (2004). Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Berlin: Springer. ISBN .
• ENCYCLOPEDIA OF COMPUTERS AND COMPUTER HISTORY http://page.mi.fu-berlin.de/rojas/pub/computer_history/m_z/plankalkuel.pdf

Посилання

• (нім.)
• (нім.)
• (англ.)
• https://github.com/timfel/plankalkul2ruby
• https://github.com/Hovestar/Plankalkul
• https://www.chessprogramming.org/Konrad_Zuse#Plankalk.C3.BCl_and_Chess
• http://www.cs.ru.nl/bachelors-theses/2010/Bram_Bruines___0213837___Plankalkul.pdf