cl.tex

\chapter{Введение в Common Lisp}
\label{ch:cl}
На вопрос о том, а надо ли оно, ответ приходит после медитации над следующими положениями:
\begin{itemize}
  \item программируемый язык программирования;
  \item код есть данные;
  \item предельно динамичный;
  \item мультипарадигменный;
  \item идеален для инкрементальной интерактивной разработки;
  \item макросы;
  \item условия и перезапуски (ошибки можно отлаживать интерактивно!);
  \item мощная объектная система, \emph{CLOS};
  \item метаобъектный протокол.
\end{itemize}

\section{Функции}
В простейшем случае функции определяются с помощью макроса \lstinline{DEFUN}. Типичное определение функции:

\begin{cllst}{}{}
(defun function-name (parameter*)
  "Optional documentation string"
  body*)
\end{cllst}

Как правило, имена функций содержат только буквы, цифры и знак ``минус''. Иногда имя может содержать даже пробельный символ.

Список параметров функции определяет переменные, которые будут использоваться для хранения аргументов, переданных при вызове функции. Различают обязательные, необязательные, множественные, и именованные (keyword) параметры.

За списком параметров может находиться строка, которая описывает назначение функции. После того, как функция определена, эта строка (строка документации) будет ассоциирована с именем функции и может быть позже получена с помощью функции \lstinline{DOCUMENTATION}.

Тело \lstinline{DEFUN} состоит из любого числа выражений CL. При вызове функции они вычисляются по порядку, и результат вычисления последнего выражения возвращается, как значение функции. Для возврата из любой точки функции может использоваться специальный оператор \lstinline{RETURN-FROM}.
\begin{cllst}{}{}
(defun verbose-sum (x y)
  "Sum any two numbers after printing a message."
  (format t "Summing ~d and ~d.~%" x y)
  (+ x y))(defun foo ()

(documentation 'verbose-sum 'function) => "Sum any two numbers after printing a message."
\end{cllst}

\subsection{Параметры функций}
Есть несколько типов параметров функций.

\subsubsection{Обязательные параметры}
Если список параметров является простым списком символов (имён переменных), то параметры называются обязательными. Когда функция вызывается, её должно быть передано ровно по одному аргументу для каждого из обязательных параметров. Каждый параметр связывается с соответствующим аргументом. Если функция вызывается с меньшим или большим количеством аргументов, чем требуется, то CL сообщит об ошибке.

\subsubsection{Необязательные параметры}
Параметры могут иметь значения по умолчанию. При вызове функции можно не использовать такие параметры.
\begin{cllst}{}{}
(defun foo (a b &optional c d) 
  (list a b c d))

(foo 1 2)     => (1 2 NIL NIL)
(foo 1 2 3)   => (1 2 3 NIL)
(foo 1 2 3 4) => (1 2 3 4)
\end{cllst}

Если значение по умолчанию не указано при определении функции, то значением по умолчанию является \lstinline{NIL}. Значение по умолчанию задаётся заменой имени параметра на список, состоящий из имени и выражения. Выражение будет вычислено при вызове функции, если вызывающий не указал значения для данного параметра.
\begin{cllst}{}{}
(defun foo (a &optional (b 10)) 
    (list a b))

(foo 1 2) => (1 2)
(foo 1)   => (1 10)
\end{cllst}

В выражениях, используемых для определения необязательных параметров, можно ссылаться на параметры, ранее встречавшиеся в списке параметров.
\begin{cllst}{}{}
(defun make-rectangle (width &optional (height width)) 
  ...)
\end{cllst}

Иногда необходимо знать, задано ли значение необязательного параметра вызывающей стороной или используется значение по умолчанию. Для этого надо добавить в список, определяющий параметр, третьим элементом имя переменной. Новая переменная будет равна \lstinline{T}, если вызывающая сторона задала значение по умолчанию при вызове, и будет равна \lstinline{NIL} в ином случае.
\begin{cllst}{}{}
(defun foo (a b &optional (c 3 c-supplied-p))
  (list a b c c-supplied-p))

(foo 1 2)   => (1 2 3 NIL)
(foo 1 2 3) => (1 2 3 T)
(foo 1 2 4) => (1 2 4 T)
\end{cllst}

\subsubsection{Остаточный (rest) параметр}
Если требуется определить функцию, которой можно передавать переменное количество аргументов, можно указать остаточный параметр. Этот параметр будет равен списку всех аргументов, которые остались после связывания обязательных и необязательных параметров.
\begin{cllst}{}{}
(defun + (&rest numbers) ...)
\end{cllst}

\subsubsection{Именованные параметры}
Для того, чтобы задать именованные параметры, необходимо после всех требуемых, необязательных и остаточных параметров, указать символ \lstinline{&key} и затем перечислить любое количество спецификаторов именованных параметров.
\begin{cllst}{}{}
(defun foo (&key a b c) 
  (list a b c))

(foo)                => (NIL NIL NIL)
(foo :a 1)           => (1 NIL NIL)
(foo :b 1)           => (NIL 1 NIL)
(foo :c 1)           => (NIL NIL 1)
(foo :a 1 :c 3)      => (1 NIL 3)
(foo :a 1 :b 2 :c 3) => (1 2 3)
(foo :a 1 :c 3 :b 2) => (1 2 3)
\end{cllst}

Также как и для необязательных параметров, для именованных параметров можно задавать выражение для вычисления значения по умолчанию и имя supplied-p-переменной. Также в варажении, которое используется для вычисления значения по умолчанию, можно ссылаться на параметры, указанные ранее.
\begin{cllst}{}{}
(defun foo (&key (a 0) (b 0 b-supplied-p) (c (+ a b)))
  (list a b c b-supplied-p))

(foo :a 1)           => (1 0 1 NIL)
(foo :b 1)           => (0 1 1 T)
(foo :b 1 :c 4)      => (0 1 4 T)
(foo :a 2 :b 1 :c 4) => (2 1 4 T)
\end{cllst}

Также если необходимо, чтобы вызывающий использовал имена аргументов, отличающиеся от имен параметров, то вы можете заменить имя параметра на список, содержащий имя, которое будет использоваться при вызове, и имя параметра.
\begin{cllst}{}{}
(defun foo (&key ((:apple a)) ((:box b) 0) ((:charlie c) 0 c-supplied-p))
  (list a b c c-supplied-p))

(foo :apple 10 :box 20 :charlie 30) => (10 20 30 T)
\end{cllst}

\subsubsection{Совместное использование различных типов параметров}
Использование всех четырех типов параметров в одной функции хоть и возможно, но встречается редко. Когда используется более одного типа параметров, они должны быть объявлены в порядке, в котором они обсуждались здесь: сначала идут обязательные параметры, затем — необязательные, потом — остаточный, и в заключение — именованные. Но обычно в функциях, которые используют несколько типов параметров, комбинируют обязательные параметры с одним из других типов параметров. Или используют вместе необязательные и остаточные параметры. Два других сочетания – необязательных или остаточных параметров с именованными параметрами — могут привести к очень удивительному поведению функции.
\begin{cllst}{}{}
(defun foo (x &optional y &key z) 
  (list x y z))

(foo 1 2 :z 3) => (1 2 3)
(foo 1)        => (1 nil nil)
(foo 1 :z 3)   => ERROR

(defun foo (&rest rest &key a b c) 
    (list rest a b c))

(foo :a 1 :b 2 :c 3)  => ((:A 1 :B 2 :C 3) 1 2 3)
\end{cllst}

\subsection{Возврат значений из функций}
Как правило, результатом вычисления функции является результат последнего вычисленного выражения в теле функции. Иногда необходимы исключения из этого правила. Для этого можно использовать специальный оператор \lstinline{RETURN-FROM}, который предназначен для немедленного возвращения любого значения из функции.
\begin{cllst}{}{}
(defun foo (n)
  (dotimes (i 10)
    (dotimes (j 10)
      (when (> (* i j) n)
        (return-from foo (list i j))))))
\end{cllst}

\subsection{Функции высшего порядка}
В CL функции являются первоклассными объектами. При определение функции с помощью \lstinline{DEFUN} происходит две вещи:
\begin{enumerate}
  \item Создаётся новый объект-функция.
  \item Создаётся новое имя, с которым ассоциирован объект-функция.
\end{enumerate}

Чтобы получить объект-функцию по имени нужно использовать \lstinline{FUNCTION} или же \lstinline{#'}.
\begin{cllst}{}{}
(defun foo (x) (* 2 x))

(function foo) => #<FUNCTION FOO>
#'foo          => #<FUNCTION FOO>
\end{cllst}

Полученный объект-функцию можно выполнить, используя \lstinline{FUNCALL} или \lstinline{APPLY}. Они отличаются тем, как они получают аргументы, которые будут переданы вызываемой функции. \lstinline{FUNCALL} — это функция, используемая, когда известно количество аргументов, которые будут переданы функции. Первым аргументом \lstinline{FUNCALL} является запускаемый объект-функция, а оставшиеся аргументы передаются данному объекту-функции при вызове.

Следующая функция демонстрирует использование \lstinline{FUNCALL}. Она принимает объект-функцию в качестве аргумента и рисует простую текстовую диаграмму значений, возвращенных переданной функцией, вызываемой для значений от \lstinline{min} до \lstinline{max} с шагом \lstinline{step}.
\begin{cllst}{}{}
(defun plot (fn min max step)
  (loop for i from min to max by step do
        (loop repeat (funcall fn i) do (format t "*"))
        (format t "~%")))

CL-USER> (plot #'exp 0 4 1/2)
*
*
**
****
*******
************
********************
*********************************
******************************************************
NIL
\end{cllst}

Первым аргументом \lstinline{APPLY} является также объект-функция, а вторым аргументом она принимает список. Затем \lstinline{APPLY} применяет объект-функцию к значениям в списке.
\begin{cllst}{}{}
(apply #'plot '(#'exp 0 4 1/2))
(apply #'plot #'exp '(0 4 1/2))
\end{cllst}

\subsection{Анонимные функции}
Анонимные функции определяются с помощью \lstinline{LAMBDA}.
\begin{cllst}{}{}
(lambda (parameters) body)

(funcall #'(lambda (x y) (+ x y)) 2 3) => 5
((lambda (x y) (+ x y)) 2 3)           => 5
\end{cllst}

\section{Переменные}
CL поддерживает два вида переменных: \emph{лексические} и \emph{динамические} (\emph{специальные}).

В CL переменные не типизированы. Переменная может содержать значения любого типа, а сами значения содержат информацию о типе, которая может быть использована для проверки типов во время выполнения.

Одной из форм, позволяющих вводить новые переменные, является \lstinline{LET}. Эта форма имеет следующий вид:
\begin{cllst}{}{}
(let (variable*)
  body-form*)
\end{cllst}
где каждая \lstinline{variable} является либо списком, состоящим из имени переменной и начального значения, либо просто именем переменной (в таком случае значение переменной равно \lstinline{NIL}).
\begin{cllst}{}{}
(let ((x 10) (y 20) z)
  (list x y z))         => (10 20 NIL)
\end{cllst}

Сначала вычисляются все выражения, результаты которых будут использоваться в качестве начальных значений. Затем создаются и инициализируются в начальные значения переменные. После чего выполняются формы из \lstinline{body-form*}.
\begin{cllst}{}{}
(defun foo (x)
  (format t "Parameter: ~a~%" x)
  (let ((x 2))
    (format t "External LET: ~a~%" x)
    (let ((x 3))
      (format t "Internal LET: ~a~%" x))
    (format t "External LET: ~a~%" x))
  (format t "Parameter: ~a~%" x))

CL-USER> (foo 1)
Parameter: 1
External LET: 2
Internal LET: 3
External LET: 2
Parameter: 1
NIL
\end{cllst}

Ещё одной связывающей формой является вариант \lstinline{LET}: \lstinline{LET*}. Различие состоит в том, что в \lstinline{LET} имена переменных могут быть использованы только в теле \lstinline{LET}, а в \lstinline{LET*} формы начальных значений могут ссылаться на переменные, введенные ранее.

\subsection{Замыкания и лексические переменные}

\begin{cllst}{}{}
(let ((count 0))
  (list
   #'(lambda () (incf count))
   #'(lambda () (decf count))
   #'(lambda () count)))


(funcall (first *count-fns*))  => 1
(funcall (first *count-fns*))  => 2
(funcall (second *count-fns*)) => 1
(funcall (third *count-fns*))  => 1
\end{cllst}

Анонимная функция называется \emph{замыканием (closure)}, потому что она замыкается вокруг привязки, созданной \lstinline{LET}. В замыканиях захватывается не значение переменной, а привязка. Поэтому замыкание может не только иметь доступ ко значению переменной, вокруг которой оно замкнуто, но и присваивать ей новые значения.

\subsection{Динамические (специальные) переменные}
CL предоставляет два способа создания динамических переменных: \lstinline{DEFVAR} и \lstinline{DEFPARAMETER}. Единственное отличие в том, что \lstinline{DEFVAR} не изменит значение уже определенной переменной, а \lstinline{DEFPARAMETER} — изменит. Обе формы принимают имя переменной, начальное значение и необязательную строку документации.

Принято, что имена динамических переменных начинаются и заканчиваются ``звёздочкой''.
\begin{cllst}{}{}
(defvar *count* 0 "Number of created widgets so far.")
*count* => 0
(defvar *count* 1)
*count* => 0

(defparameter *count* 2)
*count* => 2
\end{cllst}

Форма \lstinline{DEFVAR} может использоваться без начального значения для определения переменной без значения. Такая переменная называется \emph{несвязанной (unbound)}.

Присваивание нового значения динамической переменной в какой-либо связывающей форме приводит к тому, что весь код, который находится в теле этой связывающей форме, и код, который вызывается из кода в теле, будет видеть новое значение динамической переменной (отсюда и название).
\begin{cllst}{}{}
(defun hello-world ()
  (format *standard-output* "Hello, world!~%"))

CL-USER> (hello-world)
Hello, world!
NIL

(with-open-file (stream #p"/tmp/scream.txt" :direction :output)
  (let ((*standard-output* stream))
    (hello-world)))

CL-USER> (hello-world)
Hello, world!
NIL
\end{cllst}

В итоге \texttt{/tmp/scream.txt} содержит:
\begin{plainlst}{}{}
% cat scream.txt 
Hello, world!
\end{plainlst}

Также возможно локально объявить имя динамическим (специальным). Если в связывающей форме объявить имя специальным, то привязка, созданная для этой переменной, будет динамической, а не лексической. Другой код может локально определить имя специальным, чтобы обращаться к динамической привязке.

\subsection{Константы}
Все константы являются глобальными и определяются с помощью \lstinline{DEFCONSTANT}. Базовая форма \lstinline{DEFCONSTANT} подобна \lstinline{DEFPARAMETER}.
\begin{cllst}{}{}
(defconstant name initial-value-form [ documentation-string ])
\end{cllst}

К константе можно только обращаться. При попытке изменить константу зависит от реализации.

\subsection{Присваивание}
Чтобы присвоить новое значение переменной, следует использовать макрос \lstinline{SETF}, являющийся в CL оператором присваивания:
\begin{cllst}{}{}
(setf place value)
\end{cllst}

\lstinline{SETF} раскрывается (expand) в зависимости от того, чем является \lstinline{place}. Когда \lstinline{place} является переменной, то он раскрывается в вызов специальной формы \lstinline{SETQ}, который имеет доступ как лексическим, так и к динамическим переменным. \lstinline{SETF} возвращает последнее присвоенное значение.
\begin{cllst}{}{}
(defvar *x*)
(defvar *y*)

(setf *x* 10) => 10
(setf *x* 1 y 2) => 2
(setf *x* (setf *y* (random 10))) => 6
\end{cllst}

\subsubsection{Обобщённое присваивание}
Местом может быть не только привязки переменных. \lstinline{SETF} может присвоить значение любому месту (place). В CL можно присваивать, например, элементу списка.
\begin{cllst}{}{}
(let ((x 1))
  (setf x 10)
  x) => 10

(let ((x '(2 2 3)))
  (setf (first x) 1)
  x) => (1 2 3)

(let ((x #(2 2 3)))
  (setf (aref x 0) 1)
  x) => #(1 2 3)

(let ((x (make-hash-table)))
  (setf (gethash 'key x) 10)
  (gethash 'key x)) => 10
\end{cllst}

Новые места можно определять с помощью \lstinline{DEFSETF} и \lstinline{DEFINE-SETF-EXPANDER}.

\section{Макросы}
Макрос — определение того, как переданные S-выражения будут превращены в формы CL. С помощью макросов можно создавать новые синтаксические конструкции или даже встроенные проблемно-ориентированные языки (embedded domain-specific languages).

Когда выражение Lisp содержит вызов макроса, компилятор Lisp, вместо вычисления аргументов и передачи их в функцию, передает аргументы, не вычисляя их, в код макроса, который, в свою очередь, возвращает новое выражение на Lisp, которое затем вычисляется в месте исходного вызова макроса.

Поэтому следуем различать \emph{время раскрытия макросов} и \emph{время выполнения}, когда уже все макросы раскрыты и выполняется обычный код. Код, работающий во время раскрытия макросов, запускается в окружении, сильно отличающимся от окружения кода, работающего во время выполнения. А именно: во время раскрытия макросов не существует способа получить доступ к данным, которые будут существовать во время выполнения. Код, работающий во время раскрытия макросов, может работать только с данными, являющимися неотъемлемой частью исходного кода.

Предположим, что макрос \lstinline{WHEN} определен следующим образом:
\begin{cllst}{}{}
(defmacro when (condition &rest body)
  `(if ,condition (progn ,@body)))
\end{cllst}

И допустим, что имеется следующая функция \lstinline{FOO}:
\begin{cllst}{}{}
(defun foo (x)
  (when (> x 10) (print 'big)))
\end{cllst}

В этом случае, параметр \lstinline{condition} будет связан с формой \lstinline{(> x 10)}, а форма \lstinline{(print 'big)} будет собрана в список, который станет значением параметра \lstinline{body}. После раскрытия получится следующий код:
\begin{cllst}{}{}
(if (> x 10) (progn (print 'big)))
\end{cllst}

Синтаксис \lstinline{DEFMACRO} выглядит так:
\begin{cllst}{}{}
(defmacro name (parameter*)
  "Optional documentation string."
  body-form*)
\end{cllst}

\subsection{Макропараметры}
Список параметров макроса является списком \emph{деструктурируемых} параметров. Внутри списка деструктурируемых параметров имя параметра может быть заменено вложенным списком параметров. Параметры в таком списке будут получать свои значения из элементов переданного аргумента-списка. Список деструктурируемых параметров также предоставляет проверку ошибок.

Другой особенностью списка параметров макросов является то, что вы можете использовать \lstinline{&body} как синоним \lstinline{&rest}. Семантически \lstinline{&body} и \lstinline{&rest} эквивалентны.
\begin{cllst}{Пример макроса}{}
(defun primep (number)
  (when (> number 1)
    (loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))
 
(defun next-prime (number)
  (loop for n from number when (primep n) return n))

(defmacro do-primes ((var start end) &body body)
  `(do ((,var (next-prime ,start) (next-prime (1+ ,var))))
       ((> ,var ,end))
     ,@body))
\end{cllst}

\subsection{Раскрытие}
Выражения квазицитирования подобны выражениям цитирования за исключением того, что можно ``раскавычить'' (вычислять) определенные подвыражения, предваряя их запятой, за которой возможно следует знак ``at'' (\lstinline{@}). Без этого знака запятая вычисляет и влючает как есть значение следующего за ней подвыражения. Со знаком ``at'' значение, которое должно быть списком, ``вклеивается'' в обрамляющий список.

По сути квазицитирование — это удобный синтаксис для написания кода, который генерирует списки. Когда процедура чтения считывает выражение квазицитирования, она преобразует его в код, который генерирует соответствующую списковую структуру.

\begin{table}[h!]
  \caption{Примеры квазицитирования}
  \begin{center}
    \begin{tabular}{lll}
      \toprule
      Квазицитирования & Эквивалентный код & Результат \\
      \midrule
      \texttt{`(a (+ 1 2) c)} & \texttt{(list 'a '(+ 1 2) 'c)} & \texttt{(a (+ 1 2) c)} \\
      \texttt{`(a ,(+ 1 2) c)} & \texttt{(list 'a (+ 1 2) 'c)} & \texttt{(a 3 c)} \\
      \texttt{`(a (list 1 2) c)} & \texttt{(list 'a '(list 1 2) 'c)} & \texttt{(a (list 1 2) c)} \\
      \texttt{`(a ,(list 1 2) c)} & \texttt{(list 'a (list 1 2) 'c)} & \texttt{(a (1 2) c)} \\
      \texttt{`(a ,@(list 1 2))} & \texttt{(append (list 'a) (list 1 2))} & \texttt{(a 1 2 c)} \\
      \bottomrule
    \end{tabular}
  \end{center}
\end{table}

Для проверки раскрытия макроса можно использовать две функции: \lstinline{MACROEXPAND-1} и \lstinline{MACROEXPAND}. Функция \lstinline{MACROEXPAND-1} получает любое выражение в качестве аргумента и возвращает результат одного шага раскрытия макроса. Функция \lstinline{MACROEXPAND} продолжает раскрытие результата пока первый элемент получаемого раскрытия является именем макроса.

\subsection{Устранение протечек}
Внутренние детали реализации макроса могут ``протекать'' тремя путями.

Предположим, что макрос \lstinline{DO-PRIMES} вызван с выражением \lstinline{(random 100)}:
\begin{cllst}{}{}
(do-primes (p 0 (random 100))
  (format t "~d " p))
\end{cllst}

Если воспользоваться функцией \lstinline{MACROEXPAND-1}, то можно заметить, что выражение \lstinline{(random 100)} будет вычисляться при каждой проверке условия в макросе \lstinline{DO}:
\begin{cllst}{}{}
CL-USER> (macroexpand-1 '(do-primes (p 0 (random 100)) (format t "~d " p)))
(DO ((P (NEXT-PRIME 0) (NEXT-PRIME (1+ P))))
    ((> P (RANDOM 100)))
  (FORMAT T "~d " P))
T
\end{cllst}

Исправить это поведение можно вычислением \lstinline{end} единожды и сохранением результата вычисления.
\begin{cllst}{}{}
(defmacro do-primes ((var start end) &body body)
  `(do ((ending-value ,end)
        (,var (next-prime ,start) (next-prime (1+ ,var))))
       ((> ,var ending-value))
     ,@body))
\end{cllst}

Но данное исправление одной проблемы вводит две других.
Так как переменные цикла \lstinline{DO} инициализируются в том порядке, в каком они определены в тексте, то при раскрытии макроса выражение, переданное как \lstinline{end}, будет вычислено перед выражением, переданным как \lstinline{start}. Это устраняется изменением порядка определения двух переменных.
\begin{cllst}{}{}
(defmacro do-primes ((var start end) &body body)
  `(do ((,var (next-prime ,start) (next-prime (1+ ,var)))
        (ending-value ,end))
       ((> ,var ending-value))
     ,@body))
\end{cllst}

Последняя проблема связана с именем переменной \lstinline{ending-value}. Проблема в том, что это имя может быть использовано во внешнем пользовательском кодом. Следующий вызов do-primes не работает корректно из-за данной ``протечки'':
\begin{cllst}{}{}
(do-primes (ending-value 0 10)
  (print ending-value))
\end{cllst}

С помощью \lstinline{MACROEXPAND-1} легко отыскивается причина неверного поведения:
\begin{cllst}{}{}
(do ((ending-value (next-prime 0) (next-prime (1+ ending-value)))
     (ending-value 10))
    ((> ending-value ending-value))
  (print ending-value))
\end{cllst}

Для устранения этой проблемы нужна возможность создавать уникальный символ. Функция \lstinline{GENSYM} возвращает уникальный символ при каждом вызове. Возвращённый символ не интернируется в какой-либо пакет. Код, использующий \lstinline{GENSYM}, не должен быть частью раскрытия.
\begin{cllst}{}{}
(defmacro do-primes ((var start end) &body body)
  (let ((ending-value-name (gensym)))
    `(do ((,var (next-prime ,start) (next-prime (1+ ,var)))
          (,ending-value-name ,end))
         ((> ,var ,ending-value-name))
       ,@body)))
\end{cllst}

Теперь вышеприведённое использование макроса будет раскрыто в подобное:
\begin{cllst}{}{}
(do ((ending-value (next-prime 0) (next-prime (1+ ending-value)))
     (#:g2141 10))
    ((> ending-value #:g2141))
  (print ending-value))
\end{cllst}

\subsection{Примеры макросов}
Было бы неплохо писать код вроде следующего вместо использования \lstinline{GENSYM}:
\begin{cllst}{}{}
(defmacro do-primes ((var start end) &body body)
  (with-gensyms (ending-value-name)
    `(do ((,var (next-prime ,start) (next-prime (1+ ,var)))
          (,ending-value-name ,end))
         ((> ,var ,ending-value-name))
       ,@body)))
\end{cllst}
и получить \lstinline{DO-PRIMES}, эквивалентный предыдущей версии.
\begin{cllst}{}{}
(defmacro with-gensyms ((&rest names) &body body)
  `(let ,(loop for n in names collect `(,n (gensym)))
     ,@body))
\end{cllst}

Можно посмотреть, как раскрывается \lstinline{loop}-часть:
\begin{cllst}{}{}
CL-USER> (loop for n in '(a b c) collect `(,n (gensym)))
((A (GENSYM)) (B (GENSYM)) (C (GENSYM)))
\end{cllst}

\section{Примитивные типы данных}
\subsection{Числа}
CL поддерживает несколько числовых типов:
\begin{itemize}
  \item целые числа, максимальная величина которых аппаратно-зависима;
  \item целые числа произвольной величины;
  \item числа с плавающей точкой;
  \item дроби;
  \item комплексные числа.
\end{itemize}

\subsubsection{Запись}
Примеры записи и печати рациональных чисел:
\begin{cllst}{}{}
CL-USER> (list +1 -1 2/1 3/2 6/4 #xA #b01001 #b1010/1011 #o777 #36rABFG 1.)
(1 -1 2 3/2 3/2 10 9 10/11 511 481372 1)
\end{cllst}{}

Во время чтения дроби сокращаются, если это возможно. Как видно из примера, возможна запись чисел с основанием отличным от $10$. Если числу предшествует \lstinline{#B} или \lstinline{#b}, то число считывается как двоичное. Строки \lstinline{#O} или \lstinline{#o} используются для восьмеричных чисел, а \lstinline{#X} или \lstinline{#x} используются для шестнадцатеричных. Возможно записывать числа в системах с другими основаниями (от 2 до 36) с указанием префикса \lstinline{#nR}, где \lstinline{n} — основание (всегда записывается в десятичном виде). В качестве дополнительных ``цифр'' используются буквы A-Z или a-z.

Примеры записи и печати чисел с плавающей точкой:
\begin{cllst}{}{}
CL-USER> (list 1.0 1e0 1d0 0.1 .1 1e-3)
(1.0 1.0 1.0d0 0.1 0.1 0.001)
\end{cllst}

В CL есть четыре подтипа чисел с плавающей точкой: \lstinline{short}, \lstinline{single}, \lstinline{double} и \lstinline{long}. Количество бит, отведённых для представления значений каждого типа, зависит от реализации и аппаратной платформы. Маркеры экспоненты: \lstinline{s}, \lstinline{f}, \lstinline{d,} \lstinline{l} обозначают использование \lstinline{short}, \lstinline{single}, \lstinline{double} и \lstinline{long}. Буква \lstinline{e} указывает, что должно использоваться представление по умолчанию.

Примеры записи и печати комплексных чисел:
\begin{cllst}{}{}
CL-USER> (list #c(2 1) #c(2/3 3/4) #c(2 1.0) #c(2.0 1.0d0)
               #c(1/2 1.0) #c(3 0) #c(3.0 0.0) #c(1/2 0) #c(-6/3 0))
s
(#C(2 1) #C(2/3 3/4) #C(2.0 1.0) #C(2.0d0 1.0d0)
 #C(0.5 1.0) 3 #C(3.0 0.0) 1/2 -2)
\end{cllst}

Синтаксис: префикс \lstinline{#C} или \lstinline{#c}, за которым следует список из двух чисел, представляющих реальную и мнимую часть комплексного числа.

\subsubsection{Математические операции}
\begin{cllst}{}{}
(+)        => 0      (+ 1 2)    => 3
(+ 1 2 3)  => 6      (- 5 4)    => 1
(- 2)      => -2     (- 10 3 5) => 2
(*)        => 1      (* 2 3 4)  => 24
(/ 10 5 2) => 1      (/ 2 3)    => 2/3

(+ #c(1 2) 3) => #c(4 2)
\end{cllst}

В CL есть четыре вида функций для усечения и округления для вещественных чисел (рациональных или с плавающей точкой) в целые числа:
\begin{enumerate}
  \item \lstinline{FLOOR} усекает число в сторону отрицательной бесконечности, возвращая наибольшее целое, меньшее или равное аргументу.
  \item \lstinline{CEILING} усекает число в сторону положительной бесконечности, возвращая наименьшее целое, большее или равное аргументу.
  \item \lstinline{TRUNCATE} усекает число в сторону нуля, ведя себя как \lstinline{FLOOR} для положительных аргументов, и как \lstinline{CEILING} для отрицательных.
  \item \lstinline{ROUND} округляет число до ближайшего целого. Если аргумент находится ровно между двумя целыми числами, то округление происходит в сторону ближайшего четного числа.
\end{enumerate}

Функция \lstinline{MOD} и \lstinline{REM} возвращают модуль и остаток деления с усечением чисел. Эти две функции соотносятся с \lstinline{FLOOR} и \lstinline{TRUNCATE} следующим образом:
\begin{cllst}{}{}
(+ (* (floor    (/ x y)) y) (mod x y)) == x
(+ (* (truncate (/ x y)) y) (rem x y)) == x
\end{cllst}

\subsubsection{Сравнение чисел}
Функция \lstinline{=} является предикатом для проверки равенства чисел, который игнорирует разницу в типах, то есть сравнивает математически. Функции \lstinline{<}, \lstinline{>}, \lstinline{<=} и \lstinline{>=} сравнивают рациональные числа и числа с плавающей точкой.
\begin{cllst}{}{}
(= 1 1.0 #c(1.0 0.0) #c(1 0))  => T

(/= 1 1)     => NIL    (/= 1 2)       => T
(/= 1 2 3)   => T      (/= 1 2 3 1.0) => NIL
(<= 2 3 3 4) => T      (<= 2 3 4 3)   => NIL
\end{cllst}

Другими часто используемыми функциями и предикатами являются: \lstinline{ZEROP}, \lstinline{MINUSP}, \lstinline{PLUSP}, \lstinline{EVENP}, \lstinline{ODDP}, \lstinline{MIN} и \lstinline{MAX}.

\subsection{Знаки}
В CL знаки являются отдельным типом объектов, а не числами. Синтаксис чтения: префикс \lstinline{#\}, за которым следует нужный знак. После \lstinline{#\} может использоваться любой знак. Пробел и другие аналогичные знаки можно записывать другим способом: вместа знака за \lstinline{#\} следует название знака. Список поддерживаемых имен зависит от набора знаков и реализации Lisp, но все реализации поддерживают имена \lstinline{Space} и \lstinline{Newline}. Другими распространёнными, но не стандартными именами являются \lstinline{Tab}, \lstinline{Page}, \lstinline{Rubout}, \lstinline{Linefeed}, \lstinline{Return} и \lstinline{Backspace}.

Для сравнения знаков, не учитывая их регистр, следует использовать функции: \lstinline{CHAR=}, \lstinline{CHAR=/}, \lstinline{CHAR<}, \lstinline{CHAR>}, \lstinline{CHAR<=} и \lstinline{CHAR>=}. Для сравнения знаков, учитывая их регистр, следует использовать функции: \lstinline{CHAR-EQUAL}, \lstinline{CHAR-NOT-EQUAL}, \lstinline{CHAR-LESSP}, \lstinline{CHAR-GREATERP}, \lstinline{CHAR-NOT-GREATERP} и \lstinline{CHAR-NOT-LESSP}.

\subsection{Строки}
Строка является одномерным массивом знаков. Строки записываются, заключенными в двойные кавычки. Можно включить в строку любой знак, поддерживаемый набором знаков, за исключением двойной кавычки (\lstinline{"}) и обратного слеша (\lstinline{\}). Эти два знака необходимо экранировать.

Для сравнения строк, не учитывая их регистр, следует использовать функции: \lstinline{STRING=}, \lstinline{STRING=/}, \lstinline{STRING<}, \lstinline{STRING>}, \lstinline{STRING<=} и \lstinline{STRING>=}. Для сравнения строк, учитывая их регистр, следует использовать функции: \lstinline{STRING-EQUAL}, \lstinline{STRING-NOT-EQUAL}, \lstinline{STRING-LESSP}, \lstinline{STRING-GREATERP}, \lstinline{STRING-NOT-GREATERP} и \lstinline{STRING-NOT-LESSP}. Эти функции могут сравнивать только две строки, в отличии от аналогов для чисел.

Каждая из этих функций имеет четыре именованных параметра: \lstinline{:start1}, \lstinline{:end1}, \lstinline{:start2} и \lstinline{:end2}.
\begin{cllst}{}{}
(string= "foobarbaz" "quuxbarfoo" :start1 3 :end1 6 :start2 4 :end2 7) => T
\end{cllst}

\section{Коллекции}
В CL есть два основных вида коллекций: последовательности и хеш-таблицы. Последовательности в свою очередь подразделяются на: векторы, списки и строки. В этой главе будут рассматриваться в основном векторы, но все рассматриваемые здесь функции для работы с последовательностями, естественно, применимы к спискам и строкам.

\subsection{Векторы и массивы}
Векторы являются последовательностью с доступом по целочисленному индексу. Векторы могут иметь фиксированный размер либо же изменяемый. Создать вектор можно функцией \lstinline{VECTOR} или же специальным синтаксисом \lstinline{#(...)}. Однако, что произойдёт в результате изменения вектора, созданного вторым способом, стандартом не определено.
\begin{cllst}{}{}
(vector)     => #()
(vector 1)   => #(1)
(vector 1 2) => #(1 2)
\end{cllst}

Функцией \lstinline{MAKE-ARRAY} можно создавать массивы любой размерности. Обязательным аргументом является список размерностей либо число, если массив одномерен, то есть является вектором. Без других аргументов создатся массив с неициализированными элементами. Поведение при доступе к неициализированным элементам неопределено. Используя параметр \lstinline{:initial-element} можно создать массив, проинициализированный определённым значением.
\begin{cllst}{}{}
(make-array 5 :initial-element nil) => #(NIL NIL NIL NIL NIL)
\end{cllst}

Размер вектора хранится в \emph{указателе заполнения (fill pointer)}. Указать его начальное значение можно параметром \lstinline{:fill-pointer}.
\begin{cllst}{}{}
(make-array 5 :fill-pointer 0) => #()
(make-array 5 :fill-pointer 3) => #(0 0 0)
(make-array 5 :fill-pointer 3 :initial-element nil) => #(NIL NIL NIL)
\end{cllst}

Создать массив изменяемым можно параметром \lstinline{:adjustable}. Следующий массив может не имеет элементов, памяти выделено изначально под 5 элементов, но добавлять в массив можно больше пяти элементов.
\begin{cllst}{}{}
(make-array 5 :fill-pointer 0 :adjustable t) ==> #()
\end{cllst}

Примеры работы с векторами различных свойств:
\begin{cllst}{}{}
(defparameter *array* (make-array 2 :fill-pointer 0))
(vector-push 0 *array*) => 0
(vector-push 1 *array*) => 1
(vector-push 2 *array*) => NIL
*array* => #(0 1)

(defparameter *array*
  (make-array 2 :fill-pointer 1 :initial-element 0 :adjustable t))
(vector-push 1 *array*) => 1
(vector-push 2 *array*) => NIL
*array* => #(0 1)
(vector-push-extend 2 *array*) => 2
*array* => #(0 1 2)
\end{cllst}

Все созданные массивы и векторы могут хранить элементы любого типа. Но можно создавать массивы, которые хранят только элементы определённого типа, параметром \lstinline{:element-type}.
\begin{cllst}{}{}
(make-array 5 :fill-pointer 0 :adjustable t :element-type 'character) => ""
(make-array 3 :initial-contents '(0 1 0) :element-type 'bit) => #*010
\end{cllst}

Последний вектор является битовым.

\subsection{Функции для последовательностей}
\begin{table}[h!]
  \caption{Описание функций}
  \begin{center}
    \begin{tabular}{lp{5cm}p{6.5cm}}
      \toprule
      Название & Обязательные аргументы & Результат \\
      \midrule
      \texttt{COUNT} & Объект и последовательность & Число вхождений в последовательности \\
      \texttt{FIND} & Объект и последовательность & Объект или \texttt{NIL} \\
      \texttt{POSITION} & Объект и последовательность & Индекс ячейки в последовательности или \texttt{NIL} \\
      \texttt{REMOVE} & Удаляемый объект и последовательность & Последовательность, из которой удалены указанные объекты \\
      \texttt{SUBSTITUTE} & Новый объект, заменяемый объект и последовательность & Последовательность, в которой указанные объекты заменены на новые \\
      \bottomrule
    \end{tabular}
  \end{center}
\end{table}

\begin{table}[h!]
  \caption{Описание некоторых именованных параметров}
  \begin{center}
    \begin{tabular}{lp{8.5cm}p{2cm}}
      \toprule
      Параметр & Описание & Значение по умолчанию \\
      \midrule
      \texttt{:test} & Функция двух аргументов, используемая для сравнения элементов (или значений, извлеченных функцией \texttt{:key}) с указанным объектом. & \texttt{EQL} \\
      \texttt{:key} & Функция одного аргумента, используемая для извлечения значения из элемента последовательности. \texttt{NIL} указывает на использование самого элемента. & \texttt{NIL} \\
      \texttt{:start} & Начальный индекс (включительно) обрабатываемой последовательности. & $0$ \\
      \texttt{:end} & Конечный индекс $(n - 1)$ обрабатываемой последовательности. \texttt{NIL} указывает на конец последовательности. & \texttt{NIL} \\
      \texttt{:from-end} & Если имеет истинное значение, то последовательность будет обрабатываться в обратном порядке. & \texttt{NIL} \\
      \texttt{:count} & Число, указывающее количество удаляемых или заменяемых элементов, или \texttt{NIL} для всех элементов (только для \texttt{REMOVE} и \texttt{SUBSTITUTE}). & \texttt{NIL} \\
      \bottomrule
    \end{tabular}
  \end{center}
\end{table}

\begin{cllst}{Примеры использования}{}
(length #(1 2 3))                      => 3
(elt 1 #(1 2 3))                       => 2
(count 1 #(1 2 1 2 3 1 2 3 4))         => 3
(remove 1 #(1 2 1 2 3 1 2 3 4))        => #(2 2 3 2 3 4)
(remove 1 '(1 2 1 2 3 1 2 3 4))        => (2 2 3 2 3 4)
(remove #\a "foobarbaz")               => "foobrbz"
(substitute 10 1 #(1 2 1 2 3 1 2 3 4)) => #(10 2 10 2 3 10 2 3 4)
(substitute 10 1 '(1 2 1 2 3 1 2 3 4)) => (10 2 10 2 3 10 2 3 4)
(substitute #\x #\b "foobarbaz")       => "fooxarxaz"
(find 1 #(1 2 1 2 3 1 2 3 4))          => 1
(find 10 #(1 2 1 2 3 1 2 3 4))         => NIL
(position 2 #(1 2 1 2 3 1 2 3 4))      => 1
(position 9 #(1 2 1 2 3 1 2 3 4))      => NIL

(count "foo" #("foo" "bar" "baz") :test #'string=)    => 1
(find 'c #((a 10) (b 20) (c 30) (d 40)) :key #'first) => (C 30)

(find 'a #((a 10) (b 20) (a 30) (b 40)) :key #'first)             => (A 10)
(find 'a #((a 10) (b 20) (a 30) (b 40)) :key #'first :from-end t) => (A 30)

(remove #\a "foobarbaz" :count 1)             => "foobrbaz"
(remove #\a "foobarbaz" :count 1 :from-end t) => "foobarbz"
\end{cllst}

\subsubsection{ФВП для последовательностей}
CL также предоставляет два набора функций высшего порядка, которые вместо аргумента, используемого для сравнения, получают функцию, которая вызывается для каждого элемента последовательности. Первый набор функций имеет те же имена, что и функции из базового набора, но с добавлением суффикса \lstinline{-IF}. Эти функции подсчитывают, ищут, удаляют и заменяют элементы, для которых аргумент-функция возвращает истинное значение. Другой набор функций отличается тем, что использует суффикс \lstinline{-IF-NOT}, и выполняет те же операции над элементами, для которых функция не возвращает истинного значения.
\begin{cllst}{Примеры}{}
(count-if #'evenp #(1 2 3 4 5))         => 2
(count-if-not #'evenp #(1 2 3 4 5))     => 3
(position-if #'digit-char-p "abcd0001") => 4

(remove-if-not #'(lambda (x) (char= (elt x 0) #\f))
  #("foo" "bar" "baz" "foom")) => #("foo" "foom")

(count-if #'evenp #((1 a) (2 b) (3 c) (4 d) (5 e)) :key #'first)     => 2
(count-if-not #'evenp #((1 a) (2 b) (3 c) (4 d) (5 e)) :key #'first) => 3

(remove-if-not #'alpha-char-p
  #("foo" "bar" "1baz") :key #'(lambda (x) (elt x 0))) => #("foo" "bar")
\end{cllst}

\subsection{Хеш-таблицы}
Хеш-таблицы создаются функцией с говорящим именем \lstinline{MAKE-HASH-TABLE}. Имеет среди прочих один аргумент: \lstinline{:test}. С помощью него можно указать одну из четырёх функций: \lstinline{EQ}, \lstinline{EQL}, \lstinline{EQUAL}, \lstinline{EQUALP}, используемую для сравнения ключей.

Функция \lstinline{GETHASH} обеспечивает доступ к элементам хеш-таблицы.
\begin{cllst}{}{}
(defparameter *h* (make-hash-table))
(gethash 'foo *h*) => NIL
(setf (gethash 'foo *h*) 'quux)
(gethash 'foo *h*) => QUUX
\end{cllst}

\lstinline{GETHASH} возвращает на самом деле два значения. Получить их можно используя макрос \lstinline{MULTIPLE-VALUE-BIND}.
\begin{cllst}{}{}
(defun show-value (key hash-table)
  (multiple-value-bind (value present) (gethash key hash-table)
    (if present
      (format nil "~a is present" value)
      (format nil "~a is not present" value))))
\end{cllst}

\begin{cllst}{Функции для хеш-таблиц}{}
(defparameter *h* (make-hash-table))
(setf (gethash 'key1 *h*) 'value1)
(setf (gethash 'key2 *h*) 'value2)

CL-USER> (maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *h*)
KEY1 => VALUE1
KEY2 => VALUE2
NIL

(loop for k being the hash-keys in *h* using (hash-value v)
  do (format t "~a => ~a~%" k v))
\end{cllst}

\section{Списки}
Использование списков в CL очень часто, так как эта структура данных используется для представления, преобразования и порождения кода в макросах. Но не только — об этом следом.

\subsection{Cons-ячейки}
Списки построены на основе \emph{cons-ячеек}. Cons-ячейка (от функции \lstinline{CONS}, используемой для их создания) — это всего лишь пара объектов. Таким образом список состоит из пар, первым элементом которых являются элементы (значения) списка, а второй элемент указывает на последующую ячейку, если таковая присутствует.
\begin{cllst}{}{}
(cons 1 nil)                   => (1)
(cons 1 (cons 2 nil))          => (1 2)
(cons 1 (cons 2 (cons 3 nil))) => (1 2 3)
\end{cllst}

Для доступа к первому и второму элементам пары используются функции \lstinline{CAR} и \lstinline{CDR}, соответственно.
\begin{cllst}{}{}
(defparameter *cons* (cons 1 2))
(car *cons*)           => 1
(cdr *cons*)           => 2
(setf (car *cons*) 10) => 10
*cons*                 => (10 . 2)
(setf (cdr *cons*) 20) => 20
*cons*                 => (10 . 20)
\end{cllst}

У \lstinline{CAR} и \lstinline{CDR} есть синонимы: \lstinline{FIRST} и \lstinline{REST}.

\subsection{Функции для списков}

Для создания списков есть функция \lstinline{LIST}. Функция \lstinline{APPEND} склеивает списки, при этом все списки копируются кроме последнего.
\begin{cllst}{}{}
(defparameter *list-1* (list 1 2))
(defparameter *list-2* (list 3 4))
(defparameter *list-3* (append *list-1* *list-2*))

(setf (first *list-2*) 0)
*list-2*  => (0 4)
*list-3*  => (1 2 0 4)
\end{cllst}

Функция \lstinline{NCONC} склеивает списки, не копируя их, а изменяя последние cons-ячейки всех списков, кроме последнего.

В CL есть функции от \lstinline{SECOND} до \lstinline{TENTH}, извлекающие соответствующие элементы списка. Более общая функция \lstinline{NTH} принимает два аргумента: индекс и список, и возвращает $n$-ый (начиная с нуля) элемент списка. Также существует функция \lstinline{NTHCDR}, принимающая индекс и список и возвращающая результат $n$-кратного применения \lstinline{REST} к списку.

28 составных \lstinline{CAR}/\lstinline{CDR} функций составляют ещё одно семейство функций. Имя каждой функции получается подстановкой до 4 букв \lstinline{A} или \lstinline{D} между \lstinline{C} и \lstinline{R}. Каждая \lstinline{A} представляет вызов \lstinline{CAR}, а каждая \lstinline{D} — \lstinline{CDR}.

\begin{table}[h!]
  \caption{Другие функции для работы со списками}
  \begin{center}
    \begin{tabular}{lp{11.5cm}}
      \toprule
      Имя & Описание \\
      \midrule
      \texttt{LAST} & Возвращает последнюю cons-ячейку в списке. Если вызывается с целочисленным аргументом $n$, возвращает n ячеек. \\
      \texttt{BUTLAST} & Возвращает копию списка без последней cons-ячейки. Если вызывается с целочисленным аргументом $n$, исключает последние $n$ ячеек. \\
      \texttt{NBUTLAST} & Похожа на \texttt{BUTLAST}, но изменяет переданный список, не имеет строго заданных побочных эффектов. \\
      \texttt{LDIFF} & Возвращает копию списка до заданной cons-ячейки. \\
      \texttt{TAILP} & Возвращает \texttt{T}, если переданный объект является cons-ячейкой, которая является частью списка. \\
      \texttt{LIST*} & Строит список, содержащий все переданные аргументы кроме последнего, после этого присваивает \texttt{CDR} последней cons-ячейки списка последний аргумент, то есть смесь \texttt{LIST} и \texttt{APPEND}. \\
      \texttt{MAKE-LIST} & Строит список из $n$ элементов. Начальные элементы списка — \texttt{NIL} или значение заданное параметром \texttt{:initial-element}. \\
      \texttt{REVAPPEND} & Комбинация \texttt{REVERSE} и \texttt{APPEND}: инвертирует первый аргумент, как \texttt{REVERSE} и добавляет второй аргумент. Не имеет строго заданных побочных эффектов. \\
      \texttt{NRECONC} & Аналог предыдущей функции; инвертирует первый аргумент, как \texttt{NREVERSE} и добавляет второй аргумент. Не имеет строгих побочных эффектов. \\
      \texttt{CONSP} & Проверяет, является ли объект cons-ячейкой. \\
      \texttt{ATOM} & Проверяет, является ли объект не cons-ячейкой. \\
      \texttt{LISTP} & Проверяет, является ли объект cons-ячейкой или \texttt{NIL} \\
      \texttt{NULL} & Проверяет, является ли объект \texttt{NIL}. \\
      \bottomrule
    \end{tabular}
  \end{center}
\end{table}

Просто перечисление функций с говорящими за себя именами: \lstinline{REVERSE}, \lstinline{NREVERSE}, \lstinline{PUSH}, \lstinline{POP}, \lstinline{PUSHNEW}, \lstinline{DELETE}, \lstinline{DELETE-IF}, \lstinline{DELETE-IF-NOT}, \lstinline{DELETE-DUPLICATED}, \lstinline{NSUBSTITUTE}, \lstinline{NSUBSTITUTE-IF} и \lstinline{NSUBSTITUTE-IF-NOT}.

\subsection{Отображение}
Для отображения можно использовать функцию \lstinline{MAP}, так как она работает с любой последовательностью. Специфичными для списков являются функции \lstinline{MAPCAR}, \lstinline{MAPLIST}, \lstinline{MAPCAN}, \lstinline{MAPCON}, \lstinline{MAPC} и \lstinline{MAPL}.
\begin{cllst}{}{}
(mapcar #'(lambda (x) (* 2 x)) (list 1 2 3)) => (2 4 6)
(mapcar #'+ (list 1 2 3) (list 10 20 30))    => (11 22 33)

(maplist #'(lambda (x) x) (list 1 2 3)) => ((1 2 3) (2 3) (3))

(mapcan #'(lambda (x) (and (numberp x) (list x)))
          '(a 1 b c 3 4 d 5))
=>  (1 3 4 5)
(mapcon #'list '(1 2 3 4)) =>  ((1 2 3 4) (2 3 4) (3 4) (4))
\end{cllst}

\subsection{Списки как деревья}
Так как списки могут содержать любые значения, а ,следовательно, и списки, то с их помощью можно представлять любого вида деревья. Например, \lstinline{'((nil 1 nil) 2 (nil 3 nil))} представляет собой бинарное дерево поиска, в которое были вставлены последовательно числа $2$, $1$ и $3$.

Для работы с такими деревьями в CL есть несколько специальных функций. Одна из них — \lstinline{COPY-TREE}, которая, в отличие от \lstinline{COPY-LIST}, копирует списки не только вдоль, но и вглубь. Функция \lstinline{TREE-EQUAL} проверяет, равны ли два дерева, что подразумевает одинаковость их форм и равенство содержащихся в них значений.

Функция \lstinline{SUBST} заменяет один элемент дерева другим. Подобное делают функции \lstinline{SUBST-IF}, \lstinline{NSUBST} и \lstinline{NSUBST-IF} с очевидными особенностями.
\begin{cllst}{}{}
(subst 10 1 '(1 2 (3 2 1) ((1 1) (2 2)))) => (10 2 (3 2 10) ((10 10) (2 2)))
\end{cllst}

\begin{cllst}{Обход дерева}{}
(defun preorder (node f)
  (when node
    (funcall f (first node))
    (preorder (second node) f)
    (preorder (third node)  f)))

(defun inorder (node f)
  (when node
    (inorder (second node) f)
    (funcall f (first node))
    (inorder (third node)  f)))

(defun postorder (node f)
  (when node
    (postorder (second node) f)
    (postorder (third node)  f)
    (funcall f (first node))))

(defun level-order (node f)
  (loop with level = (list node)
        while level
        do
    (setf level (loop for node in level
                      when node
                        do (funcall f (first node))
                        and collect (second node)
                        and collect (third node)))))

(defparameter *tree* '(1 (2 (4 (7))
                            (5))
                         (3 (6 (8)
                               (9)))))

(defun show (traversal-function)
  (format t "~&~(~A~):~12,0T" traversal-function)
  (funcall traversal-function *tree* (lambda (value) (format t " ~A" value))))

(map nil #'show '(preorder inorder postorder level-order))
\end{cllst}
\begin{plainlst}{}{}
preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 2 5 1 8 6 9 3
level-order: 1 2 3 4 5 6 7 8 9
\end{plainlst}

\subsection{Списки как множества}
Реализация множеств в CL — это набор функцией, которые производят теоретико-множественные операции над списками. Для добавления элемента в множество есть функции \lstinline{ADJOIN} и \lstinline{PUSHNEW}.
\begin{cllst}{}{}
(defparameter *set* ())
(adjoin 1 *set*)
*set* => NIL

(setf *set* (adjoin 1 *set*))
(pushnew 2 *set*)
*set* => (2 1)
(pushnew 2 *set*)
*set* => (2 1)
\end{cllst}

Функции \lstinline{MEMBER}, \lstinline{MEMBER-IF} и \lstinline{MEMBER-IF-NOT} проверяют, принадлежит ли элемент множеству. Вместо того, чтобы вернуть элемент, когда он присутствует в множестве, они возвращают cons-ячейку, содержащую элемент. Если искомый элемент отсутствует в списке, все три функции возвращают \lstinline{NIL}.

Функции \lstinline{INTERSECTION}, \lstinline{UNION}, \lstinline{SET-DIFFERENCE} и \lstinline{SET-DIFFERENCE-OR-EXCLUSIVE} делают то, что следует из их названий. Все эти функции имеют свои парные функции, начинающиеся с \lstinline{N}, которые изменяют переданные множества.

Функция \lstinline{SUBSETP} проверяет, является ли одно множество подмножеством другого.

\subsection{Ассоциативные списки}
Ассоциативный список — это структура данных, которая отображает ключи на значения, и наоборот. Ассоциативные списки также поддерживают добавление пар ключ/значение, которые скрывают существующие таким образом, что вновь добавленные пары могут быть позже удалены, и первоначальные пары снова станут видимы.

Технически, ассоциативный список является списком, элементами которого являются cons-ячейки.
\begin{cllst}{}{}
((a . 1) (b . 2) (c . 3))
\end{cllst}

Поиск в ассоциативном списке производиться функцией \lstinline{ASSOC} (а также — \lstinline{ASSOC-IF} и \lstinline{ASSOC-IF-NOT}).
\begin{cllst}{}{}
(assoc 'c '((a . 1) (b . 2) (c . 3))) => 3
(assoc 'd '((a . 1) (b . 2) (c . 3))) => NIL
(cdr (assoc 'a '((a . 1) (b . 2) (c . 3)))) => 1
(assoc "a" '(("a" . 1) ("b" . 2) ("c" . 3)) :test #'string=) => ("a" . 1)
(assoc 'a '((a . 10) (a . 1) (b . 2) (c . 3))) => (A . 10)
\end{cllst}

Функции \lstinline{RASSOC}, \lstinline{RASSOC-IF} и \lstinline{RASSOC-IF-NOT} выполняют поиск с конца списка.

Новый элемент добавить можно функцией \lstinline{ACONS}.
\begin{cllst}{}{}
(acons 'new-key 'new-value alist)
(setf alist (acons 'new-key 'new-value alist))
(push (cons 'new-key 'new-value) alist)
\end{cllst}

Для копирования ассоциативного списка следует использовать функцию \lstinline{COPY-ALIST}.

Ассоциативный список также можно создать функцией \lstinline{PAIRLIS}, которая принимает два списка и возвращает список пар.

\subsection{Destructuring-bind}
С помощью макроса \lstinline{DESTRUCTURING-BIND} можно деструктурировать списки и связывать их части с некоторыми переменными.
\begin{cllst}{}{}
(destructuring-bind (parameter*) list
  body-form*)
\end{cllst}

\begin{cllst}{Примеры}{}
(destructuring-bind (x y z) (list 1 2 3)
  (list :x x :y y :z z)) => (:X 1 :Y 2 :Z 3)

(destructuring-bind (x y z) (list 1 (list 2 20) 3)
  (list :x x :y y :z z)) => (:X 1 :Y (2 20) :Z 3)

(destructuring-bind (x (y1 y2) z) (list 1 (list 2 20) 3)
  (list :x x :y1 y1 :y2 y2 :z z)) => (:X 1 :Y1 2 :Y2 20 :Z 3)

(destructuring-bind (x (y1 &optional y2) z) (list 1 (list 2 20) 3)
  (list :x x :y1 y1 :y2 y2 :z z)) => (:X 1 :Y1 2 :Y2 20 :Z 3)

(destructuring-bind (x (y1 &optional y2) z) (list 1 (list 2) 3)
  (list :x x :y1 y1 :y2 y2 :z z)) => (:X 1 :Y1 2 :Y2 NIL :Z 3)

(destructuring-bind (&key x y z) (list :x 1 :y 2 :z 3)
  (list :x x :y y :z z)) => (:X 1 :Y 2 :Z 3)

(destructuring-bind (&key x y z) (list :z 1 :y 2 :x 3)
  (list :x x :y y :z z)) => (:X 3 :Y 2 :Z 1)

(destructuring-bind (&whole whole &key x y z) (list :z 1 :y 2 :x 3)
  (list :x x :y y :z z :whole whole))
 => (:X 3 :Y 2 :Z 1 :WHOLE (:Z 1 :Y 2 :X 3))
\end{cllst}

\section{Loop}
\lstinline{LOOP} представляет собой встроенный проблемно-ориентированный язык (\emph{embedded domain-specific language, eDSL}) для описания итераций. Что он может:
\begin{itemize}
  \item описывать циклы со счётчиком и по различным структурам данных;
  \item собирать, подсчитывать, суммировать, вычислять минимальное и максимальное значения по коллекциям;
  \item выполнять выражения Lisp;
  \item описывать условия останова;
  \item выполнять определенные действия при заданных условиях;
  \item создавать локальные переменные;
  \item выполнять некоторые выражения до выполнения цикла и после него.
\end{itemize}

\subsection{Общий синтаксис и семантика}
\lstinline{LOOP} состоит из предложений (\emph{clause}), которые начинают с одного из ключевых слов. Пример конструкции с шестью предложениями:
\begin{cllst}{}{}
(loop for i from 1 to 10
   while (< i 7)
   collect (* i i)
   do (format t "Working on ~D now~%" i)
   when (evenp i)
     do (format t "~D is non-odd number~%" i)
   finally (format t "About to exit...~%"))
\end{cllst}
\begin{plainlst}{}{}
Working on 1 now
Working on 2 now
2 is non-odd number
Working on 3 now
Working on 4 now
4 is non-odd number
Working on 5 now
Working on 6 now
6 is non-odd number
About to exit...
\end{plainlst}

Каждой ключевое слова вводит либо простое предложение, либо составное, состоящее из других предложений. Предложение может содержать вспомогательные ключевые слова, которые иногда именуются предлогами (\emph{prepositions}), например, \lstinline{from} и \lstinline{to}.

\subsubsection{Порядок выполнения}
Как правило, предложения выполняются по порядку. Цикл выполняется до тех пор, пока он не закончиться либо пока не будет выполнен явный возврат из него посредством \lstinline{return}, \lstinline{go} или \lstinline{throw}. Некоторые исключения:
\begin{itemize}
  \item Все локальные переменные инициализируются изначально независимо от того, где они были определены в тексте программы.
  \item Все формы из предложений \lstinline{initially} собираются и обрамляются в \lstinline{progn}. Полученная форма выполняется после инициализации локальных переменных.
  \item Аналогично предыдущему пункту — \lstinline{finally}.
\end{itemize}

\subsubsection{Типы предложений}
Все возможные предложения бывают следующих типов:
\begin{itemize}
  \item инициализация переменных и изменение значений с заданным шагом на каждой итерации
    \begin{itemize}
      \item \lstinline{for} и \lstinline{as} предложения позволяют определить различные циклы. Определяются переменные, которые будучи единожды проинициализированы, изменяются в соответствии с указанными правилами, например, увеличиваются с определенным шагом. Можно эти предложения комбинировать, использую ключевое слово \lstinline{and}, при этом инициализация переменных будет происходить параллельно.
      \item Конструкция \lstinline{with} похожа на конструкцию \lstinline{let}. Как и в случае с \lstinline{for}, предложения \lstinline{with} можно комбинировать.
    \end{itemize}
    Возможно указать типы данных для локальных переменных. Попытка связать переменную с какими-либо значениями дважды приведёт к ошибке.
  \item накопление значений
    \begin{itemize}
      \item \lstinline{collect} создает список, в который добавляются значения, полученные вычисленнием формы на каждой итерации. По умолчанию возвращает список значений, когда цикл завершается.
      \item \lstinline{append} создает список, путём соединения списков, полученных вычисленнием формы на каждой итерации. По умолчанию возвращает список, когда цикл завершается (см. функцию \lstinline{APPEND}).
      \item \lstinline{nconc} создает список, путём соединения списков, полученных вычисленнием формы на каждой итерации. По умолчанию возвращает список, когда цикл завершается (см. функцию \lstinline{nconc}).
      \item \lstinline{sum} суммирует численные значения, полученные выполнением переданной формы на каждой итерации. По умолчанию возвращает итоговую сумму, когда цикл завершается.
      \item \lstinline{count} определяет количество раз, переданная форма вычислилась в истинное значение. По умолчанию возвращает количество, когда цикл завершается.
      \item \lstinline{minimize} выполняет переданную форму на каждой итерации и сохраняет минимальное значение. По умолчанию возвращает минимальное значение, когда цикл завершается.
      \item \lstinline{maximize} выполняет переданную форму на каждой итерации и сохраняет максимальное значение. По умолчанию возвращает максимальное значение, когда цикл завершается.
    \end{itemize}
  \item условия останова
    \begin{itemize}
      \item \lstinline{loop-finish} завершает цикл, возвращая все накопленные значение до этого момента. При этом могут выполниться предложения \lstinline{finally}, если это указано.
      \item \lstinline{for} и \lstinline{as} завершают цикл по условию, заданному в их определении.
      \item \lstinline{repeat} завершает цикл после заданного количества итерацией.
      \item \lstinline{while} завершает цикл, как только переданная форма вычисляется в ложное значение. Эквивалентно выражению \lstinline{(if (not condition) (loop-finish))}.
      \item \lstinline{until} завершает цикл, как только переданная форма вычисляется в истинное значение. Эквивалентно выражению \lstinline{(if condition (loop-finish))}.
      \item \lstinline{always} завершает цикл, как только переданная формы вычисляется в ложное значение, и возвращает \lstinline{NIL}. Иначе, предоставляет \lstinline{T} как возвращаемое значение по умолчанию.
      \item \lstinline{never} завершает цикл, как только переданная формы вычисляется в истинное значение, и возвращает \lstinline{NIL}. Иначе, предоставляет \lstinline{T} как возвращаемое значение по умолчанию.
      \item \lstinline{thereis} завершает цикл, как только переданная формы вычисляется в истинное значение, и возвращает вычисленное значение.
    \end{itemize}
  \item безусловное выполнение
    \begin{itemize}
      \item Все формы в \lstinline{do} просто выполняются по порядку.
      \item \lstinline{return} возвращает из цикла значение, полученное в результате вычисление переданной формы. Эквивалетная предложению \lstinline{do (return value)}.
    \end{itemize}
  \item условное выполнение
    \begin{itemize}
      \item Конструкция \lstinline{if} состоит из формы и предложения, которое выполняется, если формы вычисляется в истинное значение. Предложением может быть накопление значений, безусловное или еще одно условное предложение; либо комбинация перечисленных типов предложений с помощью ключевого слова \lstinline{and}.
      \item \lstinline{when} — синоним \lstinline{if}.
      \item Поведение \lstinline{unless} такое же, как и у \lstinline{when}, только предложения выполняются только тогда, когда формы вычисляется в ложное значение.
      \item Конструкция \lstinline{else} является необязательной состовляющей конструкций \lstinline{if}, \lstinline{when} и \lstinline{unless}. Если в этих конструкциях значение вычисленной формы приводит к невычислению соответствующих предложений, то выполняется предложение из \lstinline{else}.
      \item С помощью \lstinline{end} можно обозначать окончание условного предложения.
    \end{itemize}
  \item другие операции
    \begin{itemize}
      \item Конструкция \lstinline{named} назначает имя конкретной конструкции \lstinline{loop}.
      \item Формы, определенные в предложении \lstinline{initially}, вычисляются в сразу же после инициализации всех переменных.
      \item Формы, определенные в предложении \lstinline{finally}, вычисляются в эпилоге после обычного завершения цикла. Безусловное предложение может следовать за \lstinline{finally}.
    \end{itemize}
\end{itemize}

\subsubsection{Пролог и эпилог}
\lstinline{LOOP} состоит из:
\begin{itemize}
  \item \emph{эпилога}. Выполняется до самого цикла непосредственно.
  \item \emph{самого цикла}. Тут-то и происходят всё значительное.
  \item \emph{эпилога}. Выполняется после самого цикла непосредственно.
\end{itemize}

Пролог выполняется всегда, даже если цикл не выполнит ни одной итерации. Эпилог же может быть не выполнен в следующих случаях:
\begin{itemize}
  \item Выполнение предложения \lstinline{return}.
  \item Выполнение \lstinline{RETURN}, \lstinline{RETURN-FROM} или другой конструкции передачи управления.
  \item Цикл завершается в \lstinline{always}, \lstinline{nerver} или \lstinline{thereis}
\end{itemize}

Внутри эпилога могут использоваться \lstinline{RETURN} или \lstinline{RETURN-FROM} для возврата значения. Это имеет приоритет над возвращаемыми значениями предложениями накопления или останова.


\subsubsection{Синтаксис}
Ниже приводится упрощенный синтаксиса \lstinline{LOOP} без подробностей:
\begin{plainlst}{}{}
initial-final ::= initially | finally
variables ::= with | initial-final | for-as | repeat
main ::= unconditional | accumulation | conditional
       | termination | initial-final
loop ::= (loop [named name] {variables}* {main}*)
\end{plainlst}

\subsection{Детали и примеры}
С помощью \lstinline{for}-предложения можно итерировать по:
\begin{itemize}
  \item численным интервалы с заданным шагом;
  \item спискам;
  \item спискам, состоящим из cons-ячейки;
  \item векторам, включая подтипы, такие как: строки и битовые вектора;
  \item парам ключ-значение хеш-таблиц;
  \item символам пакета;
  \item результатам повторно вычислямой формы на каждой итерации.
\end{itemize}

\lstinline{loop} может содержать несколько \lstinline{for}-предложений, но цикл завершится, если хотя бы одно из них завершится.
\begin{cllst}{}{}
(loop
   for item in '(1 2 3)
   for i from 1 to 4
   collect i)            => (1 2 3)
\end{cllst}

\begin{cllst}{Циклы со счётчиками}{}
(loop for i upto 3 collect i)             => (0 1 2 3)
(loop for i from -1 downto -3 collect i)  => (-1 -2 -3)
(loop for i from 1 to 3 collect i)        => (1 2 3)
(loop repeat 3 collect (random 3))        => (2 2 0)
(loop for i below 6 by 2 collect i)       => (0 2 4)
\end{cllst}

\subsubsection{Циклы по пакетам и коллекциям}
\begin{cllst}{}{}
(loop for i in (list 1 2 3 4) collect i) => (1 2 3 4)
(loop for i in (list 1 2 3 4) by #'cddr collect i) => (1 3)
(loop for x on (list 1 2 3) collect x) ==> ((1 2 3) (2 3) (3))
(loop for x on (list 1 2 3 4) by #'cddr collect x) ==> ((1 2 3 4) (3 4))
(loop for x across "abcd" collect x) ==> (#\a #\b #\c #\d)
\end{cllst}

Итерирование по хеш-таблице или пакету немного сложнее, так как хеш-таблицы и пакеты содержат различные множества значений, по которым можно итерировать. Общая форма:
\begin{cllst}{}{}
(loop for var being the things in hash-or-package ...)
\end{cllst}{}

Для хеш-таблиц возможными значениями для \texttt{things} являются \texttt{hash-keys} и \texttt{hash-values}, означающие, что \texttt{var} будет связываться со значениями ключей или самими значениями хеш-таблицы, соответственно. Форма \texttt{hash-or-package} вычисляется единожды.

Для итерирования по пакету \texttt{things} может быть \texttt{symbols}, \texttt{present-symbols} и \texttt{external-symbols}. \texttt{var} будет связываться с каждым символом, доступным в пакете, каждым символом, присутствующем в пакете или с каждым символом, экспортированным из пакета, соответственно.

Так как часто при итерировании по хеш-таблицам нужны и ключи, и сами значения, то в предложении для хеш-таблиц можно использовать using-подпредложение.
\begin{cllst}{}{}
(loop for k being the hash-keys in h using (hash-value v) ...)
(loop for v being the hash-values in h using (hash-key k) ...)

(length (loop for s being the symbol in :cl-user collect s)) => 1277
\end{cllst}{}

\subsubsection{Equals-then итерирование}
Если ни одна форма итерирования, приведённых выше, в предложении \lstinline{for} не подходит, то можно организовывать цикл с какой-угодно логикой изменения итерируемых переменных, использую предложение \lstinline{equals-then}.
\begin{cllst}{}{}
(loop for var = initial-value-form [ then step-form ] ...)

(loop repeat 5
   for y = 1 then (+ x y)
   for x = 0 then y
   collect y) => (1 1 2 4 8)

(loop repeat 5 
   for x = 0 then y
   and y = 1 then (+ x y)
   collect y) => (1 1 2 3 5)
\end{cllst}

\subsubsection{Деструктурирование переменных}
В \lstinline{LOOP} можно деструктурировать элементы списков.
\begin{cllst}{}{}
(loop for (a b) in '((1 2) (3 4) (5 6))
   append (list a b))                      => (1 2 3 4 5 6)

(loop for (a nil) in '((1 2) (3 4) (5 6)) collect a) => (1 3 5)
\end{cllst}

\subsubsection{Накопление значений}
\begin{cllst}{}{}
(defparameter *random* (loop repeat 10 collect (random 1000)))
(loop for i in *random*
   counting (evenp i) into evens
   counting (oddp i) into odds
   summing i into total
   maximizing i into max
   minimizing i into min
   finally (return (list min max total evens odds)))

=> (34 950 5294 4 6)
\end{cllst}

\subsubsection{Безусловное выполнение}
Простейшим способом выполнить произвольный код внутри цикла является использование предложение \lstinline{do} (или \lstinline{doing}).
\begin{cllst}{}{}
(loop for i from 1 to 10 do (print i))
\end{cllst}

Можно завершить цикл и вернуть значение из предложения \lstinline{do}, используя, например, \lstinline{RETURN} или \lstinline{RETURN-FROM}.
\begin{cllst}{}{}
(block outer
    (loop for i from 0 return 100)
    (print "This will print")
    200) => 200

(block outer
    (loop for i from 0 do (return-from outer 100))
    (print "This won't print")
    200) => 100
\end{cllst}

\subsubsection{Условное выполнение}
Так как в \lstinline{do} можно выполнять произвольный код, то можно использовать, например, \lstinline{IF} и \lstinline{WHEN} для управления потоком выполнения.
\begin{cllst}{}{}
(loop for i from 1 to 10 do (when (evenp i) (print i)))
\end{cllst}

Однако внутри \lstinline{do} нельзя использовать другие предложения, поэтому, например, для суммирования чисел, удовлетворяющих какому-либо условию, необходимо иметь предложения условного выполнения:
\begin{cllst}{}{}
(loop for i from 1 to 10 when (evenp i) sum i) => 30
\end{cllst}

Предложение условного выполнения может содержать предложения накопления значений, безусловного выполнения или другие предложения условного выполнения. Во вложенном предложении можно ссылаться на результат вычисления тестовой формы, используя \lstinline{it}.
\begin{cllst}{}{}
(loop for key in some-list when (gethash key some-hash) collect it)
\end{cllst}

Все предложение условного выполнения могут содержить \lstinline{else}-ветвь. Внутри предложения можно комбинировать с помощью \lstinline{and}. Пример, демонстрирующий многое, но бессмысленно:
\begin{cllst}{}{}
(loop for i from 1 to 100
   if (evenp i)
     minimize i into min-even and 
     maximize i into max-even and
     unless (zerop (mod i 4))
       sum i into even-not-fours-total
     end
     and sum i into even-total
   else
     minimize i into min-odd and
     maximize i into max-odd and
     when (zerop (mod i 5)) 
       sum i into fives-total
     end
   and sum i into odd-total
   do (update-analysis min-even
                       max-even
                       min-odd
                       max-odd
                       even-total
                       odd-total
                       fives-total
                       even-not-fours-total))
\end{cllst}

\section{Кратко о Format}
Функция \lstinline{FORMAT} позволяет очень кратко распечатывать переданные аргументы по заданному формату (шаблону). Например, вместо
\begin{cllst}{}{}
(loop for cons on list
    do (format t "~a" (car cons))
    when (cdr cons) do (format t ", "))
\end{cllst}
можно записать
\begin{cllst}{}{}
(format t "~{~a~^, ~}" list)
\end{cllst}

У \lstinline{FORMAT} два обязательных аргумента: получатель вывода и строка формата, которая содержит директивы. Получатель вывода может быть одним из следующих:
\begin{itemize}
  \item \lstinline{T} обозначает поток \lstinline{*STANDARD-OUTPUT*}.
  \item \lstinline{NIL}. В этом случае \lstinline{FORMAT} сформирует вывод как строку.
  \item Поток, в который будет записан результат.
  \item Строка с указателем заполнения. Вывод в этом случае добавляется в конец.
\end{itemize}

\subsection{Директивы}
Директивы состоят из тильды (\lstinline{~}) и знака (в любом регистре), который и определяет конкретную директиву. Некоторые директивы принимают префиксные параметры (между тильдой и знаком директивы). Значениями префиксного параметра являются либо числа в десятичной системе счисления, либо знаки, записанные в виде одинарной кавычки, за которой следует непосредственно знак. Значение префиксного параметра может быть также получено из аргумента формата двумя способами:
\begin{itemize}
  \item Префиксный параметр \lstinline{v} заставляет \lstinline{FORMAT} использовать один аргумент формата и назначить его значение префиксному параметру.
  \item Префиксный параметр \lstinline{#} будет вычислен как количество оставшихся аргументов формата.
\end{itemize}
\begin{cllst}{}{}
(format nil "~$" pi)    => 3.14
(format nil "~5$" pi)   => 3.14159
(format nil "~v$" 3 pi) => 3.142
(format nil "~#$" pi)   => 3.1
(format nil "~,5f" pi)  => 3.14159
\end{cllst}

Также  можно изменить поведение некоторых директив при помощи модификаторов двоеточие и знака \lstinline{@}, которые ставятся после любого префиксного параметра и до определяющего директиву знака.
\begin{cllst}{}{}
(format nil "~d" 1000000)   => 1000000
(format nil "~:d" 1000000)  => 1,000,000
(format nil "~@d" 1000000)  => +1000000
(format nil "~:@d" 1000000) => +1,000,000
\end{cllst}

Директива \lstinline{~A} печатает аргумент любого типа в удобочитаемой форме. Директива \lstinline{~S} также печает один аргумент любого типа, но так чтобы сформированный вывод мог быть прочитан функцией \lstinline{READ}.
\begin{cllst}{}{}
(format nil "The value is: ~a" 10)           => "The value is: 10"
(format nil "The value is: ~a" "foo")        => "The value is: foo"
(format nil "The value is: ~a" (list 1 2 3)) => "The value is: (1 2 3)"
\end{cllst}

Директивы \lstinline{~%} и \lstinline{~&} выполняют перевод строки с тем отличием, что \lstinline{~%} всегда это делает, а \lstinline{~&} только если вывод уже не находится в начале строки.

\subsubsection{Знаковые и целочисленные директивы}
\begin{cllst}{}{}
(format nil "~c" #\a)             => "a"
(format nil "~:c" #\Space)        => "Space"
(format nil "~@c~%" #\a)          => "#\a"
(format nil "~:@c" (code-char 0)) => "^@ (Control @)"

(format nil "~d" 1000000)      => "1000000"
(format nil "~12d" 1000000)    => "     1000000"
(format nil "~12,'0d" 1000000) => "000001000000"

(format nil "~4,'0d-~2,'0d-~2,'0d" 2005 6 10) => "2005-06-10"

(format nil "~:d" 100000000)       => "100,000,000"
(format nil "~,,'.,4:d" 100000000) => "1.0000.0000"

(format nil "~x" 1000000) => "f4240"
(format nil "~o" 1000000) => "3641100"
(format nil "~b" 1000000) => "11110100001001000000"
(format nil "~3r" 1000000) ==> "1212210202001"
\end{cllst}

\subsubsection{Директивы для чисел с плавающей точкой}
Директива \lstinline{~F} печатает свой аргумент, который должен быть числом, в десятичном формате, по возможности контролируя количество разрядов после десятичной точки. Директива \lstinline{~F} может использовать компьютеризированную научную нотацию, если число достаточно велико либо мало. Директива \lstinline{~E}, с другой стороны, всегда выводит числа в компьютеризированной научной нотации.
\begin{cllst}{}{}
(format nil "~f" pi)   => "3.141592653589793d0"
(format nil "~,4f" pi) => "3.1416"
(format nil "~e" pi)   => "3.141592653589793d+0"
(format nil "~,4e" pi) => "3.1416d+0"

(format nil "~$" pi) ==> "3.14"
(format nil "~2,4$" pi) ==> "0003.14"
\end{cllst}

\subsubsection{Директивы для английского языка}
Директива \lstinline{~R} без указания системы счисления печатает числа английскими словами или римскими цифрами. 
\begin{cllst}{}{}
(format nil "~r" 1234)   => "one thousand two hundred thirty-four"
(format nil "~:r" 1234)  => "one thousand two hundred thirty-fourth"
(format nil "~@r" 1234)  => "MCCXXXIV"
(format nil "~:@r" 1234) => "MCCXXXIIII"
\end{cllst}

Директиву \lstinline{~P} выводит \texttt{'s'}, если соответствующий аргумент не равен $1$.
\begin{cllst}{}{}
(format nil "file~p" 1)  => "file"
(format nil "file~p" 10) => "files"
(format nil "file~p" 0)  => "files"

(format nil "~r file~:p" 1)  => "one file"
(format nil "~r file~:p" 10) => "ten files"
(format nil "~r file~:p" 0)  => "zero files"

(format nil "~r famil~:@p" 1)  => "one family"
(format nil "~r famil~:@p" 10) => "ten families"
(format nil "~r famil~:@p" 0)  => "zero families"
\end{cllst}

\lstinline{~(} управляет регистром вывода до соответствующей \lstinline{~)}.
\begin{cllst}{}{}
(format nil "~(~a~)" "tHe Quick BROWN foX")   => "the quick brown fox"
(format nil "~@(~a~)" "tHe Quick BROWN foX")  => "The quick brown fox"
(format nil "~:(~a~)"p "tHe Quick BROWN foX") => "The Quick Brown Fox"
(format nil "~:@(~a~)" "tHe Quick BROWN foX") => "THE QUICK BROWN FOX"
\end{cllst}

\subsection{Условное форматирование}
Условная директива \lstinline{~[} замыкается соответствующей директивой \lstinline{~]}, а между ними находятся выражения, разделенные \lstinline{~;}. Задача директивы \lstinline{~[} — выбрать одно из выражений, которое затем обрабатывает \lstinline{FORMAT}. Без модификаторов или параметров, выражение выбирается по числовому индексу.
\begin{cllst}{}{}
(format nil "~[zero~;one~;two~]" 0) => "zero"
(format nil "~[zero~;one~;two~]" 1) => "one"
(format nil "~[zero~;one~;two~]" 2) => "two"
(format nil "~[zero~;one~;two~]" 3) => ""
\end{cllst}

Если последний разделитель выражений это \lstinline{~:;} вместо \lstinline{~;}, то последнее выражение служит выражением по умолчанию.
\begin{cllst}{}{}
(format nil "~[zero~;one~;two~:;many~]" 3)   => "many"
\end{cllst}

С модификатором двоеточие \lstinline{~[} может содержать только два выражения. Директива использует единственный аргумент и обрабатывает первое выражение, если аргумент равен \lstinline{NIL}, и второе выражение в противном случае.
\begin{cllst}{}{}
(format t "~:[FAIL~;pass~]" test-result)
\end{cllst}

\subsection{Итерация}
Директива \lstinline{~{} сообщает \lstinline{FORMAT} перебрать элементы списка или неявного списка аргументов формата.
\begin{cllst}{}{}
(format nil "~{~a, ~}" (list 1 2 3))   => "1, 2, 3, "
(format nil "~{~a~^, ~}" (list 1 2 3)) => "1, 2, 3"
(format nil "~@{~a~^, ~}" 1 2 3)       => "1, 2, 3"
\end{cllst}

Можно использовать целочисленный префиксный параметр для ограничения максимального числа выполнений итерации. С модификатором двоеточие каждый элемент списка (как настоящего, так и созданного директивой \lstinline{~@{}) сам должен быть списком, чьи элементы затем будут использованы как аргументы управляющей строки в директиве \lstinline{~:{}.

\subsection{Перемещение по параметрам}
Директивой \lstinline{~*} позволяет перемещаться по списку аргументов формата. В базовой форме она просто пропускает следующий аргумент. С модификатором двоеточие она возвращает обработку параметров назад (по умолчанию — на один), позволяя одному и тому же аргументу быть обработанным дважды.
\begin{cllst}{}{}
(format nil "~r ~:*(~d)" 1) => "one (1)"
\end{cllst}

Внутри директивы \lstinline{~{} \lstinline{~*} пропускает или перескакивает назад через элементы списка.
\begin{cllst}{}{}
(format nil "~{~s~*~^ ~}" '(:a 10 :b 20)) => ":A :B"
\end{cllst}

Директиве \lstinline{~*} также может быть задан префиксный параметр. Без модификаторов или с модификатором двоеточие этот параметр определяет число аргументов, на которое нужно передвинуться вперед или назад, и по умолчанию равен единице. С модификатором \lstinline{@} префиксный параметр определяет абсолютный, отсчитываемый от нуля индекс аргумента, на который нужно перемеситься (по умолчанию — $0$).

\section{CLOS}
\emph{CLOS} — \emph{Common Lisp Object System} (объектная система Common Lisp). CLOS основана на классах. Все объекты являются экземплярами определенного класса. Класс объекта определяет его представление. Встроенные классы, такие как \lstinline{NUMBER} и \lstinline{STRING} имеют скрытое представление, доступное только через стандартные функции для работы с этими типами. Экземпляры классов, определенных пользователем, состоят из именованных частей, называемых слотами.

Классы образуют иерархию/классификацию всех объектов. Класс может быть определен как подкласс других классов, называемых базовыми (или суперклассами). Класс наследует от суперклассов часть своего определения, а экземпляры класса также считаются и экземплярами суперклассов. В Common Lisp иерархия классов имеет один общий корень – класс \lstinline{T}, который является прямым (или косвенным) суперклассом для всех остальных классов. Таким образом, в Common Lisp все данные являются экземплярами класса. Common Lisp поддерживает множественное наследование.

\subsection{Обобщённые функции и методы}
Обобщенная функция определяет абстрактную операцию (часть интерфейса), указывая имя операции и список параметров, но не определяет реализацию. 

\begin{figure}[h!]
  \centering
  \begin{tikzpicture}[class/.style={draw},
                      sibling distance=4cm]
    \node [class] at (0,0) {bank-account}
      child { node [class] {checking-account} }
      child { node [class] {savings-account} };
  \end{tikzpicture}
  \caption{Иерархия классов}
\end{figure}

Основная форма \lstinline{DEFGENERIC} похожа на \lstinline{DEFUN}, за тем исключением, что нет тела функции. Список параметров \lstinline{DEFGENERIC} определяет параметры, которые должны приниматься всеми методами, определенными для данной обобщенной функции.
\begin{cllst}{}{}
(defgeneric withdraw (account amount)
    (:documentation "Withdraw the specified amount from the account.
  Signal an error if the current balance is less than amount."))
\end{cllst}

Методы реализуют поведение для определенных типов некоторых (или всех) параметров, определенных обобщенной функцией. Есть два метода специализации: по типу и по коокретному объекту (равенство проверяется с помощью \lstinline{EQL}).

Методы должны иметь то же самое количество обязательных и необязательных параметров и принимать любые аргументы, относящиеся к остаточным (\lstinline{&rest}) или именованным (\lstinline{&key}, \lstinline{&allow-other-keys}) параметрам, определенным в обобщенной функции. Метод также может указывать именованные параметры, не указанные в списке параметров обобщенной функции. Когда вызывается обобщенная функция, будет принят любой именованный параметр, указанный обобщенной функцией или любым другим подходящим методом.
\begin{cllst}{}{}
(defmethod withdraw ((account bank-account) amount)
    (when (< (balance account) amount)
      (error "Account overdrawn."))
    (decf (balance account) amount))
\end{cllst}

Функция \lstinline{CALL-NEXT-METHOD} является частью системы обобщенных функций и используется для комбинации подходящих методов. Она сообщает, что контроль должен быть передан от текущего метода, к методу, специализированному для \lstinline{bank-account}. Когда он вызывается без аргументов, следующий в цепочке метод будет вызван с теми же аргументами, которые были переданы обобщенной функции. Он также может быть вызван с явным указанием аргументов, которые будут переданы следующему методу.

\begin{cllst}{}{}
(defmethod withdraw ((account checking-account) amount)
  (let ((overdraft (- amount (balance account))))
    (when (plusp overdraft)
      (withdraw (overdraft-account account) overdraft)
      (incf (balance account) overdraft)))
  (call-next-method))
\end{cllst}

Форма, указанная в \lstinline{EQL}-специализаторе, который используется для указания объекта вычисляется один раз, когда вычисляется \lstinline{DEFMETHOD}.
\begin{cllst}{Пример EQL-специализатора}{}
(defmethod withdraw ((account (eql *account-of-bank-president*)) amount)
  (let ((overdraft (- amount (balance account))))
    (when (plusp overdraft)
      (incf (balance account) (embezzle *bank* overdraft)))
  (call-next-method)))
\end{cllst}

\subsection{Комбинирование методов}
Обобщенная функция при каждом запуске создают \emph{эффективный метод} из методов, для которых применимы текущие параметры. Эффективный метод строится в три этапа:
\begin{enumerate}
  \item Обобщенная функция строит список методов, которые применимы к переданным аргументам.
  \item Полученный список методов сортируется в соответствии со специализированными параметрами. При сортировке специализаторы сравниваются слева направо (порядок можно изменить с помощью \lstinline{:argument-precedence-order} в \lstinline{DEFGENERIC}). Первыми в списке  ставится метод с более специфичным специализатором.
  \item Методы по порядку берутся из списка и их код комбинируется, образуя эффективный метод.
\end{enumerate}

В типичном случае, если два специализатора класса отличаются, то один будет подклассом другого. В этом случае специализатор, именующий подкласс, считается более специфичным. Поэтому метод, который специализирован для счета с классом \lstinline{checking-account} будет рассматриваться как более специфичный, чем метод, специализированный для класса \lstinline{bank-account}.

\lstinline{EQL}-специализатор всегда более специфичен, чем любой специализатор класса. Если \lstinline{EQL}-специализатор конкретного параметра имеет более одного метода, то все они должны иметь одинаковые \lstinline{EQL}-специализаторы. Сравнение данных методов происходит на основе других параметров.

\subsubsection{Стандартный комбинатор методов}
Рассмотрим, как отсортированный список методов комбинируется в эффективный метод. По умолчанию обобщенные функции используют \emph{стандартный комбинатор методов}. Стандартный комбинатор объединяет методы таким образом, что сначала запускается наиболее специфичный метод, а каждый метод может передать управление следующему, используя \lstinline{CALL-NEXT-METHOD}.

До сих пор были рассмотрены только основные методы (в которых, как правило, реализуется основной функционал). Стандартный комбинатор методов также поддерживает три вида вспомогательных методов: \lstinline{:before}, \lstinline{:after} и \lstinline{:around}. Например:
\begin{cllst}{}{}
(defmethod withdraw :before ((account bank-account) amount) ...)
\end{cllst}

Каждый вид вспомогательных методов комбинируется в эффективный метод разными способами. Все применимые методы \lstinline{:before} (не только наиболее специфические) запускаются как часть эффективного метода. Они запускаются до наиболее специфического основного метода, начиная с самого специфического.
\begin{cllst}{}{}
(defmethod withdraw :before ((account checking-account) amount)
  (let ((overdraft (- amount (balance account))))
    (when (plusp overdraft)
      (withdraw (overdraft-account account) overdraft)
      (incf (balance account) overdraft))))
\end{cllst}

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

Семантика стандартного комбинатора методов:
\begin{itemize}
  \item Если определёны \lstinline{:around} методы, то вызывается наиболее специфичный. Его результат будет результатом вызовы обобщённой функции.
  \item Внутри \lstinline{:around} метода можно использовать \lstinline{CALL-NEXT-METHOD}. Когда следующий метод завершается, можно выполнять дальше какой-либо код. Если используется \lstinline{CALL-NEXT-METHOD}, но нет применимого метода, то вызывается обобщённая функция \lstinline{NO-NEXT-METHOD}. Функция \lstinline{NEXT-METHOD-P} может быть использована для определения, есть ли следующий метод.
  \item Если в \lstinline{:around} вызывается \lstinline{CALL-NEXT-METHOD}, то следующий наиболее специфический \lstinline{:around} метод вызывается. Если нет следующего \lstinline{:around} метода или же был вызван наименее специфический \lstinline{:around} метод, то другие методы вызываются по следующим правилам:
    \begin{itemize}
      \item Вызываются все \lstinline{:before} методы, начиная с наиболее специфического. Их возвращаемые значения игнорируются. Является ошибкой вывоз \lstinline{CALL-NEXT-METHOD} из этих методов.
      \item Вызывается наиболее специфический основной метод. Внутри этого метод можно использовать \lstinline{CALL-NEXT-METHOD} для вызова следующего наиболее специфического основного метода. Когда следующий метод завершается, можно выполнять дальше какой-либо код. Если используется \lstinline{CALL-NEXT-METHOD}, но нет применимого основного метода, то вызывается обобщённая функция \lstinline{NO-NEXT-METHOD}. Функция \lstinline{NEXT-METHOD-P} может быть использована для определения, есть ли следующий метод. Если \lstinline{CALL-NEXT-METHOD} не используется в основном методе, то выполнение основных методов на нём и прекращается.
      \item Вызываются все \lstinline{:after} методы, начиная с наименее специфического. Их возвращаемые значения игнорируются. Является ошибкой вывоз \lstinline{CALL-NEXT-METHOD} из этих методов.
    \end{itemize}
  \item Если ни один \lstinline{:around} метод не был вызван, тогда результатом будет значение, возвращённое наиболее специфическим основным методом. \lstinline{CALL-NEXT-METHOD}, вызванный в наименее специфическом \lstinline{:around} методе, возвращает результат выполнения наиболее специфического основного метода.
\end{itemize}

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

\begin{cllst}{Иллюстрация порядка запуска основного и вспомогательных методов}{}
;;; integer => rational => real => number => t
(defgeneric speak (arg))

(defmethod speak ((arg number))
  (format t "number  : primary method~%"))

(defmethod speak ((arg integer))
  (format t "integer : primary method~%")
  (call-next-method))

(defmethod speak :before ((arg number))
  (format t "number  : before method~%"))

(defmethod speak :before ((arg integer))
  (format t "integer : before method~%"))

(defmethod speak :after ((arg number))
  (format t "number  : after method~%"))

(defmethod speak :after ((arg integer))
  (format t "integer : after method~%"))

(defmethod speak :around ((arg number))
  (format t "number  : around method~%")
  (call-next-method))

(defmethod speak :around ((arg integer))
  (format t "integer : around method~%")
  (call-next-method))

CL-USER> (speak 1)
integer : around method
number  : around method
integer : before method
number  : before method
integer : primary method
number  : primary method
number  : after method
integer : after method
NIL
\end{cllst}

\subsubsection{Другие комбинаторы методов}
CL в стандартной поставке имеет еще 9 других комбинаторов методов: \lstinline{+}, \lstinline{and}, \lstinline{append}, \lstinline{list}, \lstinline{max}, \lstinline{min}, \lstinline{nconc}, \lstinline{or} и \lstinline{progn}. Всё они ведут себя одинаковым образом: вместо вызова наиболее специфического метода, который в свою очередь может вызывать менее специфические, эти комбинаторы создают эффективный метод, который вычисляет все основные методы по порядку и передаёт результаты как аргументы функции с соответвующим именем комбинатора методов. Также эти комбинаторы поддерживают \lstinline{:around} методы.

Например, обобщённая функция, которая использует \lstinline{+} комбинатор, вернёт сумму всех значений, возвращённых основными методами. Следуем помнить, что при вызове обобщённой функции, которая использует \lstinline{and} или \lstinline{or} комбинатор, могут быть вычислены не все основные методы, если в вычислении конкретного метода нет необходимости.

По умолчанию, основные методы вычисляются, начиная с наиболее специфического. Можно изменить этот порядок на обратный, используя опцию \lstinline{:method-combination} в определении обобщённой функции.

\begin{cllst}{Пример использования простого комбинатора}{}
(defgeneric priority (job)
  (:documentation "Return the priority at which the job should be run.")
  (:method-combination + :most-specific-last))

(defmethod priority + ((job express-job)) 10)
\end{cllst}

Подытожим. Методы могут быть двух типов:
\begin{itemize}
  \item \lstinline{:around} методы. Являются тем же, что и \lstinline{:around} методы в стандартном комбинаторе методов. Поэтому в них можно использовать \lstinline{CALL-NEXT-METHOD} и \lstinline{NO-NEXT-METHOD-P}.
  \item Основные методы с таким же именем квалификатора, как и у соответсвующего комбинатора методов. Внутри этих методов нельзя вызывать \lstinline{CALL-NEXT-METHOD} и \lstinline{NO-NEXT-METHOD-P}.
\end{itemize}

Собственные комбинаторы методов можно определить, используя \lstinline{DEFINE-METHOD-COMBINATION}.

\subsection{Классы}
Все классы образуют иерархию наследования, на вершине которой находится класс \lstinline{T}. Классы делятся на два основных вида: встроенные и определённые пользователем. Встроенными являются, например, классы \lstinline{INTEGER}, \lstinline{STRING} и \lstinline{LIST}. Нельзя создавать наследовать классы от встроенных классов, но можно определять методы для них, таким образом изменяя поведение этих классов.

Новый класс можно определить макросом \lstinline{DEFCLASS}. \lstinline{DEFCLASS} определяет класс как тип данных, поведение же определяется обобщёнными функциями. Определение класса состоит из трёх основных частей: имени, списка базовых классов и определений слотов (аналогичны полям и аттрибутам в друих языках программирования).
\begin{cllst}{}{}
(defclass name (direct-superclass-name*)
  (slot-specifier*))
\end{cllst}

Имена классов находятся в собственном пространстве имен, отдельно от имен функций и переменных. Имя класса используется при создании объектов функцией \lstinline{MAKE-INSTANCE}. Если список базовых классов — пуст, тогда класс будет отнаследован от класса \lstinline{STANDARD-OBJECT}. \lstinline{STANDARD-OBJECT} является подклассом класса \lstinline{T}.
\begin{cllst}{}{}
(defclass bank-account () ...)
(defclass checking-account (bank-account) ...)
(defclass savings-account (bank-account) ...)
\end{cllst}

\subsection{Определение слотов}
По большей мере \lstinline{DEFCLASS} состоит из определений слотов. Слот может хранить значение. Это значение можно получить функцией \lstinline{SLOT-VALUE} и установить макросом \lstinline{SETF} вместе с \lstinline{SLOT-VALUE}.

Класс наследует слоты базовых классов. В определение слота обязательно к указанию только его имя.
\begin{cllst}{}{}
(defclass bank-account ()
  (customer-name
   balance))

(defparameter *account* (make-instance 'bank-account))  => *ACCOUNT*
(setf (slot-value *account* 'customer-name) "John Doe") => "John Doe"
(setf (slot-value *account* 'balance) 1000)             => 1000
\end{cllst}

\subsection{Инициализация объекта}
Есть три способа задать начальные значения слотам при создании объекта. С помощью опции \lstinline{:initarg} в определении слота можно указать имя, которое будет использоваться как именованный параметр при вызове \lstinline{MAKE-INSTANCE}. Опцией же \lstinline{:initform} можно задать выражение, которое будет использоваться для вычисления значения, если при вызове \lstinline{MAKE-INSTANCE} не будет передан параметр \lstinline{:initarg}.
\begin{cllst}{}{}
(defclass bank-account ()
  ((customer-name
    :initarg :customer-name)
   (balance
    :initarg :balance
    :initform 0)))

(defparameter *account*
  (make-instance 'bank-account :customer-name "John Doe" :balance 1000))

(slot-value *account* 'customer-name) => "John Doe"
(slot-value *account* 'balance)       => 1000

(slot-value (make-instance 'bank-account) 'balance)       => 0
(slot-value (make-instance 'bank-account) 'customer-name) => error
\end{cllst}

Выражений опций \lstinline{:initarg} и \lstinline{:initform} вычисляется каждый раз при создании объекта.
\begin{cllst}{}{}
(defvar *account-numbers* 0)
 
(defclass bank-account ()
  ((customer-name
    :initarg :customer-name
    :initform (error "Must supply a customer name."))
   (balance
    :initarg :balance
    :initform 0)
   (account-number
    :initform (incf *account-numbers*))))
\end{cllst}

Третьим способом инициализации объекта является использование обобщённой функции \lstinline{INITIALIZE-INSTANCE}. Основной метод, специализированный для \lstinline{STANDARD-OBJECT} инициализирует слоты, используя выражения опций \lstinline{:initarg} и \lstinline{:initform}. В своём же \lstinline{:after} методе можно инициализировать как угодно и какие угодно слоты.
\begin{cllst}{}{}
(defclass bank-account ()
  ((customer-name
    :initarg :customer-name
    :initform (error "Must supply a customer name."))
   (balance
    :initarg :balance
    :initform 0)
   (account-number
    :initform (incf *account-numbers*))
   account-type))

(defmethod initialize-instance :after ((account bank-account)
                                       &key opening-bonus-percentage)
  (when opening-bonus-percentage
    (incf (slot-value account 'balance)
          (* (slot-value account 'balance) (/ opening-bonus-percentage 100))))
  (let ((balance (slot-value account 'balance)))
    (setf (slot-value account 'account-type)
          (cond
            ((>= balance 100000) :gold)
            ((>= balance 50000) :silver)
            (t :bronze)))))

(defparameter *acct* (make-instance
                       'bank-account
                        :customer-name "Sally Sue"
                        :balance 1000
                        :opening-bonus-percentage 5))

(slot-value *acct* 'balance) => 1050
\end{cllst}

\subsection{Функции доступа}
Использование \lstinline{SLOT-VALUE} нежелательно для соблюдения принципов инкапсуляции. Поэтому есть возможность лаконично создавать функции для чтения слота, функции для записи и функции, которые могут как считывать слот, так и записывать в него.

Опция \lstinline{:reader} определения слота задаёт имя обобщённой функции, при помощи которой можно считывать значение данного слота. При вычислении \lstinline{DEFCLASS} будет создана обобщённая функций, если таковой ещё не существует, и метод, специализированный для определяемого класса, который возвращает при вызове значение слота. Например, следующее определение слота
\begin{cllst}{}{}
(balance
 :initarg :balance
 :initform 0
 :reader balance)
\end{cllst}
раскроется примерно в подобный код:
\begin{cllst}{}{}
(defgeneric customer-name (account))

(defmethod customer-name ((account bank-account))
  (slot-value account 'customer-name))

(defgeneric (setf customer-name) (value account))

(defmethod (setf customer-name) (value (account bank-account))
  (setf (slot-value account 'customer-name) value))
\end{cllst}

Опция \lstinline{:writer} позволяет создать обобщённую функцию с заданным именем для установки значения слота. Создаваемая функция и метод следуют требованиям для \lstinline{SETF}-функции, получая новое значение как первый аргумент, и возвращая его в качестве результата.
\begin{cllst}{}{}
(customer-name
 :initarg :customer-name
 :initform (error "Must supply a customer name.")
 :reader customer-name
 :writer (setf customer-name))
\end{cllst}

Для создания обеих функций, следует использовать опцию \lstinline{:accessor}.
\begin{cllst}{}{}
(customer-name
 :initarg :customer-name
 :initform (error "Must supply a customer name.")
 :accessor customer-name)
\end{cllst}

Следом — полное определение класса:
\begin{cllst}{}{}
(defclass bank-account ()
  ((customer-name
    :initarg :customer-name
    :initform (error "Must supply a customer name.")
    :accessor customer-name
    :documentation "Customer's name")
   (balance
    :initarg :balance
    :initform 0
    :reader balance
    :documentation "Current account balance")
   (account-number
    :initform (incf *account-numbers*)
    :reader account-number
    :documentation "Account number, unique within a bank.")
   (account-type
    :reader account-type
    :documentation "Type of account, one of :gold, :silver, or :bronze.")))
\end{cllst}

Для более лаконичного обращения со слотами в CL определены два макроса: \lstinline{WITH-SLOTS} и \lstinline{WITH-ACCESSORS}.
\begin{cllst}{}{}
(with-slots (slot*) instance-form
  body-form*)
\end{cllst}

Каждый элемент \lstinline{slot} может быть либо именем слота, которое также будет является именем переменной, либо списком из двух элементов, где первый элемент является именем, которое будет использоваться как переменная, а второй – именем соответствующего слота. Внутри тела макроса, каждое вхождение имени переменной преобразуется в вызов \lstinline{SLOT-VALUE} с использованием объекта и имени слота в качестве аргументов. Для сравнения:
\begin{cllst}{}{}
(defmethod assess-low-balance-penalty ((account bank-account))
  (when (< (slot-value account 'balance) *minimum-balance*)
    (decf (slot-value account 'balance) (* (slot-value account 'balance) .01))))

(defmethod assess-low-balance-penalty ((account bank-account))
  (with-slots (balance) account
    (when (< balance *minimum-balance*)
      (decf balance (* balance .01)))))
\end{cllst}

Если при определении слота была использована опция \lstinline{:accessor}, то можно использовать макрос \lstinline{WITH-ACCESSORS}, который делает то же самое, только используя функции доступа вместо \lstinline{SLOT-VALUE}.
\begin{cllst}{}{}
(defmethod assess-low-balance-penalty ((account bank-account))
  (with-accessors ((balance balance)) account
    (when (< balance *minimum-balance*)
      (decf balance (* balance .01)))))
\end{cllst}

\subsection{Общие слоты}
Последней опцией слота, которую мы рассмотрим, является \lstinline{:allocation}. Она может быть равной либо \lstinline{:instance} (значение по умолчанию), либо \lstinline{:class}. В последнем случае слот принадлежит всему классу, а не отдельному экземляру. Изменения такого слота через один экземпляр затрагивают и все остальные экземпляры. Получить доступ к такому слоту, не имея экземпляра, нельзя.

\subsection{Слоты и наследование}
В CL объект может иметь только один слот с определенным именем. Однако возможно, что в иерархии классов несколько классов будут иметь слоты с одним и тем же именем.

Проблема решается путём слияния всех спецификаторов с одним и тем же именем из нового класса и всех его суперклассов для создания отдельных спецификаторов для каждого уникального имени слота. Слияние различных опций происходит по разному.

Поскольку слот может иметь только одно значение по умолчанию, то если несколько классов указывают опцию \lstinline{:initform}, то новый класс будет использовать эту опцию из наиболее специализированного класса.

Каждая опция \lstinline{:initarg} создает именованный параметр, который может быть использован для инициализации слота.

Унаследованные опции \lstinline{:reader}, \lstinline{:writer} и \lstinline{:accessor} не включаются в новый спецификатор слота, поскольку методы, созданные при объявлении суперкласса, будут применяться и к новому классу. Однако новый класс может создать свои собственные функции доступа.

Опция \lstinline{:allocation} определяется наиболее специализированным классом.
\begin{cllst}{}{}
(defclass foo ()
  ((a :initarg :a :initform "A" :accessor a)
   (b :initarg :b :initform "B" :accessor b)))
 
(defclass bar (foo)
  ((a :initform (error "Must supply a value for a"))
   (b :initarg :the-b :accessor the-b :allocation :class)))
\end{cllst}

\subsection{Множественное наследование}
Если бы классы могли иметь только один непосредственный суперкласс, то упорядочение классов по специфичности было бы тривиальным. CL использует второе правило, которое сортирует не относящиеся друг к другу суперклассы по порядку в котором они перечислены в определении \lstinline{DEFCLASS}: классы, указанные в списке первыми, считаются более специфичными, чем классы, указанные в списке последними. Например, для следующего класса
\begin{cllst}{}{}
(defclass money-market-account (checking-account savings-account) ())
\end{cllst}
список следования будет следующим:
\begin{cllst}{}{}
(money-market-account
 checking-account
 savings-account
 bank-account
 standard-object
 t)
\end{cllst}

Поскольку все спецификаторы одинаковых слотов объединяются, то не имеет значения, что \lstinline{money-market-account} дважды наследует одни и те же слоты из \lstinline{bank-account}.

\section{Символы}
Символ — объект, который состоит минимум из трёх составляющих:
\begin{itemize}
  \item \emph{Список свойств (property list)}. Изменяемые список, состоящий из именованных компонент.
  \item \emph{Печатное имя}. Строка, по которой определяется символ.
  \item \emph{Указатель на пакет}. Пакет — это структура данных, используемая для поиска символа по его имени. Символ однозначно определён своим именем только в контексте пакета. Символ может быть в нескольких пакетах, но может принадлежать только одному. Указатель на пакет ссылается именно на тот, которому и принадлежит этот символ.
\end{itemize}

\subsection{Списки свойств}
С каждым символом ассоциирована табличная структура данных, именуемая \emph{списком свойств (property list, plist)}. Список свойств состоит из одной или нескольких записей, где запись — это ассоциация ключа (именуемого \emph{индикатором}), который, как правило, является символом, с объектом (именуемым \emph{значением} или же \emph{свойством}).

Список свойств представляет собой список с чётным числом элементов. Каждая пара элементов образует запись. Первый элемент является ключом, второй же — значением.

Получить список свойств символа можно функцией \lstinline{SYMBOL-PLIST}.

Свойства создаются функциями \lstinline{GET} и \lstinline{GETF} в сочетании с \lstinline{SETF}. Следом — их объявления:
\begin{cllst}{}{}
(defun get (symbol indicator &optional default) ...)
(defun getf (place indicator &optional default) ...)
(get x y) == (getf (symbol-plist x) y)
\end{cllst}

\begin{cllst}{Примеры использования}{}
(defvar foo (list :bar t :baz 3 :hunoz "Huh?"))

(getf foo :bar)   => T
(getf foo :baz)   => 3
(getf foo :hunoz) => "Huh?"

(setf (getf foo :baz) 4)
(getf foo :baz)  => 4
\end{cllst}

Функция \lstinline{GET-PROPERTIES} возвращает список значений значений для данного списка ключей.
\begin{cllst}{}{}
(defun get-properties (place indicator-list) ...)
\end{cllst}

Свойство можно удалить функциями \lstinline{REMPROP} и \lstinline{REMF}.
\begin{cllst}{}{}
(defun remprop (symbol indicator) ...)
(defun remf (place indicator) ...)
(remprop x y) == (remf (symbol-plist x) y)
\end{cllst}

\begin{cllst}{Примеры}{}
(defvar foo (list 'color 'blue 'height 6.3 'near-to 'bar))

(remf foo 'height) => (COLOR BLUE NEAR-TO BAR)
\end{cllst}

\subsection{Печатное имя символа}
Каждый символ имеет соответсвующую строку в качестве печатного имени. Получить его можно функцией \lstinline{SYMBOL-NAME}.
\begin{cllst}{}{}
(symbol-name 'xyz) => "XYZ"
\end{cllst}

\subsection{Создание символов}
Символы могут быть интернированными и нет. \emph{Интернированный символ} — это тот символ, который индексируется по имени в катологе, называемом \emph{пакет}. Запрос в пакете по имени всегда возвращает один и тот же символ. Всегда, когда \lstinline{READ} встречает одно и то же печатное имя, то полученный символ будет одним и тем же. \emph{Неинтернированный символ} — символ, который не принадлежит ни одному пакету. Печатаются такие символы с префиксом \lstinline{#:}.

Интернировать символ в пакет можно функцией \lstinline{INTERN}. Функций \lstinline{MAKE-SYMBOL} создаёт неинтернированный символ по печатному имени. Функция \lstinline{COPY-SYMBOL} копирует символ с его списком свойств или без него. Возвращенный символ — неинтернирован не в один пакет. По умолчанию список свойств не копируется.
\begin{cllst}{}{}
(defun make-symbol (print-name) ...)
(defun copy-symbol (sym &optional copy-props) ...)
\end{cllst}

Функция \lstinline{GENSYM} создаёт новый неинтернированный символ.
\begin{cllst}{}{}
(defun gensym (&optional x) ...)
\end{cllst}

Имя нового символа оканчивается на значение переменной \lstinline{*GENSYM-COUNTER*} или же на значение параметра \lstinline{X}, если он определён и является числом (в этом случае это число становиться новым значением счётчика). Начинается же имя на \lstinline{G} или же на значение параметра \lstinline{X}, если он определён и является строкой (этом случае это значение становиться новым префиксом по умолчанию).
\begin{cllst}{}{}
(gensym) => G7
(gensym "FOO-") => FOO-8
(gensym 32) => FOO-32
(gensym) => FOO-33
\end{cllst}

Получить пакет, в котором символ интернирован, можно функцией \lstinline{SYMBOL-PACKAGE}.

Ключевой символ — это символ, который интернирован в пакет \lstinline{KEYWORD}. Ключевой символ является константой в том смысле, что он вычисляется всегда в самого себя. Проверить, является ли символ ключевым, можно функцией \lstinline{KEYWORDP}.
\begin{cllst}{}{}
(keywordp :sym) => T
(eql ':foo :foo) => T
\end{cllst}

\section{Пакеты}
Пакет — это отображение строки в символ. \lstinline{FIND-PACKAGE} ищет пакет по его имени. Символ в пакете можной найти функций \lstinline{FIND-SYMBOL}.
Если этой функции не передан пакет, в котором следует искать символ, используется пакет, который присвоен переменной \lstinline{*PACKAGE*}, то есть текущий пакет.

Когда \lstinline{READ} считывает символ-строку в исходном коде, он преобразует эту строку к верхнему регистру и передаёт полученную строку функции \lstinline{INTERN}. Таким образом, одно и то же считываемое имя считывается в один и тот же символ пакета.

Для доступа к символу пакета извне, может использовать синтаксис \lstinline{package:symbol} или \lstinline{package::symbol}. Первым способом можно получить только тот символ пакета \lstinline{package}, который в числе экспортируемых из него. Вторым способом можно получить любой символ пакета, но так делать — не рекомендуется. Все символы, которые могут быть найдены в данном пакете функцией \lstinline{FIND-SYMBOL}, называются \emph{доступными}.

Символ может быть доступен в пакете двумя способами. Первый, таблица пакета содержит запись для этого символа. Тогда говорится, что символ \emph{присутствует} в пакете. Когда считыватель интернирует новый символ в пакет, он добавляет его в таблицу. Первый пакет, в который интернирован символ, называется \emph{домашним} пакетом этого символа.

Другой способ, которым символ может быть доступен в пакете, — это унаследование символа пакетом. Пакет наследует символы из других пакетов путём использования их. Наследуются только \emph{внешние} символы из используемых пакетов. Символ делается внешним в пакете путём его экспорта.

Существующий символ может быть \emph{импортирован} в другой пакет через добавление его в пакетную таблицу. Таким образом, один и тот же символ может присутствовать во многих пакетах.

\subsection{Определение пакетов}
\begin{cllst}{}{}
(defpackage :email-app
  (:use :common-lisp :db :network)
  (:shadow :build-index)
  (:shadowing-import-from :network :save)
  (:import-from :email :parse-email-address)
  (:export :make-email
           :send-email
           :save-email)
  (:nicknames :eapp))
\end{cllst}

\lstinline{:use} импортируют все экспортируемые символы из перечисленных далее пакетов. \lstinline{:shadow} скрывает далее определённые символы из пакетов, перечисленных в \lstinline{:use}. Эту опцию следует использовать, если в определяемом пакете определены символы с такими же именами, какие имеют некоторые символы в пакетах из \lstinline{:use}. \lstinline{:shadowing-import-from} импортирует все символы, кроме перечисленных, из указанного пакета. \lstinline{:export} экпортирует перечисленные символы. \lstinline{:nicknames} создает псевдонимы пакета.

Опции пакеты могут быть указаны в любом порядке. Вычисляются же они в следующей очерёдности:
\begin{enumerate}
  \item \lstinline{:shadow} и \lstinline{:shadowing-import-from}
  \item \lstinline{:use}
  \item \lstinline{:import-from} и \lstinline{:intern}
  \item \lstinline{:export}
\end{enumerate}

\section{Обработка исключений: состояния и перезапуски}
Система состояний CL гибче и мощнее, чем системы обработки исключений других языков. Это факт; факты нужно видеть, не доказывать, чем мы и займёмся.

Система обработки ошибок в CL позволяет отделить код, который обрабатывает исключительные ситуации (состояния), от кода, который решает, каким именно образом их обрабатывать.

\emph{Состояние} — это просто объект, который является экземпляром класса, который наследован (прямо или косвенно) от класса \lstinline{CONDITION}. По историческим причинам класс состояния не должен обязательно наследоваться от \lstinline{STANDARD-OBJECT}. Поэтому не все функции для классов, определённых макросом \lstinline{DEFCLASS}, обязательно будут работать и с состояниями. В частности, слоты условий недоступны по \lstinline{SLOT-VALUE}, для доступа к ним следует использовать опцию \lstinline{:reader} или \lstinline{:accessor}. Также для состояний не определена обобщённая функция \lstinline{INITIALIZE-INSTANCE}.

Создаются состояние функцией \lstinline{MAKE-CONDITION} (не \lstinline{MAKE-INSTANCE}). Для обработки ошибок состояния должны быть экземплярами класса \lstinline{ERROR}.
\begin{cllst}{}{}
(define-condition malformed-log-entry-error (error)
  ((text :initarg :text :reader text)))
\end{cllst}

\subsection{Обработка состояний}
Допустим, стоит задача разобрать журнальный файл. Если какая-либо запись журнала не может быть корректно разобрана на составляющие, то нужно просигнилизировать об ошибке. Для оповещения об ошике следует использовать функцию \lstinline{ERROR}, которая в свою очередь вызовет более низкоуровневую функцию \lstinline{SIGNAL}. Если ошибка не обрабатывается в коде, поток управление попадёт в отладчик. Функции \lstinline{ERROR} можно передавать как сформированный объект состояния, так и имя класса состояния с последующими аргументами инициализации.
\begin{cllst}{}{}
(defun parse-log-entry (text)
  (if (well-formed-log-entry-p text)
    (make-instance 'log-entry ...)
    (error 'malformed-log-entry-error :text text)))
\end{cllst}

Чтобы не попасть в отладчик, следует поставить обработчик состояния выше по стеку вызовов от кода, который информирует о состоянии. При оповещении о состоянии механизм оповещения просматривает список активных обработчиков и подыскивает подходящий по типу состояния.

Каждый обработчик состоит из спецификатора типа, определяющего какие типы состояний он может обработать, и функции одного аргумента — состояния. Из подходящих обработчик выбирается установленный последним.

Если обработчик нормально завершается, то управление возвращается функции \lstinline{SIGNAL}, которая ищет следующий наиболее подходящий обработчик. Для обработки состоянии обработчик должен передать управление посредством \emph{нелокального} перехода. Часто при обработке есть необходимость просто разкрутить стек до места, где обработчик сам установлен, и выполнить затем некоторый код. Это можно сделать макросом \lstinline{HANDLER-CASE}.
\begin{cllst}{}{}
(handler-case expression
  (condition-type ([var]) code)*)
\end{cllst}

Если \lstinline{expression} завершается нормально, то его значение становится значением \lstinline{HANDLER-CASE}. \lstinline{code} должно быть одним выражением. Если при вычислении происходит оповещение о состоянии, тип которого равен одному из \lstinline{condition-type}, то код из соответствующей секции будет выполнен, и его значение будет возвращено из \lstinline{HANDLER-CASE}.
\begin{cllst}{}{}
(defun parse-log-file (file)
  (with-open-file (in file :direction :input)
    (loop for text = (read-line in nil nil) while text
       for entry = (handler-case (parse-log-entry text)
                     (malformed-log-entry-error () nil))
       when entry collect it)))
\end{cllst}

\subsection{Перезапуск}
Последняя версия функции \lstinline{PARSE-LOG-FILE} берёт на себя слишком много. В правильно спроектированной программе принимать решение о том, как обрабатывать состояние, должен принимать код, например, диалога, который предлагает список возможных дальнейших действий пользователю.

Чтобы установить перезапуск вместо обработчика, нужно сменить \lstinline{HANDLER-CASE} на \lstinline{RESTART-CASE}. Форма \lstinline{RESTART-CASE} похожа на форму \lstinline{HANDLER-CASE} с тем отличием, что имена перезапусков являются просто именами, а не имена типов состояний.
\begin{cllst}{}{}
(defun parse-log-file (file)
  (with-open-file (in file :direction :input)
    (loop for text = (read-line in nil nil) while text
       for entry = (restart-case (parse-log-entry text)
                     (skip-log-entry () nil))
       when entry collect it)))
\end{cllst}

Если перезапуск не будет перехвачен пользовательским кодом, то поток управления перехватит отладчик. В этом случае среди представленных отладчиком перезапусков будет и \lstinline{skip-log-entry}. Если будет выбран именно этот перезапуск, то выполнение \lstinline{PARSE-LOG-FILE} пойдёт дальше с того места, где и было прервано, используя вместо некорректной записи журнала значение \lstinline{NIL}.

Выбор конкретного перезапуска можно сделать автоматическим. Пусть имеются следующие функции, которые вызываются последовательно и вложенно.
\begin{cllst}{}{}
(defun log-analyzer ()
  (dolist (log (find-all-logs))
    (analyze-log log)))

(defun analyze-log (log)
  (dolist (entry (parse-log-file log))
    (analyze-entry entry)))
\end{cllst}

Для выбора перехвата состояний и выбора перезапуска следует использовать \lstinline{HANDLER-BIND}. Код обработчика должен быть функцией одного аргумента. В отличие от \lstinline{HANDLER-CASE} \lstinline{HANDLER-BIND} обработчики запускаются без предварительной раскрутки стека. Запустить конкретный перезапуск можно используя функцию \lstinline{INVOKE-RESTART}.
\begin{cllst}{}{}
(defun log-analyzer ()
  (handler-bind ((malformed-log-entry-error
                  #'(lambda (c)
                      (invoke-restart 'skip-log-entry))))
    (dolist (log (find-all-logs))
      (analyze-log log))))
\end{cllst}

Если при вызове \lstinline{INVOKE-RESTART} соответствующий перезапуск не установлен, то сигнализируется \lstinline{CONTROL-ERROR}. Чтобы избежать таких ситуация, можно заменить определение анонимной функции на следующее:
\begin{cllst}{}{}
(lambda (c)
  (let ((restart (find-restart 'skip-log-entry)))
    (when restart (invoke-restart restart))))
\end{cllst}

\subsection{Множественные перезапуски}
Неплохо было иметь возможность не просто пропускать некорректные записи, но и заменять их на какое-либо значение и/или выбирать из нескольких вариантов дальнейших действий.

Перезапуски могут получать аргументы, которые передаются через \lstinline{INVOKE-RESTART}.
\begin{cllst}{}{}
(defun parse-log-entry (text)
  (if (well-formed-log-entry-p text)
    (make-instance 'log-entry ...)
    (restart-case (error 'malformed-log-entry-error :text text)
      (use-value (value) value)
      (reparse-entry (fixed-text) (parse-log-entry fixed-text)))))

(defun log-analyzer ()
  (handler-bind ((malformed-log-entry-error
                  #'(lambda (c)
                      (use-value
                       (make-instance 'malformed-log-entry :text (text c))))))
    (dolist (log (find-all-logs))
      (analyze-log log))))
\end{cllst}

\subsection{Применение состояний}
Система состояний и перезапусков может использоваться не только для обработки ошибок, но и для реализации любого протокола взаимодействия кода различного уровня вложенности.

Фундаментальная функция \lstinline{SIGNAL} ищет подходящий обработчик, не раскручивая стек; если же таковой не найден либо ни один подходящий обработчик не обработал состояние, то \lstinline{SIGNAL} возвращает \lstinline{NIL}.

Функция \lstinline{ERROR} вызывает в свою очередь \lstinline{SIGNAL}. Если ошибка обработывается обработчиком состояния, который передаёт управление через \lstinline{HANDLER-CASE} или через вызов перезапуска, тогда вызов \lstinline{SIGNAL} никогда не завершится. Но если \lstinline{SIGNAL} завершается, то \lstinline{ERROR} вызывает отладчик функцией, хранящейся в \lstinline{*DEBUGGER-HOOK*}. Таким образом, \lstinline{ERROR} никогда не завершается, так как условие должно быть обработано либо в коде, либо в отладчике.

Другая функция \lstinline{WARN} реализует ещё один протокол, используя систему состояний. \lstinline{WARN} также вызывает \lstinline{SIGNAL}, но если последняя завершается нормально, то \lstinline{WARN} не вызывает отладчик, а просто печатает сообщение в \lstinline{*ERROR-OUTPUT*} и возвращает \lstinline{NIL}. Функция \lstinline{WARN} также устанавливает перезапуск \lstinline{MUFFLE-WARNING}, который может использоваться обработчиком для подавления вывода предупреждающего сообщения. Функция перезапуска \lstinline{MUFFLE-WARNING} находит и вызывает одноимённый перезапуск, сигнализируя \lstinline{CONTROL-ERROR}, если такой не найден.
\begin{cllst}{}{}
(defun count-down (x)
  (do ((counter x (1- counter)))
      ((= counter 0) 'done)
    (when (= counter 1)
      (warn "Almost done"))
    (format t "~&~D~%" counter)))
CL-USER> (count-down 3)
3
2
Warning: Almost done
1
DONE

(defun ignore-warnings-while-counting (x)
  (handler-bind ((warning #'ignore-warning))
    (count-down x)))

(defun ignore-warning (condition)
  (declare (ignore condition))
  (muffle-warning))

CL-USER> (ignore-warnings-while-counting 3)
3
2
1
DONE
\end{cllst}

Третья функция \lstinline{CERROR} реализует еще один протокол, который есть смесь двух предыдущих. Как и \lstinline{ERROR}, \lstinline{CERROR} вызывает отладичик. Как и \lstinline{WARN}, \lstinline{CERROR} устанавливает перезапуск \lstinline{CONTINUE} вокруг вызова \lstinline{SIGNLA}. Функция \lstinline{CONTINUE} для \lstinline{CERROR} аналогична функции \lstinline{MUFFLE-WARNING} для \lstinline{WARN}.

\section{Примеры}
\begin{cllst}{Разбивка строки и слияние строк}{}
(defun comma-split (string)
  (loop :for start := 0 :then (1+ finish)
        :for finish := (position #\, string :start start)
        :collecting (subseq string start finish)
        :until (null finish)))

(defun write-with-periods (strings)
  (format t "~{~A~^.~}" strings)
\end{cllst}

\begin{cllst}{Топологическая сортировка}{}
(defun topological-sort (graph &key (test 'eql))
  "Graph is an association list whose keys are objects and whose
values are lists of objects on which the corresponding key depends.
Test is used to compare elements, and should be a suitable test for
hash-tables.  Topological-sort returns two values.  The first is a
list of objects sorted toplogically.  The second is a boolean
indicating whether all of the objects in the input graph are present
in the topological ordering (i.e., the first value)."
  (let ((entries (make-hash-table :test test)))
    (flet ((entry (vertex)
             "Return the entry for vertex.  Each entry is a cons whose
              car is the number of outstanding dependencies of vertex
              and whose cdr is a list of dependants of vertex."
             (multiple-value-bind (entry presentp) (gethash vertex entries)
               (if presentp entry
                 (setf (gethash vertex entries) (cons 0 '()))))))
      ;; populate entries initially
      (dolist (vertex graph)
        (destructuring-bind (vertex &rest dependencies) vertex
          (let ((ventry (entry vertex)))
            (dolist (dependency dependencies)
              (let ((dentry (entry dependency)))
                (unless (funcall test dependency vertex)
                  (incf (car ventry))
                  (push vertex (cdr dentry))))))))
      ;; L is the list of sorted elements, and S the set of vertices
      ;; with no outstanding dependencies.
      (let ((L '())
            (S (loop for entry being each hash-value of entries
                     using (hash-key vertex)
                     when (zerop (car entry)) collect vertex)))
        ;; Until there are no vertices with no outstanding dependencies,
        ;; process vertices from S, adding them to L.
        (do* () ((endp S))
          (let* ((v (pop S)) (ventry (entry v)))
            (remhash v entries)
            (dolist (dependant (cdr ventry) (push v L))
              (when (zerop (decf (car (entry dependant))))
                (push dependant S)))))
        ;; return (1) the list of sorted items, (2) whether all items
        ;; were sorted, and (3) if there were unsorted vertices, the
        ;; hash table mapping these vertices to their dependants
        (let ((all-sorted-p (zerop (hash-table-count entries))))
          (values (nreverse L)
                  all-sorted-p
                  (unless all-sorted-p
                    entries))))))

> (defparameter *dependency-graph*
  '((des-system-lib   std synopsys std-cell-lib des-system-lib dw02 dw01 ramlib ieee)
    (dw01             ieee dw01 dware gtech)
    (dw02             ieee dw02 dware)
    (dw03             std synopsys dware dw03 dw02 dw01 ieee gtech)
    (dw04             dw04 ieee dw01 dware gtech)
    (dw05             dw05 ieee dware)
    (dw06             dw06 ieee dware)
    (dw07             ieee dware)
    (dware            ieee dware)
    (gtech            ieee gtech)
    (ramlib           std ieee)
    (std-cell-lib     ieee std-cell-lib)
    (synopsys)))
*DEPENDENCY-GRAPH*

> (topological-sort *dependency-graph*)
(IEEE DWARE DW02 DW05 DW06 DW07 GTECH DW01 DW04 STD-CELL-LIB SYNOPSYS STD DW03 RAMLIB DES-SYSTEM-LIB)
T
NIL
\end{cllst}

\begin{cllst}{Зиг-заг матрица}{}
(defun zigzag (n)
  (flet ((move (i j)
           (if (< j (1- n))
               (values (max 0 (1- i)) (1+ j))
               (values (1+ i) j))))
    (loop with a = (make-array (list n n) :element-type 'integer)
          with x = 0
          with y = 0
          for v from 0 below (* n n)
          do (setf (aref a x y) v)
             (if (evenp (+ x y))
                 (setf (values x y) (move x y))
                 (setf (values y x) (move y x)))
          finally (return a))))

 0  1  5  6 14
 2  4  7 13 15
 3  8 12 16 21
 9 11 17 20 22
10 18 19 23 24
\end{cllst}

\begin{cllst}{Небольшие применения loop}{}
(defun sum-of-squares (vector)
  (loop for x across vector sum (expt x 2))

(defun sieve-of-eratosthenes (maximum)
  (let ((composites (make-array (1+ maximum) :element-type 'bit
                                             :initial-element 0)))
    (loop for candidate from 2 to maximum
          when (zerop (bit composites candidate))
            collect candidate
            and do (loop for composite from (expt candidate 2) to maximum by candidate
                         do (setf (bit composites composite) 1)))))
\end{cllst}

\begin{cllst}{Quicksort}{}
(defun quicksort (list)
  (if (<= (length list) 1)
      list
      (let ((pivot (first list)))
	(append	(quicksort (remove-if-not #'(lambda (x) (< x pivot)) list))
			   (remove-if-not #'(lambda (x) (= x pivot)) list)
		(quicksort (remove-if-not #'(lambda (x) (> x pivot)) list))))))

(defun qs (list)
  (if (< (length list) 2)
      list
      (macrolet ((pivot (test) `(remove (first list) list :test-not #',test)))
        (append (qs (pivot >)) (pivot =) (qs (pivot <))))))

(defun quicksort (sequence)
  (labels ((swap (a b) (rotatef (elt sequence a) (elt sequence b)))
           (sub-sort (left right)
             (when (< left right)
               (let ((pivot (elt sequence right))
                     (index left))
                 (loop for i from left below right
                       when (<= (elt sequence i) pivot)
                         do (swap i (prog1 index (incf index))))
                 (swap right index)
                 (sub-sort left (1- index))
                 (sub-sort (1+ index) right)))))
    (sub-sort 0 (1- (length sequence)))
    sequence))
\end{cllst}

\begin{thebibliography}{9}

\bibitem{cl:seibel05}
  P. Seibel,
  \emph{Practical Common Lisp}.
  Apress,
  2005.

\bibitem{cl:kiczales91}
  G. Kiczales, J. des Rivieres, D. G. Bobrow,
  \emph{The Art of the Metaobject Protocol}.
  The MIT Press,
  1991.

\bibitem{cl:graham95}
  P. Graham,
  \emph{ANSI Common Lisp}.
  Prentice Hall,
  1995.

\bibitem{cl:graham93}
  P. Graham,
  \emph{On Lisp: Advanced Techniques for Common Lisp}.
  Prentice Hall,
  1993.

\bibitem{cl:steele90}
  G. Steele,
  \emph{Common Lisp: The Language}.
  Digital Press,
  2nd ed.,
  1990.

\end{thebibliography}