Plankalkül

Plankalkül

Paradigm	Procedural
Разработано	Конрадом Цузе
Впервые появилось	1948 г.; 72 года назад (1948 г.) - впервые опубликована концепция
Основные реализации
Plankalkül-Compiler FU Berlin в 2000 г.
Под влиянием
Begriffsschrift
Под влиянием
Superplan от Heinz Rutishauser,. ALGOL 58

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

Калькюль - это немецкий термин для формальной системы, как в Гильберте-Калькюле, оригинальном названии дедуктивной системы в стиле Гильберта —So Plankalkül относится к формальной системе планирования.

Содержание

• 1 История
• 2 Описание
  • 2.1 Типы данных
    • 2.1.1 Примеры
  • 2.2 Идентификаторы
  • 2.3 Доступ к элементам с помощью index
  • 2.4 Двумерный синтаксис
  • 2.5 Операция присваивания
  • 2.6 Поток управления
  • 2.7 Терминология
  • 2.8 Пример
• 3 См. также
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки

История

В области создания вычислительных машин Цузе был самоучкой и разработал их, не зная о других механических вычислительных машинах, которые уже существовали. Для описания логических схем Цузе изобрел свою собственную систему диаграмм и обозначений, которую назвал «комбинаторикой условных выражений» (немецкий : Bedingungskombinatorik). После завершения Z1 в 1938 году Цузе обнаружил, что исчисление, которое он независимо разработал, уже существует и было известно как исчисление высказываний. Однако то, что имел в виду Цузе, должно было быть гораздо более мощным (исчисление высказываний не Тьюрингово-полное и не способно описывать даже простые арифметические вычисления). В мае 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 ], где Цузе работал над Планкалкюлем

Работая над докторской диссертацией, Цузе разработал первую известную формальную систему обозначений алгоритмов, способную к обработка ветвей и петель. В 1942 году он начал писать программу шахматы в Планкалкюле. В 1944 году Цузе встретился с немецким логиком и философом Генрихом Шольцем, который выразил признательность Цузе за использование логического исчисления. В 1945 году Цузе описал Планкалкюль в неопубликованной книге. Однако крах нацистской Германии помешал ему представить свою рукопись.

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

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

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

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

Не может продолжать создавать компьютеры - что также было запрещено союзными державами - - Цузе посвятил свое время разработке модели и языка программирования более высокого уровня. В 1948 году он опубликовал статью в Archiv der Mathematik и представил ее на ежегодном собрании GAMM. Его работы не привлекли особого внимания. В лекции 1957 года Цузе выразил надежду, что Планкалкюль, «через некоторое время в роли Спящей красавицы, все же оживет». Он выразил разочарование тем, что разработчики ALGOL 58 никогда не признавали влияние Планкалкюля на их собственную работу.

Планкалкюль был более полно опубликован в 1972 году. Диссертация 1975 г. Другие независимые реализации последовали в 1998 и 2000 годах в Свободном университете Берлина.

Описание

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

Планкалкюль использовал своеобразную нотацию, используя несколько линий с Frege Begriffsschrift 1879 г. (имеет дело с математической логикой ).

Некоторые особенности Plankalkül:

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

Типы данных

Единственным примитивным типом данных в Plankalkül является единственный бит или логический (немецкий : Ja -Nein-Werte - значение да-нет в терминологии Zuses). Обозначается идентификатором $S\; 0\; \{\backslash \; displaystyle\; S0\}$. Все остальные типы данных являются составными и строятся из примитивов. с помощью «массивов» и «записей».

Итак, последовательность Количество восьми бит (которое в современных вычислениях можно рассматривать как байт ) обозначается как $8\; \times \; S\; 0\; \{\backslash \; displaystyle\; 8\; \backslash \; times\; S0\}$, а логическая матрица размер $m\; \{\backslash \; displaystyle\; m\}$на $n\; \{\backslash \; displaystyle\; n\}$описывается как $m\; \times \; n\; \times \; S\; 0\; \{\backslash \; displaystyle\; m\; \backslash \; times\; n\; \backslash \; times\; S0\}$. Также существует сокращенная запись, поэтому можно написать $S\; 1\; \cdot \; n\; \{\backslash \; displaystyle\; S1\; \backslash \; cdot\; n\}$вместо $n\; \times \; S\; 0\; \{\backslash \; displaystyle\; n\; \backslash \; times\; S0\}$.

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

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

Тип (немецкий : Art) в Plankalkül состоит из трех элементов: структурированного значения (немецкий : Struktur), прагматического значения (немецкий : Typ) и возможного ограничения возможных значения (немецкий : Beschränkung). Типы, определяемые пользователем, обозначаются буквой A с номером, например $A\; 1\; \{\backslash \; displaystyle\; A1\}$- первый тип, определенный пользователем.

Примеры

Цузе использовал множество примеров из теории шахмат:

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

Идентификаторы

Идентификаторы представляют собой буквенно-цифровые символы с числом. Существуют следующие типы идентификаторов для переменных:

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

Конкретная переменная определенного типа идентифицируется по номеру, указанному под типом. Например:

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

Программы и подпрограммы отмечены буквой P, за которой следует по номеру программы (и, возможно, подпрограммы). Например, $P\; 13\; \{\backslash \; displaystyle\; P13\}$, $P\; 5\; \cdot \; 7\; \{\backslash \; displaystyle\; P5\; \backslash \; cdot\; 7\}$.

Выходное значение программы $P\; 13\; \{\backslash \; displaystyle\; P13\}$сохраненный там в переменной $R\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; R\; \backslash \backslash \; 0\; \backslash \; end\; \{matrix\}\}\}$доступен для других подпрограмм под идентификатором $R\; 17\; 0\; \{\; \backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; R17\; \backslash \backslash \; 0\; \backslash \; end\; \{matrix\}\}\}$, а чтение значения этой переменной также означает выполнение связанной подпрограммы.

Доступ к элементам по индексу

Plankalkül разрешает доступ к отдельным элементам переменной с помощью «индекса компонента» (немецкий : Komponenten-Index). Когда, например, программа принимает входные данные в переменной $V\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; V\; \backslash \backslash \; 0\; \backslash \; end\; \{matrix\}\}\}$типа $A\; 10\; \{\backslash \; displaystyle\; A10\}$(состояние игры), затем $V\; 0\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; V\; \backslash \backslash \; 0\; \backslash \backslash \; 0\; \backslash \; end\; \{matrix\}\}\}$- показывает состояние платы, $V\; 0\; 0\; \cdot \; i\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; V\; \backslash \backslash \; 0\; \backslash \backslash \; 0\; \backslash \; cdot\; i\; \backslash \; end\; \{matrix\}\}\}$- число на квадрате я и $V\; 0\; 0\; \cdot \; я\; \cdot \; j\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{matrix\}\; V\; \backslash \backslash \; 0\; \backslash \backslash \; 0\; \backslash \; cdot\; i\; \backslash \; cdot\; j\; \backslash \; end\; \{matrix\}\}\}$номер бит j этого фрагмента.

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

Двумерный синтаксис

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

Первая строка содержит тип переменной, затем номер переменной, помеченный буквой V (немецкий : индекс-переменная), затем индексы подкомпонентов переменных, отмеченные K (немецкий : Komponenten-Index), а затем (немецкий : Struktur-Index) помечены буквой S, которая описывает тип переменной. Тип не требуется, но Цузе отмечает, что это помогает при чтении и понимании программы.

В строке $S\; \{\backslash \; displaystyle\; S\}$типы $S\; 0\; \{\backslash \; displaystyle\; S0\}$и $S\; 1\; \{\backslash \; displaystyle\; S1\}$можно сократить до $0\; \{\backslash \; displaystyle\; 0\}$и $1\; \{\backslash \; displaystyle\; 1\}$.

Примеры:

$VV\; 3\; KS\; m\; \times \; 2\; \times \; 1\; \cdot \; n\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{r\; |\; l\}\; V\; \backslash \; V\; 3\; \backslash \backslash \; K\; \backslash \backslash \; S\; m\; \backslash \; times\; 2\; \backslash \; times\; 1\; \backslash \; cdot\; n\; \backslash \; end\; \{array\}\}\}$	переменная V3 - список $m\; \{\backslash \; displaystyle\; m\}$пар значений типа $S\; 1\; \cdot \; n\; \{\backslash \; displaystyle\; S1\; \backslash \; cdot\; n\}$
$VV\; 3\; S\; м\; \times \; 2\; \times \; 1\; \cdot \; n\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{r\; |\; l\}\; V\; \backslash \backslash \; V\; 3\; \backslash \backslash \; S\; m\; \backslash \; times\; 2\; \backslash \; times\; 1\; \backslash \; cdot\; n\; \backslash \; end\; \{array\}\}\}$	Строку K можно пропустить, если она пуста. Следовательно, это выражение означает то же, что и выше.
$VV\; 3\; К\; я\; \cdot \; 0\; \cdot \; 7\; S\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{r\; |\; l\}\; V\; \backslash \backslash \; V\; 3\; \backslash \backslash \; K\; i\; \backslash \; cdot\; 0\; \backslash \; cdot\; 7\; \backslash \backslash \; S\; 0\; \backslash \; end\; \{array\}\}\}$	Значение бита восьмерок (индекс 7) первой (индекс 0) пары і-го элемента переменной V3 имеет логический тип ($S\; 0\; \{\backslash \; displaystyle\; S0\}$).

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

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

Операция присваивания

Цузе ввел в свое исчисление оператор, неизвестный для математики до него - присваивание. Он пометил его «$\Rightarrow \; \{\backslash \; displaystyle\; \backslash \; Rightarrow\}$» и назвал знак уступки (немецкий : Ergibt-Zeichen). Использование концепции присваивания - одно из ключевых различий между математикой и информатикой.

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

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

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

$Z\; +\; 1\; =\; ZV\; 1\; 1\; K\; ii\; +\; 1\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{r\; |\; lll\}\; Z\; +\; 1\; =\; Z\; \backslash \backslash \; V\; 1\; 1\; \backslash \backslash \; K\; i\; i\; +\; 1\; \backslash \backslash \backslash \; end\; \{array\}\}\}$

Существует мнение, что Конрад Зузе изначально использовал для присвоения знак , и начал использовать $\Rightarrow \; \{\backslash \; displaystyle\; \backslash \; Rightarrow\}$под влиянием Хайнца Рутисхаузера. Кнут и Пардо считают, что Цузе всегда писал $\Rightarrow \; \{\backslash \; displaystyle\; \backslash \; Rightarrow\}$, а был введен издателями «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben». На конференции ALGOL 58 в Цюрихе европейские участники предложили использовать для присваивания символ, введенный Цузе, но американская делегация настаивала на :=.

переменной, которая хранит результат присваивания (l-значение ) записывается справа от оператора присваивания. Первое присвоение переменной считается объявлением.

Левая часть оператора присваивания используется для выражения (немецкий : Ausdruck), которое определяет, какое значение будет присвоено переменной. В выражениях могут использоваться арифметические операторы, логические операторы и операторы сравнения ($=,\; \ne ,\; \le \; \{\backslash \; displaystyle\; =,\; \backslash \; neq,\; \backslash \; leq\}$etc.).

Операция возведения в степень. записывается аналогично операции индексации - с использованием строк в 2d-нотации:

Поток управления

Терминология

Цузе назвал отдельную программу Rechenplan («план вычислений»). Он представил то, что он назвал Planfertigungsgerät («устройство для сборки чертежей»), которое автоматически переводило бы математическую формулировку программы в машиночитаемый перфорированный пленочный материал.

Пример

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

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

P1 max3 (V0 [: 8.0], V1 [ : 8.0], V2 [: 8.0]) → R0 [: 8.0] макс (V0 [: 8.0], V1 [: 8.0]) → Z1 [: 8.0] макс (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] END

См. Также

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

Примечания

Ссылки

Внешние ссылки

• "Планкалкюль" Конрада Цузе: предшественник современных языков программирования, автор Фридрих Л. Бауэр (альтернативный источник )
• Рохас, Рауль и др. (2000). «Планкалкюль: Первый язык программирования высокого уровня и его реализация ". Institut für Informatik, Freie Universität Berlin, Технический отчет B-3/2000. (полный текст) (в архиве)
• Mauerer, Wolfgang (03.06.2016). "Der Plankalkül von Konrad Zuse" (на немецком языке). Реализация i русский немецкий. Архивировано с оригинального 03.06.2016. Проверено 3 октября 2017 г.
• "Plankalkül". Интернет-архив Конрада Цузе. Архивная страница с java-апплетами Plankalkül (не работает) и несколькими документами (немецкий / английский). 2014-08-21. Архивировано с оригинала 21.08.2014. Проверено 04.10.2017. CS1 maint: others (ссылка )
• Bram Bruines: Plankalkul (2010) - Планкалкюль описан формально