Компиляция. Венский метод. Операционная семантика
Функциональный подход к программированию наиболее убедительно выражен в Венской методике определения языков программирования. Эта методика разработана в конце 60-х годов [8]. Основная идея — использование абстрактного синтаксиса и абстрактной машины при определении семантики языка программирования. Конкретный синтаксис языка отображается в абстрактный — анализ, а абстрактная машина может быть реализована с помощью конкретной машины — кодогенерация, причем и то, и другое может иметь небольшой объем и невысокую сложность. Сущность определения языка концентрируется в виде так называемой семантической функции языка, выполняющей переход от абстрактного синтаксиса к абстрактной машине — трансляцию.
При такой архитектуре компилятор можно рассматривать как три комплекта функций, обеспечивающих анализ программы, ее трансляцию и кодогенерацию. Главная задача анализа — обнаружить основные понятия и выделить, вывести или вычислить по тексту программы значения компонентов структуры, представляющей собой абстрактный синтаксис программы. Эта работа сводится к набору распознавателей и селекторов, названия которых могут быть выбраны в зависимости от смысла понятий, составляющих программу, а реализация варьируется в зависимости от конкретного синтаксиса языка. Тогда при любом конкретном синтаксисе разбор программы выполняется тем же самым определением, что и анализ ее абстрактного представления, которое и
грает роль спецификации. Любое определение анализа выглядит как перебор распознавателей, передающих управление композициям из селекторов, выбирающих существенные компоненты из анализируемой программы и заполняющих поля определенной структуры или значениями, или программами их вычисления. Содержимое полей предназначено для генерации кода программы, эквивалентной исходному тексту программы, а заодно и ее абстрактной структуре. Например, если форму PROG рассматривать как представление абстрактного синтаксиса для подмножества языка Паскаль, содержащего переменные, константы, арифметические операции и сравнения, пустой оператор, присваивание, последовательное исполнение операторов, условный оператор и безусловный переход goto, то необходим набор распознавателей, выявляющих эти понятия, и селекторов, выделяющих их характеристики.
Селекторы имеют смысл лишь при истинности соответствующего распознавателя.
Использование списочных форм в качестве абстрактного синтаксиса позволяет все распознаватели свести к анализу головы списка.
| (перем X) | x |
| (конст C) | c |
| (плюс А1 А2) | (A1 + A2) |
| (равно А1 А2) | (A1 = A2) |
| (пусто) | |
| (присвоить X A) | x := a |
| (шаги S1 S2) | S1; S2; |
| (если P ST SF) | if p then ST else SF; |
| (пока P S) | while p do S; |
Определение семантической функции, обеспечивающей корректную трансляцию абстрактного синтаксиса программы в ее абстрактный код, требует реализации соответствия между именами и их значениями в зависимости от контекста и предшествующих определений.
При интерпретации такое соответствие представлялось ассоциативным списком, в котором хранятся связи вида Имя-Смысл, преобразуемые по принципу стека, естественно отражающего динамику вызова функций. При компиляции не принято сохранять имена на время исполнения программы: их роль выполняют сопоставленные именам адреса. Поэтому вместо а-списка вида ((а . 1)(в . 2)(с . 3)...) применяется два списка (а в с ...) и (1 2 3 ...), хранящих имена и их значения на согласованных позициях. Обрабатываются эти два списка синхронно: оба удлиняются или сокращаются на одинаковое число элементов.
Можно переписать Eval-Apply с соответствующей коррекцией и определить функцию подстановки, заменяющую имена их значениями из синхронного списка.
Определение Eval-Apply особенно компактно в стиле p-списка. Иерархию определений можно организовать с помощью блоков Flet со списками определений для шаблонов (перем конст плюс равно) и отдельно для (пусто присвоить шаги если пока).
Важно обратить внимание на учет изменения контекста при последовательном выполнении шагов программы, а также на несовпадение порядка в тексте с очередностью выполнения композиций функций. Формально операторы могут рассматриваться как функции, преобразующие полное состояние памяти V. Пусть функция E списочному представлению оператора сопоставляет эквивалентную ему Лисп-функцию, вызываемую в контексте (declare (special N)).
c | (lambda (v)c) |
(конст C) | |
x | (lambda (v) (assoc-i X N v)) N — свободная переменная, задающая список имен, известных в программе |
(перем X) | |
(A1 + A2) | (lambda (v) (+(Е А1)(У А2))) |
| (плюс А1 А2) | |
(A1 = A2) | (lambda (v)(=(Е А1)(У А2))) |
| (равно А1 А2) | |
| (пусто) | (lambda (v)v)Состояние памяти неизменно |
x := a; | Замена происходит по указанному адресу (lambda (v)(replace N v X (E A))) |
| (присвоить X A) | |
S1; S2; | (lambda (v) (E S2 (E S1 v))) |
| (шаги S1 S2) | |
if e then ST else SF; | (lambda (v) (funcall (cond (((E P)v) (E S1)) (T(E S2)) ) v) |
(если P ST SF) | |
while e do S; | Циклу соответствует безымянная функция, строящая внутренний контекст (lambda (W) ((lambda (v) (cond (((E P)v)(w ((E S)v)))(T v))) (lambda (v)(cond (((E P)v)(w ((E S)v)))(T v))) )) |
| (пока P S) |
семантика ЯП (математическая) определяет семантику языка в терминах соотношений между множествами. При задании операционной семантики важно отследить корректность обработки порождаемых структур данных, что может быть сформулировано как свойство чистого результата. Согласно этому свойству задана четкая дисциплина манипуляций со стеком при обработке данных: каждая операция берет из стека в точности все свои аргументы и обязательно располагает в нем свой единственный результат.
При определении компилятора на уровне абстрактной машины должно быть выделено описание реализационного минимума языка Лисп, послужившего базой для раскрутки Лиспа и основой для функционального программирования. Необходимо лишь ввести некоторые ограничения, гарантирующие при переходе к низкоуровневому программированию сохранение важнейших свойств функциональных программ.Эти ограничения формулируются как чистый результат правильного выражения:
все аргументы убраны из стека;результат выражения записан в стек.
Компилятор и требования к коду программы
Описанная в предыдущей лекции специальная абстрактная машина SECD удобна для спецификации машинно-зависимых аспектов семантики Лиспа. Такой подход позволяет не загромождать определение компилятора, добиться его прозрачности, но главное, такое определение может быть машинно-независимым и переносимым [3].
Для функционального стиля в программировании характерно стремление снять непринципиальные ограничения на применение и построение функций. Для этого приходится сдерживать привычные для многих областей применения разграничения, а также смягчать стандартные границы при организации процессов в системах программирования. В этом отношении следует отметить:
единое пространство функций, их аргументов и всех обозначений, роль которых определяется по контексту при интерпретации форм;разрешение функциональных переменных, значение которых конструируется (вычисляется) в процессе их интерпретации. Это позволяет вводить частичные определения, уточняемые по мере необходимости;самоопределение основных механизмов символьной обработки и, следовательно, открытый характер системы программирования, поддерживающей функциональное программирование;мягкость пространтственно-временных ограничений, без точных численных оценок по отдельным параметрам;поощрение рекурсивных определений;предельная уточняемость и детализируемость определений, управление временем их существования и выполнения.
Лисп-компилятор — это программа, написанная на Лисп, которая транслирует S-выражения, определяющие функции, в машинные подпрограммы. Это средство оптимизации, позволяющее программам работать от двух до ста раз быстрее, чем было бы при простой интерпретации.
Когда компилятор вызывается для компиляции функций, он находит определение функции в списке свойств названия функции. Компилятор транслирует найденное S-выражение в S-выражение, которое представляет подпрограмму на языке ассемблера. Ассемблер после этого ассемблирует код программы. Затем в списке свойств размещается ссылка на код программы.
Опыт показывает, что скомпилированная программа может работать в 2100 раз быстрее, чем интерпретируемая программа, в зависимости от ее природы.
Скомпилированные программы могут быть и экономичнее с точки зрения расхода памяти, требуя 50–80% от полного объема.
Основная часть компилятора — транслятор или функция, отображающая S-выражения, которые обозначают функции, на язык ассемблера. Единственное основание для того, чтобы рассматривать компилятор как псевдо-функцию, состоит в том, что он изменяет свойства названий функций по завершении компиляции.
Лисп-компилятор имеет уникальную историю. Он развивался пошаговым образом (метод раскрутки)[1].
Компилятор был написан и отлажен как Лисп-программа, состоящая из набора определений функций в виде S-выражений. Это позволило компилировать любые Лисп-программы и строить специализированные расширения Лисп-интерпретатора.Компилятору была дана команда скомпилировать себя самого. Данная операция называется раскруткой (bootstrapping). На это потребовалось более 5 минут на IBM 7090, поскольку значительная часть компилятора в основном интерпретировалась. В результате было создано эффективное расширение Лисп-системы, способное компилировать Лисп-программы и строить расширения Лисп-интерпретатора.Чтобы исключить повторение медленной раскрутки при дальнейших шагах установки системы, весь код компилятора заново был введен на языке ассемблера.Была создана системная лента, и компилятор стал загружаемым на уровне ассемблера.Процесс раскрутки был повторен до полного формирования кода Лисп-системы.
Компилятор вызывается псевдо-функцией compile. Аргумент compile — список названий функций, которые следует компилировать. Каждый атом в списке должен иметь определение функции в своем списке свойств до компиляции.
Обработка каждой функции происходит в три шага. Во-первых, S-выражение, задающее функцию, транслируется в текст на уровень ассемблера. При отсутствии S-выражения, компилятор сообщает об этом и переходит к другой функции. Во-вторых, текст программы на уровне ассемблера транслируется в код программы. И, наконец, если никаких ошибок не обнаружено, то S-выражение функции может быть удалено из списков свойств.
Когда некоторые ошибки указывают на появление необъявленной переменной, компилятор предупреждает об этом и продолжает работу. Такая диагностика будет дополнительно уточнена при анализе значений переменной.
При написании большой Лисп-программы лучше отлаживать отдельные функции, используя интерпретатор, а компилировать только те из них, которые уже хорошо изучены.
Программист, планирующий применять компилятор, должен обратить внимание на следующие моменты.
Нет необходимости компилировать все функции, которые используются лишь эпизодически. Интерпретатору доступны скомпилированные функции. Компилированные функции, использующие интерпретируемые функции, могут вычислять их непосредственно при счете.Порядок выполнения компиляции не имеет значения. Даже нет необходимости определять все функции до тех пор, пока они не понадобятся при счете. (Исключение из этого правила — специальные формы. Они должны быть определены до того, как компилируется их вызов.)При динамическом использовании Label результирующая функция не может быть скомпилирована полностью.Свободные переменные в компилируемых функциях должны объявляться до компиляции функций (См. лекцию 7).
Последнее требование проясняет роль типового контроля в стандартных, ориентированных на компиляцию без интерпретации, системах программирования.Компиляция всех объектов осуществляется без анализа фактических данных, а это и означает, что на момент компиляции переменные, как правило, являются свободными. Интерпретация располагает более полной информацией, связывающей необходимые для вычислений переменные с конкретными значениями, тип которых определен.
Компилятор и ассемблер могут быть удалены из комплекта Лисп-системы. В целом существует механизм пакетов, позволяющий управлять составом функций и объектов, включаемых в комплект. При удалении части системы освободившаяся память может быть присоединена к списку свободной памяти. Имеются реализации, в которых выделено минимальное ядро системы, все остальные функции загружаются по мере необходимости, а мусорщик может рассматривать память от неиспользуемых функций как свободную.
Определение Лисп-компилятора на Лиспе
(defun compile-(s)(append (comp- s Nil)'(Ap Stop)))
(defun comp- (S N)(cond
((atom S) (list 'LD (adr S N)))
((eq (car S)'QUOTE) (list 'LDC (cadr S))) ((eq (car S)'CONS) (append (comp-(caddr S)N) (comp-(cadr S)N) 'CONS)) ((eq (car S)'CAR) (append (comp-(cadr S)N)'CAR)) ((eq (car S)'+) (append (comp-(cadr S)N) (comp- (caddr S)N) 'ADD))
((eq (car S)'IF) (let ( (then (list (comp-(caddr S)N) '(JOIN))) (else (list (comp-(cadddr S)N) '(JOIN)))) (append (comp-(cadr S)N) (list 'SEL then else))))
((eq (car S)'LAMBDA) (list 'LDF (comp-(caddr S) (append (cadr S) N)) 'RTN))
((eq (car S)'LET) (let* ((args (value (cddr S))) (mem (cons (var (cddr S)) N)) (body (append (comp-(cadr S)mem) 'RTN))) ((append (map #'(lambda(x)(comp- x N)) args) (list body 'AP)))))
((eq (car S)'LABEL) (let* ((args (value (cddr S))) (mem (cons (var (cddr S)) N)) (body (append (comp-(cadr S)mem) 'RTN))) ((append '(DUM) (map #'(lambda(x)(comp- x mem)) args) (list 'LDF body 'RAP))))) (T (append (map #'(lambda(x)(comp- x N)) (cdr S)) (list body 'AP)) ) ))
B A)
| (LAMBDA (A) (PROG (B) S (SETQ B A) (COND ((NULL B) (RETURN C))) (SETQ C (CONS (CAR A) C)) (GO S) )) |
| Пример 8.1. |
| Закрыть окно |
Требования к компиляции Лисп-программ
Рассмотрим особенности Лисп-программ, которые необходимо учесть при определении компилятора и подготовке программ к компиляции.
Прежде всего — свободные переменные. Переменная связана, если она встречается в списке lambda или prog, а также let, do, loop и т.п. Все несвязанные переменные свободны.
(LAMBDA (A) (PROG (B) S (SETQ B A) (COND ((NULL B) (RETURN C))) (SETQ C (CONS (CAR A) C)) (GO S) ))
Пример 8.1.
A и B — связанные переменные, C — свободная переменная.
Когда переменная используется как свободная, это значит, что она должна быть связана в другой функции на более высоком уровне. При интерпретации функций может быть обнаружена переменная, не связанная вообще, о чем система известит пользователя соответсвующим диагностическим сообщением об ошибке.
При компиляции новые диагностические сообщения не появляются, а переменная получает значение Nil.
Существуют разные типы переменных в компилируемых функциях: обычные и специальные — Special. Тип Special необходимо объявить до компиляции. Все необъявленные переменные рассматриваются как обычные.
При трансляции функций в подпрограммы концепция переменных отображается в распределение памяти, в которой размещаются значения аргументов. Для обычных переменных распределение памяти — это стек. Другие функции не могут знать адреса таких переменных, что и не позволяет рассматривать их как свободные.
SPECIAL-переменные размещаются в списке свойств. Это допускает реализацию с заданием фиксированных адресов ячеек. Когда такая ячейка связана, можно старое значение вытолкнуть в стек, а новое разместить по старому адресу. При выходе из области действия текущей связи старое значение восстанавливается. При использовании такой свободной переменной адрес SPECIAL-ячейки может быть доступен другим функциям.
SPECIAL-переменные объявляются псевдо-функцией DECLARE с индикатором SPECIAL, вслед за которым расположен список переменных. Эта функция устанавливает индикатор SPECIAL в списках свойств перечисленных имен и создает ячейку для хранения значения переменной.
Эта псевдо- функция для компилятора весьма существенна. Она может действовать и при интерпретации, и при прогоне компилированных программ.
(declare ... (special v1 v2 ... ) ... )
При повторном объявлении одной и той же SPECIAL-переменной компилятор выделит другую ячейку, формально это будут различные переменные.
Специальные переменные удобны для коммуникации между компилируемыми программами, но не всегда могут четко служить коммуникации между интерпретируемыми и компилируемыми программами.
Еще один тонкий аспект — функциональные константы.
Рассмотрим следующее определение, использующее S-выражение:
(DEFUN YDOT (LAMBDA (X Y) (MAPLIST X (FUNCTION (LAMBDA (J) (CONS (CAR J) Y) )) ) ) )
(ydot (A B C D) X) ;=((A . X) (B . X) (C . X) (D . X))]
За словом function располагается функциональная константа. Если ее вынести как самостоятельную функцию, то формально J — связанная переменная, а Y — свободная. Не исключено, что свободная переменная где-то будет объявлена как специальная или общедоступная, хотя она должна быть связана внутри ydot.
Теперь про функциональные аргументы.
MAPLIST может быть определен следующим образом:
(DEFUN MAPLIST (LAMBDA (L FN) (COND ((NULL L) NIL) (T (CONS (FN L) (MAPLIST (CDR L) FN) )) ) ) )
Переменная FN — это связанный функциональный аргумент. Дело в том, что его значение — определение функции.
Трассировка скомпилированных программ
Trace — работает с компилированными программами согласно следующим ограничениям:
Trace может быть объявлена после компиляции и не требует повторной компиляции программы.
Trace не отслеживает прямые переходы на функции, созданные в обход атомов, т.е. выделенные на уровне ассемблера или кода без встраивания в общую информационную систему Лиспа — таблицу символов, хранящую свойства атомов.
"В правильном выражении всегда достаточно скобок, чтобы избежать синтаксической неоднозначности"[3] Используя это утверждение Хендерсона как эпиграф, а в Лиспе со скобками все в порядке, можно уверенно приступить к определению собственно компилятора.
Реализация динамической памяти и структур данных
После обсуждения схемы функционирования Лисп-интерпретатора и его сборки из машинно-зависимого конструктива пришло время поговорить о структурах данных, используемых при реализации списков и атомов.
Обычно при обработке программ в памяти располагаются разносортные результаты, возникающие при разборе и анализе текста программы и ее данных, при построении ее внутреннего кода и при формировании результата. В Лисп-системах традиционно при всех этих видах работ принято придерживаться принципов логики здравого смысла:
новые значения строятся на новом месте,предпочитаются интересы малых программ,
автоматизируется повторное использования памяти, что на первых шагах разработки освобождает программиста от необходимость уделять внимание вторичным проблемам распределения памяти.
Кроме того, почти исключается необходимость присваиваний, они в программах заменяются именованием.
Память обычно распределена по блокам, содержащим ряд слов, образующих структуры данных. Физический объем памяти, логическая длина данных и состав информации, полезной для продолжения вычислений, могут существенно различаться. Минимальные потери в результативности работы с памятью дает динамическая обработка бинарных деревьев — без простоев из-за незаполненности части полей. Каждый узел такого дерева имеет небольшой объем, достаточный для хранения двух типизированных указателей (CAR и CDR, левый и правый). Типизация указателей нужна для оперативного контроля соответствия данных и операций по их обработке. NIL, атомы, списки, числа, строки — все это реализационно различимые типы данных. (Утверждение о бестиповости Лиспа имеет отношение лишь к отсутствию статического связывания в тексте программы имен переменных с типами их значений. Для компиляции приходится дополнять Лисп-программы сведениями о типах значений переменных, но далеко не каждая программа доживает до компиляции.) Лиспу свойственна функциональная классификация значимых типов данных, т.е. именно реализационно различимых.
Реализация бинарных деревьев или односвязных списков описана в классических курсах по программированию, а реализацию атомов мы рассмотрим подробнее.
Эффективность приведенного выше определения интерпретатора с использованием ассоциативного списка существенно зависит от числа различимых атомов в программе. Такая зависимость обычно смягчается механизмом функций расстановки (хэш-функций), обеспечивающим доступ к информации по ключу. В качестве ключа используется имя атома. В результате вся связанная с атомом информация становится легко достижимой. Структура такой информации называется списком свойств атома. Она представляет собой чередование так называемых «индикаторов» и «значений» свойств. Число свойств атома неограничено. Свойства бывают встроенные в систему или вводимые программистом. Значения атомов, адреса встроенных операций, определяющие выражения функций — примеры встроенных свойств. Встроенные операции типа LET, LABELS обычно используют списки свойств. Обработка таблицы, связывающей атомы и их списки свойств, как правило, зависит от реализации. Методы задания и изменения свойств работают подобно обычным присваиваниям. Псевдо-функция PUT задает индикатор и соответствующее ему новое значение свойства атома, а функция GET обеспечивает доступ к свойству атома, соответствующему заданному индикатору. Теперь с помощью списков свойств мы могли бы добиться точного соответствия семантики констант и определений функций их спецификации в базовом Лиспе, но не будем отвлекаться на это.
Самым интересным, можно сказать революционным, механизмом работы с памятью в Лиспе, бесспорно, стала «сборка мусора». С начала 60-х годов методам такой работы посвящены многочисленные исследования, которые продолжаются до наших дней и сильно активизировались в связи с включением похожего механизма в реализацию языка Java.
Общая идея всех таких методов достаточно проста:
пока памяти хватает, о ней можно не беспокоиться и располагать новые данные в новых блоках памяти;если памяти вдруг не оказалось, то надо выполнить «сборку мусора», в процессе которой, возможно, найдутся ставшие бесполезными для программы блоки;если память нашлась, ее снова можно тратить.
Специальная программа «Сборщик мусора» выполняет анализ достижимости всех блоков памяти просто пометкой узлов, видимых из конечного числа рабочих регистров системы программирования. К таким регистрам относятся промежуточные результаты вычислений, активная часть стека, ассоциативный список, таблица атомов и др. После пометки все непомеченные узлы объединяются в список свободной памяти, передающий их для повторного использования новым вызовам функции CONS. Такая автоматизация не лишена недостатков, но они обнаруживаются лишь в сравнительно сложных процессах, требования которых мы сейчас не учитываем.
Обычно с машиной связывается представление о блоках информации фиксированного объема, таких как слова, байты, регистры. Функциональное программирование нацелено на более крупные построения — структуры данных не ограниченной заранее длины. Такие структуры достаточно эффективно реализуются посредством специального стека, приспособленного к обработке произвольного числа компонентов текущего уровня иерархической структуры данных.
От обычного стека он отличается выделением указателя на конец текущего уровня.
|_________| _______________________________ |_________|<----|__Нач_стека_|_Кон_тек_ур__| |_________| | |_________| | |_________| | |_________| | |_________|<----------------------------------/ |_________| |_________| | |
При переходе на внутренний уровень Кон_тек_ур записывается в стек, Нач_стека переписывается в Кон_тек_ур, а новая вершина стека становится значением Нач_стека.
В результате стек хранит ссылки на границы уровней, что обеспечивает возможность возврата на любой нужный уровень, в частности, восстановления процесса обработки в случае неожиданных ситуаций.
Значительный резерв производительности функциональных программ дают деструктивные функции, являющиеся формальными аналогами чистых функций:
| Append | nconc |
| Subst | nsubst |
| Remove | delete |
| Reverse | nreverse |
| Union | nunion |
Реальный состав системы и внешний мир
Реальный состав системы и возможности ее компонентов можно исследовать с помощью специальных функций, предоставляющих информацию о включенных в систему объектах и их свойствах.
Состав системы:
(apropos ‘nm ‘package) — печатает информацию обо всех символах, имена которых содержат подстроку “nm”. Второй аргумент, если он указан, ограничивает эту информации заданным пакетом.
(describe ‘fn ) — дает описание места объекта в системе.
(symbol-plist ‘fn) — выдает перечень всех свойств объекта.
(documentation ‘fn ‘function) — выдает документацию по объекту.
Отладка программ:
(dribble ‘path) — направляет в файл протокол работы с Лисп-интерпретатором.
(step expr) — обеспечивает пошаговый режим интерпретации выражения с выдачей результатов каждого шага.
Ввод-вывод данных:
(setq inpt (open file-in :direction :input )) — заведение переменной для обозначения открытого потока.
(read inpt) — чтение из файла, открытого как поток.
(print (print eval-val prtcl) outpt) — запись данного eval-val в два разных файла.
(open file-in :direction :input ) — открытие файла на чтение.
Далее следуют три варианта открытия файлов на запись:
(open "output" :direction :output :if-exists :rename :if-does-not-exist :create) (open "protocol" :direction :output :if-exists :overwrite :if-does-not-exist :create) (open "history" :direction :output :if-exists :append :if-does-not-exist :create ) (close prtcl) — закрытие потока.
Особенности работы с файлами, основные приемы их открытия, задания специфики их функционирования и обмена данными с обычными символьными объектами иллюстрирует пример организации учебного цикла работы с Clisp, использующего пошаговую интерпретацию программ.
(defun eval-protocol () (prog (eval-val) ; выражения хранятся в файле "input.lsp"
metka (print '> prtcl) (setq eval-val (eval (list 'STEP ; пошаговое вычисление выражения (print (print ( if (eq 'eof (setq rinpt (read inpt NIL 'eof) )) (return(close inpt)) rinpt) prtcl) hstry) )))
; прочитанное записывается в файлы "protocol" и ; "history" (print '- prtcl) ;(print eval-val) (print (print eval-val prtcl) outpt) ; результат интерпретации в файлах ; "protocol" и "output" (go metka) ))
(defun help ( function-name ) (ed (string function-name )) )
(defun step1 (file-in) (prog ()
(setq inpt (open file-in :direction :input )) (setq outpt (open "output" :direction :output :if-exists :rename :if-does-not-exist :create)) (setq prtcl (open "protocol" :direction :output :if-exists :overwrite :if-does-not-exist :create)) (setq hstry (open "history" :direction :output :if-exists :append :if-does-not-exist :create )) (print '"****** new-session ******" hstry)
; цикл прервется по достижении конца файла ввода (eval-protocol)
(close prtcl) (close hstry) (close outpt) ))
(step1 "input.lsp") ; интерпретируемые выражения хранятся в файле ; "input.lsp"
Сборка системы и ее рабочий цикл
Моделирование Лиспа или другого языка программирования на идеальном базовом Лиспе вполне может послужить иллюстрацией определения операционной семантики языков программирования [8].
Традиционно система программирования для языка Лисп содержит пару интерпретатор-компилятор. Между этими понятиями трудно установить формальную границу. Любой интерпретатор содержит элементы, реализация которых описывается в машинных терминах: структура памяти, реализация двоичных деревьев и т. п. Любая компилированная программа содержит интерпретируемые элементы: например, обращения к файловой системе и другим элементам ОС. На практике достоинства интерпретации проявляются при отладке программ, а преимущества компиляции — при эксплуатации готового программного продукта. Более подробное обсуждение этой темы заслуживает отдельного разговора.
Теория программирования утверждает, что определение компилятора может быть выведено из определения интерпретатора методами смешанных вычислений [9]. Это методы, допускающие частичную обработку программ при неполных или избыточных данных с построением остаточной программы, которую можно применять по мере уточнения данных. Компилятор по такой методике получается как остаточная программа при смешанном вычислении интерпретатора. Теоретически для определения языка программирования достаточно построить определение интерпретатора, хотя практичность реальной системы программирования обычно обеспечивается оптимизирующей компиляцией и кодогенерацией программ [9]. Но здесь речь идет не об эффективном компиляторе, а лишь о понятном описании семантики.
Ядро интерпретатора языка Лисп может быть реализовано следующим образом:
выбирается реализация списков в виде бинарных деревьев, листья которого рассматриваются как атомы, а узлы используются для выстраивания списков (левые ветви — элементы списка, правые — продолжение списка или конец списка, т.е. пустой список);выбирается реализация атомов как объектов, внутренняя структура которых при определении и исполнении функций не всегда существенна, но при необходимости доступна специальным операциям;встраивается специальный атом NIL, являющийся реализацией пустого списка ();встраивается операция, связывающая различные данные с атомами, и ассоциируется с атомом LABEL;определяются правила доступа к параметрам встроенных операций с размещением их результата и встраивается специальная операция (монитор), выполняющая применение операций к правильно размещенным аргументам (SUBR);встраивается операция, строящая из атомов и списков более сложные структуры (списки и узлы из любых элементов), и ассоциируется с атомом CONS;встраиваются операции, выполняющие разбор и анализ структур, и ассоциируются с атомами CAR, CDR, ATOM, EQ, представляющими эти операции;встраиваются специальные операции (псевдо-функции), выполняющие блокировку вычислений, выбор ветви и конструирование определений функций, и ассоциируются с атомами QUOTE, COND и LAMBDA, соответственно;универсальная функция ассоциируется с EVAL;определяется рабочий цикл передачи данных интерпретатору и вывода результата интерпретации.
Такое ядро представляет собой машинно-зависимую часть Лисп-интерпретатора. Встраивание операции в ядро системы — это включение в его реализацию исполняемого кода, который является реализацией этой операции. Адрес такого кода ассоциируется с именем атома, с помощью которого будет организовано выполнение операции при интерпретации программ.
При ассоциировании атомов с произвольной информацией можно использовать специально организованный ассоциативный список, построенный из пар, содержащих атомы и их определения. Например, ассоциативный список
((T . T )(NIL . NIL))
обеспечивает значение T и NIL в соответствии с семантикой базового Лиспа, список
((ОДИН . 1)(ДВА . 2))
дает символьные имена числовым значениям, а список
((ГОЛОВА . CAR)(ХВОСТ . CDR)(УЗЕЛ . CONS))
— синонимы для обозначения базовых операций Лиспа.
Ассоциативный список работает как стек: при многократных определениях работает самое новое, т.е. расположенное ближе к началу списка. Если мы знаем адреса кода операций, встроенных в ядро системы, то можем соответствие между именами операций и адресами их кода хранить в ассоциативном списке. Можно считать, что начальное состояние ассоциативного списка содержит таблицу соответствия между именами и адресами операций.
Основой определения интерпретатора является функция EVAL (evaluation), вычисляющая произвольные выражения языка с учетом состояния ассоциативного списка AL. Спецификация такой функции для базового Лиспа может быть проиллюстрирована следующими примерами:
(EVAL NIL AL ) => NIL (EVAL T AL ) => T (EVAL 'X AL ) => (CADR (ASSOC X AL)) (EVAL '(QOUTE EXPR ) AL ) => EXPR (EVAL '(COND ((T YES) ... )) AL ) => YES (EVAL '(CSETQ X Y EXPR ) AL ) => (EVAL EXPR (CONS '(X Y ) AL)) (EVAL '(CAR A) '((A (1 2 3))(NIL NIL)) ) => 1
В других случаях выражения получают значение в результате применения некоторой функции, стоящей в голове списка, к ее аргументам, что выполняется другой важной частью определения интерпретатора — функцией APPLY. Для ее работы необходима функция, вычисляющая значения аргументов с учетом состояния ассоциативного списка.
При написании на базовом Лиспе определения функции EVAL согласно приведенной выше спецификации, способной от данного списочного представления выражения E перейти к его значению с учетом заданного ассоциативного списка AL, хранящего значения атомов, мы несколько отступаем от ранее данных определений, с тем чтобы более явно выделить линии сборки системы.
(DEFUN EVAL (e al ) (COND ((MEMBER e '(NIL T )) e ) ((ATOM e ) ((LAMBDA (v ) (COND (v (CADR v ) ) (T (ERROR 'undefdvalue )) )) (ASSOC e al ) ) ) ((EQ (CAR e) 'QUOTE ) (CAR (CDR e )) ) ((EQ (CAR e) 'COND ) (EVCON (CDR e ) al ) ) ((EQ (CAR e) 'LET ) (EVAL (CADDDR e ) (CONS (CONS (CADR e ) (CONS (EVAL (CADDR e ) al ) NIL) ) al ) )) (T (APPLY (CAR e) (EVLIS (CDR e) al ) al ) ) ))
В этом функциональном значении используется имя функции APPLY, применяющей произвольную функцию к ее аргументам при заданном ассоциативном списке. ERROR — псевдо-функция, выдающая заданные диагностические сообщения.
Определение функции APPLY работает при условии, что функция SUBR осуществляет применение встроенных функций к их аргументам, заданным в виде списка значений.
(DEFUN APPLY (fn args al ) (COND ((MEMBER fn '(CAR CDR CONS ATOM EQ )) (SUBR (CADR (ASSOC fn al)) args )) ((EQ fn NIL) NIL) ((ATOM fn ) (APPLY (EVAL fn al ) args al )) ((EQ (CAR fn ) 'LAMBDA ) (EVAL (CADDR fn ) (APPEND (PAIR (CADR fn ) args ) al ) ) ) ((EQ (CAR fn) 'LABEL ) (APPLY (CADDR fn) args (CONS (CDR fn ) al ) ) ) (T (ERROR- 'undefined_function)) ) )
Обратите внимание, что в EVAL при поиске атома в ассоциативном списке мы допускаем отсутствие ассоциированного с атомом значения и сообщаем об этом диагностикой с помощью функции ERROR. В APPLY же при выборе адреса встроенной функции мы рассчитываем, что все известные функции реализованы, и их адреса размещены в ассоциативном списке — за правильность выбора имен встроенных функций отвечает программист.
Можно еще поработать с таким определением интерпретатора и более четко локализовать его зависимость от четырех различных категорий объектов: самоопределяемые атомы — (NIL T 1 2 3 ... ), базовые операции над данными языка, обрабатывающие предварительно вычисленные аргументы, — (CAR CDR CONS ATOM EQ ... ), специальные функции, управляющие обработкой аргументов без их предварительного вычисления, — (QUOTE COND LET ...) и конструкторы функций, строящие функциональные значения из обычных выражений, — (LAMBDA LABEL... ).
Желающие могут поэкспериментировать с самодельным интерпретатором, превращая его в модель ядра любого языка программирования, используя какую-нибудь Лисп-систему, например GNU Clisp (с точностью до имен отдельных функций).
Упражнение 9.1. Пусть READ и PRINT — встроенные функции, обеспечивающие прием с клавиатуры и вывод на экран произвольных данных языка Лисп. Напишите определение рабочего цикла интерпретации последовательности выражений.
Ответ.
(DEFINE CIRCLE (al ) (PRINT (EVAL (PRINT (READ )) al )) (CIRCLE al ) )
«Но оно же зациклится!» — скажете вы и будете правы.
Но это не помешает эксперименту, ведь в нашем распоряжении имеется конец файла Ctrl-Z или встроенная операция завершения процесса типа BYE, EXEC, SYSTEM либо что-то подобное.
Упражнение 9.2. Полученные 50 строк определения Лисп-интерпретатора и его вспомогательных функций содержит 1263 символа, если не считать пробелы в начале строк. Попробуйте написать сравнимое определение на каком-нибудь знакомом вам языке программирования.
Еще одна реализация
Более прозрачная модель ООП получается на базе обычных списков свойств, заодно иллюстрирующая глубинное родство ФП и ООП:
(defun classes (cl) (cond (cl (cons (cdar cl) (classes (cdr cl)))) ))
; вывод формулы классов аргументов из определения ; параметров метода ; Nil — произвольный класс
(defun argum (cl) (cond (cl (cons (caar cl) (argum (cdr cl)))) ))
; вывод списка имен аргументов из определения ; параметров метода
(defun defmet (FMN c-as expr) (setf (get FMN 'category) 'METHOD) (setq ML (cons(cons(cons FMN (classes c-as)) (list 'lambda (argum c-as) expr) ) ML)) FMN ) ; объявление метода и расслоение его определения ; для удобства сопоставления с классами аргументов
(defun defcl (NCL SCL FCL ) ; имя, суперкласс и поля/слоты класса (setq ALLCL (cons NCL ALLCL)) (set NCL (append FCL SCL)) )
; значением класса является список его полей, ; возможно, со значениями
(defun ev-cl (vargs) (cond
; вывод формата фактических аргументов для поиска ; метода их обработки
(vargs (cons (cond ((member (caar vargs) ALLCL) (caar vargs)) ) (ev-cl (cdr vargs)))) )) ; Nil если не класс
(defun m-assoc (pm meli) (cond (meli (cond ((equal (caar meli) pm)(cdar meli)) (T(m-assoc pm (cdr meli)))))))
; поиск подходящего метода, соответствующего ; формату классов данных
(defun method (MN args &optional c) (apply (m-assoc (cons mn (ev-cl args)) ML) args c))
; если метода не нашлось, в программе следует ; выполнить приведение ; параметров к нужному классу
(defun instance (class &optional cp) (cond
; подобно Let безымянная копия контекста
(class (cond ((atom (car class))(instance (cdr class) cp)) ((assoc (caar class) cp) (instance (cdr class) cp)) (T(instance (cdr class) (cons (car class) cp))) )) ) cp)
(defun slot (obj fld) (assoc fld obj))
; значение поля объекта
Остается лишь слегка подкорректировать определение Лисп-интерпретатора, заодно используя необязательные параметры, осовобождающие от простейших вспомогательных определений, например от обязательного вхождения накопителей типа ассоциативного списка.
(DEFUN evcon- (c &optional a) ; |_________ключ, объявляющий ; необязательные параметры (COND ((eval-p (car (car c)) a) (eval-p (car (cdr (car c))) a) ) ( T (evcon- (cdr c) a) ) ))
(DEFUN evlis- (m &optional a) (COND ((EQ m Nil) Nil) ( T (cons (eval-p (car m) a) (evlis- (cdr m) a) ) ) ))
(defun eval-p (e &optional c) (cond ((atom e) (value e c)) ((atom (car e))(cond
((eq (car e) 'QUOTE) (car (cdr e))) ((eq (car e) 'COND) (evcon- (cdr e) a)) ((get (car e) 'METHOD) (method (car e) (evlis(cdr e)) c) ) ( T (apply-p (car e)(evlis- (cdr e) c) c)) ) ) (T (apply-p (car e)(evlis- (cdr e) c) c)) )) (defun apply-p (f args &optional c) (cond ((atom f) (apply-p (function f c) args c)) ((atom (car f))(cond ((get (car f) 'macro) (apply-p (apply-p (get (car f) 'macro) ( cdr f) c) args c))
(T (apply-p (eval f c) args c)) ) ) (T (apply-p (eval f c) args c)) ))
(print (eval-p 1)) (print (eval-p 'a)) (print (eval-p '(quote b))) (print (eval-p '(cond (Nil 6)(T 88) ))) (print (eval-p '(car '(3 2))))
Функциональный синтаксис
Другое улучшение — синтаксис сообщений можно варьировать без оглядки на традицию префиксных записей. Определение методов может достичь предельной гибкости благодаря возможности генерировать определения функциональных объектов с помощью DEFMACRO.
Экземпляры
До сих пор не требовалось особо различать классы, объекты и их вхождения. Логически удобно все обрабатывать по общей схеме, но весьма непроизводительно всякий раз просматривать сотни предшественников, если известно, что достаточно менее десятка. Такую оптимизацию выполняет механизм экземпляров. Экземпляр имеет одного предка — его класс. Его обработка не требует списка предшественников. Это не ведет к потере гибкости, т.к. при необходимости можно переопределить состояние объекта и как бы конвертировать экземпляр в класс.
Классы и экземпляры объектов
(defclass ob () (f1 f2 ...))
Это означает, что каждое вхождение объекта будет иметь поля-слоты f1 f2 ... (Слот — это поле записи или списка свойств.) Чтобы сделать представителя класса, мы вызываем общую функцию:
(setf с (make-instance 'ob))
Чтобы задать значение поля, используем специальную функцию:
(setf (slot-value c) 1223)
До этого значения полей были не определены.
Множественное наследование
До сих пор речь шла о простом наследовании — объект имел только одного предка. Но можно получать и множественное наследование построением списка свойств предков со слегка измененной rget. При простом наследовании, когда нам надо выбрать некоторое свойство объекта, мы сразу рекурсивно ищем его предшественников. Если собственно объект не содержит искомую информацию, мы обозреваем его предка и т.д. При множественном наследовании мы делаем примерно то же самое, но работа усложняется тем, что предшественники объекта могут образовывать граф вместо дерева.
При реализации такой идеи не следует проверять объект ранее его последователей (a b c d):
(d) / \ (b) (c) \ / (a)
Если это сделать прямым сцеплением списков, то результат слишком неэффективен.
Общее представление о декомпозиции программ
Сборка программы из автономно развивающихся компонентов опирается на формулировку достигаемой ими цели, понимание которой гарантирует не только корректность полученного результата, но и рациональность его использования. Формулировать цели частей программы — процесс нетривиальный. В его основе лежат весьма различные подходы к классификации понятий.
ООП объединяет в рамках единой методики организации программ классификацию на базе таких понятий как класс объектов, структура данных и тип значений. Тип значений обычно отражает спектр низкоуровневых реализационных средств, учет которых обеспечивает эффективность кода программы, получаемого при компиляции. Структура данных обеспечивает конструктивность построений, гарантирует доступ к частям, из которых выстроено данное любой сложности. Класс объектов характеризуется понятным контекстом, в котором предполагается их корректная обработка. Обычно контекст содержит определения, структуру объектов и их свойства.
Текст программы одновременно представляет и динамику управления процессами, и схему информационных потоков, порождаемых при исполнении программы. Кроме того, последовательность написания программы и ее модификации по мере уточнения решаемой задачи могут соответствовать логике, существенно отличающейся от процесса выбора системных и реализационных решений. Функциональное программирование скрывает сложность таких деталей управления процессами путем сведения его к общим функциям, преобразующим любые аргументы в определенные результаты. Модификации осуществляются в процессе изменения состава ветвей непосредственно в определении каждой функции.
ООП структурирует множество частных методов, используемых в программе, в соответствии с иерархией классов объектов, обрабатываемых этими методами, реализуемыми с помощью функций и процедур, в предположении, что определяемые в программе построения могут локально видоизменяться при сохранении основных общих схем информационной обработки. Это позволяет выполнять модификации объявлением новых подклассов и дописыванием методов обработки объектов отдельных классов без радикальных изменений в ранее отлаженном тексте программы.
При анализе задач, решаемых в терминах объектов, некоторая деятельность описывается так, что постепенно продумывается все, что можно делать с объектом данного класса. Потом в программе достаточно лишь упоминать методы обработки объекта. Если методов много, то они структурированы по иерархии классов, что позволяет автоматизировать выбор конкретного метода. На каждом уровне иерархии можно немного варьировать набор методов и структуру объектов. Таким образом, описание программы декомпозируется на интерфейс и реализацию, причем интерфейс скрывает сложность реализации так, что можно обозревать лишь необходимый для использования минимум средств работы с объектом.
Типичная гипотеза при программировании работы с объектами:
Объект не изменен, если на него не было воздействий из программы.
Но реальность зачастую требует понимания и учета более сложных обстоятельств, что может существенно продлить время жизни программы или ее компонентов. В таком случае удобно предоставлять объектам большую свободу, сближающую их с понятием субъекта, описание которого содержит все, что он может делать. Программа может давать ему команды-сообщения и получать ответы-результаты.
Связь методов с классами объектов позволяет вводить одноименные методы над разными классами объектов (полиморфизм), что упрощает представление логики управления: на уровне текста программы можно не выражать распознавание принадлежности объекта классу, это сделает система программирования. Таким образом обычно реализовано сложение, одинаково изображаемое для чисел, строк, векторов, множеств и т.п. Фактически субъектом является суперкласс, объединяющий классы объектов, обрабатываемые одноименными методами, т.е. функциями одного семейства. Так, при организации сложения можно считать, что существует суперкласс «слагаемые», которое умеют складываться с другими слагаемыми. При этом они используют семейство функций, реализующих сложение. В зависимости от полноты семейства результат может быть получен или не получен. Семейство легко пополняется добавлением одноименных функций с новыми комбинациями типов параметров.
Дальнейшее развитие подходов к декомпозиции программ связано с выделением отдельных проекций и шагов при решении сложных задач. Понятие проекции связано с различием точек зрения, позволяющим описывать решение всей задачи, но отражать в описании только видимые детали. По мере изменения точек зрения могут проступать новые детали, до тех пор, пока дальнейшая детализация не утрачивает смысл, т.е. улучшение трудно заметить или цена его слишком высока. Так, представление символьной информации в Лиспе выделено в отдельную проекцию, независимую от распределения памяти, вычисление значений четко отделено от компиляции программ, понятие связывания имен с их определениями и свойствами не зависит от выбора механизмов реализации контекстов исполнения конструкций программы.
Понятие шага обычно связывается с процессом раскрутки программ, оправданным в тех случаях, когда целостное решение задачи не может гарантировать получение приемлемого результата в нужный срок — это влечет за собой непредсказуемо большие трудозатраты.
Удобный подход к организации программ «отдельная работа отдельно программируется и отдельно выполняется» успешно показал себя при развитии операционной системы UNIX [21] как работоспособный принцип декомпозиции программ. Но существуют задачи, например реализация систем программирования, в которых прямое следование такому принципу может противоречить требованиям к производительности. Возможен компромисс «отдельная работа программируется отдельно, а выполняется взаимосвязано с другими работами» [22], что требует совмещения декомпозиции программ с методами сборки — комплексации или интеграции программ из компонентов. Рассматривая комплексацию как еще одну «отдельную» работу, описываемую, например, в терминах управления процессами, можно констатировать, что эта работа больше сказывается на требованиях к уровню квалификации программиста, чем на объеме программирования. При достаточно объективной типизации данных и процессов, возникающих при декомпозиции и сборке программ определенного класса, строят библиотеки типовых компонентов и разрабатывают компонентные технологии разработки программных продуктов - Corba, COM/DCOM, UML, .Net.
Одна из проблем применения таких компонентов - их обширность.
При реализации экспериментальных языков и систем программирования цель применения раскрутки — минимизация трудозатрат, основанная на учете формальной избыточности средств языков программирования. Можно выделить небольшое ядро, на основе которого методично программируется все остальное. Каждый шаг реализации по схеме раскрутки должен обеспечивать:
уменьшение трудоемкости последующих шагов,отладку прототипов сложных компонентов,подготовку демонстрационного материала.
Выбор конретных шагов можно соотнести с декомпозицией определения языка программирования на синтаксические и семантические, функциональные и машинно-ориентированные, языково-ориентированные и системные аспекты. При такой декомпозиции можно на первых шагах как бы «снять» синтаксическое и семантическое разнообразие языка, как имеющее чисто технический характер. Именно в этом смысл выделения элементарного Лиспа. Такая методика может быть успешна при освоении любого класса задач, информацию о котором можно представить в виде частично формализуемых текстовых и графовых форм.
Дальнейшие шаги раскрутки можно упорядочить по актуальности реализации компонентов, обеспечивающих положительную оценку системы пользователем. Это позволяет развить представление о принципах декомпозиции программ более созвучно ООП: «отдельная работа обнаруживается независимо от остальных работ». Наиболее устойчивая и значимая классификация работ по реализации системы программирования может быть установлена как обеспечение механизмов надежного функционирования информационных систем — «отдельная работа — это отдельное средство повышения надежности программирования». Ряд таких средств можно выделить в любом языке программирования: вычисления, статическое и динамическое управление процессами, логика выбора хода обработки информации, дисциплина именования памяти и доступа к расположенным в ней данным, правила укрупненных воздействий на блоки данных и иерархию процессов, диагностика и обработка событий — перечень открытый.
ООП на Лиспе
При переходе от обычного стандартного программирования с ООП связывают радикальное изменение способа организации программ. Это изменение произошло под давлением роста мощности оборудования. ООП взламывает традиционное программирование по многим направлениям. Вместо создания отдельной программы, оперирующей массой данных, приходится разбираться с данными, которые сами обладают поведением, а программа сводится к простому взаимодействию новой категории данных — «объекты».
Чтобы сравнить дистанцию с функциональным программированием, рассмотрим самодельный встроенный в Лисп объектно-ориентированный язык (ОО-язык), обеспечивающий основы ООП. Встраивание ОО-языка — идеальный пример, показывающий характерное применение функционального программирования, при котором типичные понятия ООП отображаются в фундаментальные абстракции.
При организации наследования следует пояснить разницу между моделями обобщенных функций и обмена сообщениями.
объекты обладают свойствами,посылают сообщения,наследуют свойства и методы от предков.
Рассмотрим программу вычисления площадей ряда геометрических фигур, таких как круги, прямоугольники, звезды и пр. Ее запись в ОО-стиле поначалу может выглядеть непринципиально отличающейся от обычной программы.
Но допустим, понадобилось ввести новый класс — раскрашенные круги. Если методы раскраски произвольных фигур уже существовали, то можно унаследовать две особенности:
от круга наследуем понятие «радиус», а от раскрашенных — «цвет»;можно не вводить метод «раскраска круга».
Практически ООП — это организация программ в терминах методов, классов, экземпляров и наследования. Почему стоит писать программы таким способом? Основной выигрыш — программы легче изменять. Если мы хотим изменить способ манипулирования каким-либо объектом некоторого класса, то мы изменяем лишь метод этого класса. Если мы хотим сделать нечто подобное объекту, но отличающееся в отдельных чертах, мы можем создать подкласс объектов, а уже для подкласса поменять его отдельные черты.
Если программа написана тщательно, то можно добиться того, чтобы все такие модификации производились даже без просмотра ранее написанного исходного текста программы.
В Лисп есть разные способы размещать коллекции свойств. Один из них — представлять объекты как хэш-таблицы и размещать свойства как входы в нее. В [7] приведен блестящий пример реализации ООП на базе хэш-таблиц. Тогда отдельное свойство можно получать из таблицы в форме:
(gethash 'color obj)
Поскольку функции являются данными объекта, мы можем размещать их точно так же, как и свойства. Это значит, что мы должны завести еще методы, позволяющие вызывать данный метод объекта как исполнение свойства данного объекта.
(funcall (gethash 'move obj) obj 10)
Мы можем определить под эту идею синтаксис как в Smalltalk
(defun tell (obj message &rest args) (apply (gethash messmage obj) obj args))
что позволяет сказать объекту, чтобы он переместился на 10 шагов, в форме:
(tell obj 'move 10)
Фактически успех наследования обеспечивает единственная особенность Лиспа: все это работает благодаря реализации рекурсивной версии GETHASH. Таким образом, определение данной функции нам сразу даст все три основные черты ООП.
Посмотрим, во что это обойдется в исходном примере.
Мы должны создать два объекта, один — потомок другого.
В объект «круги» мы помещаем методы для всех кругов. Для начала это функция одного аргумента — объекта, посылающего сообщение:
(setf (gethash 'area circle-class) #' (lambda (x) (* pi (expt (rget ' radius x) 2))))
Теперь можно спрашивать о площади круга, она будет вычисляться согласно методу, определенному для класса. Мы используем rget при чтении свойства и tell — при вызове метода.
(rget 'radius our-cicle) (tell our-circle 'area)
Прежде чем улучшать эту программу, надо проверить, что же получилось. Легкость результата — это трюк, но не программистский трюк, а концептуальный. Не будем забывать о том, что Лисп по своей природе уже был ОО-языком, или даже чем-то более общим изначально. Все что нам понадобилось — это создать новый фасад для уже существующих в Лиспе абстракций.
Определяемые объекты
Первое улучшение — функция создания объектов. Такая функция может быть не видна пользователю. Если мы создадим данную функцию, можно будет строить объекты и объявлять его предков за один шаг. Мы получим список предшествования объектов в процессе их создания вместо дорогостоящей их реорганизации при поиске свойства. Стратегия — поддерживать список всех существующих объектов, и в нем помечать списки изменяемых предшественников. Это тоже обременительно, но без потери гибкости основная нагрузка переносится в нечасто повторяющуюся область.
Средства ООП в CLOS на базе стандарта Clisp
Показанный в [7] пример работает по первому аргументу (выбор подходящего метода рассчитан на то, что достаточно разобраться с одним аргументом), CLOS делает это на всех аргументах, причем с рядом вспомогательных средств, обеспечивающих гибкий перебор методов и анализ классов объектов.
Суперкласс
Нет необходимости все новые слоты создавать в каждом классе.
Пример: ОО-определение Лисп-компилятора.
;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) (sdd :accessor sd) ) (:documentation "cons + lambda let"))
(defclass trio (expr) ((type :accessor td) (sd :accessor ft) ; (bin) ;; не объявлять sdd ??? (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)) (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) ) (: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 "шаг разбора"))
;====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)))
(print(setf (slot-value e3 'sd) '(quote const))) (print (tf e3))
CLOS, естественно, использует модель обобщенных функций, но мы написали независимую модель, используя более старые представления, тем самым показав, что концептуально ООП — это не более чем перефразировка идей Лиспа. ООП — это одна из вещей, которую Лисп изначально умеет делать. Для функционального стиля программирования в переходе к ООП нет ничего неожиданного. Это просто небольшая конкретизация механизмов перебора ветвей функциональных объектов.
Более интересный вопрос, что же нам еще может дать функциональный стиль и лисповская традиция реализации систем программирования?
Ответу на этот вопрос посвящены три следующие лекции.
Свойства слотов
Простейшее определение слота — это его имя. Но в общем случае слот может содержать список свойств. Внешне свойства слота специфицируются как ключевые параметры функции. Это позволяет задавать начальные значения. Можно объявить слот совместно используемым.
:allocation :class
Изменение такого слота будет доступно всем экземплярам
объектов класса. Можно задать тип элементов, заполняющих слот, и сопроводить их строками, выполняющими роль документации.
Векторная реализация
Реализация ООП с помощью хэш-таблиц обладает слегка парадоксальной окраской: гибкость у нее больше, чем надо, и за большую цену, чем можно позволить. Уравновесить это может подобная реализация на базе простых векторов. Этот переход показывает, как функциональное программирование дает новое качество «на лету». В опорной реализации фактически не было реализационного разделения объектов на экземпляры и классы. Экземпляр — это был просто класс с одним-единственным предком. При переходе к векторной реализации разделение на классы и экземпляры становится реальным. В ней становится невозможным превращать экземпляры в классы простым изменением свойства.
Логические связки
Логика McCarthy (компьютерная)
a & b
(if (not a) Nil b)
b вычисляется лишь при истинном a, что результативно, но не всегда соответствует интуитивным ожиданиям (логика, предложенная в свое время McCarthy, позволяет добиться высокой эффективности). Математически более надежны варианты, исключающие зависимость от порядка перебора:
Более надежны варианты, исключающие зависимость от порядка перебора:
(( lambda x { (if (not x) Nil ) | esc }) {a | b} )
Аналогичная проблема возникает при построении ветвлений
(cond (p1 e1) (p2 e2 ) ... )
( (lambda L {(cond ((eval(caar L)AL) (eval(cadr L)AL) )) | ESC }) ( любой ((p1 e1) (p2 e2) ... ) ) )
Поддержка вариантов, каждый из которых может понадобиться при построении окончательного результата, находит практическое применение при организации высокопроизводительных вычислений. Например, мультиоперации можно организовать с исключением зависимости от порядка отдельных операций в равносильных формулах:
a+b+c = (a+b)+c = a+(b+c) = (a+c)+b
((lambda (x y z) {(if (< (+ x y) K) (+(+ x y) z)) | esc}) {(a b c) | (b c a) | (c a b)})
В книге Хендерсона приведено обобщение абстрактной машины, поддерживающее на базовом уровне работу с вариантами с использованием дополнительного дампа, гарантирующего идентичность состояния машины при переборе вариантов 3.
Недетерминированные процессы
Есть мнение, что однозначное решение задачи в виде четкого алгоритма над хорошо организованными структурами и упорядоченными данными — результат аккуратной, тщательной работы, пытливого и вдумчивого изучения класса задач и требований к их решению.
Эффективные и надежные программы в таких случаях — естественное вознаграждение.
Но в ряде случаев природа задач требует свободного выбора одного из вариантов — выбор произвольного элемента множества, вероятности события при отсутствии известных закономерностей, псевдо-случайные изменения в игровых обстановках и сценариях, поиск первого подходящего адреса для размещения блока данных в памяти, лингвистический анализ при переводе документации и художественных текстов и т.д. При отсутствии предпочтений все допустимые варианты равноправны, и технология их отладки и обработки должна обеспечивать формально равные шансы вычисления таких вариантов. (Похожая проблема характерна для организации обслуживания в сетях и выполнения заданий операционными системами. Все узлы и задания сети должны быть потенциально достижимы, если нет формального запрета на оперирование ими.)
Представление вариантов в чем-то подобно определению ветвлений, но без предикатов, управляющих выбором ветви. В некоторых языках, например, учебно-игрового характера, можно указать вероятность выбора варианта. В языках логического и генетического программирования считают возможным прямой перебор вариантов, сопоставляемых с образцами, и организацию возвратов при неудачном варианте.
В отличие от множества элементов, набор вариантов не требует одновременного существования всех составляющих. Поэтому и программирование вариантов можно освободить от необходимости формулировать все варианты сразу. В логическом программировании можно продумывать варианты отношений между образцами формул постепенно, накапливая реально встречающиеся сочетания, как и методы обработки классов объектов в ООП. Содержательно такой процесс похож и на уточнение набора обработчиков прерываний на уровне оборудования.
Кроме основной программы, выполняющей целевую обработку данных, отлаживается коллекция диагностических реакций и процедур продолжения счета для разного рода неожиданных событий, препятствующих получению результата программы.
Обычно понятие алгоритма и программы связывают с детерминированными процессами.
Но эти понятия не очень усложняются, если допустить недетерминизм, ограниченый конечным числом
вариантов , так что в каждый момент времени из них существует только один вариант.
По смыслу выбор варианта похож на выбор произвольного элемента множества.
{ a | b | c } = э { a, b, c }
Чтобы такое понятие промоделировать обычными функциональными средствами, нужны дополнительные примитивы. Например, чтобы определить выбор произвольного элемента из списка L, можно представить рекурсивное выражение вида:
(любой L) = {( car L) | (любой (cdr L)) }
Если варианты в таком выражении рассматривать как равноправные компоненты, то не ясно, как предотвратить преждевременный выбор пустого списка при непустом перечне вариантов.
Чтобы решить эту задачу, вводится специальная форма ESC (ТУПИК), действие которой заключается в том, что она как бы "старается" по возможности не исполняться. Иными словами, при выборе вариантов предпочитаются варианты, не приводящие к исполнению формы ESC. (Такая же проблема возникает при обработке пустых цепочек в грамматиках. Аналогичным образом эта проблема решена при моделировании процессов интерпретированными сетями Петри [17] — соглашением о приоритете раскрашенных переходов в сравнении с пустыми.)
Уточненное таким образом определение выбора произвольного элемента списка можно представить формулой вида:
(любой L) = { (car L) | (любой (cdr L)) | (if (nl L) ESC) }
В какой-то момент L становится пустым списком, и его разбор оказывается невозможным. Тогда действует ESC.
Следует иметь в виду, что варианты не образуют иерархии. Их аксиоматика подобна так называемой упрощенной теории множеств. Принципиальная особенность — совпадение предикатов принадлежности и включения.
Другие построения, характерные для теории множеств: { x | P(X) } — множество элементов, обладающих свойством P.
Определение вида
(F x) = {(if (P ( car L )) (cons ( car L) (F ( cdr L))) ) | (if (nl L) esc) }
недостаточно, т.к. порождаемые варианты элементов, удовлетворяющих заданому свойству, существуют в разные моменты времени и могут не существовать одновременно. Чтобы иметь все
варианты одновременно, требуется еще один примитив ALL, обеспечивающий накопление всех реально осуществимых вариантов.
(F x) = (ALL {(if (P ( car L )) (cons ( car L) (F ( cdr L)) ) ) | (if (nl L) esc) } )
Обработка множеств и последовательностей
При реализации недетерминированных моделей обычно используются средства обработки множеств и последовательностей. В современных системах функционального программирования такие средства достаточно разнообразны. Здесь приведены лишь наиболее очевидные:
Member — выделяет часть списка, начиная с заданного объекта, Nil — если такого объекта в списке нет.
(member ‘a (b a c)) ;= (a c) (member ‘d (b a c)) ;= Nil
Set-difference — строит список элементов первого аргумента, не входящих во второй аргумент. Имеет деструктивный аналог — nset-difference.
Set-exlusive-or — строит список элементов первого или второго аргумента, но не входящих в оба сразу. Имеет деструктивный аналог — nset-exlusive-or.
Union — объединение множеств — строит список элементов первого или второго аргумента. Имеет деструктивный аналог — nunion.
Intersection — пересечение множеств — строит список элементов первого, входящих во второй аргумент. Имеет деструктивный аналог — nintersection.
Delete — строит последовательность из элементов второго аргумента за исключением совпадающих с первым аргументом. Имеет деструктивный аналог — remove.
(delete 1 ‘(1 2 1 3 1 4)) ;= (2 3 4)
Concatenate — строит новую последовательность заданного типа из своих аргументов, начиная со второго, при этом копирует их, кроме последнего. Для списков имеет деструктивный аналог — nconc.
Elt— выдает элемент последовательности по заданному номеру.
Find — отыскивает заданный символ в последовательности, можно управлять направлением поиска.
Sort — упорядочивает последовательность по заданному предикату.
(sort ‘(1 2 1 3 1 4) #’<) ;= (1 1 1 2 3 4)
Map — отображает с помощью данной функции ряд последовательностей в новую последовательность типа, заданного первым аргументом. Отображающая функция — второй аргумент. Кратность применения отображающей функции определяется длиной кратчайшего аргумента, начиная с третьего. Имеет деструктивный аналог map-into, строящий результат из первого аргумента.
Reverse — обращает последовательность. Имеет деструктивный аналог nreverse.
Position — выдает номер позиции первого вхождения заданного символа в последовательность.
Substitute — выполняет систематическую замену "старого" символа на "новый" в последовательности. Имеет деструктивный аналог — nsubstitute.
Maphash — методично применяет отображающую функцию двух аргументов к каждой паре из ключа и соответствующего значения в хэш-таблице.
Пересечение множеств A и B
(all ( lambda (x y) { (if (= x y) x) | esc }) (любой A) (любой B) )
Реализация недетерминированных моделей
Необходимая для такого стиля работы инструментальная поддержка обеспечивается в GNU Clisp механизмом обработки событий throw-catch, для которого следует задать примерно такое взаимодействие:
(defun vars (xl)(catch 'esc ; перебор вариантов до первого тупика (cond ; vars not Nil ((null xl)(escape)) ((car xl) (cons (car xl)(vars (cdr xl)))) )))
(defun escape () (throw 'esc Nil)) ; сигнал о попадании в тупик
(print(vars ())) (print(vars '(a))) (print(vars '(a b c))) (print(vars (list 'a 'b (vars ()) 'c)))
В этой схеме THROW играет роль прерывания процесса, а CATCH — обработчика прерываний.
Их взаимодействие синхронизировано с помощью тэга, идентифицирующего уровень, на котором расположена ловушка для соответствующего прерывания. При этом есть возможность указать передаваемое "наверх" значение. Содержательно такая схема взаимодействия похожа на PROG-RETURN, с той разницей, что отсутствует зависимость от расположения в тексте программы.
Получается, что в любом выражении можно выполнить разметку ветвей на нормальные и тупиковые. Тупики можно связать с различными тэгам и выставить ловушки на заданные тэги. При попадании в тупик формируется значение всей структуры, размещенной внутри ловушки.
Используя тупики и ловушки, можно организовать перебор вариантов до первого беступикового или собрать все беступиковые варианты. Первое можно сделать, используя отображения (map), а второе — первый подходящий — слегка модифицированным evcon, можно с добавочной ловушкой на прерывание при достижении успеха.
Более сложно обеспечить равновероятность выбора
вариантов. Наиболее серьезно возможность такой реализации рассматривалась в проекте языка SETL 12. Похожие механизмы используются в языках, ориентированных на конструирование игр, таких как Grow, в которых можно в качестве условия срабатывания команды указать вероятность.
В задачах искусственного интеллекта работа с семантическими сетями, используемыми в базах знаний и экспертных системах, часто формулируется в терминах фреймов-слотов (рамка-щель), что конструктивно очень похоже на работу со списками свойств.
Каждый объект характеризуется набором поименованных свойств, которые, в свою очередь, могут быть любыми объектами. Анализ понятийной системы, представленной таким образом, обычно описывается в недетерминированном стиле.
Следует отметить неисчерпаемый ряд задач, при решении которых результативно используются недетерминированные модели:
Обоснование упорядочений в традиционных алгоритмах — выделяется доалгоритмический уровень, на котором просто анализируются таблицы возможных решений и постепенно вырабатываются комплекты упорядочивающих условий и предикатов.Переформулировка задач и переопределение алгоритмов с целью исключения необоснованных упорядочений — одна из типовых задач оптимизации, особенно при переходе от обычных программ к параллельным. Приходится выяснять допустимость независимого исполнения всех ветвей и управляющих их выбором предикатов.Обобщение идеи абстрактных машин с целью теоретического исследования, экспериментального моделирования и прогнозирования недетерминированных процессов на суперкомпьютерах и многопроцессорных комплексах (многопроцессорная машина Тьюринга и т.п.).Конструирование учебно-игровых программ и экспериментальных макетов, в которых скорость реализации важнее, чем производительность.Описание и реализация недетерминизма в языках сверхвысокого уровня, таких как Planner, Setl, Sisal, Id, Haskell и др.Недетерминированные определения разных математических функций и организация их обработки с учетом традиции понимания формул математиками.Моделирование трудно формализуемых низкоуровневых эффектов, возникающих на стыке технических новинок и их массового применения как в научных исследованиях, так и в общедоступных приборах.Обработка и исследование естественно языковых конструкций, речевого поведения, культурных и творческих стереотипов, социально-психологических аспектов и т.п.Организация и разработка распределенных вычислений, измерений, Grid-технологий, развитие интероперабельных и телекоммуникационных систем и т.п.
Используемые при исследовании и решении таких задач модели дают богатый материал для развития нового поколения информационных систем, концептуальную основу которых можно изучать с помощью небольших функциональных программ.Принятая при решении таких задач техника сопоставления с образцом в значительной мере может быть осуществлена как работа с необязательными параметрами, что иллюстрирует эффективная версия определения сцепления списков 7:
(defun append (&optional first &rest others ) (if (null others) first (nconc (copy-list first) (apply #’append others))) )
В этой версии исключено копирование первого списка, когда других списков нет, и копии сцепляемых списков производятся лишь однократно.
Асинхронные процессы и параллелизм
Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри.
Заметное место среди языков функционального программирования занимают языки организации распределенных и параллельных вычислений. Практики с большой похвалой отзываются о языке функционального программирования Erlang фирмы Ericsson. Здесь мы рассмотрим один из довольно известных — язык функционального программирования SISAL [11].
создание универсального функционального языка;разработка техники оптимизации для высокоэффективных параллельных программ; достижение эффективности исполнения, сравнимой с императивными языками типа Fortran и C;внедрение функционального стиля программирования для больших научных программ.
Название языка расшифровывется как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка SISAL следует отметить наиболее характерные, связанные с функциональным стилем программирования:
Эти цели содателей языка SISAL подтверждают, что функциональные языки способствуют разработке корректных параллельных программ. Одна из причин заключается в том, что функциональные программы свободны от побочних эффектов и ошибок, зависящих от реального времени. Это существенно снижает сложность отладки. Результаты переносимы на разные архитектуры, операционные системы или инструментальное окружение. В отличие от императивных языков, функциональные языки уменьшают нагрузку на кодирование, в них проще анализировать информационные потоки и схемы управления. Легко создать функциональную программу, которая является безусловно параллельной, если ее можно писать, освободившись от большинства сложностей параллельного программирования, связанных с выражением частичных отношений порядка между отдельными операциями уровня аппаратуры. Пользователь Sisal-а получает возможность сконцентрироваться на конструировании алгоритмов и раз работке программ в терминах крупноблочных и регулярно организованных построений, опираясь на естественный параллелизм уровня постановки задачи.
Начнем с примера программы:
1. Вычисление числа ? (пи).
For % инициирование цикла Approx := 1.0; Sign := 1.0; Denom := 1.0; i := 1
while i <= Cycles do % предусловие завершения цикла Sign := -Sign; % однократные Denom := Denom + 2.0; % присваивания Approx := Approx + Sign / Denom; % образуют i := i + 1 % тело цикла
returns Approx * 4.0 % выбор и вычисление результата цикла end for
2. Это выражение также вычисляет число ? (пи).
for i in [1..Cycles/2] do % пространство параллельно % исполнимых итераций
val := 1.0/real(4*i-3) — 1.0/real(4*i-1); % тело цикла, для каждого i % исполняемое независимо
returns sum( val ) % выбор и свертка результатов % всех итераций цикла
end for * 4.0 % вычисление результата % выражения
Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0.
3, 4. В for-выражениях операции dot и cross могут порождать пары индексов при формировании пространства итерирования:
for i in [1..2] dot j in [3..4] do % для пар индексов [1,3] и % [2,4] returns product (i+j) % произведение сумм end for % = 24 for i in [1..2] cross j in [3..4] do % для пар [1,3], [1,4], [2,3] % и [2,4] returns product (i+j) % произведение сумм end for % = 600
5. Итеративное for-выражение с обменом данными между итерациями:
for I := 1 while I < S do K := I; I := old I + 2; % значение из предыдущей итерации J := K + I; returns product(I+J) end for
Как это свойственно языкам фукнционального программирования, Sisal язык математически правильный — функции отображают аргументы в результаты без побочных эффектов, и программа строится как выражение, вырабатывающее значение. Наиболее интересна форма параллельного цикла. Она включает в себя три части: генератор пространства итераций, тело цикла и формирователь возвращаемых значений.
SISAL-программа представляет собой набор функций, допускающих частичное применение, т.е. вычисление при неполном наборе аргументов. В таком случае по исходному определению функции строятся его проекции, зависящие от остальных аргументов, что позволяет оперативно использовать эффекты смешанных вычислений и определять специальные оптимизации программ, связанные с разнообразием используемых конструкций и реализационных вариантов параллельных вычислений.
function Sum (N); % Сумма квадратов result (+ ( sqw (1 .. N)));
Обычно рассматривают оптимизации, обеспечивающие устранение неиспользуемого кода, чистку циклов, слияние общих подвыражений, перенос участков повторяемости для обеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла, втягивание константных вычислений, уменьшение силы операций, удаление копий агрегатных конструкций и др.
Построение ряда целых от
|
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N))))) (defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) ) |
| Пример 12.1. Построение ряда целых от M до N с последующим их суммированием. |
| Закрыть окно |
| X * 0 = 0 car (A …) = A X*1 = X при любом X X-X = 0 X/X = 1 и т.п. |
| Пример 12.2. |
| Закрыть окно |
Смешанные вычисления
Идея смешанных вычислений с точки зрения реализации близка технике ленивых вычислений, но сложилась концептуально из несколько иных предпосылок [9]. Рассматривается пара Программа-Данные при недостаточных данных, отображаемая в так называемую остаточную программу, которая может дать нужный результат, если дать недостающие данные. Для определения такого отображения понадобилась разметка действий программы на исполнимые и задерживаемые. Если такую разметку не связывать с отсутствием данных, то получается модель, практически подобная вычислениям с задержками и возобновлением.
Не всегда неопределенность части данных мешает организовать вычисление.
Рассмотрим
(if (< X Y) Z T)
или эквивалент
if X < Y then Z else T
Если X и Y не определены, но известно, что X лежит в интервале [1, 4], а Y в интервале [5, 6], то логическое выражение X<Y определено, и можно сделать вывод относительно выбора ветви условного выражения и, возможно, получить его значение.
Изучение смешанных вычислений может исходить из разных толкований понятия частичности, т.е. функций, определенных не на всей области их существования.
Первые работы Lombardi в этой области посвящены частичным вычислениям, т.е. обработке частично определенных выражений над числами. Реализация такой обработки на Лиспе осуществляла выполнимые операции и строила из полученных частичных результатов и невыполнимых операций некоторый промежуточный результат — выражение, доопределив которое, можно получить полный результат.
В.Э. Иткин оценивал частичность как практичный критерий эффективности организации деятельности.
При подготовке программ на Лиспе неопределенность часто представляют пустым списком, предполагая, что в него просто не успели что-то записать. Такое представление не всегда достаточно корректно и может потребовать дополнительных соглашений при обработке данных, по смыслу допускающих NIL в качестве определенного значения. Так, при реализации Lisp 1.5 введено соглашение, что значение атома в списке свойств хранится упакованым в список [1].
В работах по семантике стандартных языков программирования принято сведение к неопределенности значений любых операций, зависящих от неопределенных данных.
Это приводит на практике к необоснованным потерям части определенной информации и результатов.
A_1+...+A_100_000_000+неопределенность -> неопределенность
Можно обратить внимание, что невелика практическая разница в уровне определенности данных вида (A …) и (A F), где F — рецепт вычисления, про который не всегда известно, приведет ли он к получению результата. Поэтому лучше было бы неопределенные данные "накрывать" рецептами, использующими специальные функции, нацеленные на раскрытие неопределенностей.
Например, роль такой функции может сыграть запрос у пользователя дополнительной информации:
(A …) => (A . ||(read))
В определении интерпретатора обработка неопределенностей сосредоточена в функции ERROR.
(defun eval (e AL) … ((assoc e AL)(cdr (assoc e AL))) (T(ERROR '"неопределенная переменная")) … )
В определение функции ERROR можно включить обращение к READ, обрамленное сообщением о ситуации с информацией о контексте.
(defun apply (f args AL) … ((assoc f AL)(apply (cdr (assoc f AL)) (evlis args AL)AL)) (T (ERROR ‘"неопределенная функция")) … )
При отладке сложных комплексов часто неразработанные определения замещают временными "заглушками", которые помогают разобраться в будущей программе по частям. Такую работу можно стандартизировать заданием предварительных определений функций в виде отображения типа аргументов в тип результата. Соответственно, исполнение предопределенной таким образом функции можно интерпретировать как проверку аргументов на соответствие типу аргументов и выдачу в качестве результата вариантов значения, принадлежащего типу результата.
При небольшом числе значений заданного типа, например истинностные значения, может быть целесообразным полный перебор таких значений с последующим выбором реальной альтернативы пользователем.
(cond (e r)(T g)) => (assoc e (list (cons T (eval r AL)) (cons Nil (eval g AL))) )
Таким образом выполнятся обе ветви, их результаты ассоциируются с различными значениями заданого типа, что позволяет получить нужный результат, как только доопределится ранее не определенное значение. Это позволяет избежать повторного выполнения предшествующих вычислений, если их объем достаточно велик.
Применение библиотечных процедур, зависящих от слишком большого числа параметров, можно упростить для пользователя построением проекций на типовые комплекты трудно задаваемых параметров, понимаемых как определение режима работы процедуры.
(defun f (x y z a b c … v t u) (g …)) (defun Fi (x y z ) (f x y z ai bi ci … vi ti ui))
Примерно это и делает необязательный параметр вида &optional.
Такое построение можно рассматривать как декомпозицию, разделение, сортировку на выполнимые и невыполнимые действия, при которой выполнимые действия в тексте определения замещаются их результатом, а невыполнимые преобразуются в остаточные, что все вместе образует проекцию процедуры на заданную часть ее параметров.
Многие выражения по смыслу используемых в них операций иногда определены при частичной определенности их операндов, что часто используется при оптимизаци кода программ:
X * 0 = 0 car (A …) = A X*1 = X при любом X X-X = 0 X/X = 1 и т.п.
Пример 12.2.
Представление функции в некоторых точках при отладке можно задать ассоциативной таблицей:
(setq f ‘((a1 . r1)(a2 . r2)(a3 . r3) …)) (defun f (x) (assoc x f))
В такое точечное определение легко добавлять недостающие пары, соответствующие нужным демонстрационным тестам при макетировании программ для согласования их функций на начальных этапах разработки, о чем еще будет речь в лекции 14.
Итак, мы получили некоторое число схем, различных с точки зрения управления вычислениями, полезных в разных ситуациях:
частичные;интервальные; многовариантные;предопределения; точечные; проекции.
Возможны и другие, обеспечивающие оптимизацию, компиляцию, предвычисления, макрогенерацию текста программы, что в перспективе может покрыть полное пространство обработки программ в рамках единой методики.Например, основой единого подхода может быть так называемый трансформационный подход, заключающийся в сведении смешанных вычислений к преобразованию программ посредством набора базовых трансформаций.
Замедленные вычисления
Средства управления процессами в функциональном программировании изначально опираются на интуитивное представление о вычислении выражений, согласно которому функция применяется к заранее вычисленным аргументам.
Ради полноты пространства вычислений, гибкости программ и результативности процессов такое представление пришлось расширить и ввести категорию специальных функций, которые "знают", когда и что из их аргументов следует вычислить. Специальные функции могут анализировать и варьировать условия, при которых вычисление аргументов необходимо. Так используется возможность манипулировать данными, представляющими выражения, и явно определять в программах позиции обращения к интерпретатору. Эта возможность применялась для поддержки стандартной программотехники и традиционных форм конструирования функциональных объектов.
Свойственная функциональному программированию тенденция к полномасштабному применению всех попадающих в поле зрения средств логически требует перехода от частных случаев к поддержке универсального механизма, т.е. от набора конкретных специальных функций к более общему аппарату управления процессами вычислений.
Результат управления проявляется в изменении некоторых оценок, например можно влиять на эффективность и надежность программ, обусловленную целостностью объемных, сложных данных, избыточностью вычислений, возможно, бесполезных выражений, необоснованной синхронизацией формально упорядоченных действий. Подобные источники неэффективности могут быть устранены достаточно простыми методами организации частичных вычислений с учетом дополнительных условий для их фактического выполнения, таких как достижимость или востребованность результата вычислений.
Любое очень объемное, сложное данное можно вычислять "по частям". Вместо вычисления списка
(x1 x2 x3 ... )
можно вычислить x1 и построить структуру:
(x1 ( рецепт вычисления остальных элементов))
Получается принципиальная экономия памяти ценой незначительного перерасхода времени на вспомогательное построение.
Рецепт — это ссылка на уже существующую программу, связанную с контекстом ее исполнения, т.е. с состоянием ассоциативного списка в момент построения рецепта.
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M (ряд_цел (1+ M) N)))))
(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( сумма (cdr X))))) )
Пример 12.1. Построение ряда целых от M до N с последующим их суммированием.
Введем специальные операции || — приостановка вычислений и @ — возобновление ранее отложенных вычислений. Избежать целостного представления ряда целых можно, изменив формулу:
(defun ряд_цел (M N) (cond ((> M N) Nil) (T(cons M ( || (ряд_цел (1+ M) N))))))
(defun сумма (X) (cond ((= X 0) 0) (T (+ (car X)( @ ( сумма (cdr X))))) ))
Чтобы исключить повторное вычисление совпадающих рецептов, в его внутреннее представление вводится флаг, имеющий значение T — истина для уже выполненых рецептов, F — ложь для невыполненных.
Тогда в выражении (all (cons { 1 | 2 } || (цел 3 100) )) второй аргумент cons выполнится только для одного варианта, а для второго подставится готовый результат. Таким образом, рецепт имеет вид:
{ ( F e AL ) | ( T X ) },
где X = ( eval e AL ).
Это позволяет распространить понятие данных на бесконечные, рекурсивно-вычислимые множества. Например, можно работать с рядом целых, больших чем N.
(defun цел (M) (cons M ( || (цел (1+ M) ))))
Можно из организованного таким образом списка выбирать нужное количество элементов, например первые K элементов можно получить по формуле:
(defun первые (K Int) (cond ((= Int Nil) Nil)((= K 0) Nil) (T (cons (car Int)( первые ( @ (cdr Int))) )) ))
Эффект таких приостанавливаемых и возобновляемых вычислений получается путем следующей реализации операций || и @:
||e = > (lambda () e ) @e = > (e ),
что при интерпретации приводит к связыванию функционального аргумента с ассоциативным списком для операции || и к вызову функции EVAL для операции @.
Обычно в языках программирования различают вызовы по значению, по имени и по ссылке. Техника приостановки и возобновления функций может быть названа вызовом по необходимости.
В некоторых языках программирования, таких как язык SAIL и Hope, отложенные или замедленные вычисления — lazy evaluation основная модель вычислений.
Наиболее частый вариант — приостановка аргументов всех определенных пользователем функций и операции CONS. В таком случае порождаются многократные приостановки, что требует итеративного возобновления до непосредственно исполняемого рецепта.
Более подробно о тонкостях определения ленивых вычислений рассказано в книге Хендерсона [3].
Конструирование распознавателей
Результативность функций высших порядков Хендерсон показывает на модельной задаче построения распознавателя контекстно-свободного языка [3].
В качестве примера такого языка рассмотрен синтаксис понятия «слог», образованный по правилам из гласных и согласных звуков, что можно представить грамматикой вида:
<а-гр> ::= А | А <а-гр>
<в-гр> ::= В | В <в-гр>
<слог> ::= <а-гр> <в-гр> | <в-гр> <а-гр> | <в-гр> <а-гр> <в-гр>
В этой грамматике «А» и «В» — терминальные символы, «слог», «а-гр» и «в-гр» — нетерминальные символы (метапонятия), «слог» — основное понятие. Необходимо быстро построить предикат is-syllable, выделяющий списки, представляющие правильно построенные слоги в соответствии с приведенными правилами.
Такое построение можно выполнить с помощью ряда функций высокого порядка, конструирующих распознаватели для альтернатив и цепочек из понятий, к которым сводится определение грамматики языка. Предполагается, что каждому правилу будет соответствовать свой распознающий предикат. Для простоты ограничимся случаями из пар альтернатив и двухзвенных цепочек.
Пусть тексты этого языка представляются списками из однобуквенных атомов A и B. Допустим, имеются предикаты is-A и is-B, выделяющие одноэлементные списки (A) и (B), соответственно.
(defun is-a (x)(cond ((eq(car x) 'a) (null (cdr x))) )) ; распознаватель A (defun is-b (x)(cond ((eq(car x) 'b) (null (cdr x))) )) ; распознаватель B
Типовые ранги этих функций одинаковы: List (X) -> Bool. Таким же должен быть и ранг результирующей функции is-syllable. При ее построении будет применена вспомогательная функция более высокого порядка is-alt, которая из произвольных предикатов конструирует новый предикат, перебирающий варианты правил и выдающий Nil, если ни одно из них не подходит. Функция is-alt может быть определена следующим образом:
(defun is-alt (p q) #'(lambda (x) (cond ((funcall p x )T) ; конструктор распознавателя альтернатив ((funcall q x) T) (T Nil))))
Ее типовый ранг имеет вид:
(List(X)->Bool List(X)->Bool ) -> List(X)->Bool
Можно использовать эквивалент:
(defun is-alt (p q) #'(lambda (x) (if (funcall p x) T (funcall q x)) )
Предикат both, работающий как логическая связка «и», можно реализовать как обычную функцию с типовым рангом (Bool Bool) -> Bool.
(defun both (x y) (cond ( x y)(T Nil)) ) ; проверка одновременности условий
Еще одна вспомогательная функция высокого порядка is-chain из произвольных предикатов конструирует новый предикат, выясняющий, не выделяют ли исходные предикаты смежные звенья цепочки. Типовый ранг этой функции должен быть таким же, как у is-alt, т.к. их результаты используются при разборе и анализе текста в одинаковых позициях.
(defun is-chain (p q) #'(lambda (x ) ; конструктор распознавателя цепочек (cond ((null x) (both (funcall p x) (funcall q nil)) ) ; пустая цепочка ((both (funcall p x) (funcall q nil)) T) ; префикс без суффикса ((both (funcall p Nil) (funcall q x)) T) ; суффикс без префикса ((both (funcall p (cons (car x)Nil)) (funcall q (cdr x)) ) T) ; допустимое разбиение (T(funcall (is-chain (lambda(y) (funcall p(cons(car x)y))) q ) (cdr x) )) ))) ; сдвиг границы разбиения вправо
Из данного распознавателя is-a можно бы и без функций высших порядков построить распознаватель is-a-gr, распознающий группу из любого числа символов A:
(defun is-a-gr (x ) (if x ; распознаватель цепочек из A (cond ((eq (car x) 'a) (is-a-tl (cdr x)) ) ; <а-гр> ::= А | А <а-гр> (t nil) ) Nil))
(defun is-a-tl (x)(cond ((null x)T)((eq (car x)'A)(is-a-tl (cdr x )) )))) ; хвост цепочки из A
Но использование конструкторов is-alt и is-chain, показанное на примере распознавателя is-b-gr, позволяет построить определение, синтаксически подобное правилу грамматики:
(defun is-b-gr (x ) (funcall (is-alt #'is-b is-chain #'is-b #'is-b-gr)) x )) ; распознаватель цепочек из B ; <в-гр> ::= В | В <в-гр>
Теперь опробованные приемы конструирования распознавателей применяем к построению функции is-syllable, активно опираясь на чисто внешнее, синтаксическое подобие определению заданной грамматики:
(defun is-syllable (x ) ; распознаватель слога (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) ; BA (is-alt (is-chain #'is-a-gr #'is-b-gr) ; AB (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr)) ; BAB ) ) x ))
(is-syllable '(a b)) (is-syllable '(b a)) (is-syllable '(b a b )) (is-syllable '(b b b b a a b b ))
Сопоставляя правила и полученное определение распознавателя, можно убедиться, что собственно конструирование распознавателя осуществляется и модернизируется сравнительно быстро: достаточно свести распознаваемый язык к композиции альтернатив и цепочек.
<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр>
(defun is-syllable (x ) ; распознаватель слога ; <слог> ::= (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) ; BA ; <в-гр> <а-гр> (is-alt (is-chain #'is-a-gr #'is-b-gr) ; AB ; | <a-гр> <b-гр> (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr)) ; BAB ; | <в-гр> <а-гр> <в-гр>
) ) x ))
Результат сопоставления показывает, что достигнуто синтаксическое подобие определения грамматики и построенного распознавателя. Это значит, что определение можно автоматически отобразить в такой распознаватель. Отображение — функция высокого порядка, вырабатывающая в качестве результата распознаватель языка, порождаемого исходной грамматикой.
(defun is-alt (p q) #'(lambda (x) (cond ((funcall p x )T) ((funcall q x) T) (T Nil))))
(defun is-chain (p q) #'(lambda (x ) (cond ((null x) nil) ; пустая цепочка недопустима ((both(funcall p x) (funcall q nil)) T) ; префикс допустим ((both(funcall p Nil) (funcall q x)) T) ; суффикс допустим ((both(funcall p (cons (car x)Nil)) (funcall q (cdr x)) ) T) ; допустимое разбиение (T(funcall (is-chain (lambda(y) (funcall p(cons(car x)y))) ; сдвиг вправо границы разбиения (lambda(y)(funcall q y)) ) (cdr x))) )))
(defun is-syllable (x ) ; распознаватель слога (funcall (is-alt (is-chain #'is-b-gr #'is-a-gr) ; BA (is-alt (is-chain #'is-a-gr #'is-b-gr) ; AB (is-chain #'is-b-gr (is-chain #'is-a-gr #'is-b-gr)) ; BAB ) ) x ))
<слог> ::= <в-гр> <а-гр> | <а-гр> <в-гр> | <в-гр> <а-гр> <в-гр>
Преобразование определений
Конечно, построенное выше определение не отличается эффективностью. Обычно синтаксические формулы приводят к нормализованной форме, гарантирующей полезные свойства распознавателей и удобство их построения. Выбор нормализованной формы и процесс нормализации обосновывается доказательными построениями, на практике воспринимаемыми как эквивалентные преобразования. Преобразования формул — еще один интересный класс задач символьной обработки. Для демонстрации рассмотрим модель реализации функций свертки текстов. При подходящем выборе обозначений такие функции можно применять для преобразования синтаксических формул с целью приведения к нормализованной форме.
Пусть свертки системы текстов представлены в стиле самоописания подобно формам Бекуса-Наура списком вида:
( (Тексты (Имя Вариант ...)...) ; первое имя — обозначение системы текстов ; за ним следуют варианты поименованных текстов (Вариант Элемент ...) ; Вариант представляет собой ; последовательность Элементов (Элемент Имя Лексема (Варианты)) ; Элемент — это или Имя, или Лексема, ; или Варианты в скобках )
Для системы текстов «((м а ш и н а)(м а ш а)(ш и н а))» можно дать свертку вида:
( (пример (ма ((ш н) (ш а)) ( ш н ) ) (н ина) )
Построение свертки системы текстов выполняется функциями 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 ((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.
Функции names, words и lexs задают алфавит и разбивают его на терминальные и нетерминальные символы на основе анализа их позиций в определении.
(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))) ;; неопределяемые лексемы
Функции d-lex и d-names формируют нечто вроде встроенной базы данных, хранящей определения символов для удобства дальнейшей работы.
(defun d-lex ( llex) ;; самоопределение терминалов (mapcar #'(lambda (x) (set x x) ) llex) )
(defun d-names ( llex) ;; определение нетерминалов (mapcar #'(lambda (x) (set (car x )(cdr x )) ) llex) )
Функции h-all, all-t и pred раскрывают слияния общих фрагментов системы текстов.
(defun h-all (h lt) ;; подстановка голов (mapcar #'(lambda (a) (cond ((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) ))
Функции sb-nm, chain и LeveL1 строят развернутые, линейные тексты из частей, выполняя подстановку определений, сборку и выравнивание.
(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) (T (append (car ll) (level1 (cdr ll)) )) ))
На основе приведенных вспомогательных функций общая схема развертки языка по заданному его определению (свертке) может быть выполнена функцией lang:
(defun lang ( frm ) ;; вывод заданной системы текстов (d-lex (lexs frm)) (d-names frm) (pred (eval (caar frm)) '(()) ) )
Вот и тесты к этой задаче, предложенные И.Н. Скопиным, справедливо предположившим, что для решения задач синтаксически управляемой обработки текстов хорошо подходит функциональный стиль программирования на Лиспе:
(lang (print (bnf 'vars '((m a s h a)(m a s h i n a)(s h i n a)) '((n (i n a))) )))
(lang '((vars (m a ((s h a)(s h n))) (s h n) ) (n (i n a)) ) )
Цель преобразования синтаксических формул при определении анализаторов и компиляторов можно проиллюстрировать на схеме рекурсивного определения понятия «Идентификатор»:
Идентификатор ::= БУКВА | Идентификатор БУКВА | Идентификатор ЦИФРА
Удобное для эффективного синтаксического разбора определение имеет вид:
Идентификатор ::= БУКВА | БУКВА КонецИд
КонецИд ::= БУКВА КонецИд | ЦИФРА КонецИд | ПУСТО
Синтаксическая диаграмма анализатора
Рис. 13.1.
Этот пример показывает, что удобные для анализа формулы приведены к виду, когда каждую альтернативу можно выбрать по одному текущему символу. Система CLOS поддерживает ООП с выделением методов для одноэлементных классов, распознаваемых простым сравнением. Тем самым обеспечено удобное построение программ над структурами, подобными нормализованным формам.
Например, определение:
<а-гр> ::= А | А <а-гр>
<в-гр> ::= В | В <в-гр>
<слог> ::= <а-гр> <в-гр> | <в-гр> <а-гр> | <в-гр> <а-гр> <в-гр>
можно привести к виду, не требующему возвратов при анализе:
<а-гр> ::= А <а-кон> <а-кон> ::= <пусто> | A <а-кон>
<в-гр> ::= B <в-кон> <в-кон> ::= <пусто> | B <в-кон>
<слог> ::= A <а-кон> B <в-кон> |B <в-кон> A <а-кон> <в-кон>
Если программирование сводит алгоритм решения задачи к программе из определенной последовательности шагов, то конструирование строит программу решения задачи из решений типовых вспомогательных задач. Для задачи реализации языка программирования ключевой (но не единственной) типовой задачей является определение реализуемого языка. Ее решение открывает возможности автоматизированного конструирования анализаторов и компиляторов. Автоматизацию конструирования системы программирования обеспечивают методы синтаксического управления обработкой информации и методы смешанных/частичных вычислений, позволяющие выводить определение компилятора программ из определения интерпретатора.
Все это хорошо изученные задачи, имеющие надежные решения, знания которых достаточно для создания своих языков программирования и проведения экспериментов с программами на своих языках. Существует ряд программных инструментов, поддерживающих автоматизацию процесса создания и реализации языков программирования и более общих информационных систем обработки формализованной информации, например YACC, LEX, Bison, Flex, основные идеи применения которых достаточно близки изложенным выше методам обработки формул и текстов. Очередной этап в этом направлении открывают технологии типа .Net и DotGNU.
Ранжирование функций
Применение функций высших порядков естественным образом завершает освоение функционального программирования как логической системы, допускающей конструирование функциональных объектов при решении задач регулярной обработки формализованной информации. Подобные задачи возникают при реализации и настройке сложных информационных систем, таких как операционные системы, системы программирования, текстовые и графические процессоры, системы управления базами данных, поддержки проектов и т.п.
Функции высших порядков используют другие функции в качестве аргументов или вырабатывают их как результат.
(defun mul-N (N) #'(lambda (x) (* x N))) ; конструктор семейства функций, множащих ; аргумент на N (funcall (mul-N 25) 7) ; применение частной функции, умножающей на 25
Правильность выражений с такими функциями требует корректной подстановки параметров и учета ранга функции, определяющего возможность манипулирования функциональными значениями. Функции можно ранжировать на основе так называемых типовых выражений, представляющих области определения и значения функций. Например,
x+1 : Number -> Number
x+y : (Number Number) -> Number
Отсутствие таких средств в языке можно компенсировать соответствующими комментариями [3].
Суперпозицию функций можно характеризовать следующими типовыми выражениями:
S(h,g) = { при h: X -> Y, g: Y -> Z строит f=g(h) — суперпозиция } : (X->Y Y->Z) -> (X->Z)
(defun super (f g) #'(lambda (x) (funcall f (funcall g x)) )) ; конструктор суперпозиции функций
(funcall (super #'car #'cdr) '(1 2 3)) ; применение суперпозиции CAR и CDR
Двойное применение функции можно определить независимо или через суперпозицию — типовое выражение от этого не зависит, но оно представляет собой параметризованное выражение.
W f = ((lambda x)(f (f x))) = S (f,f) { дважды применяется функция } : (Number->Number) -> (Number->Number)
или более точно:
: (X->X) -> (X->X),
где X — произвольный тип значения. Типовое выражение представляет зависимость от этого типа — параметризованный тип значения.
(defun duble (f) #'(lambda (x) (funcall f(funcall f x)) )) ; конструктор двойного применения функции
(funcall (duble #'car) '(((1) 2) 3)) ;= (1)
(defun duble (f) (funcall #'super f f)) ; двойное применение функции через суперпозицию
(funcall (duble #'car) '(((A B) B) C)) ; = (A B)
Можно ввести обозначения:
Atom — атомы, Number — число, List (X) — NIL или списки из элементов типа X Bool — NIL или T,` Some — любой объект.
Соответственно пишутся типовые выражения для элементарных функций:
cons : (X List (X)) -> List (X) car : List (X) -> X cdr : List (X) -> List (X) eq : (Atom Atom) -> Bool atom : Some -> Bool : (Atom -> T) & (List (X) -> NIL) null : Some -> Bool : (NIL -> T) & (Atom \=NIL -> NIL) & (List(X)\=NIL -> NIL)
Таким же образом можно специфицировать и универсальную функцию:
eval [e, al]:(Some List( (Atom . Some ) )) -> Some | | | List( (Atom . Some) ) Some{ могут попасть и неправильные выражения }
apply [fn, (a1 a2 …), al]:(List( Some ) -> Some List( Some ) List((Atom . Some) )) | | | -> Some | | List((Atom . Some)) | List(Some) (List(Some) -> Some
Отображающий функционал также может характеризоваться типовым выражением:
map [x, f] :( List(X) (X->Y) ) -> List(Y)
(defun map (x f) (cond (x (cons (funcall f (car x)) (map (cdr x) f ))))) (map '((1) (2) (3)) #'car )
Можно построить функцию, непосредственно преобразующую свой функциональный аргумент в новую функцию.
mapf [f] : List(X->Y) ->( List(X) -> List(Y))
(defun mapf (f) #'(lambda (x) (cond (x (cons (funcall f (car x)) (funcall (mapf f ) (cdr x)) ))) )) (funcall (mapf #'car ) '((1) (2) (3)) )
Аргумент может быть списком функций, результаты которых следует собрать в общий список.
manyfun [lf] : List(X->Y) -> (X -> List(Y)) | | |_____список | | результатов функций | |_____тип аргумента | отдельной функции |____________________список функций (defun manyfun (lf) #'(lambda (x) (cond (lf (cons (funcall (car lf) x) (funcall (manyfun (cdr lf)) x) ))) )) (funcall (manyfun '(car cdr length)) '(1 f (2 T) (3 D e)) )
Таким образом можно как бы «просачивать» определения функций над простыми данными, распределять их по структурам данных и тем самым распространять простые функции на сложные данные подобно матричной арифметике. Такой стиль работы характерен для теории комбинаторов и языка FORTH.
Похожие построения предлагаются Бэкусом в его программной статье о функциональном стиле программирования [20] и в языке APL, ориентированном на обработку матриц.
Существует ряд языков функционального программирования, требующих или допускающих спецификацию объектов, что, кроме дисциплины программирования, дает средства для корректной работы с пакетами, сопряжения с модулями на других языках, оптимизирующих преобразований, распараллеливания и верификации программ (Sisal, ML и др.).
Макетирование функций
При разработке больших программ, особенно по нисходящей методике, необходимость в тестировании и отладке возникает отчасти раньше, чем подготовлен текст программы. Макет программы — это некоторый предварительный ее текст, допускающий уточнение — доопределение.
Простейший макет может быть создан из небольшой коллекции тестов, иллюстрирующих поведение программы в наиболее важных точках. Выбор таких точек — необходимая работа, результаты которой многократно используются на всех фазах жизненного цикла программы: при конструировании алгоритмов, автономном тестировании компонентов программы, комплексной отладке программы, демонстрации программы всем заинтересованным лицам, при ее эксплуатации и развитии. Функционирование простых макетов особенно легко реализуется в языках, обладающих унификацией структур данных и функциональных объектов, таких как LISP и SETL.
SETL — язык сверхвысокого уровня, представляет собой попытку активного использования теоретико-множественных понятий в практике программирования [12].
Согласно концепции этого языка, понятие «функция» обладает двойственной природой. Функция может быть представлена в алгоритмическом стиле — определением процедуры, выполнение которой сопоставляет результат допустимому аргументу. Но столь же правомерно представление функции в виде графика, отображающего аргументы в результаты. Оба представления могут существовать одновременно — это всего лишь две реализации одной функции. Графическое понимание функции включает в себя и табличную реализацию подобно математическим таблицам Брадиса. Кроме того график функции не обязан быть линией — это может быть фигура произвольных очертаний. Следовательно, аргументу может соответствовать множество результатов, лежащих на пересечении вертикали с этой фигурой — графиком функции. При такой трактовке нет ничего удивительного в постепенном накоплении или построении графика функции. Можно задать небольшое множество точек графика, а потом постепенно его пополнять. По замыслу Дж.Шварца, автора языка SETL, такая методика может выполнять роль оптимизации особо сложных вычислений.
Более формальный макет может быть построен из спецификаций функций в виде типовых выражений, задающих описание типов аргументов и результатов. Такой макет может работать как «заглушка» для нереализованных компонентов. Вместо них может работать универсальная функция, проверяющая соответствие фактических аргументов предписанному типу данных и вырабатывающая в качестве результата произвольное данное, соответствующее описанию результата. Этот механизм будет более эффективен в паре с простым макетом из тестов, если результат выбирать из коллекции тестов.
Мемо-функции и тестирование
Не менее ценные следствия из унификации структурных значений и функциональных объектов дает накопительный, кумулятивный эффект ряда сеансов обработки рекурсивных программ, содержащих общие компоненты. Допустимость совместного хранения функциональных определений и тестов для их проверки в общей структуре, например в списке свойств атома, именующего функцию, позволяет строить технологические макеты с множественными определениями, коллекциями тестов и спецификаций, а также с документацией. Такие макеты пригодны для поддержки полного жизненного цикла программы. Они позволяют организовывать оперативное сравнение результатов при обновлении системы функций. На такой основе возможно автоматическое тестирование программ. С практической точки зрения технологические макеты — универсальный инструмент динамической оптимизации прикладных систем.
Представим, что вычисление каждой рекурсивной функции сопровождается сохранением пары "аргумент, результат". После этого можно запустить в дело слегка измененное правило интерпретации функций. Изменение заключается в следующем: прежде чем применять функцию к фактическому аргументу, выполняется проверка, нет ли для этого аргумента уже вычисленного результата. Готовый результат и есть результат функции, а в противном случае все работает как обычно. Механизм сохранения насчитанных результатов функций назван «мемо-функции» [4]. Естественно, основанием для его применения является достаточная сложность и частота обработки. Примечательная особенность данного метода — любая сложность очень частых вычислений стремится со временем к линейной.
Построение теорий при разработке программ
Принимая аксиоматическую теорию множеств за образец грамотно разработанной теории, попробуем проанализировать доказательные положения, полезные при обосновании и выполнении программистских проектов.
Многие построения в теории множеств выполнены над кумулятивной иерархией множеств, инициированной некоторым множеством объектов не множественной природы и пустого множества посредством операции объединения множеств. Кроме того, над множествами определены операции пересечения, дополнения, равенства, вхождения и включения, удовлетворяющие небольшому набору аксиом разной сложности.
Аналогично, структуры, такие как S-выражения, выстроены над атомами, не структурируемыми на компоненты, и пустого списка NIL, посредством операции CONS — консолидации. Над S-выражениями определены операции, позволяющие разбирать структуры на компоненты, сравнивать и анализировать структуры, отличать атомы от структур и пустой список от других данных. Элементарные операции подчинены аксиомам, обеспечивающим обратимость информационной обработки, и техника программирования на уровне строгих функций поддерживает прозрачность определений и скорость отладки.
Рассматривая программы и программные системы как формы представления знаний, трудно удержаться от попытки исследования динамики представления знаний на основе аналогии с развитием программ и программных систем.
Движущими силами этого развития являются: необходимость разных видов эффективной деятельности, потребность в уточнении представления знаний и установление новой информации, которая раньше не попадала в поле зрения или наблюдатель не был готов ее понять. Динамика представления знаний сводится к переходу от одного представления к другому.
Успешность эффективной деятельности ограничена «пропускной способностью» поля зрения. Это ограничение систематически преодолевается посредством обобщения, приводящего к представлениям более высокого порядка — представлениям более мощным, более организованным, например к процедурам, функциям, фреймам, шаблонам, макросам.
Последовательность шагов обобщения можно называть индуктивным развитием представления знаний. В методике программирования индуктивное развитие соответствует восходящим методам, «снизу вверх». Как правило, индуктивное развитие имеет некоторые пределы. Такие пределы при возрастании меры информативности используемых средств рассматриваются Д.Скоттом [5]. Интересен случай, когда пределом является теория, достаточная для порождения всей достоверной информации, установленной на данный момент времени. При разработке программ роль такого предела играет система программирования.
В результате индуктивного развития представления знаний наблюдается тенденция к возрастанию доли средств декларативного характера (таких как описания, отношения, формирователи, типы, фреймы, семантические сети, иерархии понятий, аксиоматические системы) в сравнении с долей средств процедурного характера (таких как действия, операции, операторы, процедуры, интерпретаторы, задания). Эта тенденция обуславливает рост эффективности применения дедуктивных методов и может рассматриваться как стимул к переходу от индуктивного развития к дедуктивному. Дедуктивный вывод осуществляет переход от потенциальных знаний к актуальным. Традиционно для этих целей в системах искусственного интеллекта используется метод резолюций, системы продукций и другие средства. Чередование стадий индуктивного и дедуктивного развития можно рассматривать как обоснование выбора метода программирования в зависимости от уровня развития знаний о решаемой задаче (зрелость, уровень изученности).
Применение развиваемых таким образом представлений может потребовать возврата к менее структурированным средствам (например, для упрощения обратной связи с областью, породившей решаемые задачи или для более тонкой детализации реализационных решений). Такой переход является конкретизацией представления знаний. В методике программирования конкретизация соответствует нисходящим методам «сверху вниз».
Независимо осуществляемое развитие приводит к задаче установления эквивалентности между различными системами представления знаний.При решении этой задачи возникают предпосылки для целенаправленного дедуктивного развития, что приводит к выравниванию потенциала систем (вводятся недостающие понятия, выполняются аналогичные построения, реализуются подобные инструменты). Таким образом, выделено четыре типа переходов: индуктивное и дедуктивное развитие, конкретизация и выравнивание. Эта классификация сопоставима с классификацией трансформаций программ в теории смешанных вычислений, предложенной А.П.Ершовым [9].
Итоги и выводы
Согласно рекомендациям специалистов по обучению информатике, функциональное программирование (ФП) входит в число основных подходов к изучению программирования в университетах (наряду с алгоритмическим , императивным , аппаратным, объектным и обзорно-ознакомительным). В целом средства и методы ФП образуют два слоя. Глубинный слой — локальное программирование
строгих функций , безотходных структур данных, обратимых контекстов, регулярных отображений, корректных функций высших порядков, универсальных функций и средств управления вычислениями. Внешний слой — функциональное моделирование широкого спектра парадигм программирования , обеспечивающее производственное программирование прототипами, дающее подход к оценке функциональности информационных систем и их компонентов. Глубинный слой дает концептуальную основу для применения и определения функций во всей полноте этого понятия, для его развития и выбора реализационных решений при разработке систем ФП, включая привлечение стандартной программотехники и деструктивных функций. Внешний слой открывает перспективы повышения уровня используемых конструкций на базе моделирования основных механизмов системного, низкоуровневого, оптимизационного, логического, высокопроизводительного, ООП и других подходов к разработке программ. Такие подходы расширяют понятие «функция», варьируют правила применения и реализации функций, конкретизируют расширения и специализацию систем ФП.
Фактически термин «функциональное программирование» используется при объединении в систему методов решения классов задач, обладающих исследовательскими аспектами, что влечет за собой необходимость развития полученных решений . Система предполагает общую
логику уточнения решаемых задач и формализацию обобщенных решений на основе специально выбранных базовых конструкций.
Базовые конструкции определяются как строгие функции .Общая логика развития задачи сводится к процессу раскрутки полного решения как набора шагов по расширению набора функций и повышению их потенциала использованием отображений , что обеспечивается надежными средствами языка функционального программирования (ЯФП) и быстро отлаживается на базе систем ФП (СФП), приспособленных к интерпретации программ.При необходимости выполняются формальные преобразования программ , (например, компиляция), обеспечивающие улучшение эксплуатационных характеристик, связанных с процессами исполнения программ.Важный критерий качества ФП — полнота системы функций и универсальность определений , дающая возможность синтаксически управляемой обработки данных с помощью функций высших порядков (ФВП), что существенно повышает надежность программирования.Разработка ИС средствами ФВП успешно выполняет роль прототипа для реализации другими, более распространенными средствами.
Оттолкнувшись от интуитивного представления о понятии «функция», мы для начала ограничились однозначными функциями , но разрешили предельно широкое толкование понятия «значение», включающее понятие «структура данных».
Ориентируясь на рекурсивные определения функций , мы ввели несложную схему, достаточно удобную для построения формул, задающих функциональные определения. При этом отмечено качественное различие между элементарными функциями, задаваемыми неформально вне метаязыка, и остальными функциями, определяемыми формулами языка, использующими обозначения элементарных функций. В качестве примера рассмотрен элементарный Лисп .Затем было конкретизировано основное множество значений функций как множество списков и атомов, на котором определены алгебра и логика, достаточные для обработки и анализа таких значений. Представления функций отображены в это множество и определена универсальная функция , по списочному представлению функции и ее аргументов строящая результат. Рассмотрены примеры структур данных, полезных при реализации списков, интерпретируемых как функции (стеки, пары, блоки, односвязные списки, расстановочные таблицы и др.). Изучено расширение функционального языка, достаточное для императивно- процедурного стиля программирования, что обеспечивает помимо нисходящей методики разработки программ и восходящую, более естественную для несложных задач.Определена абстрактная машина, содержащая реализацию элементарных функция языка и поддерживающая интерпретацию функционального языка, и проанализирован компилятор с абстрактного синтаксиса функционального языка программирования на языково-ориентированную абстрактную машину.
Таким образом, завершена нисходящая линия определения языка функционального программирования, позволяющая во всех деталях представлять один возможный процесс применения функций на уровне интуитивных понятий, структур данных и машинного кода. Затем была выполнена серия обобщений представления о процессах применения функций, т.е. осуществлена восходящая линия определения функционального языка.
Этот процесс не всегда удовлетворителен по эффективности с разных точек зрения. Повышение эффективности обычно требует развития размерности пространства, в котором рассматриваются оптимизируемые понятия.
Исследованы возможные направления развития как по вертикали, так и по горизонтали. Для этого изучены традиционные решения по организации структур данных и систем программирования для поддержки функционального программирования, а также списки свойств атомов и деструктивные функции. Неоднозначные функции могут рассматриваться через понятие отношения. При изучении идей ООП показано, что идеи эти весьма близки и легко поддерживаются базовыми средствами функционального программирования. Достаточно лишь продемонстрировать технику работы с классами и экземплярами объектов и способы определения методов их обработки.Рассмотрено понятие вариантов или альтернативных процессов, успешного выполнения одного из которых достаточно для построения результата функции. Реализация таких процессов потребовала уточнить определение абстрактной машины, чтобы обеспечить сохранение состояния памяти для выхода из тупиковых ситуаций. Такое же уточнение необходимо для обеспечения диагностичности.Представлены методы управления процессами вычисления функций и средства, обеспечивающие выбор времени выполнения отдельных шагов процесса, соответствующих конкретным формулам. Организация таких процессов обеспечивается совместным хранением данных и рецептов их получения, что заодно снимает требование конечности представления данных. Достаточно конечности рецепта. Техника работы с рецептами, заключающаяся в приостановке и возобновлении программ, не требует специальных реализационных механизмов.
Функции высших порядков показаны как инструмент естественной модуляризации программ, например, техникой продолжений, достаточной для достижения подобия представления функций и обрабатываемых ими типов данных. Иллюстрация такого подобия на задаче построения синтаксического анализатора позволяет замкнуть изученные механизмы на исходный язык программирования.
Практические аспекты
Требования к учебно-экспериментальной практике можно условно разделить на четыре группы, различающиеся по целям:
элементарное знакомство с концепциями ФП;
эксперименты по системному программированию на базе ФВП;
xмоделирование изучаемых приложений средствами СФП;изучение средств СФП как практического инструмента .
Первая из этих целей — знакомство — может быть достигнута на уровне концептуального минимума , достаточно далекого от решения технических проблем. В круге общеизвестных задач, пригодных для показа изучаемых явлений, на уровне регулярной обработки небольших текстов.
Вторая цель — эксперимент — гораздо чувствительнее к максимальному потенциалу реализации СФП, к ее гибкости и переносимости. Самоприменимость языков функционального программирования здесь гарантирует очевидные преимущества в сравнении со стандартными и производственными языками.
Третья цель — функциональное моделирование — обеспечивается как практичный компромисс , учитывающий разного рода обстоятельства: исторически сложившиеся стандарты, профессиональные стереотипы и жаргон, уровень квалификации заинтересованных лиц и многое другое, что порождает новые языки и их диалекты.
Четвертая цель — реальный инструмент — требует методично выбранного приемлемого баланса между уровнем изученности класса решаемых задач и уровнем организованности комплекта средств, имеющихся в СФП.
Элементарный Лисп, описанный как Pure Lisp Дж. Мак-Карти, идеально соответствует цели знакомства с ФП, его базовые средства доступны практически в любой реализации основных диалектов Лиспа. Навыки и понимание основ обработки структурированных данных на уровне элементарного Лиспа пригодятся при работе с любой СФП. Конструирование функций средствами чистого Лиспа доставляет интеллектуальное удовольствие, оно сродни решению математических головоломок. Благодаря функциональной полноте Лиспа, изучение других инструментов ФП, а также основных средств проектирования и программирования, можно обосновывать и понимать через программирование на Лиспе.
Во всей полноте идеи функционального программирования поддержаны в проекте Lisp 1.5 , выполненном Дж. Мак-Карти и его коллегами. В этом исключительно мощном языке не только реализованы основные средства, обеспечившие практичность и результативность функционального программирования, но и впервые опробован целый ряд поразительно точных построений, ценных как концептуально, так и методически и конструктивно, понимание и осмысление которых слишком отстает от практики применения. Понятийно-функциональный потенциал языка Lisp 1.5 в значительной мере унаследован стандартом Common Lisp , но многие идеи пока не получили достойного развития. Вероятно, это дело будущего — для нового поколения системных программистов.
По мере накопления опыта реализации СФП на базе Лиспа и других языков сформированы обширные библиотеки функций, весьма эффективно поддерживающих обработку основных структур данных — списков, векторов, множеств, хэш-таблиц, а также строк, файлов, каталогов, гипертекстов, изображений. Существенно повысилась результативность системных решений в области работы с памятью, компиляцией, манипулирования пакетами функций и классами объектов. Все это доступно в современных СФП, таких как GNU Clisp , Python, Cmucl и др., основная проблема при изучении которых — слишком много всего, разбегаются глаза, трудно выбрать первоочередное. Хочется найти пересечение со знакомыми программами и воспроизвести любимые приемы в новой стилистике — естественный путь для решения задач функционального моделирования .
С конца 70-х годов появились Лисп-процессоры , доказавшие, что пресловутая неэффективность функционального программирования обусловлена характеристиками оборудования, а не стилем программирования. Функциональные мини-языки хорошо показали себя и при решении задач аппаратного уровня. К середине 90-х годов появились весьма убедительные результаты [13]
по динамической оптимизации процессов, и были осуществлены высокопроизводительные схемы работы с памятью на новом оборудовании.
Все это превращает СФП в практичный и перспективный инструментарий.
Полученное при изучении ФП обобщенное представление о процессах выполнения функций нацеливает на решение задач в виде определения семейства процессов и выбор подходящего представителя семейства. Привлекая теоретико-множественный подход как обнадеживающую аналогию, наполнение понятий при функциональном программировании и организации его системной поддержки осуществляется следующими преобразованиями:
проекция в более удобное, простое, но не слишком бедное множество;ортогонализация независимых вспомогательных понятий;унификация родственных понятий;распространение реализуемых действий на новые области существования.
Посредством таких преобразований производится уточнение структуры пространства , в котором рассматривается каждое понятие. Кроме шагов расширения по горизонтали обычно происходит и реорганизация по вертикали — детализация и обобщение, при котором, как правило, возрастает число измерений исходного пространства, точнее, видимой его части.
Такая схема подтверждается самой историей развития диалектов языка Лисп и родственных ему языков программирования. (Pure Lisp , Lisp 1.5 , Lisp 2, Interlisp, CommonLisp, MicroLisp, MuLisp, Sail, Hope, Miranda, Scheme, ML, GNU Clisp , CLOS, Emacs, Elisp, xLisp, Vlisp, AutoLisp, Haskel, Python, cmucl ). Не вдаваясь здесь в подробности этой истории (ее изложение заслуживает отдельного курса!), отметим лишь особенности свободно распространяемой системы GNU Clisp , которую легально можно использовать в качестве системы, поддерживающей ФП.
Стандарт Common Lisp в сравнении с Лиспом от Мак-Карти имеет ряд отличий, несколько влияющих на программотехнику. Прежде всего, это касается реализации списков свойств атомов. Данная структура реализована в императивном стиле, в виде таблицы с непрерывным «забыванием» информации после каждого присваивания. В результате исключено многократное связывание глобальных объектов с их определениями, а заодно и множественное объявление свойств атомов.Конечно, такие эффекты можно смоделировать, но это не столь гармонично. Другое отличие связано с механизмом контекстов вычисления выражений. Стандарт при вычислении значений переменных по умолчанию привлекает статический контекст, иначе переменную надо объявить специальной. Третье отличие затрагивает унификацию представления функций и обрабатываемых ими значений. При внешнем подобии — и то, и другое выглядит как круглоскобочные списки, но реализационно это разные типы данных, и возникает нечто вроде приведения типа ( funcall ) в ситуациях вызова функций, конструируемых «на лету». Имеются и другие, не столь явные отличия, которые пока не стоит упоминать. GNU Clisp , xLisp, cmucl соответствуют стандарту Common Lisp . Документация по этим СФП доступна на сайтах любителей Лиспа и ФП, а также на многих университетских сайтах.
Развитие парадигм программирования
Знакомое нам из курса философии слово «парадигма » имеет в информатике и программировании узко профессиональный смысл, сближающий их с лингвистикой. Парадигма программирования как исходная концептуальная схема постановки проблем и их решения является инструментом грамматического описания фактов, событий, явлений и процессов, возможно, не существующих одновременно, но интуитивно объединяемых в общее понятие.
Каждая парадигма программирования имеет свой круг приверженцев и класс успешно решаемых задач. В их сфере приняты разные приоритеты при оценке качества программирования, отличаются инструменты и методы работы и соответственно — стиль мышления и изобразительные стереотипы. Нелинейность развития понятий, зависимость их обобщения от индивидуального опыта и склада ума, чувствительность к моде и внушению позволяют выбору парадигм в системе профессиональной подготовки информатиков влиять на восприимчивость к новому.
Ведущая парадигма прикладного программирования на основе императивного управления и процедурно - операторного стиля построения программ получила популярность более пятидесяти лет назад в сфере узкопрофессиональной деятельности специалистов по организации вычислительных и информационных процессов. Последнее десятилетие резко расширило географию информатики, распространив ее на сферу массового общения и досуга. Это меняет критерии оценки информационных систем и предпочтения в выборе средств и методов обработки информации.
Консервирующееся в наши дни доминирование одной архитектурной линии, стандартного интерфейса, типовой технологии программирования и т.д. чревато потерей маневренности при обновлении информационных технологий. Особенно уязвимы в этом отношении люди, привыкшие в учебе прочно усваивать все раз и навсегда. При изучении языков программирования подобные проблемы обходят за счет одновременного преподавания различных языков программирования или предварительного изложения основы, задающей грамматическую структуру для обобщения понятий, изменяемость которых трудно улавливается на упрощенных учебных примерах [14]. Именно такую основу дает изучение функционального программирования тем, что оно нацелено на изложение и анализ парадигм , сложившихся в практике программирования в разных областях деятельности с различным уровнем квалификации специалистов, что может быть полезно как концептуальная основа при изучении новых явлений в информатике.
Общие парадигмы программирования, сложившиеся в самом начале эры компьютерного программирования, — парадигмы прикладного , теоретического и функционального программирования в том числе, имеют наиболее устойчивый характер.
Прикладное программирование подчинено проблемной направленности, отражающей компьютеризацию информационных и вычислительных процессов численной обработки, исследованных задолго до появления ЭВМ. Именно здесь быстро проявился явный практический результат. Естественно, в таких областях программирование мало чем отличается от кодирования, для него, как правило, достаточно операторного стиля представления действий. В практике прикладного программирования принято доверять проверенным шаблонам и библиотекам процедур, избегать рискованных экспериментов.
Ценится точность и устойчивость научных расчетов. Язык Фортран — ветеран прикладного программирования , постепенно стал несколько уступать в этой области Паскалю-Си, а на суперкомпьютерах — языкам параллельного программирования, таким как Sisal.
Теоретическое программирование придерживается публикационной направленности, нацеленной на сопоставимость результатов научных экспериментов в области программированияи информатики. Программирование пытается выразить свои формальные модели, показать их значимость и фундаментальность. Эти модели унаследовали основные черты родственных математических понятий и утвердились как алгоритмический подход в информатике. Стремление к доказательности построений и оценка их эффективности, правдоподобия, правильности, корректности и других формализуемых отношений на схемах и текстах программ послужили основой структурированного программирования и других методик достижения надежности процесса разработки программ, например грамотное программирование . Стандартные подмножества Алгола и Паскаля, послужившие рабочим материалом для теории программирования, сменились более удобными для экспериментирования аппликативными языками , такими как ML, Miranda, Scheme и другие диалекты Лиспа. Теперь к ним присоединяются подмножества C и Java.
Функциональное программирование сформировалось как дань математической направленности при исследовании и развитии искусственного интеллекта и освоении новых горизонтов в информатике. Абстрактный подход к представлению информации, лаконичный, универсальный стиль построения функций, ясность обстановки исполнения для разных категорий функций, свобода рекурсивных построений, доверие интуиции математика и исследователя, уклонение от бремени преждевременного решения непринципиальных проблем распределения памяти, отказ от необоснованных ограничений на область действия определений — все это увязано Джоном Мак-Карти в идее языка Лисп [11]. Продуманность и методическая обоснованность первых реализаций Лиспа позволила быстро накопить опыт решения новых задач, подготовить их для прикладного и теоретического программирования . В настоящее время существуют сотни функциональных языков программирования, ориентированных на разные классы задач и виды технических средств.
Основные парадигмы программирования сложились по мере возрастания сложности решаемых задач. Произошло расслоение средств и методов программирования в зависимости от глубины и общности проработки технических деталей организации процессов компьютерной обработки информации. Выделились разные стили программирования, наиболее зрелые из которых — машинно-ориентированное , системное , логическое , трансформационное , и высокопроизводительное /параллельное программирование.
Машинно-ориентированное программирование характеризуется аппаратным подходом к организации работы компьютера, нацеленным на доступ к любым возможностям оборудования. В центре внимания — конфигурация оборудования, состояние памяти, команды, передачи управления, очередность событий, исключения и неожиданности, время реакции устройств и успешность реагирования. Ассемблер в качестве предпочтительного изобразительного средства на некоторое время уступил языкам Паскаль и Си даже в области микропрограммирования, но усовершенствование пользовательского интерфейса может восстановить его позиции.
Системное программирование долгое время развивалось под прессом сервисных и заказных работ. Свойственный таким работам производственный подход опирается на предпочтение воспроизводимых процессов и стабильных программ, разрабатываемых для многократного использования. Для таких программ оправдана компиляционная схема обработки, статический анализ свойств, автоматизированная оптимизация и контроль. В этой области доминирует императивно -процедурный стиль программирования, являющийся непосредственным обобщением операторного стиля прикладного программирования . Он допускает некоторую стандартизацию и модульное программирование, но обрастает довольно сложными построениями, спецификациями, методами тестирования, средствами интеграции программ и т.п. Жесткость требований к эффективности и надежности удовлетворяется разработкой профессионального инструментария, использующего сложные ассоциативно семантические эвристики наряду с методами синтаксически-управляемого конструирования и генерации программ. Бесспорный потенциал такого инструментария на практике ограничен трудоемкостью освоения — возникает квалификационный ценз [15].
Высокопроизводительное программирование нацелено на достижение предельно возможных характеристик при решении особо важных задач. Естественный резерв производительности компьютеров — параллельные процессы . Их организация требует детального учета временных отношений и неимперативного стиля управления действиями. Суперкомпьютеры, поддерживающие высокопроизводительные вычисления, потребовали особой техники системного программирования . Графово-сетевой подход к представлению систем и процессов для параллельных архитектур получил выражение в специализированных языках параллельного программирования и суперкомпиляторах, приспособленных для отображения абстрактной иерархии процессов уровня задач на конкретную пространственную структуру процессоров реального оборудования [11], [16].
Логическое программирование возникло как упрощение функционального программирования для математиков и лингвистов, решающих задачи символьной обработки. Особенно привлекательна возможность в качестве понятийной основы использовать недетерминизм, освобождающий от преждевременных упорядочений при программировании обработки формул. Продукционный стиль порождения процессов с возвратами обладает достаточной естественностью для лингвистического подхода к уточнению формализованных знаний экспертами, снижает стартовый барьер [10].
Трансформационное программирование методологически объединило технику оптимизации программ, макрогенерации и частичных вычислений. Центральное понятие в этой области — эквивалентность информации. Она проявляется в определении преобразований программ и процессов, в поиске критериев применимости преобразований, в выборе стратегии их использования. Смешанные вычисления, отложенные действия, «ленивое» программирование, задержанные процессы и т.п. используются как методы повышения эффективности информационной обработки при некоторых дополнительно выявляемых условиях [9].
Экстенсивные подходы к программированию — естественная реакция на радикальное улучшение эксплуатационных характеристик оборудования и компьютерных сетей. Происходит переход вычислительных средств из класса технических инструментов в класс бытовых приборов. Появилась почва для обновления подходов к программированию, а также возможность реабилитации старых идей, слабо развивавшихся из-за низкой технологичности и производительности ЭВМ. Представляет интерес формирование исследовательского , эволюционного, когнитивного и адаптационного подходов к программированию, создающих перспективу рационального освоения реальных информационных ресурсов и компьютерного потенциала.
Исследовательский подход с учебно-игровым стилем профессионального, обучающего и любительского программирования может дать импульс поисковой изобретательности в совершенствовании технологии программирования, не справившейся с кризисными явлениями на прежней элементной базе. Эволюционный подход с мобильным стилем уточнения программ достаточно явно просматривается в концепции объектно-ориентированного программирования, постепенно перерастающего в субъектно-ориентированное и даже эго-ориентированное программирование. Повторное использование определений и наследование свойств объектов могут удлинить жизненный цикл отлаживаемых информационных обстановок, повысить надежность их функционирования и простоту применения. Когнитивный подход с интероперабельным стилем визуально-интерфейсной разработки открытых систем
и использование новых аудио-видео средств и нестандартных устройств открывают пути активизации восприятия сложной информации и упрощения ее адекватной обра ботки. Адаптационный подход с эргономичным стилем индивидуализируемого конструирования персонифицированных информационных систем предоставляет информатикам возможность грамотного программирования, организации и обеспечения технологических процессов реального времени, чувствительных к человеческому фактору.
Направление развития парадигмы программирования отражает изменение круга лиц, заинтересованных в развитии и применении информационных систем. Многие важные для практики программирования понятия, такие как события, исключения и ошибки, потенциал, иерархия и ортогональность построений, экстраполяция и точки роста программ, измерение качества и т.д. не достигли достаточного уровня абстрагирования и формализации. Это позволяет прогнозировать развитие парадигм программирования и выбирать учебный материал на перспективу компонентного программирования (COM/DCOM, Corba, UML и др.). Если традиционные средства и методы выделения многократно используемых компонентов подчинялись критерию модульности, понимаемой как оптимальный выбор минимального сопряжения при максимальной функциональности, то современная элементная база допускает оперирование поликонтактными узлами, выполняющими простые операции.
Парадигма программирования в образовательном процессе является инструментом формирования профессионального поведения. Программирование прошло путь от профессиональной деятельности высококвалифицированной элиты технических специалистов и научных работников до времяпрепровождения активной части цивилизованного общества. Освоение информационных систем через понимание с целью компетентных действий и ответственного применения техники сменилось интуитивными навыками хаотичного воздействия на информационную среду со скромной надеждой на везение, без претензий на знание. Обслуживание центров коллективного пользования, профессиональная поддержка целостности информации и подготовки данных почти полностью отступили перед самообслуживанием персональных компьютеров, независимым функционированием сетей и разнородных серверов со взаимодействием различных коммуникаций.
Противопоставление разрабатываемых программ, обрабатываемых данных и управления заданиями уступает представлению об интерфейсах, приспособленных для участия в информационных потоках подобно навигации. Прежние критерии качества: скорость, экономия памяти и надежность обработки информации — все больше заслоняются игровой привлекательностью и широтой доступа к мировым информационным ресурсам. Замкнутые программные комплексы с известными гарантиями качества и надежности форсированно вытесняются открытыми информационными комплектами с непредсказуемым развитием состава, способов хранения и обработки информации.
Эти симптомы обновления парадигмы программирования определяют направление изменений, происходящих в системе базовых понятий, в концепции информации и информатики. Тенденция использования интерпретаторов (точнее неполной компиляции) вместо компиляторов, анонсированная в концепции Java в сравнении с Си, и соблазн объектно-ориентированного программирования на фоне общепринятого императивно -процедурного стиля программирования можно рассматривать как неявное движение к функциональному стилю [2]. Моделирующая сила функциональных формул достаточна для полноценного представления разных парадигм , что позволяет на их основе экстраполировать приобретение практических навыков организации информационных процессов на будущее.
Лисп и принципы технической поддержки
История Лиспа насыщена жаркими спорами, противоречивыми суждениями, яркими достижениями и смелыми изобретениями. От первых сообщений Джона Мак-Карти о замысле языка символьной обработки (1958) и авторских проектов первых Лисп-систем (1960–1962) — через демонстрацию принципиальной решаемости проблем искусственного интеллекта (1964), разрешение теоретических парадоксов (1972–1974) [5], разработку признанных стандартов (1972–1980), построение специализированных диалектов и создание практичных реализаций для широкого спектра различных применений — до появления Лисп-компьютеров (1978), систем математической обработки информации (1965–1990), визуальных и сверхэффективных Лисп-систем (1992–2002) идеи Лиспа выдержали многогранную шлифовку, достойную самой высокой оценки специалистов. Написанная Дж.Вейценбаумом на Лиспе программа-собеседник "Элиза", имитирующая речевое поведение психоаналитика, дала положительный ответ на вопрос о возможности искусственного разума.
Этого более чем достаточно для того чтобы утверждать, что Лисп — гениальное творение, но тем не менее, потенциал данного языка еще предстоит раскрыть. Выразительная сила Лиспа обретает новое дыхание на каждом эволюционном витке развития информационных технологий. При сравнительном анализе информационных систем моделирование их семантики на Лиспе позволяет классифицировать функционирование по уровню сложности, зрелости, полноты, точности и организованности. Универсальность Лиспа достаточна для изучения на его основе любой парадигмы информатики и программотехники. Можно сказать, что Лисп содержит в себе эталонную семантическую систему, пригодную для измерения функциональности других систем.
Информационный мир становится все более динамичным — Лисп приспособлен к программированию развивающихся построений и реорганизуемых конфигураций из разносортных компонентов. Многие реализационные находки Лиспа, такие как ссылочная организация памяти, "сборка мусора" для повторного использования памяти, частичная компиляция программ с интерпретацией промежуточного кода, полиморфизм, длительное хранение атрибутов объектов в период их использования и т.д. перекочевали из области исследований и экспериментов на базе Лиспа в практику реализации операционных систем и систем программирования.
Общеизвестно, что Лисп — язык искусственного интеллекта и исследования наукоемких и новых направлений информационной обработки. Но этим влияние Лиспа не ограничено. Диалекты Лиспа (Logo, ML, MuLisp, Scheme, Hope, AutoLisp, CommonLisp, Reduce и др.) заняли обширную нишу в области учебно-экспериментального программирования , связанного с развитием теории программирования, системного программирования, разработки и прототипирования новых компьютерных комплексов и архитектур, конструирования и исследования систем построения оптимизирующих компиляторов и организации особо точных и высокопроизводительных вычислений.
Многообразие откликов на Лисп не случайно. На первый взгляд, идеи Лиспа противоречат традиционным подходам к программированию. Но это противоречие отступает перед строгой логикой языка, гармонично уравновешенной полнотой и ясностью реализационных решений. Определение Лиспа дает гибкую основу для развития, варьирования и расширения Лисп-систем средствами как самого Лиспа, так и его окружения. Объем такого определения не превышает одной страницы.
Понятийная картина Лиспа — удобный инструмент, помогающий представлять решения задач в оптимально универсальной форме, свободной от пресса как преждевременной конкретизации типов данных, так и избыточного обобщения алгоритмов при компиляции программ. На Лиспе решение задачи может быть выражено в терминах постановки задачи без привлечения реализационных сущностей и внешних интерфейсных эффектов.
Базис Лиспа предельно лаконичен — атомы и структуры из простейших бинарных узлов плюс несколько базовых функций и функционалов. Базис содержит встроенные (примитивные) функции, которые анализируют, строят и разбирают любые структурные значения (atom, eq, cons, car, cdr), и встроенные специальные функции и функционалы, которые управляют обработкой структур, представляющих вычисляемые выражения (quote, cond, lambda, label, eval). Над базисом строятся предельно простые формулы в виде круглоскобочных списков, где первый элемент — функция, остальные — ее аргументы, в том числе переменные, реализуемые с помощью разных вариантов стека или ассоциативного списка. Все остальные механизмы вычисления и преобразования формул могут сводиться к этому базису, рассматриваться как его вариант или расширение. Такой лаконизм сродни алгебре, способствующей проявлению общих закономерностей в работе с формулами над объектами разной природы. Подробнее с идеями Лиспа и его математическими основами можно ознакомиться на страницах журнала "Компьютерные инструменты в образовании", № 2–5 за 2002 год.
Синтаксис Лиспа не требует особых ресурсов для запоминания разделителей и/или ограничителей и напряженного внимания на распознавание синтаксических позиций в разных рамочных конструкциях. Универсальный разделитель — пробел, ограничители — круглые скобки. В скобки заключается представление функции с ее аргументами. Все остальное — вариации в зависимости от категории функций, определенности атомов и вычислимости выражений, типов значений и структур данных. Функционалы — это одна из категорий функций, используемая при организации управления вычислениями.
Программирование на Лисп нацелено на выделение универсальных функций и отображений, композиции которых строятся как формулы над значениями. При таком стиле малые программы над небольшими объемами данных не нуждаются в заботе о распределении памяти и преобразовании информации по конкретным адресам. Новая информация размещается в свободной памяти без неявного разрушения исходных построений. Высокий уровень представления программ на Лиспе обеспечивает их реальное абстрагирование от оборудования и практическую независимость от версии реализации и даже от диалекта языка. По современным меркам реализации Лиспа компактны и не слишком требовательны к оборудованию. Существуют свободно распространяемые версии, занимающие менее мегабайта, пригодные к применению на любом процессоре.
В нашей стране программирование мало соприкоснулось с Лиспом, хотя знакомство с языком состоялось из первых рук. Джон Мак-Карти в конце 1968 года познакомил Москву и Новосибирск с Лиспом, что побудило к реализации отечественных версий языка. Две реализации на БЭСМ-6 (ВЦ АН под рук. С. С. Лаврова [24] и ВЦ СО АН под руководством А. П. Ершова [25]) и одна на ЕС ЭВМ (ВЦ АН под рук. С. С. Лаврова) нашли применение в отечественных проектах по системному и теоретическому программированию, в исследованиях по математической лингвистике, искусственному интеллекту и обработке химических формул. Существовал также проект реализации на Эльбрусе (И.Н. Скопин).
В настоящее время наблюдается устойчивый рост рейтинга интерпретируемых языков программирования и включения в компилируемые языки механизмов символьной обработки и средств динамического анализа, что повышает интерес к Лиспу. Моделирующая сила Лиспа может послужить основой для очередного круга исследований в области компонентного программирования, формализации поведения информационных систем, разработки методов преобразования и защиты информации, высокопроизводительного программирования для суперкомпьютеров, создания прототипов систем для новых применений.
Лисп успешно работает на любом уровне абстрагирования информации от ассемблера и операционной оболочки до Internet-приложений и лингвистических интерфейсов, что подтверждает его звание подлинно универсального языка программирования, показавшего стойкую жизнеспособность и интеллектуальную практичность в широком спектре применений.
История создания и развития языка программирования ЛИСП интересна как социальный феномен осуществления замысла, вызвавшего серьезные возражения и математиков, и программистов, но показавшего удивительную живучесть. Критика теоретиков была связана с так называемой "парадоксальностью" бестипового лямбда-исчисления. Практиков пугали накладные расходы на сборку мусора и интерпретацию в сравнении с компиляцией и статическим распределением памяти. (О наличии компилятора в традиционных Лисп-системах вспоминали редко.)
Первоначально предназначенный для символьной обработки, этот язык утвердился в качестве аналога эсперанто для задач искусственного интеллекта. К середине семидесятых годов именно на Лиспе решались наиболее сложные в практике программирования задачи из области дискретной и вычислительной математики, системного, экспериментального и теоретического программирования, лингвистики, химии, биологии, медицины и инженерного проектирования.Пример AutoCAD — система автоматизации инженерных расчетов, дизайна и комплектации изделий из доступного конструктива.
Многие созревшие на базе Лиспа решения постепенно обрели самостоятельность и развиваются как функциональный стиль программирования и фреймовый подход к представлению знаний в экспертных системах. Семейство диалектов Лиспа включает в себя уже сотни языков, популярность наиболее удачных из них резко возрастает при смене парадигм программирования. Приверженцы Лиспа ценят его за элегантность, гибкость, а, главное, за способность к точному представлению программистских идей, удобной отладке и быстрому прототипированию. Основные из этих качеств присущи функциональному программированию на любом языке. Его идеи, механизмы и принципы могут служить методической и технологической базой информационной обработки при решении любых новых или сложных задач.
Возможности языка Лисп наиболее ярко проявились при pешении задач искусственного интеллекта, пионерские решения которых удались благодаря отказу от необоснованных ограничений на спектр экспериментально-исследовательской работы. Программная поддержка таких работ потребовала большого числа нетрадиционных решений и соглашений, основа которых предложена и опробована Дж. Мак-Карти с его коллегами и учениками в определении языка Лисп и в первых реализациях Lisp 1.0 и Lisp 1.5 [1]. Наиболее общие из них:
Унификация понятий
"функция" и "значение".
При символьном представлении информации нет принципиальной разницы в природе изображения значений и функций. Следовательно, нет и препятствий для обработки представлений функций теми же средствами, какими обрабатываются значения, т.е. представления функций можно строить из их частей и даже вычислять по мере поступления и обработки информации. Именно так конструируют программы компиляторы. В замкнутых системах не принято к такой технике информационных воздействий допускать обычных пользователей. Но исследователь вынужден вникать во все уровни своего экспериментального полигона.
Кроме функций-констант, вполне допустимы функции-переменные.
Отсутствие навыков работы с функциональными переменными говорит лишь о том, что надо осваивать такую возможность, потенциал которой может превзойти наши ожидания теперь, когда программирование становится все более аспектно и компонентно ориентированным. Объектно-ориентированная парадигма в этом плане не обладает достаточной функциональной полнотой.
Самоприменимость.
Первые реализации Лиспа были выполнены методом раскрутки, причем в составе системы сразу были предусмотрены и интерпретатор, и компилятор. Оба инструмента были весьма точно описаны на самом Лиспе, причем основной объем описаний не превосходил пару страниц, что позволяло активно использовать эти описания при изучении языка и программ, написанных на нем. Этот эксперимент послужил базой для определения систем программирования с помощью так называемой "операционной семантики", получившей развитие в работах по Венской методике определения языков и систем программирования [8].
Интегральность ограничений.
Если не хватает памяти, то принципиально на всю задачу, а не на отдельные блоки данных, возможно, не слишком существенных для ее решения. При недостатке памяти специальная программа-"мусорщик" пытается найти свободную память. Новые реализации этого механизма рационально учитывают преимущества восходящих процессов на больших объемах памяти.
Уточняемость решений.
Современное применение информационных систем достаточно широко соприкасается с вариантами доступных решений, необходимостью уточнять отдельные особенности применения готовых решений и трудоемкостью анализа и поиска рационального выбора комплекта используемых средств. Реализация Лиспа обычно содержит списки свойств объектов, приспособленные к внешнему доопределению отдельных элементов поведения программируемой системы.
Множественность определений.
Наиболее концептуально полный Lisp 1.5 допускает множественные определения имен, что в рамках настраиваемой интерпретации обеспечивает кроме общеизвестного полиморфизма более общие схемы обработки ряда версий или вариантов функциональных построений.
Расхожее мнение о неэффективности Лиспа столь же убедительно, сколь актуальное когда-то рассуждение о бесполезности интеллигентов, некачественно собирающих колхозную картошку. Как авиация не соревнуется с автотранспортом в объеме грузоперевозок, так и функциональное программирование несравнимо со стандартными парадигмами в массовости применения, но это не умаляет его достоинств.
Столь же расхожее утверждение, что функциональный стиль программирования на Лиспе обеспечивает ясность программ, требует поправки, что больше для тех кто пишет, чем для тех, кто читает. (При стихийно-алгоритмическом стиле программист часто не ведает, что же делает его программа — утрата единства замысла).
Многие современные языки и технологии программирования унаследовали опыт реализации и применения Лиспа и других языков символьной обработки. Так, например, Java берет на вооружение идеи неполной компиляции и освобождения памяти, объектно-ориентированное программирование реализует объекты, весьма похожие на списки свойств атомов Лиспа, хэш-таблицы языка Perl напоминают применение ассоциативных списков Лиспа. Python обрабатывает программы с нетипизированными переменными. Лисповское наследие в информатике достойно отдельного рассмотрения. Здесь мы сконцентрируемся на ключевой идее Лиспа — сведении понятия "программа" к взаимодействию разных категорий функций. Базирующееся на таком сведении функциональное программирование можно описать в терминах любого языка, но Лисп дает этой идее достаточно полное звучание и формирует некую шкалу сравнения и определения стандартных конструкций и методов программирования, а также упорядочение явлений, характерных для экспериментальной разработки программ и поиска новых областей их применения.
Математические основы функционального программирования
Сформулированная Джоном Мак-Каpти (1958) концепция символьной обработки информации компьютером восходит к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов прошлого века. Выбирая лямбда-исчисление как теоретическую модель, Мак-Карти предложил рассматривать функции как общее базовое понятие, к которому достаточно естественно могут быть сведены все другие понятия, возникающие при программировании [1].
Такое сведение вовсе не означает, что все понятия сваливаются в одну кучу, что исчезают границы между понятиями. Сведение выполнено так, что при сохранении всех понятийных границ выстроено более общее пространство, в рамках которого эти понятия упорядочены и могут взаимодействовать согласно формальным определениям.
Управление обработкой информации в лямбда-исчислении осуществляется в рамках иерархии свободных и связанных переменных, реализуемых с помощью таблицы соответствия символов и их толкования. Обработка представляется посредством интерпретации выражений, построенных из всюду определенных функций, аргументы которых упорядочены. Общностью такое построение сравнимо с аксиоматической теорией множеств.
Понятие "функция" связано с понятиями аргумента функции, области ее существования и значения, соответствия между ее аргументами и результатами, а также применения функции к ее аргументам. Существуют различные точки зрения на природу всех этих терминов, на границы определяющих их множеств, на возможность их взаимодействия в более общих построениях. Наиболее явные разночтения, связанные с трактовкой однозначности результата функции, могут быть устранены при рассмотрении структурных значений. Например, два разных значения при извлечении квадратного корня можно рассматривать как один результат из двух элементов. Еще более естественна такая точка зрения на однозначность результата для целочисленного деления: cуществует общая функция, которая выполняет деление одного целого числа на другое и вырабатывает результат, содержащий два элемента — частное и остаток от деления.
Кроме того, имеется две частных функции, каждая из которых выбирает из этого результата тот элемент, который нужен для объемлющей формулы. Не менее серьезная трудность связана с границами множеств разносортных объектов, таких как скаляры, структуры, представления функций. Функциональное программирование поддерживает универсальные методы обработки разносортных объектов.
Изучение функционального программирования начинается с овладения техникой работы с так называемыми "чистыми", строго математическими, идеальными функциями. Для реализации функций характерен отказ от необоснованного использования присваиваний и низкоуровневого управления вычислениями в терминах передачи управления. Такие функции удобны при отладке и тестировании благодаря независимости от контекста описания и предпочтения явно выделенного чистого результата. Трудоемкость отладки композиций из хорошо определенных функций растет аддитивно, а не мультипликативно. Кроме того, системы из таких функций могут развиваться в любом направлении: сверху вниз и снизу вверх (а также расширяясь и сужаясь, если понадобится) [23]. Можно быстро продвинуться по сложности решаемой задачи, не отвлекаясь на синтаксическое разнообразие и коллизии при обработке общих данных. Концептуально близкие идеи "структурированного программирования" были сформулированы лишь более чем через десять лет.
Особенно интересны рекурсивные функции и методы их реализации в системах программирования. Интуитивное понятие функции, в отличие от классического понятия множества, отчасти содержит концепцию времени: сначала аргументы вычисляются в порядке вхождения, затем в соответствии с заданным алгоритмом строится значение функции — ее результат, возможно, явно зависящий от результатов других функций или от этой же функции, но при других, ранее вычисленных, значениях аргументов. Обычно подразумевается, что значения аргументов вычисляются до того как к ним применяется функция. Но если в качестве данных допускать не только значения, но и символьные формы для вычисления этих значений, то вопрос о времени вычисления аргументов можно решать не столь категорично.
Кроме обычных функций, аргументы которых вычисляются предварительно, в ряде случаев можно рассматривать и реализовывать специальные функции, способные обрабатывать аргументы нестандартным способом по любой заданной схеме. Такое развитие понятия функции напоминает развитие понятия числа по мере расширения класса удобных формул над числами. (В этом отношении показательна аналогия с историей математики. Эволюция понятия числа содержит много резких обобщений с сохранением основных алгебраических свойств базовых операций и удобства работы с формулами. Так, от натуральных чисел перешли к отрицательным, ввели ноль, дробные, вещественные, иррациональные, комплексные и т.д.)
Далее понятие "функция" обогащается представлением о псевдо-функциях, используемых с целью представления аппаратных, зависимых от устройств действий (ввод/вывод, сообщения, рисование и т.п.), фактически осуществляющих известный побочный эффект в результате работы конкретного оборудования. Но формально все псевдо-функции обязательно выполняют и отображение аргументов в результаты, что позволяет им равноправно участвовать в любой позиции формулы, задающей вычислительный процесс. Формальный результат сопровождается дополнительными эффектами. Этот переход обеспечивает при необходимости корректное моделирование всей традиционной программотехники, включая присваивания, передачи управления, системные вызовы, обработку файлов и доступ к любым устройствам. Но все эти непредсказуемо сложные машинно-зависимые реалии при функциональном стиле программирования локализованы, наращиваются на ранее отлаженный каркас функционирования программы, их представления могут быть четко отделены от сущности решаемой задачи. Исследовательская и проектная работа обычно проходит фазу поиска оптимального решения. Функциональное программирование для поддержки этой фазы предлагает еще одно отступление от чистых функций: в качестве результата функции допускаются варианты значений, равноправно выбираемые из конечного множества значений, подобно псевдослучайным числам.
Равноправие не распространяется лишь на тупиковую ситуацию, когда ни один предложенный вариант не может быть вычислен. Именно эта идея составляет одну из привлекательных особенностей логического программирования, выделившегося в самостоятельную парадигму.
Императивная организация вычислений по принципу немедленного и обязательного выполнения каждой очередной команды не всегда эффективна. Существует много неимперативных моделей управления процессами, позволяющих прерывать и откладывать процессы, а потом восстанавливать их и запускать или отменять. Организация такого управления, достаточного для оптимизации и программирования параллельных процессов, реализуется с помощью так называемых "замедленных" или "ленивых" вычислений (lazy evaluation) . Основная идея таких вычислений заключается в сведении вызовов функций к представлению рецептов их вычисления в определенном контексте. Вычисляться каждый такой рецепт может не более чем один раз и то если его результат действительно нужен.
Здание функционального программирования получает логическое завершение на уровне определения функций высших порядков, удобных для синтаксически управляемого конструирования программ на основе спецификаций, типов данных, визуальных диаграмм, формул и т.п. Функциональные программы могут играть роль спецификации обычных итеративно-императивных программ. Иногда такой переход не вызывает затруднений. Факториал можно определить рекурсивно как сведение к значению функционала от предыдущего числа, но столь же понятно и определение в виде цикла от одного до N. На языке Sisal [11]
и цикла для этого не требуется, достаточно задать границы области, элементы которой перемножаются (* 1, ,N). Конечно, числа Фибоначчи легко порождать с помощью рекурсивного восходящего процесса, но и цикл с заданной границей заработает вполне практично. Однако бывают несложные задачи, для которых такой переход не столь прост. Вовсе не любая обработка произвольной последовательности легко излагается в терминах векторов, и многие задачи на больших графах могут весьма сложно приводиться к итеративной форме.
Заметные трудности в процесс сведения рекурсии к итерации создает динамика данных и конструируемые функции. Даже реализация равенства для произвольных структур данных при неизвестной размерности и числе элементов — дело непростое. Известно, что лаконичность рекурсии может скрывать нелегкий путь. А.П.Ершов в предисловии к книге П.Хендерсона [3] привел поучительный пример не поддавшегося А.Чёрчу решения задачи о рекурсивной формуле, сводящей вычитание единицы из натурального числа к прибавлению единицы {1 –1 = 0 | ( n +1 ) -1 = n}, полученного С.Клини лишь в 1932 году:
n–1 = F (n, 0, 0)
где
F (x, y, z) = если (x = 1) то 0 иначе если ((y +1) = x) то z иначе F (x, y +1, z +1)
Решение получилось через введение формально усложненной функции F со вспомогательными аргументами, что противоречит интуитивному стремлению к монотонности и движению от простого к сложному. Универсальность понятия "функция" и разнообразие видов его применения позволяет унифицировать используемые при описании процессов понятия "действие", "значение", "формула", "переменная", "выбор варианта" и пр. Все это — разные категории функций с различными формами унифицированного представления (записи, изображения) в тексте программы и правилами интерпретации (выполнения, вычисления), обеспечивающими получение результата функции при исполнении программы. Аргументами функции могут быть готовые данные или результаты других функций. Возможны ограничения на типы данных, допускаемых в качестве аргументов — тогда речь идет о частичных функциях. Такие функции должны выяснять допустимость фактических параметров и сообщать о несоответствии. Удобно, если часть такой работы берет на себя компилятор в классической традиции статического контроля правильности типов данных,но динамический контроль типов данных в условиях, характерных для современных информационных сетей, может быть надежнее, чем традиционный статический анализ, сложившийся для замкнутых, защищенных от несанкционированного доступа конфигураций, обеспечивающий гарантии сохранения скомпилированного кода программы при его использовании. (Имеется в виду вероятность искажения скомпилированного кода при его эксплуатации на компьютере в сетях.) Это приводит к компромиссу в виде объектно-ориентированного программирования, допускающего динамический контроль типов данных.
Общее представление о функциональном программировании и его применении
Идея функционального программирования опирается на интуитивное понятие о функциях как о достаточно общем механизме представления и анализа решений сложных задач. Механизм функций основательно изучен математиками, и это позволяет программистам наследовать выверенные построения, обладающие предельно высокой моделирующей силой [1]. Систематическое применение функционального программирования впервые достаточно ярко было продемонстрировано Джоном Мак-Карти и его учениками в методах реализации языка Лисп и программирования на этом языке. Наиболее очевидные из этих методов были успешно ассимилированы другими языками и системами программирования. Обычно про функциональное программирование вспоминают при смене технологий, когда возрастает роль аналитики и исследовательских задач. В настоящее время часто употребляют термин "функциональность" при сравнительной характеристике информационных систем, что, видимо, свидетельствует о проявлении новой метрики, заслуживающей отдельного рассмотрения [2].
Функциональный стиль объединяет разные подходы к определению процессов вычисления на основе достаточно строгих абстрактных понятий и методов символьной обработки данных. Связь функционального программирования с математическими основами позволяет в тексте программы наследовать доказательность построения результата, если она достигнута, причем с использованием разных методов абстрагирования решаемой задачи [2]
[3].
Сложность решения задач с помощью функциональных определений преодолевается чисто алгебраически: нацеленностью на формализацию основного множества объектов и определения полной семантической системы операций над ними. Это позволяет представлять классы задач и их решений строгими формулами, для наглядности упрощаемыми введением дополнительных функциональных символов. При необходимости такие символы вносятся в опpеделение алгебраической системы, что приводит к ее расширению. Вводятся новые функции, подобные леммам и другим вспомогательным построениям в математике.
Активно используется рекурсия и символьные обозначения как данных, так и действий и любых формул, удобных при определении функций.
Формально такое расширение является консервативным (новый символ определен с помощью старых), оно гарантирует сохранение всех функциональных свойств исходной системы. Минимальный набор обозначений, к которым можно свести все правильные, т.е. вычислимые формулы системы, играет роль базиса системы, реализация которого является минимальной версией всей системы.
Следует отметить, что при формальной эквивалентности разные расширения одного и того же базиса могут поддерживать различные применения и восприниматься как совершенно разные системы. Программисты вынуждены строить расширения, которые выглядят неконсервативными, так как целью их работы является именно изменение ряда характеристик функционирования исходной системы (компьютера, системы программирования и т.п.) с частичным сохранением заданных функциональных свойств.
Большинство систем программирования разработано с ориентацией на расширение, уточнение и настройку пользователем реализованных программных средств, свойства которых определены и обеспечены в процессе разработки. Такое разделение труда естественно при ориентации на решение задач с исчерпанным или четко ограниченным исследовательским компонентом. Но исходная разработка любой системы включает фазу формирования базиса и наполнения ядра системы в терминах, которые не сводятся к ее языку. Это позволяет независимо рассматривать один еще более общий уровень — аппликативные системы, в которые можно включать любые символы с определенным смыслом. Поведение такой системы будет обусловлено набором включенных в нее символов.
Основная трудность перехода к функциональному программированию — соблазн легкого пути, т.е. стремление быстро смоделировать привычные средства и методы программирования. Более надежный путь — исследовать функциональное программирование как незнакомый мир. Идеи функционального программирования легче воспринять как самостоятельную теорию или интеллектуальную игру, которая новыми путями непременно приведет к знакомым и интересным задачам, но обеспечит преимущество — изящные решения и глубину понимания.
Джон Мак-Карти предложил проект языка Лисп (LISP - LISt Processing) в качестве средства исследования границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта. Идеи этого языка вызвали не утихающие по сей день дискуссии о приоритетах в программировании и сущности программирования. Лисп послужил эффективным инструментом экспериментальной поддержки теории программирования и развития сферы его применения. Рост интереса к Лиспу коррелирует с улучшением элементной базы, повышением эксплуатационных характеристик оборудования и появлением новых сфер применения ИТ.
Существует и активно применяется более трехсот диалектов Лиспа и родственных ему языков: Interlisp, muLisp, Clisp, Scheme, ML, Cmucl, Logo, Hope, Sisal, Haskell, Miranda и др.
