ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Дополнительные команды АМ для эффективной поддержки отложенных выражений Команда Пояснение LDE Загрузка отложенного выражения с созданием рецепта RPL Замена рецепта его результатом APN Возобновление отложенного выражения Вычисляться такими командами рецепт может не более чем один раз, и то если его результат действительно нужен. Таб л иц а 3 2 Дополнение АМ для эффективного выполнения отложенных действий Команда Результат s e (LDE f . c) d → ([F (f . e)] . s) e c d (x) e (RPL) ([F (F . e)] ee c . d) → (x . s) ee c d при этом ([F (F . e)] → [T x] 17 ([T x] . s) e (APN . c) d → (x .s) e c d ([F (f . e)] . s) ee (APN . c) d → Nil e f ([F (F . e)] ee c . d) Эффект отложенных вычислений можно продемонстрировать на обработке бесконечных структур данных, в которых продолжение структуры представлено как вычисление следующих элементов. Фрагмент Примечание (def beg (LAMBDA (k lst) (cond ((EQ k Nil)()) (T (cons (car lst) (beg (cdr k ) (eval (cons (cdr lst) Nil)) Вырезка начального отрезка 17 Включение в квадратные скобки «[ ]» здесь символизирует размещение по тому же адресу. 119 ) ) ) ) ) ) (def endless (LAMBDA (m) (cons m (lambda () (endless (cons m m)) )) ) ) (beg '(a b c) (endless 'A)) ; = (A (A . A) ((A . A) A . A )) Пример 24. Конструирование последовательности произвольной длины из бесконечного списка 5.5. Свойства атомов Методы расширения функциональных построений могут быть применены для моделирования привычного императивно-процедурного стиля программирования и техники работы с глобальными определениями. Здесь демонстрируется расширение базовой схемы обработки символьных выражений и представленных с их помощью функциональных форм на примере механизма списков свойств атомов. В результате можно собирать функционально полное определение гибкой и расширяемой реализации языка программирования, что и показано на примере Lisp-интерпретатора, написанном на Lisp-е. До сих пор атом рассматривался только как уникальный указатель, обеспечивающий быстрое выяснение различимости имен, названий или символов. Теперь описываются списки свойств, которые начинаются или находятся в указанных ячейках. Каждый атом имеет список свойств. Когда атом читается (вводится) впервые, тогда для него создается пустой список свойств, который потом можно заполнять. Список свойств устроен как специальная структура, подобная записям в Паскале, но указатели в такой записи сопровождаются тэгами, символизирующими тип хранимой информации. Первый элемент этой структуры расположен по адресу, который задан в указателе. Остальные элементы доступны по этому же указателю с помощью ряда специальных функций. Элементы структуры содержат различные свойства атома. Каждое свойство помечается атомом, называемым индикатором, или расположено в фиксированном поле структуры. Здесь достаточно принять к сведению, что реализация атомарных объектов – это сложная структура данных, в свою очередь представленная списками. 120 С помощью функции GETв форме (GET x i) можно найти для атома x свойство, индикатор которого равен i Значением (GET 'FF 'EXPR) будет (LAMBDA (X) (COND ... )) , если определение FF было предварительно задано с помощью (DEFUN FF (X)( COND ... )) Свойство с его индикатором может быть вычеркнуто – удалено из списка функцией REMPROP в форме (REMPROP x i) С середины 70-х годов возникла тенденция повышать эффективность разработкой специальных структур, отличающихся в разных реализациях. Существуют реализации, например, muLisp, допускающие работу с представлениями атома как с обычными списками посредством функций CAR , CDR 5.6. Гибкий интерпретатор В качестве примера повышения гибкости определений приведено упрощенное определение Lisp-интерпретатора на Lisp-е, полученное из М- выражения, приведенного Дж. Маккарти в описании Lisp 1.5. Ради удобочитаемости здесь уменьшена диагностичность, нет пост- вычислений и формы PROG. Lisp хорошо приспособлен к оптимизации программ. Любые совпадающие подвыражения можно локализовать и вынести за скобки, как можно заметить по передаче значения. Определения функций хранятся в ассоциативном списке, как и значения переменных. Функция SUBR – вызывает примитивы, реализованные другими, обычно низкоуровневыми, средствами. ERROR – выдает сообщения об ошибках и сведения о контексте вычислений, способствующие поиску источника ошибки. Уточнена работа с функциональными аргументами. Определение Примечание (DEFUN EVAL (e al ) (COND ((EQ e NIL ) NIL ) ((ATOM e )((LAMBDA (v ) (COND (v (CDR v ) ) (T (ERROR 'undefvalue )) ) ) (ASSOC e al ) ) ) ((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) ) Диагностика Однократность вычисления значения 121 ((EQ (CAR e) 'FUNCTION ) (LIST 'CLOSURE (CADR fn ) al ) ) ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) (T (apply (CAR e)(evlis (CDR e) al ) al ) ) ) ) Замыкание функционального аргумента Пример 25. Диагностика отсутствия определений при вычислении форм Определение Примечание (DEFUN APPLY (fn args al ) (COND ((EQ e NIL ) NIL ) ((ATOM fn ) (COND ((MEMBER fn '(CAR CDR CONS ATOM EQ )) (SUBR fn agrs al )) (T (APPLY (EVAL fn al ) args al )) ) ) ((EQ (CAR fn ) 'LABEL ) (APPLY (CADDR fn ) args (CONS (CONS (CADR fn )(CADDR fn )) al ) ) ) ((EQ (CAR fn ) ' CLOSURE) (APPLY (CDR fn ) args (CADDR fn)) ) ((EQ (CAR fn ) 'LAMBDA ) (EVAL (CADDR fn ) (APPEND (PAIR (CADR fn ) args ) al )) (T (APPLY (EVAL fn al ) args al )) ) ) Локализация списка встроенных подпрограмм Выполнение подпрограмм Именование локальных функций Применение функционального аргумента Пример 26. Применение подпрограмм и функциональных параметров Определения ASSOC , APPEND , PAIR , LIST – стандартны. Определение Примечание (DEFUN evcon (c a) (COND ((null c) Nil) ((evel (car c) a) (evel (cadr c) a) ) ( T (evel (caddr c) a) ) )) Возможно отсутствие ветви Пример 27. Выбор ветви 122 Определение Примечание (DEFUN evlis (m a) (COND ( m (cons(evel (car m) a) (evlis(cdr m) a) ) ) ) ) Пока «M» не пуст, присоединяем значение его первого элемента к списку значений остальных элементов Пример 28. Вычисление параметров 5.7. Функциональная модель взаимодействия монад Примерно то же самое обеспечивают EVAL-P и APPLY-P , рассчитанные на использование списков свойств атома для хранения постоянных значений и функциональных определений. Индикатор MONAD указывает в списке свойств атома на правило интерпретации функций, относящихся к отдельной монаде, MACRO – на частный метод построения представления функции. Функция VALUE реализует методы поиска текущего значения переменной в зависимости от контекста и свойств атомов. Определение Примечание (DEFUN EVAL-P (E C) (COND ((ATOM E) (VALUE E C)) ((ATOM (CAR E))(COND ((GET (CAR E) 'MONAD) ((GET (CAR E) ' MONAD) (CDR E) C) ) (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C)) ) ) (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C)) )) До применения функции выясняем еѐ категорию Пример 29. Функции разных категорий 123 Определение Примечание (DEFUN APPLY-P (F ARGS C) (COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C)) ((ATOM (CAR F))(COND ((GET (CAR F) 'MACRO) (APPLY-P ((GET (CAR F) 'MACRO) (CDR F) C) ARGS C)) (T (APPLY-P (EVAL F E) ARGS C)) ) ) (T (APPLY-P (EVAL F E) ARGS C)) )) Для макрофункций нет необходимости в вычислении аргументов Пример 30. Специальные макрофункции поддерживают пост-вычисления параметров Или то же самое с вынесением общих подвыражений во вспомогательные параметры. Определение Примечание (DEFUN EVAL-P (E C) (COND ((ATOM E) (VALUE E C)) ((ATOM (CAR E)) ((LAMBDA (V) (COND (V (V(CDR E) C) ) (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C)) )) (GET (CAR E) ' MONAD) ) ) (T (APPLY-P (CAR E)(EVLIS (CDR E) C) C)) )) Однократный поиск категории Пример 31. Исключение лишнего поиска свойства MONAD Определение Примечание (DEFUN APPLY-P (F ARGS C) (COND ((ATOM F)(APPLY-P (FUNCTION F C) ARGS C)) ((ATOM (CAR F)) ((LAMBDA (V) (COND (V (APPLY-P (V (CDR F) C) ARGS C)) (T (APPLY-P (EVAL F E) ARGS C)) ))(GET (CAR F) 'MACRO) )) (T (APPLY-P (EVAL F E) ARGS C)) )) Однократный поиск свойства Пример 32. Исключение лишнего поиска свойства MACRO 124 Расширение системы программирования при таком определении интерпретации осуществляется простым введением/удалением соответствующих свойств атомов и функций. Полученная схема интерпретации допускает разнообразные категории функций, реализуемые как отдельные монады, и макросредства конструирования функций, позволяет задавать различные механизмы передачи параметров функциям. Так, в языке Clisp различают кроме обычных, обязательных и позиционных ещѐ и необязательные (факультативные), ключевые и серийные (многократные, с переменным числом значений) параметры. При разработке и отладке программ происходит развитие средств и методов обработки данных, что приводит к изменению типов представления объектов. Объекты из неопределенных становятся константами или переменными, из обработки скаляров формируется обработка структур данных, от структур данных вероятен переход к функциям и файлам и т. п. Не менее существенное развитие происходит и на уровне постановки задачи. Задача из новой, решение которой имеет ранг пробы или демонстрации, становится направлением исследования, в котором созревают практичные или точные подзадачи, возможен и переход к поиску решений на пределе возможностей оборудования. Требования к средствам и методам решения задач на столь различных уровнях изученности привели к гибкости, присущей парадигме функционального программирования. Определение Примечание (DEFUN eval(e a) (COND ( (atom e) (cdr(assoc e a)) ) ( (eq (car e) 'QUOTE) (cadr e)) ( (eq(car e) 'COND) (evcon(cdr e) a)) ( T (apply (car e) (evlis(cdr e) a) a) )) ) (DEFUN apply (fn x a) (COND ((atom fn)(cond ((eq fn 'CAR) (caar x)) ((eq fn 'CDR) (cdar x)) ((eq fn 'CONS) (cons (car x)(cadr x)) ) ((eq fn 'ATOM) (atom (car x)) ) ((eq fn 'EQ) (eq (car x)(cadr x)) ) (T (apply (eval fn a) x a)) ) ) ) Переменная Константа Ветвление Применение функции. Элементарные функции Программируемые 125 ((eq(car fn)'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a) )) ((eq (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn)(caddr fn)) a))))) (DEFUN evcon (c a) (COND ((eval (car c) a) (eval (cadr c) a) ) ( T (eval (caddr c) a) ) )) (DEFUN evlis (m a) (COND ((null m) Nil ) ( T (cons(eval (car m) a) (evlis(cdr m) a) )) ) функции Безымянная функция Именованная функция Выбор ветви Вычисление параметров Пример 33. Самоописание Lisp-интерпретатора, предложенное Дж. Маккарти в начале 1960-х годов Наиболее очевидные следствия из выбранных принципов ФП: – процесс разработки программ разбивается на фазы: построение базиса и его пошаговое расширение; – рассмотрение программы как реализации алгоритма естественно дополняется табличной реализацией функций, т. е. допустимо использование хранимых графиков функций в виде структур из аргументов и соответствующих результатов наряду с процедурами; – прозрачность ссылок обеспечена совпадением значений одинаково выглядящих формул, вычисляемых в одинаковом контексте; – предпочтение универсальных функций и функционально полных систем, трудоемкость первичной реализации которых компенсируется надежностью определений и простотой применения. Язык программирования Lisp и сложившееся на его основе функциональное программирование реально показали свои сильные стороны как инструментарий исследования и освоения новых областей применения вычислительной техники. Это аргумент в пользу функционального подхода к решению новых сложных задач: – доступны преобразования программ и процессов; – осуществима лингвистическая обработка информации; – поддерживается гибкое управление базами данных; – возможна оптимизация информационных систем, вплоть до полного исключения потерь информации; – моделирование общения. 126 5.8. Спецификация Таб л иц а 3 2 Парадигматическая характеристика языков, поддерживающих функциональное программирование Параметр Конкретика Эксплуатационная прагматика ЯП Исследование потенциального максимума возможностей решения сравнительно новой задачи. Регистры абстрактной машины S E C D S – стек операндов и чистого результата. E – стек значений локальных переменных C – стек исполняемой программы. D – стек защиты контекста от случайных искажений. Категории команд абстрактной машины Как в Pure Lisp. Реализационная прагматика Данные строятся из тэгированных указателей с автоматизацией повторного использования памяти. Система программирования использует пару интерпретатор-компилятор функций. При связывании переменных используются стек, ассоциативный список и список свойств атомов. Парадигматическая специфика Система программирования обычно поддерживает механизмы других парадигм, возможно выделенные в отдельные подсистемы (монады в языке Haskell). 127 ЛЕКЦИЯ 6. ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Исследовательская и проектная работы обычно проходят фазу поиска практичного решения. Логическое программирование (ЛП) для поддержки этой фазы предлагает важное отступление от концепции определения подпрограмм, процедур и функций. В качестве укрупненного определения действий допускаются варианты, равноправно выбираемые из конечного множества так называемых «клауз». По мере изучения задачи это множество можно пополнять в произвольном порядке. Именно эта идея составляет одну из привлекательных особенностей ЛП, выделившегося в самостоятельную парадигму. Равноправие не распространяется лишь на тупиковую ситуацию, когда ни один предложенный вариант не приводит к целевому результату. Парадигма логического программирования использует идею автоматического вывода информации на основе заданных фактов и правил. Логическое программирование основано на теории и аппарате формальной логики. Написанная согласно формальной логике программа является множеством логических форм, представляющих факты и правила относительно некоторой предметной области. Основным языком логического программирования признан Prolog , хотя известны и другие – Planner, ASP и Datalog Во всех таких языках правила имеют форму клауз: H :- B1 1 , …, BN n , понимаемую как логическое следование if (B1 1 and … and BN) then H или B11 & … & BN → H H называют головой правила, а B1 1 , …, BN – телом. Факты – это правила без тела. Различают атомарные и составные клаузы. Предикаты, образующие тело, могут быть выражены в стиле сопоставления с образцом. Важный механизм – использование отрицаний в теле клауз, что приводит к немонотонной логике. Логика программ может использовать процедурный стиль при вычислении целей: to solve H, solve B 1 , and ... and solve B n 128 Декларативный подход к пониманию программ требует от программиста систематической проверки корректности. Более того, используются преобразования логических программ в их более эффективные эквиваленты, что сближает ЛП с макротехникой. Для повышения эффективности программ программисту следует знать особенности поведения механизма вычислений и границы вычислимости используемых выражений. 6.1. Операционная семантика Логическое программирование сводит обработку данных к выбору произвольной композиции определений (уравнений, предикатных форм), дающей успешное получение результата. Именно обработка формул является основой – вычисления рассматриваются как операция над формулой. При неуспехе происходит перебор других вариантов определений. В языках ЛП считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном выборе. Перебор вариантов выглядит как обход графа в глубину. Имеются средства управления перебором с целью исключения заведомо бесперспективного поиска. Интерпретирующий автомат для выполнения недетерминированных процессов можно представить как цикл продолжения вычислений при попадании в диагностическую ситуацию. Продолжение заключается в выборе другого варианта из набора определений функционального объекта. Вычисление признается неудачным, лишь если не удалось подобрать комплект вариантов, позволяющий вычислить значение формулы. В отличие от множества элементов набор вариантов не требует одновременного существования всех составляющих. Поэтому программирование вариантов можно освободить от необходимости формулировать все варианты сразу. В логическом программировании можно продумывать варианты отношений между образцами формул постепенно, накапливая реально встречающиеся факты и их сочетания. Содержательно такой процесс похож и на уточнение набора обработчиков прерываний на уровне оборудования. Кроме основной программы, выполняющей целевую обработку данных, отлаживается коллекция диагностических реакций и процедур продолжения счета для разного рода неожиданных событий, препятствующих получению результата программы. Следует иметь в виду, чтоварианты не образуют иерархии. Их аксиоматика подобна так называемой упрощенной теории множеств. 129 Принципиальная особенность – совпадение предикатов принадлежности и включения. Если варианты в таком выражении рассматривать как равноправные компоненты, то неясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов. Чтобы решить эту задачу, в системах ЛП вводится специальная форма ESC (ТУПИК), действие которой заключается в том, что она как бы «старается» по возможности не исполняться. Иными словами, при выборе вариантов предпочитаются варианты, не приводящие к исполнению формы ESC. Такая же проблема возникает при обработке пустых цепочек в грамматиках. Аналогичная проблема решена при моделировании процессов интерпретированными сетями Петри соглашением о приоритете нагруженных переходов в сравнении с пустыми. АС сводим к формуле: (факт | (предикат цель) | ESC) AML = В книге Хендерсона [15] приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов. s e c d r → s' e' c' d' r' Таб л иц а 3 3 |