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

Недостаток программы 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).

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

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

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

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

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

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