Глава 5 Программирование и программы

We use cookies. Read the Privacy and Cookie Policy

Глава 5

Программирование и программы

Развитие аппаратного обеспечения шло параллельно с эволюцией языков программирования. На бытовом уровне язык программирования можно определить как коммуникативный код, с помощью которого можно объяснить компьютеру, что нужно делать, чтобы решить данную задачу. Иными словами, это перечень инструкций, записанный понятным компьютеру способом в заданном порядке. Инструкции описывают последовательность действий, необходимых для получения желаемого результата. При взгляде на это определение в памяти мгновенно всплывают наши старые знакомые, о которых мы рассказали в первых главах этой книги, — алгоритмы.

И действительно, согласно более формальному определению, язык программирования — это способ описать алгоритмы, управляющие поведением компьютера.

Разумеется, инструкции языка программирования должны быть четкими и однозначными и всегда должны служить решению конкретной задачи. В языке программирования также должен быть реализован основной элемент алгоритмов и языков программирования — повтор. В языках программирования повторы реализованы двумя способами — с помощью итерации и рекурсии. Итерация — это организация обработки данных, при которой действия повторяются многократно. Она реализуется с помощью инструкций, подобных операторам repeat, while и for. Рекурсия — это повторение действий самоподобным образом, при котором процедуры вызывают сами себя.

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

* * *

ТЕРМИН «РЕАЛИЗАЦИЯ»

Реализация — это осуществление или воплощение чего-либо. В информатике этот термин означает запись определенного алгоритма на заданном языке программирования.

ТЕРМИН «ПРОГРАММИРОВАНИЕ»

Слово «программировать» (англ, to program), означающее задание инструкций, которые должен выполнить компьютер, было придумано группой исследователей, работавших над созданием компьютера ENIAC в Институте Мура Пенсильванского университета. В то время использовалось слово «настраивать» (to set up), так как программирование ENIAC (изображен на иллюстрации ниже) осуществлялось с помощью соединений и переключателей, то есть путем изменения электрической схемы самого компьютера. Постепенно, по мере того как разделение между аппаратным и программным обеспечением становилось все более явным, стало применяться слово «программирование».

* * *

Древнейшие алгоритмы, которые позволили вавилонянам провозгласить себя первыми математиками, способными решать достаточно сложные задачи, использовались для решения алгебраических уравнений, записывались в общем виде и демонстрировались на конкретных примерах. В них не использовались итерации или условные конструкции вида «если x < 0, то», так как вавилонянам не был известен нуль. Чтобы выразить несколько возможных вариантов, математики Вавилонии повторяли алгоритм необходимое число раз. Прошло много веков, прежде чем Евклид примерно в 300 году до н. э. описал алгоритм вычисления наибольшего общего делителя двух чисел. Этот алгоритм, который сегодня известен как алгоритм Евклида, как правило, реализуется с помощью рекурсии.

* * *

РЕАЛИЗАЦИЯ АЛГОРИТМА ЕВКЛИДА

Приведем в качестве примера реализацию алгоритма для нахождения наибольшего общего делителя чисел А и В сначала на языке Пролог, затем на языке Java. Сокращение gcd означает great common divisor — наибольший общий делитель.

В реализации на языке Пролог использованы три правила, соответствующие трем возможным случаям. Во всех случаях два первых аргумента являются числами, третий аргумент можно интерпретировать как результат. В первом правиле второй аргумент принят равным нулю. Второе правило применяется тогда, когда первый аргумент больше второго, третье правило — когда второй аргумент больше первого.

gcd (А, 0, А).

gcd (А, В, D)(А > В), (В > 0), R is A mod В, gcd(B, R, D).

gcd (А, В, D)(А < В), (А > 0), R is В mod A, gcd(A, R, D).

В реализации на языке Java также используются вышеизложенные правила. В качестве входных параметров использованы два числа А и В, в качестве результата функция возвращает их наибольший общий делитель. Первая версия алгоритма является рекурсивной, вторая — итеративной.

public static int gcd (int A, int B) {

if (B == 0) {return A;}

else if (A > B) {return gcd(B, A % B);}

else if (A < B) {return gcd(A, В % A);}

return 1;

}

public static int gcdlterative (int A, int B) {

int r = 0;

while (B > 0) {

r = A % B;

A = B;

В = r;

}

return A;

}

* * *

Однако эти алгоритмы представляют собой не элементы общего эволюционного процесса, а отдельные частные случаи. Наиболее известным средством автоматического выполнения задач было программирование ткацких станков Жаккара. В станке Жаккара узор ткани определялся с помощью перфокарт. Эти перфокарты содержали примитивные программы, которые исполнялись станком. Чарльз Бэббидж использовал перфокарты для программирования своей вычислительной машины.

С современной точки зрения эти примитивные программы были написаны на машинном языке, поэтому Ада Лавлейс считается первым в истории программистом. Однако понятие программы, хранящейся в памяти вычислительной машины, появилось значительно позже.

Несмотря на все усилия, предпринятые в 1930-е и 1940-е годы, а также написанные в этот период теоретические работы, в особенности те, что были посвящены лямбда-исчислению и машине Тьюринга, развитие алгоритмов началось лишь с появлением первых компьютеров: «Колосса», Mark I, ENIAC, EDSAC и UNIVAC. Языки программирования, с помощью которых стало возможным написание программ, хранящихся в оперативной памяти, позволили сэкономить время и уйти от взаимодействия с аппаратным обеспечением напрямую — именно так осуществлялось программирование первых компьютеров.

Программы для первых компьютеров писались в восьмеричном коде. Среди первых языков программирования, допускавших представление символов, были Short Order Code (1949) Джона Мокли и Sort-Merge Generator Бетти Холбертон. Short Order Code исполнялся на компьютере BINAC и был интерпретируемым языком.

Процедуры, соответствовавшие символам, хранились в памяти компьютера и вызывались системой. Эту же систему унаследовал UNIVAC. Программа, записанная на этом языке, исполнялась в 50 раз медленнее той же программы, записанной на машинном языке.

Sort-Merge Generator, в свою очередь, был приложением, разработанным для UNIVAC, которое осуществляло слияние и перемешивание карточек с входными и выходными операциями.

Бетти Холбертон (на этой фотографии она изображена за работой на ENIAC), создавшая один из первых языков программирования.

Эти первые системы, автоматического программирования (англ, automatic programming systems) всего лишь предоставляли понятные человеку коды операций и инструкции, записанные в символьном виде либо позволяли извлекать подпрограммы из библиотек и вставлять их в требуемый участок программного кода. Некоторые системы допускали интерпретацию операций для чисел с плавающей запятой и операций индексирования (indexing). Как бы то ни было, за исключением компилятора А-2 и алгебраической системы Лейнинга и Цирлера, до 1954 года даже наиболее мощные системы представляли собой всего лишь синтетические машины с кодом, отличающимся от машинного кода.

Эта модель обладала недостатками не только с технической, но и с экономической точки зрения. Оплата труда программистов вычислительного центра превышала стоимость самого компьютера, и этот разрыв неуклонно возрастал по мере того, как стоимость технологий и соответственно стоимость компьютеров снижалась. Кроме того, на программирование и отладку (debugging) тратилось от 25 до 50 % машинного времени. Системы автоматического программирования снижали быстродействие компьютера в 5—10 раз. Продавцы этих систем в худших традициях рынка стали завышать стоимость. Это привело к тому, что использование этих систем оказывалось невыгодным, и отношение к ним было скептическим.

В середине 1954 года в компании IBM под руководством Джона Бэкуса были начаты работы над языком Фортран (FORTRAN — FORmula TRANslation). Целью работ было решение всех вышеперечисленных проблем. При создании компилятора основное внимание уделялось генерации эффективного объектного кода, и эта задача была успешно решена. Качество объектного кода и преобразования, выполняемых для получения эффективных программ, удивили даже самих создателей языка FORTRAN.

Перфокарта с разметкой колонок для языка программирования Фортран.

С появлением языка Фортран появилась возможность записывать математические процедуры на четко определенном языке. Этот язык обеспечивал новый, более высокий уровень абстракции, поэтому программный код мог исполняться на разных компьютерах. Информация сохранялась в памяти и рассматривалась не как последовательность бит, а как целые или вещественные числа. В языке появились первые базовые конструкции императивных языков: условный оператор (IF <условие> <выражение_1_если_условие__истинно> <выражение_2_если_условие_ложно>) и оператор цикла (DO <инструкция> переменная = начальное значение, конечное значение, шаг).

За Фортраном последовали другие языки: Алгол-60 (одним из его создателей был голландский ученый Эдсгер Дейкстра), Кобол и LISP (предшественник функциональных языков программирования). Эти языки предназначались для решения определенных задач. В отличие от этих языков, язык PL/I был создан как язык общего назначения и содержал все нововведения, представленные в более ранних языках, что сделало его громоздким и сложным.

Компьютер Electrologica XI, работавший в период с 1958 по 1965 год, в котором использовался язык Алгол-60.

Авторы языков программирования ставили перед собой менее амбициозные задачи, но созданные ими языки оказались более эффективными. Среди них выделялись Simula 67 и Pascal. Вместо предопределенного полного множества абстракций эти языки обладали гибкими и удобными средствами определения новых произвольных абстракций. Pascal и Алгол-68 позволяли определять новые типы данных на основе предопределенных простых типов и служебных слов (array, record и других). Эти новые типы можно было рассматривать как абстракции, созданные на основе внутренних представлений, и им сопоставлялось множество операций. Эта модель была гибкой, но обладала существенным недостатком. Доступ к представлению предопределенных типов был закрыт, то есть с предопределенными объектами нельзя было работать напрямую (только с помощью операций), однако доступ к структуре пользовательских типов был открыт, и их значения можно было изменять. Причина заключалась в том, что в языке не было различий между двумя уровнями абстракции: уровнем, на котором программист использует тип данных, и уровнем реализации этого типа. Это осложняло чтение программ и исправление ошибок. Когда программы достигали определенных размеров, эта задача становилась невыполнимой.

Решением проблемы стало использование абстрактных типов данных и языков, в которых они поддерживались (Ada, Modula-2 и CLU). В них проводилось различие между этими уровнями абстракции и применялась так называемая инкапсуляция (ограничение доступа к определенным компонентам объектов). На уровне, на котором программист использовал тип, доступ к его внутренней структуре был закрыт. На уровне реализации определялся интерфейс объекта, его внутренняя структура и доступные операции.

Так как программисту были известны операции, доступные для определенных объектов, и их поведение (но не внутреннее представление!), он оперировал терминами абстракции. Любое изменение реализации, которое не приводило к изменению интерфейса, не влияло на модули, где использовался этот интерфейс, так как в них был доступен только сам интерфейс, а не его внутренняя реализация.

Благодаря этим механизмам абстракции программы, написанные на этих языках, стало возможным представлять в терминах объектов. В некоторых языках, например в языке Ада и Modula-2, использование объектов было необязательным, в других — обязательным. В языке CLU программист должен был группировать данные приложения в классы, которые назывались кластерами. Аналогичный принцип использовался в объектно-ориентированных языках, в которых вводилось понятие наследования, позволявшее определять объекты на основе предопределенных объектов.

Объектно-ориентированное программирование — это парадигма программирования, в которой приложения и компьютерные программы понимаются как совокупность объектов и их взаимодействий.

Его появление должно было облегчить создание крупномасштабных программ и помочь в создании искусственного интеллекта. В работах над искусственным интеллектом эта парадигма помогла разработать приемы структурирования знаний путем группировки информации о каком-либо понятии и о его свойствах.

Первым языком, в котором данные и операции группировались в рамках единой сущности, был Simula I, предназначенный для решения задач симуляции. Он был разработан в Норвежском вычислительном центре под руководством математика и политика Кристена Нюгорда. Работы над первой версией языка были завершены в январе 1965 года. Следующая версия получила название Simula 67. Это был язык общего назначения, в котором были формализованы понятия объекта и класса и вводилось понятие наследования. Позднее в языке Smalltalk 80, который был создан на основе языка Simula и двух предыдущих версий (Smalltalk 72 и Smalltalk 76), понятие объекта было обобщено и объекты стали единственными сущностями, используемыми в языке. В начале 1970-х в научно-исследовательском центре Xerox Palo Alto Research Center, известном как Xerox PARC, была создана система Dynabook — персональное средство обработки информации с оконным интерфейсом, текстовыми меню, значками, то есть с полноценным графическим интерфейсом (англ. GUI — Graphical User Interface), очень похожим на современные. Dynabook был разработан американцем Аланом Кеем для обучения детей работе с компьютером. Работы были завершены в 1972 году. Программы в этой системе были написаны на языке BASIC, в них использовался механизм передачи сообщений, а также понятия класса и объекта, введенные в языке Simula.

Алан Кей получает степень почетного доктора испанского Университета Мурсии за вклад в развитие информатики. Торжественная церемония состоялась 28 января 2010 года.

Сейчас существует множество объектно-ориентированных языков программирования (Eiffel, C++ и другие), некоторые из которых являются расширенными и дополненными вариантами других языков. Так, C++ является расширенным вариантом языка С. Он был создан датским программистом Бьёрном Страуструпом и содержит классы, подобно языку Simula. Система CLOS была разработана с целью стандартизировать объектную систему языка Common LISP. Понятия объекта и наследования использовались в работах по созданию искусственного интеллекта при разработке языков для представления знаний, например KRL и KL-ONE, и языков с акторами, в частности Actl, Act2, Act3, ABCL/1 и других.

Абстракция и объекты применяются во всех языках программирования, появившихся в последние годы, как в объектно-ориентированных языках, например Java или Python, так и в процедурных, где используются объектно-ориентированные конструкции, например в языке РНР. Также появились языки, ориентированные на быструю разработку приложений, и сценарные языки. К ним относятся РНР и JavaScript, разработанные в последнее десятилетие XX века. Целью авторов этих языков было упростить и ускорить разработку программ. Разумеется, для небольших программ этого действительно удалось достичь, однако по сравнению с языками прошлого проектирование крупномасштабных программ усложнилось. Как бы то ни было, влияние объектно-ориентированных языков на разработку программ привело к появлению новых вспомогательных средств, например языков моделирования, подобных UML.

Функциональная парадигма

В императивных языках программирования вычисления производятся путем присваивания переменным нужных значений. Программа, написанная на императивном языке, имитирует структуру машины фон Неймана, содержащую ячейки, где хранятся значения. Присваивание значения переменной — не более чем изменение значения этой ячейки. В функциональных языках программирования результат получается путем применения функций, определенных при помощи композиции или рекурсии.

Функциональные языки впервые были описаны Джоном Маккарти из MIT (Массачусетского технологического института), создателем термина «искусственный интеллект», в работе, опубликованной в 1960 году в журнале Communications of the ACM. Этот ежемесячный журнал выпускается американской Ассоциацией вычислительной техники (ACM) — обществом, присуждающим премию Тьюринга.

В 1958 году Маккарти изучал использование операций с упорядоченными списками в программе символьного дифференцирования. Дифференцирование — это рекурсивный процесс, поэтому Маккарти использовал рекурсивные функции. Более того, он передавал функции в качестве аргументов другим функциям. Проект по реализации задуманного им языка начался осенью того же года. Результаты были опубликованы спустя два года под названием «Рекурсивные функции над символьными выражениями и их вычисление с помощью машины. Часть I» (часть II никогда не была опубликована). Так появилась первая версия языка LISP (англ. List Processing — «обработка списков») — первого функционального языка, в котором нашло применение множество передовых идей. В описании разработанного им языка Маккарти использовал лямбда-исчисление Алонзо Чёрча.

Джон Маккарти, создатель термина «искусственный интеллект». Стэндфордский университет, 1980 год.

* * *

ЛЯМБДА-ИСЧИСЛЕНИЕ

Эта система была разработана Алонзо Чёрчем и Стивеном Клини в начале 1930-х годов. Ее возможности были эквивалентны возможностям машины Тьюринга, но основной принцип лямбда-исчисления был иным. С формальной точки зрения в лямбда-исчислении используются выражения и правила преобразования выражений, которые моделируют использование функций и вычислений. Рассмотрим в качестве примера определение истинности и ложности:

истина: ?ху. х

ложь: ?ху. у.

Логическая функция «И» определяется так:

И: ?pq.p q р.

Чтобы найти значение выражения «истина ложь», заменим каждый член этого выражения его эквивалентом с точки зрения лямбда-исчисления:

(?pq.p q р) (?ху. х) (?ху. у).

Применив правила записи, получим выражение (?ху. у), что, как мы уже говорили, эквивалентно значению «ложь». Числа и операции с числами определяются аналогично.

* * *

В языке LISP данные и программы представляются одинаковым образом. Основной парадигмой этого языка является рекурсия, что позволяет избежать нежелательных побочных эффектов императивного программирования. В этом языке также были введены условные выражения и префиксная (польская) нотация Яна Лукасевича.

* * *

ПРЕФИКСНАЯ (ПОЛЬСКАЯ) НОТАЦИЯ

Математические выражения в этой нотации обозначаются символом, соответствующим операции, который располагается перед операндами. Так, выражение

(а + Ь) — (с·d)

в польской записи будет выглядеть так:

- + ab · cd.

* * *

В середине 1960-х Питер Лэндин создал новый функциональный язык ISWIM (от англ. If You See What I Mean — «если ты видишь, что я имею в виду»), в основе которого находился язык LISP и лямбда-исчисление. На основе языка ISWIM было разработано целое семейство функциональных языков (ML, FP, Miranda и другие).

В то время функциональное программирование было интересно лишь немногим исследователям. Оно начало набирать популярность в 1978 году, когда Джон Бэкус, создатель языка Фортран, опубликовал статью «Можно ли освободить программирование от стиля фон Неймана?» Бэкус критиковал традиционные языки программирования и выступал за развитие новой парадигмы, которую он назвал «функциональное программирование». В ней делался акцент на функционалы (функции, аргументами которых являются другие функции). В своей статье, за которую он был удостоен премии Тьюринга, Бэкус описал язык FP (Functional Programming), в котором не использовались переменные. Статья пробудила интерес исследователей к функциональным языкам и привела к появлению новых подобных языков.

В настоящее время существует два обширных семейства функциональных языков. Первое образовано языками, созданными на основе LISP, второе — языками, созданными на основе ISWIM. К первому семейству принадлежат разновидности языка LISP, например Common LISP, и самостоятельные языки, например Scheme.

Ко второму семейству принадлежит язык Standard ML — результат стандартизации языков ML и Норе, созданных в Эдинбургском университете. ML в отличие от LISP является строго типизированным функциональным языком (strongly-typed language). Это означает, что все выражения в этом языке имеют тип, который определяется системой во время компиляции (статический тип). Кроме этого, программист может вводить новые типы, определяя абстрактные типы данных. Язык ML допускает определение модулей и общих модулей, которые называются функторами. В языке Норе, в отличие от ML, типы требуется определять явно.

* * *

ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ: ПРИМЕРЫ РЕАЛИЗАЦИИ

Ниже приведены примеры определения функции факториала на разных языках программирования. Обратите внимание на схожесть синтаксиса языков, принадлежащих к двум основным семействам функциональных языков. В языках, подобных USP (Scheme, Норе и ML), используются переменные, определение факториала является рекурсивным и напоминает его определение на языке Java, которое приводилось несколькими страницами ранее. В языке FP, напротив, переменные не используются. В определении на языке FP используется функция iota. Эта функция возвращает список всех натуральных чисел, меньших заданного числа. К этому списку применяется конструкция / *, осуществляющая умножение его элементов. Конструкция /op расширяет бинарную операцию, применяя ее ко всем элементам списка.

Определение на языке LISP:

(defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1)))))

Определение на языке Scheme:

(define factorial

(lambda (n)

(if (= n0) 1 (*n (factorial (-n 1))))))

Определение на языке Hope:

dec fact: num — > num;

- - - fact 0 < = 1;

- - - fact n < = n*fact(n — 1);

Определение на языке ML

fun f (0: int): int = 1

|f (n: int): int = n * f(n — 1)

Определение на языке FP:

fact =/* op iota

* * *

БЕСКОНЕЧНЫЕ СПИСКИ ЯЗЫКА HASKELL

Следующие определения двух бесконечных списков на языке Haskell помогут вам понять разницу между «жадными» и «ленивыми» вычислениями. Эти определения являются рекурсивными, то есть используют сами себя.

Первое определение соответствует списку натуральных чисел. По индукции предполагается, что список уже определен корректно. Все элементы списка увеличиваются на единицу, таким образом, получается список 2, 3, 4…., к которому добавляется единица. В определении все элементы списка натуральных чисел увеличиваются на единицу с помощью конструкции «mар (+1) naturales».

Второе определение соответствует списку чисел Фибоначчи. Предположим, что этот список уже определен. В определении списка чисел Фибоначчи каждому числу ставится в соответствие следующее число, затем вычисляется сумма в каждой такой паре чисел. В определении «listafibs» ставится в соответствие «хвосту» listafibs, который получается с помощью конструкции «tail listafibs». Далее соответствующие элементы двух списков складываются с помощью конструкции «zipWith (+)».

naturales = 1: map (+1) naturales

listafibs = 0:1: zipWith (+) listafibs (tail listafibs)

Эти определения являются корректными, так как в них используются «ленивые» вычисления. Если бы в них, как в большинстве других языков, использовались «жадные» вычисления, то компьютер обрабатывал бы эти определения бесконечно долго. Обратите внимание, что для определения натуральных чисел сначала требуется выявить бесконечный список, после чего прибавить единицу ко всем его элементам.

* * *

В языках LISP и ML используются «жадные» вычисления (greedy evaluation). Это означает, что все аргументы функции вычисляются перед ее использованием.

Также существуют языки, где применяются «ленивые» вычисления, в частности Haskell, Lazy ML, некоторые версии языка Норе и в особенности язык Miranda, созданный Дэвидом Тернером на основе языков KRC и SASL. В этих языках аргумент оценивается только тогда, когда требуется узнать его значение. Это позволяет создавать программы, которые выполнялись бы бесконечное время, если бы в них использовались «жадные» вычисления.

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

Главная страница сайта, посвященного языку Miranda, который был создан Дэвидом Тёрнером.

Логическая парадигма

После создания императивных и функциональных языков возникла еще одна альтернативная парадигма. Эта третья парадигма получила название логического программирования. Логическое программирование отличается тем, что при создании таких языков программирования используется формальная логика, которая изучает принципы доказательств и формирования корректных умозаключений. Ее не следует путать с математической логикой, которая используется в информатике.

В императивном и функциональном программировании программа понимается как функция, которая выдает результат на основе заданных входных значений. В императивных языках программа — это последовательность команд, определяющих порядок чтения карточек с входными данными и записывающих выходные данные на других карточках после выполнения необходимых вычислений. В логических языках программы реализуют отношения. С помощью множества правил, называемых дизъюнктами Хорна, программист указывает, какие факты являются истинными, а пользователь может сформировать запрос к программе для оценки истинности некоторого отношения. Вычисления основаны на принципе резолюции Робинсона и заключаются в оценке того, истинно или ложно заданное пользователем отношение, либо в указании случаев, когда это отношение является истинным.

* * *

ДИЗЪЮНКТЫ ХОРНА

Дизъюнкты Хорна — это множество логических правил вида «если антецедент является истинным, то консеквент является истинным». Можно сказать, что дизъюнкты Хорна представляют собой логические операции импликации, содержащие множество предпосылок и единственное следствие.

Предпосылок может быть 0, 1 или более:

а1^а2 ^… ^ aN —> b.

* * *

Самым известным логическим языком является Пролог (PROLOG — от фр. PROgrammation еп LOGique). Он был разработан в 1972 году и является единственным логическим языком, широко используемым на данный момент. Первая версия была разработана под руководством Алана Колмерауэра в университете ЭксМарсель группой, работавшей над созданием искусственного интеллекта, при участии британского логика Роберта Ковальски из Эдинбургского университета. Пролог появился в результате слияния двух направлений исследований. Первое, во главе которого стоял Колмерауэр, не было напрямую связано с информатикой, а было посвящено изучению естественного языка; второе, возглавляемое Ковальски, было сосредоточено на автоматическом доказательстве теорем. На этот язык повлияли В-грамматика (нотация, использованная для описания языка Алгол-68) и язык Planner, разработанный в Стэнфордском университете. Успех Пролога был обусловлен его реализацией усилиями Дэвида Уоррена из группы Ковальски в Эдинбургском университете. Так называемая абстрактная машина Уоррена (VAM) исполняла программы со скоростью, сравнимой со скоростью исполнения программ на языке LISP.

* * *

ОПРЕДЕЛЕНИЕ НА ЯЗЫКЕ ПРОЛОГ

Представим в качестве примера небольшую программу на Прологе, вычисляющую натуральные числа. Для этого определим nat (N) так, что это условие будет выполняться только в том случае, когда N — натуральное. Определение является конструктивным в том смысле, что вычисление натуральных чисел будет производиться только тогда, когда мы будем задавать вопрос, какие значения N удовлетворяют заданному нами условию. Программа выглядит так:

nat(N): — N = 0.

nat (N): — nat(Np), N is Np + 1

В первой строке указано, что ноль является натуральным числом. Вторая строка означает, что если существует натуральное число Np, то Np + 1 также является натуральным. Если говорить более формально, то программа указывает, что N является натуральным, если N равно нулю или если существует такое Np, что N равно Np + 1.

* * *

Формальное описание языков программирования

Описание синтаксиса и семантики первых языков программирования производилось неформальными методами. Научное сообщество приступило к рассмотрению вопросов синтаксиса языков программирования. В 1960 году для описания синтаксиса языка Алгол-60 Джон Бэкус и Петер Наур создали нотацию BNF (форма Бэкуса — Наура), которая оказалась очень полезной при формальном описании синтаксиса языка и в значительной степени способствовала его разработке. Несколько лет спустя была обнаружена существенная схожесть формы Бэкуса — Наура с правилами грамматики, которые в IV веке до н. э. сформулировал Панини для описания классического санскрита.

Одновременно с созданием BNF известнейший лингвист, философ и политический публицист Ноам Хомский создал свою теорию грамматики, известную как иерархия Хомского. В рамках этой теории грамматики и языки, их порождающие, делятся на четыре типа в зависимости от их условной сложности. К типу 3 относятся регулярные грамматики, которые являются наиболее строгими. К типу 2 относятся контекстно-свободные грамматики, которые можно описать посредством BNF.

К типу 1 относятся контекстно-зависимые грамматики, к типу 0 — неограниченные грамматики. Каждая следующая обладает большей выразительностью, чем грамматики предыдущих типов. Иерархия Хомского связана с вычислительной мощностью. Вычислительная система общего назначения способна распознавать фразы на любом языке с грамматикой типа 0. К этой категории вычислительных систем относятся машина Тьюринга и лямбда-исчисление. Конечные автоматы являются вычислительными системами типа 3.

Несколько лет спустя швейцарский ученый Никлаус Вирт, лауреат премии Тьюринга и создатель множества языков, описал синтаксис языка Pascal с помощью синтаксических диаграмм и расширенной формы Бэкуса — Наура, EBNF (Extended BNF). Эти нотации не являются более выразительными, чем BNF, однако в настоящее время они широко используются, так как существуют программы, автоматически генерирующие распознаватели синтаксиса по его заданному описанию.

Лингвист Ноам Хомский, создатель иерархии грамматик, носящей его имя.

Меньший успех имела формальная спецификация семантики языков программирования, то есть описание их поведения. Было разработано несколько спецификаций, но ни одна из них не пользуется такой популярностью, как формальные средства описания синтаксиса.

Первой из предложенных была VDL (Vienna Definition Language), созданная в венской лаборатории IBM для формального определения языка PL/I. Она состоит из двух частей: транслятора, выстраивающего абстрактное синтаксическое дерево для программы на языке PL/I, и интерпретатора, который указывает, как следует исполнять или интерпретировать программу, соответствующую этому дереву. Эта семантика называется операционной семантикой и является крайне подробной. Так как язык PL/I очень объемен, беспорядочен и изобилует частными случаями, его формальная спецификация также очень объемна и сложна для понимания. За свои размеры она получила шутливое название VTD — Vienna Telephone Directory («Венский телефонный справочник»). Тем не менее создание этой спецификации стало важным достижением в данной области.

Работы в венской лаборатории были продолжены, и появилась вторая, улучшенная версия спецификации — VDM (англ. Vienna Development Method — венский метод разработки), содержащая несколько особых свойств для создания спецификаций императивных языков. Эта спецификация была создана в 1982 году как объединение точек зрения Динеса Бьёрнера и Клиффа Джонса, которые легли в основу двух школ программирования — датской и английской соответственно. VDM использовался для созданий спецификаций языков Pascal и Алгол-60, а также для подмножества языка Ада’79.

С другой стороны, выдающийся американский ученый Роберт Флойд в 1967 году показал, как можно оценить корректность программы с помощью утверждений (assertions), помещенных в определенные участки программы. Каждое утверждение — это логическая формула, устанавливающая некое отношение между переменными программы. Утверждение остается истинным по завершении программы и устанавливает связь между ее входными и выходными значениями. Метод Флойда улучшил и дополнил британский логик Чарльз Хоар, изложив его в виде набора аксиом и правил вывода, связанных с построением языков программирования, и дав определение аксиоматической семантике. В 1973 году Хоар и Вирт опубликовали аксиоматическую спецификацию подмножества языка Pascal. Во время работы над ней они обнаружили некоторые недостатки в языке и исправили их, создав новую, улучшенную версию Pascal. В следующем году Хоар и Лоуэр изучили возможность одновременного использования аксиоматической и операционной семантики. Эдсгер Дейкстра представил понятие слабейшего предусловия в 1973 году.

Дональд Кнут (слева) и Гэрман Цапф обсуждают свойства новой компьютерной типографики. Стэнфордский университет, Калифорния, 1980 год.

Существуют и другие способы описания семантики языка. В 1968 году силами Дональда Кнута, одного из самых уважаемых специалистов в области вычислительных систем, известного своим чувством юмора, была создана атрибутивная грамматика.

Эта грамматика подробным образом изучается применительно к методам компиляции. Существует и четвертый тип семантики — денотационная, которая была разработана в Оксфордском университете американцами Даной Скоттом и британцем Кристофером Стрэчи в начале 1970-х. В денотационной семантике каждой программе присваивается значение, называемое денотацией (denotation), выраженное в терминах математических объектов. Денотация, как правило, является функцией, сопоставляющей входные и выходные значения программы. Проводились исследования систем для генерации компиляторов на основе денотационной семантики языка, однако на данный момент подобные системы являются крайне неэффективными.

Теория вычислительных систем далека от того момента, когда найдут применение все ранее полученные результаты и будут объединены ранее созданные теории. Напротив, эволюция вычислительных систем продолжается, и она как никогда связана с развитием технологий, дающих нам возможности, о которых раньше нельзя было и мечтать. Языки программирования управляют не только нашими компьютерами, но и телевизорами, мобильными телефонами и даже простейшей бытовой техникой. Мы вновь совершаем первые шаги в новый мир. Как вы увидели, современный облик нашего мира сформировался не случайно, а в результате упорного труда человека. Тем не менее настоящее — лишь эпизод по дороге к непредсказуемому, но, вне всяких сомнений, удивительному будущему.