函数式编程(一)

提纲

  • 引子
  • 函数式编程特点
  • Clojure简单语法
  • Clojure与Java
  • 高阶函数

多线程容易遇到的问题

一、逸出

1
2
3
4
5
6
7
8
9
10
11
public class Manager {
private List<Player> players = new LinkedList<Player>();
private synchronized void addPlayer(Player p) {
players.add(p);
}
public synchronized Iterator<Player> getPlayerIterator() {
return players.iterator();
}
}

虽然所有方法都加了synchronized关键字,但是Iterator逸出了。无法保证对Iterator的操作都是同步的。

二、隐藏的可变状态

1
2
3
4
5
6
7
8
public class DateParser {
private final DateFormat format = new SimpleDateFormat("yyyy-MM-dd");
public Date parse(String s) throws ParseException {
return format.parse(s);
}
}

jdk中的说明:

Synchronization
Date formats are not synchronized. It is recommended to create separate format instances for each thread. If multiple threads access a format concurrently, it must be synchronized externally.

原因:SimpleDateFormat中有隐藏的可变状态。

函数式编程中有一些并发的模式、框架、以及一些延迟、异步等编程模式

  • Actor (Erlang, Scala)
  • STM(software transactional memory) (clojure)
  • 响应式编程(RxJava)
  • ……
    这些都和函数式编程相关

命令式与函数式

  • 命令式
    • 程序设计的主流是命令式的,计算基于一组基本操作,在一个环境里进行。操作效果是改变环境的状态,体现在所创建和修改的状态中。
    • 层次较低,更接近硬件,可能更高效;关注更多细节,更加复杂,容易出错。
    • 1
  • 函数式
    • 程序设计把程序设计看成是数据的变换,程序的行为就是对数据的一系列交换。
    • 层次更高,更加抽象,隐藏细节,可能效率低
    • 2

函数式语言

一些函数式语言

  • Lisp,Scheme
  • Haskell
  • clojure, Erlang
  • scala? Python? Ruby? js? Java?

什么是函数式编程

  • 函数是一等公民,函数与其他类型一样,可以作为参数传递,可以作为其他函数的返回值
  • 只用表达式(expression),不用语句(statement)
  • 没有副作用,是指一个函数存在的意义就是他的返回值,而不会修改外部变量的值,不存在状态变量,没有赋值语句(for循环,while循环怎么办)
  • 引用透明,是指不依赖于外部环境。即:一个函数,如果参数相同,一定能得到相同的返回值。
    完全符合函数式特性的语言有哪些?

函数式编程的优点

  1. 代码简洁,开发快速
    Paul Graham在《黑客与画家》一书中写道:同样功能的程序,极端情况下,Lisp代码的长度可能是C代码的二十分之一。

  2. 接近自然语言,易于理解
    表达式(1 + 2) * 3 - 4,写成函数式编程的写法:
    subtract(multiply(add(1,2), 3), 4) ->
    add(1,2).multiply(3).subtract(4)

  3. 更方便的代码管理
    函数式编程不依赖、也不会改变外界的状态,只要给定输入参数,返回的结果必定相同。因此,每一个函数都可以被看做独立单元,很有利于进行单元测试(unit testing)和除错(debugging),以及模块化组合。

  4. 易于”并发编程”
    函数式编程不需要考虑”死锁”(deadlock),因为它不修改变量,所以根本不存在”锁”线程的问题。不必担心一个线程的数据,被另一个线程修改,所以可以很放心地把工作分摊到多个线程,部署”并发编程”(concurrency)。

  5. 代码的热升级
    函数式编程没有副作用,只要保证接口不变,内部实现是外部无关的。所以,可以在运行状态下直接升级代码,不需要重启,也不需要停机。Erlang语言早就证明了这一点,它是瑞典爱立信公司为了管理电话系统而开发的,电话系统的升级当然是不能停机的。

语言的三种机制

  • 基本的表达形式
  • 组合的方法
  • 抽象的方法

clojure简单语法基础

尽量只涉及到简单的语法,能说明问题即可。btw,实时计算框架Storm就是拿clojure写的。

  • 数字
    • 236
  • 简单算术表达式
    • (+ 1 2)
    • (* 1 2 3 4)
  • 表达式嵌套
    • (* (* 1 3) (- 5 2) 3)
  • 对象命名
    • (def size 10)
    • (* size 3)
  • 更复杂的表达式
    • (def num1 (+ 1 2))
    • (def num2 (* num1 2))
  • 过程定义
    • (defn square [x] (* x x))
    • (square 3)
    • (def square2 (fn [x] (* x x))),defn是语法糖,fn创建函数,可以看做是lambda表达式
  • 条件
    • (defn zero? [x] (if (= x 0) true false))
    • (defn abs [x] (cond (> 0 x) x (= 0 x) 0 (< 0 x) (- x)))
  • 集合
    • '(1 2 3)
    • (vector 1 2 3)
    • (def stooges ["Moe" "Larry" "Curly" "Shemp"])
    • (first stooges)
    • (nth stooges 2)

示例1:牛顿法求平方根

牛顿法采用猜测并不断改进猜测值的方式,一直做到满意为止。例如选 初始猜测值 1 求 2 的平方根(改进猜测值的方法是求平均)
|猜测|相除|平均|
|—-|—|—-|
|1| (2/1) = 2| ((2 + 1)/2) = 1.5|
|1.5| (2/1.5) = 1.3333| ((1.3333 + 1.5)/2) = 1.4167|
|1.4167| (2/1.4167) = 1.4118| ((1.4167 + 1.4118)/2) = 1.4142|
| 1.4142|…..|…..|

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Sqrt {
public static double THRESHOLD = 0.0001;
public static double GUESS = 1.0;
public static boolean goodEnough(double guess, double x) {
return Math.abs(guess*guess - x) < THRESHOLD;
}
public static double average(double x, double y) {
return (x + y) / 2;
}
public static double improve(double guess, double x) {
return average(guess, x/guess);
}
/**
* iter begin
*/
public static double sqrtIter(double guess, double x) {
return goodEnough(guess, x) ? guess : sqrtIter(improve(guess, x), x);
}
public static double sqrt1(double x) {
return sqrtIter(GUESS, x);
}
/*
* iter end
*/
public static double sqrt2(double x) {
double guess = GUESS;
while(!goodEnough(guess, x)) {
guess = improve(guess, x);
}
return guess;
}
public static void main(String[] args) {
System.out.println(Sqrt.sqrt1(2));
System.out.println(Sqrt.sqrt2(2));
}
}

sqrt1和sqrt2的区别是什么?

clojure实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
(def init-guess 1.0)
(def threshold 0.0001)
(def mysquare
(fn [x] (* x x)))
(mysquare 3)
(defn good-enough? [guess x]
(< (Math/abs (- (square guess) x)) threshold))
;;(good-enough? 1 1.000001)
(defn average [x y]
(/ (+ x y) 2))
;;(average 2 4)
(defn improve [guess x]
(average guess (/ x guess)))
(defn sqrt-iter [guess x]
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(defn sqrt [x]
(sqrt-iter init-guess x))

目前java和clojure还看不出什么太大的区别

高阶函数

以过程作为参数或返回值的,操作过程的过程称为高阶函数,考虑下面几个过程:

  • a + … + b

    1
    2
    3
    4
    5
    6
    7
    (defn sum-integers [a b]
    (if (> a b)
    0
    (+ a
    (sum-integers (+ a 1) b))))
    (sum-integers 1 10)
  • a^3 + … + b^3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    (defn cube [x]
    (* x x x))
    (defn sum-cubes [a b]
    (if (> a b)
    0
    (+ (cube a)
    (sum-cubes (+ a 1) b))))
    (sum-cubes 1 3)
    ```
    + 1/1*3 + 1/5*7 + 1/9*11 + ...
    ``` clojure
    (defn pi-sum [a b]
    (if (> a b)
    0
    (+ (/ 1.0 (+ a (+ a 2)))
    (pi-sum (+ a 4) b))))
    (pi-sum 1 7)

虽然各过程的细节不同,但它们都是从参数 a 到参数 b,按一定步长, 对依赖于参数 a 的一些项求和,这几个过程有着公共的模式

Clojure高阶函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
;;伪代码
(defn <pname> [a b]
(if (> a b)
0
(+ (<term> a)
(<pname> (<next> a) b))))
;;clojure实现
(defn sum [term a next b]
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))
;;利用sum实现
(defn sum-itegers [a b]
(sum (fn [x] x) a (fn [x] (+ x 1)) b))
(defn sum-cubes [a b]
(sum (fn [x] (* x x x)) a (fn [x] (+ x 1)) b))
(defn pi-sum [a b]
(sum (fn [x] (/ 1.0 (+ x (+ x 2)))) a (fn [x] (+ x 4)) b))

Java和C用什么方法解决类似的问题?
Java:接口;java8中的函数式接口
C:函数指针

Java8实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class SumAccu {
public Double sum(Function<Double,Double> term, Double a, Function<Double,Double> next, Double b) {
if(a > b) {
return 0.0;
}else {
return term.apply(a) + sum(term, next.apply(a), next, b);
}
}
public Double sumIntegers(Double a, Double b) {
return sum((x)->{return x;}, a, (x)->{return x+1;}, b);
}
public Double sumCubes(Double a, Double b) {
return sum((x)->{return Math.pow(x,3);}, a, (x)->{return x+1;}, b);
}
public Double piSum(Double a, Double b) {
return sum((x)->{return 1.0/(x + (x + 2));}, a, (x)->{return x + 4;}, b);
}
public static void main(String[] args) {
SumAccu accu = new SumAccu();
System.out.println(accu.sumIntegers(1.0, 3.0));
System.out.println(accu.sumCubes(1.0, 3.0));
System.out.println(accu.piSum(1.0, 3.0));
}
}

数据变换

map

1
2
3
4
(range 10) ;(0 1 2 3 4 5 6 7 8 9)
(map inc (range 10)) ;(1 2 3 4 5 6 7 8 9 10)
;map如何实现?

filter

1
2
3
(filter even? (range 10)) ;(0 2 4 6 8)
(filter odd? (range 10)) ;(1 3 5 7 9)
(filter #(> % 5) (range 10)) ;(6 7 8 9)

reduce

1
(reduce + 0 (range 1 6))

示例

1
2
3
4
5
(reduce +
0
(filter #(> % 5)
(map #(* 2 %)
(range 10))))

函数式编程异步

Future模型

future函数可以接受一段代码,并在一个单独的线程中执行这段代码。返回一个future对象。

1
2
(def sum (future (+ 1 2 3 4 5)))
(deref sum)

Promise模型

Promise也是异步求值的,但是不会立刻执行

1
2
3
(def meaning-of-life (promise))
(future (println "Meaing is:" @meaning-of-life))
(deliver meaning-of-life 10)

数列求和,并发简单示例

Java实现

1
2
3
4
5
6
7
8
9
public class Accumulator {
public static int sum(int[] numbers) {
int accu = 0;
for(int n : numbers) {
accu = accu + n;
}
return accu;
}
}

Clojure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
;;简单
(defn reduce-sum [numbers]
(reduce (fn [acc x] (+ acc x)) 0 numbers))
;;更简单
(defn sum [numbers]
(reduce + numbers))
;;并发
(require '[clojure.core.reducers :as r])
(defn parallel-sum [numbers]
(r/fold + numbers))
(parallel-sum nums)
;;测试
(def the-nums (into [] (range 0 1000000)))
(time (sum the-nums))
(time (parallel-sum the-nums))