М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 49
Текст из файла (страница 49)
in addfactors(n div 2) = n end;
-
Сравните исключения в языке ML с исключениями в языках Ada, C++ и Eiffel.
Глава 17
Логическое программирование
Логическое программирование основано на том наблюдении, что формулы математической логики можно интерпретировать как спецификацию вычисления. Стиль программирования при этом становится скорее декларативным, чем процедурным. Мы не выдаем команды, сообщающие компьютеру, что делать; вместо этого мы описываем связь между входными и выходными данными и предоставляем компьютеру «догадаться», как получить из входа выход. В пределах, в которых этого удается достичь, логическое программирование обеспечивает значительно более высокий уровень абстракции с соответствующим преимуществом чрезвычайной краткости программ.
Есть две основные абстракции, которые характеризуют логическое программирование. Суть первой состоит в том, что от таких управляющих операторов, как хорошо известные for и if, мы отказываемся полностью. Вместо них «компилятор» предоставляет чрезвычайно мощный механизм управления, который единообразно применяется ко всей программе. Механизм основан на понятии доказательства в математической логике: программа рассматривается не как пошаговый алгоритм, а как набор логических формул, которые предполагаются истинными (аксиомы), а вычисление — как попытка доказать формулу на основе аксиом программы.
Суть второй абстракции в том, что больше не используются операторы присваивания и явные указатели; вместо этого для создания и декомпозиции структур данных используется обобщенный механизм сопоставления с образцом, названный унификацией. При унификации создаются неявные указатели на компоненты структур данных, но программист видит только абстрактные структуры данных, такие как списки, записи и деревья.
После того как мы обсудим «чистое» логическое программирование, мы опишем компромиссы, введенные в языке Prolog, первом и все еще очень популярном языке логического программирования, используемом на практике.
В то время как проделать вручную вышеупомянутое вычисление довольно утомительно, для компьютера это всего лишь случай без конца повторяющейся задачи, с которой он превосходно справляется. Для выполнения логической программы набор логических формул (программа) и формула-цель, например:
"wor" =>"Hello world"?
предлагаются программной системе, которая названа машиной вывода, потому что она из одних формул выводит другие, являющиеся их следствием, пока проблема не будет решена. Метод логического вывода проверяет, можно ли доказать целевую формулу, исходя из аксиом, т.е. формул программы, которые приняты за истинные. Ответом может быть и «да», и «нет», что в логическом программировании называется «успехом» или «неуспехом». «Неуспех» мог быть получен из-за того, что цель не следует из программы, например, "wro" не является подстрокой "Hello world", или из-за неправильности программы, например, если мы пропустили одну из формул программы. Возможен и третий вариант, когда поиск машины вывода будет продолжаться без выбора того или иного ответа, и, так же как это может случиться с while-циклом в языке С, никогда не завершится.
Основные понятия логического программирования:
• Программа является декларативной и состоит исключительно из формул математической логики.
• Каждый набор формул для того же самого предиката (такого как «с») интерпретируется как процедура (возможно, рекурсивная).
• Конкретное вычисление определяется предложенной целью, т.е. формулой, о которой нужно выяснить, является ли она следствием программы.
• Компилятор является машиной вывода, которая по мере возможности ищет доказательство цели из программы.
Таким образом, каждую логическую программу можно прочитать двояко: как набор формул и как спецификацию вычисления. В некотором смысле, логическая программа — это минимальная программа. В разработке программного обеспечения вас обучают точно определять смысл программы перед попыткой ее реализовать, и для точной спецификации используется формальная нотация, обычно некоторая форма математической логики. Если спецификация является программой, то делать больше нечего, и тысячи программистов можно заменить горсткой логиков. Причина того, что логическое программирование нетривиально, состоит в том, что чистая логика недостаточно эффективна для практического программирования, и поэтому есть этап, который должен быть пройден от научной теоретической логики до ее инженерных приложений в программировании.
В логическом программировании нет никаких «операторов присваивания», потому что управляющая структура единообразна для всех программ и состоит из поиска доказательства формулы. Поиск решений проблемы, конечно, не нов; новым является предположение, что поиск решений вычислительных проблем возможен в рамках общей схемы логических доказательств. Логика стала логическим программированием, когда было обнаружено, что, ограничивая структуру формул и способы, которыми делается поиск доказательств, можно сохранить простоту логических утверждений и тем не менее искать решения проблем эффективным способом. Перед объяснением как это делается, мы должны обсудить, как обрабатываются данные в логическом программировании.
17.2. Унификация
Хорновский клоз (Нот clause) — это формула, в которой с помощью конъюнкции («и»)элементарных формул выводится одиночная элементарная формула:
(s=>t)<=(t = tl||t2)^(S=>tl)
Логическое программирование основано на том наблюдении, что, ограничивая формулы хорновскими клозами, мы получаем правильное соотношение между выразительностью и эффективностью вывода. Такие факты, как t => t, являются выводами, которые ниоткуда не следуют, т. е. они всегда истинны. Вывод также называется головой формулы, потому при записи в инверсной форме оно появляется в формуле первым.
Чтобы инициализировать вычисление логической программы, задается цель:
"wof" => "Hello world"?
Машина вывода пытается сопоставить цель и вывод формулы. В данном случае соответствие устанавливается сразу же: "wor" соответствует переменной s, a "Hello world" — переменной t. Это определяет подстановку выражений (в данном случае констант) для переменных; подстановка применяется ко всем переменным в формуле:
"wor" с "Hello world" c= ("Hello world" = tl || t2) л ("wor" с tl)
Теперь мы должны показать, что:
("Hello world" = t1|| t2) л ("wor" с tl)
является истинным, и это ведет к новому соответствию образцов, а именно попытке установить соответствие "Hello world" с tl || t2. Здесь, конечно, может быть много соответствий, что приведет к поиску. Например, машина вывода может допускать, чтобы tl указывало на "Не", a t2 указывало на "Но world"; эти подстановки затем проводятся во всем вычислении.
Знак «: — » обозначает импликацию, а переменные должны начинаться с прописных букв. Когда задана цель:
?- substring ("wor", "Hello world").
вычисление пытается унифицировать ее с головой формулы; если это удается сделать, цель заменяется последовательностью элементарных формул (также называемых целями):
?- concat ("Hello world", T1,12), substring ("wor", T1).
Цель, которая получается в результате, может состоять из боле? чем одной элементарной формулы; машина вывода должна теперь выбрать одну из них, чтобы продолжить поиск решения. По правилу вычисления языка Prolog машина вывода всегда выбирает крайнюю левую элементарную формулу. В данном примере правило вычисления требует, чтобы concat было выбрано перед рекурсивным вызовом substring.
Головы нескольких формул могут соответствовать выбранной элементарной формуле, и машина вывода должна выбрать одну из них, чтобы попытаться сделать унификацию. Правило поиска в языке Prolog определяет, что формулы выбираются в том порядке, в котором они появляются в тексте программы. При попытке установить соответствие целевой формулы с формулами процедуры substring правило поиска требует, чтобы сначала была выбрана истинная substring (Т,Т), затем вторая формула с substring (S, T1), и, только если она не выполняется, третья формула с substring (S, T2). ,
Основанием для этих, по-видимому, произвольных требований, послужило то, что они дают возможность реализовать язык Prolog на стековой архитектуре точно так же, как языки С и Ada, и сделать большинство вычислений в языке Prolog столь же эффективными, как и в процедурных языках. Вычисление выполняется перебором с откатами (backtracking). В приведенном выше примере:
?- concat ("Hello world", Т1, Т2), substring ("wor", T1).
предположим, что вычисление выбрало для concat подстановку
["Н" -»tl, "ello world" -> t2]
Теперь делается попытка доказать substring ("wor", "H"), которая, очевидно, не выполняется. Вычисление делает откат и пытается найти другое доказательство concat с другой подстановкой. Все данные, необходимые для вычисления substring ("wor", "Н"), можно отбросить после отката. Таким образом, правило вычисления в языке Prolog естественно и эффективно реализуется на стеке.
Чтобы еще улучшить эффективность программ, написанных на языке Prolog, в язык включена возможность, названная обрезанием (cut обозначается «!»), которая позволяет задать указание машине вывода воздержаться от поиска части пространства возможных решений. Именно программист должен гарантировать, что никакие возможные решения не «обрезаны». Например, предположим, что мы пытаемся проанализировать арифметическое выражение, которое определено как два терма, разделенных знаком операции:
expression (T1, OP, T2):- term (T1), operator (OP), !, term (T2).
operator ('+').
operator ('-').
operator ('*').
operator ('/').
и что цель — expression (n, '+', 27). Очевидно, что и п и 27 являются термами, а '+' — одним из операторов, поэтому цель выполняется. Если, однако, в качестве цели задать expression (n,'+', '>'), то вычисление при отсутствии обрезания продолжится следующим образом:
n — терм
'+' соответствует operator ('+')
'>' —нетерм
'+' не соответствует operator('-')
'+' не соответствует operator ('*')
'+' не соответствует operator ('/')
Машина вывода делает откат и пытается доказать operator (OP) другими способами в надежде, что другое соответствие позволит также доказать term (T2). Конечно, программист знает, что это безнадежно: обрезание приводит к тому, что вся формула для expression дает неуспех, если неуспех происходит после того, как будет пройдено обрезание. Конечно, обрезание уводит язык Prolog еще дальше от идеального декларативного логического программирования, но обрезание активно используют на практике для улучшения эффективности программы.
Нелогические формулы
Для практического применения в язык Prolog включены свойства, которые не имеют никакого отношения к логическому программированию. По определению операторы вывода не имеют никакого логического значения в вычислении, поскольку их результат относится только к некоторой среде за пределами программы. Однако операторы вывода необходимы при написании программ, которые открывают файлы, отображают символы на экране и т. п.
Другая область, в которой язык Prolog отходит от чистого логического программирования, — численные вычисления. Конечно, в логике можно определить сложение; фактически, это единственный способ определить сложение строго:
N + 0 = N
N + s (М) = s (К) <= N + М = К
О — это числовой ноль, a s(N) — выражение для числа, следующего за N, так, например, s(s(s(0))) — выражение для числа 3. Формулы определяют «+», используя два правила: 1) число плюс ноль — это само число, и 2) N плюс следующее за М — это следующее за N + М. Очевидно, было бы чрезвычайно утомительно писать и неэффективно выполнять логическую версию для 555 + 777.
Prolog включает элементарную формулу:
Var is Expression
Вычисляется значение Expression, и создается новая переменная Var с этим значением. Обратите внимание, что это не присваивание; переменной нельзя присвоить значение еще раз, ее только можно будет использовать позднее как аргумент в какой-нибудь элементарной формуле.