Предикаты

Понятие предикаты является распространенным «предикат» не используется. Операторы = и  является функциями – предикатами в том же самом смысле, в каком операторы + и * являются функциями двух переменных, в частности, мы могли бы построить функцию EQUAL (A, B), которая своим результатом имела бы логическое значение TRUE. (или true), если A равно B и FALSE ( или false) в противном случае. То же самое справедливо для других операторов сравнения, таких, как «больше чем», «меньше или равно» и т. д.

В ЛИСПе, как правило, предикаты имеют значение Т для истины и NIL для лжи. Это согласуется с тем, что мы уже говорили ранее об употреблении NIL, а не F. Подобно любой другой конструкции в ЛИСПе предикат является функцией.

Функция АТОМ в качестве аргумента имеет атом или список. Если значением аргумента служит атом, ее значение Т, в противном случае NIL. Так,

если X есть 5, то (АТОМ Х) есть Т;

если X есть (символ), то (АТОМ Х) есть Т;

если X есть (1 2 3). то (АТОМ Х) есть NIL.

Функция NULL проверяет, не является ли значением ее аргумента NIL. Если так, то значением NULL будет Т, в противном случае – NIL.

Так

если X есть 5, то (NULL Х) есть NIL;

если X есть (1 2 3) то (NULL Х) есть NIL;

если X есть NIL, то (NULL Х) есть Т;

Заметим, что если Х является списком из одного элемента, например (Т), то (NULL X) есть NIL, но (NULL (CDR X)) есть Т. Это происходит потому, что, как мы обсуждали в предыдущем разделе, (CDR X) в данном случае доопределяется, чтобы быть NIL.

Функция EQUAL проверяет, равны ли значения двух ее аргументов. Если да, то ее значение Т, в противном случае NIL. Так,

если X есть (4 6 (8 3 )) и Y есть ((4 6 ) 8 3), то (EQUAL X Y) есть NIL;

если X есть (+ 2 2)) и Y есть 4, то (EQUAL X Y) есть NIL;

( (+ 2 2) – есть список с 3 аргументами)

если X есть (+ 2 2) и Y есть (+ 2 2), то (EQUAL X Y) есть Т.

Функция EQ подобна EQUAL.

Функция ZEROP проверяет, является ли ее аргумент нулем. Буква P в ZEROP означает «predicate» (предикат). Если значением аргумента ZEROP служит нуль, то ее значение Т, в противном случае NIL.

Функция > имеет два аргумента. Ее значение – истина, если первый аргумент больше, чем второй, и ложь в противном случае (т. е. ее значением служит NIL). Так,

если Х есть 7 и Y есть 9, то (> X Y)есть NIL;

если Х есть 9 и Y есть 7, то (> X Y)есть Т.

Лекция №5

PROG- выражения в ЛИСПе

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

Аргументы PROG реализуют различные понятия процедурных программ:

1. Описание. Первым документом PROG- служит список переменных, которые будут использоваться в этом PROG и значения которые к моменту использования должно быть определено. Они называются PROG- переменными. Каждая переменная, используемая в PROG- выражении ЛИСПа, должна быть определена.

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

3. Метки. Они также выступают в роли аргументов PROG. Поэтому аргументы PROG бывают трех типов: первый аргумент который является списком PROG- переменных; операторы, которые служат обращениями к функциям, и метки. Метка – это всегда отдельный атом, и благодаря этому она отличается от обращения к функции.

4. Передача управления. Вместо оператора GO TO мы имеем функцию GO. Ее единственный аргумент- метка. Так,

(GO SIGMA)

- это оператор означающий передачу управления на метку SIGMA, т.е. оператору, следующему непосредственно после этой метки.

5. Условные выражения. Функция COND используется вместо оператора IF. Между использованием COND в функциях и в PROG существует два главных различия. В случае PROG- выражения второй элемент каждой пары является не величиной, а оператором ( оператором любого типа). Кроме того, последняя пара не должна начинаться с Т. если COND- выражение в PROG не удовлетворяется ( т. е. если первый член каждой пары в COND равен NIL), то выполняется следующий оператор последовательности

6. Возврат значения. Это делается функцией RETURN. Она имеет один аргумент. Его значение и является значением PROG- выражения. В ЛИСПе записывается просто

(RETUEN Z)

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

Integer procedure fact (n);

value n; integer n;

begin integer i, j;

i: = n; j: = 1;

k: if j = 0 then

begin fact: = j; goto z end

else begin j: = j*i;

i: = i-1; goto k end;

z: end.

В ЛИСПе было бы так:

(DEFUN (N) (PROG ( I J )

(SETQ I N ) (SETQ J 1 )

K (COND ( ( ZEROP I ) (GO L )))

(SETQ J ( * J I))

(SETQ I (- I 1))

(GO K)

L (RETURN J)))

PROG- выражение для обработки списков

Используя PROG в ЛИСПе, тоже можно писать программы, работающие со списками. Рассмотрим, как бы мы обрабатывали список в алгебраическом языке. Прежде всего весьма вероятно, что «список» был бы вовсе не списком, а скорее одномерным массивом. В таком случае мы бы имели индекс, который изменялся бы на 1 при переходе к следующему элементу массива.

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

Чтобы проиллюстрировать такое применение CDR, давайте перепишем функцию ADD, суммирования элементов списка, как программу, использую PROG:

(DEFUN ADD (L) ( PROG (M N )

(SETQ M L ) ( SETQ N 0)

A (COND (( NULL M) (RETURN N )))

(SETQ N (+ N ( CAR M )))

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

В качестве примера рассмотрим работуADD, предположив, что L есть список (4 3 6 2 ). Метка А проходиться в течении работы программы пять раз и переменные M и N в каждой из этих моментов времени имеют следующие значения:

Номер интеграции Значение М Значение N

1 (4 3 6 2 ) 0

2 (3 6 2) 4

3 (6 2) 7

4 (2) 13

5 NIL 15

Таким образом, значением N которое в конце концов будет получено, будет 15= 4+3+6+2 – сумма атомов данного списка L.

На оператор (SETQ M (CDR M)) нужно обратить особое внимание. Он в действительности и является тем оператором, который находит, куда нужно передвинуть указатель при прохождении по списку M, каждый раз, когда этот оператор выполняется, «удаляется» первый элемент списка.