Точно Не проект 2 / Не books / Источник_1

Хотя изначально Лисп предназначался для символьной обработки, современные версии языка не менее эффективно выполняют и числовую обработку.

5.5. Основные функции обработки списков

Для обработки списков в Лиспе имеется небольшой набор базовых функций, образующих ядро языка. Такие функции обеспечивают доступ к различным частям списков и позволяют конструировать из них другие списки.

К операциям выделения отдельных частей списков и создания из них новых структур сводятся многие алгоритмы обработки символьной информации. Основными функциями, на основе которых выполняются указанные действия, являются встроенные функции CAR, CDR и CONS. Ниже рассматриваются также и другие функции, облегчающие работу со списками и имеющиеся в языке Коммон Лисп. Эти функции определяются на основе функций CAR, CDR, CONS. Поскольку список – частный случай точечной пары, то ниже рассматриваются функции, аргументы которых заданы точечными парами.

Для доступа к первому элементу точечной пары или списка применяется функция CAR. Например,

(car ’(a . b)) А (car ’(a b)) А

Здесь апостроф, обозначает вызов специальной формы QUOTE , которая блокирует вычисление значения s-выражения (а . b) или (а b). Если этого не сделать, то Лисп-интерпретатор (EVAL) предпримет попытку вычислить эти s-выражения. В соответствии с правилами работы интерпретатора, первый элемент s-выражения воспринимается как имя функции. Однако, на самом деле, функции с именем А нет. Поэтому возникает ошибка: UNDEFINED-FUNCTION (неопределенная функция). Применение функции QUOTE сообщает Лисп-системе, что аргументы функции CAR не подлежат вычислению и представляют самих себя. Необходимость блокировки вычислений возникает всякий раз, когда рассматриваются символьные данные.

Для выделения второго элемента точечной пары применяется функция CDR. Например,

(cdr ’(a . b)) В (cdr ’(a b)) (В)

Здесь сначала строится точечная пара (Z . NIL), затем точечная пара

– (Y . (Z . NIL)), а в конце – точечная пара (X .(Y . (Z . NIL))), которая и представляет список (X Y Z). Таким образом, функция CONS включает очередной элемент в начало списка, представленного ее вторым аргументом. Конструирование списков с помощью CONS не очень наглядно. В Лиспе имеется функция LIST с произвольным числом аргументов, которая упрощает задачу создания списков:

(list 1 ’b ’c) (1 B C)

Списки можно также создавать из других списков путем их объединения. Для этого применяется функция APPEND. Например,

(append ’(1 2 a) ’(b 4 5)) (1 2 A B 4 5)

В Лиспе имеется ряд других полезных функций для обработки списков: LAST – выделяет последний элемент списка (результат – список); NTH – выделяет n-й элемент списка;

SUBST – выполняет замену элементов в списке; BUTLAST – выделяет список без последних элементов; MEMBER – проверяет принадлежность элемента списку; LENGTH – вычисляет длину списка;

REVERSE – выполняет обращение списка;

ADJOIN – добавляет элемент в множество, представленное списком; REMOVE– удаляет элемент из списка.

Примеры:

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

(setf {место форма }*)

Здесь место – вычисляемое выражение, позволяющее определить лисповскую ячейку памяти, значение которой необходимо изменить.

Примеры:

(setf a 8.8 d 2.0) 2.0 (setq x ’( a b c)) ( A B C)

(setf (car x ) 2 (cadr x ) 3) 3

x(2 3 C)

Впервом примере символ А получает значение 8,8 , а символ d – 2,0. Результатом вызова является последнее присвоенное значение – 2,0. Если принять, что значением символа Х является список (А В С), то второй вызов макроса SETF меняет в этом списке вхождение А на 2, а В на 3. Иными словами, после вызова SETF символ Х будет иметь значение (2 3 С). Если при вызове SETF аргументы не задавать, то результатом вызова будет NIL. Обработка пар аргументов макроса SETF выполняется последовательно слева направо. Макрос SETF позволяет изменять не только значение символа, но и другие его атрибуты.

5.7. Предикаты

Для обработки данных необходимы различные функции, позволяющие выяснять те или иные свойства данных. Так, выполняя арифметические функции, следует убедиться в том, что аргументы – числа, а в случае применения функций CAR и CDR в том, что аргументы представлены точечными парами. Функции, выполняющие такую проверку, возвращают логические значения и называются предикатами. В Лиспе имеется большой набор предикатов. Рассмотрим основные встроенные предикаты Лиспсистем.

Функция EQ сравнивает значения двух своих аргументов. При этом сравнение выполняется не на логическом уровне, а на физическом, т.е. выясняется, представлены ли аргументы в памяти ЭВМ одной и той же физической структурой данных. Функция EQ возвращает значение Т, если ее

аргументы – символы, и в памяти ЭВМ они представлены одной и той же структурой. Сравните следующие вызовы:

(setq x ’(a b c)) (A B C) (setq y ’(a b c)) (A B C) (eq x y) NIL

и

(setq x ’(a b c)) (A B C)

В Лиспе имеется большой выбор предикатов, классифицирующих типы значений: ATOM, NUMBER, INTEGERP, FLOATP, RATIONALP, SYMBOLP,

LISTP и др. Предикат АТОМ проверяет, представляет ли его аргумент атом:

(atom ’a) Т

(atom nil) Т

Предикат NUMBERP устанавливает, является ли его аргумент чис-

лом:

(number 5.0) Т (number ’a) NIL

Предикаты INTEGERP, FLOATP, RATIONALP позволяют выяснить, относится ли значение аргумента к целым, вещественным или рациональным числам, соответственно.

Предикаты SYMBOLP, CONSP, LISTP позволяют из множества различных значений выделять символы, точечные пары и списки:

(setq x ’(a b c)) (A B C) (symbolp x) NIL

(consp x) Т (listp x) Т (consp ’( )) NIL (listp ’( )) Т

Для проверки свойств числовых значений в Лиспе используются предикаты: ZEROP (равенство нулю), ODDP (нечетность), EVENP (четность), MINUSP (отрицательность).

Рассмотренные предикаты обычно применяются при построении тест-форм условных выражений.

5.8.Определение функций

Сматематической точки зрения функция f представляет отображение множества Х на множество Y:

f: Х Y.

Множество Х – задает область определения функции, а множество Y

– область значений функции. Говорят, что f – это функция типа X Y . При этом каждому элементу x X соответствует единственный

элемент y Y. Это обычно записывают в хорошо известной форме y= f(x).

(( lambda ( x ) ( * x x x x x)) 4 ) 1024

(( lambda ( x y) (cons x (cons y nil ))) ’a ’b) (А В)

Такие вызовы называются лямбда-вызовами. В первом примере формальному параметру Х лямбда-списка присваивается фактическое значение 4, а затем вычисляется тело лямбда-выражения. Во втором примере формальным параметрам Х и У назначаются значения фактических параметров, заданных атомами А и В, из которых строится список (А В). По окончании вычислений связи между формальными параметрами и значениями фактических параметров разрушаются.

Проводить вычисление с помощью лямбда-вызовов неудобно, так как приходится каждый раз при очередном вызове заново переписывать тело функции. Проблема решается, если с лямбда-выражением связать некоторое имя (символ), которое будет выступать в роли имени функции, определяемой лямбда-выражением. Для связи имени и лямбда-выражения в Лиспе применяется форма DEFUN:

( defun имя лямбда-выражение )

При этом для упрощения записи в лямбда-выражении опускается слово LAMBDA и скобки. В итоге получаем:

(defun имя лямбда-список {форма}*)

Результатом вызова формы DEFUN является имя определенной функции. Например:

Отметим, что имя функции представляется символом. Поэтому можно говорить о том, что DEFUN устанавливает связь между символом и определением функции.

При задании формальных параметров в форме DEFUN или в лямбдасписке языка Коммон Лисп выделяют:

-обязательные параметры;

-необязательные параметры (optional);

-остаточные параметры, связываемые с хвостом списка параметров

(rest);

-ключевые параметры (key);