7. Типы данных

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

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

Выражение DECLARE не является формой, так как не требует вычислений. Выражение может использоваться внутри других вычисляемых форм - defun, do, let, prog, defmacro, with-open-file.

В то же время, для ПЕРЕМЕННОЙ указание типа данных, вообще говоря, необязательно. Например, для функции max, которую в Лиспе можно для двух аргументов определить как

(DEFUN my-max (x y) (if (> x y) x y)))

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

(defun my-max (x y) (declare (number x y)) (max x y)),

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

- выбор кода для сравнения чисел будет выбираться в момент компиляции;

- при компиляции вызова (my-max 4 'hello) произойдет ошибка компиляции.

Для различных типов объектов существуют свои базовые функции, а также имеются предикаты, проверяющие принадлежность к определенному типу:

ATOM

CONSP

LISTP

NUMBERP

STRINGP

ARRAYP

Обобщенный предикат проверки типа:

(TYPEP объект тип) => T или NIL

Пример:

(typep 'spisok 'atom) => T

Функция, возвращающая тип аргумента:

(TYPE-OF объект) => тип

Примеры:

(setq spisok ‘(A B C) ) => (A B C)

(type-of spisok) => CONS

(type-of 'spisok) => SYMBOL

(type-of "spisok") => STRING

Функция, преобразующая объект, являющийся первым аргументом, к типу, задаваемому вторым аргументом:

(coerce "spisok" 'list) => (#\s #\p #\i #\s #\o #\k)

Основные типы данных:

Числа имеют тип Number, который в зависимости от реализации может включать integer, real, float ( short-float, single-float, double-float, long-float).

Для операций с числами существуют функции сравнения, арифметические функции, тригонометрические функции: sin, cos, tan, atan, asin, acos, exp, (expt x y), (log x y) y – основание, по умолчанию – е. Есть также гиперболические функции.

(RANDOM X) – генерирует случайное число от 0 до X-1.

Символ – это структурный объект, состоящий из 4-х компонент: имя; значение; определение функции; список свойств.

Предикаты:

BOUNDP –проверяет, есть ли у символа значение;

FUNCTIONP - проверяет, связано ли с символом определение функции, макроса или специальной формы.

Строка - это константа, записывается в двойных кавычках.

(setq x “строка”) => “строка”

#\ х - знак элемента строки.

Знак строки может быть неотображаемым, например

#\ return – перевод строки

#\ tab – табуляция

Выбор элемента строки (индексация с 0)

(char строка n)

Пример:

(char x 3) => #\о

Изменение элемента строки:

(setf (char строка n) # символ)

Пример:

(setf (char x 4) #\п) => #\п

X => «стропа»

Сравнение строк

(string= строка1 строка2)

Проверяется логическая идентичность строк с учетом регистра.

Массивы. Массивы создаются формой:

(MAKE-ARRAY (N1 N2 … NM) режимы)

Функция возвращает в качестве значения новый объект – массив. NJ – размер по J-й размерности; размерность 0 – один элемент; 1 – вектор, 2 – матрица и т.д.

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

Если тип элементов массива известен, то это специализированный массив.

(setq mass (make-array 10

:initial-element 'c)) => #(C C C C C C C C C C)

(make-array '(2 4)

:element-type '(unsigned-byte 2)

:initial-contents '((0 1 2 3) (3 2 1 0)))

=> #2A((0 1 2 3) (3 2 1 0))

setq b (make-array '(2 3 ) :initial-element '3) => #2A((3 3 3) (3 3 3))

setf (aref b 1 2) 'c) => C

b => #2A((3 3 3) (3 3 C)) - индексация элементов массива с начинается с 0.

Ссылка на элемент массива осуществляется с помощью функции:

(AREF массив n1n2 … nM)

SETF – функция присваивания.

setq d (aref b 1 2) => C

(setf (aref mass 0) "aaa" ) => "aaa"

Кроме массивов с численными индексами можно работать с хэш-массивами. Если с помощью массива можно связать Лисповские объекты с числовыми значениями индексов, то хэш-массив связывает два произвольных Лисповских объекта (атомы, списки, массивы, хэш-массивы и т.д.)

При работе с хэш-массивами в качестве индекса элемента массива используется указатель на Лисповский объект.

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

Структуры – составной тип данных, который используется для отображения объектов предметной области.

Определение структурного типа производится с помощью макроса:

(defstruct имя типа

компонента1

…

компонентаN)

Например, определим структуру «точка на плоскости»:

(defstruct point x y) => POINT

Или

(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 1000 :type short-float :read-only t))

Каждая компонента (слот) содержит короткое вещественное, последний слот не может быть изменен, после того как структура создана.

Могут быть следующие опции для слотов:

:type  - тип. Содержимое слота всегда имеете этот тип.

:read-only x. Если x  -  true, слот не может быть изменен.

Создание экземпляра структуры

(defstruct (door (:conc-name dr-)) color width material) => DOOR

(setq my-door (make-door :color 'red :width 5.0))

=> #S(DOOR :COLOR RED :WIDTH 5.0 :MATERIAL NIL)

(dr-width my-door) => 5.0

(setf (dr-width my-door) 43.7) => 43.7

(dr-width my-door) => 43.7

Для самой структуры могут быть следующие опции:

:conc-name – автоматический префикс для имен слотов в функциях чтения (доступа). По умолчанию в качестве префикса используется имя структуры.

(defstruct (door (:conc-name dr-)) color width material) => DOOR

(setq my-door (make-door :color 'red :width 5.0))

=> #S(DOOR :COLOR RED :WIDTH 5.0 :MATERIAL NIL)

(dr-width my-door) => 5.0

(setf (dr-width my-door) 43.7) => 43.7

(dr-width my-door) => 43.7

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

Пример программы на Лиспе. Дифференцирование выражений. Напишем программу дифференцирования алгебраических выражений. Для наглядности ограничимся алгебраическими выражениями в следующей форме: (+ x y) (* x y)

Сложение и умножение можно свободно комбинировать. Например, (*(+ a ( * a b)) c). Программируя непосредственно получаем:

(defun diff0 ( l x)

(cond (( atom l)

(if (eq l x) 1 ;l=1

0));l=константа

(( eq (first l) '+)

(list '+

(diff0 (second l) x)

(diff0 (third l) x)))

(( eq (first l) '*)

(list '+

(list '*

(diff0 (second l) x)

(third l))

(list '*

(diff0 (third l) x)

(second l))))

(t l)))

Испoльзуем

(diff0 '(+ x (* 3 x)) 'x)

( + 1 (+ (* 0 x) (* 1 3))) = 4

(diff0 '(- x (* 3 x)) 'x) return

(- x (* 3 x))

(diff0 '(* x ( + x 1)) 'x)

(+ (* 1 ( x 1))(*(1 0) x))

Вычисляемые выражения не упрощаются, хотя это не трудно сделать.

Модульный подход. Эта программа неудобна, так как ее трудно расширять, приходится все группировать в один cond. Она не является модульной. Мы получим более удобное решение, если для каждого действия определим свою дифференцирующую функцию и через свойство diff свяжем эту функцию с символом, обозначающим действие.

Упрoстим запись самой дифференцирующей функции:

(defun dif1 (l x)

(cond (( atom l)

(if (eq l x) 1 0))

( t (funcall (get (first l) 'diff) (cdr l) x))))

Функции дифференцирования становятся значениями свойства 'diff:

(setf (get '+ 'diff) 'dif+)

(setf (get '* 'diff) 'dif*).

Таким образом, извлекаем действие из данных. Сами функции записываются:

(defun dif* (l x)

(list '+ (list '* (dif1 (first l) x)

(second l))

(list '* (dif1 (second l) x)

(first l))))

(defun dif+ (l x)

(list '+ (dif1 (first l) x) (dif1 (second l) x)))

Благодаря модульности можно дополнить для разности «-»

(defun dif- (l x)

(list '- (dif1 (first l) x) (dif1 second l) x)))

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

Можно использовать макросы. Определим макрос defdif, c помощью которого определяются дифференцирующие функции для новых действий:

(defmacro defdif (act args body)

`(setf (get ',act 'diff)

'(lambda,args,body)))

Тогда дифференцирующие функции задаются:

(defdif + (l x)

(list '+ (dif1 (first l) x) (dif1 (second l) x)))

(defdif * (l x)

(list '+ (list '* (dif1 (first l) x)

(second l))

(list '* (dif1 (second l) x)

(first l))))

(dif1 '(+ x x) 'x)

(defdif - (l x)

(list '- (dif1 (first l) x)

(dif1 (second l) x)))

(dif1 '(+ x (* 3 x)) 'x)

(dif1 '(- x (* 3 x)) 'x)

(dif1 '(* x ( - x 1)) 'x)

Интерфейс программы. Дополним программу несколькими функциями, обеспечивающими ввод информации (чтение дифференцируемого списка):

(defun read-list () (princ " diff-list ? ") (setq l (read))).

Пусть продолжаются вычисления до тех пор, пока не будет введено не d:

(defun d () (princ "enter command : d -diff; q - quit") (terpri)

(if (eq (read) 'd) (progn (read-list)

(print (dif1 l 'x ))

(terpri) (d))

'end))