Планкалкюль

Plankalkül ( немецкое произношение: [ˈplaːnkalkyːl] ) — язык программирования, разработанный для инженерных целей Конрадом Цузе между 1942 и 1945 годами. Это был первый язык программирования высокого уровня , разработанный для компьютера.

Kalkül (от латинского calculus ) — немецкий термин для формальной системы , как в Hilbert-Kalkül , первоначальном названии дедуктивной системы в стиле Гильберта , поэтому Plankalkül относится к формальной системе планирования. ^[2]

В области создания вычислительных машин Цузе был самоучкой и разрабатывал их, не имея знаний о других уже существовавших механических вычислительных машинах, хотя позже (при создании Z3 ) он был вдохновлен книгой Гильберта и Аккермана по элементарной математической логике (см. Принципы математической логики ). ^{[3] : 113, 152, 216} Для описания логических схем Цузе придумал собственную схему и систему обозначений, которую назвал «комбинаторикой условных выражений» ( нем . Bedingungskombinatorik ). Закончив Z1 в 1938 году, Цузе обнаружил, что независимо разработанное им исчисление уже существовало и было известно как исчисление высказываний . ^{[4] : 3} Однако Цузе имел в виду нечто гораздо более мощное (исчисление высказываний не является полным по Тьюрингу и не способно описывать даже простые арифметические вычисления ^[5] ). В мае 1939 года он описал свои планы по развитию того, что впоследствии стало Планкалкюлем. ^{[3] : 113, 152, 216} Он записал в своей записной книжке следующее:

Работая над докторской диссертацией, Цузе разработал первую известную формальную систему записи алгоритмов ^{[6] : 9,} способную обрабатывать ветви и циклы. ^{[7] : 18  [3] : 56} В 1942 году он начал писать шахматную программу на языке Plankalkül. ^{[3] : 216–217} В 1944 году Цузе встретился с немецким логиком и философом Генрихом Шольцем , который выразил признательность Цузе за использование логического исчисления . ^[8] В 1945 году Цузе описал Plankalkül в неопубликованной книге. ^[9] Однако крах нацистской Германии помешал ему представить свою рукопись. ^{[7] : 18}

В то время в мире существовало всего два работающих компьютера: ENIAC и Harvard Mark I , ни один из которых не использовал компилятор, и ENIAC приходилось перепрограммировать для каждой задачи, меняя способ подключения проводов. ^{[4] : 3}

Хотя большинство его компьютеров были уничтожены бомбами союзников, Цузе удалось спасти одну машину, Z4 , и перевезти ее в альпийскую деревню Хинтерштайн ^{[6] : 8} (часть Бад-Хинделанга ).

Первая попытка разработать алгоритмический язык была предпринята в 1948 году К. Цузе. Его обозначения были весьма общими, но предложение так и не получило должного внимания.

—  Хайнц Рутисхаузер , создатель АЛГОЛА

Не имея возможности продолжать строить компьютеры, что также было запрещено союзными державами ^[10] , Цузе посвятил свое время разработке модели и языка программирования более высокого уровня. ^{[7] : 18} В 1948 году он опубликовал статью в Archiv der Mathematik и представил ее на ежегодном собрании GAMM . [ ^{3] : 89} Его работа не привлекла особого внимания. ^{[ необходима цитата ]} В лекции 1957 года Цузе выразил надежду, что Plankalkül, «после некоторого времени в виде Спящей красавицы , все же оживет». ^{[4] : 3} Он выразил разочарование тем, что разработчики ALGOL 58 никогда не признавали влияние Plankalkül на их собственную работу. ^{[7] : 18  [6] : 15}

Plankalkül был переиздан с комментариями в 1972 году. ^[11] Первый компилятор для Plankalkül был реализован Иоахимом Хохманном в его диссертации 1975 года. ^[12] Другие независимые реализации последовали в 1998 ^[13] и 2000 годах в Свободном университете Берлина . ^{[4] : 2}

Plankalkül проводит сравнения с языком APL и реляционной алгеброй . Он включает в себя операторы присваивания, подпрограммы , условные операторы, итерацию, арифметику с плавающей точкой , массивы, иерархические структуры записей, утверждения, обработку исключений и другие расширенные функции, такие как целенаправленное выполнение. Plankalkül предоставляет структуру данных, называемую обобщенным графом ( verallgemeinerter Graph ), которая может использоваться для представления геометрических структур. ^[14]

Многие черты Планкалкюля вновь появляются в более поздних языках программирования; исключением является его своеобразная двумерная нотация с использованием нескольких строк.

Некоторые особенности Планкалкюля: ^{[3] : 217}

• только локальные переменные
• функции не поддерживают рекурсию
• поддерживает только вызов по значению
• составные типы — это массивы и кортежи
• содержит условные выражения
• содержит цикл for и цикл while
• нет goto

Единственный примитивный тип данных в Plankalkül — это один бит или Boolean ( нем . Ja-Nein-Werte — значение «да-нет» в терминологии Цузе). Он обозначается идентификатором . Все последующие типы данных являются составными и строятся из примитивных с помощью «массивов» и «записей». ^{[15] : 679}${\displaystyle S0}$

Так, последовательность из восьми бит (которая в современных вычислениях может рассматриваться как байт ) обозначается как , а булева матрица размером описывается   как . Существует также сокращенная запись, поэтому можно написать вместо . ^{[15] : 679}${\displaystyle 8\times S0}$${\displaystyle м}$${\displaystyle n}$${\displaystyle m\times n\times S0}$${\displaystyle S1\cdot n}$${\displaystyle n\times S0}$

Тип может иметь два возможных значения и . Таким образом, 4-битная последовательность может быть записана как L00L, но в случаях, когда такая последовательность представляет число, программист может использовать десятичное представление 9. ^{[15] : 679}${\displaystyle S0}$${\displaystyle 0}$${\displaystyle L}$

Запись двух компонентов и записывается как . ^{[15] : 679}${\displaystyle \сигма}$${\displaystyle \тау}$${\displaystyle (\сигма,\тау)}$

Тип ( нем . Art ) в Plankalkül состоит из 3 элементов: структурированное значение ( нем . Struktur ), прагматическое значение ( нем . Typ ) и возможное ограничение возможных значений ( нем . Beschränkung ). ^{[15] : 679} Пользовательские типы обозначаются буквой A с цифрой, например – первый пользовательский тип.${\displaystyle A1}$

Цузе использовал много примеров из теории шахмат: ^{[15] : 680}

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

Идентификаторы — это буквенно-цифровые символы с номером. ^{[15] : 679} Существуют следующие виды идентификаторов для переменных: ^{[9] : 10}

• Входные значения ( нем . Eingabewerte, Variablen ) — отмечены буквой V.
• Промежуточные, временные значения ( нем . Zwischenwerte ) — обозначаются буквой Z.
• Константы ( нем . Constanten ) — обозначаются буквой С.
• Выходные значения ( нем . Resultatwerte ) — обозначены буквой R.

Конкретная переменная некоторого вида идентифицируется числом, написанным под видом. ^{[15] : 679} Например:

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

Программы и подпрограммы обозначаются буквой P, за которой следует номер программы (и, возможно, подпрограммы). Например , . ^{[15] : 679}${\displaystyle P13}$${\displaystyle P5\cdot 7}$

Выходное значение программы, сохраненное в переменной, доступно для других подпрограмм под этим идентификатором , а чтение значения этой переменной также означает выполнение связанной подпрограммы. ^{[15] : 680}${\displaystyle P13}$${\displaystyle {\begin{matrix}R\\0\end{matrix}}}$${\displaystyle {\begin{matrix}R17\\0\end{matrix}}}$

Plankalkül позволяет получить доступ к отдельным элементам переменной с помощью «индекса компонента» ( нем . Komponenten-Index ). Когда, например, программа получает входные данные в переменной типа (состояние игры), то  — выдает состояние доски,  — фигуру на поле номер i и бит номер j этой фигуры. ^{[15] : 680}${\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}}}$${\displaystyle {\begin{matrix}V\\0\\0\cdot i\cdot j\end{matrix}}}$

В современных языках программирования это можно описать с помощью записи, похожей на V0[0], V0[0][i], V0[0][i][j](хотя для доступа к отдельному биту в современных языках программирования обычно используется битовая маска ).

Поскольку индексы переменных записываются вертикально, для записи каждой инструкции Plankalkül требуется несколько строк. ^{[ необходима ссылка ]}

Первая строка содержит вид переменной, затем номер переменной, обозначенный буквой V ( нем . Variablen-Index ), затем индексы подкомпонентов переменной, обозначенные буквой K ( нем . Komponenten-Index ), а затем ( нем . Struktur-Index ), обозначенные буквой S, которая описывает тип переменной. Тип не обязателен, но Цузе отмечает, что это помогает при чтении и понимании программы. ^{[15] : 681}

В строках типов и можно сократить до и . ^{[15] : 681}${\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 м}$${\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), первой (индекс 0) пары, і-го элемента переменной V3, имеет логический тип ( ).${\displaystyle S0}$

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

Z5-й элемент переменной V3. Эквивалент выражения V3[Z5]во многих современных языках программирования. [15] : 681

Цузе ввел в свое исчисление оператор присваивания, неизвестный в математике до него. Он обозначил его « », и назвал его yields-sign ( нем . Ergibt-Zeichen ). Использование концепции присваивания является одним из ключевых различий между математикой и информатикой. ^{[6] : 14}${\displaystyle \Стрелка вправо}$

Цузе писал, что выражение:

${\displaystyle {\begin{array}{r|lll}&Z+1&\Стрелка вправо &Z\\V&1&&1\\\end{array}}}$

аналогично более традиционному математическому уравнению:

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

Есть утверждения, что Конрад Цузе изначально использовал этот глифкак знак для назначения, и начал использоваться под влиянием Хайнца Рутисхаузера . ^{[15] : 681} Кнут и Пардо считают, что Цузе всегда писал , и что${\displaystyle \Rightarrow }$${\displaystyle \Rightarrow }$был введен издателями «Über den allgemeinen Plankalkül als Mittel zur Formulierung Schetisch-Kombinativer Aufgaben ^» в 1948 году ^. делегация настаивала на . ^{[15] : 681}:=

Переменная, которая хранит результат присваивания ( l-value ), записывается в правую часть оператора присваивания. ^{[6] : 14} Первое присваивание переменной считается объявлением. ^{[15] : 681}

Левая часть оператора присваивания используется для выражения ( нем . Ausdruck ), которое определяет, какое значение будет присвоено переменной. Выражения могут использовать арифметические операторы, булевы операторы и операторы сравнения ( и т. д.). ^{[15] : 682}${\displaystyle =,\neq ,\leq }$

Операция возведения в степень записывается аналогично операции индексации — с использованием строк в двумерной нотации: ^{[9] : 45}

Булевы значения были представлены как целые числа с FALSE=0и TRUE=1. Условный поток управления принял форму защищенного оператора A -> B, который выполнял блок, Bесли Aбыл истинным. Также был оператор итерации в форме W { A -> X; B -> Y} , который повторяется до тех пор, пока все охранники не станут ложными. ^[16]

Цузе назвал одну программу Rechenplan («план вычислений»). Он представлял себе то, что он назвал Planfertigungsgerät («устройство сборки плана»), которое автоматически переводило бы математическую формулировку программы в машиночитаемую перфорированную кинопленку , что сегодня называется транслятором или компилятором . ^{[3] : 45, 104, 105}

Первоначальная нотация была двумерной. ^{[ необходимо пояснение ]} Для более поздней реализации в 1990-х годах была разработана линейная нотация.

В следующем примере определяется функция max3(в линейной транскрипции), которая вычисляет максимальное из трех переменных:

P1 макс3 (V0[:8.0],V1[:8.0],V2[:8.0]) → R0[:8.0]макс(V0[:8.0],V1[:8.0]) → Z1[:8.0]max(Z1[:8.0],V2[:8.0]) → R0[:8.0]КОНЕЦP2 макс (V0[:8.0],V1[:8.0]) → R0[:8.0]V0[:8.0] → Z1[:8.0](Z1[:8.0] < V1[:8.0]) → V1[:8.0] → Z1[:8.0]Z1[:8.0] → R0[:8.0]КОНЕЦ

• История языков программирования
• Хронология языков программирования
• Список языков программирования

• Цузе, Конрад (1943). Ansätze einer Theorie des allgemeinen Rechnens unter besonderer Berücksichtigung des Aussagenkalküls und dessen Anwendung auf Relaisschaltungen [ Создание универсальной теории вычислений со специальным рассмотрением исчисления высказываний и ее применения к релейным схемам ] (неопубликованная рукопись) (на немецком языке). Документы Цузе 045/018.
• Цузе, Конрад (1948-12-06) [ноябрь 1948]. Написано в Хопферау-бай-Фюссен, Германия. «Über den allgemeinen Plankalkül als Mittel zur Formulierung Schetisch-Kombinativer Aufgaben». Archiv der Mathematik (на немецком языке). 1 (6). Карлсруэ / Штутгарт / Базель, Германия: Birkhäuser Verlag : 441–449. дои : 10.1007/BF02038459. eISSN  1420-8938. ISSN  0003-889X.(9 страниц)
• Рохас, Рауль ; Гёктекин, Джюнейт; Фридланд, Джеральд; Крюгер, Майк; Кунис, Денис; Лангмак, Олаф (февраль 2000 г.). Plankalkül: первый язык программирования высокого уровня и его реализация (PDF) . Берлин, Германия: Институт информатики, Свободный университет Берлина и Feinarbeit.de. Технический отчет B-3/2000. Архивировано из оригинала 1 мая 2006 г.[2] (22 страницы)
• Bruines, Bram (2010-01-08). "Plankalkül" (PDF) (Диссертация). Архивировано (PDF) из оригинала 2023-11-02 . Получено 2023-11-02 .(24 страницы)

• "Plankalkül-Programme". Интернет-архив Конрада Цузе (на немецком и английском языках). 2014-08-21. Архивировано из оригинала 2014-08-21 . Получено 2017-10-04 .(Примечание. Планирование апплетов и документов Java.)