Характерные черты функциональных языков программирования

ХАРАКТЕРНЫЕ ЧЕРТЫ ФУНКЦИОНАЛЬНЫХ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ Alex Kolonitsky

ЧЕГО ОЖИДАТЬ. Будут  Идеи функционального программирования.  Примеры на языке Haskell /Scala  Сравнение функциональных языков и императивных. Не будет  Разбора математической теории, лежащей в основе функционального программирования.  Полного описания языка Haskell/Scala 2

СОДЕРЖАНИЕ  Введение  Вывод типов  Функции  Функция высшего порядка  Замыкание  Частичное применение и карринг  Функции вместо объектов  Algebraic data type  Сопоставление с образцом  Ленивые Вычисления  Неизменяемое состояние  Benefits 3

Введение ПРОГРАММИРОВАНИЕ...  Императивное – мы говорим компьютеру, как решать задачу (что делать по шагам).  Основной акцент – манипулирование ячейками памяти  Функции как способ декомпозиции задачи на более простые  Функциональное - мы говорим компьютеру, что решать (описание задачи). Выполнение программы рассматривается как вычисление математических функций (выражений).  Мы описываем функции, работающие над данными – система программирования решает, как их вычислять! 4

Введение ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ 5

Вывод типов КОНТРОЛЬ ТИПОВ  По времени выполнения  Статическая типизация — контроль типов осуществляется во время компиляции.  Динамическая типизация — контроль типов осуществляется во время выполнения.  …может быть строгим и слабым  Строгая типизация — совместимость типов автоматически контролируется транслятором:  Слабая типизация — совместимость типов никак транслятором не контролируется. В языках со слабой типизацией обычно используется подход под названием6 «утиная типизация».

Вывод типов ТИПИЗАЦИЯ (ДОПОЛНЯЕМ…) Статическая Динамическая + Повышение надежности - Понижение надежности - Избыточность описания + Удобство кодирования + Возможность поддержки + Гибкость кода ~ Понижение производительности + Эффективность выполнения 7

Вывод типов ВЫВОД ТИПОВ  Синтаксическая структура программы позволяет составить систему уравнений относительно типов ее частей, автоматическое решение которой избавляет программиста от необходимости явно указывать типы. 8

Вывод типов ВЫВОД ТИПОВ: SCALA class StringArrayFactory { def create: Array[String] = { val array: Array[String] = Array[String](“1”, “2”, “3”) array } } 9

Вывод типов ВЫВОД ТИПОВ: SCALA class StringArrayFactory { def create = { val array = Array(“1”, “2”, “3”) array } } 10

Вывод типов ВЫВОД ТИПОВ: SCALA object InferenceTest extends Application { val x = 1 + 2 * 3 // type of x is Int val y = x.toString() // type of y is String def inc(x: Int) = x + 1 // succ returns Int values } 11

Вывод типов ВЫВОД ТИПОВ: HASKELL correctChecksum :: ByteString -> Int -> Bool correctChecksum header checksum = checksum == checksum’ where −− sum of all 512 bytes in the header block, −− treating each byte as an 8−bit unsigned value checksum’ = BS.Char8.foldl’ (x y -> x + ord y) 0 header’ −− treating the 8 bytes of chksum as blank characters. header’ = BS.concat [BS.take 148 header, BS.Char8.replicate 8 ’ ’, BS.drop 156 header] 12

Вывод типов ВЫВОД ТИПОВ  статически типизированные языки способны производить вывод типов выражений вида: order.getCustomer().getName() тут из типа order автоматически выводится тип выражения order.getCustomer() и компилятор убеждается, что для этого типа определена операция getName()  Java, аналогично, позволяет в некоторых простых случаях выводить типовые аргументы методов- дженериков List<String> strings = Collections.emptyList(); List<String> strings = Collections.<String>emptyList(); 13

Вывод типов ВЫВОД ТИПОВ: ПРЕИМУЩЕСТВА… + Повышение надежность + Эффективность выполнения + Удобство кодирования ~ Возможность поддержки ~ Немногословность 14

СОДЕРЖАНИЕ  Функции  Функция высшего порядка  Замыкание  Частичное применение и карринг  Функции вместо объектов 15

Функция высшего порядка ФУНКЦИЯ ВЫСШЕГО ПОРЯДКА  Функция, принимающая на вход или возвращающая функцию.  Оператор отображения списка map: map :: ( a->b ) -> [a] -> [b] > map toUpper [”Hello”, ”World”] [”HELLO”, ”WORLD”]  Оператор фильтрации списка filter: filter :: ( a -> Bool) -> [a] -> [a] > filter even [1..10] [2,4,6,8,10] 16

Функция высшего порядка ФУНКЦИЯ ВЫСШЕГО ПОРЯДКА SCALA import math._ // functions as values val cube = (x: Double) => x * x * x val cuberoot = (x: Double) => pow(x, 1 / 3d) // higher order function, as a method def compose[A,B,C](f: B => C, g: A => B) = (x: A) => f(g(x)) // partially applied functions in Lists val fun = List(sin _, cos _, cube) val inv = List(asin _, acos _, cuberoot) // composing functions from the above Lists val comp = (fun, inv).zipped map (_ compose _) // output results of applying the functions 17 comp foreach {f => println(f(0.5))}

Замыкание ЗАМЫКАНИЕ  Функция, использующая переменные из области видимости, в которой была создана.  Замыкание — это особый вид функции. Она определена в теле другой функции и создаётся каждый раз во время её выполнения. В записи это выглядит как функция, находящаяся целиком в теле другой функции. При этом вложенная внутренняя функция содержит ссылки на локальные переменные внешней функции. 18

Замыкание ЗАМЫКАНИЕ: JAVA class CalculationWindow extends JFrame { private JButton btnSave; ... public final void calculateInSeparateThread (final URI uri) { // Пример анонимного класса. new Thread() { void run() { // Имеет доступ к финальным (final) переменным: calculate(uri); // Имеет доступ к приватным членам содержащего класса: btnSave.setEnabled(true); } }.start(); } 19 }

Замыкание ЗАМЫКАНИЕ: SCALA var factor = 3 val multiplier = (i:Int) => i * factor val l1 = List(1, 2, 3, 4, 5) map multiplier factor = 5 val l2 = List(1, 2, 3, 4, 5) map multiplier println(l1) // List(3, 6, 9, 12, 15) println(l2) // List(5, 10, 15, 20, 25) 20

Замыкание ЗАМЫКАНИЕ: SCALA val belowFirst = (xs : List[Int]) => { val first = xs(0) val isBelow = (y : Int) => y < first for (x <- xs; if(isBelow(x))) yield x } ... belowFirst(List(5, 1, 7, 4, 9, 11, 3)) // => List( 1, 4, 3 ) 21

Замыкание ЗАМЫКАНИЕ: HASKELL f x = (y -> x + y) Внутренняя(анонимная) функция использует переменную х из контекста внешней функции f 22

Замыкание ЗАМЫКАНИЕ: HASKELL t -> t1 -> (t -> t1 -> t2) -> t2 pair a b = fnc -> fnc a b first p = p (a b -> a) second p = p (a b -> b) some_pair = pair 1 2 > first some_pair 1 > second some_pair 2 23

Замыкание ЗАМЫКАНИЕ: JAVASCRIPT function pair(a, b) { return function (fuc) { return fnc(a, b) } } function first(p) { return p(function(a, b) {return a}) } function second(p) { return p(function(a, b) {return b}) } var somePair = pair(1, 2) first(somePair) // 1 second(somePair) // 2 24

Currying ЧАСТИЧНОЕ ПРИМЕНЕНИЕ, КАРРИНГ  Фиксацией некоторых аргументов из функции получается новая функция с меньшим числом аргументов.  У термина «карринг» есть три взаимосвязанных значения 1. Фиксация несколько первых аргументов 2. Каррирование f: X*Y -> Z, есть построение f`: X -> (Y -> Z) 3. Применение каррированной функции к аргументам g = f`(x) 25

Currying КАРРИРОВАНИЕ 1. частный случай частичного применения, при котором фиксируется несколько первых аргументов функции add :: Integer -> Integer -> Integer add x y = x + y inc :: Integer -> Integer inc = add 1 26

Currying КАРРИРОВАНИЕ 1. Превращение функции F над 2-местным кортежем (парой с типами компонентов X и Y ) в функцию над X, возвращающую функцию над Y (такая функция называется «каррированной» версией F) matchesRegexpUncurried :: (String,String) -> Bool matchesRegexpUncurried = ... matchesRegexpCurried :: String -> (String -> Bool) matchesRegexpCurried pattern = matcher where matcher s = matchesRegexpUncurried (pattern,s) 27

Currying КАРРИРОВАНИЕ 1. Применение каррированной функции к аргументам: isNumber = matchesRegexpCurried ”−?[0−9]+” В таком случае говорят, что процедура isNumber получена каррированием процедуры matchesRegexpCurried 28

Currying КАРРИРОВАНИЕ SCALA def cat(s1: String)(s2: String) = s1 + s2 def cat(s1: String) = (s2: String) => s1 + s2 def curry(x:Int)(y:Int) = x + y // curry: (Int)(Int)Int curry(4)(5) // Int = 9 def multiplier(i: Int)(factor: Int) = i * factor val byFive = multiplier(5) _ val byTen = multiplier(10) _ 29

Currying КАРРИРОВАНИЕ SCALA def fs(f:Int=>Int, s:List[Int])=s map f def f1(x:Int)=x*2 def f2(x:Int)=x*x def fsf1 = fs (f1,_:List[Int]) def fsf2 = fs (f2,_:List[Int]) println(fsf1(List(0,1,2,3))) println(fsf1(List(2,4,6,8))) println(fsf2(List(0,1,2,3))) println(fsf2(List(2,4,6,8))) 30

Functions Ending TRY-WITH-RESOURCES STATEMENT try (BufferedReader br = new BufferedReader(new FileReader(path))) { return br.readLine(); } Any object that implements java.lang.AutoCloseable  void close() throws Exception 31

Functions Ending TRY-WITH-RESOURCES STATEMENT def using[A <: {def close(): Unit}, B](param: A) (f: A => B): B = try { f(param) } finally { param.close() } ... usage ... using(new BufferedReader(otherReader)) { reader => reader.readLine() } 32

Functions Ending ФУНКЦИИ ВМЕСТО ОБЪЕКТОВ  Замыкание и Каррирование связывают данные и функции аналогично объектам. 33

СОДЕРЖАНИЕ  Введение  Вывод типов  Функции  Функция высшего порядка  Замыкание  Частичное применение и карринг  Функции вместо объектов  Algebraic data type  Сопоставление с образцом  Ленивые Вычисления  Неизменяемое состояние 34  Benefits

Algebraic datatype ALGEBRAIC DATATYPE  Тип данных, состоящий из нескольких различимых разновидностей (возможно, составных) термов (значений).  Алгебраические типы позволяют определять:  типы произведения (кортежи)  типы-суммы.  «сумма произведений» 35

Algebraic datatype ALGEBRAIC DATATYPE  Типы произведения (кортежи) data FileInfo where FileInfo { name::String, accessRights::Int, lastModified::Date } :: FileInfo  Типы – суммы data Color where Red :: Color Orange :: Color 36 Yellow :: Color

Algebraic datatype ПРИМЕР С ДЕРЕВОМ (С++) С++ Haskell struct Tree { data Tree = Leaf Int union { ∣ Node Tree Tree int value; struct { struct Tree *left; struct Tree *right; } branches; Или полиморфное определение } data; data Tree a = Leaf a enum { ∣ Node (Tree a) (Tree a) LEAF, NODE } selector; 37 };

Algebraic datatype ПРИМЕР BILLINGINFO (JAVA) Java public class BillingInfo { public static final BillingInfo CreditCard (String number, String holder, String[] address) { return new CreditCard(number, holder, address); } public static final BillingInfo CashOnDelivery () { return new CashOnDelivery(); } public static final BillingInfo Invoice(String customerId) { return new Invoice(customerId); } public static class CreditCard extends BillingInfo { ... public CreditCard(String number, String holder, String[] address) { ... } } public static class CashOnDelivery extends BillingInfo { } public static class Invoice extends BillingInfo { ... public Invoice(String customerId) { ... } 38 } }

Algebraic datatype ПРИМЕР BILLINGINFO (SCALA & HASKELL) Scala Haskell abstract class BillingInfo type Number = String type Holder = String case class CreditCard( type CustomerID = String val number: String, type Address = [String] val holder: String, val address: Array[String]) extends BillingInfo data BillingInfo = CreditCard Number Holder Address case class CashOnDelivery | CashOnDelivery extends BillingInfo | Invoice CustomerID case class Invoice( val customerId: String) extends BillingInfo 39

Algebraic datatype ALGEBRAIC DATATYPE  Конструкторы алгебраического типа T могут упоминать не только те типовые переменные, по которым параметризован тип T.  Типы результатов веток в определении параметризованного алгебраического типа могут различаться. data Hash k v where Hash { hash::k->h, equal::k->k->Bool, table::Array h [(k,v)]} 40

Сопоставление с образцом СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ 41

Сопоставление с образцом GOOGLE TRANSLATE API GET https://www.googleapis.com/language/translate/v2?key=INSERT-YOUR-KEY& Hello%20world JSON { "data": { "translations": [ { "translatedText": "Hallo Welt" } ] } } Как я буду разбирать “это” в Java: 42

Сопоставление с образцом GOOGLE TRANSLATE API (JAVA) protected void processTranslation (JSONObject json) { Map data = (Map) json.get("data"); if (data == null) { return null; } List translations = (List) data.get("translations"); if (translations == null || translations.size() == 0) { return null; } Map o = (Map) translations.get(0); if (o == null) { return null; } String text = (String) o.get("translatedText"); 43 . . . processing . . . }

Сопоставление с образцом КАК Я БЫ ХОТЕЛ protected void processTranslation (JSONObject match { "data": { "translations": [ { "translatedText": text } ] } }) { . . . processing . . . } 44

Сопоставление с образцом СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ  Сопоставление формы структуры данных с формой образца и заполнение переменных-«дырок» в образце значениями в соответствующих местах структуры данных. 45

Сопоставление с образцом СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ В HASKELL zip xs [] = [] zip [] xs = [] zip (x:xs) (y:ys) = (x,y):zip xs ys > zip [1,2,3] [4,5,6] [(1,4),(2,5),(3,6)] 46

Сопоставление с образцом КОНЕЧНЫЙ АВТОМАТ ДЛЯ ПОДСЧЕТА СЛОВ countWords s = space 0 s where space n [] = n space n (’ ’:rest) = space n rest space n (c:rest) = word (n+1) rest word n [] = n word n (’ ’:rest) = space n rest 47 word n (c:rest) = word n rest

Сопоставление с образцом СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ В SCALA sealed trait Tree case object Empty extends Tree case class Leaf (n: Int) extends Tree case class Node (l: Tree, r: Tree) extends Tree . . . def depth(t: Tree): Int = t match { case Empty => 0 case Leaf(n) => 1 case Node(l, r) => 1 + max(depth(l), depth(r)) } 48

Ленивые Вычисления ЛЕНИВЫЕ ВЫЧИСЛЕНИЯ 49

Ленивые Вычисления ОТЛОЖЕННЫЕ (ЛЕНИВЫЕ) ВЫЧИСЛЕНИЯ  Концепция, согласно которой вычисления следует откладывать до тех пор, пока не понадобится их результат.  Ленивые вычисления позволяют сократить общий объём вычислений за счёт тех вычислений, результаты которых не будут использованы. 50

Ленивые Вычисления МЕХАНИЗМЫ ВЫЗОВА ФУНКЦИИ x = f(exp)  Вызов по значению  Вычисляем exp, подставляем результат в f  Вызов по текстовой замене  без замены переменных для устранения конфликта имен  Вызов по имени  с обходом конфликта имен с помощью переименования, но с повторным вычислением выражения  Вызов по необходимости  Вызов по имени + мемоизация 51

Ленивые Вычисления ЛЕНИВЫЕ ВЫЧИСЛЕНИЯ  Примерами нестрогих вычислений в императивных языках могут быть операции && и ||. boolean res = findFist() || findSecond() 52

Ленивые Вычисления БЕСКОНЕЧНЫЕ СТРУКТУРЫ :) бесконечная последовательность единичек ones = 1 : ones numsFrom, которая получает один аргумент — целое число n — и возвращает список всех целых чисел, которые больше либо равны n numsFrom n = n : numsFrom (n + 1)  Ленивое определение структур fib = 1:1:[ a+b | (a,b) <- zip fib (tail fib)] 53

Programming / Practice / Data structure DATA STRUCTURE & FOLDING  Data structure  Вместо изменения структуры данных можно формировать новую структуру, немного отличающуюся от старой.  Folding  Вычисление снизу вверх «по индукции», применяющее в каждом узле структуры данных оператор, соответствующий данному типу узла, к содержимому узла и результатам для его подузлов.  Структурная рекурсия (индукция)  Рекурсия, при которой аргумент рекурсивного вызова в каком-то смысле строго меньше аргумента 54 исходного.

PROGRAMMING: BENEFITS  Чистота  Easy Concurrent Programming  λ-исчисление  Формальность  Доказуемость  Выразительность (композиция)  Скорость разработки  Ленивость …  Cкорость выполнения 55

Benefits ЧИСТОТА  Язык программирования является чистым в том случае, если все функции в программах этого языка являются чистыми.  Чистая функция:  Является детерминированой:  если для одного и того же набора входных значений она возвращает одинаковый результат.  Не обладает побочными эффектами:  не может изменить значения глобальных переменных;  не может модифицировать переданные в функцию параметры 56

Benefits ВЫРАЗИТЕЛЬНОСТЬ 57

LITERATURE  http://www.google.com  http://ru.wikipedia.org/  http://www.haskell.org  http://fprog.ru/  http://habrahabr.ru/blogs/Haskell/  http://www.rsdn.ru/article/haskel  http://learnyouahaskell.com 58

ПОЧЕМУ “НИКТО” НЕ Summary ИСПОЛЬЗОВАЛ ФУНКЦИОНАЛЬНЫЕ ЯЗЫКИ  Совместимость с другими языками  Поддержка языка (как инструмента)  Инструментальные средства  Обучение  Популярность  Библиотеки  Мобильность (переносимость)  Возможности упаковки  Эффективность 59

Summary ГДЕ СЕЙЧАС ИСПОЛЬЗУЕТСЯ ФП?  Mainstream языки программирования:  C# 3.0, следующий стандарт C++  Java.next (Clojure, Groovy, JRuby, Scala)  LINQ  XSLT  Приложения  AutoCAD  emacs (LISP)  HeVeA 60

Характерные черты функциональных языков программирования

More Related Content

What's hot

Similar to Характерные черты функциональных языков программирования

Характерные черты функциональных языков программирования

Editor's Notes