Массивы. Макросы. Пример программы на лиспе
ЛЕКЦИЯ 9.
Массивы. Макросы. Пример программы на лиспе. Дифференцирование выражений.
Содержание
9.1 Массивы.
Для хранения большого количества данных в лиспе используются массивы.
Массив - это переменных, ячеек, имеющих одно имя, но разные номера, обеспечивающие доступ к этим ячейкам.
9.1.1 Определение массива
Для определения массива заданной размерности используется функция make-array
(make-array ) поддерживаются только одномерные массивы-векторы.
Пример :
(setq data (make-array 10))
#
(0 0 0 0 0 0 0 0 0 0)
data - имя массива,
0 - начальное наполнение.
9.1.2 Доступ к ячейке массива.
Доступ производится с помощью функции aref. AREF имеет два аргумента - имя массива и индекс и возвращает значение ячейки
(aref )
* (aref data 8)
0,
так как там записан 0.
Особенности: первый аргумент не блокируется, первая ячейка имеет номер 0.
9.1.3 Запись данных в массив.
Поместить данные в массив можно ,используя функцию setf
* (setf (aref data 2) 'dog)
aref -вызывает значение ячейки, функция setf помещает значение.
Рассмотрим массив testdata
(setq testdata (make-array 4))
#
* (setf (aref testdata 1) 'dog)
* (setf (aref testdata 0) 18 )
* (setf (aref testdata 2) '(a b) )
* (setf (aref testdata 3) 4 )
Можно (setq testdata ( vector 18 'dog '(a b) 0)) (aref d 1)
В результате получим
testdata 0 1 2 3
18 dog (a b) 0
Можно использовать эти данные
(cons (aref testdata 1) (list (aref testdata 3)
(aref testdata 2)))
(dog 0 ( a b))
(aref testdata (aref testdata 3))
18
9.1.4 Обработка массивов.
Так как доступ к элементам массива производится по номерам, то удобно использовать численные итерации и рекурсии.
Рассмотрим функцию, которая берет два аргумента имя массива и его длину и возвращает все значения, помещенные в список
(defun array-list (arnam len)
(do (( i 0 ( + 1 i))
( result nil (append result (list (aref arnam i)))))
(( equal i len) result)))
(array-list testdata 4)
( 18 dog (a b) 0)
9.1.5 Длина массива.
(array-length ) возвращает длину массива.
(array- length testdata) возвращает длину массива 4.
9.2 Обратная блокировка.
Обычная блокировка не позволяет вычислять выражения
* '(a b c)
(a b c)
Иногда возникает необходимость вычислить только часть выражения.
Если
(setq b '(x y z))
И мы запишем
* `( a ,b c) ,то
b - будет вычислено и мы получим
(a (x y z) c)
` - обратная верхняя запятая обозначает блокировку, которая может частично сниматься запятой.
Обратная блокировка может использоваться при печати:
(setq n 'john)
(setq m 'Robert)
(print `(boys ,n and ,m))
(boys john and roberts)
Наиболее часто обратная блокировка используется в мощном средстве лиспа - макросах.
9.3.1 Макросы.
Это специальное средство,позволяющее формировать вычисляемое выражение в ходе выполнения программы.
Рассмотрим например функцию blancs, которая производит n переводов каретки (пропускает n линий)
(defun blancs (n)
(do ((count n ( - count 1)))
(( zerop count) nil)
(terpri)))
(blancs 4) пропустит четыре строки.
Будем писать программу, которая позволит выполнять некоторое действие n раз
Для blancs:
(do-times '(terpri) 4)
Или
(do-times '(print 'hello) 3)
Напечатает hello три раза
Можно через
eval определить
(defun do-times (operation n)
(do ((count n ( - count 1)))
(( zerop count) nil)
(eval operation)))
Это можно сделать также через специальную форму :
defmacro
(defmacro do-times (operation n)
` (do ((count ,n ( - count 1)))
(( zerop count) nil)
,operation))
Как видно, форма макро похожа на определение функции, но есть отличия:
1. Аргументы макро не вычисляются перед их использованием.
Тогда обращение записывается:
(do-times (print 'hello) 3)
2. Когда макро вызывается, лисп сначала вычисляет тело макро, а затем выполняет получившееся выражение.
Например,после обращения
(do-times (print 'hello) 3)
Получим
(do ((count 3 ( - count 1)))
(( zerop count) nil)
(print 'hello))
Этот список потом вычисляется.
Таким образом при вызове макро сначала вычисляется тело (этап называется расширением) и формируется выражение.
На втором этапе вычисляется полученное выражение, и полученное значение возвращается как результат.
Вызывая macro с разными аргументами получим разные результаты. Если мы вызываем:
(do-times (print count) 10)
После вычисления тела получим:
(do ((count 10 ( - count 1)))
(( zerop count) nil)
(print count))
Печатается числа от 10 до 1.
Можно определить функцию обратной печати чисел
(defun print-number (n)
(do-times (print count) n))
( print-number 5)
9.3.2 Разработка макро
При разработке макро необходимо выполнить три шага:
Пример. Надо определить макро
term-search, которая будет просматривать список и выделять первый элемент удовлетворяющий заданному условию.
Шаг1. Сформулируем пример. Запишем тело для поиска чисел:
(setq l '(s d 3 d)) (setq item 5) _ (do (( tail l (cdr tail))) ((null tail) nil) ( cond ((numberp (car tail)) (return (car tail))))) ~~~~~~~
Шаг2. Выделяем общие части список
lis - l и предикат
predicate - number.
Шаг3.Формируем макро
(defmacro term-search ( predicate lis) ` (do (( tail , lis (cdr tail))) ((null tail) nil) (cond ((,predicate (car tail)) (return (car tail))))))
9.4 Пример программы на лиспе. Дифференцирование выражений.
Напишем программу дифференцирования алгебраических выражений. Для наглядности ограничимся алгебраическими выражениями в следующей форме:
(+ 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)) Why? (diff0 '(* x ( + x 1)) 'x) (+ (* 1 ( x 1))(*(1 0) x))
Вычисляемые выражения не упрощаются,хотя это не трудно сделать.
9.5.1 Модульный подход.
Эта программа неудобна,так как трудно расширять,приходится все группировать в один
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)
9.5.2 Интерфейс программы.
Дополним программу несколькими функциями,обеспечивающими ввод информации:
Чтение дифф. списка
(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))
Вызов программы теперь (d)
9.5.3 Загрузка программы.
Можно сразу загружать программу и начать ее выполнение, для этого используют функцию
load
(load )
Записываются обычным образом,но \\ надо использовать двойные.
(load "diff1")
и сразу начинается выполнение.
