那些 Functional Programming 教我的事

  • Published on
    12-Sep-2014

  • View
    16.760

  • Download
    0

DESCRIPTION

OSDC.TW 2012

Transcript

  • Functional Programming

    ihower@gmail.com2012/4/15

    OSDC.TW

    Sunday, April 15, 12

  • About Me

    a.k.a. ihower Twitter: @ihower Ruby Scala Ruby on Rails

    Sunday, April 15, 12

  • Agenda

    1. FP? 2. FP?

    Sunday, April 15, 12

  • Part1:

    Functional Programming

    Sunday, April 15, 12

  • Moores Law Ending

    Sunday, April 15, 12

  • Single-Threading cant scale!

    4 Cores

    Sunday, April 15, 12

  • Horizontal scalingQ: Concurrency Ready ?

    Sunday, April 15, 12

  • Multithreading ProgramDemo

    Example from: What All Rubyist Should Know About Threads (Jim Weirich, RubyConf 2008)Sunday, April 15, 12

  • Thread-safe (1)

    Synchronize

    Sunday, April 15, 12

  • Thread safe (2)

    Atomic

    Sunday, April 15, 12

  • Thread safe (3)

    Deadlock

    Sunday, April 15, 12

  • Thread safe (4)

    Library (1)~(3)

    Sunday, April 15, 12

  • ...

    Synchronized blocking threads thread :(

    Sunday, April 15, 12

  • Multi-threading Programing is Hard

    Sunday, April 15, 12

  • Hard to program

    Sunday, April 15, 12

  • Hard to test

    Sunday, April 15, 12

  • Mutable shared state

    Sunday, April 15, 12

  • Mutable

    Sunday, April 15, 12

  • Mutable Synchronize

    !!

    Sunday, April 15, 12

  • Functional ProgramingCPU50

    Sunday, April 15, 12

  • (Wikipedia)In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state.

    Sunday, April 15, 12

  • (Wikipedia)In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state.

    Sunday, April 15, 12

  • Functional Language

    Concurrency program

    Sunday, April 15, 12

  • Functional Language?

    Sunday, April 15, 12

  • Erlang

    Ericsson Functional Language No mutable variable and side effects For distributed, reliable, soft real-time

    highly concurrent systems.

    Use the Actor model of concurrency

    Sunday, April 15, 12

  • Erlang

    Facebook chat Github RabbitMQ NoSQL CouchDB, Riak, Membase

    Sunday, April 15, 12

  • Clojure

    Lisp-like functional language JVM Use STM (Software transactional memory) for concurrency ACI (Atomicity, Consistent, Isolation)

    Sunday, April 15, 12

  • Hybrid: Object-orient and functional JVM Use Akka (Actor and STM) for concurrency

    Sunday, April 15, 12

  • Twitter LinkedIn

    Scala

    Sunday, April 15, 12

  • F#

    Microsofts functional language .NET OCaml-like

    Sunday, April 15, 12

  • Haskell

    Pure Functional language

    Haskell Curry

    Sunday, April 15, 12

  • Concurrency OO Concurrency Functional Programing Concurrency

    Programming

    Sunday, April 15, 12

  • Part2:

    FP

    Sunday, April 15, 12

  • 1. Avoiding Mutable State 2. Recursion 3. Higher-Order Functions 4. Function Composition 5. Lazy Evaluation 6. Pattern Matching

    Sunday, April 15, 12

  • 1. Mutable State

    Sunday, April 15, 12

  • FP immutable

    ** Erlang R15B **X = 1234.

    X = 5678.** exception error: no match of right hand side value 5678

    Sunday, April 15, 12

  • Scala val

    val a = 1234

    a = 5678:8: error: reassignment to val

    var b = 1234b = 56785678

    Sunday, April 15, 12

  • Persistent data structure

    Immutable Map, Hash, Set Produce new values by sharing structure

    with existing values

    Sunday, April 15, 12

  • Why need Immutable data structure?

    No side-effects !! Copying overhead

    Sunday, April 15, 12

  • Linked ListList

    Sunday, April 15, 12

  • Tree ()Tree

    Sunday, April 15, 12

  • Scalas collection Immutable List Map Vector Set Mutable import scala.collection.mutable.LinkedList scala.collection.mutable.Map scala.collection.mutable.ArrayBuffer scala.collection.mutable.Set

    Sunday, April 15, 12

  • 2. Recursion?

    Sunday, April 15, 12

  • Non-recursion result

    def factorial(n) result = 1 # result for i in 2..n result = i * result end return resultend

    Sunday, April 15, 12

  • Recursion recursion

    def factorial(n) if (n==1) return 1 else return n * factorial(n-1) endend

    Sunday, April 15, 12

  • Recursion? call stack ?

    > factorial(10000)# SystemStackError: stack level too deep

    Sunday, April 15, 12

  • Tail-call optimizationFP loop (:Scala)

    @tailrec def factorial(acc: Int, n: Int): Int = { if (n

  • 3. Higher-Order function

    Sunday, April 15, 12

  • Function is first-class value ( JavaScript )

    var sayHello = function(){ alert("Hello World!");};

    sayHello();

    Sunday, April 15, 12

  • Higher-order function

    function function function function

    Sunday, April 15, 12

  • JavaScript (ECMA5) forEach [2,3,5,6].forEach( function(item){ console.log(item); });

    // 2// 3// 5// 6

    Sunday, April 15, 12

  • Callback method( Java Anonymous inner class)

    final Button button = new Button(this);button.setOnClickListener(

    );

    new View.OnClickListener() { public void onClick(View v) { "Hello, World!"}}

    Sunday, April 15, 12

  • JDK 8 lambda

    final Button button = new Button(this);button.setOnClickListener( );

    (View v) -> { "Hello" }

    Sunday, April 15, 12

  • Combinator Functions

    Collection filter map fold

    Sunday, April 15, 12

  • Tickets 1000

    val tickets = List("a","b", "c")

    def getPrice(ticket : String) = { Map( "a" -> 1100, "b" -> 900, "c" -> 800 ). get(ticket).getOrElse(0)}

    def Less1000(price: Int) = price < 1000

    def pickHighPriced(price1: Int, price2: Int) = { if (price1 > price2) price1 else price2}

    Sunday, April 15, 12

  • import scala.collection.mutable.ArrayBuffer//val prices = new ArrayBuffer[Int]for(ticket
  • Functional Style

    val highestPrice = tickets.map{ x => getPrice(x) } .filter{ x => Less1000(x) } .reduce{ (x,y) => pickHighPriced(x,y) }[a, b,c]

    Sunday, April 15, 12

  • Functional Style

    val highestPrice = tickets.map{ x => getPrice(x) } .filter{ x => Less1000(x) } .reduce{ (x,y) => pickHighPriced(x,y) }

    [1100, 900,800]

    Sunday, April 15, 12

  • Functional Style

    val highestPrice = tickets.map{ x => getPrice(x) } .filter{ x => Less1000(x) } .reduce{ (x,y) => pickHighPriced(x,y) }

    [900,800]

    Sunday, April 15, 12

  • Functional Style

    val highestPrice = tickets.map{ x => getPrice(x) } .filter{ x => Less1000(x) } .reduce{ (x,y) => pickHighPriced(x,y) }

    900

    Sunday, April 15, 12

  • Scala _

    val highestPrice = tickets.map{ getPrice(_) } .filter{ Less1000(_) } .reduce{ pickHighPriced(_,_) }

    Sunday, April 15, 12

  • val higtestPrice = tickets.map.getPrice.filter.Less1000.reduce.pickHighPriced

    Sunday, April 15, 12

  • Scala method call

    val higtestPrice = tickets map getPrice filter Less1000 reduce pickHighPriced

    Sunday, April 15, 12

  • State transformation Mutate Collection

    Sunday, April 15, 12

  • 4. Function Composition

    Sunday, April 15, 12

  • Partial Functions Function

    Sunday, April 15, 12

  • Haskelladd x y = x + yadd 2 3# 5

    addTwo = add 2addTwo 3# 5

    Sunday, April 15, 12

  • Scala _ wildcard

    def add(x:Int, y:Int) = x + y

    val addTwo = add(2, _:Int)

    addTwo(3)//5

    Sunday, April 15, 12

  • Curryingnamed after Haskell Curry

    N function N function

    Sunday, April 15, 12

  • Haskell function Curried

    max 4 5

    # (max 4) 5

    # maxmax :: Ord a => a -> (a -> a)max 4 :: (Ord a, Num a) => a -> a

    Sunday, April 15, 12

  • Haskell function Curried

    max 4 5

    # (max 4) 5

    # maxmax :: Ord a => a -> (a -> a)max 4 :: (Ord a, Num a) => a -> a

    (max 4) Partial Function

    5

    Sunday, April 15, 12

  • Scala Curried

    def sum(a: Int, b: Int) = a + bsum(2, 3) // 5

    def curriedSum(a: Int)(b: Int) = a * bcurriedSum(2)(3) // 5

    curriedSum(2) Partial

    Function3

    Sunday, April 15, 12

  • Compose Function

    f(g(x)) = (fg)(x)

    Sunday, April 15, 12

  • Haskell

    reverse( sort [2,5,1,10,5] )

    # -- the '.' operator is used to compose functionsreverseSort = reverse . sortreverseSort [2,5,1,10,5]

    Sunday, April 15, 12

  • JavaScript compose

    function compose(f, g) { return function(x) { return f(g(x)); }}

    Sunday, April 15, 12

  • 5. Lazy evaluation

    list

    Sunday, April 15, 12

  • Haskell is lazy functional language

    cycle [1,2,3]# [1,2,3, 1,2,3, 1,2,3, 1,2,3, 1,2,3, 1,2,3, 1,2,3,....

    take 10 (cycle [1,2,3])# [1,2,3,1,2,3,1,2,3,1]"

    Sunday, April 15, 12

  • Scalas lazy valuseful for lazy initialization

    val a = { println("evaluating A"); "A" }// evaluating A// a: java.lang.String = A

    lazy val b = { println("evaluating B"); "B" }// b: java.lang.String =

    Sunday, April 15, 12

  • Scala Stream (lazy list)Scala List Lazy

    def from(n: Int): Stream[Int] = Stream.cons( n, from(n+1) )lazy val odds = from(0).filter(_ % 2 == 1)

    odds.take(10).print // 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, empty

    Sunday, April 15, 12

  • Ruby Enumerable::Lazy Lazy Combinator

    functions

    require 'prime'

    Prime.to_a # ...

    Prime.take(10).to_a# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    Prime.lazy.select{ |x| x % 4 == 3 }.take(10).to_a# => [3, 7, 11, 19, 23, 31, 43, 47, 59, 67]

    Sunday, April 15, 12

  • 6. Pattern Matching

    expression

    Sunday, April 15, 12

  • Erlang

    X."1: variable 'X' is unbound"

    X = 2.

    {X, Y} = {1, 2}."exception error: no match of right hand side value {1,2}"

    {X, Y} = {2, 3}.{2,3}

    Y." Y 3"

    Sunday, April 15, 12

  • Erlang List

    [H|T] = [1,2,3,4,5].

    H. "1"T. "[2,3,4,5]"

    Sunday, April 15, 12

  • Erlang (cont.) List

    [A,B,C|T] = [1,2,3,4,5].A. "1"B. "2"C. "3"T. "[4,5]"

    Sunday, April 15, 12

  • Scala match

    import scala.util.Random

    val randomInt = new Random().nextInt(10)

    randomInt match { case 7 => println("lucky seven") case otherNumber => println("get " + otherNumber)}

    Sunday, April 15, 12

  • Scala Type

    val items = List(1, "foo", 3.5)

    for (item println("got an Integer: " + i) case s: String => println("got a String: " + s) case f: Double => println("got a Double: " + f) case other => println("got others: " + other) }}

    Sunday, April 15, 12

  • Scala Guard

    val t1 = ("A", "B")val t2 = ("C", "D")val t3 = ("E", "F")

    for( tuple println("Ctuple") case (one, two) => println("blah") }}

    // blah// Got tuple starting with C// blah

    Sunday, April 15, 12

  • Sunday, April 15, 12

  • Functional Style

    immutability Function Side-effects side-effects (IO)

    FP Style Mutable State Concurrency

    Sunday, April 15, 12

  • FP? Functional Programing

    Java FP Style Scripting (Ruby/Python/JavaScript)

    FP

    Avoid Mutable State No-side Effects Function Functional

    FP Lisp, Haskell, Scala, F#

    Sunday, April 15, 12

  • Sunday, April 15, 12

  • Thanks.

    @godfat (Haskell) @idryman (Lisp )

    FP FP user group :-)

    Sunday, April 15, 12

Recommended

View more >