🗊Презентация Функциональное программирование в реальной жизни

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

Лекция 4 Функциональное программирование в реальной жизни

zn+1(c)= zn2(c)+c, z0(c)=0; zC zn+1(c)= zn2(c)+c, z0(c)=0; zC M = { c  C | lim zn(c)<∞} M’= { c  C | |z20(0)|<1 }

Mainstream языки программирования: Mainstream языки программирования: C# 3.0, следующий стандарт C++ Java.next (Clojure, Groovy, JRuby, Scala) LINQ XSLT Excel Spreadsheets

Autocad Autocad emacs (LISP) HeVeA Проекты в рамках Microsoft и MSR F# Compiler Driver code verification AdCenter Challenge

Cash-cow of Search Cash-cow of Search Selling “web space” at www.live.com and www.msn.com. “Paid Search” (prices by auctions) The internal competition focuses on Paid Search.

4 месяца на программирование 4 месяца на программирование 1 месяц на обучение Задача: На основе обучающих данных за несколько недель (просмотры страниц) предсказывать вероятность перехода по ссылке Ресурсы: 4 (2 x 2) 64-bit CPU machine 16 Гб ОП 200 Гб НЖМД

Объем входных данных Объем входных данных 7,000,000,000 записые, 6 терабайт Время ЦП на обучение: 2 недели × 7 дней × 86,400 сек/день = 1,209,600 секунд Требования к алгоритму обучения: 5,787 записей / сек 172.8 μs на одну запись

4 недели кодирования, 4 эксперта в области Machine Learning 4 недели кодирования, 4 эксперта в области Machine Learning 100 миллионов вероятностных переменных Обработано 6 терабайт обучающих данных Обработка в реальном времени!

Обработка данных Обработка данных Синтаксический разбор Компиляторы, преобразования программ Data Mining Традиционное мнение: плохо решаются UI-задачи Смотрим пример!

Отсутствие операторов присваивания и побочных эффектов Отсутствие операторов присваивания и побочных эффектов Функции-как-данные – между функциями и данными не делается явного различия, в чистом ФП «все есть функция» Декларативное программирование Высокая функциональная абстракция Более короткий и выразительный код За счет автоматического вывода типов За счет отсутствия операторов присваивания Прозрачная семантика, близость к математическому понятию функции Возможность рассуждать о программах, доказывать их свойства

Принципы функционального программирования Принципы функционального программирования Математическая теория в основе функционального программирования – λ-исчисление Семантика функциональных языков, вопросы реализации Языки функционального программирования: Базовый язык - F# Семейство ML-языков: OCaml, Caml Light, ML, SML Другие похожие языки: Haskell, Hope, … Классика ФП – LISP Примеры на C#, XSLT, …

Лекции – 14 шт. (по 2 шт. раз в 2 недели) Лекции – 14 шт. (по 2 шт. раз в 2 недели) Интерактивные занятия – 2 шт. Доклады Обсуждения Семинары по подгруппам, по 1 паре, раз в 2 недели Лабораторные работы (6-8 шт.) выполняются дома самостоятельно http://functional.soshnikov.com

Экзамен (письменный, 5 вопросов) – 50% Экзамен (письменный, 5 вопросов) – 50% Лабораторные работы – 25% - ОБЯЗАТЕЛЬНОЕ! Самостоятельная работа (доклады, выступления на семинарах, вопросы, дополнительная работа) – 25% 5 – 75% 4 – 60% 3 – 50%

Научно-исследовательская работа Научно-исследовательская работа Выполнение полу-исследовательского проекта Выступление с докладом (15-20 мин.) Функциональное программирование в реальном мире Разбор масштабного примера (Fractal-3D, график функции) Обзор библиотеки / fsharp samples Обзор языка функционального программирования Функционально-стековый язык catl

http://functional.soshnikov.com http://functional.soshnikov.com Филд А., Харрисон П. Функциональное программирование. – М.: Мир, 1993. Harrison, J. Introduction to Functional Programming. Lecture Notes, Cambridge University, 1997. R.Pickering, Foundations of F#, A-Press, 2008. D.Syme, A.Granicz, A.Cisternio. Expert F#. A-Press, 2008 E. Chailloux, P. Manoury, B.Pagano. Разработка программ с помощью Objective Caml. O’Reilly. Русский перевод: http://shamil.free.fr/comp/ocaml/ Хювёнен Э., Сеппенен И. Мир Lisp'а. В 2-х томах. М.: Мир, 1990. J.Harrop, F# for Scientists, Wiley, 2008. Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley, 1999. http://www.codeplex.com/fsharpsamples