Основные особенности языка программирования лисп
Лисп -- это язык программирования, имеющий широкий набор управляющих
конструкций и функций для обработки созданных пользователем структур данных.
В отличие от многих ЯП, предназначенных изначально для обработки числовых
данных, лисп в первую очередь предназначен для работы с символьными данными
такими как слова и предложения.
Лисп представляет собой язык функционального программирования. Он основан
на алгебре списочных структур, лямбда-исчислении и теории рекурсивных
функций. Функциональный подход к программированию основан на идее, что в
результате каждого действия возникает значение. Значения становятся
аргументами следующих действий, и конечный результат всей задачи выдается
пользователю. Программы строятся из определений функций. Определения состоят
из организующих вычисление управляющих структур и из вложенных, часто
рекурсивных вызовов функций. Кроме функционального стиля программирования
можно использовать стиль, основанный на последовательном исполнении операторов
с присваиваниями, передачами управления и циклами. С помощью
использования макросов можно запрограммировать новые структуры языка и
реализовать совершенно новые языки, одним из них является, например, плэннер.
Можно применять множество методов программирования, характерных для
других языков. Используя лисп и его расширения, можно использовать методы
логического (logic), продукционного (rule-based), и даже ситуационного
(event-based) и объектно-ориентированного (object oriented) программирования.
Для отладки программ существует пошаговый режим исполнения. В лиспе формы для
представления программ и данных одинаковы. И то и другое представляется
списочной структурой. Программы естественным образом могут обрабатывать
другие программы и самих себя. В процессе выполнения программа может
синтезировать новую программу и передать ей управление. Все данные
программы и сама программа хранятся в динамически распределяемой памяти,
поэтому при работе с лиспом всегда доступны все ресурсы памяти компьютера.
Выделение и освобождение динамической памяти происходят автоматически.
Лисп иногда рассматривают не только как язык прикладного программирования,
но и как язык системного программирования. Лисп в том, что его программы и
данные имеют одинаковую форму, напоминает машинный язык компьютера архитектуры
фон Неймана. Для компьютеров, предназначенных исключительно для выполнения
лисп-программ, так называемых лисп-машин, лисп является машинным языком.
Часто интерпретаторы лиспа и интегрированные среды лисп-систем пишутся на
самом лиспе, а наиболее короткий интерпретатор пролога занимает на лиспе
несколько десятков строк.
Программы обычно выполняются в режиме интерпретации, но их можно и
компилировать.
Раньше считалось, что лисп неэффективен для числовых расчетов, что было
связано с тем, что разработчики лиспа вначале придавали им малое по сравнению
с символьной обработкой значение. Но современные трансляторы лиспа для
проведения числовых вычислений могут создать код, который будет быстрее
кода программы на фортране. Это связано с тем, что программы на лиспе легче
оптимизировать.
Большим недостатком лиспа в глазах новичков является обилие скобок. Лиспу
даже была придумана расшифровка его аббревиатуры (``Lots of Idiotic Silly
Parantheses''). Но для программистов, овладевших функциональным образом
мышления синтаксис лиспа является наиболее естественным.
В развитых языках программирования си++ или паскаль с объектами
есть все средства для работы со списочными структурами. Но уровень этих
средств чрезвычайно низок. Поэтому программисту, работающему со списками на
этих языках, приходится практически реализовывать часть возможностей лиспа.
Знакомство с огромным опытом, накопленным за годы развития лиспа, в области
обработки списков поможет ему реализовать развитые средства для работы со
списками наиболее полным и эффективным способом. Для объектно-ориентированных
языков можно реализовать класс, соответствующий лисп-транслятору, и
пользоваться его объектами в случае необходимости сложной обработки списков.
Этот подход практически применяется при переводе программ с лиспа, а также и
с пролога на си++ с целью получения более быстрого кода.
На вариант лиспа, Common Lisp, установлен стандарт ANSI. Существут множество
других вариантов лиспа (AutoLisp, Visual Lisp, Emacs Lisp, muLisp, ...).
Базовый лисп
В лиспе практически любая символьная структура может быть представлена как
отдельный объект. Сначала рассмотрим, что образуют такой объект, и как такие
объекты можно использовать для представления символьных структур данных.
Объекты данных могут быть простыми или составными. Простые объекты
называются атомами. Атом нельзя разделить на компоненты. Каждый атом имеет
имя, например, APPLE, RABBIT, 54321, -41, |КРАСНОЕ ЯБЛОКО|.
Составные объекты называются списками. Списки состоят из нуля или
более объектов, каждый из которых может быть как простым, так и составным.
Списки вводятся и отображаются так, что их элементы заключены в скобки.
Пример списка: (THE QUICK BROWN FOX).
Вследствие того, что лисп является функциональным языком программирования,
манипуляция символьными данными осуществляется при помощи функций.
Получая упорядоченный набор объектов, функция возвращает значение,
основанное на этом наборе. Лисп предоставляет ряд примитивных (определенных
на машинном языке) функций для работы с данными, например, атомами и
списками. Написание программы состоит в определении дополнительных функций
для выполнения желаемого задания.
Работа в лисп-системе похожа на использование калькулятора. После введения
выражения лисп-система вычисляет его, выводит результат на экран и ждет
ввода следующего выражения.
Для того, чтобы предотвратить выражение от непосредственного вычисления
перед ним нужно поставить знак одинарной кавычки (апострофа). Атомы-числа
обозначают самих себя всегда, а прочие атомы могут иметь произвольное
значение, в частности, обозначать самих себя.
Ввод списка предварять апострофом необходимо. Пример списка домашних
животных: '(CAT COW DOG PIG). Если забыть поставить перед подобным списком
апостроф, то это приведет к ошибке, обусловленной попыткой вызова
неопределенной функции.
Элементы списка сами могут быть списками. Например, следующий список может
быть частью структуры данных, описывающей некоторого человека:
'((HEIGHT 172) (WEIGHT 75) (EYES BLUE) (HAIR BLOND)).
Комментарии начинаются со знака ``точка с запятой'' и заканчиваются концом
строки.
Наиболее общими операциями со списками являются выделение членов списка
для дальнейшего анализа. Функции, выполняющие их, называются селекторными.
Две из пяти примитивных функций базового лиспа являются селекторными. Функция
CAR возвращает первый элемент списка, а функция CDR (could-er) -- весь список
без первого элемента. Имена этих функций связаны с языком ассемблера
компьютера 60-х годов IBM 704.
Вызов функции имеет следующий формат:
(<имя функции> <аргумент 1> <аргумент 2> ...),
т.е. левая скобка предшествует имени функции, в отличие от способа записи,
принятого в математике и большинстве языков программирования.
Например, результатом вызова (CAR '(DOG CAT COW PIG)) будет атом DOG, а
результатом (CAR '((RAM 256) (ROM 64) (DISK 322))) будет список (RAM 256).
Программисты называют части списка, возвращаемые функциями CAR и CDR, CAR-
и CDR-частями списка.
Например, CDR-частью списка (DOG CAT COW PIG) является список
(CAT COW PIG), а результатом вызова
(CDR '((HEIGHT 172) (WEIGHT 75) (HAIR BLOND))) будет список
((WEIGHT 75) (HAIR BLOND)).
Аргументом функции может быть результат вызова другой функции,
например, чтобы получить второй элемент списка нужно взять CAR-часть от
CDR-части списка. Результатом вызова (CAR (CDR '(DOG CAT COW PIG))) будет
атом CAT, а результатом вызова
(CAR (CDR (CAR (CDR '((HEIGHT 172) (WEIGHT 75) (HAIR BLOND)))))) -- атом 75.
Кроме функций-селекторов в базовый лисп входит примитивная
функция-конструктор CONS (construct), которая может создавать составные
объекты из более простых. Ее первый аргумент -- это объект, который
добавляется в качестве первого элемента ко второму аргументу-списку.
Например, результатом вызова (CONS 'DOG '(CAT COW PIG)) будет список
(DOG CAT COW PIG), а результатом вызова
(CONS '(EYES BROWN) '((HEIGHT 72) (WEIGHT 175) (HAIR BLOND))) будет
список ((EYES BROWN) (HEIGHT 72) (WEIGHT 175) (HAIR BLOND)).
Т.о. CAR-часть списка-результата, возвращаемого CONS, -- это первый
аргумент CONS, а CDR-часть списка-результата, возвращаемого CONS, -- это
второй аргумент CONS. Например, результатом вызова
(CAR (CONS 'DOG '(CAT COW PIG))) будет атом DOG, а результатом вызова
(CDR (CONS 'DOG '(CAT COW PIG))) будет список (CAT COW PIG). Следующий пример
иллюстрирует возможность вставки элемента из одного списка в другой.
Результат вызова (CONS (CAR '(A B C)) (CDR '(X Y Z))) -- это список (A Y Z).
Для правильного понимания лисп-программ необходимо уметь их правильно
читать. Программу из предыдущего примера следует читать: ``CONS CAR-части
списка (A B C) и CDR-части списка (X Y Z)''. Предписанию: ``Найти CONS
CAR-части от CDR-части списка (A B C) и списка (X Y Z)'', -- соответствует
программа (CONS (CAR (CDR '(A B C))) '(X Y Z)), результат выполнения
которой -- это список (B X Y Z).
Функции CAR и CDR можно применять только к спискам. Для возможности
отличать атомы от списков в базовый
лисп встроена функция ATOM, возвращающая атом T, если ее аргумент -- атом,
и атом NIL в противном случае. Например, результатом вызова (ATOM 'PIE)
будет T, а результатом вызова (ATOM '(DOG CAT COW PIG)) будет NIL. Необычный
результат, T, даст вызов (ATOM '()), т.е. пустой список считается атомом,
совпадающим с NIL. Вследствие этого, результатом вызова (CDR '(APPLE))
будет NIL.
Последней примитивной функцией базового лиспа является EQL, используемая
для сравнения двух атомов. Например, результатом вызова (EQL 'ROM 'RAM) будет
NIL, а результатом вызова
(EQL (CAR '(DOG CAT COW)) (CAR (CDR '(HORSE DOG PIG)))) -- T.
Функцию EQL можно использовать только для сравнения атомов: если
хотя бы один ее аргумент не атом, то ее результат -- NIL. Например,
результат вызова (EQL '(DOG CAT COW) '(DOG CAT COW)) будут NIL.
Определение новых функций
Программист может определять свои собственные функции и впоследствии их
использовать таким же образом как и примитивные. Имя, используемое внутри
определения функции для ссылки на неизвестный аргумент, называется
формальным аргументом. Список формальных аргументов включается в начало
определения функции. Синтаксис определения функции -- следующий:
(DEFUN <имя функции> <список формальных аргументов>
<задание 1>
<задание 2>
... ).
Функция DEFUN (DEfine FUNction) является особенной -- она возвращает значение
своего первого аргумента (имя функции), но используется из-за своего
побочного эффекта. Тело определяемой функции может состоять из одного и более
заданий. Результатом вызова функции является значение последнего выполненного
задания.
Многим не нравятся немнемоничные названия селекторных функций. Используя
DEFUN, можно определить функции с более понятными названиями, выполняющие то
же самое:
(DEFUN FIRST (LST)
(CAR LST) )
(DEFUN TAIL (LST)
(CDR LST) ).
После чего результатом вызова (FIRST (TAIL '(DOG CAT COW PIG))) будет CAT.
Подобным же образом можно определить функцию для извлечения второго элемента
списка:
(DEFUN SECOND (LST)
(CAR (CDR LST)) ).
После чего результатом вызова (SECOND '(DOG CAT COW PIG)) будет CAT.
Таким же образом можно определить функцию THIRD, FOURTH и т.д.
Значениями атомов NIL и T, как и чисел, всегда являются они сами.
Атом NIL имеет очень важное значение, поэтому полезно иметь функцию NULL,
возвращающую T, если ее аргумент NIL, и NIL -- в противном случае.
(DEFUN NULL (ARG)
(EQL NIL ARG))
Результатом вызова (NULL '(A B C)) будет NIL, а (NULL '()) -- T.
Разветвление вычислений
Определенные до сих пор функции были не более чем аббревиатуры для одного
задания, составляющего их тела. Но настоящие возможности функций
раскрываются в их способности выбирать способ действий в зависимости от
аргументов.
Функции, используемые для проверки своих аргументов, называются
предикатами. Примерами таких функций являются EQL, ATOM и NULL.
Основным средством разветвления вычислений является функция COND (от слова
condition), с помощью которой можно строить условные предложения вида
(COND (p1 e1)
(p2 e2)
...
(pN eN) ),
где pi --- это предикаты, а ei --- выражения. Значение функции COND
определяется следующим образом:
1. Последовательно вычисляются предикаты до тех пор, пока вычисленное
значение не станет истинным;
2. Вычисляется выражение, соответствующее этому предикату, --- его значение
считается значением всей функции COND;
3. Если ни одного истинного предиката нет, то значением COND будет NIL.
Вызов COND может принимать следующий вид:
(COND (p1 e1)
(p2 e21 e22 e23 ... e2M)
(p3)
...
(pN eN) ). Если предикату-условию не ставится в соответствие
результирующее выражение, то в качестве результата возвращается значение
этого предиката. Если же условию соответствует последовательность выражений,
то при его истинности выражения вычисляются слева направо и возвращаемым
результатом будет значение последнего выражения.
Определим функцию-предикат LISTP, возвращающую T, если ее аргумент ---
список, и NIL в противном случае:
(DEFUN LISTP (LST)
(COND ((ATOM LST) NIL)
(T) ) ).
В этом определении не учтено, что NIL является одновременно и атомом и
списком. Поэтому его следует усовершенствовать.
(DEFUN LISTP (LST)
(COND
((NULL LST))
((ATOM LST) NIL)
(T) ) )
Примеры вызовов новой функции.
(LISTP 'DOG) ;NIL
(LISTP '()) ;T
(LISTP '(DOG CAT COW)) ;T
При использовании длинных списков естественно иметь функцию, позволяющую
узнать, есть ли заданный элемент в списке или нет. Используя EQL, можно
определить функцию MBR (MemBeR), возвращающую T, если искомый элемент найден,
и NIL, если нет:
(DEFUN MBR (ELEM LST)
(COND
((EQL ELEM (FIRST LST)))
((EQL ELEM (SECOND LST)))
((EQL ELEM (THIRD LST)))
((EQL ELEM (THIRD (CDR LST))))
... ))
Подобное определение неудобно своей длиной и ограничивает длину списка,
который она сможет эффективно обрабатывать. Поэтому нужно использовать другой
подход. Рассмотрим алгоритм поиска вхождения элемента в список:
Шаг 1. Если список пуст, то результат функции -- NIL;
Шаг 2. Если CAR-часть списка равна искомому элементу, то ее результат -- T;
Шаг 3. Искать элемент в CDR-части списка.
Этому рекурсивному алгоритму соответствует следующее определение функции:
(DEFUN MBR (ELEM LST)
(COND
((NULL LST) NIL)
((EQL ELEM (CAR LST)))
((MBR ELEM (CDR LST))) )).
Результатом вызова (MBR 'DOG '(CAT COW DOG PIG)) будет T.
Функция EQL позволяет сравнивать атомы, напишем функцию EQLIST, позволяющую
сравнивать списки, состоящие из атомов. Но сначала выпишем алгоритм ее
работы:
Шаг 1. Если оба списка пусты, то результат --- T;
Шаг 2. Если первый список пуст, то результат -- NIL;
Шаг 3. Если второй список пуст, то результат -- NIL;
Шаг 4. Если CAR-часть первого списка не равна CAR-части второго, то
результат -- NIL;
Шаг 5. Сравнить CDR-части списков.
Этому алгоритму соответствует определение:
(DEFUN EQLIST (LST1 LST2)
(COND
((EQL LST1 LST2))
((NULL LST1) NIL)
((NULL LST2) NIL)
((EQL (CAR LST1) (CAR LST2))
(EQLIST (CDR LST1) (CDR LST2)) ))).
Если определить функцию NOT, то функцию EQLIST можно определить так:
(DEFUN NOT (OBJ) ;возвращает T, если аргумент равен NIL, и NIL в противном
(EQL OBJ NIL) ) ;случае
(DEFUN EQLIST (LST1 LST2)
(COND
((NULL LST1) (NULL LST2))
((NULL LST2) NIL)
((NOT (EQL (CAR LST1) (CAR LST2))) NIL)
((EQLIST (CDR LST1) (CDR LST2))) )).
Функцию NOT необязательно описывать до описания функции EQLIST, ее можно
описать в любом месте до первого вызова ее самой или функции, ее вызывающей.
Описание функции NOT идентично NULL, т.е. вместо нее везде можно использовать
NULL, но это сделало бы логику программы менее понятной.
Теперь если вызвать (EQLIST '(DOG CAT COW) '(DOG CAT COW)), то результатом
будет T.
До сих пор определенные функции были либо селекторами, либо предикатами.
Создадим функцию APPEND для объединения списков: CONS для этого не подходит,
например, результатом (CONS '(A B C) '(X Y Z)) будет ((A B C) X Y Z) вместо
желаемого (A B C X Y Z). Сначала выпишем алгоритм ее работы:
Шаг 1. Если первый список пуст, то возвратить второй список;
Шаг 2. Возвратить CONS CAR-части первого списка и результата APPEND,
примененной к CDR-части первого списка и ко всему второму списку.
Этому алгоритму соответствует определение:
(DEFUN APPEND (LST1 LST2)
(COND
((NULL LST1) LST2)
((CONS (CAR LST1) (APPEND (CDR LST1) LST2))) )).
Вызов (APPEND '(A B) '(X Y)) обусловит вызов
(CONS 'A (APPEND '(B) '(X Y))). Вызов (APPEND '(B) '(X Y)) обусловит вызов
(CONS 'B (APPEND () '(X Y))), результатом которого будет (B X Y), т.е.
результатом вызова (CONS 'A (APPEND '(B) '(X Y))) будет (A B X Y), что и
требовалось.
Для работы со списками необходима функция, которая может удалять
заданный элемент из заданного списка. Определим функцию REMBER (REMove
memBER), которая удаляет первое вхождение первого аргумента-атома во втором
аргументе-списке, например, результатом (REMBER 'DOG '(CAT DOG COW DOG))
должен быть список (CAT COW DOG):
(DEFUN REMBER (ATM LST)
(COND
((NULL LST) NIL)
((EQL ATM (CAR LST)) (CDR LST))
((CONS (CAR LST) (REMBER ATM (CDR LST)))) )).
Часто нужно удалять все вхождения заданного элемента, а не только первое.
Опишем для этого функцию REMBER-ALL:
(DEFUN REMBER-ALL (ATM LST)
(COND
((NULL LST) NIL)
((EQL ATM (CAR LST))
(REMBER-ALL ATM (CDR LST)) )
((CONS (CAR LST) (REMBER-ALL ATM (CDR LST)))) )).
Функцию REVERSE для инвертирования списка можно описать так:
(DEFUN REVERSE (LST)
(COND
((NULL LST) NIL)
((APPEND (REVERSE (CDR LST)) (CONS (CAR LST) ()))) )).
Конструкция (CONS (CAR LST) ()) необходима, т.к. аргументами APPEND могут
быть только списки. Вместо этой конструкции можно использовать примитивную
функцию лиспа LIST, которая превращает свои аргументы в список, т.е. вместо
использованной конструкции можно использовать (LIST (CAR LST))
Результатом вызова (REVERSE '(DOG CAT COW PIG)) должен быть список
(PIG COW CAT DOG).
Данное определение функции REVERSE очень неэффективно, т.к. APPEND
вызывается для каждого элемента инвертируемого списка. Гораздо быстрее
будет функция, описание которой основано на аналогии с действиями при
инвертировании порядка следования лежащих друг на друге листов бумаги.
При работе с листами их просто перекладывают лист за листом на новое место.
Таким образом, в функции REVERSE нужно сначала создать пустой список, а затем
перенести в него все элементы исходного:
(DEFUN REVERSE (LST1 &optional LST2)
(COND
((NULL LST1) LST2)
((REVERSE (CDR LST1) (CONS (CAR LST1) LST2))) )).
Хотя в описании функции объявлено два формальных аргумента, ее можно
вызывать с одним фактическим аргументом: неуказанным явно при вызове
аргументам автоматически назначается значение NIL. Необязательные формальные
аргументы необходимо предварять директивой &OPTIONAL.
Типы данных
В лиспе имена символов, переменных, списков, функций и других объектов не
закреплены предварительно за каким-нибудь типом данных. Типы не связаны с
именами объектов данных, а сопровождают сами объекты. Таким образом,
переменные могут в различные моменты представлять различные объекты, тип
которых определяется по ходу исполнения программы. Только в этом смысле лисп
является бестиповым языком. Набор же возможных типов данных для развитых
лисп-систем очень разнообразен.
Динамическая, осуществляемая лишь в процессе исполнения, проверка типа и
позднее связывание (late binding) допускают разностороннее использование
символов и гибкую модификацию программы. При позднем связывании связь вызова
функции с ее кодом осуществляется на этапе исполнения программы, а не на
этапе компиляции. Одним из примеров позднего связывания являются
виртуальные функции.
Функции можно определять практически независимо от
типов данных, к которым они применяются. Платой за эту
необычайную гибкость является скорость исполнения. В некоторых диалектах
лиспа есть возможность для ускорения работы программ жестко привязывать
тип данных к объектам данных. В лисп-машинах проверка типов данных на этапе
исполнения осуществляется на аппаратном уровне и не замедляет исполнение
программ.
В лиспе есть три вида примитивных объектов данных: символы, числа и
(точечные) пары (списочные ячейки, conses -- по имени функции CONS).
Лисп обеспечивает возможность использовать множество функций для
различения, сравнения, соединения и преобразования этих примитивных объектов,
что позволяет создавать сложные структуры данных, которые могут
моделировать в компьютере проблемы реального мира.
В базовом лиспе есть только два типа данных: атомы и списки. В лиспе
атомы делятся на символы и числа, а списки являются частным случаем более
общих структур, называемых бинарными деревьями, которые строятся из пар.
Каждый символ лиспа имеет 4 атрибута:
1. Имя -- уникальная последовательность кодов расширенного ASCII,
используемая для идентификации символов при вводе и отображении
значения символов при выводе. Имя символа не может быть изменено,
его можно получить, используя примитивную функцию SYMBOL-NAME;
2. Текущее значение. Значением символа может быть любой объект данных,
его можно получить, используя примитивную функцию SYMBOL-VALUE
или сам символ;
3. Текущее определение функции. Если символ является CAR-частью списка,
то этот список можно рассматривать как вызов функции, ассоциируемой с
этим символом. Предопределенное значение определения функции для
символа -- это функция-ошибка, сообщающая о вызове неопределенной
функции. Определение функции, назначенной данному символу, можно
многократно менять -- используется последнее выполненное определение.
Определение функции, соответствующее символу, можно получить, используя
примитивную функцию SYMBOL-FUNCTION;
4. Список свойств -- это список, состоящий из пар элементов, первый
элемент которых -- это имя свойства, а второй -- его значение.
Предопределенное значение списка свойств -- это пустой список.
Список свойств, соответствующий символу, можно получить, используя
примитивную функцию SYMBOL-PLIST.
Функция-предикат SYMBOLP возвращает T, если ее единственный аргумент --
символ и NIL в противном случае. Например, вызов (SYMBOLP 'XYZ) возвращает T,
вызов (SYMBOLP 41) -- NIL, вызов (SYMBOLP '(DOG CAT COW)) -- NIL, а вызов
(SYMBOLP NIL) -- T. Символ NIL является особым случаем -- его
предопределенное значение не может быть изменено.
В лиспе функции NULL, NOT, LISTP, EQUAL, REVERSE, LENGTH и APPEND являются
примитивными, причем APPEND допускает любое число аргументов.
Знаки пробел, круглые скобки, точка, двойная и одинарная кавычки, точка с
запятой, обратная наклонная черта и вертикальная черта имеют специальные
значения и не могут обычным образом использоваться в составе имени символа.
Знаки обратная косая черта (backslash) и вертикальная черта
используются для возможности вводить в состав имени любой код расширенного
ASCII. Любой одиночный знак после обратной косой черты не имеет
уже никакого специального значения, при этом сам знак обратной косой черты
отбрасывается. Все знаки, кроме знака обратной косой черты, заключенные между
знаками вертикальной черты, также теряют возможные специальные значения,
причем сами заключающие знаки вертикальной черты отбрасываются.
Все строчные латинские буквы в символах по умолчанию преобразуются в
заглавные, чтобы избежать этого нужно использовать символы обратной косой
или вертикальной черты. Например, |This is a (single) symbol.|.
Примитивная функция SET позволяет присвоить символу значение, например,
после вызова (SET 'FRUITS '(APPLES ORANGES LEMONS PEARS)), результатом
которого будет список (APPLES ORANGES LEMONS PEARS), текущее значение символа
FRUITS станет список-результат вызова.
Обычно первым аргументом SET является символ, следующий за апострофом.
Поэтому предусмотрена функция SETQ (SET Quote), позволяющая не
писать апостроф. Например, вызов (SETQ FRUITS '(APPLES ORANGES LEMONS PEARS))
идентичен рассмотренному ранее.
По историческим причинам существует функций QUOTE, эквивалентная знаку
апострофа, например, записи '(A B C) и (QUOTE (A B C)) -- эквиваленты.
Рассмотрим следующий пример:
(SETQ VOWELS '(A E I O U))
(SETQ VOWELS (CONS 'Y VOWELS)) ;значение VOWELS -- список (Y A E I O U).
Числа делятся на целые и отношения. Целые числа вводятся как
последовательный ряд 10-х цифр, которым может предшествовать знак минус.
Для сравнения чисел можно использовать функцию EQL, но есть более мощная
функция =, которая сравнивает все свои аргументы-числа и генерирует сообщение
об ошибке, если хотя бы один ее аргумент нечисло. Например, результат вызова
(= 3 3 0) будет NIL, а результат вызова (= 2 2 2 2) -- T.
Отношения можно вводить двумя способами: при помощи нотации с десятичной
точкой или как дроби с числителем и знаменателем. Примеры чисел-отношений:
3/4, -0.34, -17/5. [Можно указать лисп-системе показывать числа-отношения
любым из этих способов, а в случае выбора десятичной нотации указать еще
и количество показываемых после десятичной точки знаков.]
Функция-предикат INTEGERP возвращает T, если ее единственный аргумент --
целое число и NIL в противном случае. Например, вызов (INTEGERP '123)
возвращает T, вызов (INTEGERP 41) -- T, вызов (INTEGERP 'FIVE) -- NIL, вызов
(INTEGERP 1/2) -- NIL.
Функция-предикат NUMBERP возвращает T, если ее единственный аргумент --
число и NIL в противном случае. Например, вызов (NUMBERP '-25) возвращает T,
вызов (NUMBERP '(A B)) -- NIL, вызов (NUMBERP -1/3) -- T, а вызов
(NUMBERP |123|) -- NIL (|123| или \1\2\3 --- не число, а символ).
Пара --- это примитивный неатомарный объект данных, который указывает на
два других объекта данных.
Любой примитивный объект данных занимает в памяти компьютера
непрерывный участок, имеющий адрес. Пара -- это упорядоченный набор двух
адресов памяти компьютера, указывающих на примитивные объекты данных.
Рассмотрим, например, пару, указывающую на атомы BILBO и 31:
+-----+-----+
| . | . |
+-/---+---\-+
/ \
/ \
BILBO 31.
Сокращенно эту же пару можно изобразить так:
.
/ \
/ \
BILBO 31.
Хотя соединение набора пар представляется в виде бинарного дерева,
линейное представление пар более удобно для использования в языке
программирования. Линейное представление бинарных деревьев в лиспе основано
на точечной нотации, в которой пара представляется в виде открывающей скобки,
элемента данных, точки, элемента данных и закрывающей скобки. Пара из
предыдущего примера в точечной нотации -- это (BILBO . 31), а бинарное дерево
.
/ \
/ \
. 31
/ \
/ \
BILBO BAGGINS
в точечной нотации -- это ((BILBO . BAGGINS) . 31). Точки в точечной нотации
необходимо окружать пробелами, т.к. сама точка является знаком элемента-пары
в списке, представляющем бинарное дерево. Кроме того, необходимо различать
точки-пары и десятичные точки.
Левый элемент пары называется CAR-частью пары, а правый -- CDR-частью.
Добавим к дереву, описывающему Бильбо, факт того, что он -- хоббит:
.
/ \
/ \
. HOBBIT
/ \
/ \
. 31
/ \
/ \
BILBO BAGGINS
или в точечной нотации (((BILBO . BAGGINS) . 31) . HOBBIT). Эти же данные
можно представить и другим бинарным деревом
((BILBO . BAGGINS) . (31 . HOBBIT)), т.е.
.
/ \
/ \
/ \
. .
/ \ / \
/ \ / \
BILBO BAGGINS 31 HOBBIT.
Более естественно и удобно представлять пары в виде списка объектов, а не
в виде бинарного дерева. Например, элементы множества естественно показывать
в виде списка.
Лисп представляет список как набор пар, чья CAR-часть указывает на элемент
списка, а CDR-часть указывает на следующую пару. Список заканчивается парой,
CDR-часть которой указывает на NIL. Итак, список -- это структура вида
.--------.--- . . . ---.----- NIL
| | |
| | |
object1 object2 objectN.
Этой структуре соответствует список (object1 object2 ... objectN) или
(object1 . (object2 . ... (objectN . NIL) ...)). Естественно, что первая
запись гораздо предпочтительнее.
Можно совмещать точечную и обычную нотации, например, бинарное дерево вида
.------.------.----- D
| | |
| | |
A B C
лучше всего представить в виде (A B C . D).
Основные приемы программирования и использования примитивных функций
В базовом лиспе CDR всегда возвращает результат-список, но если работать
с парами, то результатом CDR может быть и атом, например,
результат вызова (CDR '(RED . BLUE)) -- это атом BLUE.
Для удобства в большинстве версий лиспа многочисленные последовательные
вызовы CAR и CDR можно заменять на вызов одной функции-сокращения, имя
которой начинается с C, заканчивается R, а средние буквы индицируют
последовательность вызовов CAR и CDR. Например, вызов
(CAR (CDR '(DOG CAT COW))) можно заменить на (CADR '(DOG CAT COW)).
Таким образом можно использовать функции с именами CDAR, CAAR, CDDR, CAAAR,
CAADR, CADAR, CDAAR и т.д. Ранее была определена функция SECOND, используя
введенные функции-сокращения ее можно определить так:
(DEFUN SECOND (LST)
(CADR LST) ).
Аналогично,
(DEFUN THIRD (LST)
(CADDR LST) ).
До сих пор не была определена функция, позволяющая получить последний
элемент списка. Определим функцию LAST-ELEMENT для этой цели:
(DEFUN LAST-ELEMENT (LST)
(CAR (REVERSE LST)) ).
После чего результатом вызова (LAST-ELEMENT '(THE QUICK BROWN FOX)) будет
атом FOX.
До сих пор рассматривался так называемый заявительный (APPLICATIVE) стиль
программирования. В этом стиле особое внимание уделяется вычислению
выражений, композиции функций и рекурсии. Кроме него лисп также поддерживает
итерационный стиль программирования, в котором особое внимание уделяется
управляющим структурам, работе с переменными и последовательным вычислениям.
Особая функция LOOP -- это главный компонент итерационных конструкций. Она
может иметь любое количество аргументов-заданий, которые выполняются подобно
заданиям тела функции, но с рядом отличий:
1. После выполнения последнего задания, т.е. вычисления последнего
аргумента, управление передается на первое задание;
2. Если выполнилась функция RETURN с аргументом-выражением, то значение
этого выражения возвращается как результат LOOP.
LOOP может иметь сколько угодно функций RETURN, но если в ней не будет ни
одной такой функции, то ее выполнение будет бесконечным.
Использование LOOP можно проиллюстрировать на примере итерационного
описания функции LAST-ELEMENT:
(DEFUN LAST-ELEMENT (LST)
(COND ((ATOM LST) NIL))
(LOOP
(COND ((NULL (CDR LST)) (RETURN (CAR LST))))
(SETQ LST (CDR LST)) )).
Фактические аргументы копируются в формальные, поэтому
применение этой функции к любому списку не сможет его разрушить. Таким
образом, параметры функций лиспа передаются по значению, а не по ссылке.
В лиспе есть примитивная функция LAST, которая возвращает
последнюю пару списка. Используя LAST, можно определить LAST-ELEMENT так:
(DEFUN LAST-ELEMENT (LST)
(CAR (LAST LST)) ).
Таким образом результат вызова (LAST '(THE QUICK BROWN FOX)) будет список
(FOX), а результатом вызова (LAST '(23 54 -23 15 . 27)) -- (15 . 27).
Для работы со списками полезна примитивная функция-селектор NTH,
которая имеет два аргумента: первый -- номер элемента в списке, второй --
список, из которого выделяется элемент. Нумерация элементов в списке
начинается с нуля. Например, результатом вызова (NTH 4 '(A B C D E F G H I))
будет атом E. Если требуемый элемент выделить невозможно, то результатом
NTH будет NIL.
Используя NTH, определим функцию INDEXER, которая имеет два
аргумента-списка и возвращает те элементы первого списка, номера которых
входят во второй, например, результатом вызова
(INDEXER '(A B C D E F G) '(6 2 4 0)) должен быть список (G C E A):
(DEFUN INDEXER (LST1 LST2 &optional LST3)
(LOOP
(COND ((NULL LST2) (RETURN LST3)))
(SETQ LST3
(APPEND LST3
(LIST (NTH (CAR LST2) LST1)) ))
(SETQ LST2 (CDR LST2)) )).
Не используя APPEND, INDEXER можно определить так:
(DEFUN INDEXER (LST1 LST2)
(COND
((NULL LST2) NIL)
((CONS
(NTH (CAR LST2) LST1)
(INDEXER LST1 (CDR LST2))) ))).
Аналогичная NTH по синтаксису функция-селектор NTHCDR возвращает остаток
(хвост) списка, т.е. если n -- это первый аргумент, то NTHCDR возвращает
n-ый CDR списка. Например, результатом вызова
(NTHCDR 0 '(A B C D)) будет (A B C D), результатом вызова
(NTHCDR 2 '(A B C D)) -- (C D), а результатом вызова (NTHCDR 4 '(A B C D))
-- NIL. В случае бессмысленного аргумента NTHCDR возвращает NIL.
Рассмотрим теперь подробнее примитивные функции-конструкторы.
Ранее функция CONS использовалась только для образования списков, но
CONS является функцией в общем случае, образующей пару, а не список.
Например, вызов (CONS 'AGE 43) имеет результатом пару (AGE . 43).
Рассмотрим следующий пример. Пусть необходимо создать список значений,
присвоенных переменным FIRSTNAME, LASTNAME и ADDRESS. Это можно сделать так:
(SETQ FIRSTNAME 'Jane)
(SETQ LASTNAME 'Smith)
(SETQ ADDRESS '(Honolulu Hawaii))
(CONS FIRSTNAME (CONS LASTNAME (CONS ADDRESS NIL))).
Вместо последней конструкции удобнее использовать конструкцию с примитивной
функцией LIST: (LIST FIRSTNAME LASTNAME ADDRESS).
Примитивную функцию APPEND используют для соединения любого числа списков в
один список, например, результатом вызова
(APPEND '(DOG CAT COW) '(SNAKE LIZARD CROCODILE) '(TROUT SALMON TUNA)) будет
список (DOG CAT COW SNAKE LIZARD CROCODILE TROUT SALMON TUNA).
Для выделения различий между тремя рассмотренными функциями-конструкторами
применим их к одним и тем же аргументам:
(CONS '(DOG CAT) '(COW PIG)) ; ((DOG CAT) COW PIG)
(LIST '(DOG CAT) '(COW PIG)) ; ((DOG CAT) (COW PIG))
(APPEND '(DOG CAT) '(COW PIG)) ; (DOG CAT COW PIG).
Ранее рекурсивно была определена функция REVERSE, инвертирующая свой
аргумент-список. Определим теперь REVERSE, используя итерацию:
(DEFUN REVERSE (LST1 &optional LST2)
(LOOP
(COND ((NULL LST1) (RETURN LST2)))
(SETQ LST2 (CONS (CAR LST1) LST2))
(SETQ LST1 (CDR LST1)) )).
Часто при использовании итерации нужно получить значение первого элемента
списка и затем изъять его из списка. Для удобства программирования такой
последовательности операций используется примитивная функция POP, извлекающая
первый элемент из списка-аргумента и возвращающая его значение, т.е. POP
изменяет свой аргумент.
Другой часто возникающей при итерационном стиле программирования ситуацией
является необходимость вставить элемент в список, который является значением
переменной, с соответствующим изменением после этого значения этой
переменной, как например, в вызове (SETQ lst (CONS object lst)). Для удобства
программирования подобной ситуации используется примитивная функция PUSH,
которая вместо вызова из предыдущего примера позволяет использовать вызов
(PUSH object lst).
Используя POP и PUSH, можно определить REVERSE так:
(DEFUN REVERSE (LST1 &optional LST2)
(LOOP
(COND ((NULL LST1) (RETURN LST2)))
(PUSH (POP LST1) LST2) ) ).
При выборе между рекурсией и итерацией нужно учитывать, что рекурсивные
алгоритмы чуть-чуть медленнее, но и меньше (часто намного) итерационных.
Недостатком рекурсивных алгоритмов является их зависимость от размера
системного стека, который ограничивает количество вложенных вызовов. Если
при использовании какой-либо рекурсивной функции выполнение программы аварийно
прекратится с сообщением о переполнении стека, то следует использовать
итерационную версию этой функции. Однако, рекурсивный подход --- более мощный,
существуют рекурсивные алгоритмы (например, расчет функции Аккермана), которые
нельзя свети к итерационным.
Функции могут менять значения символов, не включенных в список аргументов,
-- это называется побочным эффектом функций. Пользоваться подобными
возможностями нужно с осторожностью, т.к. их трудно отслеживать и они часто
приводят к труднонаходимым ошибкам. Локальные переменные вводятся после
&OPTIONAL в списке формальных аргументов.
Для поддержки работы с логическими выражениями есть три примитивные
функции: AND, OR и NOT. Лжи соответствует NIL, истине -- любое
значение, отличное от NIL.
Функция OR может иметь любое количество аргументов и вычисляет их слева
направо до тех пор, пока результатом вычисления не станет величина, отличная
от NIL, или не останется больше аргументов для вычисления. В первом случае
значением OR будет вычисленная величина, отличная от NIL, во втором -- NIL.
OR не вычисляет аргументов, следующих за тем, значение которого не NIL.
Используя OR, можно определить функцию-предикат ATOM, эквивалентную
примитивной:
(DEFUN ATOM (ARG)
(OR (SYMBOLP ARG) (NUMBERP ARG)) ).
Функция AND может иметь любое количество аргументов, она вычисляет их слева
направо до тех пор, пока результатом вычисления не является NIL или не
останется больше аргументов для вычисления. Значением AND будет последняя
вычисленная величина. AND не вычисляет аргументов, следующих за тем, значение
которого NIL. Например, результатом вызова (AND (SYMBOLP 'frog) (NUMBERP 7))
будет T.
Математические функции и вычисления
В лиспе есть возможность работать как с точной арифметикой целых чисел
неограниченной длины, так и с приближенной и точной арифметикой дробей.
Первая возможность позволяет эффективно использовать лисп для работ в
области теории чисел и криптографии. Точность вычислений с дробями можно
регулировать в определенных пределах.
Примитивными арифметическими функциями являются +, *, - и /. Все они
могут иметь неограниченное количество аргументов, например, результатом
(+ 1 2 3 4 5) будет 15, результатом (* 1 2 3 4 5) -- 120, результатом
(- 1 2 3) -- -4 (запись (- 1 2 3) эквивалентна математической записи
1 - 2 - 3), а результатом (/ 48 2 3) -- 8. Если арифметическую функцию
вызвать с хотя бы одним нечисловым аргументом, то это приведет к аварийному
прекращению ее выполнения с выдачей сообщения о недопустимом аргументе.
Другие полезные функции -- это MAX и MIN, например, (MAX 2 7 5) вернёт 7.
Определим функцию для вычисления факториала:
(DEFUN FACTORIAL (N)
(COND
((= N 0) 1)
((* N (FACTORIAL (- N 1)))) ))
или так
(DEFUN FACTORIAL (N)
(OR
(AND (= N 0) 1)
(* N (FACTORIAL (- N 1)))) ).
Используя эту функцию можно, например, вычислить 100! (это 78-значное
число). Более эффективной с точки зрения быстроты вычислений будет
итерационная реализация функции-факториал:
(DEFUN FACTORIAL (N &optional F)
(SETQ F 1)
(LOOP
(COND ((= N 0) (RETURN F)))
(SETQ F (* N F))
(SETQ N (- N 1)) )).
Вместо конструкции (= N 0) можно использовать примитивную функцию-предикат
ZEROP с единственным аргументом в конструкции (ZEROP N).
В лиспе есть примитивная функция ! для вычисления факториала, например,
результатом (! 5) будет 120.
Последовательность, которую можно встретить в природе в самых необычных
местах, два первых элемента которой 1, а остальные равны сумме двух
предыдущих, называется последовательностью Фибоначчи. Рекурсивную функцию
для вычисления N-го члена этой последовательности можно определить так:
(DEFUN FIBONACCI (N)
(COND
((= N 0) 1)
((= N 1) 1)
((+ (FIBONACCI (- N 1)) (FIBONACCI (- N 2)))) )).
Это очень медленно работающий из-за двойной рекурсии алгоритм. Определим
функцию для вычисления чисел Фибоначчи итерационно:
(DEFUN FIBONACCI (N &optional S1 S2 Z)
(SETQ S1 1)
(SETQ S2 0)
(LOOP
(COND ((= N 0) (RETURN S1)))
(SETQ Z (+ S1 S2))
(SETQ S2 S1)
(SETQ S1 Z)
(SETQ N (- N 1)) )).
Определим теперь функцию POWER, возводящую свой первый аргумент в степень
значения второго аргумента:
(DEFUN POWER (N P &optional M)
(SETQ M 1)
(LOOP
(COND ((= P 0) (RETURN M)))
(SETQ M (* N M))
(SETQ P (- P 1)) )).
Вместо вызова (- P 1) можно использовать вызов (1- P), а вместо
вызова (+ P 1) -- (1+ P). Функции 1+ и 1- являются примитивными.
Ещё короче использовать вместо (SETQ P (- P 1)) (INCF P), а для
уменьшения на 1 -- DECF.
Функцию POWER можно определить и рекурсивно, по следующему алгоритму:
Шаг 1. Если P равно 0, то N в степени P равно 1;
Шаг 2. Если P -- четное, то N в степени P равно N в квадрате в степени
P/2;
Шаг 3. N в степени P равно N умножить на N в степени P-1.
Для реализации этого алгоритма удобно воспользоваться примитивной функцией
EVENP, которая возвращает T только в случае, если ее единственный аргумент --
четное число и NIL в других случаях. Получим:
(DEFUN POWER (N P)
(COND
((ZEROP P) 1)
((EVENP P) (POWER (* N N) (/ P 2)))
((* N (POWER N (- P 1)))) )).
Примитивная функция ODDP --- это отрицание EVENP.
Примитивная функция EXPT по результату и аргументам не отличается от
определенных функций POWER.
Примитивная функция TRUNCATE возвращает целое число, получаемое из ее
единственного аргумента отбрасыванием дробной части, например,
результатом (TRUNCATE 7/3) будет 2, результатом (TRUNCATE -0.95) --- 0.
Кроме того, TRUNCATE можно вызывать и с двумя аргументами. В этом
случае вызов (TRUNCATE n m) эквивалентен (TRUNCATE (/ n m)). Например,
результатом (TRUNCATE 7 2) будет 3, а результатом (TRUNCATE -46.3 5.2) ---
-8.
Примитивная функция REM возвращает остаток от деления ее первого аргумента
на второй. Если результат (TRUNCATE n m) --- q и результат (REM n m) --- r,
то n = q*m + r.
Одним из наиболее фундаментальных в теории чисел является алгоритм Евклида
поиска наибольшего общего делителя (НОД) двух целых чисел. Вычисление
НОД(n,m) согласно нему происходит так:
Шаг 1. Если n = 0, то НОД(n,m)=|m|;
Шаг 2. НОД(n,m) = НОД(m mod n, n).
Его реализация может быть следующей:
(DEFUN EUCLID (N M)
(COND
((ZEROP N) (ABS M))
((EUCLID (REM M N) N)) )).
Примитивная функция ABS возвращает модуль своего единственного аргумента.
В лиспе есть примитивные функции GCD (Greatest Common Diviser) и LCM (Least
Common Multiple) для вычисления НОД и наименьшего общего кратного (НОК)
соответственно, которые могут принимать любое число аргументов.
С числами, кроме функции =, можно еще использовать примитивные
функции-сравнители /=, <, >, <=, >=. Например, результатом
(= 34 34.0) будет T, (/= 3/4 0.75) -- NIL, (< 67 45) -- NIL, (>= 19 17 17) --
T. Функции-сравнители можно вызывать с неограниченным количеством аргументов,
в этом случае аргументы последовательно попарно сравниваются: если все
сравнения успешны, но результат T, в противном случае результат -- NIL.
Например, результатом вызова (< 96 102 114 123) будет T.
При работе со списками часто возникает необходимость их сортировки.
Реализуем сортировку вставкой списка чисел по возрастанию. Сначала нужно
создать функцию INSERT-NUM, вставляющую свой первый аргумент в правильное
место второго аргумента, отсортированного списка:
(DEFUN INSERT-NUM (NUM LST)
(COND
((NULL LST) (LIST NUM))
((< NUM (CAR LST)) (CONS NUM LST))
((CONS (CAR LST) (INSERT-NUM NUM (CDR LST)))) )).
Например, результатом вызова (INSERT-NUM 12 '(5 9 11 14 19 21)) будет список
(5 9 11 12 14 19 21). Напишем теперь функцию NUMBER-SORT, возвращающую
отсортированным свой аргумент-список:
(DEFUN NUMBER-SORT (LST1 &optional LST2)
(LOOP
(COND ((NULL LST1) (RETURN LST2)))
(SETQ LST2 (INSERT-NUM (POP LST1) LST2)) )).
Рекурсивный вариант этой функции можно реализовать так:
(DEFUN NUMBER-SORT (LST)
(COND
((NULL LST) NIL)
((INSERT-NUM (CAR LST) (NUMBER-SORT (CDR LST)))) )).
Примитивная функция SORT вызывается с двумя аргументами: первый -- это
сортируемый список, второй -- это имя функции-сравнителя. Результат вызова
SORT -- это отсортированный первый аргумент-список. Например, вызов
(SORT '(34 23 -14 27 56 22 83) '<) даст в результате (-14 22 23 27 34 56 83),
а вызов (SORT '(DOG CAT RAT COW PIG) 'STRING<) -- (CAT COW DOG PIG RAT).
Функция SORT изменяет свой аргумент, делая его отсортированным.
Примитивная функция STRING< -- это одна из функций-сравнителей строк.
Кроме нее есть также функции STRING>, STRING=, STRING/=, STRING<= и STRING>=.
Лямбда-исчисление
В 1930 Черч предложил специальную форму записи для функции, вводить
символическое обозначение для которой не нужно. Например, для записи значения
функции sin(2x) в точке 1 используется следующая конструкция
\lambda sin(2x)(1). Сегодня для записи того же чаще используется конструкция
|
sin(2x)|
|x=1.
Лямбда-запись является одной из фундаментальных конструкций лиспа. Например,
значением вызова ((lambda (x) (+ x 5)) 5) будет 10, а значением вызова
((lambda (x y) (cons x y)) '(a) 'b) будет пара ((a) . b).
Использование лямбда-записи позволяет избавить программу от введения
ненужных имен для функций.
Функция EVAL
Эта функция вычисляет значение своего аргумента. Например, результатом
вызова следующей далее последовательности функций будет X.
(SETQ X 'Y)
(SETQ Y 'Z)
(SETQ Z 'X)
(EVAL Y)
Применение этой функции к синтезируемым в программе спискам --- это
необычайно мощное средство, отсутствующее не только в языках программирования
классической структуры (паскаль, си++, ада и т.п.), но и в прологе.
Пример синтеза и выполнения программы:
(SETQ PRG (CONS 'CAR '('(A B C))))
(EVAL PRG) ;A.
Функции ввода-вывода и преобразования типов
У READ нет аргументов -- она читает данные со стандартного потока ввода и
возвращает их в качестве результата. У PRINT в точности 1 аргумент, который
распечатывается. Например, (PRINT (READ)).
Для посимвольного ввода можно использовать (READ-CHAR), результат которой
знак таблицы кодировки - особый тип, например, #\s, #\N, #\1, #\Newline,
#\Space. Для преобразования типов есть функция coerce.
Пример.
(coerce '(#\A #\B #\7) 'string) ;"AB7"
(coerce 'a 'character) ;#\a
(coerce "aB2" 'list) ;(#\a #\B #\2)
(set (intern "AB7") 'ok)
AB7 ;ok
(symbol-name 'A2) ;"A2"
Таким образом, для преобразования типа строки в тип символ и обратно нужны
функции INTERN и SYMBOL-NAME.
У READ-CHAR могут быть аргументы. Первый аргумент - это входной поток,
по-умолчанию, *standard-input*. Второй - проверка на конец ввода, по-умолчанию,
ее нет, T. Третий - значение, которое возвращается при детекции конца данных.
Пример.
(defun inp1 (&optional l x)
(loop
(setq x (read-char *standard-input* nil nil))
(cond ((symbolp x) (return (coerce (reverse l) 'string))))
(push x l)))
Можно вводить данные из строки или файла. Пример.
(defun inp2 (&optional l x)
(with-input-from-string (is "0123")
(loop
(setq x (read-char is nil nil))
(cond ((symbolp x) (return (coerce (reverse l) 'string))))
(push x l))))
(defun inp3 (&optional l x)
(with-open-file (if "filename")
(loop
(setq x (read-char if nil nil))
(cond ((symbolp x) (return (coerce (reverse l) 'string))))
(push x l))))
Можно печатать в строку, например, (write-to-string 255 :base 16) напечатает
"ff".
Функции MAPCAR, MAPLIST и APPLY
MAPCAR применяет свой первый аргумент-функцию к каждому члену второго
аргумента-списка, например,
(MAPCAR 'LENGTH '((1 2) (3 4 5)))
будет список (2 3), (MAPCAR 'ATOM '(A (A) ())) напечатает (T NIL T), а
(MAPCAR (LAMBDA (X) (* X X)) '(1 2 5)) --- (1 4 25). В общем случае
(MAPCAR 'f '(x1 x2 ... xn)) эквивалентно (LIST (f 'x1) (f 'x2) ... (f xn)).
В MAPLIST f применяется к CDR-частям этого списка, начиная с исходного
списка. Например, (MAPLIST 'LENGTH '(1 4 5)) --- (3 2 1).
APPLY применяет первый аргумент-функцию ко второму аргументу-списку.
Пример.
(SETQ F '+)
(APPLY F '(1 2 3 4)) ;10
(SETQ F '*)
(APPLY F '(1 2 3 4)) ;24
Вызов (APPLY f l) эквивалентен (EVAL (CONS f l)).
При использовании APPLY, MAPCAR и подобных средств, использующих значения
выражений как вызовы функций, естественно использовать лямбда-запись.
Пример применения функции x^3+1 к списку.
(MAPCAR (LAMBDA (X) (+ (EXPT X 3) 1)) '(1 2 3)) ;(2 9 28)
(APPLY (LAMBDA (X) (+ (EXPT X 3) 1)) '(3)) ;28
Упрощенная иерархия типов
1. Числа
1. рациональные
1. целые
1. фиксированного размера, соответствуют аппаратуре, быстрые
2. произвольной длины
2. дроби
2. вещественные
3. комплексные
2. Знаки таблицы кодировки: буквы, цифры, ...
3. Символы
4. Последовательности
1. списки
2. векторы
1. списочные
2. строки
3. битовые
5. Массивы
1. векторы
2. многомерные
6. Хэши
7. Структуры и объекты
8. Потоки ввода-вывода
9. Пакеты
Функция CHARACTERP определяет, является ли объект знаком таблицы кодировки, например,
(CHARACTERP #\P) ;T
(CHARACTER 'P) ;NIL
Векторы это списки, к компонентам которых имеется прямой доступ. Например,
(SETQ V #(1 #(A 2) Y))
присвоит V вектор из трёх компонент. Теперь к компонентам V можно обращаться
по индексу функцией AREF, нумерация с 0.
(AREF V 2) ;Y
(AREF (AREF V 1) 0) ;A
К векторам нельзя использовать CAR или CDR.
Доступ к компонентам массива
также производится при помощи AREF. Например,
(SETQ A #2A((1 2 5) (6 4 7)))
присвоит массив 2x3 A. Число после # -- это число размерностей.
(AREF A 1 2) ;7
(SETQ B (MAKE-ARRAY '(2 3 2))) ;создаст массив B размерности 2x3x2
;с компонентами NIL
Строки -- это частный случай вектора, когда все компоненты -- знаки. Строки
заключают в кавычки. Функция STRING преобразует символ лиспа в строку.
(EQL (AREF "CAT" 1) (AREF "TOAD" 2)) ;T
Для последовательностей есть ряд общих операций, например, ELT для доступа
к компоненте.
(ELT "123" 1) ;эквивалентно AREF
(ELT #(1 2 3) 1)
(ELT '(1 2 3) 1) ;эквивалентно NTH
Дополнительные средства работы с параметрами
Использование &REST позволяет использовать любое число фактических аргументов
-- параметр после этого слова получает все оставшиеся фактические аргументы
в виде списка.
(defun f (x &rest y)
(+ x (apply '+ y)))
(f 1 2 3 4 5) ;15
Параметрам можно задавать значения по умолчанию.
(defun f (&optional (x 1) (y 2) (z 3))
(+ x y z))
(f) ;6
(f 2) ;7
(f 3 4) ;10
(f 5 6 7) ;18
Использование &KEY позволяет передавать параметры по ключу -- фактические
аргументы, передаваемые по ключу, нужно предварять двоеточием и именем
аргумента.
(defun f (&key x y (z 3))
(list x y z))
(f :y 4 :x 5) ;(5 4 3)
Базовые средства функционального программирования
Функция FUNCTION предназначена для получения функционального значения
-- вместо нее можно использовать сокращение -- #'. Похожа на
SYMBOL-FUNCTION.
Пример.
(symbol-function '+) ;примитивная функция
(symbol-function 'setq) ;спецоператор
(function +) ;аналогично 1-у
#'+ ;-/-
Функция FUNCALL осуществляет вызов функции, задаваемой значением своего второго
аргумента, например, (funcall '! 5) напечатает 120.
Другой пример.
(setq b '!)
(defun b (x) (- x))
(funcall b 5); 120
(funcall 'b 5) ;-5, можно #'b
(funcall (lambda (x) (- x)) 5) ;-5
Определим лямбда-функцию для расчета и печати факториала.
(funcall ((lambda(x)(funcall x x))
(lambda(F)
(lambda(n)
(cond
((= n 0) 1)
((* n (funcall (funcall F F) (- n 1)))))))) 5) ;120
Рекурсия организуется передачей лямбда-выражения аргументом лямбда-функции.
Например, следующие выражение -- это бесконечная рекурсия.
((lambda(x) (funcall x x))
(lambda(x) (funcall x x)))
Функция LET создает среду выполнения функций -- набор локальных переменных,
например, (let ((X 2) (Y (* 3 4))) (list x y)) ;(2 12)
-- все присваивания переменным среды происходят одновременно. Функция LET*
производит присваивания последовательно. Следующий пример работает только с
LET*, а с LET генерирует ошибку.
(let* ((X 2) (Y (* 3 X))) (list x y)) ;(2 6)
Вызов (LET ((X1 E1) ... (Xn En)) O1 .. Om) эквивалентен
((LAMBDA (X1 ... Xn) O1 ... Om) E1 .. En).
(Лексическое) замыкание -- это функция с сохраняемой средой. Переменые среды
замыкания недоступны извне замыкания. Замыкания можно создавать, в частности,
с помощью LET.
(let ( (x 0) ) ; x -- переменная среды замыкания
(defun set-x (value) (setq x value))
(defun get-x () x))
(set-x 7) ;7
(get-x) ;7
x ; ошибка!
Создадим функцию-генератор замыканий с анонимной функцией-счетчиком.
(defun make-counter ()
(let ((x -1))
(lambda () (incf x))))
(setq f1 (make-counter))
(setq f2 (make-counter))
(funcall f1) ;0
(funcall f1) ;1
(funcall f1) ;2
(funcall f2) ;0
(funcall f1) ;3
Макропроцессор
При помощи DEFMACRO можно создавать макросы, такие, как например, POP и PUSH.
Синтаксис почти такой же как у DEFUN. Определим PUSH
(DEFMACRO PUSH (A P)
(LIST 'SETQ P (LIST 'CONS A P)))
Аргументы у макросов в отличие от функций не вычисляются. Макросы
вычисляются два раза. Например, вызов
(PUSH 'A V)
сначала приведёт к раскрытию макроса, к форме
(SETQ V (CONS 'A V)),
которая затем вычисляется обычным образом.
Обобщенное присваивание
Функцию SETF можно использовать вместо SETQ. Кроме того, SETF можно
использовать для присваивания значений указателям точечных пар.
(setf a '(a b c))
(setf b a)
(setf (car a) 'd)
b
(setf c '(1 2 3))
(setf (cdddr a) c)
b ;(d b c 1 2 3)
; ^ ^
;a,b c
(null (setf (cdr a) a)) ;создание циклического списка
(car a) ;a
(cadr a) ;a
(caddr a) ;a
SETF позволяет присваивать значение элементу массива.
(setq a #(a b c))
(setf (aref a 1) '(d e))
a ;#(a (d e) c)