* * *
ДИЗЪЮНКТЫ ХОРНА
Дизъюнкты Хорна — это множество логических правил вида «если антецедент является истинным, то консеквент является истинным». Можно сказать, что дизъюнкты Хорна представляют собой логические операции импликации, содержащие множество предпосылок и единственное следствие.
Предпосылок может быть 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, однако в настоящее время они широко используются, так как существуют программы, автоматически генерирующие распознаватели синтаксиса по его заданному описанию.