Парадигмы программирования

Универсальная функция


Интерпретация или универсальная функция - это функция, которая может вычислять значение любой формы, включая формы, сводимые к вычислению произвольной заданной функции, применяемой к аргументам, представленным в этой же форме, по доступному описанию данной функции. (Конечно, если функция, которой предстоит интерпретироваться, имеет бесконечную рекурсию, интерпретация будет повторяться бесконечно.)

Определим универсальную функцию eval от аргумента expr - выражения, являющегося произвольной вычислимой формой языка Лисп.

Универсальная функция должна предусматривать основные виды вычисляемых форм, задающих значения аргументов, а также представления функций, в соответствии со сводом приведенных выше правил языка. При интерпретации выражений учитывается следующее:

  • Атомарное выражение обычно понимается как переменная. Для него следует найти связанное с ним значение. Например, могут быть переменные вида "x", "elem", смысл которых зависит от контекста, в котором они вычисляются.
  • Константы, представленные как аргументы функции QUOTE, можно просто извлечь из списка ее аргументов. Например, значением константы (QUOTE T) является атом T, обычно символизирующий значение "истина".
  • Условное выражение требует специального механизма для предварительного вычисления предиката и выбора нужной ветви. Например, интерпретация условного выражения:1)

    (IF (ATOM x) x (first (CAR x) ) ) должна обеспечивать выбор ветви в зависимости от атомарности значения переменной.

  • Остальные формы выражений рассматриваются по общей схеме как список из функции и ее аргументов. Обычно аргументы вычисляются, а затем вычисленные значения передаются функции для интерпретации ее определения. Так обеспечивается возможность писать композиции функций. Например, в выражении (first (CAR x)) внутренняя функция CAR сначала получит в качестве своего аргумента значение переменной x, а потом свой результат передаст как аргумент более внешней функции first.
  • Если функция представлена своим названием, то среди названий различаются имена встроенных функций, такие как CAR, CDR, CONS и т.п., и имена функций, введенные в программе, например first.
    Для встроенных функций интерпретация сама "знает", как найти их значение по заданным аргументам, а для введенных в программе функций - использует их определение, которое находит по имени.
  • Если функция использует лямбда-конструктор, то прежде чем его применять, понадобится связывать переменные из лямбда-списка со значениями аргументов. Функция, использующая лямбда-выражение,

    (LAMBDA (x) (IF (ATOM x) x (first (CAR x) )) ) зависит от одного аргумента, значение которого должно быть связано с переменной x. В определении используется свободная функциональная переменная first, которая должна быть определена в более внешнем контексте.
  • Если представление функции начинается с LABEL, то понадобится сохранить имя функции с соответствующим ее определением так, чтобы корректно выполнялись рекурсивные вызовы функции. Например, предыдущее LAMBDA-определение безымянной функции становится рекурсивным, если его сделать вторым аргументом специальной функции LABEL, первый аргумент которой - fisrt, имя новой функции.

    (LABEL first (LAMBDA (x) (IF (ATOM x) x (first (CAR x) )) ))


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

  • обработка структур данных (cons, car, cdr, atom, eq);
  • конструирование функциональных объектов (lambda, label);
  • идентификация объектов в контексте (имена переменных и названия функций);
  • управление логикой вычислений и границей вычислимости (композиции, quote, if, eval).


Прежде чем дать определение универсальной функции eval для вышеописанного подмножества Лиспа на языке Clisp, опишем, используя функцию DEFUN2), ряд дополнительных функций, обеспечивающих работу с переменными и названиями функций.

PAIRLIS - функция аргументов x, y, al строит список пар соответствующих элементов из списков x и y и присоединяет их к списку al. Полученный список пар, похожий на таблицу с двумя столбцами, называется ассоциативным списком или контекстом. Такой список используется для связывания имен переменных и функций при организации вычислений интерпретатором.



(DEFUN pairlis (x y al) (IF (null x) al (CONS (CONS (CAR x) ( CAR Y) ) (pairlis (CDR x) (CDR y) al) ))

(pairlis '(A B C) '(u t v) '((D . y)(E . y))) = ((A . u)(B . t)(C . v)(D . y)(E . y))

ASSOC - функция двух аргументов, x и al. Если al - ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения в контексте, реализованном как ассоциативный список.

(DEFUN assoc (x al) (IF (equal x (CAAR al)) (CAR al) (assoc x (CDR al)) )



Частичная функция - рассчитана на наличие ассоциации.

(assoc 'B '((A . (m n)) (B . (CAR x)) (C . w) (B . (QUOTE T)))) = (B . (CAR x))

Универсальная функция eval, которую предстоит определить, должна удовлетворять следующему условию: если представленная аргументом форма сводится к функции, имеющей значение на списке аргументов этой же формы, то данное значение и является результатом функции eval.

(eval '(fn arg1 ... argK)) = результат применения fn к аргументам arg1, ..., argK.

Явное определение такой функции позволяет достичь четкости механизмов обработки Лисп-программ.

(eval '((LAMBDA (x y) (CONS (CAR x) y)) '(A B) '(C D) )) = (A C D)

Вводим две основные функции eval и apply для обработки форм и обращения к функциям, соответственно. Каждая из этих функций использует ассоциативный список для хранения связанных имен - значений переменных и определений функций. Сначала этот список содержит лишь определения встроенных констант.

Вернемся к синтаксической сводке вычислимых форм в примере 2.1.

Каждой ветви этой сводки соответствует ветвь универсальной функции:

(DEFUN eval (e) (evl e '((Nil . Nil) (T . T))))

Вспомогательная функция evl понадобилась, чтобы в eval ввести контекст - накапливающий параметр, в котором будут храниться связи между переменными и их значениями и названиями функций и их определениями. При определении evl ранее выбранные распознаватели и селекторы погружаем в более общее ветвление COND3) и каждому из них сопоставляем свой семантический обработчик, выполняющий действие, соответствующее смыслу распознанной конструкции4):



(DEFUN evl(e a) (COND ( (atom e) (cdr(assoc e a)) ) ( (eq (car e) 'QUOTE) (cadr e)) ( (eq(car e) 'IF) (evcon(cdr e) a)) ( T (apply (car e) (evlis(cdr e) a) a) )) )

(defun apply (fn x a) (COND ((atom fn)(cond ((eq fn 'CAR) (caar x)) ((eq fn 'CDR) (cdar x)) ((eq fn 'CONS) (cons (car x)(cadr x)) ) ((eq fn 'ATOM)(atom (car x)) ) ((eq fn 'EQ) (eq (car x)(cadr x)) ) (T (apply (evl fn a) x a)) ) ) ) ((eq(car fn)'LAMBDA) (eval (caddr fn) (pairlis (cadr fn) x a) )) ((eq (car fn) 'LABEL) (apply (caddr fn) x (cons (cons (cadr fn)(caddr fn)) a)))))

(DEFUN evcon (c a) (COND ((evl (car c) a) (evl (cadr c) a) ) ( T (evl (caddr c) a) ) ))

(DEFUN evlis (m a) (COND ((null m) Nil ) ( T (cons(evl (car m) a) (evlis(cdr m) a) )) )

Поясним ряд пунктов этих определений.

Первый аргумент evl - форма. Если она - атом, то этот атом может быть только именем переменной, а значение переменной должно уже находиться в ассоциативном списке.

Если CAR от формы - QUOTE, то она представляет собой константу, значение которой выбирается селектором CADR от нее самой.

Если CAR от формы - IF, то форма - условное выражение. Вводим вспомогательную функцию EVCON, которая обеспечивает вычисление предиката и выбор формы, соответствующей значению предиката. Эта форма передается EVL для дальнейших вычислений.

Все остальные случаи рассматриваются как список из функции с последующими аргументами.

Вспомогательная функция EVLIS обеспечивает вычисление аргументов, затем представление функции и список вычисленных значений аргументов передаются функции APPLY.

Первый аргумент apply - функция. Если она - атом, то существует две возможности. Атом может представлять одну из элементарных функций (car cdr cons atom eq). В таком случае соответствующая ветвь вычисляет значение этой функции на заданных аргументах. В противном случае, этот атом - имя ранее заданного определения, которое можно найти в ассоциативном списке, подобно вычислению переменной.

Если функция начинается с LAMBDA, то ее аргументы попарно соединяются со связанными переменными и размещаются в ассоциативном списке, а тело определения (форма из лямбда-выражения) передается как аргумент функции eval для дальнейшей обработки.



Если функция начинается с LABEL, то ее название и определение соединяются в пару, и полученная пара размещается в ассоциативном списке, чтобы имя функции стало определенным при дальнейших вычислениях. Они произойдут как рекурсивный вызов apply, которая вместо имени функции теперь работает с ее определением при более полном ассоциативном списке - в нем уже размещено определение имени функции. Поскольку определение размещается "наверху" стека, оно становится доступным для всех последующих переопределений, то есть работает как локальный объект.

Определение универсальной функции является важным шагом, показывающим одновременно и механизмы реализации, и технику программирования на любом языке.

  1. В строгой теории языка программирования все функции следует определять всякий раз, когда они используются. На практике это неудобно. Реальные системы имеют большой запас встроенных функций, известных языку, и возможность присоединения такого количества новых функций, какое понадобится.
  2. Для языков программирования характерно большое разнообразие условных форм, конструкций выбора, ветвлений и циклов, практически без ограничений на их комбинирование.
  3. В реальных системах программирования обычно поддерживается работа с целыми, дробными и вещественными числами в предельно широком диапазоне, а также работа с кодами и строками. Такие данные, как и атомы, являются минимальными объектами при обработке информации, но отличаются от атомов тем, что их смысл задан непосредственно их собственным представлением.


Приведенное выше определение интерпретации на примере мини-Лиспа является концептуальным минимумом, обеспечивающим постепенность восприятия более сложных методов реализации языков и систем программирования, которые будут иллюстрироваться в дальнейшем. Они будут введены как расширения или уточнения чистого определения универсальной функции. Такое определение часто называют самоопределением, т.к. вспомогательные функции в принципе можно описать на самом определяемом подмножестве Лиспа.



Составляющие этой формальной системы следующие:

  1. Множество символов, называемых списками.
  2. Система функциональных обозначений для основных понятий, необходимых при программировании обработки списков.
  3. Формальное представление функциональных обозначений в виде списков.
  4. Универсальная функция (записанная в виде списка), интерпретирующая обращение произвольной функции, записанной как списка, к ее аргументам.
  5. Система базовых функций, обеспечивающих техническую поддержку обработки списков, и специальных функций, обеспечивающих управление вычислениями.


Более интересные и не столь очевидные следствия возникают при варьировании и расширении этой формальной системы, что и будет продемонстрировано в следующих лекциях.

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

APPEND - функция двух аргументов x и y, сцепляющая два списка в один.

(DEFUN append (x y) (IF (null x) y (CONS (CAR x) (append (CDR x) y) )))

INSERT - вставка z перед вхождением ключа x в список al.

(DEFUN insert (al x z) (COND ((null al) Nil) ((equal (CAR al) x) (CONS z al)) ((QUOTE T) (CONS (CAR al) (insert (CDR al) x z))) ))

(insert '(a b c) 'b 's) = (a s b c)

ASSIGN - модель присваивания переменным, хранящим значения в ассоциативном списке. Замена связанного с данной переменной в первой паре значения на новое заданное значение. Если пары не было вообще, то новую пару из переменной и ее значения помещаем в конец списка, чтобы она могла работать как глобальная.

(DEFUN assign (x v al) (COND ((Null al) (CONS (CONS x v) Nil )) ((equal x (CAAR al))(CONS (CONS x v) (CDR al))) ((QUOTE T) (CONS (CAR al) (assign x v (CDR al)))) ))

(assign 'a 111 '((a . 1)(b . 2)(a . 3))) = ((a . 111)(b . 2)(a . 3)) (assign 'a 111 '((c . 1)(b . 2)(a . 3))) = ((c . 1)(b . 2)(a . 111)) (assign 'a 111 '((c . 1)(d . 3))) = ((c . 1)(d . 3) (a . 111))

Методы верификации программ активно используют структурную и рекурсивную индукцию (Мак-Карти) при доказательстве таких свойств рекурсивно определенных функций, как эквивалентность.


Поэтому операционная семантика языка программирования, заданная над списочными структурами и поддерживающая все уровни определения языка от текста до кода, включая моделирование средств различных парадигм программирования, образует технологичную основу для решения актуальных проблем разработки надежных информационных систем.

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

  1)

  Условные выражения такого вида были введены в математическую теорию вычислений Маккарти (1963)

  2)

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

  3)

  (if pr tr fl) эквивалентно (cond (pr tr) (T fl)) , где T - тождественная истина.

  4)

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

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