globalf5-240972240972 (850810), страница 27
Текст из файла (страница 27)
( Слот — это поле записи или списка свойств.) Чтобы сделатьпредставителя класса, мы вызываем общую функцию:(SETF с (make-instance 'ob))Чтобы задать значение поля, используем специальную функцию:(SETF (slot-value c) 1223)До этого значения полей были не определены.181Л.В. ГородняяОсновы функционального программированияСвойства слотовПростейшее определение слота — это его имя. Но в общем случае слотможет содержать список свойств. Внешне свойства слотаспецифицируются как ключевые параметры функции. Это позволяетзадавать начальные значения. Можно объявить слот совместноиспользуемым.:allocation :classИзменение такого слота будет доступно всем экземплярам объектовкласса. Можно задать тип элементов, заполняющих слот, и сопроводитьих строками, выполняющими роль документации.СуперклассНет необходимости все новые слоты создавать в каждом классе.Пример: ОО-определение Лисп-компилятора.;oop-compile(defclass expr ()((type :accessor td)(sd :accessor ft))(:documentation "C-expression"))(defclass un (expr); \_____суперкласс для унарных форм((type :accessor td) ;; можно унаследовать,(sd :accessor ft)) ;; а здесь не дублировать(:documentation "quote car *other *adr"))(defclass bin (expr)((type :accessor td)(sd :accessor ft)182Л.В.
ГородняяОсновы функционального программирования(sdd :accessor sd) )(:documentation "cons + lambda let"))(defclass trio (expr);; (bin) тогда можно не объявлять первые 3 поля((type :accessor td)(sd :accessor ft)(sdd :accessor sd)(sddd :accessor td) )(:documentation "if label"))(defmethod texrp ((x expr) (nt atom))(SETF (slot-value x 'type) nt)(SETF (td x) nt) ;;--;; variant(:documentation "объявляем тип выражения"))(defmethod spread ((hd (eql 'QUOTE))(tl expr))(let ( (x (make-instance 'un)) )(SETF (ft x) (car tl))(SETF (td x) hd)) (:documentation "распаковка выражения"))(defmethod compl ((hd (eql 'QUOTE))(tl expr))(list 'LDC tl)(:documentation "сборка кода"))(defmethod compl ((hd (eql 'CAR))(tl expr)) N)(append (compl(ft tl) N) '(CAR))(:documentation "сборка кода"))(defmethod spread ((hd (eql 'CONS))(tl expr))(let ( (x (make-instance 'bin)) )(SETF (ft x) ( CAR tl))(SETF (sd x) ( cadr tl))(SETF (td x) hd)183Л.В.
ГородняяОсновы функционального программирования) (:documentation "распаковка выражения"))(defmethod compl ((hd (eql 'CONS))(tl bin) N )(append (compl(sd tl) N) (compl(ft tl) N)'(CONS))(:documentation "сборка кода"))(defmethod compl ((hd (eql '+))(tl bin) N )(append (compl(ft tl) N) (compl(sd tl) N)'(ADD))(:documentation "сборка кода"))(defmethod spread ((hd (eql 'IF))(tl expr))(let ( (x (make-instance 'trio)) )(SETF (ft x) ( CAR tl))(SETF (sd x) ( cadr tl))(SETF (td x) ( caddr tl))(SETF (td x) hd)) (:documentation "распаковка выражения"))(defmethod compl ((hd (eql 'IF))(tl expr) N )(let ( (then (list (compl(sd tl) N) '(JOIN)))(else (list (compl(td tl) N) '(JOIN))) )(append (compl(ft tl) N) (list 'SEL then else)))(:documentation "сборка кода"))(defmethod parh ((x expt))(let (ftx (ft x))(COND((ATOM ftx) (spread 'ADR ftx))((member (CAR ftx)'(QUOTE CAR CONS + IF LAMBDA LABEL LET))(spread (CAR ftx) (CDR ftx))(T (spread 'OTHER ftx) )))(:documentation "шаг разбора"))184Л.В.
ГородняяОсновы функционального программирования;====test==========(SETF test1 (make-instance 'expr))(texpr test1 'expr)(SETF (slot-value test1 'sd) (READ))()(SETF e1 (make-instance 'expr))(SETF e2 (make-instance 'expr))(SETF e3 (make-instance 'expr))(print (tf e2))(SETF (slot-value e3 'type) 'expr)(print (tf e3))(SETF (slot-value e3 'sd) '(QUOTE const))(defmethod ep ((x expr))((LAMBDA (xt)(SETF (slot-value x 'type) xt) )(CAR (slot-value x 'sd)) ) )(print (ep e3))(print (tf e3))(print (td e3))(print (sd e3))(defmethod ep-q ((x (eql 'QUOTE)) (y expr))(SETF y (make-instance 'un)))(SETF (slot-value y 'type) 'QUOTE)(SETF (slot-value y 'sd) y)(print (tf (e3 'sd)))(print (tf e1))(print(SETF (slot-value e1 'type) (tf e1)))(SETF (slot-value e2 'sd) 'atom1)(print (tf (sd e2)))185Л.В.
ГородняяОсновы функционального программирования(print(SETF (slot-value e3 'sd) '(QUOTE const)))(print (tf e3))CLOS, естественно, использует модель обобщенных функций, но мынаписали независимую модель, используя более старые представления,тем самым показав, что концептуально ООП — это не более чемперефразировка идей Лиспа.
ООП — это одна из вещей, которую Лиспизначальноумеетделать.Дляфункциональногостиляпрограммирования в переходе к ООП нет ничего революционного.Такой переход практически не расширяет пространство предстоящихрешений. Это просто небольшая конкретизация механизмов перебораветвей функциональных объектов Императивному стилю ООПкомпенсирует избыточную целостность представления отлаживаемыхпрограмм, смягчает жесткость зависимости компонентов программы отпотока информационных процессов.Более интересный вопрос, что же нам еще может дать функциональныйстиль и лисповская традиция реализации систем программирования?Ответу на этот вопрос посвящены три следующие лекции.186Л.В. ГородняяОсновы функционального программированияВарианты, последовательности, множестваОписаны приемы организации недетерминированных вычислений врамках функционального стиля программирования.
Реализацияпрограмм с возвратами, перебор вариантов, откат влекут за собойрасширениесемантическогобазисамеханизмамиобработкипрерываний. Анализируется соответствие точности решения задач иуровня их изученности. Исследуются связь диагностическойинтерпретации и средств логического программирования. Обработкамножеств, последовательностей и хэш-таблиц дает материал дляпростых примеров.Недетерминированные процессыЕсть мнение, что однозначное решение задачи в виде четкого алгоритманад хорошо организованными структурами и упорядоченными данными— результат аккуратной, тщательной работы, пытливого и вдумчивогоизучения класса задач и требований к их решению.Эффективные и надежные программы в таких случаях — естественноевознаграждение.Но в ряде случаев природа задач требует свободного выбора одного извариантов — выбор произвольного элемента множества, вероятностисобытия при отсутствии известных закономерностей, псевдослучайные изменения в игровых обстановках и сценариях, поискпервого подходящего адреса для размещения блока данных в памяти,лингвистический анализ при переводе документации и художественныхтекстов и т.д.
При отсутствии предпочтений все допустимые вариантыравноправны, и технология их отладки и обработки должнаобеспечивать формально равные шансы вычисления таких вариантов.(Похожая проблема характерна для организации обслуживания в сетях ивыполнения заданий операционными системами. Все узлы и заданиясети должны быть потенциально достижимы, если нет формальногозапрета на оперирование ими.)Представление вариантов в чем-то подобно определению ветвлений,но без предикатов, управляющих выбором ветви. В некоторых языках,например, учебно-игрового характера, можно указать вероятность187Л.В. ГородняяОсновы функционального программированиявыбора варианта.
В языках логического и генетическогопрограммирования считают возможным прямой перебор вариантов,сопоставляемых с образцами, и организацию возвратов при неудачномвыборе.В отличие от множества элементов, набор вариантов не требуетодновременного существования всех составляющих, что по реализациинапоминает вариантные записи или объединения. Поэтому ипрограммирование вариантов можно освободить от необходимостиформулировать все варианты сразу. В логическом программированииможно продумывать варианты отношений между образцами формулпостепенно, накапливая реально встречающиеся сочетания, как иметоды обработки классов объектов в ООП.
Содержательно такойпроцесс похож и на уточнение набора обработчиков прерываний науровне оборудования. Кроме основной программы, выполняющейцелевую обработку данных, отлаживается коллекция диагностическихреакций и процедур продолжения счета для разного рода неожиданныхсобытий, препятствующих получению результата программы.Обычнопонятиеалгоритмаидетерминированными процессами.программысвязываютсНо эти понятия не очень усложняются, если допустить недетерминизм,ограниченый конечным числом вариантов, так что в каждый моментвремени из них существует только один вариант.По смыслу выбор варианта похож на выбор произвольного элементамножества.{ a | b | c } = э { a, b, c }Чтобы такое понятие промоделировать обычными функциональнымисредствами, нужны дополнительные примитивы.
Например, чтобыопределить выбор произвольного элемента из списка L, можнопредставить рекурсивное выражение вида:(любой L) = { ( CAR L)| (любой (CDR L)) }Если варианты в таком выражении рассматривать как равноправные188Л.В. ГородняяОсновы функционального программированиякомпоненты, то не ясно, как предотвратить преждевременный выборпустого списка при непустом перечне вариантов.Чтобы решить эту задачу, вводится специальная форма ESC ( ТУПИК ),действие которой заключается в том, что она как бы "старается" повозможности не исполняться. Иными словами, при выборе вариантовпредпочитаются варианты, не приводящие к исполнению формы ESC.(Такая же проблема возникает при обработке пустых цепочек вграмматиках.
Аналогичным образом эта проблема решена примоделировании процессов интерпретированными сетями Петри [17] —соглашением о приоритете раскрашенных переходов в сравнении спустыми.)Уточненное таким образом определение выбора произвольногоэлемента списка можно представить формулой вида:(любой L) = { (CAR L)| (любой (CDR L))| (if (nl L) ESC) }В какой-то момент L становится пустым списком, и его разбороказывается невозможным. Тогда действует ESC.Следует иметь в виду, что варианты не образуют иерархии.
Ихаксиоматика подобна так называемой упрощенной теории множеств.Принципиальнаяособенность—совпадениепредикатовпринадлежности и включения.Другие построения, характерные для теории множеств: { x | P(X)} — множество элементов, обладающих свойством P.Определение вида(F L) = {(if (P ( CAR L ))(CONS ( CAR L) (F ( CDR L))) )| (if (nl L) ESC) }недостаточно, т.к. порождаемые варианты элементов, удовлетворяющихзаданому свойству, существуют в разные моменты времени и могут несуществовать одновременно. Чтобы иметь все варианты одновременно,189Л.В. ГородняяОсновы функционального программированиятребуется еще один примитив ALL, обеспечивающий накопление всехреально осуществимых вариантов.(F L) = (ALL {(if (P ( CAR L ))(CONS ( CAR L) (F ( CDR L)) ) )| (if (nl L) ESC) } )Пересечение множеств A и B(ALL ( LAMBDA (x y) { (if (= x y) x)|ESC }) (любой A) (любой B) )Логические связкиЛогика McCarthy (компьютерная)a&b(if (not a) NIL b)b вычисляется лишь при истинном a, что результативно, но не всегдасоответствует интуитивным ожиданиям (логика, предложенная в своевремя McCarthy, позволяет добиться высокой эффективности).Математически более надежны варианты, исключающие зависимостьот порядка перебора:Более надежны варианты, исключающие зависимость от порядкаперебора:(( ALL( LAMBDA x { (if (not x) NIL )| ESC }){a | b} )Если a и b оба истины, то получается ESC.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
