Составные Домены и Списки
В этом руководстве мы представим составные домены (иногда называемые алгебраическими структурами данных). Составные домены используются для обработки наборов данных как единого целого. Списки являются примером составных доменов. Они используются настолько часто, что получили даже специальную синтаксическую окраску.
Составные домены и списки создаются с использованием встроенных (built-in) и других составных или списковых доменов. Справочная система Visual Prolog (Help) объясняет встроенные домены:
- integer - целые
- real - вещественные
- string - строковые
- symbol -символьные
- char - знаковые
- sring8 - строковые 8-разрядные
- pointer - указатели
- binary - двоичные (бинарные)
- boolean - булевские
- object - объекты
Составные домены и Функторы
Составные домены позволяют рассматривать наборы данных как единое целое и при этом мы можете рассматривать их и раздельно. Рассмотрим, например, дату "October 15, 2003". Она состоит из трех единиц информации – месяца, дня и года – но было бы полезно рассматривать дату как единое целое в виде древовидной структуры:
DATE /|\ / | \ / | \ / | \ October 15 2003
Это можно сделать путем объявления домена date_cmp, содержащего данные date:
domains date_cmp = date(string Month, unsigned Day, unsigned Year).
и затем писать просто, то есть
D = date("October", 15, 2003),
Это выглядит как факт Пролога, но это не так – это всего лишь значение, которое можно обрабатывать почти также, как строки или числа. Такая структура начинается с имени, обычно называемым функтор (functor) (в данном случае - date), за которым следуют три аргумента.
Обращаем Ваше внимание на то, что функтор в Visual Prolog не имеет ничего общего с функциями в языках программирования. Функтор не вызывает никаких вычислений, это всего лишь имя, которое идентифицирует составную величину и объединяет свои аргументы.
Аргументы составной величины могут быть, в свою очередь, составными. К примеру, Вы можете думать о чьем-либо дне рождения как о структуре данных, так, как показано:
birthday / \ / \ / \ / \ / \ person date / \ / | \ / \ / | \ "Per" "Schultze" "Apr" 14 1960
На Прологе это может быть записано как:
birthday(person("Per", "Schultze"), date("Apr",14,1960)).
В этом примере видны две подчасти составного значения birthday: аргумент person("Per", "Schultze") и аргумент date("Apr", 14, 1960). Функторами этих величин являются person и date.
Унификация Составных Доменов
Значения составных доменов могут унифицироваться либо с одиночными переменными, либо с составными значениями, которые сопоставимы с ними (здесь возможны переменные, как части внутренней структуры). Это значин, что Вы можете использовать составные величины для передачи в виде целого набора данных, а затем разбирать их по частям путем операции унификации. К примеру,
date("April", 14, 1960)
сопоставляется с переменной X и связывает переменную X с date("April",14,1960). Кроме того,
date("April", 14, 1960)
сопоставляется с date(Mo,Da,Yr) и связывает Mo с "April", Da с 14 и Yr с 1960.
Использование Знака Равенства для Унификации Составных Доменов
Visual Prolog выполняет унификацию в двух случаях. Первый - это когда вызов сопоставляется с головой клаузы. Второй - это при использовании знака равно (=), который в действительности является инфиксной формой предиката (предикат, который находится между своими аргументами, вместо того, чтобы быть перед ними).
Visual Prolog осуществляет необходимые связывания для унификации значений по обе стороны от знака равно. Это полезно для выделения значений аргументов в составных величинах. Например, следующий код проверяет имеют ли два человека одинаковы фамилии, после чего второй человек получает тот же адрес, что и первый.
class my domains person = person(name, address). name = name(string First, string Last). address = addr(street, string City, string State). street = street(integer Number, string Street_name). predicates run :(). end class implement my clauses run():- console::init(), P1 = person(name("Jim", "Smith"),addr(street(5, "1st st"), "igo", "CA")), P1 = person(name(_, "Smith"), Address), P2 = person(name("Jane", "Smith"), Address), !, stdio::write("P1 = ", P1, "\n"), stdio::write("P2 = ", P2, "\n") ; stdio::write("No solution"). end implement goal my::run.
Структура Данных Как Единое Целое
Составные данные могут рассматриваться как одиночные значения в клаузах Пролога, что значительно упрощает программирование. Рассмотрим следующий факт
owns("John", book("From Here to Eternity", "James Jones")).
в котором утверждается, что John владеет книгой "From Here to Eternity", написанной автором "James Jones". В то же время можно написать
owns("John", horse("Blacky")).
что может интерпретироваться как John владеет лошадью с именем Blacky.
Составными значениями в этих двух примерах являются
book("From Here to Eternity", "James Jones")).
и
horse("Blacky").
Если бы вместо этого было бы записаны два факта:
owns("John", "From Here to Eternity"). owns("John", "Blacky").
то нельзя было бы решить является ли Blacky названием книги или имнем лошади. С другой стороны, можно использовать первый компонент структуры – функтор, для обозначения различия между различными типами данных. В этом примере использовались, соответственно функторы book и horse для того, чтобы показать различие между данными.
Помните: Составные данные состоят из функтора и аргументов, принадлежащих функтору, как показано ниже:
functor(argument1, argument2, ..., argumentN)
Пример Использования Составных Доменов
Важным свойством составных доменов является возможность легкой передачи сгруппированных данных с помощью одного аргумента. Рассмотрим случай поддержки базы данных телефонных номеров. В эту базу данных мы хотим включать также дни рождения своих друзей и членов их семей. Ниже приведен фрагмент кода, который можно было бы написать для этого:
predicates phone_list :(string First, string Last, string Phone, string Month, intege Day, integer Year) determ. clauses phone_list("Ed", "Willis", "422-0208", "aug", 3, 1955). phone_list("Chris", "Grahm", "433-9906", "may", 12, 1962).
Анализируя данные, замечаем, что факт phone_list имеет шесть аргументов; пять из них могут разбиты на два составных домена:
person birthday / \ / | \ / \ / | \ First Name Last Name Month Day Year
Было бы более полезно представить эти факты в виде составных доменов. Отступив на шаг, видим, что персона (person) является отношением, а имя (First Name) и фамилия (Last Name) являются его аргументами. Кроме того, день рождения является также отношением с тремя аргументами: месяц (month), день (day) и год (year). Представление этих отношений средствами Пролога аналогично уже упоминавшемуся
owns("John", "From Here to Eternity"). owns("John", "Blacky").
Теперь можно переписать нашу небольшую базу данных с использованием этих составных доменов в базе данных.
domains name = person(string First, string Last). birthday = b_date(string Month, integer Day, integer Year). class predicates phone_list :(name, string Ph_num, birthday) determ. clauses phone_list(person("Ed", "Willis"), "422-0208",b_date("aug", 3, 1955)). phone_list(person("Chris", "Grahm"), "433-9906",b_date("may", 12, 1962)).
В этой программе появились объявления двух составных доменов (domains). Мы детальнее рассмотрим эти составные структыры данных позднее в этой главе. Пока же мы обратим внимание на преимущества использования таких составных доменов.
Предикат phone_list теперь содержит три аргумента вместо прежних шести. Иногда разбиение данных на составные структуры упрощает программу и облегчает обработку данных.
Теперь добавим некоторые правила в программу. Предположим, нам надо получить список людей, чьи дни рождения выпадают на текущий месяц. Ниже приведена программа, решающая эту задачу; эта программа использует стандартный предикат date для получения текущей даты из внутренних часов компьютера. Предикат date возвращает текущий год (year), месяц (month) и день (day) часов компьютера.
class my domains name = person(string First, string Last). birthday = b_date(string Month, integer Day, integer Year). predicates phone_list :(name, string Ph_num, birthday) multi(o,o,o). get_months_birthdays :(). convert_month :(string Name, integer Num) determ(i,o). check_birthday_month :(integer Month_num, birthday) determ. write_person :(name). end class implement my clauses get_months_birthdays() :- stdio::write("****** This Month's Birthday List *****\n"), stdio::write(" First Name\t\t Last Name\n"), stdio::write("***********************************\n"), CurTime = time::new(), CurTime:getDate(_, ThisMonth, _), phone_list(Person, _, Date), check_birthday_month(ThisMonth, Date), write_person(Person), fail. get_months_birthdays() :- stdio::write("\n Press any key to continue:\n"), _ = console::readChar(). clauses write_person(person(FirstName, LastName)) :- stdio::write(" ", FirstName, "\t\t ", LastName, "\n"). clauses check_birthday_month(Mon, b_date(Month, _, _)) :- convert_month(Month, Month1), Mon = Month1. clauses phone_list(person("Ed", "Willis"), "11-1111", b_date("Jan", 3, 1955)). phone_list(person("Benjamin", "Thomas"), "222-2222", b_date("Feb", 5, 1965)). phone_list(person("Ray", "William"), "333-3333", b_date("Mar", 3, 1955)). phone_list(person("Tomas", "Alfred"), "444-4444", b_date("Apr", 29, 1975)). phone_list(person("Chris", "Gralm"), "555-5555", b_date("May", 12, 1975)). phone_list(person("Dastin", "Robert"), "666-6666", b_date("Jun", 17, 1975)). phone_list(person("Anna", "Friend"), "777-7777", b_date("Jul", 2, 1975)). phone_list(person("Naomi", "Friend"), "888-8888", b_date("Aug", 10, 1975)). phone_list(person("Christina", "Lynn"), "999-9999", b_date("Sep", 25, 1975)). phone_list(person("Kathy", "Ann"), "110-1010", b_date("Oct", 20, 1975)). phone_list(person("Elizabeth", "Ann"), "110-1111", b_date("Nov", 9, 1975)). phone_list(person("Aaron", "Friend"), "110-1212", b_date("Dec", 31, 1975)). phone_list(person("Jenifer", "Faitlin"), "888-8888", b_date("Aug", 14, 1975)). clauses convert_month("Jan", 1). convert_month("Feb", 2). convert_month("Mar", 3). convert_month("Apr", 4). convert_month("May", 5). convert_month("Jun", 6). convert_month("Jul", 7). convert_month("Aug", 8). convert_month("Sep", 9). convert_month("Oct", 10). convert_month("Nov", 11). convert_month("Dec", 12). end implement goal console::init(), my::get_months_birthdays().
Каким образом составные домены помогают в этой программе? Это несложно увидеть, просмотрев код. Основная часть обработки производится в предикате get_months_birthdays.
- Сначала создается окно предикатом console::init()
- После этого пишется заголовок в окне, помогающий интерпретировать результаты.
- В предикате get_months_birthdays программа использует встроенный (built-in) предикат date, чтобы получить значение текущего месяца.
- Далее все в программе направлено на поиск в базе данных и получения списка людей, родившихся в текущем месяце. Прежде всего надо найти первого человека в базе данных. Вызов phone_list(Person, _, Date) связывает имя и фамилию человка с переменной Person путем связывания целого функтора person с этой переменной Person. Одновремиенно связывается день рождения человека с переменной Date.
Обратите внимание, что для этого требуется всего одна переменная для запоминания полного имени человека и всего одна переменная Date для запоминания дня рождения. В этом и заключается мощность составных доменов. - Теперь программа передает день рождения человека в виде одной переменной Date. Это происходит в следующей подцели, где программа передает значение текущего месяца (month), представленного целым числом, и день рождения (обрабатываемого человека) в предикат check_birthday_month.
- Посмотрите внимательно, что происходит. Visual Prolog вызывает предикат check_birthday_month с двуми параметрами: первый параметр связан с целым числом, а второй - с термом birthday. В голове правила, определяющего предикат check_birthday_month, первый аргумент сопоставляется с переменной Mon. Второй аргумент, Date, сопоставляется с b_date(Month, _,_).
Поскольку нас интересует только месяц рождения человека, то на месте как дня, так и года рождения мы используем анонимную переменную. - Предикат check_birthday_month сначала преобразует строку с названием месяца в целочисленное значение. Как только это сделано, Visual Prolog может сравнивать значение текущего месяца со значением месяца рождения человека. Если такое сравнение положительно (успешно), то цель check_birthday_month считается успешной, и обработка продолжается. Если же сравнение неуспешно (fails) - обрабатываемый человек не родился в текущем месяце, то Visual Prolog начинает операцию отката для поиска другого возможного решения задачи.
- Следующая обрабатываемая подцель - write_person. У обрабатываемого человека день рождения выпадает на текущий месяц, следовательно можно печатать его имя в отчете. После печати информации, клауза завершается предикатом неуспешности (fail), что вызывает откат.
- Откат всегда распространяется вверх до ближайшего недетерминированного вызова и пытается передоказать вызов. В нашей программе последним недетерминированным вызовом является вызов phone_list. Именно здесь программа выбирает следующего человека для обработки. Если людей в списке (в базе данных) больше нет, то текущая клауза завершается неуспешно (fails); Visual Prolog теперь пытается доказать эту цель путем просмотра быза правил ниже. Поскольку есть еще одна клауза, определяющая get_months_birthdays, Visual Prolog пытается доказать обращение к get_months_birthdays путем доказательства подцелей этой другой части клаузы.
Декларирование Составных Доменов
В этом разделе мы покажем как определяются составные домены. После компиляции программы, содержащей следующие отношения:
owns("John", book("From Here to Eternity", "James Jones")).
и
owns("John", horse("Blacky")).
можно запрашивать систему с помощью следующей цели:
owns("John", X))
Переменная X может быть связана с различными типами данных - книгой, лошадью или возможно другим типом, который будет определен. Поскольку предикат owns теперь определен, больше его нельзя использовать в смысле старого определения:
owns :(string, string).
Второй аргумент больше не относится к домену string. Вместо этого необходимо сформулировать новое определение предиката, такое как, например
owns :(name, articles).
Вы можете теперь описать домен articles в секции domains как показано здесь:
domains articles = book(string Title, string Author); horse(string Name). /* Articles - это книги или лошади */
Точка с запятой здесь читаются как or (или). В нашем случае возможны две альтернативы: либо книга может быть определена своим названием и автором, либо лошадь определяется своим именем. Домены Title, Author и Name - все являются стандартными доменами string.
Дополнительные альтернативы могут быть легко добавлены в декларацию домена. К примеру, articles мог бы включать лодку, дом, или банковский счет. Для лодки, можно было бы использовать функтор без аргументов. С другой стороны, может возникнуть желание представлять баланс счета в качестве банковской записи. Тогда объявления домена articles расширяются до:
domains articles = book(string Title, string Author); horse(string Name); boat; bankbook(real Balance).
Далее приведена полная программа, которая показывает как составной домен articles может быть использован в определениях предиката owns.
class my domains articles = book(string Title, string Author) ; horse(string Name) ; boat ; bankbook(real Balance). predicates owns :(string Name, articles) nondeterm(i,o) determ(i,i). end class implement my clauses owns("John", book("A friend of the family", "Irwin Shaw")). owns("John", horse("Blacky")). owns("John", boat). owns("John", bankbook(1000)). end implement goal console::init(), my::owns("John", Thing), stdio::write("Thing: ", Thing, "\n"), fail ; stdio::write("The end.").
Загрузим теперь эту программу в IDE и запустим ее. Visual Prolog теперь ответит:
Thing: book("A friend of the family","Irwin Shaw") Thing: horse("Blacky") Thing: boat() Thing: bankbook(1000) The end.
Объявления Доменов: Выводы
Дадим теперь общее представление способа записи объявлений составных доменов:
domain = alternative1(D, D, ...); alternative2(D, D, ...); ...
Здесь alternative1 и alternative2 являются равновозможными (но различными) функторами. Обозначение (D, D, ...) представляет список имен, которые объявлены в любом месте либо относятся к стандартным типам доменов(таким как string, integer, real и т.д.).
Примечания:
- Алтернативы разделяются точкой с запятой.
- Каждая алттернатива состоит из фуктора и, возможно, списка доменов для соответствующих аргументов.
- Если функтор не имеет аргументов, его можно записывать как alternativeN или alternativeN( ).
Многоуровневые Составные Домены
Visual Prolog позволяет организовывать многоуровневые составные домены. Например, в
book("The Ugly Duckling", "Andersen").
вместо использования фамилии автора, можно было бы использвать новую структуру, детализирующую автора глубже, включая имя и фамилию автора. Дав название новому составному домену author, теперь можно поменять описание книги на
book("The Ugly Duckling", author("Hans Christian", "Andersen")).
В старом объявлении домена
book(string Title, string Author).
второй аргумент функтора book, представляющий автора может представлять только одиночное имя, но этого теперь недостаточно. Надо теперь объявить, что автор представляется составным доменом, образованным из имени и фамилии. Это делается декларацией домена:
author = author(string First_name, string Last_name).
что приводит к следующим объявлениям:
domains articles = book(string Title, author Author); ... /* First level */ author = author(string First_name, string Last_name). /* Second level */
Используя составные домены таким образом на разных уровнях, часто бывает полезно рисовать дерево:
book / \ / \ title author / \ / \ First_name Last_name
Одна декларация домена всегда описывает только один уровень дерева, а не все дерево. В частности, домен book не может быть объявлен такой декларацией:
/* Not allowed */ book = book(string Title, author(string First_name, string Last_name)).
Объявления Составных Смешанных Доменов
Давайте обсудим три различных объявления доменов, которые можно включать в программы. Эти декларации позволяют использовать предикаты, которые
- принимают аргументы более чем одного типа
- принимают переменное число аргументов одного типа
- принимают переменное число аргументов, каждый из которых может иметь более одного типа
Аргументы множественных типов
Для того, чтобы предикат в Visual Prolog допускал использование аргументов различного типа, необходимо использовать функторные объявления. Следующий пример, клауза your_age clause будет воспринимать аргументы типа age, которые могут иметь тип string, real или integer.
domains age = i(integer); r(real); s(string). class predicates your_age :(age). clauses your_age(i(Age)) :- stdio::write(Age). your_age(r(Age)) :- stdio::write(Age). your_age(s(Age)) :- stdio::write(Age).
При этом Visual Prolog не допускает декларации вида:
/* Не допустимо. */ domains age = integer; real; string.
Списки
Предположим, мы обрабатываем данные о предметах, которые может преподавать учитель. Код может выглядеть так:
class predicates teacher :(string First_name, string Last_name, string Class) determ. clauses teacher("Ed", "Willis", "english1"). teacher("Ed", "Willis", "math1"). teacher("Ed", "Willis", "history1"). teacher("Mary", "Maker", "history2"). teacher("Mary", "Maker", "math2"). teacher("Chris", "Grahm", "geometry").
Здесь необходимо повторять имя преподавателя для каждого предмета, который он (она) может преподавать. Для каждого предмета необходимо добавлять такой факт в базу данных. Хотя в данной ситуации это не вызывает трудности, можно найти школу, в которой сотни предметов, и тогда поддержка такой структур данных становится утомительной. Тогда было бы удобно создать такой аргумент для предиката, который мог бы воспринимать один или несколько значений.
В Прологе это делает список. В следующем коде аргумент class объявлен имеющим тип список. Покажем, как список представляется в Прологе.
domains classes = string*. /* объявляет списковый домен*/ class predicates teacher :(string First_name, string Last_name, classes Classes) determ. clauses teacher("Ed", "Willis", ["english1", "math1", "history1"]). teacher("Mary", "Maker", ["history2", "math2"]). teacher("Chris", "Grahm", ["geometry"]).
В этом примере код более лаконичен и проще читается, чем код предыдущего примера. Обратите внимание на объявление домена. Звездочка (*) означает, домен classes является списком строк. Так же легко можно объявить список целых:
domains integer_list = integer*.
Объявив домен, теперь просто его использовать, поместив его в качестве аргумента в декларации предиката в секции предикатов. Посмотрим пример использования списка целых:
domains integer_list = integer*. class predicates test_scores : (string First_name, string Last_name, integer_list Test_Scores) determ. clauses test_scores("Lisa", "Lavender", [86, 91, 75]). test_scores("Libby", "Dazzner", [79, 75]). test_scores("Jeff", "Zheutlin", []).
Обратите внимание, в случае Jeff Zheutlin список не содержит никаких элементов.
Еще один пример показывает как можно использовать списки для представления семейного дерева.
domains tree_list = tree*. tree = tree(string Text, tree_list TreeList). class predicates family :(tree) determ. clauses family(tree("Grandmother", [tree("John", [tree("Eric", []), tree("Mark", []), tree("Leonard", []) ] ), tree("Ellen", []) ] )).
Заключение
В этом руководстве были рассмотрены важные понятия:
- Программа на Visual Prolog может содержать множество типов значений: простых и составных, встроенных (стандартных) и определяемых в программе.
- Простые значения - это: числа, строки и т.д..
- Составные домены позволяют рассматривать структуру информации как единую сущность. Составной домен состоит из имени (известного как функтор) и одного или более аргументов. Можно определить домен с несколькими альтернативными фукторами.
- Функтор в Visual Prolog не есть то же, что функция в других языках программирования. Функтор не вызывает никаких вычислений. Это просто имя которое обозначает составной домен и объединяет его аргументы.
- Составные значения могут обрабатываться и рассматриваться как одиночные переменные; функторы используются для создания различия между различными типами составных значений. Visual Prolog позволяет строить многоуровневые структурированные значения; Аргументами составных доменов могут быть опять-таки составные значения. Используя декларации составных смешанных доменов, можно использовать предикаты, которые:
- принимают аргументы нескольких различных типов (определяется объявлениями функторов).
- принимают переменное число аргументов, каждый определенного типа (объявления списков).
- принимают переменное число аргументов, часть из которых могут иметь более одного типа.