Сошников Дмитрий Валерьевич к.ф.-м.н., доцент Факультет инноваций и высоких технологий Московский физико-технический институт

2 Лекция 5 Основные принципы функционального программирования

©2008 Сошников Д.В. 3 Без побочных эффектов С прозрачной математической основой (с прозрачной семантикой) Имеет смысл рассматривать семантические отображения функций ФП на математические функции, что невозможно в императивном подходе Без присваивания Функции-как-данные, все есть функция

©2008 Сошников Д.В. 4 Функциональное программирование описывает решения задачи как применение функции к данным Число -> double -> 2*число Доска1 -> nextMove -> доска2 I like math -> translate -> Я люблю математику -> invert ->

©2008 Сошников Д.В. 5 Функция в мат.анализе: f : A B описывается как f A B Функция в ФП / λ-исчислении описывается как процесс преобразования данных Что такое функция?

©2008 Сошников Д.В. 6 f(x) = x 2 +1 Что обозначает запись f(x)? Саму функцию (множество пар) Значение функции в некоторой точке x Что обозначает запись f(x)= x 2 +1? Определение функции Уравнение

©2008 Сошников Д.В. 7 Для построения исчисления функций нам необходимо: Иметь возможность описывать анонимные «функции», задавать функциональные константы x x 2 +1 ŷ 2 +1 λx.x 2 +1 Иметь возможность описывать применение функции к аргументу f(3) f 3

©2008 Сошников Д.В. 8 Математическая теория, изучающая описание и применение (вызов) функций Две основные операции: Аппликация (применение функции): (AB) Абстракция (получение функции): λx.Expr Чистое λ-исчисление ограничивается этими операциями Прикладное λ-исчисление может включать в себя некоторые константы и операторы (например, числа, сложение и т.д.)

©2008 Сошников Д.В. 9 Процесс вывода в λ-исчислении – это упрощение выражения (редукция) [ или ] (λx.(x 2 +1)) (λf.(f 0)) sin sin 0 0 Основные виды редукции: δ-преобразование – вычисление «внешней» операции β-преобразование – аппликация к абстракции (λx.exp)t = [x/t]exp [x/t]exp означает замену переменной x на выражение t в exp

©2008 Сошников Д.В. 10 (λx.(x 2 +1)) 3 [x/3] (x 2 +1) (λf.λx.(f (f x)) (λz.z 2 ) 3 [f/(λz.z 2 )] λx.(f (f x)) 3 λx.(λz.z 2 )((λz.z 2 ) x) 3 [x/3] (λz.z 2 )((λz.z 2 ) x) (λz.z 2 )((λz.z 2 ) 3) (λz.z 2 )([z/3]z 2 ) (λz.z 2 ) 3 2 [z/3 2 ] z 2 (3 2 ) 2

©2008 Сошников Д.В. 11 Система функционального программирования пытается вычислить (редуцировать) встречающиеся ей выражения 3+1;; val it : int = 4 (fun x -> x+1) 3;; val it : int = 4

©2008 Сошников Д.В. 12 λ-нотация позволяет создавать функцию от одного аргумента plus = λx.λy.(x+y) plus 1 2 λx.λy.(x+y) plus 1 λx.λy.(x+y) 1 λy.(1+y) Каррирование – определение функции нескольких аргументов как функции высшего порядка Каждое применение аргумента понижает порядок функции

©2008 Сошников Д.В. 13 Для понимания того, какого порядка функция и к каким аргументам ее можно применять, удобно рассмотреть (неформально) понятие типа λx.(x*2) : int int + : int int int (означает (int (int int)) (λf.(f 0)) : (int T) T Классическое λ-исчисление – бестиповая теория

©2008 Сошников Д.В. 14 Базовые типы: int, float, string, bool, … Функциональный тип: T 1 T 2 Кортежи (tuples): T 1 *T 2 Прямая сумма (union): T 1 +T 2 …

©2008 Сошников Д.В. 15 type person = string * int;; let vasya = ("Vasya",14);; type document = SSN of int | Passport of string;; type personx = string * int * document;; let vasyax = ("Vasya",14,SSN 1234);; type T option = Some of T | None Option type

©2008 Сошников Д.В. 16 Некаррированная функция от пары аргументов: plus_u (x,y) = x+y plus_u = λ (x,y). x+y plus_u: int*int int Каррированная функция второго порядка: plus_c x y = x+y plus_c = λx.λy.x+y = λxy.x+y plus_c : int int int

©2008 Сошников Д.В. 17 curry = λf.λx.λy.f(x,y) uncurry = λf.λ(x,y).(f x y) let curry f = (fun x y -> f(x,y));; let uncurry f = (fun (x,y) -> (f x y));; curry: (A*B C) A B C uncurry: (A B C) A*B C

©2008 Сошников Д.В. 18 Аналогично оператору ?: в С/С++ Обязательны обе ветки: then и else Типы выражений в then и else должны совпадать (fun x -> if x%2=0 then "Чет" else "нечет") 4;; (fun x -> if x>0 then Положительное elif x if x%2=0 then "чет" else "нечет";; f 4;; f 3;;

©2008 Сошников Д.В. 19 Системы функционального программирования позволяют давать имена выражениям и использовать их в дальнейшем: let z = expr1 in expr2 Oзначает [z/expr1]expr2 Или (λz.expr2)expr1 let a,b = 1,2 – связывание имен для пар Отличается от let a=1 in let b=2 in … let a,b=b,a

©2008 Сошников Д.В. 20 let x = 1;; let y = x+1;; let x = 2;; (y,x);; let x = 1 in let y = x+1 in let x = 2 in (y,x);;

©2008 Сошников Д.В. 21 Определенное имя действует только в рамках подвыражения in Изменить значение переменной нельзя, но можно написать let x = … для уже определенного x, при этом Определяется «новый» x, и связывается со значением выражения в правой части Все ранее сделанные ссылки будут ссылаться на старое значение x При выходе из области видимости восстанавливается старое значение Можно даже написать let x=x+1 Переменные, определенные в top level, сохраняют свои значения на время сеанса (т.е. являются локальными для сеанса)