Разработка приложений на языке F# Андрей Терехов Microsoft Украина

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

Подробнее про F# Lisp Scheme Common Lisp ML HopeSML Miranda Haskell Caml OCaml F#C# 3.0 FORTRAN …

Глобальные проблемы программирования СЛОЖНОСТЬ - Сложность окружающего мира влияет на сложность программных систем - Параллелизм – необходимость писать параллельный код резко увеличивает сложность - Сложная система => большее количество ошибок, резко возрастает стоимость качественного кода + Сложность удается частично скрыть с помощью инструментов разработки (пример: языки высокого уровня) + Software Factories, Domain-Specific Languages Актуальность этих проблем быстро растет со временем

Как бороться со сложностью? Наследование в ООП Перенос сложных функций (в т.ч. распараллеливание) на систему программирования или runtime Domain-Specific Languages, Software Factories Декларативное программирование Функциональная абстракция Абстракция Структурное программирование (процедуры/функции, пошаговая детализация) Компонентный подход Объектная декомпозиция Функциональная декомпозиция Декомпозиция

Подходы к параллельным вычислениям Программирование «вручную» Locks, Semaphores, …, MPI.NET Parallel Extensions /.NET 4.0 Parallel.For, … Применимо только к независимым участкам кода Декларативное программирование Parallel LINQ CCR (Concurrency Coordination Runtime) Транзакционная память Функциональный подход!

«Классическое программирование» Императивное – мы говорим компьютеру, как решать задачу (что делать) Основной акцент – манипулирование ячейками памяти – Оператор присваивания Функции как способ декомпозиции задачи на более простые

Функциональное программирование Парадигма программирования, которая рассматривает выполнение программы как вычисление математических функций (выражений) – Неизменяемые данные, нет состояния среды – Функции – first-class citizen Стиль программирования, позволяющий писать программы, свободные от ошибок Языки программирования (F#, LISP, ML, Haskell, …)

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

Особенности ФП Функциональное программирование имеет очень четкую математическую основу – Рассуждение о программах: доказательство корректности, … Определение последовательности действий – рекурсивно – При умелом программировании не ведет к падению эффективности (компилятор сводит к итерации) Встроенные структуры данных (tuples, списки, discriminated unions) с компактным синтаксисом Отсутствует оператор присваивания – let имеет другую семантику – связывание имен – Будучи один раз связанным, имя не может менять свое значение (в рамках области видимости) – А это значит – нет побочных эффектов! – Раз в императивной программе 90% - это операторы присваивания, то функциональные программы на 90% короче!

Демо Синтаксис Связывание имен Типизация Применение функций Реализация циклов в функциональном стиле Знакомство с F#

Пример: вычисление числа π S/A=Pi*R 2 /4/R 2 =H/M public double area(double p) { var R = new Random(); int max = 10000; int hits = 0; for (var i = 0; i < max; i++) { var x = R.NextDouble() * p; var y = R.NextDouble() * p; if (x * x + y * y

Вычисление π на F# let rand max n = Seq.generate (fun () -> new System.Random(n)) (fun r -> Some(r.NextDouble()*max)) (fun _ -> ());; let MonteCarlo hit max iters = let hits = (float)( Seq.zip (rand max 1) (rand max 3) |> Seq.take iters |> Seq.filter hit |> Seq.length) in 4.0*max*max*hits/((float)iters);; let area radius = MonteCarlo (fun (x,y) -> x*x+y*y

Декомпозиция Какие способы комбинирования функций доступны в традиционном программировании? function myexp(x:real):real; var s : real; i : integer; begin s:=0; for i:=0 to 10 do s:=s+taylor(x,i); end; function taylor(x : real, i:integer):real; begin taylor:=power(x,i)/fact(i); end; Вызов Композиция

Функциональная декомпозиция MyExp Taylor PowFact

Декомпозиция и абстракция в функциональном стиле Более богатые возможности композиции за счет рассмотрения «функций- как-данных» iter – функциональная абстракция, лежащая в основе вычисления myexp, pow, fact и др. iter – может быть получено как частный случай абстракции let iter f a b i = fold_left f i [a..b];; let rec iter f a b i = if a>b then i else f (iter f (a+1) b i) a;; let pow x n = iter (fun y i -> y*x) 1 n 1.0;; let fact n = iter (fun y i -> y*(float i)) 1 n 1.0;; let taylor x n = pow x n / fact n;; let myexp x = iter (fun y n -> y+taylor x n) ;; f(f(f(…f(i,b),b-1)),…,a+1),a)

Функциональная декомпозиция При этом: – Технология мемоизации и ленивых вычислений могут увеличить эффективность вычисления факториала и степени до линейной, за счет запоминания предыдущих результатов вычислений – Функционально-декомпозированный (более простой для человека) алгоритм будет обладать такой же эффективностью, что и более сложный алгоритм вычисления суммы в одном цикле (домножение предыдущего слагаемого на фактор) iter fold_left MyExp Taylor PowFact

Простота vs. эффективность Сравните: function sum_even(L:List):integer; var s : integer; begin s:=0; foreach (var x in L) do if x mod 2 = 0 then s:=s+x; sum_even:=s; end; let sum_even L = sum(List.filter(fun x->x%2=0) L);;

Плюсы/минусы Императивный подход На первый взгляд – большая эффективность по памяти (не создаются списки), по времени (один проход) Нет декомпозиции задачи, невозможно повторно использовать код Функциональный подход Высокий уровень абстракции -> решение для других фигур получается заменой функции Проще для математика? Для программиста? Пусть компилятор заботится об эффективности! Большая эффективность при параллельных вычислениях (возможность распараллеливания, поскольку списковые функции не имеют зависимостей по данным) При использовании ленивых вычислений / LINQ – получаем однопроходный алгоритм, эквивалентный императивному!

Другой пример: сортировка Хоара void quickSort (int a[], int l, int r) { int i = l; int j = r; int x = a[(l + r) / 2]; do { while (a[i] < x) i++; while (x < a[j]) j--; if (i qsort([for x in t do if xh then yield x]);;

Особенности функционального подхода Множество способов комбинирования дает дополнительное преимущество в борьбе со сложностью Можно эксплуатировать как декомпозицию, так и функциональную абстракцию Отсутствие побочных эффектов резко снижает затраты на тестирование и отладку Декларативный стиль перекладывает существенную часть решения на компилятор (пример: суммирование четных элементов списка) Функциональный код явно описывает зависимости по данным, позволяя более эффективно распараллеливать код Функциональный подход приводит к более компактному коду, но требует больших размышлений и специальных навыков

Множество Мандельброта

Определение z n+1 (c)= z n 2 (c)+c, z 0 (c)=0; z C M = { c C | lim z n (c)

Реализация на F# let mandelf (c:Complex) (z:Complex) = z*z+c;; let ismandel c = Complex.Abs(rpt (mandelf c) 20 Complex.zero)

WinForms #light open System.Drawing open System.Windows.Forms let form = let image = new Bitmap(400, 400) let lscale = scale (-1.0,1.0) (0,400) for i = 0 to (image.Height-1) do for j = 0 to (image.Width-1) do let t = complex (lscale i) (lscale j) in image.SetPixel(i,j,if ismandel t then Color.Black else Color.White) let temp = new Form() temp.Paint.Add(fun e -> e.Graphics.DrawImage(image, 0, 0)) temp [ ] do Application.Run(form);;

Результат

Вычисления «по требованию» По умолчанию – энергичная стратегия вычислений Lazy / Force Вычисления по необходимости open System.IO let rec allFiles(dir) = seq { for file in Directory.GetFiles(dir) do yield file for sub in Directory.GetDirectories(dir) do yield! allFiles(sub) } |> Seq.take 100 |> show

F# - это: Мультипарадигмальный язык Функционально-императивный С акцентом на функциональном программировании Компактный код Автоматический вывод типов – при статической типизации! Встроенные структуры данных, своя библиотека обработки Интероперабельность с.NET Все возможности.NET Framework Двухсторонняя интероперабельность с пользовательским кодом Эффективный язык Статическая типизация Оптимизаторы порождают качественный.NET-код (оптимизация хвостовой рекурсии) Ленивые вычисления

C# 3.0 – императивно- функциональный язык! var s = new int[] {1, 2, 3}; Вывод типов var x = new { Name=Вася, Age=30 }; Анонимные типы (tuples) var double = x => x*2; Функциональные константы Func,int> sum = X => X.Aggregate((x,y)=>(x+y), 0); Функции высших порядков Expression > test = s => s.Group==806; Expression Trees (метапрограммир.)

LINQ Технология Language Integrated Query представляет собой трансляцию SQL-подобного синтаксиса в выражение в функциональном стиле Выражение представляет собой отложенное вычисление / преобразование функциональных вызовов к синтаксису источника данных Идеи из ФП: ленивые вычисления, мета-программирование var res = from x in L where x.Age>16 orderby x.Age select x.Name; var res = L.Where(x => x.Age>16).OrderyBy(x=>x.Age).Select(x => x.Name);

ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ И ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

Основные проблемы асинхронных и параллельных вычислений Общая память Инверсия управления Параллелизм ввода-вывода Масштабирование

Общая память Инверсия управления Параллелизм ввода-вывода Масштабирование o Сложность поддержки и тестирования o Сложно распараллеливать! o Фундаментальные проблемы locking: o Явная разработка параллельного кода o Всем модулям системы надо учитывать параллельность

Asynchronous Workflows let task1 = async { return } let task2 = async { return } Async.Parallel [ task1; task2 ];; let map' func items = let tasks = seq { for i in items -> async { return (func i) } } Async.RunSynchronously (Async.Parallel tasks) ;; let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1);; List.map (fun x -> fib(x)) [1..30];; map' (fun x -> fib(x)) [1..30];;

Инверсия управления Общая память Инверсия управления Параллелизм ввода-вывода Масштабирование o Привычка писать последовательный код o Асинхронное программирование ведёт к разделению начала и конца действия o Сложность o Совмещение нескольких асинхр.операций o Исключения и отмена

using System; using System.IO; using System.Threading; public class BulkImageProcAsync { public const String ImageBaseName = "tmpImage-"; public const int numImages = 200; public const int numPixels = 512 * 512; // ProcessImage has a simple O(N) loop, and you can vary the number // of times you repeat that loop to make the application more CPU- // bound or more IO-bound. public static int processImageRepeats = 20; // Threads must decrement NumImagesToFinish, and protect // their access to it through a mutex. public static int NumImagesToFinish = numImages; public static Object[] NumImagesMutex = new Object[0]; // WaitObject is signalled when all image processing is done. public static Object[] WaitObject = new Object[0]; public class ImageStateObject { public byte[] pixels; public int imageNum; public FileStream fs; } using System; using System.IO; using System.Threading; public class BulkImageProcAsync { public const String ImageBaseName = "tmpImage-"; public const int numImages = 200; public const int numPixels = 512 * 512; // ProcessImage has a simple O(N) loop, and you can vary the number // of times you repeat that loop to make the application more CPU- // bound or more IO-bound. public static int processImageRepeats = 20; // Threads must decrement NumImagesToFinish, and protect // their access to it through a mutex. public static int NumImagesToFinish = numImages; public static Object[] NumImagesMutex = new Object[0]; // WaitObject is signalled when all image processing is done. public static Object[] WaitObject = new Object[0]; public class ImageStateObject { public byte[] pixels; public int imageNum; public FileStream fs; } public static void ReadInImageCallback(IAsyncResult asyncResult) { ImageStateObject state = (ImageStateObject)asyncResult.AsyncState; Stream stream = state.fs; int bytesRead = stream.EndRead(asyncResult); if (bytesRead != numPixels) throw new Exception(String.Format ("In ReadInImageCallback, got the wrong number of " + "bytes from the image: {0}.", bytesRead)); ProcessImage(state.pixels, state.imageNum); stream.Close(); // Now write out the image. // Using asynchronous I/O here appears not to be best practice. // It ends up swamping the threadpool, because the threadpool // threads are blocked on I/O requests that were just queued to // the threadpool. FileStream fs = new FileStream(ImageBaseName + state.imageNum + ".done", FileMode.Create, FileAccess.Write, FileShare.None, 4096, false); fs.Write(state.pixels, 0, numPixels); fs.Close(); // This application model uses too much memory. // Releasing memory as soon as possible is a good idea, // especially global state. state.pixels = null; fs = null; // Record that an image is finished now. lock (NumImagesMutex) { NumImagesToFinish--; if (NumImagesToFinish == 0) { Monitor.Enter(WaitObject); Monitor.Pulse(WaitObject); Monitor.Exit(WaitObject); } public static void ReadInImageCallback(IAsyncResult asyncResult) { ImageStateObject state = (ImageStateObject)asyncResult.AsyncState; Stream stream = state.fs; int bytesRead = stream.EndRead(asyncResult); if (bytesRead != numPixels) throw new Exception(String.Format ("In ReadInImageCallback, got the wrong number of " + "bytes from the image: {0}.", bytesRead)); ProcessImage(state.pixels, state.imageNum); stream.Close(); // Now write out the image. // Using asynchronous I/O here appears not to be best practice. // It ends up swamping the threadpool, because the threadpool // threads are blocked on I/O requests that were just queued to // the threadpool. FileStream fs = new FileStream(ImageBaseName + state.imageNum + ".done", FileMode.Create, FileAccess.Write, FileShare.None, 4096, false); fs.Write(state.pixels, 0, numPixels); fs.Close(); // This application model uses too much memory. // Releasing memory as soon as possible is a good idea, // especially global state. state.pixels = null; fs = null; // Record that an image is finished now. lock (NumImagesMutex) { NumImagesToFinish--; if (NumImagesToFinish == 0) { Monitor.Enter(WaitObject); Monitor.Pulse(WaitObject); Monitor.Exit(WaitObject); } public static void ProcessImagesInBulk() { Console.WriteLine("Processing images... "); long t0 = Environment.TickCount; NumImagesToFinish = numImages; AsyncCallback readImageCallback = new AsyncCallback(ReadInImageCallback); for (int i = 0; i < numImages; i++) { ImageStateObject state = new ImageStateObject(); state.pixels = new byte[numPixels]; state.imageNum = i; // Very large items are read only once, so you can make the // buffer on the FileStream very small to save memory. FileStream fs = new FileStream(ImageBaseName + i + ".tmp", FileMode.Open, FileAccess.Read, FileShare.Read, 1, true); state.fs = fs; fs.BeginRead(state.pixels, 0, numPixels, readImageCallback, state); } // Determine whether all images are done being processed. // If not, block until all are finished. bool mustBlock = false; lock (NumImagesMutex) { if (NumImagesToFinish > 0) mustBlock = true; } if (mustBlock) { Console.WriteLine("All worker threads are queued. " + " Blocking until they complete. numLeft: {0}", NumImagesToFinish); Monitor.Enter(WaitObject); Monitor.Wait(WaitObject); Monitor.Exit(WaitObject); } long t1 = Environment.TickCount; Console.WriteLine("Total time processing images: {0}ms", (t1 - t0)); } public static void ProcessImagesInBulk() { Console.WriteLine("Processing images... "); long t0 = Environment.TickCount; NumImagesToFinish = numImages; AsyncCallback readImageCallback = new AsyncCallback(ReadInImageCallback); for (int i = 0; i < numImages; i++) { ImageStateObject state = new ImageStateObject(); state.pixels = new byte[numPixels]; state.imageNum = i; // Very large items are read only once, so you can make the // buffer on the FileStream very small to save memory. FileStream fs = new FileStream(ImageBaseName + i + ".tmp", FileMode.Open, FileAccess.Read, FileShare.Read, 1, true); state.fs = fs; fs.BeginRead(state.pixels, 0, numPixels, readImageCallback, state); } // Determine whether all images are done being processed. // If not, block until all are finished. bool mustBlock = false; lock (NumImagesMutex) { if (NumImagesToFinish > 0) mustBlock = true; } if (mustBlock) { Console.WriteLine("All worker threads are queued. " + " Blocking until they complete. numLeft: {0}", NumImagesToFinish); Monitor.Enter(WaitObject); Monitor.Wait(WaitObject); Monitor.Exit(WaitObject); } long t1 = Environment.TickCount; Console.WriteLine("Total time processing images: {0}ms", (t1 - t0)); } let ProcessImageAsync () = async { let inStream = File.OpenRead(sprintf "Image%d.tmp" i) let! pixels = inStream.ReadAsync(numPixels) let pixels' = TransformImage(pixels,i) let outStream = File.OpenWrite(sprintf "Image%d.done" i) do! outStream.WriteAsync(pixels') do Console.WriteLine "done!" } let ProcessImagesAsyncWorkflow() = Async.Parallel [ for i in 1.. numImages -> ProcessImageAsync i ] Обработка изображений

Asynchronous Workflows open System.Net open Microsoft.FSharp.Control.WebExtensions let urlList = [ "Microsoft.com", " "MSDN", " "Bing", " ] let fetchAsync(name, url:string) = async { try let uri = new System.Uri(url) let webClient = new WebClient() let! html = webClient.AsyncDownloadString(uri) printfn "Read %d characters for %s" html.Length name with | ex -> printfn "%s" (ex.Message); } let runAll() = urlList |> Seq.map fetchAsync |> Async.Parallel |> Async.RunSynchronously |> ignore runAll()

Параллелизм ввода-вывода Общая память Инверсия управления Параллелизм ввода-вывода Масштабирование o Ввод-вывод часто становится узким местом o Веб-сервисы o Данные на диске o Ресурсы ввода-вывода естественным образом параллельны o Большие возможности для ускорения

Масштабирование Общая память Инверсия управления Параллелизм ввода-вывода Масштабирование o На несколько компьютеров o Многокомпьютерные ресурсы o Собственные кластеры o Облачные вычисления / Windows Azure o Но o Общая память не масштабируется

Recap: Some Concurrency Challenges Общая память Инверсия управления Параллелизм в/в Масштабирование immutability async { … } agents

ПЕРСПЕКТИВЫ ПРИМЕНЕНИЯ ФП

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

ФП в реальных проектах emacs (диалект LISPа) HeVeA – LaTeX to HTML конвертер (Objective Caml) Genome Assembly Viewer (F#, 500 строк) ПО для телефонных станций Ericsson (Erlang) Проекты в рамках Microsoft и MSR – F# Compiler – Driver code verification – AdCenter Challenge

Наиболее прибыльная часть поиска Продажа «веб-пространства» на и Оплаченные ссылки (цены выставляются по аукциону) Внутреннее соревнование с упором на оплаченные ссылки The adCenter Challenge

Внутреннее соревнование 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 записей / сек – μs на одну запись

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

Наблюдения Быстрое кодирование Вывод типов – меньше печатать, больше думать Agile-стиль Думаем в терминах предметной области, не языка Скриптинг Интерактивное «исследование» данных и тестирование алгоритмов Совместно с Excel Производительность Немедленное масштабирование на огромные массивы данных Экономный расход памяти Огромные структуры данных на 16 Гб Выразительный синтаксис Краткий код позволяет легко осуществлять рефакторинг и реиспользование Символьная обработка Метапрограммирование Интеграция с.NET В том числе Excel, SQL Server

Какие задачи хорошо решаются на функциональных языках? Обработка данных – Синтаксический разбор – Компиляторы, преобразования программ – Data Mining – Биоинформатика Вычислительные задачи Параллельные задачи Традиционное мнение: сложно строить UI – Смотрим пример!

Источники

Филд А., Харрисон П. Функциональное программирование, М.: Мир, 1993 J.Ullman, Elements of ML Programming, 2 nd edition, Prentice Hall, 1998 Thompson S. Haskell: The Craft of Functional Programming, 2nd edition, Addison-Wesley, 1999 R.Pickering, Foundations of F#, A-Press, 2008 D.Syme, A.Granicz, A.Cisternio. Expert F#. A-Press, 2008 J.Harrop, F# for Scientists, Wiley, 2008 Д.В. Сошников «Функциональное программирование», видеокурс:

Андрей Терехов Директор департамента стратегических технологий Microsoft Украина Вопросы?