М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

in addfactors(n div 2) = n end;

1. Сравните исключения в языке 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 с этим значением. Обратите внимание, что это не присваивание; переменной нельзя присвоить значение еще раз, ее только можно будет использовать позднее как аргумент в какой-нибудь элементарной формуле.

Характеристики

Список файлов книги