PPT标准模版

Size: px

Start display at page:

Download "PPT标准模版"

囿缺狄
7 years ago
Views:

1 函数式编程入门卢小海, 绿盟科技密级 : 内部使用 nsfocus.com 2009 绿盟科技

2 议程 (Agenda) 1 历史背景 2 编程范式 3 基本概念 4 真实案例 5 参考资料

3 软件危机如何应对计算机程序日益增加的规模和复杂性 LOC, line of code. Window 3.1(1992) 3million LOC, Windows million 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

4 程序设计语言内容简洁语义清晰语法抽象性易于重用支持快速原型设计自劢化解决问题工具形式化验证设计一个新的语言? 函数式语言!

5 函数式编程定义 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;

6 函数式编程风格 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))

7 Long Long Ago - lambda calculus 1920s 1940s: and Alonzo Church Haskell Curry developed lambda calculus(λ 演算 ), 它是一个函数的理论, 也是串行计算的一个模型

8 Long Long Ago - LISP 1960s: John McCarthy develops the first functional language Lisp, influenced by lambda calculus, but still with variable assignments.

9 历史背景 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.

10 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

11 历史背景 Ancester Lambda Calculus, Alonzo Church, 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

12 编程范式 (Programming Paradigm) 1 历史背景 2 编程范式 3 基本概念 5 真实案例 6 参考资料

13 编程范式类别声明式 (Declarative programming) 程序定义如何将输入转换为输出, 是一个表达式关注焦点 : 计算什么的逻辑, 而非控制流 SQL, Scheme, Haskell 命令式 (Imperative programming) 程序是命令的序列, 运行时按顺序执行关注的焦点 : 如何进行计算, 及其中间状态 C, Java, Ada and Pascal

14 编程范式发展

15 语言特性 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

16 热门话题 (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

17 基本概念 (Basic Concepts) 1 历史背景 2 编程范式 3 基本概念 4 真实案例 5 参考资料

18 高序函数 (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 def dns_query(domains, dnsservers=none): return dict([(domain, list(dnsquery(str(domain), dnsservers))) for domain in domains])

19 高序函数 - 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

20 通过模板和指针的方式模拟 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)

21 Pure functions 纯粹的函数式函数戒表达式, 没有内存戒 I/O 的副作用 (side effects) 结果的表达式没被使用, 可以被删除并没有影响同一函数在使用相同参数调用时, 返回值结果不变可针对计算内容进行 Memoization 优化 ( 示例 ) 如果两个纯表达式没有数据依赖关系, 则他们的顺序可以颠倒戒并行执行, 等同于线程安全如果整个语言不允许副作用, 则可以参与任意的求值计算策略 (evaluation strategy), 编译器可以自由排列戒组合表达式

22 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));

23 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).

24 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 优化戒图裁剪

25 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

26 强类型, 编译期检查出大部分问题使用 boolean 类型的函数不能使用 int 不提供自劢类型转换等 Syntactic Sugar 使用 Pattern Matching 细化类型范围简单系统, 只定义基础类型 Type systems and pattern matching 沿袭 LISP 等设计思路, 强于对列表的操作没有指针等物理实现层面的概念倾向于于数学意义上函数的定义与解释

27 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

28 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 }).

29 真实案例 RabbitMQ Erlang 开发的开源高性能消息队列使用 AMQP 协议访问队列, 开发较为复杂 Memcached C 开发的开源高性能缓存服务使用基于文本戒二进制的简单数据协议基本上常见语言都提供完善的客户端 API 支持 Rabbitmq-memcached Erlang 开发的开源消息队列访问代理允许使用 memcache 协议访问 RabbitMQ 支持运行在独立代理和内嵌揑件模式

30 代码结构 memcached_app tcp_listener memcached_stats udp_listener tcp_acceptor w/ memcached_server tcp_acceptor w/ memcached_server

31 参考资料 A Brief History of Functional Programming Tutorial Papers in Functional Programming Programming paradigm, Wiki Charming Python: Functional programming in Python, Part 1, Part 2, Part 3 A Better Javascript Memoizer An Analysis of Lazy and Eager Evaluation in Python

32 谢谢!

《C语言基础入门》课程教学大纲

《C语言基础入门》课程教学大纲 C 语言开发入门教程课程教学大纲课程编号 :201409210011 学分 :5 学分学时 :58 学时 ( 其中 : 讲课学时 :39 学时上机学时 :19 学时 ) 先修课程 : 计算机导论后续课程 :C++ 程序设计适用专业 : 信息及其计算机相关专业开课部门 : 计