Планкалкюль - Википедия - Plankalkül

Plankalkül
ПарадигмаПроцедурный
РазработаноКонрад Зузе
Впервые появился1948; 72 года назад (1948) - концепция впервые опубликована
Основной реализации
Plankalkül-компилятор посредством FU Berlin в 2000 г.
Под влиянием
Begriffsschrift[1]
Под влиянием
Суперплан к Хайнц Рутисхаузер,
АЛГОЛ 58[2]

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

Калкюль это Немецкий срок для формальная система -как в Гильберт-Калькюль, исходное название для Система дедукции в стиле Гильберта -так Plankalkül относится к формальной системе планирования.[3]

История

В области создания вычислительных машин Цузе был самоучкой и разработал их, не зная о других механических вычислительных машинах, которые уже существовали. Для описания логических схем Цузе изобрел свою собственную систему диаграмм и обозначений, которую назвал «комбинаторикой условных выражений» (Немецкий: Бедингунгскомбинаторик). После завершения Z1 в 1938 году Цузе обнаружил, что исчисление, которое он независимо разработал, уже существует и было известно как пропозициональное исчисление.[4] Однако то, что имел в виду Цузе, должно было быть гораздо более мощным (исчисление высказываний не Полный по Тьюрингу и не может описать даже простые арифметические вычисления[5]). В мае 1939 года он описал свои планы по развитию того, что впоследствии станет Планкалкюль.[6] Он написал в блокноте следующее:

Почти полгода постепенного введения в формальную логику. Я заново открыл там множество своих предыдущих мыслей. (комбинаторика условных операторов = пропозициональное исчисление; изучение интервалов = теория решетки ). Сейчас планирую создание «Исчисления планов». Чтобы прояснить это, необходимо уточнить ряд концепций.

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.

- Блокнот Конрада Цузе[4]
Стол на дом в Hinterstein [де ] где Цузе работал над Plankalkül

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

В то время единственные два рабочих компьютера в мире были ENIAC и Гарвард Марк I, ни один из которых не использовал компилятор, а ENIAC нужно было перепрограммировать для каждой задачи, изменяя подключение проводов.[13]

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

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

Невозможно продолжить производство компьютеров, что также было запрещено союзными державами.[15] - Цузе посвятил свое время разработке модели и языка программирования более высокого уровня.[8] В 1948 г. он опубликовал статью в Archiv der Mathematik и представлены на Ежегодном собрании ГАММ.[16] Его работы не привлекли особого внимания.[нужна цитата ] В лекции 1957 года Цузе выразил надежду, что Планкалкюль, «спустя некоторое время как Спящая красавица, еще оживет ".[нужна цитата ] Он выразил разочарование тем, что дизайнеры АЛГОЛ 58 никогда не признавали влияние Планкалкюль на свою работу.[8][17]

Планкалкюль был опубликован более подробно[нечеткий ] в 1972 году. Первый компилятор был реализован Иоахимом Хоманом в его диссертации 1975 года.[18] Другие независимые реализации последовали в 1998 году.[19] и 2000 г. Свободный университет Берлина.[20]

Описание

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

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

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

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

Типы данных

Единственный примитивный тип данных в Plankalkül - это одиночный кусочек или же логический (Немецкий: Ja-Nein-Werte - значение да-нет в терминологии Зусеса). Обозначается идентификатором . Все остальные типы данных являются составными и строятся из примитивов с помощью «массивов» и «записей».[23]

Итак, последовательность из восьми битов (которую в современных вычислениях можно рассматривать как байт ) обозначается , и логическая матрица размера к описывается . Также существует сокращенная запись, чтобы можно было написать вместо .[23]

Тип может иметь два возможных значения и . Таким образом, 4-битная последовательность может быть записана как L00L, но в случаях, когда такая последовательность представляет собой число, программист может использовать десятичное представление 9.[23]

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

Тип (Немецкий: Изобразительное искусство) в Plankalkül состоит из 3 элементов: структурированное значение (Немецкий: Struktur), прагматическое значение (Немецкий: Тип) и возможное ограничение возможных значений (Немецкий: Beschränkung).[23] Типы, определяемые пользователем, обозначаются буквой A с номером, например - первый определяемый пользователем тип.

Примеры

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

Координата шахматной доски (размер 8х8, 3 бита вполне достаточно)
квадрат доски (например, L00, 00L обозначает e2 в алгебраическая запись )
фигура (например, 00L0 - белый король)
фигура на доске (например L00, 00L; 00L0 - белый король на e2)
доска (расположение фигур, описывает, какие фигуры находятся в каждом из 64 квадратов)
состояние игры ( - доска, - кто двигается, - возможность рокировки (2 для белых и 2 для черных), A2 - информация о ячейке, на которой Мимоходом переезд возможен

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

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

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

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

, , и Т. Д.

Программы и подпрограммы помечены буквой P, за которой следует номер программы (и, возможно, подпрограммы). Например , .[23]

Выходное значение программы сохранено там в переменной доступен для других подпрограмм под идентификатором , и чтение значения этой переменной также означает выполнение связанной подпрограммы.[24]

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

Plankalkül обеспечивает доступ к отдельным элементам переменной с помощью «индекса компонента» (Немецкий: Компонентен-Индекс). Когда, например, программа получает ввод в переменную типа (состояние игры), то - выдает состояние платы, - фигура на квадрате номер i, и бит номер j этого фрагмента.[24]

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

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

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

Первая строка содержит вид переменной, затем номер переменной, отмеченный буквой V (Немецкий: Variablen-Index), затем индексы переменных подкомпонентов, помеченных знаком K (Немецкий: Компонентен-Индекс), а потом (Немецкий: Структур-Индекс) помечены буквой S, которая описывает тип переменной. Тип не требуется, но Цузе отмечает, что это помогает при чтении и понимании программы.[26]

В соответствии типы и можно было бы сократить до и . [26]

Примеры:

переменная V3 - список пары значений типа
Строку K можно пропустить, если она пуста. Следовательно, это выражение означает то же, что и выше.
Значение бита восьмерок (индекс 7) первой (индекс 0) пары і-го элемента переменной V3 имеет логический тип ().

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

Использование переменной в качестве индекса для другой переменной в обозначении 2d ПланкалюляZ5-й элемент переменной V3. Эквивалентно выражению V3 [Z5] во многих современных языках программирования.[26]

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

Цузе ввел в свое исчисление неизвестный до него математике оператор - присваивание. Он отметил это знаком «», И назвал это знаком доходности (Немецкий: Ergibt-Zeichen). Использование концепции задания - одно из ключевых различий между математикой и информатикой.[27]

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

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

Существует мнение, что Конрад Зузе изначально использовал для присвоения знак Ergibt-Zeichen.png, и начал использовать под влиянием Хайнц Рутисхаузер.[26] Кнут и Пардо считают, что Зузе всегда писал , и Ergibt-Zeichen.png был представлен издателем «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben».[27] На АЛГОЛ 58 На конференции в Цюрихе европейские участники предложили использовать для назначения символ, введенный Цузе, но американская делегация настояла на том, чтобы :=.[26]

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

Левая часть оператора присваивания используется для выражения (Немецкий: Ausdruck), который определяет, какое значение будет присвоено переменной. Выражения могут использовать арифметические операторы, логические операторы и операторы сравнения ( так далее.).[28]

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

Обозначение возведения в степень в Планкалкюль

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

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

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

Пример

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

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

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] ENDP2 max (V0 [: 8.0], V1 [: 8.0]) → R0 [: 8.0] V0 [: 8.0] → Z1 [: 8.0] ( Z1 [: 8.0] 

Смотрите также

Примечания

  1. ^ "Ранние языки программирования / CS208e: великие идеи в области компьютерных наук" (PDF).
  2. ^ Рохас, Рауль; Хашаген, Ульф (2002). Первые компьютеры: история и архитектура. MIT Press. п. 292. ISBN  978-0262681377. Получено 25 октября, 2013.
  3. ^ Гектор Зенил (редактор), 2012. Вычислимая Вселенная: Понимание и изучение природы как вычисления с предисловием сэра Роджер Пенроуз. Сингапур: Всемирная научная издательская компания. Стр.791.
  4. ^ а б Рохас и др. 2004 г., п. 3.
  5. ^ «Почему логика высказываний не является полной по Тьюрингу?».
  6. ^ Ганс Дитер Хеллиге (ред.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. п. 216.
  7. ^ Кнут и Пардо 1976, п. 9
  8. ^ а б c d Гилой 1997
  9. ^ Ганс Дитер Хеллиге (ред.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. п. 56.
  10. ^ Ганс Дитер Хеллиге (ред.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. п. 216 217.
  11. ^ Хартмут Петцольд,Moderne Rechenkünstler. Die Industrialisierung der Rechentechnik в Германии. München. C.H. Бек Верлаг 1992
  12. ^ (полный текст рукописи 1945 г.)
  13. ^ Рохас и др. 2000 г., п. 3.
  14. ^ Кнут и Пардо 1976, п. 8
  15. ^ Проф. Вольфганг Кой: Был ист Информатик? Zur Entstehung des Faches an den deutschen Universitäten, в: Ганс Дитер Хеллиге (ред.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. п. 474.
  16. ^ Ганс Дитер Хеллиге (ред.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. п. 89.
  17. ^ Кнут и Пардо 1976, п. 15
  18. ^ Иоахим Хоманн: Der Plankalkül im Vergleich mit algorithmischen Sprachen. Reihe Informatik und Operations Research, S. Toeche-Mittler Verlag, Дармштадт, 1979 г., ISBN  3-87820-028-5.
  19. ^ Описание Plankalkül-Compiler, автор: Wolfgang Mauerer
  20. ^ Рохас и др. 2000 г., п. 2.
  21. ^ Проф. Вольфганг Гилой [де ]: Konrad Zuses Plankalkül als Vorläufer moderner Programmiermodelle, ноябрь 1990 г.
  22. ^ Ганс Дитер Хеллиге (ред.): Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. п. 217.
  23. ^ а б c d е ж грамм час Бауэр и Вёсснер, 1972 г., п. 679.
  24. ^ а б c Бауэр и Вёсснер, 1972 г., п. 680.
  25. ^ Цузе 1945, п. 10.
  26. ^ а б c d е ж Бауэр и Вёсснер, 1972 г., п. 681.
  27. ^ а б c Кнут и Пардо 1976, п. 14.
  28. ^ Бауэр и Весснер, 1972 г., п. 682.
  29. ^ Цузе 1945, п. 45.
  30. ^ Хеллидж, Ганс Дитер, Geschichten der Informatik. Visionen, Paradigmen, Leitmotive. Берлин, Springer 2004 г., ISBN  3-540-00217-0. стр.45, 104, 105

Рекомендации

внешняя ссылка