Структурированные и абстрактные данные

Недостаток программы 2.2, описывающей вентиль «И», состоит в том, что программа рассматривает схему как черный ящик. В ответе на вопрос «and_gate» не содержится никакой информации о структуре схемы, хотя эта структура неявно использовалась при поиске ответа. Правила утверждают, что схема реализует вентиль «И», но структура вентиля задана лишь неявно. Мы устраним этот недостаток, добавив дополнительный аргумент к каждой цели в базе данных. Для единообразия этот аргумент будет стоять на первом месте. Основные факты просто получают идентификатор. На рис. 2.2 отметим слева направо: резисторы r1 и r2, транзисторы t1, t2 и t3.

Имена функциональных компонентов должны отражать их структуру. Инвертор строится из транзистора и резистора. Чтобы представить это, нам потребуются структурированные данные. Нужное средство дает составной терм inv(T,R), где Т и R – соответствующие имена транзистора и резистора, образующих инвертор. Аналогично именем вентиля «И-НЕ» будет nand(T1,T2,R), где T1, T2 и R – имена двух транзисторов и резистора, образующих вентиль «И-НЕ». Наконец, имя вентиля «И» может быть построено на основе имен инвертора и вентиля «И-НЕ». Программа 2.3 представляет собой модифицированный текст, содержащий нужные имена.

Вопрос and_gate(G,In1,In2,Out) имеет решение {G = and(nand(t2,t3r2), inv(t1, r1)), In1 = n3, In2 = n5, 0ut = n1}. In1, In2 и Out имеют те же значения, что и ранее. Сложная структура G в точности отражает функциональную схему вентиля «И».

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

Рассмотрим два способа представления факта о курсе лекций по теории сложности, которую Дэвид Хэрел читает по понедельникам в корпусе им. Фейнберга, аудитория А:

курс(сложность, понедельник, 9, 11, дэвид, хэрел, фейнберг, а).

и

курс(сложность, время(понедельник, 9, 11),

лектор(дэвид, хэрел), место(фейнберг, а)).

Первый факт описывает курс как отношение между восемью элементами: название курса, день недели, время начала, время окончания, имя лектора, фамилия лектора, корпус и аудитория. Второй факт рассматривает курс как отношение между четырьмя элементами: название, время, лектор и место – с дальнейшим уточнением. Время состоит из дня, времени начала и времени окончания; лектор имеет имя и фамилию, место определяется корпусом и аудиторией. Второй факт яснее отражает существующие отношения.

resistor(R, Node1, Node2)

R – резистор с выводами Node1 и Node2.

resistor(r1,power,n1).

resistor(r2,power,n2).

transistor (T,Gate,Source,Drain)

T – транзистор с затвором Gate, истоком Source и стоком Drain.

transistor(t1,n2,ground,n1).

transistor(t2,n3,n4,n2).

transistor(t3,n5,ground,n4).

inverter(I,Input,Output)

I – инвертор, который обращает Input в Output.

inverter(inv(T,R), Input, Output)

transistor(T, Input, ground, Output),

resistor(R, power, Output).

nand_gate(Nand,Input1,Input2,Output)

nand – вентиль «И-НЕ» с входами Input1 и Input2 и выходом Output.

nand_gate(nand(T1, T2, R),Input1, Input2, Output) 

transistor(T1, Input1, X, Output),

transistor(T2, Input2, ground, X),

resistor(R, power, Output).

And_gate(And,inputl.Input2, Output) 

And – вентиль «И» с входами Input1 и Input2 и выходом Output.

and_gate(and(N,I), Input1, Input2, Output)

nand_gate(N, Inputl, Input2, X),

inverter(I, X, Output).

Программа 2.3. База данных схемы с именами.

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

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

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

лектор(Лектор,Курс)  курс(Курс,Время,Лектор,Место).

продолжительность(Курс,ЧислоЧасов) 

курс(Курс,время(День,Начало,Окончание),Лектор,Место). плюс(Начало,ЧислоЧасов,Окончание).

занятие(Лектор,День) 

курс(Курс,время(День,Начало,Окончание),Лектор,Место).

занята(Аудитория,День,Время)

курс(Курс,время(День,Начало,Окончание),Лектор,Аудитория),

НачалоВремя,Время Окончание.

Программа 2.4. Правила расписания.

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

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

день(сложность, понедельник).

время_начала(сложность, 9).

время_окончания(сложность, 11).

лектор(сложность, хэрел).

корпус(сложность, фейнберг).

аудитория(сложность, а).

Правила теперь следует записывать иначе, в духе предыдущего метода явной записи неявных взаимосвязей:

занятие(Лектор, День) 

лектор(Курс, Лектор), день(Курс, День).

Рекурсивные правила

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

Рассмотрим правила, описывающие прародителей, прапрародителей и т.д.:

прародитель(Предок, Потомок) 

родитель(Предок, Человек),

родитель(Человек, Потомок).

прапрародитель(Предок, Потомок) 

родитель(Предок, Человек),

прародитель(Человек, Потомок).

прапрапрародитель(Предок, Потомок) 

родитель(Предок, Человек),

прапрародитель(Человек, Потомок).

Можно заметить простую схему, которую мы опишем в правиле, задающем отношение предок(Предок, Потомок):

предок(Предок, Потомок) 

родитель(Предок, Человек), предок(Человек, Потомок).

Это правило представляет собой обобщение введенных ранее правил.

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

предок (Предок, Потомок) 

Предок является предком субъекта Потомок.

предок(Предок, Потомок) 

родитель(Предок, Потомок).

предок(Предок, Потомок) 

родитель(Предок, Человек), предок(Человек, Потомок).

Программа 2.5. Отношение предок.

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

Рассмотрим программу проверки связности в ориентированном графе. Ориентированный граф может быть задан в виде логической программы с помощью набора фактов. Факт edge(Node1, Node2) входит в программу, если в графе существует ребро, ведущее из вершины Node1 в вершину Node2. На рис. 2.4 изображен некоторый граф, а программа 2.6 дает его представление в виде логической программы

Рис. 2.4. Простой граф.

edge(a,b). edge(a,c). edge(b,d).

edge(c,d). edge(d,e). edge(f,g).

Программа 2.6. Ориентированный граф.

Две вершины графа связаны, если существует последовательность ребер, ведущая из первой вершины во вторую. Таким образом, отношение connected(Node1,Node2), являющееся истинным, если вершины Node1 и Node2 связаны, есть транзитивное замыкание отношения edge. Например, в графе на рис.2.4 вершины а и е связаны, а b и f – нет. Программа 2.7 описывает требуемое отношение. Значение программы совпадает с множеством целей вида connected(X,Y), где X и Y – связанные вершины. Заметим, что ввиду выбора исходного факта connected является транзитивным рефлексивным отношением

connected(Node1,Node2) 

вершина Node1 связна с вершиной Node2 в графе, заданном отношением edge/2.

connected(Node,Node).

соnnected(Nodel,Node2) 

edge(Nodel,Link), connected(Link,Node2).

Программа 2.7.Транзитивное замыкание отношения edge.