[Изображение логотипа компании]

Структуры данных

В.Водолазкий

Первые шаги в Common Lisp - Структуры данных

Часть 6

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

Введение в структуры

Механизм структур в Common Lisp почти полностью скрывается в одном единственном макросе -- defstruct, который позволяет пользователю создавать и использовать агреггированные типы данных с именованными полями (элементами). По большому счету, этот макрос явился ответом на "структуры", используемые в старом добром PL/I, или "records" в языке Паскаль.

Начнем с примера. Предположим, что вы разрабатываете очередную версию Стар-трека -- одну из первых компьютерных игр, но на этот раз на Лиспе. Одна из задач, которая стоит перед вами, состоит в управлении космическими кораблями, которые перемещаются в двумерном координатном пространстве. Понятно, что корабль должен представляться Лисп-объектом некоторого типа. В нашей игре каждый корабль будет характеризоваться текущими координатами (в виде пары x и y), скоростью (представляемой в виде проекций вдоль осей x и y axes), и массой корабля.

В результате корабль может быть представлен как запись, имеющая пять составляющих: x-координата, y-координата, x-скорость, y-скорость, и масса. Эта структура, в свою очередь, может быть реализована в Лиспе несколькими способами.

Во-первых, это может быть список, состоящий из пяти элементов -- в этом случае x-координата извлекается с помощбю функции car, y-координата -- с помощью cadr, и так далее. Аналогичным образом можно попытаться использовать пятиэлементный вектор: x-координата будет храниться в элементе с номером 0, координата y -- в элементе с номером 1, и так далее. Однако при использовании любого из этих представлений возникает общая проблема, состоящая в том, что компоненты занимают внутри объекта позиции, выбираемые достаточно произвольным образом, что довольно сложно запомнить, и что, в конце концов, приводит к различным ошибкам.

Например, если взглянуть на запись (cadddr ship1) или (aref ship1 3), то догадаться, что речь идет об y-составляющей вектора скорости ship1 весьма нелегко. Более того, если в силу каких-либо обстоятельств представление данных о корабле будет изменено, то найти все участки кода программы, которые должны быть изменены будет еще сложнее (например, речь идет не обо всех вызовах функции cadddr, а лишь о тех, котрые предназначены для извлечения y-составляющей скорости корабля).

В идеальном случае компоненты таких структур должны иметь имена. Например, достаточно удобно использовать конструкцию: (ship-y-velocity ship1) вместо неудобоваримой (cadddr ship1). Можно также попытаться использовать более удобный способ создания записи о параметрах корабля по сравнению с:

(list 0 0 0 0 0)

В самом деле, разве не удобнее определить ship как новый тип данных, аналогичный другим типам данных в Лиспе, который мог бы, например, проверяться с помощью предиката typep. Для этого в Common Lisp предусмотрен всего лишь один механизм --- defstruct, которого, впрочем, вполне достаточно.

Сам по себе вызов defstruct представляет собой маакрос, который создает описание структуры. Например, для описания параметров космического корабля, мы можем определить следующую структру:

(defstruct ship 
  x-position 
  y-position 
  x-velocity 
  y-velocity 
  mass)

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

ship-x-position интерпретируется как функция с одним аргументом -- именем корабля, которая возвращает x-координату корабля; ship-y-position и другие компоненты представляют собой определения аналогичных функций. Эти функции называются функциями доступа, поскольку они используются для доступа к отдельным элементам структуры.
Символ ship становится именем (названием) типа данных, экземпляры которого содержат определенные с помощью defstruct компоненты. Это имя становится распознеаваемым с помощью предиката typep; в результате (typep x 'ship) принимает значение T, если x является кораблем и NIL, если x представляет собой объект любого другого типа.
Определяется предикат ship-p, использующий один аргумент, который принимает значение T, если аргумент имеет тип ship, и NIL, если он имеет любой другой тип.
Создается функция make-ship, которая при вызове создает новую структуру данных с пятью компонентами, которая пригодна для использования совместно с функциями доступа. В результате выполнение
(setq ship2 (make-ship))
устанавливает ship2 равным вновь созданному объекту типа ship. При необходимости можно задать начальные значения для любого из компонентов путем вызова make-ship с ключевыми аргументами следующим образом:
(setq ship2 (make-ship :mass *default-ship-mass* :x-position 0 :y-position 0))
В результате будет создан новый корабль и одновременно будет установлено значение трех его параметров. Эта функция называется обычно конструктором, поскольку собирает (конструирует) новую структуру.
Для чтения значений экземпляров ship может использоваться синтаксис #S, а кроме того, в Common Lisp реализована функция печати, позволяющая выводить произвольные структуры данных. Например, значение переменной ship2, определенной выше, может быть выведено в следующем виде:
#S(ship x-position 0 y-position 0 x-velocity nil y-velocity nil mass 170000.0)

Определяется функция с именем copy-ship, которая принимает один аргумент, и при передаче ей объекта типа ship, создаст новый объект типа ship, который является копией исходного. Эта функция называется копировщиком.
В просторечьи, ее иногда называют также ксероксом, что является русифицированной калькой с англоязычного термина copier function.

Для изменения значений компонентов ship можно использовать функцию setf:
(setf (ship-x-position ship2) 100)
В результате x-координата корабля ship2 получит новое значение, равное 100. Этот механизм работает потому, что макрос defstruct фактически генерирует соответствующие каждому компоненту формы defsetf.

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

Как использовать defstruct с максимальной пользой

Абсолютно все структуры в Common Lisp определяются с помощью конструкции defstruct. Вызов defstruct определяет новый тип данных, все экземпляры которого содержат один итот же набор именованных компонентов.

Макрос defstruct

defstruct name-and-options [doc-string] slot-description*

Эта макрокоманда предназначена для определения структур данных в Common Lisp. Наиболее распространенное использование defstruct выглядит так, как это показано в следующем примере.

(defstruct ( name  option-1 option-2 ... option-m) 
            doc-string
            slot-description-1
            slot-description-2
            ... 
            slot-description-n)

Аргумент name должен быть символом; он становится именем нового типа данных, состоящего из всех экземпляров структуры. Функция typep после определения структуры сможет распознавать и корректно обрабатывать это имя.

Это же имя name возвращается в качестве результата выполнения формы defstruct.

Впрочем, в наиболее распространенных случаях никакие дополнительные параметры не нужны вообще. При этом вы можете написать просто имя name, вместо ( name) после слова defstruct.

Если при описании структуры используется необязательная строка документирования doc-string, она присоединяется к типу name, как строка документации типа structure.

Каждое из описаний компонентов slot-description-j имеет следующий вид:

( slot-name  default-init
  slot-option-name-1  slot-option-value-1
  slot-option-name-2  slot-option-value-2
  ... 
  slot-option-name-k  slot-option-value-k)

При этом каждый slot-name должен представлять собой символ; именно это позволяет создать для каждого слота (компонента) соответствующую функцию доступа. Если же при определении структуры не заданы ни параметры ни объявление default-init, то вы можете просто написать slot-name вместо ( slot-name) при описании соответствующего компонента.

Форма default-init оценивается всякий раз при создании структуры; полученное значение используется в качестве начального значения соответствующего компонента. Эта форма оценивается только в том случае, если соответствующие начальные значения не передаются конструктору структуры явным образом. Если при определении структуры default-init задана не была, то начальные значения компонентов, по большому счету не определены и зависят от реализации системы.

В ряде случаев может оказаться удобным использовать объявление структур вообще без каких-либо компонентов. Такие определения, несмотря на кажущуюся абсурдность, оказываются полезными в тех случаях, когда используется параметр :include, конечно, совместно с другими параметрами. Например, вы можете иметь две структуры, которые в целом подобны друг другу, за исключением того, что по-разному выводятся на печать (потому что имеют различные реализации функции :print-function).

Макрос defstruct не только определяет функции доступа для каждого компонента, но также настраивает setf для корректной работы с такими функциями доступа, а также определяет предикат name-p, функцию конструктора make-name, и функцию копировщика copy-name. Все имена автоматически созданных функций становятся домашними для того пакета, который является текущим в момент вызова defstruct

Кроме того, все такие функции могут быть объявлены с помощью inline, что позволяет несколько повысить эффективность генерации кода. Этот режим используется по умолчанию, и если вы не хотите, чтобы какие-либо функции создавались inline, то за формой defstruct должно следовать объявление notinline, которое перекрывает старое, созданное по умолчанию.

Однако, это не слишком безопасное решение. Во многих реализациях Common Lisp результаты переопределения defstruct, то есть повторные вызовы defstruct с одним и тем же именем могут давать непредсказуемые результаты.

Причина такого поведения состоит в том, что экземпляры структур, созданных со старыми и новыми определениями могут оказаться несовместимыми друг с другом. А если функции, ассоциированные со старым определением были объявлены inline, и скомпилированы в исполняемый код, то они останутся доступными и после нового определения, в результате чего код станет несовместим с новым определением структуры.

Конечно, такое ограничение оказывает влияние на разработку и процесс отладки. Большинство программных сред Lisp, что называется "в курсе" проблем переопределения defstruct, и предусматривают возможность их переопределения, хотя и с генерацией предупреждающих сообщений о возможных конфликтах с другими частями программной среды. Однако, к моменту выпуска готового программного обеспечения все эти конфликты должны быть улажены разработчиком -- в работающих программах подобные разногласия недопустимы!

Использование автоматически порожденной функции конструктора

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

Например, для структуры с названием foo, автоматически создается конструктор с названием make-foo; впрочем вы можете задать и другое имя, передав его ключевому аргументу :constructor, или указать, что вы не нуждаетесь в конструкторе вообще, использовав вместо имени конструктора NIL.

В общем случае обращение к функции конструктора имеет вид:

(name-of-constructor-function
           slot-keyword-1 form-1
           slot-keyword-2 form-2
       ...)

Все аргументы являются ключевыми. Каждое из ключевых слов slot-keyword должно совпадать с именем компонента структуры. Оцениваются все ключевые слова ...keyword... и формы form.... Коротко говоря, это выглядит так, как если бы функция конструктора получила все свои аргументы как параметры {&key}. Например, структура ship, содержит функцию конструктора, которая получает аргументы с помощью некоторого эквивалента вызова

(defun make-ship (&key x-position y-position 
                  x-velocity y-velocity mass) \\
...)

Если slot-keyword-j обозначает название компонента, то каждый элемент созданной структуры будет при инициализации получать значение формы form-j. Если же для данного компонента нет пары slot-keyword-j и form-j, значение компонента инициализируется формой default-init, заданной для этого компонента при вызове defstruct.

Другими словами, инициализация, заданная в defstruct, отменяется, если используется специальный вызов инициализатора в форме конструктора. Если используется форма инициализации по умолчанию, то она оценивается во время выполнения конструктора, но в лексическом контексте defstruct-формы, в которой она была определена.

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

Каждая мз форм инициализации, заданных для компонентов defstruct, оценивается при каждом вызове функции конструктора. Понятно, что это может использоваться для получения весьма нетривиальных результатов. Например, если в качестве формы инициализации используется форма (gensym) (либо при вызове функции конструктора, либо как форма инициализации по умолчанию), то каждый вызов функции конструктора будет приводить к однократному вызову gensym, который в свою очередь, будет создавать новый символ.

Параметры компонентов defstruct

Каждое описание компонента slot-description в вызове defstruct может задать один или несколько параметров компонента. Таким параметры состоят из пар, содержащих ключевое слово и значение (которое не является оцениваемой формой, а представляет собой непосредственное значение!).

Например:

(defstruct ship 
  (x-position 0.0 :type short-float) 
  (y-position 0.0 :type short-float)
  (x-velocity 0.0 :type short-float) 
  (y-velocity 0.0 :type short-float) 
  (mass *default-ship-mass* :type short-float :read-only t))

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

Ниже следует полный список поддерживаемых параметров компонентов.

:type
Параметр :type type указывает, что содержимое компонента всегда должно иметь один и тот же тип. Это полностью аналогично определению переменной или функции и позволяет надежно задать тип результата, возвращаемого функцией доступа. Следует отметить, что аргумент type не оценивается, он должен лишь быть правильным спецификатором типа.
:read-only
Параметр :read-only x, где x не равно NIL, указывает, что этот компонент не может быть изменен; он всегда содержит значение, установленное при конструировании экземпляра структруы. В результате нельзя использоваться для доступа к этому компоненту функцию setf. Если x равно NIL, этот параметр не оказывает никакого влияния. Форма аргумента x не оценивается.

Обратите внимание, что если задано значение по умолчанию, то установить параметр компонента нельзя.

Теперь вы можете самостоятельно попробовать применить структуры на практике. А в следующий раз мы еще раз вернемся к старой доброй defstruct, но обсудим более тонкие моменты, которые позволят получить действительно полную власть над структурами Common Lisp.

Используются технологии uCoz