Программирование
<<  Функциональное программирование Функциональное программирование  >>
Функциональное программирование
Функциональное программирование
Лекция 22
Лекция 22
Семиотика
Семиотика
Семантика языков программирования
Семантика языков программирования
Классификация формальных семантик
Классификация формальных семантик
Денотационная семантика
Денотационная семантика
Теория доменов
Теория доменов
Стандартные домены и лифтинг
Стандартные домены и лифтинг
Функциональные пространства
Функциональные пространства
Теорема о неподвижной точке
Теорема о неподвижной точке
PCF: Programming language for Computable Functions
PCF: Programming language for Computable Functions
Семантическая функция
Семантическая функция
Вспомогательные обозначения
Вспомогательные обозначения
Описание семантики
Описание семантики
Пример
Пример
Описание рекурсии
Описание рекурсии

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

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

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

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

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

2 Лекция 22

Лекция 22

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

2

3 Семиотика

Семиотика

Наука, изучающая свойства языков (знаковых систем)

3

4 Семантика языков программирования

Семантика языков программирования

Каков будет результат запуска программы? Потребность в формальной семантике: Стандартизация описания языка Доказательство корректности программ Построение более стройных языков Прототипирование языков / построение более эффективных трансляторов

4

5 Классификация формальных семантик

Классификация формальных семантик

5

6 Денотационная семантика

Денотационная семантика

Описываем «означивание» конструкций языка ||.|| - отображение синтаксических конструкций в денотаты ||2+1|| = 3 || letrec fact = fun x -> if x=1 then 1 else x*fact(x-1) || = ?! Проблема: Как обозначать частично-определенные функции? Как быть с рекурсивными определениями? Как быть с рекурсивными описаниями типов? type ‘a tree = Nil | Node of ‘a * ‘a tree * ‘a tree;; Если объекты ?-исчисление денотируются множеством D, то туда входят функции высших порядков => D изоморфно D?D, что невозможно!

6

7 Теория доменов

Теория доменов

Функции определяются на множествах – доменах (полные частично-упорядоченные множества, CPO) <D,?>, ? - отношение частичного порядка ?xo ?x1 ?… ?x=?ixi : ?i xi?x и ?x’ : xi?x’ => x?x’ «Стандартные домены»: int, bool Конструкторы доменов: [D1?D2] – все непрерывные функции D1+D2 – дизьюнктная сумма D1?D2 – декартово произведение D* - множество конечных последовательностей Пример: D = {nil}+(int?D?D)

7

8 Стандартные домены и лифтинг

Стандартные домены и лифтинг

Множество конечных элементов (bool) – СPO с отношением x?x Множество целых чисел <Z,?> : x?x Для моделирования «неопределенности» добавляем знаечение ? Z?=<Z?{?}, ?> : (?x) x?x и (?x) ??x B?=<{?,t,f},{??t, ??f, t?t, f?f}>

8

9 Функциональные пространства

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

f: D?E – монотонная, если ?x,y?D x?y => f(x)?f(y) f: D?E – непрерывная, если ? xo?x1?x2? … f(?ixi)= ?if(xi) Домен [D?E] – мн-во всех непрерывных функций f: D?E с порядком f?g ? ?x,y?D f(x)?g(x)

9

10 Теорема о неподвижной точке

Теорема о неподвижной точке

Пусть D – домен с наименьшим элементом ?, f ?[D?D]. Тогда ?x=fix f : x = f(x), и x=?ifi(?) Пусть xi=fi(?), x0=? В силу монотонности xi ? xi+1=f(xi) ?x=?i xi f(x)=f(?i xi)=?i f(xi)=?i xi+1=x

10

11 PCF: Programming language for Computable Functions

PCF: Programming language for Computable Functions

Типы ? ::= int | bool | ??? Выражения e ::= n | t | x | if e0 then e1 else e2 | e0e1 | fun x:??e | fix x: ?=e | let x = e1 in e2 letrec f x = e in E – синоним для let f = fix (f’: ??? = fun x:??e) in E

11

12 Семантическая функция

Семантическая функция

||Int|| = Z? , ||bool|| = B? ||???|| = [||?||?||?||] ||.||. : exp?env?d, где D – универсальное множество типов Z?+ B? exp – множество выражений языка env : ide ?D – контекст (среда) ||x+1||{x ?3}=4 ||let x=3 in x+1||?=||x+1||{x ?3}=4

12

13 Вспомогательные обозначения

Вспомогательные обозначения

cond : B? ? D ? D ? D [e/x]? = ?y.cond (x=y) e (?y)

13

14 Описание семантики

Описание семантики

||X||?= ?x ||n||?=n; ||t||?=t; n? Z?; t? B? ||e1e2||?=(||e1||?) (||e2||?) ||fun x: ??e||? = ?d.||E||([d/x]?) где f=?d.E означает ?x?d f(x) = e ||if e0then e1else e2||? = cond ||e0||? ||e1||? ||e2||? || let x= e1 in e2||? = ||e2||([d/x]?), где d=||e1||? || fix x: ?=e||? = y(?d.||E||([d/x]?))

14

15 Пример

Пример

||let id = fun x->x in id 3||?= ||id 3||{id->||fun x->x|| ?} = ||id 3||{id->?d.||x||{x->d}} = || id 3||{id->?x.x}= (||id||{id-> ?x.x})(||3||{id-> ?x.x})= (?x.x)3 = 3

15

16 Описание рекурсии

Описание рекурсии

let fact = Y(?f.?x.if x=1 then 1 else x*f(x-1)) Что представляет собой функции f? f0=? f1=?x.if x=1 then 1 else x*f0(x-1) [ n!, n?1; иначе ?] f2=?x.if x=1 then 1 else x*f1(x-1) [ n!, n?2; иначе ?] … f0?f1?f2?f3?… fact = ?ifi

16

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

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

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

Информатика

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