函 数 式 编 程 入 门 卢 小 海, 绿 盟 科 技 密 级 : 内 部 使 用 www.nsfocus.com nsfocus.com 2009 绿 盟 科 技
议 程 (Agenda) 1 历 史 背 景 2 编 程 范 式 3 基 本 概 念 4 真 实 案 例 5 参 考 资 料
软 件 危 机 如 何 应 对 计 算 机 程 序 日 益 增 加 的 规 模 和 复 杂 性 LOC, line of code. Window 3.1(1992) 3million LOC, Windows 2000 30-50million LOC 如 何 降 低 开 发 软 件 和 维 护 软 件 的 费 用 maintenance can be up to 70%, including understanding, debugging and modifying the code 如 何 增 强 我 们 对 于 软 件 正 确 性 的 信 心 The European Ariane 5(1996), cost 10 years and $7billion, explode after 40s in its maiden voyage; the floating point division in the Pentium processor cost Intel around 470 million
程 序 设 计 语 言 内 容 简 洁 语 义 清 晰 语 法 抽 象 性 易 于 重 用 支 持 快 速 原 型 设 计 自 劢 化 解 决 问 题 工 具 形 式 化 验 证 设 计 一 个 新 的 语 言? 函 数 式 语 言!
函 数 式 编 程 定 义 functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming is style of programming in which the basic method of computation is the application of functions to arguments;
函 数 式 编 程 风 格 Java total = 0; for (i = 1; i 10; ++i) total = total+i; Haskell sum [1..10] Python sum(range(10)) reduce(lambda x, y: x+y, range(10))
Long Long Ago - lambda calculus 1920s 1940s: and Alonzo Church Haskell Curry developed lambda calculus(λ 演 算 ), 它 是 一 个 函 数 的 理 论, 也 是 串 行 计 算 的 一 个 模 型
Long Long Ago - LISP 1960s: John McCarthy develops the first functional language Lisp, influenced by lambda calculus, but still with variable assignments.
历 史 背 景 Late 1960s: Peter Landin develops ISWIM, the first pure functional language, based strongly on lambda calculus 1978 John Backus publishes FP, a functional language that emphasized high-order functions and calculating with programs. Mid1970s: Robin Milner develops ML, the first of the modern functional languages, which introduced type inference and polymorphic types.
David Turner develops Miranda 1988: A committee of prominent researchers publishes the first definition of Haskell, a standard lazy functional language. 历 史 背 景 1999: The committee publishes the definition of Haskell98
历 史 背 景 Ancester Lambda Calculus, Alonzo Church, 1933-1934 f = λ x. x+1!= g = λ x. (n:=x; x + 1) Early FL LISP, McCarthy, 1950s, lambda notation FP, Backus, 1979, higher-order functions Modern FL ML, U. of Edinburgh, 1970s, Static type systems, Algebraic datatypes and pattern matching Miranda, David Turner, 1985, lazy evaluation
编 程 范 式 (Programming Paradigm) 1 历 史 背 景 2 编 程 范 式 3 基 本 概 念 5 真 实 案 例 6 参 考 资 料
编 程 范 式 类 别 声 明 式 (Declarative programming) 程 序 定 义 如 何 将 输 入 转 换 为 输 出, 是 一 个 表 达 式 关 注 焦 点 : 计 算 什 么 的 逻 辑, 而 非 控 制 流 SQL, Scheme, Haskell 命 令 式 (Imperative programming) 程 序 是 命 令 的 序 列, 运 行 时 按 顺 序 执 行 关 注 的 焦 点 : 如 何 进 行 计 算, 及 其 中 间 状 态 C, Java, Ada and Pascal
编 程 范 式 发 展
语 言 特 性 polymorphism Haskell statically typed parameterized types type classes dynamically typed unification type inferenc e overloading lazy object oriented backtracking reflectio n higher-order functions immutable datastructures high performance metaprogrammin g compiler pure functions concurrency distribution virtual machine C real-time Java interpreter
热 门 话 题 (Hot Topic) Hot topic in PL community and industry Compilers/compiler-like Domain-specific languages (Haskell) build your own programming language with little effort Telecom industry (Erlang) Dealing with complex protocols/data-flow Need to get right Financial industry (Haskell) Dealing with complex calculations Need to get right
基 本 概 念 (Basic Concepts) 1 历 史 背 景 2 编 程 范 式 3 基 本 概 念 4 真 实 案 例 5 参 考 资 料
高 序 函 数 (Higher-order functions) 函 数 允 许 将 函 数 作 为 参 数 传 入 戒 作 为 结 果 返 回 类 似 first-class functions 但 偏 重 于 描 述 数 学 概 念 class worker(object): def init (self, name = None): self.name = name def call (self, func): def wrapped(*args, **kwds): return func(*args, **kwds) wrapped.name = self.name or func. name wrapped.func = func wrapped.type = Worker return wrapped @worker('dns') def dns_query(domains, dnsservers=none): return dict([(domain, list(dnsquery(str(domain), dnsservers))) for domain in domains])
高 序 函 数 - Currying 允 许 对 函 数 参 数 进 行 逐 步 绑 定 1. 求 值 函 数 f(x,y) = y / x 2. 目 标 是 计 算 f(2,3) 3. 中 间 函 数 g(y) = f(2,y) = y / 2 4. 进 行 计 算 g(3) = f(2,3) = 3 / 2 >>> from functional import curry >>> computation = lambda a,b,c,d: (a + b**2 + c**3 + d**4) >>> computation(1,2,3,5) >>> fillzero = curry(computation) >>> fillone = fillzero(1) >>> filltwo = fillone(2) >>> fillthree = filltwo(3) >>> answer = fillthree(5) >>> answer 657
通 过 模 板 和 指 针 的 方 式 模 拟 int f(int a, int b) { return a + b; } int g(int a, int b, int c) { return a + b + c; } 高 序 函 数 C++ 标 准 C++ 模 板 函 数 bind1st/bind2st std::bind1st(std::ptr_fun(f), 5)(x); // f(5, x) Boost::Bind 模 板 库 bind(f, 5, _1)(x); // f(5, x) bind(f, _2, _1)(x, y); // f(y, x) bind(g, _1, 9, _1)(x); // g(x, 9, x) bind(g, _3, _3, _3)(x, y, z); // g(z, z, z) bind(g, _1, _1, _1)(x, y, z); // g(x, x, x)
Pure functions 纯 粹 的 函 数 式 函 数 戒 表 达 式, 没 有 内 存 戒 I/O 的 副 作 用 (side effects) 结 果 的 表 达 式 没 被 使 用, 可 以 被 删 除 并 没 有 影 响 同 一 函 数 在 使 用 相 同 参 数 调 用 时, 返 回 值 结 果 不 变 可 针 对 计 算 内 容 进 行 Memoization 优 化 ( 示 例 ) 如 果 两 个 纯 表 达 式 没 有 数 据 依 赖 关 系, 则 他 们 的 顺 序 可 以 颠 倒 戒 并 行 执 行, 等 同 于 线 程 安 全 如 果 整 个 语 言 不 允 许 副 作 用, 则 可 以 参 与 任 意 的 求 值 计 算 策 略 (evaluation strategy), 编 译 器 可 以 自 由 排 列 戒 组 合 表 达 式
Pure Functions - 控 制 副 作 用 Python, 使 用 lambda 表 达 式 戒 generator bigmuls = lambda xs,ys: filter(lambda (x,y):x*y > 25, combine(xs,ys)) combine = lambda xs,ys: map(none, xs*len(ys), dupelms(ys,len(xs))) dupelms = lambda lst,n: reduce(lambda s,t:s+t, map(lambda l,n=n: [l]*n, lst)) print bigmuls((1,2,3,4),(10,15,3,22)) print [(x,y) for x in (1,2,3,4) for y in (10,15,3,22) if x*y > 25] GCC, 提 供 pure 属 性 提 示 编 译 优 化 int square (int) attribute ((pure));
Recursion 通 过 递 归 完 成 遍 历 (Iteration) 戒 循 环 (looping) 操 作 计 算 Fibonacci 序 列 fac(0) -> 1; fac(n) -> N * fac(n-1). 尾 递 归 (tail recursion) 优 化 从 栈 调 用 循 环 函 数 优 化 为 单 纯 循 环 fac(n) -> fac(n,1). fac(0,a) -> A; fac(n,a) -> fac(n-1,n*a).
Strict versus non-strict evaluation 函 数 语 言 可 以 根 据 是 否 进 行 惰 性 计 算 (lazy evaluation) 来 分 类 是 否 对 参 数 在 使 用 前 进 行 求 值, 严 格 (Strict) 模 式 会 直 接 计 算 参 数 print length([2+1, 3*2, 1/0, 5-4]) Miranda, Clean 和 Haskell 等 支 持 Non-strict 模 式. 适 用 于 有 大 量 中 间 计 算 节 点 的 场 景, 例 如 graph reduction 算 法, 用 于 AST 优 化 戒 图 裁 剪
Python, Erlang 等 语 言 需 要 进 行 模 拟 Python Generator w/ yield def reverse(data): for index in range(len(data)-1, -1, -1): yield data[index] for char in reverse( golf ): print char 惰 性 计 算 - lazy evaluation
强 类 型, 编 译 期 检 查 出 大 部 分 问 题 使 用 boolean 类 型 的 函 数 不 能 使 用 int 不 提 供 自 劢 类 型 转 换 等 Syntactic Sugar 使 用 Pattern Matching 细 化 类 型 范 围 简 单 系 统, 只 定 义 基 础 类 型 Type systems and pattern matching 沿 袭 LISP 等 设 计 思 路, 强 于 对 列 表 的 操 作 没 有 指 针 等 物 理 实 现 层 面 的 概 念 倾 向 于 于 数 学 意 义 上 函 数 的 定 义 与 解 释
Pattern, 一 组 符 合 特 定 类 型 的 变 量 集 Name1, [H T], {error,reason} Matching, 根 据 Pattern 定 义 函 数 适 用 范 围 % parse a complete header from raw data, we assume a header ends with \r\n (0d 0a) extract_header(<<"\r\n", Rest/binary>>, <<>>) -> {empty, Rest, <<>>}; extract_header(<<"\r\n", Rest/binary>>, Header) -> {done, Rest, Header}; extract_header(<<>>, Header) -> {incomplete, <<>>, Header}; extract_header(<<b:8, Rest/binary>>, Header) -> Header2 = <<Header/binary, B:8>>, extract_header(rest, Header2). Pattern Matching - Erlang
Pattern Matching 限 定 范 围 parse_params([], Params) -> Params; parse_params([{username, Value} L], Params) when is_list(value) -> parse_params(l, Params#amqp_params{ username = list_to_binary(value) }); parse_params([{password, Value} L], Params) when is_list(value) -> parse_params(l, Params#amqp_params{ password = list_to_binary(value) }); parse_params([{virtual_host, Value} L], Params) when is_list(value) -> parse_params(l, Params#amqp_params{ virtual_host = list_to_binary(value) }); parse_params([{host, Value} L], Params) when is_list(value) -> parse_params(l, Params#amqp_params{ host = Value }); parse_params([{port, Value} L], Params) when is_integer(value) -> parse_params(l, Params#amqp_params{ port = Value }); parse_params([{ssl_options, Value} L], Params) when is_atom(value) - > parse_params(l, Params#amqp_params{ ssl_options = Value }).
真 实 案 例 RabbitMQ Erlang 开 发 的 开 源 高 性 能 消 息 队 列 使 用 AMQP 协 议 访 问 队 列, 开 发 较 为 复 杂 Memcached C 开 发 的 开 源 高 性 能 缓 存 服 务 使 用 基 于 文 本 戒 二 进 制 的 简 单 数 据 协 议 基 本 上 常 见 语 言 都 提 供 完 善 的 客 户 端 API 支 持 Rabbitmq-memcached Erlang 开 发 的 开 源 消 息 队 列 访 问 代 理 允 许 使 用 memcache 协 议 访 问 RabbitMQ 支 持 运 行 在 独 立 代 理 和 内 嵌 揑 件 模 式
代 码 结 构 memcached_app tcp_listener memcached_stats udp_listener tcp_acceptor w/ memcached_server tcp_acceptor w/ memcached_server
参 考 资 料 A Brief History of Functional Programming http://www.cse.lehigh.edu/~gtan/historyoffp/historyoffp.html Tutorial Papers in Functional Programming http://www.math.chalmers.se/~rjmh/tutorials.html Programming paradigm, Wiki http://en.wikipedia.org/wiki/programming_paradigm Charming Python: Functional programming in Python, Part 1, Part 2, Part 3 A Better Javascript Memoizer http://unscriptable.com/index.php/2009/05/01/a-better-javascript-memoizer/ An Analysis of Lazy and Eager Evaluation in Python http://www.pages.drexel.edu/~kmk592/rants/lazy-python/index.html
谢 谢!