Структуры, массивы, векторы и строки

Структуры (defstruct), массивы и векторы, строки как векторы символов: типизированные «контейнеры» Lisp с быстрым индексным доступом.

defstruct создаёт новый составной тип с именованными полями, автоматически порождая конструктор, предикат типа и аксессоры; вектор — это одномерный массив с доступом по индексу за O(1).

Зачем это: за пределами списков

Списки — гибкий, но не всегда правильный инструмент: доступ к n-му элементу списка — O(n), а «записи» из cons-пар не самодокументированы. Когда нужны фиксированный набор именованных полей или быстрый индексный доступ, Lisp предлагает структуры, массивы, векторы и строки. Они дают то, что списки не дают: O(1)-доступ по индексу, компактное хранение, типизацию полей, эффективные числовые массивы. Освоив их, вы перестаёте «натягивать списки» на задачи, для которых есть точные структуры.

Существует распространённое заблуждение, будто Lisp «весь про списки» и потому медленный для серьёзных вычислений. Это миф, и данный урок его развенчивает. Списки — это лишь одна из структур, удобная для рекурсивного построения и обхода, но Common Lisp с самого начала проектировался как практический язык с полным набором эффективных структур: типизированные массивы для числового кода (по плотности и скорости не уступающие C), хеш-таблицы для индексов, структуры и классы для записей. Хороший Lisp-программист выбирает структуру под задачу так же осознанно, как выбирает алгоритм: список — для рекурсивных данных и стеков, вектор — для индексного доступа, специализированный массив — для матриц чисел, структура — для именованных полей. Привычка «всё списком» — признак новичка; зрелый код пёстр от разных структур, и каждая стоит там, где её сильные стороны кстати. Именно поэтому на SBCL можно писать численно тяжёлый код, который соперничает по скорости с компилируемыми языками, — при условии, что вы используете правильные структуры и декларации типов.

defstruct: записи с именованными полями

defstruct — самый быстрый способ объявить «запись». Одна форма порождает целое семейство функций: конструктор make-имя, предикат имя-p, аксессоры имя-поле (читаемые и устанавливаемые через setf).

(defstruct point
  (x 0)            ; поле x со значением по умолчанию 0
  (y 0))           ; поле y со значением по умолчанию 0

;; defstruct автоматически создал:
;;   (make-point :x 3 :y 4)   — конструктор
;;   (point-p obj)            — предикат типа
;;   (point-x p) (point-y p)  — аксессоры (и setf-места)

(defparameter *p* (make-point :x 3 :y 4))
(point-x *p*)               ; => 3
(setf (point-y *p*) 10)     ; изменить поле
(point-y *p*)               ; => 10
(point-p *p*)               ; => T
(point-p 42)                ; => NIL

Структуры дают типобезопасность (предикат), читаемость (именованные поля) и эффективность (поля хранятся в смежной памяти, доступ — прямой, а не поиск). defstruct поддерживает наследование через :include (одиночное), кастомные конструкторы, печать. Это «лёгкий» ООП: когда нужен полноценный полиморфизм и мультиметоды — переходят на CLOS (следующий раздел), но для простых записей defstruct и проще, и быстрее CLOS-классов.

Когда выбирать defstruct, а когда полноценный класс CLOS? Это частый вопрос, и ответ практичен. defstruct — когда вам нужна простая запись: фиксированный набор полей, быстрый доступ, возможно одиночное наследование, и не требуется ни мультидиспетчеризация, ни множественное наследование, ни возможность менять класс «на лету». Структуры компактнее и их аксессоры обычно чуть быстрее. CLOS — когда нужен полиморфизм: разные реализации поведения для разных типов (обобщённые функции), множественное наследование, миксины, комбинирование методов, метапрограммирование. Грубое правило: начинайте с defstruct, если объект — это «просто данные с именованными полями»; переходите на defclass, как только появляется потребность в полиморфном поведении или гибкой иерархии. Многие проекты используют оба: структуры для внутренних «пакетов данных» в горячих путях и классы для доменной модели с богатым поведением. Важно: переход с defstruct на defclass позже обычно несложен, потому что аксессоры именуются похоже, — так что преждевременно усложнять не нужно.

Массивы и векторы

Массив — структура с доступом по целочисленным индексам за O(1). Одномерный массив называется вектором. Создание: литерал #(...) (константный), vector (свежий), общий make-array. Доступ — aref (для любых размерностей) или svref (для простых векторов); запись — через setf.

(defparameter *v* (vector 10 20 30))   ; вектор из 3 элементов
(aref *v* 0)                  ; => 10
(setf (aref *v* 1) 99)        ; изменить элемент
(aref *v* 1)                  ; => 99
(length *v*)                  ; => 3

;; make-array даёт контроль: размер, тип элементов, начальное значение
(defparameter *grid* (make-array '(2 3) :initial-element 0))  ; 2x3
(aref *grid* 1 2)             ; => 0  (двумерный доступ)
(setf (aref *grid* 0 1) 7)

Главное преимущество вектора над списком — индексный доступ за O(1) (в списке — O(n)). Зато список дёшев для добавления в голову, а вектор фиксированной длины — нет. Особый и очень полезный вид — растущий вектор с заполнением: (make-array n :fill-pointer 0 :adjustable t) позволяет vector-push-extend — динамический массив, как «список с быстрым доступом».

;; динамический вектор: растёт по мере добавления
(defparameter *stack* (make-array 0 :fill-pointer 0 :adjustable t))
(vector-push-extend 'a *stack*)   ; добавить, растя при нужде
(vector-push-extend 'b *stack*)
(aref *stack* 0)                   ; => A
(length *stack*)                   ; => 2  (по fill-pointer)

Строки как векторы символов

Ключевая идея: в Lisp строка — это вектор символов (специализированный массив с элементами типа character). Это не аналогия, а буквальная правда: к строке применимы aref, length, а также всё «семейство последовательностей» (map, subseq, find, position), потому что и списки, и векторы, и строки — это последовательности (sequences) с единым API.

(defparameter *s* "Lisp")
(aref *s* 0)             ; => #\L   (символ L)
(length *s*)             ; => 4
(char *s* 1)             ; => #\i   (char — аналог aref для строк)
(subseq *s* 1 3)         ; => "is"  (подстрока, как у любой последовательности)

;; строковые операции
(string-upcase "lisp")   ; => "LISP"
(concatenate 'string "Common " "Lisp")   ; => "Common Lisp"
(format nil "~a + ~a = ~a" 2 3 5)        ; => "2 + 3 = 5"

Важно понимать: строковые литералы "..." по стандарту считаются константами — их нельзя изменять на месте без последствий. Чтобы получить изменяемую строку, создавайте её через make-string или copy-seq. То, что строка — это последовательность, объединяет огромный пласт функций: одна и та же find, reduce, remove, sort работает над списком, вектором и строкой. Это редкая по элегантности унификация: вместо отдельных API для каждого типа — единый протокол последовательностей.

Эту унификацию стоит прочувствовать глубже, потому что она экономит огромные усилия. В типичном языке у строк свой набор методов, у массивов — свой, у списков — третий, и одну и ту же по смыслу операцию («найти элемент», «взять подотрезок», «перевернуть») приходится вызывать по-разному для каждого типа. В Common Lisp есть единый протокол последовательностей: десятки функций (length, elt, subseq, find, position, count, remove, substitute, map, reduce, sort, reverse и другие) работают единообразно над любой последовательностью — списком, вектором, строкой. Выучив их один раз, вы применяете их везде. Более того, многие принимают именованные аргументы :test, :key, :start, :end, :from-end, что делает их чрезвычайно гибкими. Это одна из самых сильных сторон стандартной библиотеки CL: вместо зоопарка типоспецифичных методов — стройный, ортогональный набор операций над абстракцией «последовательность». Поэтому, говоря «строка — это вектор символов», мы не просто констатируем факт реализации, а открываем доступ ко всему этому богатству для работы с текстом.

Когда что выбирать

Как работает под капотом

Структура defstruct по умолчанию реализуется как вектор фиксированного размера со скрытым «тегом типа» в нулевом слоте; аксессоры — это просто индексный доступ к нужному слоту, поэтому они быстры (компилятор знает смещение поля на этапе компиляции). Вектор/массив хранятся как непрерывный блок памяти с заголовком (размер, тип элементов); aref — арифметика «база + индекс × размер_элемента», отсюда O(1). Специализированные массивы (:element-type '(unsigned-byte 8) или 'double-float) хранят элементы «упакованно», без обёрток-объектов, что даёт C-подобную плотность и скорость для числовых расчётов. Строка — специализированный вектор с :element-type 'character: те же механизмы доступа, плюс она участвует в протоколе последовательностей. fill-pointer — это дополнительное поле «логическая длина ≤ физическая ёмкость», позволяющее «дописывать» без пересоздания, а :adjustable разрешает перевыделение при переполнении (как растущий массив). Этот механизм — прямой аналог «динамического массива» (как std::vector в C++ или list в Python): ёмкость растёт скачками (обычно удвоением), а fill-pointer отслеживает реально занятую часть, поэтому добавление в среднем O(1), несмотря на редкие дорогие перевыделения. Понимая это, вы видите, что «список против вектора» в Lisp — не выбор «гибкость против скорости», а выбор конкретной структуры: растущий вектор даёт и динамический рост, и быстрый индексный доступ одновременно.

Частые ошибки

• Изменять строковый литерал. "..." — константа; правка на месте — неопределённое поведение. Для изменяемой строки берите make-string/copy-seq.
• Ждать O(1) от nth по списку. Доступ к n-му элементу списка линеен. Нужен индексный доступ — используйте вектор.
• Путать длину и ёмкость растущего вектора. length учитывает fill-pointer (логическую длину), а не выделенную ёмкость. Добавляйте через vector-push-extend.
• Брать svref для неподходящего массива. svref — только для простых векторов; универсальный доступ — aref (любые размерности и виды массивов).
• Использовать список там, где нужна запись. Самодельные «записи» из позиционных списков хрупки; defstruct даёт имена, предикат и скорость.

Итоги

• defstruct порождает тип с конструктором make-, предикатом -p и аксессорами (читаемыми и setf-устанавливаемыми) — лёгкий и быстрый ООП для записей.
• Вектор — одномерный массив с доступом aref/svref за O(1); make-array даёт контроль размера, типа и начального значения.
• Растущий вектор (:fill-pointer :adjustable + vector-push-extend) — динамический массив.
• Строка — это вектор символов; к ней применим весь протокол последовательностей (find, subseq, map, length).
• Списки/векторы/строки — последовательности с единым API; выбирайте структуру под задачу (доступ, размер, тип).
• Под капотом: структура — вектор со слотами и тегом; массив — непрерывная память (O(1) индекс); специализированные массивы дают C-плотность для чисел.