Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2)

Нажмите для полного просмотра!

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №2

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №3

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №4

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №5

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №6

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №7

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №8

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №9

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №10

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №11

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №12

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №13

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №14

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №15

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №16

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №17

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №18

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №19

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №20

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №21

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №22

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №23

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №24

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №25

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №26

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №27

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №28

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №29

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №30

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №31

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №32

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №33

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №34

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №35

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №36

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №37

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №38

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №39

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №40

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №41

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №42

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №43

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №44

Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2), слайд №45

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Функциональное программирование. Бестиповые арифметические выражения. (Лекция 2.2). Доклад-сообщение содержит 45 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 2. Тема 2. Бестиповые арифметические выражения Функциональное программирование

Слайд 2

Описание слайда:

План лекции Термы. Синтаксис. Индукция на термах. Семантические стили.

Слайд 3

Описание слайда:

Необходимость изучения теоретических основ ФП Базовые характеристики языков программирования (во многом определяются системой типов в ФП) Четкие, ясные, точные механизмы описания синтаксиса и семантики программ Пример: язык Haskell Поскольку Haskell представляет собой чисто функциональный язык, все вычисления осуществляются с помощью исчисления выражений (синтаксических термов), производящих значения (абстрактные сущности, которые мы рассматриваем как ответы). Каждое значение имеет связанный с ним тип (на интуитивном уровне мы можем рассматривать типы как множества значений). Налицо построенная строгая система типов закономерности и свойства которой необходимо учитывать, уметь формально обращаться с ней

Слайд 4

Описание слайда:

Грамматика псевдо-языка t ::= {- термы: -} true {- константа «истина» -} false {- константа «ложь» -} if t then t else t {- условное выражение -} 0 {- константа «ноль» -} succ t {- следующее число -} pred t {- предыдущее число -} iszero t {- проверка на ноль -}

Слайд 5

Описание слайда:

Определения и пояснения Результаты вычислений 0 либо булевы константы, либо числа - это все термы Такие термы будем называть значениями

Слайд 6

Описание слайда:

Другие определения синтаксиса Определение 1 [термы через индукцию] Множество термов – это наименьшее множество  такое , что 1. {true; false; 0}  T ; 2. если t1  T , то {succ t1; pred t1; iszero t1} T ; 3. если t1  T , t2  T , t3  T , то if t1 then t2 else t3  T .

Слайд 7

Описание слайда:

Другие определения синтаксиса Определение 2 [термы через правила вывода]: множество термов определяется следующим образом

Слайд 8

Описание слайда:

Другие определения синтаксиса Определение 3 [термы через правила вывода]: множество термов определяется объединением множеств S= для каждого iN, где S0= Si+1= {true, false,0} {succ t1, pred t1, iszero t1  t1 Si} { if t1 then t2 else t3  t1, t2, t3 Si} T=S !!

Слайд 9

Описание слайда:

Домашнее задание: Сколько элементов содержит S3? Покажите  i, SiSi+1 Покажите, что S - наименьшее множество

Слайд 10

Описание слайда:

T=S !! Для S должны выполняться условия 1. {true; false; 0}  S ; 2. если t1  S , то {succ t1; pred t1; iszero t1} S ; 3. если t1  S , t2  S , t3  S , то if t1 then t2 else t3  S .

Слайд 11

Описание слайда:

T=S !! Пусть S’ удовлетворяет условиям наименьшего множества При помощи полной индукции по i докажем что SiS’ Для случая i=0 Для случая i=j+1>0, пусть SjS’

Слайд 12

Описание слайда:

Индукция на термах Из определения 1 если t  T 1. t является константой; 2. t результатом succ t1; pred t1; iszero t1 t1

Слайд 13

Описание слайда:

Определения

Слайд 14

Описание слайда:

Определения

Слайд 15

Описание слайда:

Определения

Слайд 16

Описание слайда:

Пример соотношения между числом констант в темме и его размером

Слайд 17

Описание слайда:

Принцпы индукции по термам Индукция по глубине

Слайд 18

Описание слайда:

Принцпы индукции по термам Индукция по размеру

Слайд 19

Описание слайда:

Принцпы индукции по термам Структурная индукция

Слайд 20

Описание слайда:

О синтаксисе псевдо-языка (повтор) t ::= {- термы: -} true {- константа «истина» -} false {- константа «ложь» -} if t then t else t {- условное выражение -} 0 {- константа «ноль» -} succ t {- следующее число -} pred t {- предыдущее число -} iszero t {- проверка на ноль -}

Слайд 21

Описание слайда:

О синтаксисе псевдо-языка (повтор) Множество термов – это наименьшее множество  такое , что 1. {true; false; 0}  T ; 2. если t1  T , то {succ t1; pred t1; iszero t1} T ; 3. если t1  T , t2  T , t3  T , то if t1 then t2 else t3  T .

Слайд 22

Описание слайда:

Семантические стили Для определения смысла программы необходим её математический эквивалент, а для его построения нам надо в точности знать свойства языка, на котором написана программа. Проблема сводится к отысканию способа построения математических эквивалентов всех конструкций языка - к формализации его семантики.

Слайд 23

Описание слайда:

Семантические стили Семантика языка — это смысловое значение слов. В программировании — начальное смысловое значение операторов, основных конструкций языка и т. п. 1) i=0; while(i

Слайд 24

Описание слайда:

Семантические стили Различные подходы к формализации семантики: Операционная семантика Денотационая семантика Аксиоматическая семантика Интерпретационная семантика Трансляционная семантика Трансформационная семантика

Слайд 25

Описание слайда:

Семантические стили Операционная семантика Специфицирует поведение языка определяя простую абстрактную машину (использует термы языка, а не машинные команды) Состояние машины – терм Поведение определяется функцией перехода. Смысл терма t – конечное состояние

Слайд 26

Описание слайда:

Семантические стили Трансляционная семантика Описание операционной семантики конструкций в терминах языков программирования высокого уровня. С помощью этого способа можно изучать язык, схожий с уже известным программисту.

Слайд 27

Описание слайда:

Семантические стили Трансформационная семантика Описание операционной семантики конструкций языка в терминах этого же языка. Трансформационная семантика является основой метапрограммирования.

Слайд 28

Описание слайда:

Семантические стили Денотационная семантика Смысл терма - математические объекты (число, функция, их величины) Построение семантики: нахождение набора семантических доменов (СД) Определение функции интерпретации – (соответствие СД и термов)

Слайд 29

Описание слайда:

Семантические стили Аксиоматическая семантика Семантика каждой синтаксической конструкции языка определяется как некий набор аксиом или правил вывода, который можно использовать для вывода результатов выполнения этой конструкции. Чтобы понять смысл всей программы, эти аксиомы и правила вывода следует использовать так же, как при доказательстве обычных математических теорем. Смысл терма, то что можно о нем доказать. Когда программа выполнена, получаем доказательство - что вычисленные результаты удовлетворяют необходимым ограничениям на их значения относительно входных значений. То есть, доказано, что выходные данные представляют значения соответствующей функции, вычисленной по значениям входных данных.

Слайд 30

Описание слайда:

Семантические стили Интерпретационная семантика описание операционной семантики конструкций в терминах языков программирования низкого уровня (язык ассемблера, машинный код). Позволяет выявлять медленно выполняемые участки программы, и зачастую используется в целях оптимизации кода программ.

Слайд 31

Описание слайда:

ВЫЧИСЛЕНИЯ

Слайд 32

Описание слайда:

ВЫЧИСЛЕНИЯ (случай только булевых выражений) t → t’ понимается как t за 1 шаг вычисляется как t’ Константы ни во что не вычисляются E-IFTrue и E-IFFalse – рабочие правила E-IF – правило соответствия Определение: Экземпляр правила вывода получается при замене каждой метапеременной в заключении правила и во всех его предпосылках

Слайд 33

Описание слайда:

ВЫЧИСЛЕНИЯ Пример

Слайд 34

Описание слайда:

ВЫЧИСЛЕНИЯ (случай только булевых выражений) Определение: Правило выполняется на отношении, если для каждого экземпляра правила его заключение является элементом отношения, либо одна из его предпосылок не является таковой

Слайд 35

Описание слайда:

ВЫЧИСЛЕНИЯ (случай только булевых выражений) Определение: Одношаговое отношение вычисления → есть наименьшее бинарное отношение на термах, на котором выполняются все три правила Если пара (t → t’) является элементом отношения вычисления, то говорят, что утверждение о вычислении t → t’ выводимо

Слайд 36

Описание слайда:

ВЫЧИСЛЕНИЯ Пример

Слайд 37

Описание слайда:

ВЫЧИСЛЕНИЯ (свойства отношения вычисления) Теорема [теорема о детерминированности одношагового вычисления]

Слайд 38

Описание слайда:

ВЫЧИСЛЕНИЯ (свойсТва конечного состояния) Результат вычисления – конечное состояние Определение 3 Терм t находится в нормальной форме если к нему не применимо никакое правило вычисления (t’, т.ч. t → t’ ) Теорема 2. Всякое значение находится в нормальной форме. Теорема 3. Всякая нормальная форма есть значение

Слайд 39

Описание слайда:

ВЫЧИСЛЕНИЯ Определение. Отношение многошагового вычисления →* это наименьшее отношение, т.ч. (1) Если t → t’, то t →* t’ (2) Для всех t выполняется t →* t (3) Если t →* t’ и t’ →* t’’, то t →* t’’

Слайд 40

Описание слайда:

ВЫЧИСЛЕНИЯ Теорема [теорема о единственности нормальных форм] Если t →* u и t →* u’ нормальные формы, то u=u’

Слайд 41

Описание слайда:

ВЫЧИСЛЕНИЯ Каждый терм можно вычислить и получить значение Теорема [завершение вычислений] Для каждого терма t существует нормальная форма t’ такая что и t →* t’

Слайд 42

Описание слайда:

ВЫЧИСЛЕНИЯ Домашнее задание: упражнение 3.5.13, стр. 59

Слайд 43

Описание слайда:

ВЫЧИСЛЕНИЯ (арифметические выражения)

Слайд 44

Описание слайда:

ВЫЧИСЛЕНИЯ (арифметические выражения) Определение. Терм если он находиться в нормальной форме, но не является значением называется тупиковым термом Пример: succ false