Построение списков

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

В качестве примера программы, создающий список, давайте напишем программу под названием REVERSE, которая переписывает список в обратном порядке. Так,

Если Х есть (1 2 3 4 ), то (REVERSE X) будет (4 3 2 1 ).

Программа REVERSE определяется следующим образом:

(DEFUN REVERSE (L) (PROG (M P)

(SETQ M L ) (SETQ P NIL)

A (COND ((NULL M) (RETURN P)))

(SETQ P (CONS (CAR M) P))

(SETQ M (CDR M)) (GO A)))

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

Например, может возникнуть необходимость в функции, которая удваивает каждое целое число из списка целых чисел. Если эта функция называется DOUBLE, то

если X есть (1 2 3 4), то (DOUBLE X) есть (2 4 6 8).

Отчасти для того, чтобы делать это легко и эффективно, многие ЛИСП- системы включают набор функций, которые создают списки из других списков. В совокупности они известны как «МАР- функции».

Функция MAPCAR- типичная MAP- функция. Она имеет два аргумента: второй аргумент обозначает список, а первый аргумент является именем функции. MAPCAR применяет эту функцию последовательно к элементам списка и в качестве своего значения вырабатывает список из результатов этих функций. Более конкретно, MAPCAR применяет данную функцию к (CAR L), (CADR L), (CADDR L), (CADDDR L) и. т. д., т.е, к последовательным элементам списка L. Так, в частности, мы можем определить функцию (DOUBLE X), описанную выше, как (MARCAR X (QUOTE H)), Н- функция, которая удваивает целое число. Более строго, если мы записали

(DEFUN H (N) (+ N N)),

то

(DEFUN DOUBLE (X) (MAPCAR ‘H X))

Имеются и другие MAP-функции, чьё действие мало чем отличается от MAPCAR.

Предикаты, написанные при помощи PROG- выражений

Предикаты могут быть записаны, как PROG- выражения так же, как любые другие функции в ЛИСПе. Просто в этом случае они возвращают Т или NIL, а какое- либо другое значение.

PROG- выражения, которые возвращают T и NIL, очевидно должны возвращать Т в одном месте и NIL в другом. Конечно, не существует каких- либо ограничений, которые препятствовали бы нам иметь один оператор RETURN в одном PROG- выражении. В качестве примера такого предиката мы сейчас опишем PROG, который действует на список, представляющий набор игральных карт.

Формат списка следующий. Каждая карта представляется списком из двух элементов: первый- масть, а второй- достоинство. Так, например:

(PIC TUZ) или (BUB 10) или (TRE 5).

«Игрок» имеет список таких карт. Функция, которую мы определим, будет просматривать такой список, чтобы установить, есть ли пики ( не являются ли пики «пустой мастью»).если пик нет, то в качестве значения возвращается Т, в противном случае NIL. Определение функции имеет следующий вид:

(DEFUN PICN (L) (PROG (M P)

(SETQ M L)

A (COND (( NULL M) (RETURN T)))

(SETQ P (CAR M)) (SETQ M (CDR M))

(COND ((EQUAL (CAR P) ‘PIC)

(RETURN NIL))) ( GO A))

эта функция выдает NIL как только находит пики, если же она не находит пик у игрока, то выдает T. Так,

если X есть ((CHE TUZ) (CHE COR) (CHE 3)

(TRE 4) (TRE 3) (BUB 6)), то

(PICN X) есть T.

Лекция № 6

ПРОДУКЦИОННЕ ПРОГРАММИРОВАНИЕ

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

Продукция = условие + следствие

Под продукцией (rule), или правилом понимается объект, состоящий из двух частей: условия (antecedent, condition) и следствия (consequent, conclusion):

ЕСЛИ условие То следствие

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

В грамматике правила используются для продуцирования предложений или, наоборот, для их распознавания или анализа (parse). В таком случае говорят о правилах трансформации (преобразования) (transformation) и о порождающих правилах (production rule), в которых левая часть есть условие продукции, а правая – следствие продукции.