Программирование
<<  Функциональное программирование Функциональное программирование  >>
Функциональное программирование
Функциональное программирование
Лекция 5
Лекция 5
Функциональное программирование
Функциональное программирование
В начале была функция…
В начале была функция…
Разные функции
Разные функции
Неоднозначность нотации
Неоднозначность нотации
Анонимные функции
Анонимные функции
?-исчисление (неформально)
?-исчисление (неформально)
Редукция
Редукция
?-редукция
?-редукция
На практике
На практике
Каррирование
Каррирование
Функциональные типы
Функциональные типы
Система типов
Система типов
Описание типов F#
Описание типов F#
Функции нескольких аргументов
Функции нескольких аргументов
Каррирование
Каррирование
Условное выражение
Условное выражение
Связывание имен
Связывание имен
Области видимости
Области видимости
Область видимости
Область видимости

Презентация на тему: «Функциональное программирование». Автор: Митя;Лена. Файл: «Функциональное программирование.ppt». Размер zip-архива: 2946 КБ.

Функциональное программирование

содержание презентации «Функциональное программирование.ppt»
СлайдТекст
1 Функциональное программирование

Функциональное программирование

Факультет инноваций и высоких технологий Московский физико-технический институт

2 Лекция 5

Лекция 5

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

2

3 Функциональное программирование

Функциональное программирование

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

3

4 В начале была функция…

В начале была функция…

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

4

5 Разные функции

Разные функции

Что такое функция?

Функция в мат.анализе: f : A?B описывается как f ? A?B Функция в ФП / ?-исчислении описывается как процесс преобразования данных

5

6 Неоднозначность нотации

Неоднозначность нотации

f(x) = x2+1

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

6

7 Анонимные функции

Анонимные функции

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

7

8 ?-исчисление (неформально)

?-исчисление (неформально)

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

8

9 Редукция

Редукция

Процесс вывода в ?-исчислении – это упрощение выражения (редукция) 1+2 ? 3 [ или + 1 2 ] (?x.(x2+1)) 3 ? 32+1 ? 10 (?f.(f 0)) sin ? sin 0 ? 0 Основные виды редукции: ?-преобразование – вычисление «внешней» операции ?-преобразование – аппликация к абстракции (?x.exp)t = [x/t]exp [x/t]exp означает замену переменной x на выражение t в exp

9

10 ?-редукция

?-редукция

(?x.(x2+1)) 3 [x/3] (x2+1) 32+1 10

(?f.?x.(f (f x)) (?z.z2) 3 [f/(?z.z2)] ?x.(f (f x)) 3 ?x.(?z.z2)((?z.z2) x) 3 [x/3] (?z.z2)((?z.z2) x) (?z.z2)((?z.z2) 3) (?z.z2)([z/3]z2) (?z.z2) 32 [z/32] z2 (32)2

10

11 На практике

На практике

Система функционального программирования пытается вычислить (редуцировать) встречающиеся ей выражения

3+1;; val it : int = 4 (fun x -> x+1) 3;; val it : int = 4

11

12 Каррирование

Каррирование

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

12

13 Функциональные типы

Функциональные типы

Для понимания того, какого порядка функция и к каким аргументам ее можно применять, удобно рассмотреть (неформально) понятие типа ?x.(x*2) : int ?int + : int ? int ? int (означает (int ? (int ? int)) (?f.(f 0)) : (int ?T) ? T

13

14 Система типов

Система типов

Базовые типы: int, float, string, bool, … Функциональный тип: T1 ? T2 Кортежи (tuples): T1*T2 Прямая сумма (union): T1+T2 …

14

15 Описание типов F#

Описание типов F#

Option type

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

15

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

16

17 Каррирование

Каррирование

curry = ?f.?x.?y.f(x,y) uncurry = ?f.?(x,y).(f x y)

curry: (A*B?C)?A?B?C uncurry: (A?B?C)?A*B?C

let curry f = (fun x y -> f(x,y));; let uncurry f = (fun (x,y) -> (f x y));;

17

18 Условное выражение

Условное выражение

Аналогично оператору ?: в С/С++ Обязательны обе ветки: then и else Типы выражений в then и else должны совпадать

(fun x -> if x%2=0 then "Чет" else "нечет") 4;; (fun x -> if x>0 then “Положительное” elif x<0 then “Отрицательное” else “Ноль”) 0;;

Let f = fun x -> if x%2=0 then "чет" else "нечет";; f 4;; f 3;;

18

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

19

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);;

20

21 Область видимости

Область видимости

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

21

«Функциональное программирование»
http://900igr.net/prezentacija/informatika/funktsionalnoe-programmirovanie-174850.html
cсылка на страницу

Программирование

31 презентация о программировании
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Программирование > Функциональное программирование