1 Функциональное программирование. 2 Симуни Михаил Лазаревич msimuni.wikidot.com/fp группа ВКонтакте Функциональное программирование (мат-мех 13) simuni@mail.ru. - презентация

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

2 2 Симуни Михаил Лазаревич msimuni.wikidot.com/fp группа ВКонтакте Функциональное программирование (мат-мех 13)

3 3 Что надо будет для зачета? 1. Набрать >= 20 баллов 2. Зачет: задачи + теор.вопросы 3. Контрольная в середине курса (в начале ноября) Больше баллов – льготы на зачете 30 – минус 1 задача 40 – минус 2 задачи 50 – минус 3 задачи и т.д.

4 4 Откуда берутся баллы Задачи на дом (примерно по 4 задачи на занятии) И еще, скорее всего, будут дополнительные задачи посложнее

5 5 Про задачи Как сдавать задачи: Система тестирования Или можно присылать по почте, или приносить на листке Правила про задачи: Надо сдавать не позже начала пары Можно писать не (совсем) правильно Нельзя присылать очень похожие решения…

6 6 На чем писать? Я пишу на Haskell и немного на C# и С++ Желающие могут использовать и другой язык (почти для всех задач подходит F#, LISP (Clojure, Racket и т.д.), ML (OCaml), Scala, Erlang и т.д. А м.б. и Питон, Ruby и т.д. Компиляторы – Haskell Platform, WinHugs, FP Haskell Center (?) На сайте документ «Как работать с Hugs»

7 7 Литература См. ссылки на сайте Роганова Н.А. «Функциональное программирование» – основы, очень просто

8 8 Немного истории

9 Алонзо Черч Alonzo Chirch Примерно 1932 г. (10 лет до первого компьютера!) Вопросы: Что такое алгоритм? Выбрать минимальный набор средств, которым можно описать любой алгоритм Ответы: Тьюринг: Машина Тьюринга Черч: Лямбда-исчисление: Функции! 9

10 Лисп John McCarthy 1958 г. LISP Язык высокого уровня #2! (После Фортрана) Маленький и простой Не используется GOTO и т.д. Сборка мусора Программы можно использовать, как данные 10

11 Haskell и потом Scheme, ML, OCAML … 1990 – Haskell C# 3.0 F# C++11 Java 8 Erlang Scala Python, Ruby и т.д. 11

12 12 Функциональное программирование – это про что?

13 Чисто фунциональное программирование Wikipedia: functional programming is a programming paradigm, that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Т.е. мы себя ограничиваем Не использовать оператор присваивания Все переменные const А.П.Ершов: Примерно как играть в волейбол с одной й привязанной рукой Зачем? Меньше ошибок Проще оптимизировать Проще выполнять параллельно И т.д. Действительно так? John Hughes «Why Functional Programming Matters» «Если бы исключение оператора присваивания принесло такие огромные выгоды, то программисты на Фортране сделали бы это лет двадцать назад». 13

14 Функции высшего порядка Функция, параметр которой – тоже функция. Например: integral(0, 1, sin) draw(0, 1, cos) forall(list, print); Можно зайти очень далеко (и мы постараемся): Функции, как результат функции Сложные случаи (функция, которая возвращает функцию, которая возвращает функцию и т..д.) Например, одна из функций, которую придумал Черч: λn.λf.λx. n (λg.λh. h (g f)) (λu. x) (λu. u) 14

15 Ленивые вычисления, бесконечные списки x = sin(y); идея: может быть, тут не вычислять ничего… … cout

16 Система типов Вывод типов C#: var x = Math.Sin(1); Не надо писать тип x – компилятор и сам может догадаться И, опять же, попробуем далеко зайти) Вообще не пишем типы (ну, почти совсем…). Но они есть – компилятор выводит их сам. Полиморфизм То, что в С++ хотели ввести под именем concept (но не очень получилось) 16

17 Фокусы continuations «вызвать функцию, а потом …» Монады Один из примеров: Выполняем последовательность действий до первой ошибки М.б. еще что-то (lens, arrows)?? 17

18 Теория Лямбда исчисление Изоморфизм Карри-Ховарда М.б. еще что-то?? (free theorems?) 18

19 Это все действительно полезно знать? Будете ли вы писать на Хаскеле? Скорее всего, нет Будете ли вы использовать приемы ФП в обычных языках? Скорее всего, да Просто как пример, Map/Reduce Развивает сообразительность… 19

20 20 Простые программы на Haskell

21 Лексика Комментарии -- это комментарий {-- А это многострочный комментарий --} Имена Первая буква имеет значение x, sin – переменные, функции Integer, True - имена типов, константы Можно использовать кавычки abc 21

22 Числа Как обычно: e9 М.б. бесконечнозначные 2^100 2^1000 Операции как обычно: + - * / Для деления нацело с остатком функции div, mod ^ - возведение в степень 22

23 Логические значения Сравнение Не равно: /= Остальное как обычно: >= == True, False && || not Пример: x*y < 0 && (y*y + x*x < 1) 23

24 Функции Не совсем обычно! Не пишутся ни запятые, ни скобки sin x mod k 10 + div k 10 Приоритет: сначала функции, потом операторы sin x*x– это (sin x) * x Совет: Непонятная ошибка проверьте, правильно ли расставлены скобки f g x – это (f g) x Т.е. скобки группируются слева направо. sin sin 1 – это (sin sin) 1 (ошибка) А когда это удобно? Позже обсудим… 24

25 Как определить свою функцию Самый простой пример: sqr x = x*x Потом: sqr 5 Пример простой рекурсивной функции (Конечно же, это факториал:) fact 1 = 1 fact n = fact (n-1) * n Порядок важен! fact n = fact (n-1) * n fact 1 = 1 // Досюда не дойдет:( Одно ограничение, на первый взгляд непонятное: f n n = … // Так нельзя! Переменная слева от = не может встречаться 2 раза (называется: линейность) 25

26 Условный оператор. Где начинается следующее правило? if условие then выражение else выражение abs x = if x > 0 then x else –x f x = x + if x > 0 then x else 0 Откуда компилятор знает, где начинается следующее правило? С первой позиции в строке новое правило Строка начинается с пробела продолжение правила 26

27 Хвостовая рекурсия Накапливающие параметры 27

28 Как вычисляется факториал fact 1 = 1 fact n = fact (n-1) * n fact 5 = fact 4 * 5 fact 4 = fact 3 * 4 fact 3 = fact 2 * 3 fact 2 = fact 1 * 2 fact 1 = 1 Для fact на стеке будет вызовов

29 Еще вариант факториала Давайте сразу перемножать во время рекурсии fact n = fact n 1 fact' 1 p = p fact' n p = fact (n-1) (n*p) fact' 5 1 = fact 4 (5*1) fact' 4 5 = fact 3 (4*5) fact 3 20 = fact 2 (3*20) fact 2 60 = fact 1 (2*60) fact =120 fact n = fact n 1 fact' n p = fact (n-1) n*p fact' 1 p = p Две ошибки

30 Хвостовая рекурсия Если вызов функции – это последнее, что происходит при вычислении правило, то он называется хвостовым вызовом (tail call). Если в некоторой функции все рекурсивные вызовы – хвостовые, то говорят, что в этой функции используется хвостовая рекурсия (tail recursion) Студент X: пример хвостовой рекурсии: fact n = n * fact (n-1) Нет! Зачем нужна хвостовая рекурсия? Можно реализовать более эффективно (и во многих языках так и реализовано) Но не в Haskell… Иногда просто удобнее писать (накапливающие парамметры). 30

31 Накапливающие параметры Еще пример fact' 1 p = 1 fact' n p = fact (n-1) (n*p) Функция использует p, чтобы передавать в рекурсивный вызов информацию о частично вычисленном значении. Называется накапливающие параметры (accumulating parameters) Еще пример: sumprod n = … + n / 1*2*3*…*n sumprod n = sumprod 1 n 0 1 sumprod' 0 s p = s / p sumprod' n s p = sumprod (n-1) (s+n) (p*n) 31

32 Д.з. 1 Просто как напоминание, задачи можно решить online: Описать функцию f n, которая вычисляет: 1+1/(1+1/( /1)) - всего n дробей 2. Описать функцию b n, которая вычисляет 0+1/(1+1/(2+1/( /n))) - всего n дробей 3. Описать функцию: sumsin n = sin( n)/(sin 1+sin sin n)) В решении желательно (но не обязательно) использовать хвостовую рекурсию и накапливающие параметры. 32

33 Д.з Описать функцию sumfact n: sumfact n = 1!+2!+...+n! В решении желательно (но не обязательно) использовать хвостовую рекурсию и накапливающие параметры. 5. * Сколько существует строго возрастающих последовательностей положительных целых чисел, сумма которых равна данному числу n? Например, для n = 9 существуют такие последовательности: 1 2 6, 1 3 5, 1 8, 2 3 4, 2 7, 3 6, 4 5, 9, то есть ответ на вопрос равен 8 33