Бизенц Торра - Том 15. От абака к цифровой революции. Алгоритмы и вычисления

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

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

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

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

* * *

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

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

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

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