Функциональное программирование

Массивы. Макросы. Пример программы на лиспе


ЛЕКЦИЯ 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")

    и сразу начинается выполнение.




    Содержание раздела