От абака к цифровой революции

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

* * *

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

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

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

а₁^а₂ ^… ^ a_N —> 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 веке до н. э. сформулировал Панини для описания классического санскрита.