'

Глава 3. Стили функционального программирования

Понравилась презентация – покажи это...





Слайд 0

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 имеет значением самого себя. Списки тоже имеют значение – значение списка «вычисляется» по специальным правилам.


Слайд 1

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)


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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 : <5, <1,7,5,2>> (/F or) : ((? eq) : (distl : <5, <1,7,5,2>>)) (/F or) : ((? eq) : <<5,1>,<5,7>,<5,5>,<5,2>>) (/F or) : <F,F,T,F> T


Слайд 9

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


Слайд 10

11 Кубенский А.А. Функциональное программирование. Глава 4. Основы лямбда-исчисления. Правила преобразований выражений. 1. ?-редукция f e1 e2... ek ? result + 3 5 ? 8 or T F ? T 2. ?-редукция (?x.e1) e2 ? e1{x|e2} (?x.+ 1 x) 5 ? + 1 5 (?x.x x)(?x.x 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)


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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)


Слайд 17

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


Слайд 18

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


×

HTML:





Ссылка: