1 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Глава 3. Стили функционального программирования 3.1. Язык ЛИСП (John McCarthy, 1960) Две формы представления данных: атомы: A 123 B_12 + T NIL списки: (A) (PLUS 12 25) (LAMBDA (X Y) (PLUS X Y)) () С помощью атомов представляются «атомарные» объекты – числа, символы и логические значения; С помощью списков представляются составные объекты – структуры, выражения и функции; Вызов функции – применение функции к списку аргументов: (PLUS 12 15) (PLUS (MINUS 12 5) 15) (COND ((LT X Y) (MINUS 0 1)) ((EQ X Y) 0) (T 1)) (QUOTE (LAMBDA (X) (PLUS 1 X)))' (LAMBDA (X) (PLUS 1 X)) (LET (FACT 5) (FACT '(LAMBDA (N) (COND ((EQ N 0) 1) (T (MULT N (FACT (MINUS N 1)))))))) Атомы могут обладать значением. Например, атом PLUS имеет значением функцию сложения, а атом 123 имеет значением самого себя. Списки тоже имеют значение – значение списка «вычисляется» по специальным правилам.

2 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Основные примитивные функции в ЛИСПе Арифметические и логические функции: PLUS, MULT, LE, EQ, AND Специальные функции: COND, QUOTE, LET Функции обработки списков: CAR, CDR, CONS (CONS 'A '(B C)) (A B C) (CONS 'A (CONS 'B NIL)) (A B) (CAR '(A B C)) A (CDR '(A B C)) (B C) (CDR '(A)) NIL (CONS '(A B) '(C D)) ((A B) C D) (CAR (CDR '(A B C D))) B (CADDR '(A B C D))) C (CONS 'LAMBDA (CONS '(X) '((PLUS X 1)))) (LAMBDA (X) (PLUS X 1)) Функции высших порядков в ЛИСПе: (DEFINE MAP (LAMBDA (F L) (COND (L (CONS (F (CAR L)) (MAP F (CDR L)))) (T NIL) ))) (MAP '(LAMBDA (X) (PLUS X 1)) '(1 3 8)) (2 4 9)

3 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Функции как значения Функциональное значение – это либо встроенная функция, либо список, первым атомом которого является специальный атом LAMBDA. Например, (LAMBDA (X) (MULT 2 X)) Если функция применяется к аргументу, то формальные параметры «связываются» со значением аргумента, поэтому, например, выражение ((LAMBDA (X) (MULT 2 X)) 3) при вычислении выдает значение 6. Как происходит вычисление, если в теле функции используются «глобальные» атомы? (LAMBDA (X) (MULT Y X)) Два возможных подхода: статический: значения «глобальных» атомов фиксируются в момент определения функции (в момент «исполнения» функции LAMBDA ). динамический: значения «глобальных» атомов определяются во время работы функции. Разница может проявиться, если функция определена в одном контексте, а исполняется в другом. В некоторых (старых) версиях ЛИСПа для «фиксации» контекста применялись специальные функции, например, если лямбда-выражение передавалось в качестве аргумента в другую функцию, то можно было использовать специальную функция FUNCTION вместо QUOTE.

4 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Подведение итогов: основные черты и особенности языка ЛИСП Простой синтаксис – скобочная запись данных и программ. Энергичная схема вычислений (кроме специальных функций). Нет образцов и конструкторов – определение функций построено на суперпозиции примитивных и ранее определенных функций; построение сложных объектов также использует функцию CONS. Возможность определения функций высших порядков, в которых аргументами и/или результатом работы являются функции. Возможность динамического построения фрагментов программы непосредственно в ходе ее выполнения. Определение «контекста переменных» с помощью блочной структуры (LET). Язык ЛИСП послужил прообразом и идейной основой большой группы языков. В той или иной степени он лежит в основе всех современных функциональных языков программирования и многих других языков.

5 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования Система комбинаторного программирования FP (John Backus, 1978) Теоретически любую функцию можно получить из базовых с помощью комбинаторных преобразований. FP – система, реализующая этот принцип. Набор констант не определен, но предполагается, что есть списки и логические значения. Набор базовых функций не определен, но предполагается, что он достаточно богат. Также предполагается, что принята энергичная схема вычислений (все функции – строгие). Определим следующие комбинаторы: Композиция f g ( f g) x = f (g x) Условие f g; h ( f g; h) x = Константа k k x = Конструкция [ f 1, f 2,..., f n ] [ f 1, f 2,..., f n ] x = { g x, если f x - истинно h x, если f x - ложно не опр., если f x – не определено { k, если x – определено не опр., если x – не определено

6 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Еще несколько важных комбинаторов Отображение α f (α f) : = Правая вставка / f (/ f) : = x (/ f) : = f : > Левая вставка \ f (\ f) : = x (\ f) : = f :, x n > (map) (foldr1) (foldl1) Вариант правой вставки с базовой константой / k f (/ k f) : = k (/ k f) : = f : > Вариант левой вставки с базовой константой \ k f (\ k f) : = k (\ k f) : = f :, x n > (foldr) (foldl)

7 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Определим типичный язык программирования на основе FP-системы Введем набор констант и базовых функций Константы: Функции: Арифметические функции: +, -, *, add1, mul5, sub3: + : = 7 add1 : 3 = 4 Логические функции: =, /=,,..., and, or, not,... eq0, neq5, lt2: = : = F = T lt2 : 5 = T or : = T Функции-селекторы: 1, 2,..., 1r, 2r,...: 2 : = 5 1r : = 8 Тождественная функция: id: id : = в программах в явном виде не присутствуют! гетерогенные списки ( ,, T>,…) целые числа ( 0, 1, 2,..., -1, -2,...); логические значения ( T и F ); символы ( 's', '*',…);

8 hd : = 3 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Функции обработки списков tl : = hr : = 8 tr : = cons : > = consr :, 3> = null : = T null : = F distl : > =,, > distr :, 3> =,, > ι : 5 = ι : 0 = Программа в FP – это определение функций: def sqr = * [id, id] sqr : 5 = * : = 25 def pow4 = * [sqr, sqr] pow4 : 3 = * : = 81

9 Кубенский А.А. Функциональное программирование. Глава 3. Стили функционального программирования. Примеры программ в языке программирования на базе FP Haskell: fact n = if n = 0 then 1 else n * fact (n-1) FP: def fact = eq0 1; (* [id, fact (- [id, 1])]) def fact = (/ 1 *) ι Haskell: test elem [] = False test elem (x:lst) | x == elem = True | otherwise = test elem lst FP: def test = null 2 F; eq [1, hd 2] T; test [1, tl 2] def test = (/ F or) (α eq) distl Haskell: fact n = foldr (*) 1 [1..n] Haskell: test elem = (foldr (||) False). (map (== elem)) test : > (/ F or) : ((α eq) : (distl : >)) (/ F or) : ((α eq) :,,, >) (/ F or) : T

10 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Будем задавать функции с помощью «лямбда-выражений», которые будем преобразовывать по определенным правилам (правила «вычислений»). Основные типы лямбда-выражений: переменная константа применение функции определение функции x +3nilc ((+ 2) 3) (e1 e2) (λx.((+ 2) x)) (λx.e) + 2 x λx. Свободная переменная Связывающее вхождение (λx.+ x y) x Связанная переменная Этот x связан Этот x свободен 4.1. Основные понятия Замкнутое выражение – выражение, не содержащее свободных переменных. (λx.(x x))

11 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Правила преобразований выражений. 1. δ-редукция f e1 e2... ek result or T F T 2. β-редукция (λx.e1) e2 e1{x|e2}(λx.+ 1 x) (λx.x x)(λx.x x) 3. α -преобразование λx.e1 λz.e1{x св. |z}λx.((λy.λx.+ x y) x) λz.((λy.λx.+ x y) z) 4. η-преобразование λx.E x Eλx.((λy.λx.+ x y) x) (λy.λx.+ x y)

12 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Примеры преобразования выражений (λx.λy.+ x y) 2 5 (λy.+ 2 y) 5 ( β-редукция) ( β-редукция) 7 ( δ-редукция) (λx.λy.y)((λx.x x)(λx.x x)) Функция Аргумент (λy.y) ( β-редукция) (λx.λy.y)((λx.x x)(λx.x x))... От порядка применения редукций может зависеть результат!

13 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Ромбическое свойство системы редукций α 0 α 1 … α k α 0 * α k Нормальная форма: лямбда-выражение, к которому не применимы β- и δ-редукции α0α0 β1β1 β2β2 ω * * Теорема (Черча – Россела): система преобразований, основанная на применении β-редукций обладает ромбическим свойством. Следствие: лямбда-выражение не может иметь более одной нормальной формы. Замечание: в некоторых случаях применение редукций может, в зависимости от порядка, либо приводить к нормальной форме, либо не приводить к ней. существует (?) форма ω Отношение * это рефлексивное транзитивное замыкание отношения

14 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Стандартные порядки редукций. Редекс (redex) – выражение, к которому применима одна из редукций. Reducible Expression – редуцируемое выражение.β-редекс; δ-редекс… Выражение может содержать (или не содержать) один или несколько редексов. Выражение (λx.λy.y)((λx.x x)(λx.x x)) содержит два редекса. Внутренний редекс Внешний редекс Самый левый (самый правый) редекс – текстуально расположен левее (правее) других. Самый внутренний редекс – не содержит внутри себя других редексов. Самый внешний редекс – не содержится внутри никакого другого редекса. Аппликативный порядок редукций – редукция всегда применяется к самому левому из самых внутренних редексов Нормальный порядок редукций – редукция всегда применяется к самому левому из самых внешних редексов

15 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Еще пример редукции выражения (λx.* x x)((λy.+ 1 y) 2) Аппликативный порядок редукций (λx.* x x)(+ 1 2) (λx.* x x) 3 * – нормальная форма Нормальный порядок редукций * ((λy.+ 1 y) 2) ((λy.+ 1 y) 2) * (+ 1 2) ((λy.+ 1 y) 2) * 3 ((λy.+ 1 y) 2) * 3 (+ 1 2) * – нормальная форма β-редукция δ-редукция β-редукция δ-редукция β-редукция δ-редукция β-редукция δ-редукция

16 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Сравнение различных порядков редукций. Аппликативный порядок (АПР)Нормальный порядок (НПР) Не приводит к копированию одних и тех же выражений, если они не находятся в нормальной форме. Одни и те же выражения аргументов могут многократно копироваться при подстановке в тело лямбда-выражения. Выполняет редукцию даже тех выражений, которые в дальнейшем могут быть отброшены. Никогда не редуцирует выражение, если это может оказаться впоследствии ненужным. Может не приводить к нормальной форме, даже если она существует. Всегда приводит выражение к нормальной форме, если только она вообще существует. Преобразование выражения к нормальной форме в АПР соответствует энергичному порядку вычислений выражений в языках программирования. Преобразование выражения к нормальной форме в НПР соответствует вычислениям выражений с подстановкой аргументов «по наименованию».

17 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Проблема конфликта имен. λx.((λy.λx.+ x y) x) Свободное вхождение переменной Связанное вхождение переменной λx.(λx.+ x x)λz.((λy.λx.+ x y) z) α-преобразование λz.(λx.+ x z) η-преобразование λy.(λx.+ x y)

18 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Слабая заголовочная нормальная форма (СЗНФ) Выражение, не имеющее свободных переменных (замкнутое) находится в СЗНФ, если оно имеет один из следующих видов: Константа c Определение функции λx.E Частичное применение функции P E 1 E 2... E k Выражение λx.((λy.λx.+ x y) x) находится в СЗНФ. Вычисления, происходящие при исполнении программы в «ленивых» вычислениях, соответствуют редукции выражения в НПР до приведения к СЗНФ, дополненной эффектом «разделения» значений переменных при подстановке аргумента, еще не находящегося в СЗНФ. (λx.+ x x)(* 2 3) + (* 2 3) (* 2 3) + 6 (* 2 3) x x (* 2 3) + x x 6 12

19 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Итоги: механизмы редукций в лямбда-исчислении 1.От способа применения редукций может зависеть окончательный вид выражения, но не его функциональный смысл. 2.Если выражение может быть приведено к нормальной форме, то это может быть сделано с помощью редукций в НПР, возможно, с переименованиями переменных. 3.Аппликативный порядок редукций, приводящий выражение к СЗНФ соответствует энергичной схеме вычислений, принятой в некоторых функциональных языках. 4.«Ленивая» схема вычислений может быть смоделирована приведением выражений к СЗНФ при применении НПР + разделение переменных.