Сошников Дмитрий Валерьевич к.ф.-м.н., доцент Майкрософт Россия, департамент стратегических технологий Факультет инноваций и высоких технологий, МФТИ Факультет прикладной математики, МАИ

©2008 Сошников Д.В.

Lisp Scheme Common Lisp ML HopeSML Miranda Haskell Caml OCaml F#C# 3.0 FORTRAN …

©2008 Сошников Д.В.

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

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

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

©2008 Сошников Д.В.

let x = 0;; for i = 1 to 10 do let x = x+1;; for i = 1 to 10 do let x = x+1 in ();; x;; ?

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

©2008 Сошников Д.В. 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

©2008 Сошников Д.В. 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

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

©2008 Сошников Д.В. 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 quicksort ([ for x in t when x quicksort ([ for x in t when x>h -> x]);;

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

©2008 Сошников Д.В.

z n+1 (c)= z n 2 (c)+c, z 0 (c)=0; z C M = { c C | lim z n (c)

©2008 Сошников Д.В. let mandelf (c:Complex) (z:Complex) = z*z+c;; let ismandel c = Complex.Abs(rpt (mandelf c) 20 Complex.zero)

©2008 Сошников Д.В. #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);;

©2008 Сошников Д.В.

По умолчанию – энергичная стратегия вычислений 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

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

©2008 Сошников Д.В. 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 (метапрограммир.)

©2008 Сошников Д.В. Технология 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);

©2008 Сошников Д.В. let task1 = async { return } let task2 = async { return } Async.Run (Async.Parallel [ task1; task2 ]) let map' func items = let tasks = seq { for i in items -> async { return (func i) } } Async.Run (Async.Parallel tasks) ;; List.map (fun x -> fib(x)) [1..30];; map' (fun x -> fib(x)) [1..30];;

©2008 Сошников Д.В. let rec ffor op f (a: float) (b: float) (h: float) = if a>=b then f b else op (f a) (ffor op f (a+h) b h);; let mutable nsteps = ;; let integrate f a b = let h = (b-a)/nsteps in ffor (+) (fun x -> h*f(x)) a b h;; let pintegrate f a b = let c = (b-a)/2.0 in let t = Async.Run(Async.Parallel2( async { return integrate f a c }, async { return integrate f c b })) in fst t + snd t;;

©2008 Сошников Д.В. 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.Run (Async.Parallel [ for i in 1.. numImages -> ProcessImageAsync i ])

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

©2008 Сошников Д.В. AutoCAD emacs (LISP) HeVeA Проекты в рамках Microsoft и MSR F# Compiler Driver code verification AdCenter Challenge Genome Assembly Viewer (500 строк F#)

©2008 Сошников Д.В. Cash-cow of Search Selling web space at and Paid Search (prices by auctions) The internal competition focuses on Paid Search.

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

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

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

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

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

©2008 Сошников Д.В.

Филд А., Харрисон П. Функциональное программирование. – М.: Мир, Harrison, J. Introduction to Functional Programming. Lecture Notes, Cambridge University, R.Pickering, Foundations of F#, A-Press, D.Syme, A.Granicz, A.Cisternio. Expert F#. A-Press, 2008 Хювёнен Э., Сеппенен И. Мир Lisp'а. В 2-х томах. М.: Мир, J.Harrop, F# for Scientists, Wiley, Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley,

Сошников Дмитрий Валерьевич к.ф.-м.н., доцент