Реферат: Язык логического программирования Visual Prolog

I. Основы языка Visual Prolog

Введение в логическое программирование

В Прологе мы получаем решение задачи логическим выводом из ранее известных положений. Обычно программа на Прологе не является последовательностью действий, — она представляет собой набор фактов с правилами, обеспечивающими получение заключений на основе этих фактов. Поэтому Пролог известен как декларативный язык.

Пролог включает механизм вывода, который основан на сопоставлении образцов. С помощью подбора ответов на запросы он извлекает хранящуюся (известную) информацию. Пролог пытается проверить истинность гипотезы (другими словами, ответить на вопрос), запрашивая для этого информацию, о которой уже известно, что она истинна. Прологовское знание о мире — это ограниченный набор фактов (и правил), заданных в программе.

Одной из важнейших особенностей Пролога является то, что, в дополнение к логическому поиску ответов на поставленные вами вопросы, он может иметь дело с альтернативами и находить все возможные решения. Вместо обычной работы от начала программы до ее конца, Пролог может возвращаться назад и просматривать более одного «пути» при решении всех составляющих задачу частей.

Логика предикатов была разработана для наиболее простого преобразования принципов логического мышления в записываемую форму. Пролог использует преимущества синтаксиса логики для разработки программного языка. В логике предикатов вы, прежде всего, исключаете из своих предложений все несущественные слова. Затем вы преобразуете эти предложения, ставя в них на первое место отношение, а после него — сгруппированные объекты. В дальнейшем объекты становятся аргументами, между которыми устанавливается это отношение. В качестве примера в табл. представлены предложения, преобразованные в соответствии с синтаксисом логики предикатов.

Синтаксис логики предикатов

Предложения на естественном языке

Синтаксис логики предикатов

Машина красивая

fun (car)

Роза красная

red (rose)

Билл любит машину, если машина красивая

likes (bill, Car) if fun (Car)

Факты

На Прологе описываются объекты (objects) и отношения (relations), а затем описывает правила (rules), при которых эти отношения являются истинными. Например, предложение

Билл любит собак. (Bill likes dogs.)

устанавливает отношение между объектами Billи dogs(Билл и собаки); этим отношением является likes(любит). Ниже представлено правило, определяющее, когда предложение «Билл любит собак» является истинным:

Билл любит собак, если собаки хорошие. (Bill likes dogs if the dogs are nice.)

В Прологе отношение между объектами называется фактом (fact). В естественном языке отношение устанавливается в предложении. В логике предикатов, используемой Прологом, отношение соответствует простой фразе (факту), состоящей из имени отношения и объекта или объектов, заключенных в круглые скобки. Как и предложение, факт завершается точкой (.).

Ниже представлено несколько предложений на естественном языке с отношением «любит» (likes):

Билл любит Синди. (Bill likes Cindy)

Синди любит Билла. (Cindy likes Bill)

Билл любит собак. (Bill likes dogs)

А теперь перепишем эти же факты, используя синтаксис Пролога:

likes(bill, cindy).

likes(cindy, bill).

likes (bill, dogs).

Факты, помимо отношений, могут выражать и свойства. Так, например, предложения естественного языка "Kermitisgreen" (Кермит зеленый) и "Caitlinisgirl" (Кейтлин — девочка) на Прологе, выражая те же свойства, выглядят следующим образом:

green (kermit).

girl(caitlin).

Предикаты

Отношение в Прологе называется предикатом. Аргументы — это объекты, которые связываются этим отношением; в факте

likes (bill, cindy).

отношение likes— это предикат, а объекты billи cindy— аргументы.

Примеры предикатов с различным числом аргументов:

pred(integer, symbol)

person (last, first, gender)

run()

birthday(firstName, lastName, date)

В примере показано, что предикаты могут вовсе не иметь аргументов.

Правила

Правила позволяют вам вывести один факт из других фактов. Другими словами, можно сказать, что правило — это заключение, для которого известно, что оно истинно, если одно или несколько других найденных заключений или фактов являются истинными. Ниже представлены правила, соответствующие связи «любить» (likes):

Синди любит все, что любит Билл. (Cindy likes everything that Bill likes)

Кейтлинлюбитвсезеленое. (Caitlin likes everything that is green)

Используя эти правила, вы можете из предыдущих фактов найти некоторые вещи, которые любят Синди и Кейтлин:

Синди любит Синди. (Cindy likes Cindy)

Кейтлин любит Кермит. (Caitlin likes Kermit)

Чтобы перевести эти правила на Пролог, вам нужно немного изменить синтаксис:

likes(cindy, Something):- likes (bill, Something). ilikes(caitlin, Something):- green (Something) .

Символ :- имеет смысл «если», и служит для разделения двух частей правила: заголовка и тела.Можно рассматривать правило и как процедуру. Другими словами, правила

likes(cindy, Something):- likes (bill, Something).

likes(caitlin, Something):- green (Something).

означают: «Чтобы доказать, что Синди любит что-то, докажите, что Билл любит это» и "Чтобы доказать, что Кейтлин любит что-то, докажите, что это что-то зеленое". С такой «процедурной» точки зрения правила могут «попросить» Пролог выполнить другие действия, отличные от доказательств фактов, например, напечатать что-нибудь.

Запросы (Цели)

Описав в Прологе несколько фактов, можно задавать вопросы, касающиеся отношений между ними. Это называется запросом (query) системы языка Пролог. Можно задавать Прологу такие же вопросы, которые мы могли бы задать вам об этих отношениях. Основываясь на известных, заданных ранее фактах и правилах, вы можете ответить на вопросы об этих отношениях, в точности так же это может сделать Пролог. На естественном языке мы спрашиваем: DoesBilllikeCindy? (Билл любит Синди?) По правилам Пролога мы спрашиваем:

--PAGE_BREAK--

likes(bill, cindy).

Получив такой запрос, Пролог ответит:

yes (да)

потому что Пролог имеет факт, подтверждающий, что это так. Немного усложнив вопрос, можно спросить на естественном языке: WhatdoesBilllike? (Что любит Билл?) По правилам Пролога мы спрашиваем:

likes(bill, What).

Необходимо отметить, что второй объект — What-начинается с большой буквы, тогда как первый объект — bill— нет. Это происходит потому, что bill— фиксированный, постоянный объект — известная величина, aWhat— переменная.

Переменные всегда начинаются с заглавной буквы или символа подчеркивания!

Пролог всегда ищет ответ на запрос, начиная с первого факта, и перебирает все факты, пока они не закончатся. Получив запрос о том, что Билл любит, Пролог ответит:

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

поскольку Пролог знает, что Синди любит Билла, и что Синди любит то же, что и Билл, и что Билл любит Синди и собак.

Мы могли бы задать Прологу и другие вопросы, которые можно задать человеку. Но вопросы типа «Какую девушку любит Билл?» не получат решения, т. к. Прологу в данном случае не известны факты о девушке, а он не может вывести заключение, основанное на неизвестных данных: в этом примере мы не дали Прологу какого-нибудь отношения или свойства, чтобы определить, являются ли какие-либо объекты девушками.

Размещение фактов, правил и запросов

Предположим, есть следующие факты и правила:

Быстрая машина — приятная. (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 likes that activity)

В данном правиле заголовок — это likes(bill, Activity), а тело — likes(torn, Activity). Заметим, что в этом примере нет фактов о том, что Билл любит бейсбол. Чтобы выяснить, любит ли Билл бейсбол, можно дать Прологу такой запрос:

likes (bill, baseball).

Пытаясь отыскать решение по этому запросу, Пролог будет использовать правило:

likes(bill, Activity):- likes(torn, Activity).

Загрузите программу ch02e01.proв среду визуальной разработки VisualPrologи запустите ее утилитой TestGoal.

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).

Утилита TestGoalответит в окне приложения:

yes (да)

Система использовала комбинированное правило

likes(bill, Activity):- likes(torn, Activity).

сфактом

likes(torn, baseball). для решения, что likes(bill, baseball).

Попробуйте также следующий запрос в GOAL-разделе:

likes (bill, tennis).

УтилитаTest Goal ответит:

no (нет)

    продолжение
--PAGE_BREAK--

поскольку:

нет фактов, которые говорят, что Билл любит теннис;

отношение Билла к теннису не может быть логически выведено с использованием данного правила и имеющихся в распоряжении фактов.

Вполне возможно, что Билл любит теннис в реальной жизни, но ответ Visual Prolog основан только на фактах и правилах, которые вы дали ему в тексте программы.

7. ПРОГРАММЫ НА VISUAL PROLOG

Синтаксис VisualPrologразработан для того, чтобы отображать знания о свойствах и взаимосвязях.

В отличие от других версий Пролога, VisualProlog— компилятор, контролирующий типы: для каждого предиката объявляются типы объектов, которые он может использовать. Это объявление типов позволяет программам VisualPrologбыть скомпилированными непосредственно в машинные коды, при этом, скорость выполнения сравнима, а в некоторых случаях — и превышает скорости аналогичных программ на языках С и Pascal.

8. Основные разделы Visual Prolog-программ

Обычно программа на VisualPrologсостоит из четырех основныхпрограммных разделов, к которым относятся:

раздел clauses(предложений);

раздел predicates (предикатов);

раздел domains (доменов);

раздел goal (целей).

Раздел clauses— это сердце VisualProlog-программы; именно в этот раздел записываются факты и правила, которыми будет оперировать VisualProlog, пытаясь разрешить цель программы.

Раздел predicates— это тот, в котором объявляются предикаты и домены (типы) их аргументов (вам не нужно объявлять предикаты, встроенные в VisualProlog).

Раздел domainsслужит для объявления доменов, не являющихся стандартными доменами VisualProlog.

В разделgoalпомещается цель VisualProlog-программы.

9. Раздел предложений

В раздел clauses(предложений) помещаются все факты и правила, составляющие программу. Все предложения для каждого конкретного предиката в разделе clausesдолжны располагаться вместе. Последовательность предложений, описывающих один предикат, называется процедурой.

Пытаясь разрешить цель, VisualProlog(начиная с первого предложения раздела clauses) будет просматривать каждый факт и каждое правило, стремясь найти сопоставление. По мере продвижения вниз по разделу clauses, он устанавливает внутренний указатель на первое предложение, являющееся частью пути, ведущего к решению. Если следующее предложение не является частью этого логического пути, то VisualPrologвозвращается к установленному указателю и ищет очередное подходящее сопоставление, перемещая указатель на него (этот процесс называется поиск с возвратом).

10. Раздел предикатов

Если в разделе clausesпрограммы на VisualPrologописан собственный предикат, то его необходимо объявить в разделе predicates(предикатов). В результате объявления предиката сообщается, к каким доменам (типам) принадлежат аргументы этого предиката.

11. ОБЪЯВЛЕНИЕ ПОЛЬЗОВАТЕЛЬСКОГО ПРЕДИКАТА

Объявление предиката начинается с имени этого предиката, за которым идет открывающая (левая) круглая скобка, после чего следует ноль или больше доменов (типов) аргументов предиката:

predicateName (argument_typel OptionalNamel,

argument_type2 OptionalName2, …,

argument_typeN OptionalNameN)

После каждого домена (типа) аргумента следует запятая, а после последнего типа аргумента — закрывающая (правая) скобка. В отличии от предложений в разделе clauses, декларация предиката не завершается точкой. Доменами (типами) аргументов предиката могут быть либо стандартные домены, либо домены, объявленные вами в разделе domains. Можно указывать имена аргументов OptionalNameK— это улучшает читаемость программы, и не сказывается на скорости ее исполнения, т. к. компилятор их игнорирует.

Имена предикатов

Имя предиката должно начинаться с буквы, за которой может располагаться последовательность букв, цифр и символов подчеркивания. Буквы должны быть в нижнем регистре!Имя предиката может иметь длину до 250 символов.

В именах предикатов запрещается использовать пробел, символ минус, звездочку и другие алфавитно-цифровые символы.

Аргументы предикатов

Аргументы предикатов должны принадлежать доменам, известным VisualProlog. Эти домены могут быть либо стандартными, либо пользовательскими.

12. Раздел доменов

Домены позволяют задавать разные имена различным видам данных, которые, в противном случае, будут выглядеть абсолютно одинаково. В программах VisualPrologобъекты в отношениях (аргументы предикатов) принадлежат доменам, причем это могут быть как стандартные, так и описанные пользователем специальные домены. Раздел domainsслужит двум полезным целям. Во-первых, можно задать доменам осмысленные имена, даже если внутренне эти домены аналогичны уже имеющимся стандартным. Во-вторых, объявление специальных доменов используется для описания структур данных, отсутствующих в стандартных доменах.

Иногда очень полезно описать новый домен — особенно, когда вы хотите прояснить отдельные части раздела predicates. Объявление собственных доменов, благодаря присваиванию осмысленных имен типам аргументов, помогает документировать описываемые вами предикаты. Рассмотрим пример, показывающий, как объявление доменов помогает документировать предикаты:

Франк — мужчина, которому 45 лет.

Используя стандартные домены, вы можете так объявить соответствующий предикат:

person(symbol, symbol, integer).

В большинстве случаев такое объявление будет работать хорошо, но не наглядно для чтения программы. Более правильным было бы следующее описание:

domains

    продолжение
--PAGE_BREAK--

name, sex = symbol

age = integer

predicates

person(name, sex, age)

Одним из главных преимуществ объявления собственных доменов является то, что VisualPrologможет отслеживать ошибки типов, например, такие:

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) .

Visual Prolog (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не следует :-;

при запуске программы VisualPrologавтоматически выполняет цель.

Если все подцели в разделе goalистинны, — программа завершается успешно. Если же какая-то подцель из раздела goalложна, то считается, что программа завершается неуспешно (хотя чисто внешне никакой разницы в этих случаях нет, — программа просто завершит свою работу).

14. Декларации и правила

В VisualPrologесть несколько встроенных стандартных доменов. Их можно использовать при декларации типов аргументов предикатов без описания в разделе 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(и их беззнаковые аналоги) для более специализированных приложений.

    продолжение
--PAGE_BREAK--

В объявлениях доменов ключевые слова signedи unsignedмогут использоваться вместе со стандартными доменами типов byte, wordи dwordдля построения новых базовых доменов. Так:

domains

i8 = signed byte

создает новый базовый домен в диапазоне от -128 до +127.

Другие базовые домены показаны в табл. 21.

Таблица 2. Основные стандартные домены

Домен

Описание и реализация

char

Символ, реализуемый как беззнаковый byte. Синтаксически это символ, заключенный между двумя одиночными кавычками: 'а'

real

Число с плавающей запятой, реализуемое как 8 байт в соответствии с соглашением IEEE; эквивалентен типу double в С. При необходимости, целые автоматически преобразуются в real

string

Последовательность символов, реализуемых как указатель на байтовый массив, завершаемый нулем, как в С. Для строк допускается два формата:1. Последовательность букв, цифр и символов подчеркивания, причем первый символ должен быть строчной буквой.2. Последовательность символов, заключенных в двойные кавычки.

Примеры строк:

telephone_number "railway ticket" "Dorid Inc"

Строки, которые пишутся в программе, могут достигать длины в 255 символов, в то время как строки, которые система Visual Prolog считывает из файла или строит внутри себя, могут достигать (теоретически) до 4 Гбайт на 32-битных платформах

symbol

Последовательность символов, реализуемых как указатель на вход в таблице идентификаторов, хранящей строки идентификаторов. Синтаксис — как для строк

Идентификаторы и строки взаимозаменяемы в программе, однако VisualPrologхранит их раздельно. Идентификаторы хранятся в таблице идентификаторов, а для представления используются лишь их индексы в этой таблице, но не сами строки идентификаторов. Это означает, что сопоставление идентификаторов выполняется очень быстро, а в случае если они встречаются в программе несколько раз, то и хранение их компактно. Строки же не хранятся в поисковой таблице, и при необходимости сопоставления VisualPrologпроверяет их символ за символом. Вы сами должны определять, какой домен лучше использовать в каждой конкретной программе.

Задание типов аргументов при декларации предикатов

Объявление доменов аргументов в разделе 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

    продолжение
--PAGE_BREAK--

father(person)% этот person — отец

father(person, person)% первый person является отцом другого

clauses

father (Man) :-father(Man, _) .

father(adam,seth).

father(abraham,isaac).

Синтаксис правил

Правила используются в Прологе в случае, когда какой-либо факт зависит от истинности другого факта или группы фактов. Как мы объясняли ранее в этой главе, в правиле Пролога есть две части: заголовок и тело. Ниже представлен обобщенный синтаксис правила в VisualProlog:

HEAD: — <Subgoal>, <Subgoal>, ..., <Subgoal>.

Заголовок: — <Подцель>, <Подцель>,…, <Подцель>.

Тело правила состоит из одной или более подцелей. Подцели разделяются запятыми, определяя конъюнкцию, а за последней подцелью правила следует точка.

Каждая подцель выполняет вызов другого предиката Пролога, который может быть истинным или ложным. После того, как программа осуществила этот вызов, VisualPrologпроверяет истинность вызванного предиката, и если это так, то работа продолжается, но уже со следующей подцелью. Если же в процессе такой работы была достигнута точка, то все правило считается истинным; если хоть одна из подцелей ложна, то все правило ложно.

Для успешного разрешения правила Пролог должен разрешить все его подцели и создать последовательный список переменных, должным образом связав их. Если же одна из подцелей ложна, Пролог вернется назад для поиска альтернативы предыдущей подцели, а затем вновь двинется вперед, но уже с другими значениями переменных. Этот процесс называется поиск с возвратом.

Как упоминалось выше, в качестве разделителя заголовка и тела правила Пролог использует знак:-, который читается как «если» (if). Однако ifПролога отличается от if, написанного в других языках, например в Pascal, где условие, содержащееся в операторе if, должно быть указано перед телом оператора, который может быть выполнен. Другими словами:

если ЗАГОЛОВОК истинен, тогда ТЕЛО истинно (или: тогда выполнить ТЕЛО

Данный тип оператора известен как условный оператор если/тогда (if/then). Пролог же использует другую форму логики в таких правилах. Вывод об истинности заголовка правила Пролога делается, если (после того, как) тело этого правила истинно, например, так:

ЗАГОЛОВОК истинен, если ТЕЛО — истинно (или: если ТЕЛО может Сыть выполнено).

Учитывая вышесказанное, правило Пролога соответствует условной форме тогда/если (then/if).

Автоматическое преобразование типов

Совсем не обязательно, чтобы при сопоставлении двух VisualProlog-переменных они принадлежали одному и тому же домену. Переменные могут быть связаны с константами из различных доменов. Такое (избирательное) смешение допускается, т. к. VisualPrologавтоматически выполняет преобразование типов (из одного домена в другой), но только в следующих случаях:

между строками (string) и идентификаторами (symbol);

между целыми, действительными и символами (char). При преобразовании символа в числовое значение этим значением является величина символа в коде ASCII.

Аргумент из домена my_dom, который объявлен следующим образом:

domains

my_dom = <base domain> % <base domain> — этостандартныйдомен

может свободно смешиваться с аргументами из этого основного домена и с аргументами всех совместимых с ним стандартных доменов. Если основной домен — string, то с ним совместимы аргументы из домена symbol; если же основной домен integer, то с ним совместимы домены real, char, wordи др. Такое преобразование типов означает, например, что вы можете:

вызвать предикат с аргументами типа string, задавая ему аргументы типа symbol, и наоборот;

передавать предикату с аргументами типа realпараметры типа integer;

передавать предикату с аргументами типа charпараметры типа integer;

использовать в выражениях и сравнениях символы без необходимости получения их кодов в ASCII.

Существует набор правил, определяющих, к какому домену принадлежит результат смешивания разных доменов. Эти правила будут детально рассмотрены далее.

15. Другие разделы программ

Теперь, когда вы ознакомились с такими разделами программ VisualProlog, как clauses, predicates, domainsи goal, поговорим о некоторых других, часто используемых разделах программ: facts, constantsи различных глобальных (global) разделах.

Раздел фактов

Программа на VisualPrologпредставляет собой набор фактов и правил. Иногда в процессе работы программы бывает необходимо модифицировать (изменить, удалить или добавить) некоторые из фактов, с которыми она работает. В этом случае факты рассматриваются как динамическая или внутренняя база данных, которая при выполнении программы может изменяться. Для объявления фактов программы, рассматривающихся как части динамической (или изменяющейся) базы данных, VisualPrologвключает специальный раздел — facts.

Ключевое слово factsобъявляет раздел фактов. Именно в этой секции вы объявляете факты, включаемые в динамическую базу данных. Отметим, что в ранних версиях VisualPrologдля объявления раздела фактов использовалось ключевое слово database, т. е. ключевое слово facts— синоним устаревшего ключевого слова database. В VisualPrologесть несколько встроенных предикатов, облегчающих использование динамических фактов.

Раздел констант

В своих программах на VisualPrologвы можете объявлять и использовать символические константы. Раздел для объявления констант обозначается ключевым словом constants, за которым следуют сами объявления, использующие следующий синтаксис:

    продолжение
--PAGE_BREAK--

<id> = <Макроопределение>

<id>— имя символической константы, а <макроопределение> — это то, что вы присваиваете этой константе. Каждое <макроопределение> завершается символом новой строки и, следовательно, на одной строке может быть только одно описание константы. Объявленные таким образом константы могут позже использоваться в программах.

Рассмотрим следующий фрагмент программы:

constants

zеrо= О

one = 1

two = 2

hundred = (10*(10-1)+10)

pi = 3.141592653

ega= 3

slash_fill = 4

red = 4

Перед компиляцией программы VisualPrologзаменит каждую константу на соответствующую ей строку.

На использование символических констант накладываются следующие ограничения:

описание константы не может ссылаться само на себя:

my_number = 2*my_number/2 % недопускается

это приведет к сообщению об ошибке "Recursioninconstantdefinition" (Рекурсия в описании константы);

в описаниях констант система не различает верхний и нижний регистры. Следовательно, при использовании в разделе программы clausesидентификатора типа constants, его первая буква должна быть строчной для того, чтобы избежать путаницы между константами и переменными.

в программе может быть несколько разделов constants, однако объявление константы должно производиться перед ее использованием;

идентификаторы констант являются глобальными и могут объявляться только один раз. Множественное объявление одного и того же идентификатора приведи к сообщению об ошибке "Constantidentifiercanonlybedeclaredonce" (Идентификатор константы может объявляться только один раз).

Директивы компилятора

VisualPrologподдерживает несколько директив компилятора, которые можно добавлять в программу для сообщения компилятору специальных инструкций по обработке вашей программы при ее компиляции. Кроме этого, вы можете устанавливать большинство директив компилятора с помощью команды меню среды визуальной разработки VisualPrologOptions/Project/CompilerOptions.

Директива include

Для того чтобы избежать многократного набора повторяющихся процедур, вы можете использовать директиву include.

Ниже приведен пример того, как это делается.

Создаете файл (например, MYSTUFF.PRO), в котором объявляете свои наиболее Iчасто используемые предикаты (с помощью разделов domainsи predicates) и даете их описание в разделе clauses.

Пишете исходный текст программы, которая будет использовать эти процедуры.

В «допустимых областях» исходного текста программы размещаете строку:include "mystuff.pro"

«Допустимые области» — это любое место программы, в котором вы можете расположить декларацию разделов domains, facts, predicates, clausesили goal.

При компиляции исходных текстов программы VisualPrologвставит содержание файла 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, «DR NO»).

written_by(melville, «MOBY DICK»).

book(«MOBY DICK», 250).

book(«DR NO», 310).

long_novel (Title) :-

written_by(_, Title),

book(Title, Length),

Length > 300.

Листинг программы ch04e01.pro

Пытаясь выполнить целевое утверждение written_by(X, Y), VisualPrologдолжен проверить каждое предложение written_by(X, Y)в программе. Сопоставляя аргументы Xи Yс аргументами каждого предложения written_by, VisualPrologвыполняет поиск от начала программы до ее конца. Обнаружив предложение, соответствующее целевому утверждению, VisualPrologприсваивает значения свободным переменным таким образом, что целевое утверждение и предложение становятся идентичными. Говорят, что целевое утверждение унифицируется с предложением. Такая операция сопоставления называется унификацией.

    продолжение
--PAGE_BREAK--

Поскольку Xи Yявляются свободными переменными в целевом утверждении, а свободная переменная может быть унифицирована с любым другим аргументом (и даже с другой свободной переменной), то целевое утверждение может быть унифицировано с первым предложением written_byв программе, как показано ниже:

written_by (X,Y).

¯¯

written_by(fleming,«DR NO»).

VisualPrologустанавливает соответствие, Xстановится связанным с fleming, aY– “drno”. В этот момент VisualPrologнапечатает:

X=fleming, Y=«DR NO»

Поскольку TestGoalищет все решения для заданной цели, целевое утверждение также будет унифицировано и со вторым предложением written_by:

written_by(melville, «MOBY DICK»).

TestGoalпечатает второе решение:

X=melville, Y=«MOBY DICK»

2 Solutions

Рассмотрим, как VisualPrologвыполнит следующее целевое утверждение:

long_novel(X).

Когда VisualPrologпытается выполнить целевое утверждение, он проверяет, действительно ли обращение может соответствовать факту или заголовку правила. В нашем случае устанавливается соответствие с

long_novel(Title)

VisualPrologпроверяет предложение для long_novel, пытаясь завершить сопоставление унификацией аргументов. Поскольку в целевом утверждении X— свободная переменная, то она может быть унифицирована с любым другим аргументом. Titleтакже не является связанным в заголовке предложения long_novel. Целевое утверждение соответствует заголовку правила, и унификация выполняется. Впоследствии VisualPrologбудет пытаться согласовывать подцели с правилом

long_novel(Title) :-

written_by(_, Title), book(Title, Length), Length>300.

Пытаясь выполнить согласование тела правила, VisualPrologобратится к первой подцели в теле правила — written_by(_, Title). Поскольку авторство книги является несущественным, на месте аргумента authorпоявляется анонимная переменная (_). Обращение written_by(_, Title) становится текущей подцелью, и Пролог ищет решение для этого обращения.

Пролог ищет соответствие с данной подцелью от вершины и до конца программы. В результате достигается унификация с первым фактом для written_by, а именно:

written_by(_, Title),

¯¯

written_by (fleming, «DR NO»).

Переменная Titleсвязывается с "drno", и к следующей подцели book(Title, Length) обращение выполняется уже с этим значением переменной. Далее VisualPrologначинает очередной процесс поиска, пытаясь найти соответствие с обращением к book. Так как Titleсвязан с "drno", фактическое обращение выглядит как book("DRNO", Length). Процесс поиска опять начинается с вершины программы. Заметим, что первая попытка сопоставления с предложением book(“MOBYDICK", 250) завершится неудачно, и VisualPrologперейдет ко второму предложению bookв поиске соответствия. Здесь заголовок книги соответствует подцели, и VisualPrologсвязывает переменную Lengthс величиной 310.

Теперь третье предложение в теле long_novelстановится текущей подцелью:

length > 300.

VisualPrologвыполняет сравнение, завершающееся успешно: 310 больше, чем 300. В этот момент все подцели в теле правила выполнены, и, следовательно, обращение long_novel(X) успешно. Так как Xв обращении был унифицирован с переменной Titleв правиле, то значение, с которым связывается Titleпри подтверждении правила, возвращается и унифицируется с переменной X. Переменная Titleв случае подтверждения правила имеет значение "drno", поэтому VisualPrologвыведет:

X=«DR NO»

1 Solution.

2. Поиск с возвратом

Часто при решении реальной задачи мы придерживаемся определенного пути для ее логического завершения. Если полученный результат не дает искомого ответа, мы должны выбрать другой путь.

Так, вам, возможно, приходилось играть в лабиринт. Один из верных способов найти конец лабиринта — это поворачивать налево на каждой развилке лабиринта до тех пор, пока вы не попадете в тупик. Тогда следует вернуться к последней развилке и попробовать свернуть вправо, после чего опять поворачивать налево на каждом встречающемся распутье. Путем методичного перебора всех возможных путей вы, в конце концов, найдете выход.

    продолжение
--PAGE_BREAK--

VisualPrologпри поиске решения задачи использует именно такой метод проб и возвращений назад; этот метод называется поиск с возвратом. Если, начиная поиск решения задачи (или целевого утверждения), VisualPrologдолжен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится, VisualPrologвернется к точке отката и попробует проверить другую подцель.

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).

Программа ch04e02.pro

Эта маленькая программа составлена из двух множеств фактов и одного правила. Правило, представленное отношением likes, утверждает, что Билл любит вкусную пищу.

Чтобы увидеть, как работает поиск с возвратом, дадим программе для решения следующее целевое утверждение:

likes(bill, What).

Когда Пролог пытается произвести согласование целевого утверждения, он начинает поиск с вершины программы.

В данном случае Пролог будет искать решение, производя с вершины программы поиск соответствия с подцелью likes (bill, what).

Он обнаруживает соответствие с первым предложением в программе и переменная Whatунифицируется с переменной X. Сопоставление с заголовком правила заставляет VisualPrologпопытаться удовлетворить это правило. Производя это, он двигается по телу правила и обращается к первой находящейся здесь подцели: food(X).

Если выполняется новое обращение, поиск соответствия для этого обращения вновь начинается с вершины программы.

Пытаясь согласовать первую подцель, VisualProlog(начиная с вершины) производит сопоставление с каждым фактом или заголовком правила, встреченным в программе.

Он обнаруживает соответствие с запросом у первого же факта, представляющего отношение food. Таким образом, переменная Xсвязывается со значением brussels_sprouts. Поскольку существует более чем один возможный ответ на обращение food(X), VisualPrologставит точку возврата (маркер) возле факта 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и VisualPrologсообщает решение:

What=pizza

1 Solution

3. Управление поиском решений

Встроенный механизм поиска с возвратом в Прологе может привести к поиску ненужных решений, в результате чего теряется эффективность, например, когда желательно найти только одно решение. В других случаях может оказаться необходимым продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано.

VisualPrologобеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикат fail, который используется для инициализации поиска с возвратом, и cutили отсечение (обозначается !) — для запрета возможности возврата.

    продолжение
--PAGE_BREAK--

Использование предиката fail

VisualPrologначинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. VisualPrologподдерживает специальный предикат 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.

Программа ch04e06.pro

Пусть необходимо найти все решения цели father(X,Y). Используя утилиту TestGoal, можно записать цель как

goal

father(X,Y).

TestGoalнайдет все решения цели father(X,Y) и отобразит значения всех переменных следующим образом:

X=leonard, Y=katherine

X=carl, Y=jason

X=carl, Y=marilyn

3 Solutions

Но если вы скомпилируете эту программу и запустите ее, то VisualPrologнайдет только первое подходящее решение для father(X,Y). После того как целевое утверждение, определенное в разделе goal, выполнено впервые, ничто не говорит Прологу о необходимости продолжения поиска с возвратом. Поэтому обращение к fatherприведет только к одному решению. Как же найти все возможные решения? Предикат everybodyв программе ch04e06.proиспользует failдля поддержки поиска с возвратом.

Задача предиката everybody— найти все решения для fatherи выдать полный ответ. Сравните предыдущие ответы утилиты TestGoalс целью father(X,Y) и ответы на выполнение следующей цели:

goal

everybody.

отображенные сгенерированной программой:

leonard is katherine' s father

carl is Jason's father

carl is marilyn's father

Предикат everybodyиспользует поиск с возвратом с тем, чтобы получить все решения для father(X, Y), заставляя Пролог выполнять поиск с возвратом сквозь тело правила everybody:

father (X, Y),

mite(X," is ",Y, "'s father\n"),

fail.

failне может быть согласован (он всегда неуспешен), поэтому VisualPrologвынужден повторять поиск с возвратом. При поиске с возвратом он возвращается к последнему обращению, которое может произвести множественные решения. Такое обращение называют недетерминированным. Недетерминированное обращение является противоположностью детерминированному обращению, которое может произвести только одно решение.

Предикат writeне может быть вновь согласован (он не может предложить новых решений), поэтому VisualPrologдолжен выполнить откат дальше, на этот раз к первой подцели в правиле.

Обратите внимание, что помещать подцель после failв теле правила бесполезно. Предикат failвсе время завершается неудачно, нет возможности для достижения подцели, расположенной после fail.

Прерывание поиска с возвратом: отсечение

VisualPrologпредусматривает возможность отсечения, которая используется для прерывания поиска с возвратом; отсечение обозначается восклицательным знаком (!). Действует отсечение просто: через него невозможно совершить откат (поиск с возвратом).

Отсечение помещается в программу таким же образом, как и подцель в теле правила. Когда процесс проходит через отсечение, немедленно удовлетворяется обращение к cutи выполняется обращение к очередной подцели (если таковая имеется). Однажды пройдя через отсечение, уже невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением, и также невозможно возвратиться к другим предложениям, определяющим обрабатывающий предикат (предикат, содержащий отсечение).

Существуют два основных случая применения отсечения.

Если вы заранее знаете, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), — примените отсечение, — программа станет быстрее и экономичнее. Такой прием называют зеленым отсечением.

Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это — красное отсечение.

В этом вопросе даются примеры, показывающие, как следует использовать отсечение, рассматриваются несколько условных правил (rl, r2 и rЗ), которые определяют условный предикат г, а также несколько подцелей — а, b, с и т. д.

    продолжение
--PAGE_BREAK--

Предотвращение поиска с возвратом к предыдущей подцели в правиле

r1 :- а,b,

!,

c.

Такая запись является способом сообщить VisualPrologо том, что вас удовлетворит первое решение, найденное им для подцелей а и 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 < 25000.

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. Программа ch04e07.pro

В данном примере поставлена цель: найти corvette(Корвет) приятного цвета, подходящий по стоимости. Отсечение в правиле buy_carозначает, что поскольку в базе данных содержится только один «Корвет» приятного цвета, хоть и со слишком высокой ценой, то нет нужды искать другую машину. Получив целевое утверждение

buy_car(corvette, Y)

программа отработает следующие шаги:

1. VisualPrologобращается к саг, первой подцели для предиката buy_car.

2. Выполняет проверку для первой машины, maserati, которая завершается неудачно.

3. Затем проверяет следующее предложение саг и находит соответствие, связывая переменную Colorсо значением black.

4. Переходит к следующему обращению и проверяет, имеет ли выбранная машина приятный цвет. Черный цвет не является приятным в данной программе, таким образом, проверка завершается неудачно.

5. Выполняет поиск с возвратом к обращению саг и снова ищет corvette, удовлетворяющий этому критерию.

6. Находит соответствие и снова проверяет цвет. На этот раз цвет оказывается приятным, и VisualPrologпереходит к следующей подцели в правиле: к отсечению. Отсечение немедленно выполняется, «замораживая» все переменные, ранее связанные в этом предложении.

7. Переходит к следующей (и последней) подцели в правиле, к сравнению

Price < 25000.

8. Проверка завершается неудачно, и VisualPrologпытается совершить поиск с возвратом с целью найти другую машину для проверки. Отсечение предотвращает попытку решить последнюю подцель, и наше целевое утверждение завершается неудачно.

Предотвращение поиска с возвратом к следующему предложению

Отсечение может быть использовано, как способ сообщить VisualProlog, что он выбрал верное предложение для определенного предиката. Например, рассмотрим следующий фрагмент:

r(1) :-

!,

а, b, с.

r(2):-

!,

d.

r(3):-

!,

с.

r(_) :-

write(«This is a catchall clause.»).

Использование отсечения делает предикат rдетерминированным. В данном случае VisualPrologвыполняет обращение к rс единственным целым аргументом. Предположим, что произведено обращение r(l). VisualPrologпросматривает программу в поисках соответствия для обращения; он находит его с первым предложением, определяющим r. Поскольку имеется более чем одно возможное решение для данного обращения, VisualPrologпроставляет точку возврата около этого предложения.

Теперь VisualPrologначинает обработку тела правила, проходит через отсечение и исключает возможность возвращения к другому предложению r. Это отменяет точки поиска с возвратом, повышая эффективность выполнения программы, а также гарантирует, что отлавливающее ошибки предложение будет выполнено лишь в том случае, если ни одно из условий не будет соответствовать обращению к r.

Обратите внимание, что конструкция такого типа весьма похожа на конструкцию caseв других языках программирования; условие проверки записывается в заголовке правил. По возможности, всегда следует помещать проверочное условие именно в заголовок правила, — это повышает эффективность программы и упрощает ее чтение.

Детерминизм и отсечение

Если бы предикат r, определенный в предыдущей программе, не содержал отсечений, то это был бы недетерминированныйпредикат (способный производить множественные решения при помощи поиска с возвратом). В предыдущих реализациях Пролога программисты должны были обращать особое внимание на недетерминированные предложения из-за сопутствующих им дополнительных требований к ресурсам памяти. Теперь VisualPrologсам выполняет проверку на недетерминированные предложения, облегчая вашу работу.

    продолжение
--PAGE_BREAK--

В Прологе существует директива компилятора check_determ. Если вставить эту директиву в самое начало программы, то VisualPrologбудет выдавать предупреждение в случае обнаружения недетерминированных предложений в процессе компиляции.

Можно превратить недетерминированные предложения в детерминированные, вставляя отсечения в тело правил, определяющих данный предикат.

Предикат 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) .

Программа ch04e10.pro

При использовании предиката notнеобходимо иметь в виду следующее:

Предикат not будет успешным, если не может быть доказана истинность данной подцели.

Это приводит к предотвращению связывания внутри notнесвязанных переменных. При вызове изнутри notподцели со свободными переменными, VisualPrologвозвратит сообщение об ошибке: "Freevariablesnotallowedinnotorretractall" (Свободные переменные не разрешены в notили retract). Это происходит вследствие того, что для связывания свободных переменных в подцели, подцель должна унифицироваться с каким-либо другим предложением и выполняться. Правильным способом управления несвязанными переменными подцели внутри notявляется использование анонимных переменных.

Первый пример работает правильно:

likes (bill, Anyone) :-% Anyone — выходной аргумент

likes(sue, Anyone),

not(hates(bill, Anyone).

В этом примере Anyoneсвязывается посредством likes(sue, Anyone) до того, как VisualPrologделает вывод, что hates(bill, Anyone) не является истиной. Данное предложение работает корректно.

Если пример изменить таким образом, что обращение к notбудет выполняться первым, то получите сообщение об ошибке: "Freevariablearenotallowedinnot" (Свободные переменные в 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 приведет к сообщению об ошибке или к ошибкам в логике вашей программы.Простые и составные объекты

До сих пор мы работали только основными видами объектов данных VisualProlog, таких как числа, идентификаторы и строки. VisualPrologможет создавать не только простые, но и составные типы.

5. Простые объекты данных

Простой объект данных — это переменная или константа. Не путайте это значение слова «константа» с символьными константами, которые вы определяете в разделе constantsпрограммы. То, что мы здесь называем константой, это нечто, идентифицирующее объект, который нельзя изменять: символ (char), число (integerили real) или атом (symbolили string).

Константы включают числа, символы и атомы. Числа и символы были рассмотрены ранее.

Атомы имеют тип идентификатор (symbol) или строка (string). Отличие между ними — главным образом вопрос машинного представления и реализации, и, в основном, оно синтаксически не заметно. Когда атом передается в качестве аргумента при вызове предиката, то к какому домену принадлежит атом — symbolили string-определяется по тому, как описан этот аргумент в декларации предиката.

    продолжение
--PAGE_BREAK--

VisualPrologавтоматически преобразует типы между доменами stringи symbol, поэтому вы можете использовать атомы symbolв доменах stringи наоборот. Однако принято считать, что объект в двойных кавычках принадлежит домену string, а объект, не нуждающийся в кавычках, домену symbol. Атомы типа symbol— это имена, начинающиеся со строчной буквы и содержащие только буквы, цифры и знак подчеркивания.

Атомы типа stringвыделяются двойными кавычками и могут содержать любую комбинацию литер, кроме ASCII-нуля (0, бинарный нуль), который обозначает конец строки атома.

Примеры строк и идентификаторов приведены в табл. 1.

Строки и идентификаторы

Атомы-идентификаторы

Атомы-строки

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, как древовидную структуру.

/>

Древовидная структура даты

Можно объявить домен, содержащий составной объект date:

domains

date_cmp = date(string,unsigned,unsigned)

а затем просто записать:

D = date(«0ctober»,15,1991) .

Такая запись выглядит как факт Пролога, но это не так — это объект данных, который вы можете обрабатывать наряду с символами и числами. Он начинается с имени, называемого функтором (в данном случае date), за которым следуют три аргумента.

Функтор в VisualProlog— не то же самое, что функция в других языках программирования; это просто имя, которое определяет вид составного объекта данных и объединяет вместе его аргументы. Функтор не обозначает, что будут выполнены какие-либо вычисления.

Аргументы составного объекта данных могут сами быть составными объектами. Например, вы можете рассматривать чей-нибудь день рождения (рис. 2), как информацию со следующей структурой:

/>

Рис. 2. древовидная структура даты рождения.

На языке Пролог это выглядит следующим образом:

birthday(person(«Leo»,«Jensen»),date(«Apr»,14,1960))

Унификация составных объектов

Составной объект может быть унифицирован с простой переменной или с составным объектом (возможно, содержащим переменные в качестве частей во внутренней структуре), который ему соответствует. Это означает, что составной объект можно использовать для того, чтобы передавать целый набор значений как единый объект, и затем применять унификацию для их разделения. Например:

date(«April»,14,I960)

сопоставляется с Xи присваивает Xзначение date("April", 14,1960). Также

date(«April»,14,I960)

сопоставляется с date(Mo, Da, Yr) и присваивает переменным Мо = "April", Da=14 и Yr= 1960.

Использование нескольких значений как единого целого

Составные объекты могут рассматриваться в предложениях Пролога как единые объекты, что сильно упрощает написание программ. Рассмотрим, например, факт:

owns(john, book(“From Here to Eternity", «James Jones»)).

в котором утверждается, что у Джона есть книга "FromHeretoEternity" (Отсюда в вечность), написанная JamesJones(Джеймсом Джонсом). Аналогично можно записать:

owns (john, horse (blacky) ) .

что означает:

John owns a horse named blacky.(У Джона есть лошадь Блеки.)

Если вместо этого описать только два факта:

owns (john, «From Here to Eternity»), owns(john, blacky).

то нельзя было бы определить, является ли blackyназванием книги или именем лошади.

Объявление составных доменов

Рассмотрим, как определяются составные домены. После компиляции программы, которая содержит следующие отношения:

owns(john, book(«From Here to Eternity», «James Jones»)).

и

owns (John, horse (blacky) ).

вы можете послать системе запрос в следующем виде:

    продолжение
--PAGE_BREAK--

owns (John, X)

Переменная Х может быть связана с различными типами объектов: книга, лошадь и, возможно, другими объектами, которые вы определите. Отметим, что теперь вы не можете более использовать старое определение предиката owns:

owns (symbol, symbol)

Второй элемент более не является объектом типа symbol. Вместо этого вы можете дать новое определение этого предиката

owns(name, articles)

Доменarticles вразделеdomains можноописатьтак

domains

articles = book(title, author); horse(name)

Точка с запятой читается как «или» В этом случае возможны два варианта книга будет определяться своим заглавием и автором, а лошадь будет распознаваться своим именем Домены title, authorи nameимеют стандартный тип symbol.

К определению домена легко могут быть добавлены другие варианты.

Многоуровневые составные объекты

VisualPrologпозволяет конструировать составные объекты на нескольких уровнях. Например:

domains

articles = book(title, author);%Первый уровень

author= author(first_name, last_name) %Второй уровень

title, first_name, last_name = symbol%Третий уровень

При использовании составных объектов со многими уровнями часто помогает такое «дерево» (рис. 7):

/>

Дерево многоуровневого составного объекта

Повтор и рекурсия

Компьютеры способны повторять одно и то же действие снова и снова, VisualPrologможет выражать повторение как в процедурах, так и в структурах данных. Идея повторяющихся структур данных может показаться странной, но Пролог позволяет создавать структуры данных, размер которых не известен во время создания.

Процесс повторения

Программисты на языках Pascal, Basic или С, которые начинают использовать Visual Prolog, часто испытывают разочарование, обнаружив, что язык не имеет конструкций for, while или repeat. В Прологе не существует прямого способа выражения повтора. Пролог обеспечивает только два вида повторения

откат, с помощью которого осуществляется поиск многих решений в одном запросе,

и рекурсию, в которой процедура вызывает сама себя.

Однако этот недостаток не снижает мощи Пролога. Фактически, VisualPrologраспознает специальный случай рекурсии — хвостовую рекурсию — и компилирует ее в оптимизированную итерационную петлю. Это означает, что хотя программная логика и выражается рекурсивно, скомпилированный код так же эффективен, как если бы программа была написана на 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.

Программа ch06e01.pro

Предварительные и последующие операции

Отметим, что программа, которая находит решения для целевого утверждения, может выполнять какие-либо предварительные или завершающие операции. Например, в нашем примере программа могла бы:

Напечатать

Some delightful places to live are… (Некоторые восхитительные места для проживания...).

Напечатать все решения для country(X).

Завершить печать фразой Andmaybeothers(Могут быть и другие).

Заметьте, что print_countries, определенное в предыдущем примере, уже содержит предложение вывести на печать все решения country(X) и отпечатать завершающее сообщение.

Первое предложение для print_countriesсоответствует шагу 2 и выводит на печать все решения. Его второе предложение соответствует шагу 3 и просто успешно завершает целевое утверждение (потому что первое предложение всегда в режиме fail— «неудачное завершение»).

Можно было бы изменить второе предложение в программе ch06e01.pro.

print_countnes :-

write(«And maybe others.»), nl.

    продолжение
--PAGE_BREAK--

которое выполнило бы шаг 3, как указано.

А что можно сказать о шаге 1? В нем нет смысла, когда print_countnesсодержал только 2 предложения. Но в предикате может быть и три предложения:

print_countries :-

write(«Some delightful places to live are»), nl,

fail.

pnnt_countnes :-

country(X),

write(X),nl,

fail.

print_countries :-

write(«And maybe 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.

Листинг 13.2. Программа ch06e02.pro

Программа ch06e02 pro показывает, как работает repeat Правило typewriter — описывает процесс приема символов с клавиатуры и отображения их на экране, пока пользователь не нажмет клавишу <Enter> (<Return>)

Правило typewriter работает следующим образом

1 Выполняет repeat (который ничего не делает, но ставит точку отката).

2 Присваивает переменной с значение символа.

3 Отображает С.

4 Проверяет, соответствует ли с коду возврата каретки.

5 Если соответствует, то — завершение. Если нет — возвращается к точке отката и ищет альтернативы, так как ни write, ни readchar не являются альтернативами,

Рекурсивные процедуры

Понятие рекурсии

Одним из способов организации повторений — рекурсия. Рекурсивная процедура — это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката.

Логика рекурсии проста для осуществления. Представьте себе ЭВМ, способную «понять»:

Найти факториал числа N:

Если N равно 1, то факториал равен 1

Иначе найти факториал N-1 и умножить его на N.

Этот подход означает следующее:

первое («закручиваете» стек), чтобы найти факториал 3, вы должны найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факториал 1. факториал 1 ищется без обращения к другим факториалам, т.к. он равен 1, поэтому повторения не начнутся.

второе («раскручиваете» стек), если у вас есть факториал 1, то умножаете его на 2, чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получить факториал 3.

Информация хранится в области памяти, называемой стековым фреймом (stackframe) или просто стеком (stack), который создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стековым фреймом память освобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя.

Преимущества рекурсии

Рекурсия имеет три основных преимущества:

она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;

она логически проще метода итерации;

она широко используется в обработке списков.

Рекурсия — хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, поиск в дереве (дерево состоит из более мелких деревьев) и рекурсивная сортировка (для сортировки списка, он разделяется на части, часть сортируются и затем объединяются вместе).

Логически рекурсивным алгоритмам присуща структура индуктивного математического доказательства. Приведенная выше рекурсивная программа вычисления факториала описывает бесконечное множество различных вычислений с помощью всего лишь двух предложений. Это позволяет легко увидеть правильность этих предложений. Кроме того, правильность каждого предложения может быть изучена независимо от другого.

Пример рекурсивного определения правил

Давайте добавим к программе о родственных связях еще одно отношение — предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет

/>

определять непосредственных (ближайших) предков, а второе — отдаленных. Будем говорить, что некоторый Xявляется отдаленным предком некоторого Z, если между Xи Zсуществует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1… В нашем примере на рис. 1. Том — ближайший предок Лиз и отдаленный предок Пат.

    продолжение
--PAGE_BREAK--

/>

Пример отношения предок:(а) 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).

Пары предок-потомок, разделенных разным числом поколений.

Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения.

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

/>
Рекурсивная формулировка отношения предок.

Ключевым моментом в данной формулировке было использование самого отношения предок в его определении. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны. Рекурсия — один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.

Оптимизация хвостовой рекурсии

У рекурсии есть один большой недостаток — она «съедает» память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно (состояния выполнения решения сохраняются в стековом фрейме). Максимальный размер стека у 16-битных платформ, таких как IBM PC, работающая под DOS, составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековых фреймов. На 32-битных платформах стек теоретически может возрасти до нескольких гигабайт; но здесь проявятся другие системные ограничения, прежде чем стек переполнится. Что же можно сделать, чтобы избежать использования столь большого стекового пространства?

Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии. Что, если вызывающая процедура не собирается возобновлять свое выполнение после завершения вызванной процедуры?

Предположим, что процедура вызывается последний раз, т. е. когда вызванная процедура завершит работу, вызывающая процедура не возобновит свое выполнение. Это значит, что вызывающей процедуре не нужно сохранять свое состояние, потому что эта информация уже не понадобится. Как только вызванная процедура завершится, работа процессора должна идти в направлении, указанном для вызывающей процедуры после ее выполнения.

Например, допустим, что процедура А вызывает процедуру В, а В — С в качестве своего последнего шага. Когда В вызывает С, В не должна больше ничего делать. Поэтому, вместо того чтобы сохранить в стеке процедуры В информацию о текущем состоянии С, мы можем переписать старую сохраненную информацию о состоянии В (которая больше не нужна) на текущую информацию о С, сделав соответствующие изменения в хранимой информации. Когда С закончит выполнение, она будет считать, что она вызвана непосредственно процедурой А.

Предположим, что на последнем шаге выполнения процедура В вместо процедуры С вызывает себя. Получается, что когда В вызывает В, стек (состояние) для вызывающей в должен быть заменен стеком для вызванной В. Это очень простая операция, просто аргументам присваиваются новые значения и затем выполнение процесса возвращается на начало процедуры В. Поэтому, с процедурной точки зрения, происходящее очень похоже на всего лишь обновление управляющих переменных в цикле

Эта операция называется оптимизацией хвостовой рекурсии (tailrecursionoptimization) или оптимизацией последнего вызова (last-calloptimization) Обратите внимание, что по техническим причинам оптимизация последнего вызова неприменима к рекурсивным функциям.

Как задать хвостовую рекурсию

Что означает фраза «одна процедура вызывает другую, выполняя свои самый последний шаг»? На языке Пролог это значит.

П вызов является самой последней подцелью предложения,

О ранее в предложении не было точек возврата

Ниже приводится удовлетворяющий обоим условиям пример

count (N) : -write(N), nl, NewN = N+l, count(NewN) .

Эта процедура является хвостовой рекурсией, которая вызывает себя без резервирования нового стекового фрейма, и поэтому не истощает запас памяти Как показывает программа ch06e04 pro(листинг 13 4), если вы дадите ей целевое утверждение

    продолжение
--PAGE_BREAK--

count(0) .

то предикат countбудет печатать целые числа, начиная с 0, и никогда не остановится В конечном счете произойдет целочисленное переполнение, но остановки из-за истощения памяти не произойдет

Листинг 13.4. Программа ch06e04.pro

/* Программа с хвостовой рекурсией, которая не истощает память */ predicatescount(ulong)

clauses

count(N):-

write('\r',N), NewN = N+l, count(NewN).

GOALnl, count(0).

Определение списка

В Прологе список — это объект, который содержит конечное число других объектов. Списки можно грубо сравнить с массивами в других языках, но, в отличие от массивов, для списков нет необходимости заранее объявлять их размер.

Список, содержащий числа 1, 2 и 3, записывается так:

[1, 2, 3]

Каждая составляющая списка называется элементом. Чтобы оформить списочную структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные скобки. Вотнесколькопримеров:

[dog, cat, canary]

[«valerie ann», «jennifer caitlin», «benjamin thomas»]

Объявление списков

Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:

domains

integerlist = integer*

Символ (*) означает «список чего-либо»; таким образом, integer* означает «список целых».

Элементы списка могут быть любыми, включая другие списки. Однако все его элементы должны принадлежать одному домену. Декларация домена для элементов должна быть следующего вида:

domains

elementlist = elements*

elements = ....

Здесь elementsимеют единый тип (например: integer, realили symbol) или являются набором отличных друг от друга элементов, отмеченных разными функторами. В VisualPrologнельзя смешивать стандартные типы в списке. Например, следующая декларация неправильно определяет список, составленный из элементов, являющихся целыми и действительными числами или идентификаторами:

elementlist = elements*

elements = integer; real; symbol/* Неверно */

Чтобы объявить список, составленный из целых, действительных и идентификаторов, надо определить один тип, включающий все три типа с функторами, которые покажут, к какому типу относится тот или иной элемент. Например:

elementlist = elements*

elements = i(integer); r(real); s(symbol)% функторы здесь i,r и s

Головы и хвосты

Список является рекурсивным составным объектом. Он состоит из двух частей — головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка — всегда список, голова списка — всегда элемент. Например:

голова [а, b, с] есть а

хвост [а, b, с] есть [b, с]

Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:

голова [с] есть с

хвост [с] есть []

Если выбирать первый элемент списка достаточное количество раз, вы обязательно дойдете до пустого списка []. Пустой список нельзя разделить на голову и хвост.

В концептуальном плане это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.

/>

Рис. 1. Структура дерева

Одноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле — это составная структура данных.

Работа со списками

В Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например:

[а, 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% неудача

    продолжение
--PAGE_BREAK--

Использование списков

Список является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка — это просмотр и обработка каждого его элемента, пока не будет достигнут конец.

Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе — что делать с пустым списком.

Печать списков

Если нужно напечатать элементы списка, это делается так, как показано в листинге 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, описанные на обычном языке:

Печатать пустой список — значит ничего не делать.

Иначе, печатать список — означает печатать его голову (которая является одним элементом), затем печатать его хвост (список) .

Подсчет элементов списка

Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:

Длина [] — 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 вызывает сама себя рекурсивно.