Более сложные проекты
Может показаться, что некоторые проекты данного раздела невозможно выполнить до конца, однако все они были реализованы на Прологе. Некоторые из них просто являются усложнениями программ, которые рассматривались ранее, а другие – совершенно новые и требуют знакомства с литературой по искусственному интеллекту или по информатике.
1. Дана карта, которая описывает дороги, соединяющие города. Написать программу планирования поездки между двумя городами, которая выдает расписание предполагаемой поездки. Данные, описывающие карту, могут включать расстояния, состояние дороги, уклон дороги, возможность заправки топливом вдоль разных дорог.
2. В существующих Пролог-системах встроенные арифметические операции предусмотрены только для целых чисел. Разработайте пакет программ, поддерживающий арифметические операции над рациональными числами, представленными в виде целой и дробной частей или в виде мантиссы и порядка.
3. Написать процедуры обращения и умножения матриц.
4. Компиляцию с языка высокого уровня на язык низкого уровня можно представить себе как последовательное преобразование синтаксических деревьев. Написать такой компилятор сначала для компиляции арифметических выражений. Затем добавить управляющие структуры (типа if-then-else).Точное соблюдение синтаксиса ассемблера в данном случае не столь существенно. Например, арифметическое выражение х+1 может быть «упрощено» до ассемблерной операции inc x, где incопределена как одноместная операция. Проблема распределения регистров может быть отложена на потом за счет предположения, что объектный код предназначен для выполнения на машине с магазинной (стековой) памятью (безадресная машина),
5. Разработать представление для сложной настольной игры, такой как шахматы или го, и разобраться в том, как возможности Пролога в части сопоставления образцов могут быть использованы при реализации стратегий для этих игр.
6. Разработать формализм для описания набора аксиом, например, из теории групп, евклидовой геометрии, денотационной семантики, и исследовать проблему создания программы доказательства теорем для этих областей.
7. Интерпретатор утверждений Пролога может быть написан на самом Прологе. Напишите интерпретатор, реализующий иные семантики выполнения Пролога, такие как более гибкий порядок выполнения (вместо жесткого слева-направо), возможно, с использованием какого-нибудь «расписания» или планировщика.
8. Ознакомиться по литературе по искусственному интеллекту с вопросом построения планов решения задач, и реализовать генератор планов.
9. Решить с помощью средств Пролога задачу интерпретации контурного рисунка в терминах некоторой лежащей в его основе сцены. Характеристики рисунка могут быть помечены переменными, представляющими соответствующие характеристики сцены. Тогда рисунок соответствует набору ограничений, которым должны удовлетворять эти переменные.
10. Написать программу, которая, используя правила грамматики, осуществляет разбор предложений вида;
Fred saw John.
Магу was seen by John.
Fred told Mary to see John.
John was believed to have been seen by Fred.
Was John believed to have told Mary to see Fred?
11. В исследованиях по искусственному интеллекту используется система специальных правил (продукций), которая представляет собой последовательность правил вида «Если ситуация, то действие». Как оказалось, в задачах искусственного интеллекта с помощью таких правил удобно описывать «экспертные знания». Например, для реальных экспертных систем, использующих такие правила, типичны следующие предложения, содержащие «экспертные знания»:
Фармакология: Если агент X есть четырехвалентная соль аммония и противоаритмическое средство, а агент Y есть салицилат, то X и Y будут реагировать, порождая повышенную абсорбцию за счет образования ионной пары.
Игра в шахматы; Если белый король может быть придвинут к черному слону и при этом расстояние от белого короля до этого слона более одной клетки, то тогда этот слон в безопасности.
Медицина: Если культура высевается из крови и граммреакция организма отрицательна и морфологически организм есть палочка, и пациент является «хозяином» организма, то имеется 60% шансов на то, что этот организм естьPseudomonas aeruqinosa.
Напишите Пролог-программу интерпретации набора продукционных правил. Рассмотрите такие области как определение растений или животных по характерным признакам. Например, подобное правило из ботаники могло бы выглядеть так:
Если растение имеет стебель квадратного сечения, парные листья, двухгубчатые закрытые цветы, а его плод состоит из четырех маленьких орешков, заключенных в кожуру, то это растение принадлежит семейству Labiatae.
Таким образом, если программа спросит нас: «у цветка квадратный стебель?», то ответив «нет» мы тем самым исключаем возможность того, что он принадлежит семейству Labiatae.
12. Написать программу переводящую определенный класс предложений на английском языке на язык исчисления предикатов.
13. Написать программу доказательства теорем в исчислении предикатов.
14. Написать программу-«психиатр», которая выдает ответы, основанные на ключевых словах, имеющихся во вводимой информации. Эта программа напоминает ту, что рассматривалась в гл. 3, и которая заменяла ключевые слова в предложении на другие слова. Типичный диалог такой программы мог выглядеть следующим образом (ответы программы выделены курсивом):
What is your problem? На что жалуетесь?
This is too much work. Очень много работы.
What else do you regard as too much work? Что еще вы имеете в виду, говоря, что очень много работы?
Writing letters. Написание писем.
I see. Please continue.Понятно, продолжайте.
Also washing my mother's car. А также мытье машины моей матери.
Tell me more about your family. Расскажите подробнее о вашей семье.
Why should I? Зачем это?
Why should you what? Что зачем?
Здесь ключевыми словами были this is, motherи why.Недостаток подходящих ключевых слов вызывал ответ I see. Please continue.
15. Написать программу, разбирающую предложения с сообщениями о событиях в некотором учреждении, такие как «Smith will be in his office at 3 pm for a meeting.» (Смит будет в своем учреждении в 3 часа дня для участия в собрании). Программа должна выдавать на печать «суть» предложения, сообщая кто, где и когда, следующим образом:
who: smith Кто: Смит
where: office Где: контора
when: 3 pm Когда: 3 часа дня
what: meeting Что: собрание
Эта «суть» должна быть занесена в базу данных в виде утверждений, с тем чтобы можно было получить ответ на такие вопросы:
Where is Smith at 3 pm? Где Смит в 3 часа?
where: office Где: контора
what: meeting Что: собрание
16. Написать интерфейс для общения на естественном (английском) языке с файловой системой вашей ЭВМ, чтобы можно было получать ответы на такие вопросы:
How many files David own? Сколько файлов принадлежат Дейвиду?
Does Chris share PROG.MAC with David? Использует ли Крис файл PROG.MAC совместно с Дейвидом?
When did Bill change file Когда Билл изменил свой VIDEO.C? файл VIDEO.C?
Программа должна уметь опрашивать различные характеристики файловой системы, такие как принадлежность файлов и даты.
ПРИЛОЖЕНИЕ А. ОТВЕТЫ К НЕКОТОРЫМ УПРАЖНЕНИЯМ
Сюда вошли предлагаемые авторами ответы на некоторые из упражнений, встречающихся в тексте. Для большинства упражнений по программированию редко существует единственный правильный ответ, и, вполне возможно, что у вас получится другой верный ответ, который несколько отличается от предложенного нами. В любом случае следует обязательно опробовать вашу программу на Пролог-системе, имеющейся в вашем распоряжении, чтобы практически проверить, работает она или нет. Но даже в том случае, если вы написали правильную, но отличающуюся от нашей программу, может оказаться поучительным потратить немного времени на изучение альтернативного подхода к решению той же самой задачи.
Упражнение 1.2. Здесь представлены возможные определения семейных отношений.
явл_матерью(М):- мать(М,Ребенок).
явл_отцом(О):- отец(О, Ребенок).
явл_сыном(Сын):- родитель(Род,Сын), Мужчина(Сын).
явл_сестрой(Сес,Ч):- родитель(Род,Сес), родитель(Род,Ч), женщина(Сес), различ(Сес,Ч).
дедушка, (Дед,X):- родитель(Род,Х), отец(Дед,Род).
брат_или_сестра (S1,S2):- родитель(Род,Б1), родитель(Род, S2), различ(S1,S2).
Заметим, что нам приходится использовать предикат различв определении предикатов явл_сестрой и брат_или_сестра. Это гарантирует нам, что система не будет считать, что кто-то может быть сестрой или братом самому себе. Дать определение предиката различна этом этапе вы не сможете.
Упражнение 5.2.Следующая программа циклически считывает символы (из текущего файла ввода) и печатает их, заменяя при этом все строчные буквы 'а' на 'b'.
go:- repeat, get0(C), deal_with(C), fail.
deal_with(97):-!, put(98).
deal_with(X):- put(X).
Наличие «отсечения» в первом правиле предиката deal_withсущественно (почему?). Числа 97 и 98 есть значения кодов ASCII для символов 'а' и 'b' соответственно.
Упражнение 6.2.Почему следующее определение предиката get не работает, если целевое утверждение getзадано с конкретизированным аргументом?
get(X):- new_get(X), X›32.
new_get(X):- repeat, getO(X).
Предположим, мы задали Пролог-системе целевое утверждение get(97) (проверить, является ли следующий печатаемый символ строчной буквой 'а'?), тогда как на самом деле этот следующий символ есть 'b'. Чтобы согласовать get(97),делается попытка согласовать new_get(97).Цель repeatуспешно согласуется, но затем цель get0(97)оказывается несогласуемой (так как следующий символ не 'а'). Тогда начинается возвратный ход. Цель get0 не может быть повторно согласована, а цель repeat- может. Итак, целевое утверждение repeatснова согласуется с базой данных, и вновь делается попытка согласовать get0(97). На этот раз, конечно, следующим символом будет тот, что следует за 'b'. Если это не 'а', то цель оказывается несогласуемой, a repeatснова завершается успешно. Теперь будет проверяться следующий символ и так далее. Фактически происходит следующее: программа считывает новые и новые символы до тех пор пока она, наконец, не находит тот, что совпадает с аргументом. Но это не то, что должен делать предикат get.Правильное определение предиката get,которое обходит эту проблему, а также содержит «отсечение», устраняющее возможность повторного согласования repeatвыглядит следующим образом:
get(X):- repeat, get0(Y), 32‹Y,!, X-Y.
Упражнение 7.10.Вот программа, которая порождает пифагоровы тройки.
pythag(X,Y,Z):- intriple(X,Y,Z), Sumsq is Х*Х + Y*Y, Sumsq is Z*Z.
intriple(X,Y,Z):- is_integer(Sum), minus(Sum,X,Sum1), minus(Sum1,Y,Z).
minus(Sum,Sum,0).
minus(Sum,Dl,D2):- Sum›0, Suml is Sum-1, minus(Suml,Dl,D3), D2 is D3+1.
is_integer(0).
is_integer(N):- is_integer(N1), N is N1 + 1.
С помощью предиката intripleпрограмма порождает все возможные тройки чисел X, Y, Z, а затем проверяет, является ли данная тройка чисел пифагоровой тройкой. Определение intripleгарантирует, что рано или поздно все возможные тройки чисел будут порождены. Прежде всего порождается целое число, являющееся суммой X, Y и Z. Затем с помощью недетерминированного предиката вычитания minusиз него порождаются значения X, Y и Z.
Упражнение 9.1. Здесь приведена программа, транслирующая простое правило грамматики в процедуру на языке Пролог. При этом предполагается, что это правило не содержит; классов словосочетаний с дополнительными аргументами, целевых утверждений внутри фигурных скобок, а также дизъюнкций и отсечений.
?- op(255,xfx,--›).
трансляция ((P1--›P2), (Gl:-G2)):- левая_часть(Р1,S0,S,G1), правая_частъ(Р2,S0,S,G2).
левая_часть(Р0,S0,S,G):- nonvar(PO), tag(P0,S0,S,G).
правая_часть((Pl,P2),S0,S,G):-!, правая_часть(Р1,S0,S1,G1), правая_чacть(P2,S1,S,G2), и(G1, G2,G).
правая_часть(P,S0,S,true):- явл_списком(Р),!, присоединить(Р,S,S0).
правая_часть(P,S0,S,G):- tag(P,S0,S,G).
tag(P,S0,S,G):- atom(P), G =.. [P,S0,S].
и(true,G,G):-!.
и(G,true,G):-!.
и(G1,G2, (G1,G2)).
явл_списком([]):-!.
явл_списком([_ |_]).
присоединить([А|В],C,[A|D]):- присоединить(В,С,D).
присоединить([], Х,Х).
В этой программе переменные, начинающиеся с латинской буквы Р, используются для обозначения описаний словосочетаний (в виде атомов или списков слов) в правилах грамматики. Переменные, начинающиеся с G, обозначают целевые утверждения Пролога. Переменные, начинающиеся с S, обозначают аргументы целевых утверждений Пролога (которые представляют последовательности слов). Для тех, кто заинтересуется, ниже приведена программа, которая способна обрабатывать более общие случаи трансляции правил грамматики. Один из приемов приспособления Пролог-системы к обработке правил грамматики состоит в использовании измененной версии предиката consult, где предложение вида А--›Bтранслируется перед занесением его в базу данных.
?- op(251,fx,{).
?- op(250,fx,}).
?- op(255,XFX,>).
трансляция((Р0--›Q0), (P:- Q)):- левая_часть(P0,S0,S,P), правая_часть(Q0, S0,S,Q1), лин(Q1, Q).
левая_часть((NT,Ts),S0,S,P):- !, nonvar(NT), явл_списком(Тs), tag(NT,S0,Sl,P), присоединить(Ts, S0,S1).
левая_часть (NT,S0,S,P):- nonvar(NT), tag(NT,SO,S,P).
правая_часть((Х1,Х2),S0,S,Р):- правая_часть(Х1,S0,S1,Р1), правая_часть(X2,Sl,S,P2), и(Р1,Р2,Р).
правая_часть((Xl;X2),S0,S,(P1;P2)):-!, или(Xl,S0,S,P1), или(Х2,S0,S,Р2).
правая_часть(Р,S,S,Р):-!.
правая_часть(!,S,S,!):-!.
правая_часть(Ts,SO,S,true):- явл_списком(Тs),!, присоединить(Ts, S,S0).
правая_часть(Х,S0,S,P):- tag(X,S0,S,P).
или(Х,S0,S,Р):- правая_часть(X,S0a,S,Pa), (var(S0a), S0a=S,!, S0=S0a, P=Pa; P=(S0=S0a,Pa)).
tag(X,S0,S,P):- X =..[F|A], присоединить(А,[S0,S],АХ), P =.. [F|AX].
и(true,P,P):-!.
и(P,true,P):-!.
и(P,Q,(P,Q)).
лин(А,А):- var(A),!.
лин((А,В),С):-!, лин1(А,С,R), лин(В,R).
лин(А,А).
лин1(А,(А,R),R):- VAR(A),!.
лин1((А,В),С,R):-!, лин1(А,С,R1), лин1(В,R1,R).
лин1(A,(A,R),R).
явл_списком([]):-!.
явл_списком([_|_]).
присоединить([А|В],С,[А|D]):- присоединить(В,С,D).
присоединить([], X, X).
Упражнение 9.2.Определение универсальной версии предиката phrase (словосочетание)выглядит следующим образом:
phrase(Cтип,Слова):- Стип =.. [Pred|Args], присоединить(Args,[Слова,[]],Newargs), Цель =.. [Pred|Newargs], call (Цель).
где присоеднитьопределен так же как в разд. 3.6.
ПРИЛОЖЕНИЕ В. ПРОГРАММА ПРИВЕДЕНИЯ ФОРМУЛ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ К СТАНДАРТНОЙ ФОРМЕ
Как было обещано в гл. 10, мы проиллюстрируем процесс преобразования формулы исчисления предикатов в стандартную форму, представив фрагменты программы на Прологе, выполняющей это преобразование. Верхний уровень программы выглядит следующим образом:
translate(X):-
implout(X,Xl), /* Этап 1 */
negin(Xl,X2), /* Этап 2 */
skolem(X2,X3,[]), /* Этап 3 */
univout(X3,X4), /* Этап 4 */
conjn(X4,X5), /* Этап 5 */
clausify(X5,Clauses, []), /* Этап 6 */
pclauses(Clauses). /* Печать дизъюнктов */
Здесь приведено определение предиката translate, действующего таким образом, что, если выполнить целевое утверждение translate(X), где X – это формула исчисления предикатов, то программа напечатает эту формулу в стандартной форме в виде последовательности дизъюнктов. В этой программе формулы исчисления предикатов представляются в виде структур языка Пролог, как на это указывалось ранее (в гл. 10). Однако мы сделаем некоторое отступление от предыдущего описания и будем представлять переменные, входящие в формулы исчисления предикатов, атомами языка Пролог, с целью облегчить их обработку. Предполагается, что можно отличить переменные в формулах исчисления предикатов от констант, используя некоторое соглашение относительно формы записи имен. Например, можно считать, что имена переменных всегда начинаются с одной из букв х, у, z. В действительности, переменные всегда вводятся в формулу посредством кванторов и, следовательно, их легко можно опознать. Лишь при чтении результата, печатаемого программой, программисту необходимо помнить, какие имена соответствуют переменным формул исчисления предикатов, а какие константам.
Прежде всего, необходимо объявить операторы для логических связок, используемых в формулах:
?- op(30,fx,~).
?- op(100,xfy,#).
?- op(100,xfy,&).
?- op(150,xfy,-›).
?- op(150,xfy,‹-›).
Следует обратить внимание на то, как определены операторы. В частности ~ имеет более низкий приоритет чем # и &. Для начала, необходимо сделать одно важное предположение. Предполагается, что переменные переименованы таким образом, что в обрабатываемой формуле одна и та же переменная никогда не вводится более чем одним квантором. Это необходимо, чтобы предотвратить возможные конфликты в употреблении имен в дальнейшем.
Для преобразования формул к стандартной форме мы используем метод преобразования дерева, обсуждавшийся в разд. 7.11 и 7.12. При представлении логических связок как функторов, формулы исчисления предикатов превращаются в структуры, которые могут быть изображены в виде деревьев. Каждый из шести основных этапов перевода в стандартную форму представляет некоторое преобразование дерева, которое отображает входное дерево в выходное.