Программирование на языке пролог
Шрифт:
императив(L,[уоu|L]).
То есть, последовательность, возвращаемая после обработки, длиннее исходной последовательности. В общем случае, левая часть грамматического правила может включать нетерминальный символ, за которым, через запятую, следует список слов. Смысл такого правила состоит в том, что в процессе разбора предложения слова, указанные в списке, вставляются во входную последовательность после того, как завершится обработка целевыми утверждениями в правой части правила.
Упражнение 9.3.Приведенное определение для грамматических правил, даже если бы оно было полным, не сможет выполнить функции синтаксического анализатора, если на вход ему подавать последовательность знаков. Почему?
В заключение рассмотрим пример грамматических
14
На «ломаном» русском языке этот пример можно представить следующим образом: «Каждый мужчина нравится некоторая женщина».
все (X, мужчина (X)--› существует (Y, (женщина (Y) & нравится (X)))) .
– Прим. ред.
all(X,(man(X)->exists(Y,(woman(Y)& loves(X,Y)))))
Здесь представлены грамматические правила программы:
?- op(100,xfy,&)
?- op(150,xfy,->)
предложение(Р)--› группа_существительного(Х,Р1,Р),группа_глагола(Х,Р1).
группа_существительного(Х,Р1,Р)--›определитель(Х,Р2,Р1,Р),существительное(Х,Р3), отн_утверждение(Х,Р3,Р2).
группа_существительного(Х,Р,Р)--› наст_существительное(Х).
группа_глагола(Х,Р)--› перех_глагол(Х,Y,Р1),группа_существительного(Y,Р1,Р).
группа_глагола(Х,Р)--› неперех_глагол(Х,Р).
отн_утверждение(Х,Р1,(Р1&Р2))--› [that], группа_глагола(Х,Р2).
отн_утверждение(_,Р,Р)--› [].
определитель(Х,Р1,Р2,аll(Х,(Р1>Р2)))--› [every].
определитель(Х,Р1,Р2,ехists(Х,(Р1&Р2)))--› [а].
существительное(Х,man(Х))--› [man].
существительное(Х, woman (X))--› [woman].
наст_существительное(john)--› [john].
пepex_глагол(X,Y,loves(X,Y))--› [loves].
неперех_глагол(Х,lives(Х)))--› [lives].
В этой программе аргументы используются для построения структур, представляющих смысл словосочетаний. Смысл каждого словосочетания определяет последний аргумент соответствующего правила. Однако смысл словосочетания может зависеть от некоторых других факторов, представленных другими аргументами. Например, глагол lives(живет) порождает высказывание вида lives(X),где X– это объект, обозначающий человека, который живет. Смысл слова livesне позволяет заранее определить, чем будет являться X. Чтобы быть полезным, понятие подобное livesдолжно быть применимо к некоторому конкретному классу объектов. Что представляет этот объект, будет определено из контекста, в котором используется глагол lives.Таким образом, имеем следующее определение: для любого X, применение глагола livesк Xимеет смысл lives(X).Слово, подобное every(каждый), является значительно более сложным. В этом случае понятие, соответствующее слову, должно применяться к некоторой переменной и к двум высказываниям, содержащим эту переменную. Результат можно сформулировать так: если подстановка некоторого объекта вместо переменной в первом утверждении делает что-то истинным, то подстановка того же объекта вместо переменной во втором утверждении также сделает что-то истинным.
Упражнение 9.4.Разберитесь в приведенной программе. Попробуйте проследить выполнение программы при обращении к ней с вопросами типа
?- предложение(Х, [every, man, loves, a, woman],[]).
Во что транслируются программой предложения
ГЛАВА 10. ПРОЛОГ И МАТЕМАТИЧЕСКАЯ ЛОГИКА
Язык программирования Пролог был разработан коллективом во главе с Колмерауэром приблизительно в 1970 году. Это была первая попытка в разработке языка, который позволял бы программисту описывать свои задачи средствами математической логики, а не с помощью традиционных для программирования конструкций, указывающих чтои когдадолжна делать вычислительная машина. Эта идея нашла отражение в названии языка программирования «Пролог» (английское название «Prolog» является сокращением для Programming in Logic.– Перев.).
В этой книге основное внимание было уделено вопросам, связанным с использованием Пролога в качестве инструментального средства для решения практических задач. При этом ничего не говорилось о путях достижения конечной цели – создании системы логического программирования, шагом к которой является Пролог. В этой главе мы намереваемся отчасти исправить это несоответствие, рассмотрев вкратце связь Пролога с математической логикой и вопрос о том, в какой степени программирование на Прологе соответствует идее логического программирования.
10.1. Краткое введение в исчисление предикатов
Если мы намерены обсуждать связь Пролога с математической логикой, то прежде всего необходимо установить, что мы понимаем под логикой. Первоначально логика развивалась как некоторый способ представления определенного класса высказываний, так чтобы можно было, используя формальную процедуру, проверить, справедливы они или нет. Таким образом, логика может быть использована для выражения высказываний, отношений между высказываниями и правил выводаодних высказываний из других. Логическое исчисление специального вида, о котором будет идти речь в этой главе, называется исчисление предикатов.Здесь мы лишь затронем некоторые вопросы исчисления предикатов. Хорошим введением в математическую логику является книга Hodges W. Logic,Penguin Books, 1977. Более подробное обсуждение предмета дано в книге Mendelson E. Intro ductiontoMathematicalLogic,VanNostrandReinhold. [15] Вы так же можете обратиться к любой книге по математической логике. Другая книга, представляющая интерес, написана Chin L. С, Lee R. С.-Т. Symbolic Logic and Mechanical Theorem Proving,Academic Press, 1973. [16]
15
Имеется перевод: Мендельсон Э. Введение в математическую логику.- М.: Наука, 1971.- Прим. перев.
16
Имеется перевод: Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем.- М.: Наука, 1983.- Прим. перев.
Для того чтобы делать высказывания о мире, необходимо уметь описывать объекты этого мира. В исчислении предикатов объекты представляются с помощью термов.Существуют термы трех типов:
• Константа.Это символ, обозначающий индивидуальный объект или понятие. Константы можно рассматривать как атомы языка Пролог и далее будет использоваться соответствующая форма записи. Так, грек, агатаи мирявляются константами.