Типы и декларации типов в Common Lisp (love5an)

Table of Contents

Система типов CL

В прошлом постинге я обещал рассказать о декларациях типов.

Но, сначала надо разобраться с тем, что собственно из себя представляет система типов Common Lisp.

Так вот, типы CL это не то же самое, что типы во многих других языках, особенно статически-типизированных.

В Common Lisp тип это, по сути, просто некое неупорядоченное множество(set) объектов(возможно даже, и бесконечное). Каждый объект лиспа принадлежит, вообще говоря, бесконечному количеству типов, так как разных множеств можно придумать бесконечно много. Сами же типы не являются объектами лиспа, они описываются косвенно, по спецификациям типов, в s-выражениях.

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

По причине того, что типы суть множества в математическом смысле, рекурсивных типов в Common Lisp нет. Если кто помнит теорию множеств из математики, то множество можно задать либо перечислением всех объектов, в него входящих, либо указанием предиката, который проверяет принадлежность объекта множеству. Сами имена типов, поэтому, значения не имеют - это просто сокращения для записи множеств, грубо говоря.

Спецификатор типа, перечисляющий все элементы, в тип входящие, называется member. Задается он в виде

(member объект1 объект2 _и_так_далее_)

Например, тип (member 1 2 3) - множество из трех чисел - 1, 2 и 3, соответственно. На равенство объекты проверяются так, как это делает функция eql. Кстати, собственно спецификатор eql тоже есть - он равнозначен member с одним аргументом. Пример - (eql :symbol) - множество из одного элемента - символа :symbol.

Задать тип по предикату можно с помощью спецификатора satisfies - он принимает один аргумент, имя глобально-определенной функции(символ), которая проверяет на принадлежность объекта типу. Например - (satisfies integerp) - тип, которому принадлежат все целые числа.

Существует два особых типа - T и NIL. Первый тип описывает универсальное множество, т.е. ему принадлежат все объекты лиспа, которые только могут быть. Второй - пустое множество, т.е. множеству nil не принадлежит ни один объект, а само оно является подмножеством всех других множеств. Кстати, тип nil не следует путать с типом null, который суть (eql nil) (т.е. множество из одного объекта - символа nil).

Операции с типами

Как и множества, типы можно разными способами комбинировать. Например - спецификатор and описывает пересечение множеств, спецификатор or - объединение, а not - дополнение множества до универсального. Пример: тип

(and (or (satisfies numberp) (satisfies symbolp)) (not (satisfies
         floatp)) (member #\a :b 123 123.0))
  • это множество из двух объектов - числа 123 и символа :b.

В стандарте CL определены две базовых функции, работающие с типами - typep и subtypep. Первая определяет принадлежность объекта типу(т.е. принадлежность объекта множеству), вторая выясняет отношения между типами - проверяет, является ли один тип подтипом другого(то есть, определяет, является ли одно множество подмножеством другого).

Существует также функция type-of. Вкратце - она возвращает спецификацию типа, которая при использовании в typep для того же объекта всегда вернет значение истины(T). Если немного подробнее - тип, который возвращенная спецификация описывает скорее всего является фактическим типом, который конкретная реализация CL использует для представления объекта(например (type-of 123) в 32-битном SBCL возвращает (integer 0 536870911) или (mod 536870912), то есть суть неотрицательный fixnum; но про это ниже).

Deftype

Новые типы можно вводить с помощью макроса deftype. Он чем-то похож на defmacro, в частности видом списка аргументов, за исключением того, что неиспользованные &optional и &key параметры в качестве значения по умолчанию используют символ *, а не nil. Почему звездочку? Ну, она используется во многих встроенных спецификациях типов, например в array - там она может указывать на произвольность типа элемента массива, на произвольную длину какой-либо размерности массива или на произвольное количество размерностей вообще.

Внутри deftype можно выполнять произвольный код, но в итоге нужно возвращать валидную спецификацию типа(причем не рекурсивную. Почему - см. выше). Рекурсивные спецификации типов в лучшем случае выльются в ошибку (сигнал класса error), в худшем - завесят лисп-систему или вызовут stack overflow). deftype раскрываются при вызове typep, в декларациях типов при компиляции, и так далее.

Вот пример определения типа с помощью deftype:

(deftype my-set (&optional (exclude-even nil)) (cons 'member
  (loop :for i
        :below 16
        :unless (and exclude-even (evenp i))
        :collect i)))

;; (typep 2 'my-set) ==> T (typep 2 '(my-set t)) ==> NIL (typep 123
;; 'my-set) ==> NIL

defclass, define-condition, defstruct и другие подобные макросы/функции из CLOS и MOP тоже вводят именованные типы(причем их спецификации - атомарные), и subtypep для двух классов/структур, один из которых является родителем, а другой - наследником, работает так, как и ожидается. Но, по сути, классы и типы это разные вещи - хотя бы потому, что классы в CLOS являются объектами лиспа, а типы - нет, и с помощью классов нельзя выразить то, что можно выразить типами (обратное тоже верно, впрочем).

В CL присутствует множество встроенных спецификаторов типов, как составных, так и атомарных.

Декларации типов.

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

  • Первым элементом в списке (т.е. в car) идет символ type
  • Вторым элементом - спецификатор типа
  • После - имена переменных(одно или больше)
  • Символ type, в принципе, можно опускать, но это распознается не всеми реализациями CL, и кроме того, это может вызывать конфликты с другими декларациями.

Существует также декларация ftype. Она, в принципе, аналогична type, но используется только для функций, и единственный допустимый спецификатор типа в ней - function. Существует она потому, что в Common Lisp неймспейсы функций и переменных разделены (грубо говоря, в структуре "символ" для функций и переменных - отдельные слоты).

Кстати, немного о спецификаторе function. Составной спецификатор, т.е. форма вида

(function (...типы_аргументов...)  тип_возращаемого_значения)

валиден только в контексте деклараций - попытка узнать конкретный тип функции с помощью typep вызовет ошибку. Тип возвращаемого значения в составной форме спецификатора functon, кстати, может быть не только конкретным спецификатором какого-либо одного типа, но и формой (values ...типы_возвращаемых_значений...) - для функций, возвращающих несколько значений.

Декларации типов обычно расставляются в declaim и(гораздо чаще) declare и в операторе the. В контексте функции proclaim смысла от них немного (особенно для оптимизации кода).

Используются они для оптимизации, для документирования кода, для проверки типов во время компиляции и, в некоторых реализациях CL, при высоких уровнях safety в декларации optimize - для проверки типов в рантайме.

Хотя общие принципы в использовании деклараций типов есть, на самом деле их полезность очень сильно зависит от конкретной реализации Common Lisp. Так, clisp практически все декларации типов игнорирует, в SBCL они очень сильно помогают оптимизировать код, а в Clozure CL - проверять типы (иногда даже лучше SBCL).

Итак, по пунктам:

Документирование кода.

Я бы рекомендовал расставлять декларации типов в начале всех глобально определяемых функций (defun); особенно тех, которые экспортируются из пакетов. Знать, с какими типами некая конкретная функция работает всегда полезно.

Часто только по одному имени функции и по ее типу можно понять, что она делает и для чего предназначена. Это очень большой плюс для процесса интерактивной разработки - информацию по типу функции выдает describe, разнообразные IDE(типа SLIME), и так далее.

И, конечно, это очень хорошее дополнение к документации библиотеки/приложения, особенно когда оная документация неполноценна или просто отсутствует(допустим, проект еще только начат и/или автору пока просто лень оную документацию писать).

Проверка типов в рантайме.

Ошибки типов в рантайме все же иногда случаются. Ну, хотя бы в процессе разработки. Далеко не так часто, как предполагают адепты статической типизации, но тем не менее. Видеть в дебаггере имя какой-нибудь знакомой функции из своего кода, или из API чужой библиотеки, предполагаемые типы ее аргументов, и типы переданных значений - гораздо приятнее, чем наблюдать километровый стектрейс и какой-нибудь SB-KERNEL:TWO-ARG-+ где-нибудь в кишках рантайма конкретной лисп-системы, ругающийся на то, что у него второй аргумент не число, а NIL.

Проверка типов на этапе компиляции.

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

Почему предупреждения, а не собственно ошибки, которые бы останавливали компилятор? Потому что CL очень динамичен по своей сути, и несоответствия типов с точки зрения компилятора совсем не обязательно могут вылиться в ошибку в рантайме.

Декларации типов и оптимизации.

Итак. Да, декларации типов очень сильно помогают компиляторам лиспа оптимизировать код. Но, это не значит, что их надо лепить где попало, и декларировать тип всем переменным, которые в коде присутствуют. Поэтому, первым делом я опишу когда их расставлять не стоит:

  • Нет смысла декларировать типы значениям, которые используются как булевые переменные. В CL существует понятие "generalized boolean" - все, что не NIL это истина, и только NIL - ложь. Соответственно, любая логическая операция всегда подразумевает просто сравнение с константой NIL, а это и так очень быстро, декларация (type boolean …), или использование только T, а не любого лиспового объекта в качестве значения истины производительности коду не прибавит.
  • Не нужно рассчитывать на то, что при декларациях типов CLOS-методы и slot-value (доступ к экземплярам CLOS-классов (defclass/define-condition)) будут инлайниться и/или быстрее работать - CLOS слишком динамична, она подразумевает обязательную диспетчеризацию в рантайме.
  • При работе с длинными числами(bignum), дробями(ratio) и, вообще, "обобщенными" числовыми типами(integer, float, rational, real, complex (в виде атомарного спецификатора; (complex double-float) компилятор может вполне себе оптимизировать), number etc.) декларации типов сильно оптимизации не помогут - рантайм лисп-системы скорее всего будет проводить обобщенную арифметику(про нее ниже), как он это делает и без деклараций. Но, для проверки типов декларации могут быть полезны, опять же.
  • Хэш-таблицы(hash-table) от деклараций типов работать быстрее не станут.
  • Символы(symbol) тоже.

Теперь про то, когда следует. Но сначала небольшой экскурс в устройство современных лисп-систем. Кстати, хотя все, что ниже, относится в основном к SBCL, тем не менее, для многих других оптимизирующих компиляторов CL(вроде того же Clozure CL) это также должно оставаться верным.

Вобщем, как я упомянул в предыдущем постинге - все в лиспе есть объект. Что это значит в контексте типов и оптимизации?

Первым делом это значит вот что. Несмотря на то, что типы суть множества, каждый конкретный объект все же должен иметь некое конкретное представление на самом низком уровне(ну, в байтах), и это представление должно иметь какое-то отношение к типам. Так вот, это то, что я (и не только я) называю "фактический тип"(я уже выше про него упомянул, его спецификацию обычно возвращает функция type-of).

Задача разработчика, если он ставит своей целью оптимизировать код с помощью деклараций типов состоит в том, чтобы помочь компилятору свести типы переменных от универсального типа T к одному из таких фактических типов, объектами которых рантайм лисп-системы может оперировать с максимальной эффективностью. При этом, естественно, не обязательно декларировать типы для всего и вся - как я уже сказал, современные компиляторы лиспа очень хорошо умеют проводить вывод типов - достаточно указать типы для нескольких переменных на вершине стека, а потом следовать замечаниям компилятора.

Что будет, если компилятор не сможет свести типы каких-либо переменных к своим фактическим типам? Лисп-система вынуждена будет проводить диспетчеризацию в рантайме, то есть в рантайме выбирать конкретные функции, необходимые для осуществления некой конкретной операции над некоторыми конкретными объектами. А это чревато неслабыми издержками по производительности.

Что из себя представляют объекты в современных лисп-системах? Каждая сущность представляет собой указатель на данные, которые, среди прочего, хранят информацию о типе объекта. Стоп. Тут я немного наврал - на самом деле, часть информации о типе хранится в самом указателе на объект. Эта информация, несколько битов, откушенные от машинного слова, обычно называется type tag(метка типа). Например, в 32битном SBCL это ровно три бита, в 64битном - 4.

Возникает вопрос - а как собственно, на 32-битной системе, например, если от указателя остается 29 бит, лисп-система может адресовать больше 512 мегабайт? Ответ прост - если данные выровнены по 8 байтам, у нас есть ровно 3 бита в начале машинного слова, которые никогда не используются для адресации(они всегда равны нулю), и соответственно мы можем их использовать под метку типа. Для 64-битного SBCL данные, соответственно, выравниваются по 16 байтам.

Для "стирания" метки типа, и превращения тегированного указателя в обычный можно использовать модель адресации современных процессоров(base+offset) - крайне эффективная техника; пример - ниже.

Тут возникает еще один вопрос - а если у нас некоторая информация о типе может хранится прямо в машинном слове, зачем, собственно, выделять память под мелкие объекты и делать машинное слово указателем? Ведь, для, например, представления всех литер из юникода достаточно 21 бита.

И, действительно, тип character в SBCL это просто тегированное машинное слово.

Аналогичная ситуация с небольшими целыми числами. Составители стандарта CL все это хорошо предусмотрели много лет назад и добавили в CL специальный тип fixnum, который суть целое число со знаком, которое умещается в машинное слово с меткой типа.

С fixnum интересен еще вот какой момент - их можно представлять не какой-то специфической меткой типа, а просто побитово сдвинутым влево числом. Если fixnum представляется в такой форме(а так он и представляется в SBCL, и много где еще), то для арифметических операций на нем процессору не нужно постоянно очищать/восстанавливать метку типа(т.е. сдвигать вправо и т.д.). Такая модель fixnum удобна для обращения к вектору, значения которого являются либо указателями, либо числами размером с машинное слово - не нужно сдвигать fixnum-индекс вправо.

Для 32-битного SBCL fixnum, таким образом, имеет две "метки типа" - 0b100(все нечетные fixnum) и 0b000(все четные).

Кстати, 64-битный SBCL в машинном слове может содержать целый single-float(который суть single IEEE 754).

К этому моменту, я надеюсь, читателям стало немного понятно, зачем числа и character в Common Lisp не сравниваются по eq, а только как минимум по eql.

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

Структуры в CL (defstruct) предусматривают возможность типизации своих слотов, а массивы могут быть гомогенными. "Машинные" типы, то есть такие типы, которыми оперирует процессор, SBCL в типизированных слотах структур и в гомогенных массивах хранит разбоксенными. Кроме того, боксинга не происходит при локальных операциях над объектами таких типов - то есть, выделение памяти и маркировка указателя происходит только тогда, когда число отправляется "в свободное плавание" - т.е. передается в какую-либо глобально-определенную функцию, или возвращается из такой.

Вот пример кода и дизассемблерный листинг для 32-битного SBCL на x86, иллюстрирующий вышесказанное:

(deftype int-vector () '(simple-array (signed-byte 32) (*)))

(defun add-int-vectors (v1 v2)
  (declare (type int-vector v1 v2)
           (optimize (speed 3) (safety 0)))
  (dotimes (i (min (length v1)
                   (length v2)))
    (incf (aref v1 i) (aref v2 i)))
  ;; v1[i] += v2[i] v1
  )
; disassembly for ADD-INT-VECTORS
; 243F0CD8: 850500000021 TEST EAX, [#x21000000]
; no-arg-parsing entry point
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Размеры массивов хранятся в виде fixnum.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; "-3" это "стирание" метки типамассива,
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; т.е. превращение тегированногоуказателя в обычный
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (метка типа массива - 0b111),
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; и одновременно добавление куказателю 4.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Т.е. реально данные лежат в(указатель_на_вектор + 8)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; А в (указатель_на_вектор + 4) лежит длина вектора.
; CDE: 8B42FD MOV EAX, [EDX-3] ;; EDX == v1
; CE1: 8B4FFD MOV ECX, [EDI-3] ;; EDI == v2
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Вычисление минимальной длины:
; CE4: 39C8 CMP EAX, ECX
; CE6: 7F26 JNLE L3
; CE8: 8BC8 MOV ECX, EAX       ;;; ECX - минимальная из длинн векторов
; CEA: L0: 31C0 XOR EAX, EAX   ;;; EAX - счетчикцикла
; CEC: EB11 JMP L2
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Цикл:
; CEE: L1: 8B740701 MOV ESI, [EDI+EAX+1] ;; вытаскиваем число из вектора v1
; CF2: 8B5C0201 MOV EBX, [EDX+EAX+1]     ;; вытаскиваем число из v2
; CF6: 01F3 ADD EBX, ESI                 ;; суммируем
; CF8: 895C0201 MOV [EDX+EAX+1], EBX     ;; складываем результат в v1
; CFC: 83C004 ADD EAX, 4                 ;; инкремент. 4(0b100) -число 1 в виде fixnum
; CFF: L2: 850500000021 TEST EAX, [#x21000000]
; D05: 39C8 CMP EAX, ECX                 ;; проверяем, надо лизаканчивать цикл
; D07: 7CE5 JL L1
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Возврат из функции. Восстановлениепредыдущего фрейма, и т.д.
; D09: 8BE5 MOV ESP, EBP
; D0B: F8 CLC
; D0C: 5D POP EBP
; D0D: C3 RET                    ;; возвращаемое значение - вEDX, первый аргумент, v1
; D0E: L3: EBDA JMP L0

Спецификаторы типов массивов

Напоследок - пару слов о спецификаторах типов массивов. Выглядят они в общем виде так:

(array[или simple-array] [тип_элементов [размерности]])

Тип элементов может быть любой спецификацией типа, либо символом *. Тип элементов * обозначает множество массивов с любым типом элементов. Да, это отличается от типа элементов T; последний обозначает множество массивов, способных хранить любой объект - но, к примеру, массивы из множества (array character) не способны хранить любой объект, они могут хранить только литеры, и поэтому (array character) не является подтипом (array T).

Аргумент, описывающий размерности может быть либо символом *, который обозначает множество массивов с любым количеством размерностей любых длин, либо числом, обозначающим количество размерностей у массивов данного множества, либо списком, каждый элемент которого - либо число, обозначающее длину размерности массива, либо *, что означает, что длина может быть произвольной.

Чем отличаются array и simple-array? Массивы в CL бывают разные - с указателем заполнения, с изменяемым размером и отображенные (displaced).

Так вот, simple-array это такие массивы, в которых нет ни первого, ни второго, ни третьего - это просто, грубо говоря, данные плюс метаинформация о типе. Доступ к массивам типа simple-array в современных реализациях CL обычно намного быстрее, чем к массивам других видов (особенно отображенных).

Яндекс.Метрика
Home