ФУНКЦИИ БОЛЕЕ ВЫСОКОГО ПОРЯДКА Функциональное программирование Григорьева И.В. - презентация

1 ФУНКЦИИ БОЛЕЕ ВЫСОКОГО ПОРЯДКА Функциональное программирование Григорьева И.В.

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

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

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

5 Одно и то же выражение может в связи с различными аспектами выступать, с одной стороны, как обыкновенный аргумент, а с другой стороны, как функциональный. Роль и интерпретация выражения зависят от его синтаксической позиции. Приведем пример: _(car '(lambda (x) (list x))) LAMBDA _((lambda (x) (list x)) 'car) (CAR)

6 Переданное функции CAR лямбда- выражение не является функциональным аргументом, и CAR не становится функционалом. То же самое лямбда- выражение, стоящее в позиции функции, уже интерпретируется как функция в то время, как CAR интерпретируется как данные. Функциональный аргумент и функционал являются некоторым обобщением простого понятия функции: функциональным аргументом может быть любой подходящий объект, который используется в теле функционала в позиции функции и в роли функции.

7 Далее мы будем использовать понятия функции, вызова функции и значения функции в следующем смысле: 1. Функция сама есть изображение вычислений или определение. 2. Вызов функции есть применение этого изображения. 3. Значение функции есть результат такого применения.

8 Функция является функционалом, если в качестве ее аргумента используется лисповский объект типа (1), который интерпретируется как функция (2) в теле функционала. Таким функциональным объектом может быть 1. символьное имя, представляющее определение функции (системная функция или функция, определенная пользователем), 2. безымянное лямбда-выражение, 3. так называемое замыкание (рассматриваемое позже).

9 Фактический параметр для функционального аргумента функционала задается в виде формы, значением которой будет объект, который можно интерпретировать как функцию. Приведем примеры:... '(lambda (x) (list x)) (list 'lambda '(x) (list list 'x)) (first '(car cdr cons)).

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

11 Вызов функции с функциональным значением или другая форма с функциональным значением может в вызове функции находиться в двух различных позициях: 1. функционального аргумента в вызове функционала; 2. на месте имени функции в вызове функции (или функционала, или функции с функциональным значением).

12 В Коммон Лиспе предполагается, что в вызове функции на месте имени функции находится символ, определенный с помощью формы DEFUN как имя функции. Переданный в качестве параметра функциональный объект можно использовать лишь через явный вызов применяющих функционалов (FUNCALL, APPLY), которые мы рассмотрим. В некоторых других системах такого ограничения нет и в вызове функции на месте имени функции может быть любая форма, имеющая функциональное значение. Когда именем в вызове является атом без функциональной связи, то в качестве функционального объекта берется значение этого имени (SYMBOL-VALUE).

13 Способы композиции функций Все типы функций могут быть использованы в определениях в следующих позициях: 1.Обыкновенный вызов: (defun f...(… g…)…) 2.Рекурсивный вызов: (defun f...(… g…)…) 3. Вложенный рекурсивный вызов: (defun f...(f…(f…)…)…) 4. Функциональный аргумент: (defun f (... g...) …(apply g …)…)

14 Аргументами функций были данные, выражения, значением которых являются данные или, как в случае функций более высокого порядка, другие функции. Объединяя использование рекурсии и функционалов, остановимся на еще одном способе использования, когда функция принимает саму себя в качестве функционального аргумента: 5. Рекурсивный функциональный аргумент: (defunf(...f...)... (apply f... f...)...)

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

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

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

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

19 Применяющие функционалы родственны универсальной функции Лиспа EVAL. В то время как EVAL вычисляет значение произвольного выражения (формы), применяющий функционал вычисляет значение вызова некоторой функции. Интерпретатор Лиспа ЕVAL и на самом деле вызывает применяющий функционал APPLY при вычислении вызова, a APPLY в свою очередь вызывает EVAL при вычислении значения других форм.

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

21 APPLY применяет функцию к списку аргументов APPLY является функцией двух аргументов, из которых первый аргумент представляет собой функцию, которая применяется к элементам списка, составляющим второй аргумент функции APPLY: (APPLY fn список) (fn 'xl 'x2... 'xN), где список=(х1 x2... xN)

22 _(apply '+ '(2 3)) 5 _(apply 'cons '(что) (пожелаете)) (ЧТО ПОЖЕЛАЕТЕ) _(setq f +) + _(apply f '(2 3)) 5 _( apply 'apply '(+ 2 3))) 5 _(apply (lambda (x y) (+ x у)) '(2 3)) 5

23 FUNCALL вызывает функцию с аргументами Функционал FUNCALL по своему действию аналогичен APPLY, но аргументы для вызываемой функции он принимает не списком, а по отдельности: (FUNCALL fnxt x2... xN) (fn x1 x2... xN) Приведем пример: _(funcall '+2 3) 5

24 _(setq сложение '+) + _(funcall сложение 2 3) 5 _(funcall (car '(+ - * /)) 2 3) 5

25 Таким образом появляется возможность использовать синонимы имени функции. С другой стороны, имя функции можно использовать как обыкновенную переменную, например для хранения другой функции (имени или лямбда-выражения), и эти два смысла (значение и определение) не будут мешать друг другу: _(setq cons '+) _(funcall cons 2 3) 5 _(cons 2 3) (2. 3) (2. 3)

26 Поскольку первый аргумент функционала FUNCALL вычисляется по обыкновенным правилам, то на его месте должно стоять выражение, значением которого будет функциональный объект. Функциональным аргументом может быть только "настоящая" функция. Такие специальные формы, как QUOTE и SETQ, либо рассматриваемые позже макросы для этого не подходят, даже если бы их значением был функциональный объект.

27 Упражнения 1.Вычислите значения следующих вызовов: (apply list '(а b)) (funcall list '(а b)) (funcall 'apply list '(а b)) (funcall list 'apply '(a b)) (funcall 'funcall 'funcall list list '(a b)) 2.Определите FUNCALL через функционал APPLY.