Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

14.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ

795

являющееся его аргументом, рассматривается как функция (он часто сокра-

щается в конкретном синтаксисе до

#’

), второй образует значение функцио-

нального типа. Имя функции является и именем функционального блока.

Пример 14.2.1. Определение факториала, вызов анонимной функции и воз-

можность вычисления произвольного функционального выражения, создан-

ного в программе.

[1]> (defun fact (n) (if (= n 0) 1 (* (fact (- n 1)) n)))

FACT

[2]> (fact 40)

815915283247897734345611269596115894272000000000

[3]> ((lambda (x) (fact (* x x))) 5)

15511210043330985984000000

[55]> (setq g ’(lambda (x) (fact (* x x))))

(LAMBDA (X) (FACT (* X X)))

[56]> (eval (list g 3))

362880

Конец примера 14.2.1.

Нужно заметить, что определение функции с данным именем и значение

имени могут задаваться независимо. Например, мы можем в этом же кон-

тексте задать

(setq fact 7)

, хотя, конечно же, это отвратительный стиль про-

граммирования.

Конечно же, все формальные параметры функций являются локальными

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

другие свойства остаются глобальными! Пример смотри ниже.

[23]> (defun f (x) (progn (setf (get ’x ’weight) ’(25 kg)) (+ x 3)))

[24]> (setf (get ’x ’weight) ’(30 kg))

(30 KG)

[25]> (get ’x ’weight)

(30 KG)

[26]> (setq x 5)

[27]> (f 3)

[28]> x

796

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

[29]> (get ’x ’weight)

(25 KG)

LISP

имеется возможность создать анонимный блок со своими локаль-

ными переменными, не объявляя его функцией. Это называется связыванием

переменных и производится функцией

let

Внимание!Значение имени,унаследованного извне,все равно будет внеш-

ним! Смотрите пример ниже.

[32]>(setq a ’(b c d))

(B C D)

[33]>(setq b 5)

[34]> (list (let ((b 6)) (eval (car a))) (eval (car a)))

(5 5)

[35]> (list (let ((b 6)) b) (eval (car a)))

(6 5)

[36]> (list (let ((b 6)) (list b a)) (eval (car a)))

((6 (B C D)) 5)

[37]> (list (let ((b 6)) (eval (car (list ’b a)))) (eval (car a)))

(5 5)

Важнейшей особенностью языка

LISP

и функционального программиро-

вания как стиля являются функционалы с аргументами-функциями. Они, в

частности, делают практически ненужными циклы. Например, рассмотрим

пример возведения всех членов кортежа в квадрат.

[57]> (setq a (list 1 5 7 9 11 13 15 19 22 28))

(1 5 7 9 11 13 15 19 22 28)

[58]> (mapcar (function (lambda (x) (* x x))) a)

(1 25 49 81 121 169 225 361 484 784)

Функционал

mapcar

применяет свой первый аргумент ко всем членам

второго.

Тем не менее в языке

LISP

есть конструкции циклов, как дань програм-

мистской традиции. Чужеродность циклов подчеркивается тем. что они все-

гда выдают значение

NIL

И, наконец, приведем пример, любезно предоставленный Л. Городней.

Пример 14.2.2. Посмотрите сами, какую из рассмотренных ранее задач ре-

шает данная программа.

14.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ

797

Программа 14.2.1

;==============================================================

;

свертка/развертка системы текстов

;

текст представлен списком

;

((Имя Вариант ...)...)

;

первое имя в свертке - обозначение системы текстов

;

(Элемент ...)

;

(Имя Лексема (Варианты))

;

((пример (ма (ш н)

;

(ш а) )

;

( ш н ) )

;

((н ина)) )

;======================================================

;

реализация свертки:

unic, ass-all, swin, gram, bnf

(defun unic (vac) (remove-duplicates (mapcar ’car vac) ))

;;

список уникальных начал

(defun ass-all (Key Vac)

;;

список всех вариантов продолжения (что может идти за ключом)

(cond

((Null Vac) Nil)

((eq (caar Vac) Key) (cons (cdar Vac)

(ass-all Key (cdr Vac)) ))

(T (ass-all Key (cdr Vac)) )

) )

(defun swin (key varl) (cond

;;

очередной шаг свертки или снять скобки при отсутствии вариантов

((null (cdr varl))(cons key (car varl)))

(T (list key (gram varl)) )

))

(defun gram (ltext)

;;

левая свертка, если нашлись общие начала

( (lambda (lt) (cond

798

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

((eq (length lt)(length ltext)) ltext)

(T (mapcar

#’(lambda (k) (swin k (ass-all k ltext ) ))

lt )

) ) ) (unic ltext)

) )

(defun bnf (main ltext binds) (cons (cons main (gram ltext)) binds))

;;

приведение к виду БНФ

;======================================================

;

реализация развертки

: names, words, lexs, d-lex, d-names,

; h-all, all-t, pred, sb-nm, chain, level1, lang

(defun names (vac) (mapcar ’car vac))

;;

определяемыя символы

(defun words (vac) (cond

;;

используемые символы

((null vac) NIL)

((atom vac) (cons vac NIL ))

(T (union (words(car vac)) (words (cdr vac)))) ))

(defun lexs (vac) (set-difference (words vac) (names vac)))

;;

неопределяемые лексемы

(defun d-lex ( llex)

;;

самоопреление терминалов

(mapcar #’(lambda (x) (set x x) ) llex) )

(defun ( llex)

;;

определение нетерминалов

(mapcar #’(lambda (x) (set (car x )(cdr x )) ) llex) )

(defun h-all (h lt)

;;

подстановка голов

(mapcar #’(lambda (a)

(cond

14.2. МОДЕЛЬ ВЫЧИСЛЕНИЙ

799

((atom h) (cons h a))

(T (append h a)) )

) lt) )

(defun all-t (lt tl)

;;

подстановка хвостов

(mapcar #’(lambda (d)

(cond

((atom d) (cons d tl))

(T(append d tl))

) ) lt) )

(defun pred (bnf tl)

;;

присоединение предшественников

(level1 (mapcar #’(lambda (z) (chain z tl )) bnf) ))

(defun sb-nm (elm tl)

;;

постановка определений имен

(cond

((atom (eval elm)) (h-all (eval elm) tl))

(T (chain (eval elm) tl))

) )

(defun chain (chl tl)

;;

сборка цепочек

(cond

((null chl) tl)

((atom chl) (sb-nm chl tl))

((atom (car chl))

(sb-nm (car chl) (chain (cdr chl) tl) ))

(T (pred (all-t (car chl) (cdr chl)) tl)) ))

(defun level1 (ll)

;;

выравнивание

(cond

((null ll)NIL)

800

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

(T (append (car ll) (level1 (cdr ll)) )) ))

(defun lang ( frm )

;;

вывод заданной системы текстов

(d-lex (lexs frm))

(d-names frm)

(pred (eval (caar frm)) ’(())

) )

Конец примера 14.2.2.

§ 14.3. ОБЪЕКТЫ И LISP

Стандартная надстройка над

Common Lisp

, имитирующая объектно-ори-

ентированный стиль, это модуль

CLOS — Common Lisp Object System

. Са-

ма по себе объектность не дает никакого выигрыша по сравнению с языком

LISP

, поскольку возможности динамического вычисления функций в

LISP

даже шире. Видимо, именно поэтому в

CLOS

имеются две интересных мо-

дификации, делающие его не совсем похожим на стандартное ООП.

Начнем с понятия структуры данных в языке

Common Lisp

. Структура

определяется функцией

defstruct

вида

(defstruct pet name (species ’cat) age weight sex)

Задание структуры автоматически задает функцию-конструктор структуры

make-pet

, которая может принимать ключевые аргументы для каждого из по-

лей:

(make-pet :nick ’Viola :age ’(3 years), :sex ’femina))

и функции доступа для каждого из полей, например,

pet-nick

, использующу-

юся для получения значения поля или ссылки на него. Если поле не иници-

ализировано ни по умолчанию, ни конструктором, оно получает начальное

значение

NIL

.Никакой дальнейшей спецификации полей структур нет

,спис-

ки являются столь общей структурой данных, которая провоцирует игнори-

рование типов данных.

В объекте для каждого поля могут явно указываться функции доступа и

имена ключевых парамеров для инициализации аргументов.

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

14.3. ОБЪЕКТЫ И LISP

801

(defclass pet (animal possession) (

(species :initform ’cat)

(nick :accessor nickof

:inintform ’Pussy

:initarg namepet)

)

Этот класс наследует поля, функции доступа и прочее от классов

animal

possession

.Например, поле

cost

имеется в значении класса, если оно имеется

в одном из этих классов. Поскольку статических типов у полей нет, нет и

конфликтов.

Основная функция наследования в

CLOS

— определение упорядочения

на классах. С каждым классом связано свое упорядочение. Наследник мень-

ше своих предков, из предков меньшим считается тот, который раньше пе-

речислен в списке наследования при определении класса.

CLOS

достраива-

ет этот частичный порядок до линейного. Способ пополнения порядка мо-

жет быть в любой момент и без оповещения изменен, и хакерское исполь-

зование особенностей конкретного пополнения считается грубой стилисти-

ческой ошибкой. Если система находит несовместимость в определении по-

рядка, то она выдает ошибку, как в следующем примере:

[6]> (defclass init () ())

#<STANDARD-CLASS INIT>

[7]> (defclass a (init) ())

#<STANDARD-CLASS A>

[8]> (defclass b (init) ())

#<STANDARD-CLASS B>

[9]> (defclass c1 (a b) ())

#<STANDARD-CLASS C1>

[10]> (defclass c2 (b a) ())

#<STANDARD-CLASS C2>

[11]> (defclass contr (c1 c2) ())

*** - DEFCLASS CONTR: inconsistent precedence graph,

cycle (#<STANDARD-CLASS A> #<STANDARD-CLASS B>)

Типы в

LISP

есть, но они определяются динамически. В частности, если

атому придано как значение действительное число, его тип будет

ﬂoat

CLOS

могут задаваться методы, отличающиеся от функций тем, что их

аргументы специфицированы, например,

802

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

(defmethod inspectpet ((x pet) (y ﬂoat))

(setf weightofanimal3.5))

Как видно из примера, методы не обязательно связа-

ны с классами. Они могут быть связаны с любыми типами. Методы в языке

LISP

могут иметь дополнительные спецификации. О том, как эти специфи-

кации взаимодействуют с упорядочением типов классов, можно судить, рас-

смотрев следующую программу и генерируемый при ее исполнении резуль-

тат.

Программа 14.3.1

(defclass thing ()

((weight :initform ’(0 kg)

:accessor weightof

:initarg :weight)))

(defclass animal (thing)

((specie :accessor specieof

:initarg :spec)

(sex :accessor sexof

:initform ’m

:initarg :sex)))

(defclass possession (thing)

((owner :accessor ownerof

:initform ’nnn)

(cost :accessor costof

:initform ’(0 bucks)

:initarg :cost))

)

(defclass person (animal)

((specie :initform ’human)

(name :initarg :thename

:accessor nameof)))

(defclass pet (animal possession)

((nick :initarg :thenick

:accessor nickof)

(specie :initform ’cat)))

(defmethod act :before ((p pet))

(print "Cat mews"))

14.3. ОБЪЕКТЫ И LISP

803

(defmethod act :after ((p pet))

(print "Cat turns"))

(defmethod act :around ((p pet))

(progn (print "You have a cat") (call-next-method)))

(defmethod act ((p animal))

(progn (print "Animal is close to you") (call-next-method)))

(defmethod act :before ((p animal))

(print "You see an animal"))

(defmethod act :after ((p animal))

(print "You send the animal off"))

(defmethod act :around ((p animal))

(progn (print "You don’t like wild animals") (call-next-method)))

(defmethod act ((p possession))

(progn (print "You test your property") (call-next-method)))

(defmethod act :before ((p possession))

(print "You see your property"))

(defmethod act :after ((p possession))

(print "You are pleased by your property"))

(defmethod act :around ((p possession))

(progn (print "You admire your property if it is in good state") (call-next-method)))

(defmethod act ((p thing))

(print "You take the thing"))

(defmethod act :before ((p thing))

(print "You see something"))

(defmethod act :after ((p thing))

(print "You identiﬁed this thing"))

(defmethod act :around ((p thing))

(progn (print "You are not interested in strange things") (call-next-method)))

(act (make-instance ’pet :thenick "Viola" :cost ’(25 kop)))

При загрузке этого файла происходит следующее:

[1]> (load ’myclasses)

;; Loading ﬁle E:\clisp-2000-03-06\myclasses.lsp ...

804

ГЛАВА 14. ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

"You have a cat"

"You don’t like wild animals"

"You admire your property if it is in good state"

"You are not interested in strange things"

"Cat mews"

"You see an animal"

"You see your property"

"You see something"

"Cat purrs"

"Animal is close to you"

"You test your property"

"You take the thing"

"You identiﬁed this thing"

"You are pleased by your property"

"You send the animal off"

"Cat turns"

;; Loading of ﬁle E:\clisp-2000-03-06\myclasses.lsp is ﬁnished.

Как видите, упорядоченность классов по отношению наследования по-

зволяет выстраивать целые последовательности действий при вызове одного

метода.

Поскольку в

CLOS

нет ни механизмов скрытия конкретных представле-

ний, ни механизмов замены прямого доступа к данным на функции, ни дру-

гих характерных особенностей ООП, мы видим еще один пример того, как

модным словом прикрывается совершенно другая (и на самом деле не менее

интересная) сущность: начатки планирования действий по структуре типов

данных.

Такое неадекватное теоретизирование, как мы уже не раз убеждались, за-

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

вить ее реальные достониства.

Вопросы для самопроверки

1. Из примера 14.2.1 можно извлечь информацию о целых числах в языке

LISP

. Сделайте это.

2. Из программы 14.2.1 установите, что является в

LISP

признаком ком-

ментария.