I.Основы языка VisualProlog/>1. Введение влогическое программирование
В Прологе мыполучаем решение задачи логическим выводом из ранее известных положений. Обычнопрограмма на Прологе не является последовательностью действий, — онапредставляет собой набор фактов с правилами, обеспечивающими получениезаключений на основе этих фактов. Поэтому Пролог известен как декларативныйязык.
Прологвключает механизм вывода, который основан на сопоставлении образцов. С помощьюподбора ответов на запросы он извлекает хранящуюся (известную) информацию.Пролог пытается проверить истинность гипотезы (другими словами, ответить навопрос), запрашивая для этого информацию, о которой уже известно, что онаистинна. Прологовское знание о мире — это ограниченный набор фактов (и правил),заданных в программе.
Одной изважнейших особенностей Пролога является то, что, в дополнение к логическомупоиску ответов на поставленные вами вопросы, он может иметь дело сальтернативами и находить все возможные решения. Вместо обычной работы отначала программы до ее конца, Пролог может возвращаться назад и просматриватьболее одного «пути» при решении всех составляющих задачу частей.
Логикапредикатов была разработана для наиболее простого преобразования принциповлогического мышления в записываемую форму. Пролог использует преимуществасинтаксиса логики для разработки программного языка. В логике предикатов вы,прежде всего, исключаете из своих предложений все несущественные слова. Затемвы преобразуете эти предложения, ставя в них на первое место отношение, а посленего — сгруппированные объекты. В дальнейшем объекты становятся аргументами,между которыми устанавливается это отношение. В качестве примера в табл.представлены предложения, преобразованные в соответствии с синтаксисом логикипредикатов.
Таблица 1.Синтаксис логики предикатовПредложения на естественном языке Синтаксис логики предикатов Машина красивая fun (car) Роза красная red (rose) Билл любит машину, если машина красивая likes (bill, Car) if fun (Car) /> 2. Факты
На Прологеописываются объекты (objects) и отношения (relations), а затем описывает правила(rules), при которых эти отношения являются истинными. Например, предложение
Билл любит собак. (Bill likes dogs.)
устанавливаетотношение между объектами Bill и dogs (Билл и собаки); этим отношением является likes (любит). Нижепредставлено правило, определяющее, когда предложение «Билл любитсобак» является истинным:
Билл любит собак, если собаки хорошие. (Bill likes dogs if the dogs are nice.)
В Прологеотношение между объектами называется фактом (fact). В естественном языкеотношение устанавливается в предложении. В логике предикатов, используемойПрологом, отношение соответствует простой фразе (факту), состоящей из имениотношения и объекта или объектов, заключенных в круглые скобки. Как ипредложение, факт завершается точкой (.).
Нижепредставлено несколько предложений на естественном языке с отношением«любит» (likes):
Билл любит Синди. (Billlikes Cindy)
Синди любит Билла.(Cindy likes Bill)
Билл любит собак. (Bill likes dogs)
А теперьперепишем эти же факты, используя синтаксис Пролога:
likes(bill, cindy).
likes(cindy, bill).
likes (bill, dogs).
Факты, помимоотношений, могут выражать и свойства. Так, например, предложения естественногоязыка «Kermit is green» (Кермит зеленый) и «Caitlin is girl» (Кейтлин —девочка) на Прологе, выражая те же свойства, выглядят следующим образом:
green (kermit).
girl(caitlin)./>3. Предикаты
Отношение вПрологе называется предикатом. Аргументы — это объекты, которыесвязываются этим отношением; в факте
likes (bill, cindy).
отношение likes — это предикат, аобъекты bill и cindy — аргументы.
Примерыпредикатов с различным числом аргументов:
pred(integer, symbol)
person (last, first, gender)
run()
birthday(firstName, lastName,date)
В примерепоказано, что предикаты могут вовсе не иметь аргументов./>4. Правила
Правилапозволяют вам вывести один факт из других фактов. Другими словами, можносказать, что правило — это заключение, для которого известно, что оноистинно, если одно или несколько других найденных заключений или фактов являютсяистинными. Ниже представлены правила, соответствующие связи «любить»(likes):
Синди любит все, что любит Билл. (Cindy likes everything that Bill likes)
Кейтлин любит все зеленое. (Caitlin likes everything that is green)
Используя этиправила, вы можете из предыдущих фактов найти некоторые вещи, которые любятСинди и Кейтлин:
Синди любит Синди. (Cindy likes Cindy)
Кейтлин любит Кермит. (Caitlin likesKermit)
Чтобыперевести эти правила на Пролог, вам нужно немного изменить синтаксис:
likes(cindy,Something):- likes (bill, Something). ilikes(caitlin, Something):- green(Something) .
Символ :-имеет смысл «если», и служит для разделения двух частей правила:заголовка и тела. Можно рассматривать правило и как процедуру. Другими словами, правила
likes(cindy,Something):- likes (bill, Something).
likes(caitlin, Something):- green(Something).
означают: «Чтобыдоказать, что Синди любит что-то, докажите, что Билл любит это» и"Чтобы доказать, что Кейтлин любит что-то, докажите, что это что-то зеленое".С такой «процедурной» точки зрения правила могут«попросить» Пролог выполнить другие действия, отличные отдоказательств фактов, например, напечатать что-нибудь./>5. Запросы(Цели)
Описав вПрологе несколько фактов, можно задавать вопросы, касающиеся отношений междуними. Это называется запросом (query) системы языка Пролог. Можно задавать Прологутакие же вопросы, которые мы могли бы задать вам об этих отношениях.Основываясь на известных, заданных ранее фактах и правилах, вы можете ответитьна вопросы об этих отношениях, в точности так же это может сделать Пролог. Наестественном языке мы спрашиваем: DoesBilllikeCindy? (Билл любит Синди?) По правилам Пролога мыспрашиваем:
likes(bill, cindy).
Получив такойзапрос, Пролог ответит:
yes (да)
потому чтоПролог имеет факт, подтверждающий, что это так. Немного усложнив вопрос, можноспросить на естественном языке: WhatdoesBilllike? (Что любит Билл?) По правилам Пролога мыспрашиваем:
likes(bill, What).
Необходимоотметить, что второй объект — What -начинается с большой буквы, тогда как первыйобъект — bill — нет. Это происходит потому, что bill — фиксированный,постоянный объект — известная величина, a What — переменная.
Переменныевсегданачинаются с заглавной буквы или символа подчеркивания!
Прологвсегда ищет ответ на запрос, начиная с первого факта, и перебирает все факты,пока они не закончатся. Получив запрос о том, что Билл любит, Пролог ответит:
What=cindy
What=dogs
2 Solutions
Так, как емуизвестно, что
likes(bill, cindy).
и
likes(bill, dogs) .
Если бы мыспросили:
What does Cindy like? (Что любит Синди?)
likes(cindy, What).
то Прологответил бы:
What = bill
What = cindy
What = dogs
3 solutions
посколькуПролог знает, что Синди любит Билла, и что Синди любит то же, что и Билл, и чтоБилл любит Синди и собак.
Мы могли бызадать Прологу и другие вопросы, которые можно задать человеку. Но вопросы типа«Какую девушку любит Билл?» не получат решения, т. к. Прологу вданном случае не известны факты о девушке, а он не может вывести заключение,основанное на неизвестных данных: в этом примере мы не дали Прологукакого-нибудь отношения или свойства, чтобы определить, являются ли какие-либообъекты девушками./>6. Размещение фактов,правил и запросов
Предположим,есть следующие факты и правила:
Быстрая машина — приятная. (A fast car is fun).
Большая машина — красивая. (A big car is nice).
Маленькая машина —практичная. (A little car is practical).
Биллу нравится машина, если она приятная.(Bill likes a car if the car is fun).
Исследуя этифакты, вы можете сделать вывод, что Биллу нравится быстрый автомобиль. Вбольшинстве случаев Пролог придет к подобному решению. Если бы не было фактов обыстрых автомобилях, вы не смогли бы логически вывести, какие автомобилинравятся Биллу. Вы можете делать предположения о том, какой тип машин можетбыть крепким, но Пролог знает только то, что вы ему скажете. Пролог не строитпредположений.
Вот пример,демонстрирующий, как Пролог использует правила для ответа на запросы.Посмотрите на факты и правила в этой части программы ch02e01.pro:
likes(ellen, tennis).
likes (John, football).
likes (torn, baseball).
likes (eric, swimming).
likes (mark, tennis).
likes (bill, Activity):-likes (torn, Activity).
Последняястрока в программе является правилом. Это правило соответствует предложениюестественного языка:
Биллу нравится занятие, если Томунравится это занятие. (Bill likes an activity if Tom likesthat activity)
В данномправиле заголовок — это likes (bill, Activity), а тело — likes (torn, Activity). Заметим, что в этомпримере нет фактов о том, что Билл любит бейсбол. Чтобы выяснить, любит ли Биллбейсбол, можно дать Прологу такой запрос:
likes (bill, baseball).
Пытаясь отыскатьрешение по этому запросу, Пролог будет использовать правило:
likes(bill, Activity):-likes(torn, Activity).
Загрузитепрограмму ch02e01.pro в среду визуальной разработки Visual Prolog и запустите ее утилитой Test Goal.
predicates
likes(symbol,symbol)
clauses
likes(ellen,tennis).
likes(John,football).
likes(torn,baseball).
likes(eric,swimming).
likes(mark,tennis).
likes(bill,Activity):-likes(torn,Activity).
goal
likes(bill,baseball).
Утилита Test Goal ответит в окнеприложения:
yes (да)
Системаиспользовала комбинированное правило
likes(bill, Activity):-likes(torn, Activity).
с фактом
likes(torn, baseball).для решения, что likes(bill, baseball).
Попробуйтетакже следующий запрос в GOAL-разделе:
likes (bill, tennis).
Утилита Test Goal ответит:
no (нет)
поскольку:
· нетфактов, которые говорят, что Билл любит теннис;
· отношениеБилла к теннису не может быть логически выведено с использованием данногоправила и имеющихся в распоряжении фактов.
Вполневозможно, что Билл любит теннис в реальной жизни, но ответ Visual Prologоснован только на фактах и правилах, которые вы дали ему в тексте программы./>
7. ПРОГРАММЫНА VISUAL PROLOG
Синтаксис Visual Prolog разработан для того,чтобы отображать знания о свойствах и взаимосвязях.
В отличие отдругих версий Пролога, Visual Prolog — компилятор, контролирующий типы: для каждогопредиката объявляются типы объектов, которые он может использовать. Этообъявление типов позволяет программам Visual Prolog быть скомпилированныминепосредственно в машинные коды, при этом, скорость выполнения сравнима, а внекоторых случаях — и превышает скорости аналогичных программ на языках С и Pascal./>8. Основные разделы Visual Prolog-программ
Обычнопрограмма на Visual Prolog состоит из четырех основных программных разделов, ккоторым относятся:
· разделclauses (предложений);
· разделpredicates(предикатов);
· разделdomains(доменов);
· разделgoal(целей).
Раздел clauses — это сердце Visual Prolog-программы; именно в этотраздел записываются факты и правила, которыми будет оперировать Visual Prolog, пытаясь разрешить цельпрограммы.
Раздел predicates — это тот, в которомобъявляются предикаты и домены (типы) их аргументов (вам не нужно объявлятьпредикаты, встроенные в Visual Prolog).
Раздел domains служит для объявлениядоменов, не являющихся стандартными доменами Visual Prolog.
В разделgoalпомещается цель Visual Prolog-программы./> 9.Раздел предложений
В раздел clauses (предложений) помещаютсявсе факты и правила, составляющие программу. Все предложения для каждогоконкретного предиката в разделе clausesдолжны располагатьсявместе. Последовательностьпредложений, описывающих один предикат, называется процедурой.
Пытаясьразрешить цель, Visual Prolog (начиная с первого предложения раздела clauses) будет просматриватькаждый факт и каждое правило, стремясь найти сопоставление. По мере продвижениявниз по разделу clauses, он устанавливает внутренний указатель на первое предложение,являющееся частью пути, ведущего к решению. Если следующее предложение неявляется частью этого логического пути, то Visual Prolog возвращается кустановленному указателю и ищет очередное подходящее сопоставление, перемещаяуказатель на него (этот процесс называется поиск с возвратом)./>10.Раздел предикатов
Если вразделе clauses программы на Visual Prolog описан собственный предикат, то его необходимообъявить в разделе predicates (предикатов). В результате объявления предиката сообщается,к каким доменам (типам) принадлежат аргументы этого предиката./>11. ОБЪЯВЛЕНИЕПОЛЬЗОВАТЕЛЬСКОГО ПРЕДИКАТА
Объявление предикатаначинается с имени этого предиката, за которым идет открывающая (левая) круглаяскобка, после чего следует ноль или больше доменов (типов) аргументовпредиката:
predicateName(argument_typel OptionalNamel,
argument_type2OptionalName2, …,
argument_typeN OptionalNameN)
После каждогодомена (типа) аргумента следует запятая, а после последнего типа аргумента —закрывающая (правая) скобка. В отличии от предложений в разделе clauses, декларация предикатане завершается точкой. Доменами (типами) аргументов предиката могут бытьлибо стандартные домены, либо домены, объявленные вами в разделе domains. Можно указывать именааргументов OptionalNameK — это улучшает читаемость программы, и не сказывается наскорости ее исполнения, т. к. компилятор их игнорирует./>Имена предикатов
Имя предикатадолжно начинаться с буквы, за которой может располагаться последовательностьбукв, цифр и символов подчеркивания. Буквы должны быть в нижнем регистре!Имя предиката может иметь длину до 250 символов.
В именах предикатов запрещается использовать пробел,символ минус, звездочку и другие алфавитно-цифровые символы. />Аргументыпредикатов
Аргументыпредикатов должны принадлежать доменам, известным Visual Prolog. Эти домены могут бытьлибо стандартными, либо пользовательскими./>12.Раздел доменов
Доменыпозволяют задавать разные имена различным видам данных, которые, в противномслучае, будут выглядеть абсолютно одинаково. В программах Visual Prolog объекты в отношениях(аргументы предикатов) принадлежат доменам, причем это могут быть какстандартные, так и описанные пользователем специальные домены. Раздел domains служит двум полезнымцелям. Во-первых, можно задать доменам осмысленные имена, даже если внутреннеэти домены аналогичны уже имеющимся стандартным. Во-вторых, объявлениеспециальных доменов используется для описания структур данных, отсутствующих встандартных доменах.
Иногда оченьполезно описать новый домен — особенно, когда вы хотите прояснить отдельныечасти раздела predicates. Объявление собственных доменов, благодаря присваиванию осмысленныхимен типам аргументов, помогает документировать описываемые вами предикаты. Рассмотримпример, показывающий, как объявление доменов помогает документироватьпредикаты:
Франк — мужчина, которому 45 лет.
Используястандартные домены, вы можете так объявить соответствующий предикат:
person(symbol, symbol, integer).
В большинствеслучаев такое объявление будет работать хорошо, но не наглядно для чтенияпрограммы. Более правильным было бы следующее описание:
domains
name, sex = symbol
age = integer
predicates
person(name, sex, age)
Одним изглавных преимуществ объявления собственных доменов является то, что Visual Prolog может отслеживать ошибкитипов, например, такие:
same_sex(X,Y):-
person(X, Sex, _),
person(Sex, Y, _).
Несмотря нато, что и name и sex описываются как symbol, они не эквивалентны друг другу. Это и позволяетVisual Prolog определить ошибку, есливы перепутаете их. Это полезно в тех случаях, когда ваши программы очень великии сложны.
Аргументыс типами из специальных доменов не могут смешиваться между собой, даже если этидомены одинаковы.
Следующийпример программы при его загрузке приведет к ошибке типа.
Domains product, sum =integer
predicates
add_em_up(sum,sum,sum)
multiply_em(product,product,product)
clauses
add_em_up(X, Y, Sum):-Sum=X+Y.
multiply_em(X,Y,Product):-Product=X*Y.
Эта программавыполняет две операции: складывает и умножает. Зададим ей следующую цель:
add_em_up(32, 54, Sum).
VisualProlog (Test Goal) ответит:
Sum=86
1 Solution
что являетсясуммой двух целых чисел, которые вы передали в программу.
С другойстороны, эта же программа с помощью предиката multiply_em умножает два аргумента.Допустим, мы хотим удвоить произведение 31 на 17. Задаем следующую цель:
multiply_em(31, 17, Sum), add_em_up(Sum, Sum, Answer).
и ждем, что Visual Prolog (Test Goal)ответит:
Sum=527, Answer=1054
1 Solution
Однако вместоэтого вы получите ошибку типа. Это случилось из-за того, что имела местопопытка передать результирующее значение предиката multiply_em, которое относится кдомену product, в качестве первого и второго аргументов (которые должныотносится к домену sum) в предикат add_em_up. И хотя оба эти домена соответствуют типу integer — это различные домены.
Еслипеременная в предложении используется более чем в одном предикате, она должнабыть одинаково объявлена в каждом из них.
/>13.Раздел цели
По существу,раздел goal (цели) аналогичен телу правила: это просто список подцелей. Цельотличается от правила лишь следующим:
· заключевым словом goal не следует :-;
· призапуске программы Visual Prolog автоматически выполняет цель.
Если всеподцели в разделе goal истинны, — программа завершается успешно. Если же какая-топодцель из раздела goal ложна, то считается, что программа завершается неуспешно (хотячисто внешне никакой разницы в этих случаях нет, — программа просто завершитсвою работу)./>14.Декларации и правила
В Visual Prolog есть нескольковстроенных стандартных доменов. Их можно использовать при декларации типоваргументов предикатов без описания в разделе domains.
Основныестандартные домены перечислены в табл. 1.
Таблица 1.Основныестандартные доменыДомен Описание Реализация short Короткое, знаковое, количественное Все платформы 16 бит (-32 768—32 767) ushort Короткое, беззнаковое, количественное Все платформы 16 бит (0—65 535) long Длинное, знаковое, количественное Все платформы 32 бит (-2 147 483 648-2 147 483 647) ulong Длинное, беззнаковое, количественное Все платформы 32 бит (0-4 294 967 295) integer Знаковое, количественное, имеет платформо-зависимый Платформы 1 6 бит (-32 768-32 767) размер Платформы 32 бит (-2 147 483 648-2 147 483 647) unsigned Беззнаковое, количественное, имеет платформо-зависимый размер Платформы 16 бит (0—65 535) Платформы 32 бит (0-4 294 967 295) byte Все платформы 8 бит (0— 55) word Все платформы 16 бит (0—65 535) dword Все платформы 32 бит (0—4 294 967 295)
Синтаксическизначение, принадлежащее одному из целочисленных доменов, записывается какпоследовательность цифр, которой в случае знакового домена может предшествоватьне отделенный от нее пробелом знак минус. Имеются также восьмеричные ишестнадцатеричные синтаксисы для основных.
Домены типов byte, word и dword наиболее удобны приработе с машинными числами. В основном используются типы integer и unsigned, а также short и long (и их беззнаковыеаналоги) для более специализированных приложений.
В объявленияхдоменов ключевые слова signed и unsigned могут использоваться вместе со стандартнымидоменами типов byte, word и dword для построения новых базовых доменов. Так:
domains
i8 = signed byte
создает новыйбазовый домен в диапазоне от -128 до +127.
Другиебазовые домены показаны в табл. 2[1].
Таблица 2.Основныестандартные доменыДомен Описание и реализация char Символ, реализуемый как беззнаковый byte. Синтаксически это символ, заключенный между двумя одиночными кавычками: 'а' real Число с плавающей запятой, реализуемое как 8 байт в соответствии с соглашением IEEE; эквивалентен типу double в С. При необходимости, целые автоматически преобразуются в real string
Последовательность символов, реализуемых как указатель на байтовый массив, завершаемый нулем, как в С. Для строк допускается два формата:1. Последовательность букв, цифр и символов подчеркивания, причем первый символ должен быть строчной буквой.2. Последовательность символов, заключенных в двойные кавычки.
Примеры строк:
telephone_number «railway ticket» «Dorid Inc»
Строки, которые пишутся в программе, могут достигать длины в 255 символов, в то время как строки, которые система Visual Prolog считывает из файла или строит внутри себя, могут достигать (теоретически) до 4 Гбайт на 32-битных платформах symbol Последовательность символов, реализуемых как указатель на вход в таблице идентификаторов, хранящей строки идентификаторов. Синтаксис — как для строк
Идентификаторыи строки взаимозаменяемы в программе, однако Visual Prolog хранит их раздельно. Идентификаторыхранятся в таблице идентификаторов, а для представления используются лишьих индексы в этой таблице, но не сами строки идентификаторов. Это означает, чтосопоставление идентификаторов выполняется очень быстро, а в случае если онивстречаются в программе несколько раз, то и хранение их компактно. Строки же нехранятся в поисковой таблице, и при необходимости сопоставления Visual Prolog проверяет их символ засимволом. Вы сами должны определять, какой домен лучше использовать в каждойконкретной программе./>Заданиетипов аргументов при декларации предикатов
Объявлениедоменов аргументов в разделе predicates называется заданием типов аргументов. Предположим,имеется следующая связь объектов:
Франк — мужчина, которому 45 лет.
Факт Пролога,соответствующий этому предложению естественного языка, может быть следующим:
person(frank, male, 45).
Для тогочтобы объявить person (человек), как предикат с этими тремя аргументами, вы можетеразместить в разделе predicates следующую строку:
person(symbol, symbol, unsigned).
Здесь длявсех трех аргументов использованы стандартные домены. Отныне всякий раз приработе с предикатом person, вы должны передавать ему три аргумента, причем первые два должныбыть типа symbol, а третий — типа integer.
Если впрограмме используются только стандартные домены, то нет необходимостииспользовать раздел domain; вы уже видели несколько программ такого типа.
Или,предположим, что вы хотите описать предикат, который сообщал бы позицию буквы валфавите, т. е. цель
alphabet_position(Letter, Position)
должнавернуть вам Position = 1, если Letter = a, Position = 2, если Letter = Ь и т. д. Предложения этого предиката могутвыглядеть следующим образом:
alphabet_position(A_character,N).
Если приобъявлении предиката используются только стандартные домены, то программе ненужен раздел domains. Предположим, что вы хотите описать предикат так, что цель будетистинна, если A_character является N-м символом алфавита.Предложения этого предиката будут такими:
alphabet_position('а', 1). alphabet_position('b', 2).
alphabet_position('с', 3).
alphabet_position(' z1, 26).
Вы можетеобъявить данный предикат следующим образом:
predicates
alphabet_position(char, unsigned)
и тогда вамне будет нужен раздел domains. Если разместить все фрагменты программы вместе,получим:
predicates
alphabet_position(char, integer)
clauses
alphabet_position('a', 1).
alphabet_position('b', 2).
alphabet_position('c', 3).
% здесь находятся остальные буквы
alphabet_position('z', 26).
Нижепредставлено несколько простых целей, которые вы можете использовать:
alphabet_position ('а', 1).
alphabet_position(X, 3).
alphabet_position (' z',What)./>Арность(размерность)
Арностьпредиката — это количество аргументов, которые он принимает. Вы можете иметь двапредиката с одним и тем же именем, но отличающейся арностью. В разделах predicates и clauses версии предикатов содним именем и разной арностью должны собираться вместе; за исключением этогоограничения, различная арность всегда понимается как полное различиепредикатов. Проиллюстрируем это примером/
domains
person = symbol
predicates
father(person)% этотperson — отец
father(person, person)% первыйperson является отцом другого
clauses
father (Man):-father(Man, _) .
father(adam,seth).
father(abraham,isaac)./>Синтаксисправил
Правилаиспользуются в Прологе в случае, когда какой-либо факт зависит от истинностидругого факта или группы фактов. Как мы объясняли ранее в этой главе, в правилеПролога есть две части: заголовок и тело. Ниже представлен обобщенный синтаксисправила в Visual Prolog:
HEAD: — , , ...,.
Заголовок: — ,,…, .
Тело правиласостоит из одной или более подцелей. Подцели разделяются запятыми, определяяконъюнкцию, а за последней подцелью правила следует точка.
Каждаяподцель выполняет вызов другого предиката Пролога, который может быть истиннымили ложным. После того, как программа осуществила этот вызов, Visual Prolog проверяет истинностьвызванного предиката, и если это так, то работа продолжается, но уже соследующей подцелью. Если же в процессе такой работы была достигнута точка, товсе правило считается истинным; если хоть одна из подцелей ложна, то всеправило ложно.
Для успешногоразрешения правила Пролог должен разрешить все его подцели и создатьпоследовательный список переменных, должным образом связав их. Если же одна изподцелей ложна, Пролог вернется назад для поиска альтернативы предыдущейподцели, а затем вновь двинется вперед, но уже с другими значениями переменных.Этот процесс называется поиск с возвратом.
Какупоминалось выше, в качестве разделителя заголовка и тела правила Прологиспользует знак:-, который читается как «если» (if). Однако if Пролога отличается от if, написанного в другихязыках, например в Pascal, где условие, содержащееся в операторе if, должно быть указаноперед телом оператора, который может быть выполнен. Другими словами:
если ЗАГОЛОВОК истинен, тогда ТЕЛОистинно (или: тогда выполнить ТЕЛО
Данный типоператора известен как условный оператор если/тогда (if/then). Пролог же используетдругую форму логики в таких правилах. Вывод об истинности заголовка правилаПролога делается, если (после того, как) тело этого правила истинно, например,так:
ЗАГОЛОВОК истинен, если ТЕЛО — истинно(или: если ТЕЛО может Сыть выполнено).
Учитываявышесказанное, правило Пролога соответствует условной форме тогда/если (then/if)./>Автоматическоепреобразование типов
Совсем необязательно, чтобы при сопоставлении двух Visual Prolog-переменных онипринадлежали одному и тому же домену. Переменные могут быть связаны сконстантами из различных доменов. Такое (избирательное) смешение допускается,т. к. Visual Prolog автоматически выполняет преобразование типов (из одного домена вдругой), но только в следующих случаях:
· междустроками (string) и идентификаторами (symbol);
· междуцелыми, действительными и символами (char). При преобразовании символа в числовое значениеэтим значением является величина символа в коде ASCII.
Аргумент издомена my_dom, который объявлен следующим образом:
domains
my_dom = % — это стандартный домен
можетсвободно смешиваться с аргументами из этого основного домена и с аргументамивсех совместимых с ним стандартных доменов. Если основной домен — string, то с ним совместимыаргументы из домена symbol; если же основной домен integer, то с ним совместимы домены real, char, word и др. Такоепреобразование типов означает, например, что вы можете:
· вызватьпредикат с аргументами типа string, задавая ему аргументы типа symbol, и наоборот;
· передаватьпредикату с аргументами типа real параметры типа integer;
· передаватьпредикату с аргументами типа char параметры типа integer;
· использоватьв выражениях и сравнениях символы без необходимости получения их кодов в ASCII.
Существуетнабор правил, определяющих, к какому домену принадлежит результат смешиванияразных доменов. Эти правила будут детально рассмотрены далее./>15.Другие разделы программ
Теперь, когдавы ознакомились с такими разделами программ Visual Prolog, как clauses, predicates, domains и goal, поговорим о некоторыхдругих, часто используемых разделах программ: facts, constants и различных глобальных (global) разделах./>Разделфактов
Программа на Visual Prolog представляет собой наборфактов и правил. Иногда в процессе работы программы бывает необходимомодифицировать (изменить, удалить или добавить) некоторые из фактов, с которымиона работает. В этом случае факты рассматриваются как динамическая или внутренняябаза данных, которая при выполнении программы может изменяться. Дляобъявления фактов программы, рассматривающихся как части динамической (илиизменяющейся) базы данных, Visual Prolog включает специальный раздел — facts.
Ключевоеслово facts объявляет раздел фактов. Именно в этой секции вы объявляетефакты, включаемые в динамическую базу данных. Отметим, что в ранних версиях Visual Prolog для объявления разделафактов использовалось ключевое слово database, т. е. ключевое слово facts — синоним устаревшегоключевого слова database. В Visual Prolog есть несколько встроенных предикатов,облегчающих использование динамических фактов./>Разделконстант
В своихпрограммах на Visual Prolog вы можете объявлять и использовать символические константы.Раздел для объявления констант обозначается ключевым словом constants, за которым следуют самиобъявления, использующие следующий синтаксис:
=
— имя символическойконстанты, а — это то, что вы присваиваете этойконстанте. Каждое завершается символом новой строки и,следовательно, на одной строке может быть только одно описание константы.Объявленные таким образом константы могут позже использоваться в программах.
Рассмотримследующий фрагмент программы:
constants
zеrо = О
one = 1
two = 2
hundred = (10*(10-1)+10)
pi = 3.141592653
ega = 3
slash_fill = 4
red = 4
Передкомпиляцией программы Visual Prolog заменит каждую константу на соответствующую ейстроку.
Наиспользование символических констант накладываются следующие ограничения:
· описаниеконстанты не может ссылаться само на себя:
my_number = 2*my_number/2% не допускается
· этоприведет к сообщению об ошибке «Recursion in constant definition» (Рекурсия вописании константы);
· вописаниях констант система не различает верхний и нижний регистры.Следовательно, при использовании в разделе программы clauses идентификатора типа constants, его первая буква должнабыть строчной для того, чтобы избежать путаницы между константами ипеременными.
· впрограмме может быть несколько разделов constants, однако объявлениеконстанты должно производиться перед ее использованием;
· идентификаторыконстант являются глобальными и могут объявляться только один раз.Множественное объявление одного и того же идентификатора приведи к сообщению обошибке «Constant identifier can only be declared once» (Идентификаторконстанты может объявляться только один раз)./>Директивыкомпилятора
Visual Prolog поддерживает несколько директивкомпилятора, которые можно добавлять в программу для сообщения компиляторуспециальных инструкций по обработке вашей программы при ее компиляции. Кромеэтого, вы можете устанавливать большинство директив компилятора с помощьюкоманды меню среды визуальной разработки Visual Prolog Options/Project/CompilerOptions.
Директива include
Для тогочтобы избежать многократного набора повторяющихся процедур, вы можетеиспользовать директиву include.
Ниже приведенпример того, как это делается.
1. Создаетефайл (например, MYSTUFF.PRO), в котором объявляете свои наиболее I часто используемыепредикаты (с помощью разделов domains и predicates) и даете их описание в разделе clauses.
2. Пишетеисходный текст программы, которая будет использовать эти процедуры.
3. В«допустимых областях» исходного текста программы размещаете строку:include «mystuff.pro»
«Допустимыеобласти» — это любое место программы, в котором вы можете расположить декларациюразделов domains, facts, predicates, clauses или goal.
Прикомпиляции исходных текстов программы Visual Prolog вставит содержание файлаMYSTUFF.PRO прямо в окончательныйтекст файла для компиляции.
Директиву include можно использовать длявключения в исходный текст (практически любого) часто используемого фрагмента.Кроме того, любой включаемый в программу файл может, в свою очередь, включатьдругой файл (однако каждый файл может быть включен в вашу программу только одинраз).
II. Унификация и поиск с возвратом
1. Сопоставлениеи унификация
Рассмотрим программу ch04e01.pro(рис.1) с точки зрения того, как утилита Test Goal будет отыскивать все решения следующей цели written_by(X,Y).
domains
title,author = symbol
pages=unsigned
predicates
book(title,pages)
written_by(author,title)
long_novel(title)
clauses
written_by(fleming, «DRNO»).
written_by(melville,«MOBY DICK»).
book(«MOBYDICK», 250).
book(«DRNO», 310).
long_novel(Title) :-
written_by(_,Title),
book(Title,Length),
Length> 300.
Рис. 1. Листинг программы ch04e01.pro
Пытаясьвыполнить целевое утверждение written_by(X, Y), Visual Prolog должен проверить каждоепредложение written_by(X, Y) в программе. Сопоставляя аргументы X и Y саргументами каждого предложения written_by, Visual Prolog выполняет поиск отначала программы до ее конца. Обнаружив предложение, соответствующее целевомуутверждению, Visual Prolog присваивает значения свободным переменным таким образом, чтоцелевое утверждение и предложение становятся идентичными. Говорят, что целевоеутверждение унифицируется с предложением. Такая операция сопоставленияназывается унификацией.
Поскольку X и Y являютсясвободными переменными в целевом утверждении, а свободная переменная может бытьунифицирована с любым другим аргументом (и даже с другой свободной переменной),то целевое утверждение может быть унифицировано с первым предложением written_by в программе, какпоказано ниже:
written_by(X,Y).
¯¯
written_by(fleming,«DRNO»).
Visual Prolog устанавливаетсоответствие, Xстановится связанным с fleming, a Y – “dr no”. В этот момент Visual Prolog напечатает:
X=fleming,Y=«DR NO»
Поскольку Test Goal ищет все решения длязаданной цели, целевое утверждение также будет унифицировано и со вторымпредложением written_by:
written_by(melville,«MOBY DICK»).
Test Goal печатает второе решение:
X=melville,Y=«MOBY DICK»
2Solutions
Рассмотрим,как Visual Prolog выполнит следующее целевое утверждение:
long_novel(X).
Когда Visual Prolog пытается выполнитьцелевое утверждение, он проверяет, действительно ли обращение можетсоответствовать факту или заголовку правила. В нашем случае устанавливаетсясоответствие с
long_novel(Title)
Visual Prolog проверяет предложениедля long_novel, пытаясь завершить сопоставление унификацией аргументов.Поскольку в целевом утверждении X — свободная переменная, то она может быть унифицирована слюбым другим аргументом. Title также не является связанным в заголовкепредложения long_novel. Целевое утверждение соответствует заголовку правила, иунификация выполняется. Впоследствии Visual Prolog будет пытатьсясогласовывать подцели с правилом
long_novel(Title):-
written_by(_,Title), book(Title, Length), Length>300.
Пытаясьвыполнить согласование тела правила, Visual Prolog обратится к первойподцели в теле правила — written_by(_, Title). Поскольку авторство книги является несущественным,на месте аргумента author появляется анонимная переменная (_). Обращение written_by (_, Title) становится текущейподцелью, и Пролог ищет решение для этого обращения.
Пролог ищетсоответствие с данной подцелью от вершины и до конца программы. В результатедостигается унификация с первым фактом для written_by, а именно:
written_by(_,Title),
¯¯
written_by(fleming, «DR NO»).
Переменная Title связывается с «dr no», и к следующей подцели book (Title, Length) обращение выполняетсяуже с этим значением переменной. Далее Visual Prolog начинает очереднойпроцесс поиска, пытаясь найти соответствие с обращением к book. Так как Title связан с «dr no»,фактическоеобращение выглядит как book(«DR NO», Length). Процесс поиска опятьначинается с вершины программы. Заметим, что первая попытка сопоставления спредложением book(“MOBY DICK", 250) завершится неудачно, и Visual Prolog перейдет ко второмупредложению book в поиске соответствия. Здесь заголовок книги соответствуетподцели, и Visual Prolog связывает переменную Length с величиной 310.
Теперь третьепредложение в теле long_novel становится текущей подцелью:
length> 300.
Visual Prolog выполняет сравнение,завершающееся успешно: 310 больше, чем 300. В этот момент все подцели в телеправила выполнены, и, следовательно, обращение long_novel(X) успешно. Так как X в обращении былунифицирован с переменной Title в правиле, то значение, с которым связывается Title при подтвержденииправила, возвращается и унифицируется с переменной X. Переменная Title в случае подтвержденияправила имеет значение «dr no»,поэтому Visual Prolog выведет:
X=«DRNO»
1Solution.2. Поискс возвратом
Часто прирешении реальной задачи мы придерживаемся определенного пути для ее логическогозавершения. Если полученный результат не дает искомого ответа, мы должнывыбрать другой путь.
Так, вам, возможно, приходилось играть в лабиринт.Один из верных способов найти конец лабиринта — это поворачивать налево накаждой развилке лабиринта до тех пор, пока вы не попадете в тупик. Тогдаследует вернуться к последней развилке и попробовать свернуть вправо, послечего опять поворачивать налево на каждом встречающемся распутье. Путемметодичного перебора всех возможных путей вы, в конце концов, найдете выход.
Visual Prolog при поиске решениязадачи использует именно такой метод проб и возвращений назад; этот методназывается поиск с возвратом. Если, начиная поиск решения задачи (илицелевого утверждения), Visual Prolog должен выбрать между альтернативными путями, тоон ставит маркер у места ветвления (называемого точкой отката) ивыбирает первую подцель, которую и станет проверять. Если данная подцель невыполнится, Visual Prolog вернется к точке отката и попробует проверить другую подцель.
predicates
likes(symbol,symbol)
tastes(symbol,symbol)
food(symbol)
clauses
likes(bill,X):-
food(X),tastes(X,good) .
tastes(pizza,good).
tastes(brussels_sprouts,bad).
food(brussels_sprouts).
food(pizza).
Рис. 2. Программа ch04e02.pro
Эта маленькаяпрограмма составлена из двух множеств фактов и одного правила. Правило,представленное отношением likes, утверждает, что Билл любит вкусную пищу.
Чтобыувидеть, как работает поиск с возвратом, дадим программе для решения следующеецелевое утверждение:
likes(bill,What).
Когда Прологпытается произвести согласование целевого утверждения, он начинает поиск свершины программы.
В данномслучае Пролог будет искать решение, производя с вершины программы поисксоответствия с подцелью likes (bill, what).
Онобнаруживает соответствие с первым предложением в программе и переменная What унифицируется спеременной X.Сопоставление с заголовком правила заставляет Visual Prolog попытаться удовлетворитьэто правило. Производя это, он двигается по телу правила и обращается к первойнаходящейся здесь подцели: food(X).
Есливыполняется новое обращение, поиск соответствия для этого обращения вновьначинается с вершины программы.
Пытаясьсогласовать первую подцель, Visual Prolog (начиная с вершины) производит сопоставление скаждым фактом или заголовком правила, встреченным в программе.
Онобнаруживает соответствие с запросом у первого же факта, представляющегоотношение food. Таким образом, переменная X связывается со значениемbrussels_sprouts. Поскольку существуетболее чем один возможный ответ на обращение food(X), Visual Prolog ставит точку возврата(маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом указывает на томесто, откуда Пролог начнет поиск следующего возможного соответствия для food(X).
Когдаустановление соответствия обращения завершается успешно, говорят, что обращениевозвращается, и может быть испытана очередная подцель.
Посколькупеременная Xсвязана с brussels_sprouts, следующее обращение будет выполняться так:
tastes(brussels_sprouts,good)
и Visual Prolog вновь начнет поиск свершины программы, пытаясь согласовать это вращение. Поскольку соответствующихпредложений не обнаруживается, обращение завершается неудачно, и теперь Visual Prolog запускает механизм возврата.Начиная поиск с возвратом, Пролог отступает к последней позиции, где былауставлена точка отката. В данном случае Пролог возвращается к факту
food(brussels_sprouts).
Единственнымспособом освободить переменную, однажды связанную в предложении, является откатпри поиске с возвратом.
Когда Прологотступает к точке поиска с возвратом, он освобождает все переменные, связанныепосле этой точки, и будет искать другое решение для исходного обращения.
Обращениебыло food(X),так что связанность brussels_sprouts с X отменена. Теперь Пролог пытается заново произвести решение дляэтого обращения. Он обнаруживает соответствие с фактом food (pizza); на этот раз переменнаяX связывается со значениемpizza.
Прологпереходит к следующей подцели в правиле, имея при этом новую связаннуюпеременную. Производится новое обращение, tastes (pizza, good), и начинается поиск(опять от вершины программы). На этот раз соответствие найдено, и целевоеутверждение успешно выполняется.
Посколькупеременная what в целевом утверждении унифицирована с переменной X в правиле likes, а переменная X связана со значением pizza, переменная What отныне связана созначением pizza и Visual Prolog сообщает решение:
What=pizza
1Solution3. Управлениепоиском решений
Встроенныймеханизм поиска с возвратом в Прологе может привести к поиску ненужных решений,в результате чего теряется эффективность, например, когда желательно найтитолько одно решение. В других случаях может оказаться необходимым продолжатьпоиск дополнительных решений, даже если целевое утверждение уже согласовано.
Visual Prolog обеспечивает дваинструментальных средства, которые дают возможность управлять механизмом поискас возвратом: предикат fail, который используется для инициализации поиска свозвратом, и cut или отсечение (обозначается !) — для запрета возможностивозврата.Использование предиката fail
Visual Prolog начинает поиск свозвратом, когда вызов завершается неудачно. В определенных ситуациях бываетнеобходимо инициализировать выполнение поиска с возвратом, чтобы найти другиерешения. Visual Prolog поддерживает специальный предикат fail, вызывающий неуспешноезавершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту отсравнения 2=3 или другой невозможной подцели. Программа ch04e06.pro (рис. 3) иллюстрируетиспользование этого специального предиката.
domains
name= symbol
predicates
father(name,name)
everybody
clauses
father(leonard,katherine).
father(carl, jason).
father(carl,marilyn)
everybody:-
father(X,Y),
write(X,"is ",Y,"'s father\n"), fail.
Рис. 3. Программа ch04e06.pro
Пустьнеобходимо найти все решения цели father (X,Y). Используя утилиту Test Goal, можно записать цель как
goal
father(X,Y).
Test Goal найдет все решенияцели father (X,Y)и отобразит значения всех переменных следующим образом:
X=leonard,Y=katherine
X=carl,Y=jason
X=carl,Y=marilyn
3Solutions
Но если выскомпилируете эту программу и запустите ее, то Visual Prolog найдет только первое подходящеерешение для father (X,Y).После того как целевое утверждение, определенное в разделе goal, выполнено впервые,ничто не говорит Прологу о необходимости продолжения поиска с возвратом.Поэтому обращение к father приведет только к одному решению. Как же найти все возможныерешения? Предикат everybody в программе ch04e06.pro использует fail для поддержки поиска свозвратом.
Задачапредиката everybody — найти все решения для father и выдать полный ответ.Сравните предыдущие ответы утилиты Test Goal с целью father(X,Y) и ответы на выполнениеследующей цели:
goal
everybody.
отображенныесгенерированной программой:
leonardis katherine' s father
carlis Jason's father
carlis marilyn's father
Предикат everybody использует поиск свозвратом с тем, чтобы получить все решения для father (X, Y), заставляя Прологвыполнять поиск с возвратом сквозь тело правила everybody:
father(X, Y),
mite(X,"is ",Y, "'s father\n"),
fail.
fail не может быть согласован (он всегда неуспешен),поэтому Visual Prolog вынужден повторять поиск с возвратом. При поиске с возвратом онвозвращается к последнему обращению, которое может произвести множественныерешения. Такое обращение называют недетерминированным. Недетерминированноеобращение является противоположностью детерминированному обращению,которое может произвести только одно решение.
Предикат write не может быть вновьсогласован (он не может предложить новых решений), поэтому Visual Prolog должен выполнить откатдальше, на этот раз к первой подцели в правиле.
Обратитевнимание, что помещать подцель после fail в теле правила бесполезно. Предикат fail все время завершаетсянеудачно, нет возможности для достижения подцели, расположенной после fail.Прерывание поиска с возвратом:отсечение
Visual Prolog предусматриваетвозможность отсечения, которая используется для прерывания поиска с возвратом;отсечение обозначается восклицательным знаком (!). Действует отсечение просто:через него невозможно совершить откат (поиск с возвратом).
Отсечениепомещается в программу таким же образом, как и подцель в теле правила. Когдапроцесс проходит через отсечение, немедленно удовлетворяется обращение к cut и выполняется обращениек очередной подцели (если таковая имеется). Однажды пройдя через отсечение, уженевозможно произвести откат к подцелям, расположенным в обрабатываемомпредложении перед отсечением, и также невозможно возвратиться к другимпредложениям, определяющим обрабатывающий предикат (предикат, содержащийотсечение).
Существуютдва основных случая применения отсечения.
· Есливы заранее знаете, что определенные посылки никогда не приведут к осмысленнымрешениям (поиск решений в этом случае будет лишней тратой времени), — применитеотсечение, — программа станет быстрее и экономичнее. Такой прием называют зеленымотсечением.
· Еслиотсечения требует сама логика программы для исключения из рассмотренияальтернативных подцелей. Это — красное отсечение.
В этомвопросе даются примеры, показывающие, как следует использовать отсечение,рассматриваются несколько условных правил (rl, r2 и rЗ), которые определяютусловный предикат г, а также несколько подцелей — а, b, с и т. д.6.1.1 Предотвращение поиска с возвратомк предыдущей подцели в правиле
r1:- а,b,
!,
c.
Такая записьявляется способом сообщить Visual Prolog о том, что вас удовлетворит первое решение,найденное им для подцелей а и b. Имея возможность найти множественные решения при обращениик с путем поиска с возвратом, Пролог при этом не может произвести откат (поискс возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не можетвозвратиться к другому предложению, определяющему предикат rl.
В качествеконкретного примера рассмотрим программу ch04e07.pro (рис. 4).
predicates
buy_car(symbol,symbol)
car(symbol,symbol,integer)
colors(symbol,symbol)
clauses
buy_car(Model,Color):-
car(Model,Color,Price),
colors(Color,sexy),
!,
Price
car(maserati,green,25000).
car(corvette,black,24000).
car(corvette,red,26000).
car(porsche,red,24000).
colors(red,sexy).
colors(black,mean).
colors(green,preppy).
goal
buy_car(corvette,Y).
Рис. 4. Рис. 4. Программа ch04e07.pro
В данномпримере поставлена цель: найти corvette (Корвет) приятного цвета, подходящий постоимости. Отсечение в правиле buy_car означает, что поскольку в базе данных содержитсятолько один «Корвет» приятного цвета, хоть и со слишком высокойценой, то нет нужды искать другую машину. Получив целевое утверждение
buy_car(corvette,Y)
программаотработает следующие шаги:
1. Visual Prolog обращается к саг, первойподцели для предиката buy_car.
2. Выполняетпроверку для первой машины, maserati, которая завершается неудачно.
3. Затемпроверяет следующее предложение саг и находит соответствие, связывая переменнуюColor со значением black.
4. Переходитк следующему обращению и проверяет, имеет ли выбранная машина приятный цвет.Черный цвет не является приятным в данной программе, таким образом, проверказавершается неудачно.
5. Выполняетпоиск с возвратом к обращению саг и снова ищет corvette, удовлетворяющий этомукритерию.
6. Находитсоответствие и снова проверяет цвет. На этот раз цвет оказывается приятным, и Visual Prolog переходит к следующейподцели в правиле: к отсечению. Отсечение немедленно выполняется,«замораживая» все переменные, ранее связанные в этом предложении.
7. Переходитк следующей (и последней) подцели в правиле, к сравнению
Price
8. Проверказавершается неудачно, и Visual Prolog пытается совершить поиск с возвратом с цельюнайти другую машину для проверки. Отсечение предотвращает попытку решитьпоследнюю подцель, и наше целевое утверждение завершается неудачно.6.1.2 Предотвращение поиска с возвратомк следующему предложению
Отсечениеможет быть использовано, как способ сообщить Visual Prolog, что он выбрал верноепредложение для определенного предиката. Например, рассмотрим следующийфрагмент:
r(1):-
!,
а,b, с.
r(2):-
!,
d.
r(3):-
!,
с.
r(_):-
write(«Thisis a catchall clause.»).
Использованиеотсечения делает предикат r детерминированным. В данном случае Visual Prolog выполняет обращение к r с единственным целымаргументом. Предположим, что произведено обращение r(l). Visual Prolog просматривает программув поисках соответствия для обращения; он находит его с первым предложением,определяющим r.Поскольку имеется более чем одно возможное решение для данного обращения, Visual Prolog проставляет точкувозврата около этого предложения.
Теперь Visual Prolog начинает обработку телаправила, проходит через отсечение и исключает возможность возвращения к другомупредложению r.Это отменяет точки поиска с возвратом, повышая эффективность выполненияпрограммы, а также гарантирует, что отлавливающее ошибки предложение будетвыполнено лишь в том случае, если ни одно из условий не будет соответствоватьобращению к r.
Обратитевнимание, что конструкция такого типа весьма похожа на конструкцию case в других языкахпрограммирования; условие проверки записывается в заголовке правил. Повозможности, всегда следует помещать проверочное условие именно в заголовокправила, — это повышает эффективность программы и упрощает ее чтение.Детерминизм и отсечение
Если быпредикат r,определенный в предыдущей программе, не содержал отсечений, то это был бы недетерминированныйпредикат (способный производить множественные решения при помощи поиска свозвратом). В предыдущих реализациях Пролога программисты должны были обращатьособое внимание на недетерминированные предложения из-за сопутствующих имдополнительных требований к ресурсам памяти. Теперь Visual Prolog сам выполняет проверкуна недетерминированные предложения, облегчая вашу работу.
В Прологесуществует директива компилятора check_determ. Если вставить эту директиву в самое началопрограммы, то Visual Prolog будет выдавать предупреждение в случае обнаружениянедетерминированных предложений в процессе компиляции.
Можнопревратить недетерминированные предложения в детерминированные, вставляяотсечения в тело правил, определяющих данный предикат.Предикат not
Следующаяпрограмма ch04el0.pro (рис. 5.) демонстрирует, как вы можете использовать предикат not для того, чтобы выявитьуспевающего студента: студента, у которого средний балл (GPA) не менее 3.5 и укоторого в настоящее время не продолжается испытательный срок.
domains
name= symbol
gpa= real
predicates
honor_student(name)
student(name,gра)
probation(name)
clauses
honor_student(Name) :-
student(Name,GPA),
GPA>=3.5,
not(probation(Name)).
student(«Betty Blue», 3.5).
student(«David Smith», 2.0).
student(«John Johnson», 3.7).
probation(«Betty Blue»).
probation(«David Smith»).
goal
honor_student(X) .
Рис. 5. Программа ch04e10.pro
Прииспользовании предиката not необходимо иметь в виду следующее:
Предикат not будетуспешным, если не может быть доказана истинность данной подцели.
Это приводитк предотвращению связывания внутри not несвязанных переменных. При вызове изнутри not подцели со свободнымипеременными, Visual Prolog возвратит сообщение об ошибке: «Free variables not allowed in not or retractall» (Свободныепеременные не разрешены в not или retract). Это происходит вследствие того, что длясвязывания свободных переменных в подцели, подцель должна унифицироваться скаким-либо другим предложением и выполняться. Правильным способом управлениянесвязанными переменными подцели внутри not является использованиеанонимных переменных.
Первый примерработает правильно:
likes(bill, Anyone) :-% Anyone — выходной аргумент
likes(sue,Anyone),
not(hates(bill,Anyone).
В этомпримере Anyone связывается посредством likes (sue, Anyone) до того, как Visual Prolog делает вывод, что hates (bill, Anyone) не является истиной.Данное предложение работает корректно.
Если примеризменить таким образом, что обращение к not будет выполнятьсяпервым, то получите сообщение об ошибке: «Free variable are not allowed in not» (Свободныепеременные в not не разрешены).
likes(bill,Anyone):-% Это не будет работать правильно
not(hates(bill,Anyone)),
likes(sue,Anyone).
Даже если вызамените в not (hates (bill, Anyone)) Anyone на анонимную переменную, и предложение, таким образом, не будетвозвращать ошибку, все равно получите неправильный результат.
likes(bill,Anyone):- % Это не будет работать правильно
not(hates(bill,_)),
likes(sue,Anyone).
Этопредложение утверждает, что Биллу нравится кто угодно, если неизвестно ничего отом, кого Билл ненавидит, и если этот «кто-то» нравится Сью.Подлинное предложение утверждало, что Биллу нравится тот, кто нравится Сью, ипри этом Билл не испытывает к этому человеку ненависти.
Неверное использованиепредиката not приведет к сообщению об ошибке или кошибкам в логике вашей программы.Простые и составныеобъекты
До сих пор мыработали только основными видами объектов данных Visual Prolog, таких как числа, идентификаторыи строки. Visual Prolog может создавать не только простые, но и составные типы.5. Простыеобъекты данных
Простойобъект данных — это переменная или константа. Не путайте это значение слова«константа» с символьными константами, которые вы определяете вразделе constants программы. То, что мы здесь называем константой, это нечто,идентифицирующее объект, который нельзя изменять: символ (char), число (integer или real) или атом (symbol или string).
Константы включают числа, символы иатомы. Числа и символы были рассмотрены ранее.
Атомы имеют тип идентификатор (symbol) или строка (string). Отличие между ними —главным образом вопрос машинного представления и реализации, и, в основном, оносинтаксически не заметно. Когда атом передается в качестве аргумента при вызовепредиката, то к какому домену принадлежит атом — symbol или string -определяется по тому,как описан этот аргумент в декларации предиката.
Visual Prolog автоматическипреобразует типы между доменами string и symbol, поэтому вы можете использовать атомы symbol в доменах string и наоборот. Однакопринято считать, что объект в двойных кавычках принадлежит домену string, а объект, ненуждающийся в кавычках, домену symbol. Атомы типа symbol — это имена,начинающиеся со строчной буквы и содержащие только буквы, цифры и знакподчеркивания.
Атомы типа string выделяются двойнымикавычками и могут содержать любую комбинацию литер, кроме ASCII-нуля (0, бинарный нуль),который обозначает конец строки атома.
Примеры строки идентификаторов приведены в табл. 1.
Таблица 2.Строки и идентификаторыАтомы-идентификаторы Атомы-строки food «Jesse James» rick_Jones_2nd «123 Pike street» fred_Flintstone_1000_Bс_Bedrock «jon» a «a» new_york «New York» pdcProlog «Visual Prolog, by Prolog Development Center»
Так как string/symbol взаимозаменяемы, ихотличие не существенно. Однако имена предикатов и функторы для составныхобъектов должны соответствовать синтаксическим соглашениям домена symbol.6. Составныеобъекты данных и функторы
Составныеобъекты данных позволяют интерпретировать некоторые части информации как единоецелое таким образом, чтобы затем можно было легко разделить их вновь. Возьмем,например, дату «октябрь 15, 1991». Она состоит из трех частейинформации — месяц, день и год. Представим ее на рис. 1, как древовиднуюструктуру.
/>
Рис. 6. Древовидная структура даты
Можнообъявить домен, содержащий составной объект date:
domains
date_cmp= date(string,unsigned,unsigned)
а затемпросто записать:
D= date(«0ctober»,15,1991) .
Такая записьвыглядит как факт Пролога, но это не так — это объект данных, который вы можетеобрабатывать наряду с символами и числами. Он начинается с имени, называемого функтором(в данном случае date), за которым следуют три аргумента.
Функтор в Visual Prolog — не то же самое, чтофункция в других языках программирования; это просто имя, которое определяетвид составного объекта данных и объединяет вместе его аргументы. Функтор необозначает, что будут выполнены какие-либо вычисления.
Аргументысоставного объекта данных могут сами быть составными объектами. Например, выможете рассматривать чей-нибудь день рождения (рис. 2), как информацию соследующей структурой:
/>
Рис. 2. древовиднаяструктура даты рождения.
На языкеПролог это выглядит следующим образом:
birthday(person(«Leo»,«Jensen»),date(«Apr»,14,1960))7. Унификациясоставных объектов
Составнойобъект может быть унифицирован с простой переменной или с составным объектом(возможно, содержащим переменные в качестве частей во внутренней структуре),который ему соответствует. Это означает, что составной объект можноиспользовать для того, чтобы передавать целый набор значений как единый объект,и затем применять унификацию для их разделения. Например:
date(«April»,14,I960)
сопоставляетсяс X и присваивает X значение date («April», 14,1960). Также
date(«April»,14,I960)
сопоставляетсяс date (Mo, Da, Yr) и присваиваетпеременным Мо = «April», Da=14 и Yr = 1960.
8. Использованиенескольких значений как единого целого
Составныеобъекты могут рассматриваться в предложениях Пролога как единые объекты, чтосильно упрощает написание программ. Рассмотрим, например, факт:
owns(john,book(“From Here to Eternity", «James Jones»)).
в которомутверждается, что у Джона есть книга «From Here to Eternity» (Отсюда ввечность), написанная James Jones (Джеймсом Джонсом). Аналогично можно записать:
owns(john, horse (blacky) ) .
что означает:
Johnowns a horse named blacky.(У Джона есть лошадь Блеки.)
Если вместоэтого описать только два факта:
owns(john, «From Here to Eternity»), owns(john, blacky).
то нельзябыло бы определить, является ли blacky названием книги или именем лошади.9. Объявлениесоставных доменов
Рассмотрим,как определяются составные домены. После компиляции программы, которая содержитследующие отношения:
owns(john,book(«From Here to Eternity», «James Jones»)).
и
owns(John, horse (blacky) ).
вы можетепослать системе запрос в следующем виде:
owns(John, X)
Переменная Хможет быть связана с различными типами объектов: книга, лошадь и, возможно,другими объектами, которые вы определите. Отметим, что теперь вы не можете болееиспользовать старое определение предиката owns:
owns(symbol, symbol)
Второйэлемент более не является объектом типа symbol. Вместо этого вы можетедать новое определение этого предиката
owns(name,articles)
Домен articles в разделе domains можно описать так
domains
articles= book(title, author); horse(name)
Точка сзапятой читается как «или» В этом случае возможны два варианта книгабудет определяться своим заглавием и автором, а лошадь будет распознаватьсясвоим именем Домены title, author и name имеют стандартный тип symbol.
К определениюдомена легко могут быть добавлены другие варианты.10. Многоуровневыесоставные объекты
Visual Prolog позволяет конструироватьсоставные объекты на нескольких уровнях. Например:
domains
articles= book(title, author);%Первый уровень
author=author(first_name, last_name) %Второй уровень
title,first_name, last_name = symbol%Третий уровень
Прииспользовании составных объектов со многими уровнями часто помогает такое«дерево» (рис. 7):
/>
Рис. 7. Дерево многоуровневого составного объекта/>
Повтор и рекурсия
Компьютерыспособны повторять одно и то же действие снова и снова, Visual Prolog может выражатьповторение как в процедурах, так и в структурах данных. Идея повторяющихсяструктур данных может показаться странной, но Пролог позволяет создаватьструктуры данных, размер которых не известен во время создания.11. Процессповторения
Программистына языках Pascal, Basic или С, которые начинают использовать Visual Prolog, часто испытываютразочарование, обнаружив, что язык не имеет конструкций for, while илиrepeat. В Прологе не существует прямого способа выраженияповтора. Пролог обеспечивает только два вида повторения
· откат,спомощью которого осуществляется поиск многих решений в одном запросе,
· и рекурсию,в которой процедура вызывает сама себя.
Однако этот недостатокне снижает мощи Пролога. Фактически, Visual Prolog распознает специальныйслучай рекурсии — хвостовую рекурсию — и компилирует ее в оптимизированнуюитерационную петлю. Это означает, что хотя программная логика и выражаетсярекурсивно, скомпилированный код так же эффективен, как если бы программа быланаписана на Pascal или Basic.Использование поиска с возвратомдля организации повторов
Когдавыполняется процедура поиска с возвратом (откат), происходит поиск другогорешения целевого утверждения. Это осуществляется путем возврата к последней изпроверенных подцелей, имеющей альтернативное решение, использования следующейальтернативы этой подцели и новой попытки движения вперед (см. пример ch06e01). Очень часто дляэтого используется директива fail.
predicates
country(symbol)
print_countries
clauses
country(«England»).
country(«France»).
country(«Germany»).
country(«Denmark»).
print_countries:-
country(X),
write(X),%записать значениеХ
nl,%начать новую строку
fail.
print_countries.
goal
print__countnes.
Рис. 8. Программа ch06e01.pro
Предварительные и последующиеоперации
Отметим, чтопрограмма, которая находит решения для целевого утверждения, может выполнятькакие-либо предварительные или завершающие операции. Например, в нашем примерепрограмма могла бы:
1. Напечатать
Somedelightful places to live are… (Некоторые восхитительные места дляпроживания...).
2. Напечатать все решениядля country (X).
3. Завершить печать фразой And maybe others (Могут быть и другие).
Заметьте, чтоprint_countries, определенное впредыдущем примере, уже содержит предложение вывести на печать все решения country (X) и отпечататьзавершающее сообщение.
Первоепредложение для print_countries соответствует шагу 2 и выводит на печать все решения. Его второепредложение соответствует шагу 3 и просто успешно завершает целевое утверждение(потому что первое предложение всегда в режиме fail — «неудачноезавершение»).
Можно было быизменить второе предложение в программе ch06e01.pro.
print_countnes:-
write(«Andmaybe others.»), nl.
котороевыполнило бы шаг 3, как указано.
А что можносказать о шаге 1? В нем нет смысла, когда print_countnes содержал только 2предложения. Но в предикате может быть и три предложения:
print_countries:-
write(«Somedelightful places to live are»), nl,
fail.
pnnt_countnes:-
country(X),
write(X),nl,
fail.
print_countries:-
write(«Andmaybe others.»), nl.
Наличие fail в первом предложенииважно, поскольку он обеспечивает после выполнения первого предложения возврат ипереход ко второму предложению Кроме того, это важно, потому что предикаты write и nl не образуют альтернативСтрого говоря, первое предложение проверяет все возможные решения перед тем,как завершиться неуспехом.
Такая структураиз трех предложений более удобна по сравнению с общепринятым подходом.Использование отката с петлями
Поиск свозвратом является хорошим способом определить все возможные решения целевогоутверждения Но, даже если ваша задача не имеет множества решений, можноиспользовать поиск с возвратом для выполнения итераций Просто определитепредикат с двумя предложениями
repeat
repeat- repeat
Этот приемдемонстрирует создание структуры управления Пролога (см листинг на рис. 2.),которая порождает бесконечное множество решений. Цель предиката repeat — допуститьбесконечность поиска с возвратом (бесконечное количество откатов)
/*Использование repeat для сохранения введенных символов и печатать их до техпор, пока пользователь не нажмет Enter (Ввод)*/
predicates
repeat
typewriter
clauses
repeat.
repeat-repeat.
typewriter:-
repeat,
readchar(C),%Читать символ, его значение присвоить С
write(С),
С= '\r',% Символ возврат каретки (Enter)? или неуспех
goal
typewriter(), nl.
Рис. 9. Листинг 13.2. Программа ch06e02.pro
Программа ch06e02 pro показывает, как работаетrepeat Правило typewriter — описывает процесс приема символов с клавиатуры иотображения их на экране, пока пользователь не нажмет клавишу ()
Правило typewriter работает следующим образом
1 Выполняет repeat (который ничего не делает, ноставит точку отката).
2 Присваивает переменной с значение символа.
3 Отображает С.
4 Проверяет, соответствует ли с коду возвратакаретки.
5 Если соответствует, то — завершение. Если нет —возвращается к точке отката и ищет альтернативы, так как ни write, ни readcharне являются альтернативами,
12. РекурсивныепроцедурыПонятие рекурсии
Одним изспособов организации повторений — рекурсия. Рекурсивная процедура — этопроцедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемызапоминания результатов ее выполнения, потому что любые вычисленные значенияможно передавать из одного вызова в другой как аргументы рекурсивно вызываемогопредиката.
Логикарекурсии проста для осуществления. Представьте себе ЭВМ, способную«понять»:
Найтифакториал числа N:
ЕслиN равно 1, то факториал равен 1
Иначенайти факториал N-1 и умножить его на N.
Этот подходозначает следующее:
первое(«закручиваете» стек), чтобы найти факториал 3, вы должны найти факториал 2, ачтобы найти факториал 2, вы должны вычислить факториал 1. факториал 1 ищетсябез обращения к другим факториалам, т.к. он равен 1, поэтому повторения неначнутся.
второе(«раскручиваете» стек), если у вас есть факториал 1, то умножаете его на 2,чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получитьфакториал 3.
Информацияхранится в области памяти, называемой стековым фреймом (stack frame) или просто стеком (stack), который создаетсякаждый раз при вызове правила. Когда выполнение правила завершается, занятаяего стековым фреймом память освобождается (если это не недетерминированныйоткат), и выполнение продолжается в стековом фрейме правила-родителя.Преимущества рекурсии
Рекурсияимеет три основных преимущества:
· онаможет выражать алгоритмы, которые нельзя удобно выразить никаким другимобразом;
· оналогически проще метода итерации;
· онашироко используется в обработке списков.
Рекурсия —хороший способ для описания задач, содержащих в себе подзадачу такого же типа.Например, поиск в дереве (дерево состоит из более мелких деревьев) ирекурсивная сортировка (для сортировки списка, он разделяется на части, частьсортируются и затем объединяются вместе).
Логическирекурсивным алгоритмам присуща структура индуктивного математическогодоказательства. Приведенная выше рекурсивная программа вычисления факториалаописывает бесконечное множество различных вычислений с помощью всего лишь двухпредложений. Это позволяет легко увидеть правильность этих предложений. Крометого, правильность каждого предложения может быть изучена независимо отдругого.Пример рекурсивного определенияправил
Давайтедобавим к программе о родственных связях еще одно отношение — предок. Определимего через отношение родитель. Все отношение можно выразить с помощью двухправил. Первое правило будет
/>
определятьнепосредственных (ближайших) предков, а второе — отдаленных. Будем говорить,что некоторый Xявляется отдаленным предком некоторого Z, если между X и Z существует цепочкалюдей, связанных между собой отношением родитель-ребенок, как показано нарис.1… В нашем примере на рис. 1. Том — ближайший предок Лиз и отдаленныйпредок Пат.
/>
Рис. 10. Пример отношения предок:(а) X — ближайшийпредок Z; (b) X — отдаленный предок Z.
Первое правилопростое и его можно сформулировать так:
Для всех X и Z,
X — предок Z, если X — родитель Z.
Этонепосредственно переводится на Пролог как
предок(X, Z) :.-родитель( X, Z).
Второеправило сложнее, поскольку построение цепочки отношений родитель может вызватьнекоторые трудности. Один из способов определения отдаленных родственников могбы быть таким, как показано на рис. 2. В соответствии с ним отношение предокопределялось бы следующим множеством предложений:
предок(X, Z) :-
родитель(X, Z).
предок( X, Z) :-
родитель(X, Y), родитель( Y, Z).
предок(X, Z) :-
родитель(X, Y1),
родитель(Y1, Y2),
родитель(Y2, Z).
предок(X, Z) :-
родитель(X, Y1),
родитель(Y1, Y2),
родитель(Y2, Y3),
родитель(Y3, Z).
Рис. 11. Пары предок-потомок, разделенных разным числом поколений.
Эта программадлинна и, что более важно, работает только в определенных пределах. Она будетобнаруживать предков лишь до определенной глубины фамильного дерева, посколькудлина цепочки людей между предком и потомком ограничена длиной нашихпредложений в определении отношения.
Существует,однако, корректная и элегантная формулировка отношения предок — корректная втом смысле, что будет работать для предков произвольной отдаленности. Ключеваяидея здесь — определить отношение предок через него самого. Рис. 3 иллюстрируетэту идею:
Длявсех X и Z,
X- предок Z, если существует Y, такой, что
(1)X — родитель Y и
(2)Y — предок Z.
ПредложениеПролога, имеющее тот же смысл, записывается так:
предок(X, Z) :-
родитель( X, Y), предок( Y, Z).
Теперь мыпостроили полную программу для отношения предок, содержащую два правила: однодля ближайших предков и другое для отдаленных предков. Здесь приводятся они обавместе:
предок(X, Z) :-
родитель(X, Z).
предок(X, Z) :-
родитель(X, Y),
предок(Y, Z).
Рис. 12. /> />
Рекурсивная формулировка отношения предок.
Ключевыммоментом в данной формулировке было использование самого отношения предок в егоопределении. Такие определения называются рекурсивными. Логически онисовершенно корректны и понятны. Рекурсия — один из фундаментальных приемовпрограммирования на Прологе. Без рекурсии с его помощью невозможно решатьзадачи сколько-нибудь ощутимой сложности.Оптимизация хвостовой рекурсии
У рекурсииесть один большой недостаток — она «съедает» память. Всякий раз, когда однапроцедура вызывает другую, информация о выполнении вызывающей процедуры должнабыть сохранена для того, чтобы она (вызывающая процедура) могла, послевыполнения вызванной процедуры, возобновить выполнение на том же месте, гдеостановилась. Это означает, что если процедура вызывает себя 100 раз, то 100различных состояний должно быть записано одновременно (состояния выполнения решениясохраняются в стековом фрейме). Максимальныйразмер стека у 16-битных платформ, таких как IBM PC, работающая под DOS,составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековыхфреймов. На 32-битных платформах стек теоретически может возрасти донескольких гигабайт; но здесь проявятся другие системные ограничения, преждечем стек переполнится. Что же можно сделать, чтобы избежать использования стольбольшого стекового пространства?
Рассмотримспециальный случай, когда процедура может вызвать себя без сохраненияинформации о своем состоянии. Что, если вызывающая процедура не собираетсявозобновлять свое выполнение после завершения вызванной процедуры?
Предположим,что процедура вызывается последний раз, т. е. когда вызванная процедура завершитработу, вызывающая процедура не возобновит свое выполнение. Это значит, чтовызывающей процедуре не нужно сохранять свое состояние, потому что этаинформация уже не понадобится. Как только вызванная процедура завершится,работа процессора должна идти в направлении, указанном для вызывающей процедурыпосле ее выполнения.
Например,допустим, что процедура А вызывает процедуру В, а В — С в качестве своегопоследнего шага. Когда В вызывает С, В не должна больше ничего делать. Поэтому,вместо того чтобы сохранить в стеке процедуры В информацию о текущем состоянииС, мы можем переписать старую сохраненную информацию о состоянии В (котораябольше не нужна) на текущую информацию о С, сделав соответствующие изменения вхранимой информации. Когда С закончит выполнение, она будет считать, что онавызвана непосредственно процедурой А.
Предположим,что на последнем шаге выполнения процедура В вместо процедуры С вызывает себя.Получается, что когда В вызывает В, стек (состояние) для вызывающей в долженбыть заменен стеком для вызванной В. Это очень простая операция, простоаргументам присваиваются новые значения и затем выполнение процессавозвращается на начало процедуры В. Поэтому, с процедурной точки зрения,происходящее очень похоже на всего лишь обновление управляющих переменных вцикле
Эта операцияназывается оптимизацией хвостовой рекурсии (tail recursion optimization) или оптимизациейпоследнего вызова (last-call optimization) Обратите внимание, что по техническимпричинам оптимизация последнего вызова неприменима к рекурсивным функциям.Как задать хвостовую рекурсию
Что означаетфраза «одна процедура вызывает другую, выполняя свои самый последнийшаг»? На языке Пролог это значит.
П вызовявляется самой последней подцелью предложения,
О ранее впредложении не было точек возврата
Нижеприводится удовлетворяющий обоим условиям пример
count(N): -write(N), nl, NewN = N+l,count(NewN) .
Эта процедураявляется хвостовой рекурсией, которая вызывает себя без резервирования новогостекового фрейма, и поэтому не истощает запас памяти Как показывает программа ch06e04 pro (листинг 13 4), если выдадите ей целевое утверждение
count (0) .
то предикат count будет печатать целыечисла, начиная с 0, и никогда не остановится В конечном счете произойдет целочисленноепереполнение, но остановки из-за истощения памяти не произойдет
Листинг13.4. Программа ch06e04.pro
/* Программас хвостовой рекурсией, которая не истощает память */ predicates count(ulong)
clauses
count(N):-
write('\r',N), NewN = N+l, count(NewN).
GOAL nl, count(0).13. Определениесписка
В Прологе список— это объект, который содержит конечное число других объектов. Списки можногрубо сравнить с массивами в других языках, но, в отличие от массивов, длясписков нет необходимости заранее объявлять их размер.
Список,содержащий числа 1, 2 и 3, записывается так:
[1,2, 3]
Каждаясоставляющая списка называется элементом. Чтобы оформить списочнуюструктуру данных, надо отделить элементы списка запятыми и заключить их в квадратныескобки. Вот несколько примеров:
[dog,cat, canary]
[«valerieann», «jennifer caitlin», «benjamin thomas»]14. Объявлениесписков
Чтобыобъявить домен для списка целых, надо использовать декларацию домена, такуюкак:
domains
integerlist= integer*
Символ (*)означает «список чего-либо»; таким образом, integer* означает «списокцелых».
Элементысписка могут быть любыми, включая другие списки. Однако все его элементы должныпринадлежать одному домену. Декларация домена для элементов должна бытьследующего вида:
domains
elementlist= elements*
elements= ....
Здесь elements имеют единый тип(например: integer, real или symbol) или являются набором отличных друг от друга элементов,отмеченных разными функторами. В Visual Prolog нельзя смешивать стандартные типы в списке.Например, следующая декларация неправильно определяет список, составленный изэлементов, являющихся целыми и действительными числами или идентификаторами:
elementlist= elements*
elements= integer; real; symbol/* Неверно */
Чтобыобъявить список, составленный из целых, действительных и идентификаторов, надоопределить один тип, включающий все три типа с функторами, которые покажут, ккакому типу относится тот или иной элемент. Например:
elementlist= elements*
elements= i(integer); r(real); s(symbol)% функторы здесь i,r и s15. Головы ихвосты
Списокявляется рекурсивным составным объектом. Он состоит из двух частей — головы,которая является первым элементом, и хвоста, который является списком,включающим все последующие элементы. Хвост списка — всегда список,голова списка — всегда элемент. Например:
голова [а, b, с] есть а
хвост [а, b, с] есть [b, с]
Чтопроисходит, когда вы доходите до одноэлементного списка? Ответ таков:
голова [с] естьс
хвост [с]есть []
Если выбиратьпервый элемент списка достаточное количество раз, вы обязательно дойдете допустого списка []. Пустой список нельзя разделить на голову и хвост.
Вконцептуальном плане это значит, что список имеет структуру дерева, как идругие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.
/>
Рис. 1.Структура дерева
Одноэлементныйсписок, как, например [а], не то же самое, что элемент, который в него входит,потому что [а] на самом деле — это составная структура данных.16. Работа сосписками
В Прологеесть способ явно отделить голову от хвоста. Вместо разделения элементовзапятыми, это можно сделать вертикальной чертой "|". Например:
[а, b, с] эквивалентно [а| [b, с]] и, продолжаяпроцесс,
[а| [b, с] ] эквивалентно [а| [b| [с] ]], чтоэквивалентно [а| [b| [с| [] ] ] ]
Можноиспользовать оба вида разделителей в одном и том же списке при условии, чтовертикальная черта есть последний разделитель. При желании можно набрать
[а, b, с, d] как [а, b|[с, d]].
В табл. 1.приведены несколько примеров на присвоение в списках.
Таблица 1.Присвоение в спискахСписок 1 Список 2 Присвоение переменным [X, Y, Z] [эгберт, ест, мороженое] Х=эгберг, У=ест, Z=мороженое [7] [X | Y] Х=7, Y=[] [1, 2, 3, 4] [X, Y | Z] X=l, Y=2, Z=[3,4] [1, 2] [3 | X] fail% неудача 17. Использованиесписков
Списокявляется рекурсивной составной структурой данных, поэтому нужны алгоритмы дляего обработки. Главный способ обработки списка — это просмотр и обработкакаждого его элемента, пока не будет достигнут конец.
Алгоритмуэтого типа обычно нужны два предложения. Первое из них говорит, что делать собычным списком (списком, который можно разделить на голову и хвост), второе —что делать с пустым списком.18. Печатьсписков
Если нужнонапечатать элементы списка, это делается так, как показано в листинге 1.
Листинг 1.Программа ch07e01.pro;
domains
list= integer*% Или любой тип, какой вы хотите
predicates
write_a_list(list)
clauses
write_a_list([]),% Если список пустой — ничего не делать
write_a_list([Н|Т]):-%Присвоить Н-голова, Т-хвост, затем...
write(H),nl,
write_a_list(Т).
goal
write_a_list([1,2, 3]).
Вот двацелевых утверждения write_a_list, описанные на обычномязыке:
Печататьпустой список — значит ничего не делать.
Иначе,печатать список — означает печатать его голову (которая является однимэлементом), затем печатать его хвост (список) .
19. Подсчетэлементов списка
Рассмотрим,как можно определить число элементов в списке. Что такое длина списка? Вотпростое логическое определение:
Длина[] — 0.
Длиналюбого другого списка — 1 плюс длина его хвоста.
Можно липрименить это? В Прологе — да. Для этого нужны два предложения (листинг 2).
Листинг2. Программаch07e02.pro
domains
list= integer*
predicates
length_of(list,integer)
clauses
length_of( [ ], 0).
length_of( [ _|T],L) :-
length_of(T,TailLength),
L= TailLength + 1.
Посмотримсначала на второе предложение. Действительно, [_|T] можно сопоставитьлюбому непустому списку, с присвоением т хвоста списка. Значение головы неважно, главное, что оно есть, и компьютер может посчитать его за один элемент.
Такимобразом, целевое утверждение
length_of([1,2, 3], L).
подходитвторому предложению при T=[2, 3]. Следующим шагом будет подсчет длины T. Когда это будет сделано(не важно как), TailLength будет иметь значение 2, и компьютер добавит к нему 1 и затемприсвоит Lзначение 3.
Итак, каккомпьютер выполнит промежуточный шаг? Это шаг, в котором определяется длина [2,3] при выполнении целевого утверждения
length_of([2,3], TailLength).
Другими словами, length_of вызывает сама себя рекурсивно.