Планкалкюль

Шаблон:Мова програмування Планкалкюль (Шаблон:Lang-de) — перша у світі мова програмування високого рівня, створена німецьким інженером Конрадом Цузе в 1943—1945 роках і вперше опублікована в 1948 році.

Історія

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

Табличка на будинку в Шаблон:Iw в якому Цузе працював над розробкою Plankalkül

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

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

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

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

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

Опис

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

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

Типи даних

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

Допускається також скорочена форма запису $S1\cdot n$ замість $n\times S0$Шаблон:Sfn.

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

Запис із двох компонентів $\sigma$ і $\tau$ записується як $(\sigma ,\tau )$Шаблон:Sfn.

Тип (Шаблон:Lang-de) у Plankalkül складається з трьох елементів: структури і її складових (Шаблон:Lang-de), прагматичного змісту (Шаблон:Lang-de) і можливого обмеження (Шаблон:Lang-de) для значень типуШаблон:Sfn.

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

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

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

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

• вхідні дані (Шаблон:Lang-de) — їх позначають буквою V;
• проміжні дані (Шаблон:Lang-de) — позначають буквою Z;
• константи (Шаблон:Lang-de) — позначають буквою С;
• вихідні дані (Шаблон:Lang-de) — позначають буквою R.

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

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

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

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

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

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

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

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

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

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

У рядку $S$ типи $S0$ і $S1$ можна скорочувати до $0$ і $1$ відповідноШаблон:Sfn.

Приклади:

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

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

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

Присвоєння

Цузе ввів у своє числення невідомий для математики символ — присвоєння (Шаблон:Lang-de), «$\Rightarrow$». Саме використання поняття присвоєння означає перехід від математичного мислення до інформатикиШаблон:Sfn.

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

$\begin{array}{cccc}& Z+1& \Rightarrow & Z\\ V& 1& & 1\end{array}$

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

$\begin{array}{cccc}& Z+1& =& Z\\ V& 1& & 1\\ K& i& & i+1\end{array}$

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

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

Оператори

Зліва від оператора присвоєння записується вираз (Шаблон:Lang-de), що описує значення, яке треба присвоїти змінній. Вирази можуть використовувати арифметичні оператори, булеві оператори й оператори порівняння ($=,\ne ,\le$ тощо)Шаблон:Sfn.

Булеві оператори застосовуються до типу $S0$Шаблон:Sfn:

• $\begin{array}{c}\bar{V}\\ 0\end{array}$ — заперечення
• $\begin{array}{ccc}V& \vee & V\\ 0& & 1\end{array}$ — диз'юнкція
• $\begin{array}{ccc}V& \wedge & V\\ 0& & 1\end{array}$ — кон'юнкція
• $\begin{array}{ccc}V& \to & V\\ 0& & 1\end{array}$ — обернення
• $\begin{array}{ccc}V& \sim & V\\ 0& & 1\end{array}$ — Шаблон:Iw
• $\begin{array}{ccc}V& \cancel{\sim }& V\\ 0& & 1\end{array}$ — виняткова диз'юнкція

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

Шаблон:Section-stub

Plankalkül 2000

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

Література

• Шаблон:Cite book
• 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.Шаблон:Ref-de
• Шаблон:Cite journal(HTML версія)
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• ENCYCLOPEDIA OF COMPUTERS AND COMPUTER HISTORY http://page.mi.fu-berlin.de/rojas/pub/computer_history/m_z/plankalkuel.pdf

Посилання

• Берлінський центр інформатики ім. Конрада ЦузеШаблон:Ref-de
• Список літератури з мови ПланкалкюльШаблон:Ref-de
• Опис мови Планкалкюль на сайті Хорнста Цузе в Технічному університеті м. Берлін Шаблон:Ref-en
• 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