函数程序设计.ppt

1、函数程序设计 Functional Programming http:/ 海燕 020-31981361,Important links,All about the course: http:/ All about Haskell: http:/haskell.org,课程安排与要求,每周二1214节，213周； 地点：实验室B202 讲义：Haskell函数程序设计； 成绩评定：平时成绩50% + 期末成绩50%，平时成绩包括 课堂参与； 课堂、课下作业； 要求：认真对待“选修课”，选修/=不重要；共同保证这两个学分的质量。,函数程序设计简介,函数程序设计语言的历史背景 什么是函数程序设计

2、 函数程序设计的特点 函数与类型 Hugs 一个Haskell 解释器,简介,历史背景 什么是函数程序设计 函数程序设计的特色 函数与类型 Hugs 一个Haskell 解释器,软件危机,如何应对计算机程序日益增加的规模和复杂性 (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

3、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、 函数程序设计语言较好地到达了上述目标。,历史背景,1920s1940s: and Alonzo Church Haskell Currydeveloped lambda calculus（演算）, 它是一个函数的理论，也是串行计算的一个模型。,历史背景,1960s:John McCarthydevelops the first functional language Lisp, influenced by lambda calculus, but still with variable assignments.,历史背景,Late 1960s: Peter Landin develops I

5、SWIM, 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

6、 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,Introduction,历史背景 什么是函数程序设计 函数程序设计的特点 函数与类型 Hugs 一

7、个Haskell 解释器,什么是函数程序设计?,C, Java, Ada and Pascal 是命令式（ imperative ）语言: 一个程序时一些命令的序列，程序运行时命令按顺序执行。关注的焦点: 如何 进行计算. 一个函数程序定义了如何将输入数据转换为输出数据，它是一个表达式：程序的运行通过计算表达式实现。关注焦点: 计算什么. 函数程序设计基于一种不同于其他程序设计语言的程序观：一个程序是从输入到输出的函数，程序的执行是表达式的计算，而非命令的执行。,Let the machine do machines work and let the human do humans work.

8、,什么是函数程序设计 (2),表达式由函数和基本值构成. 例: 计算从1至10 的和.,命令式语言:total = 0;for (I = 1; I=10, I+)total += I;,Haskell语言:sum 110,sum 是一个函数, 110 表示1 至 10的整数.,简介,背景 什么是函数程序设计 函数程序的特点 函数与类型 Hugs 一个Haskell 解释器,函数程序设计的特点,简洁、优美. 函数程序更简洁。例如: qsort.容易理解 qsort = qsort (x:xs) = qsort less + x + qsort morewhere less = y | y = x

9、,函数程序设计的特点(2),无副作用，较少的错误. The result of a function (no side effect) is determined by its input, and only by its input. The result doesnt depend on the evaluation order. This eliminates a whole class of bugs in imperative languages. 强类型. It is impossible to apply a function to a boolean when you shou

10、ld apply it to an int. Bugs are caught at compile-time, rather than run-time. This also makes it less bugy.,Features of functional programming(3),代码重用: Polymorphism enhance reusability. For example, qsort can be used to lists of int, lists of double, lists of any type that has = defined. 模块化: A good

11、 programming language support modular programming, and this requires good glue. Functional programming provides two kinds of glue- higher order functions and lazy evaluation.,Features of functional programming(4),高阶函数 A higher order function can takes functions as arguments and return a function. 惰性

12、计算 Non-strict functional languages have another powerful feature: they only evaluate as much of the program as is required to get the answer - this is called lazy evaluation（惰性计算）. See “Why functional programming matter?”,简介,背景 什么是函数程序设计 函数程序设计的特点 函数和类型 Hugs 一个Haskell 解释器,值与表达式,一个值是一个数据:2, 3.1415, “

13、Alice”, 一个表达式可以计算其值:2+3, pi*r2, -b + sqrt(b2 4*a*c)/(2*a), 表达式: 由值、运算符和函数构成; 一个值是不可再计算其值的表达式.,operation,function,定义和类型,一个类型是同类型值的集合，或者说，这些值支持一组相同的运算。例如，整数的集合Int，布尔值的集合Bool，图形的集合。 2 : Int 读作“2 具有类型 Int”， 称之为类型说明. 一个定义给一个特定类型的表达式赋予一个名area : Intarea = 3 * 4,名称以小写字母开始,说明值的类型,说明如何计算表达式的值,函数与类型,一个函数具有一些输入

14、 (arguments, parameters) 并返回一个输出值(result). 设A是函数f的输入值集合，称之为f的定义域（the domain of the function f）. 设B是函数f 的结果值的集合，称之为f的值域（the codomain of the function f.) 称f是从集合A到集合B的函数。 用 A - B表示A到B的所有函数的集合 。 A - B成为函数f的类型。,函数定义,一个函数定义说明如何由输入计算输出。double : Int - Intdouble x = 2 * xarea : Int - Int - Intarea l b = l *

15、b,参数,说明输入类型和输出类型,函数体说明如何由输入计算结果,函数名,函数应用,在数学上，函数应用通常表示为函数名后接包含在括号内的参数，如f(x, y), f (2, 4). 在Haskell中, 函数应用表示为函数名后接依次用空格分隔的参数，如，f x y, f 2 4.在Haskell中, 括号用于组织表达式,如 f 2 (2 + 2) 函数应用比其他运算符具有更高的优先级，如 f 2 + 4 等价于 (f 2) + 4,函数程序,一个函数程序由一些函数和值构成。 一个函数通常是用其他函数定义的。 一个主函数计算整个程序在输入下的输出。,Your first Haskell progr

16、am,使用一个文本编辑器编辑如下文本并存储为 FirstScript.hs: - My first Haskell scriptFirstScript.hs - - size is define as an integersize : Intsize = 23 + 45square : Int - Intsquare n = n * ndouble : Int - Intdouble x = 2 * xexample : Intexample = double (size square (3 23),注释,- 单行注释 - 多行注释-,脚本格式Layout,Haskell也使用 , 和 ; 组

17、织定义. 但是，更多的是使用版面格式规则。 基本规则: 如果新的一行开始于前一行的右边，则新行是前一行说明（定义）的继续，否则是另一个说明（定义）的开始。 例如，,f x y = x + y +123 g x = f x x,简单规则 : 一系列的同层定义应该始于同一列。,Layout rule,OK Not OK,max : Int - Int - Intmax x y = if x=y then x else ymin : Int - Int - Int min x y = ,max : Int - Int - Int max x y = if x=y then min : Int - I

18、nt - Int min x y = ,Haskell中的命名,函数名和变量名以小写字母开始。 类型名和构造符名以大写字母开始。如 Int, True. 保留字（Reserved words）: case class data default deriving do else if import in infix infixl infixr instance let module newtype of then type where,简介,背景 什么是函数程序设计 函数程序设计的特点 函数与类型 Hugs Haskell 解释器,运行 Hugs,Hugs 是 Haskell 的一个实现，它的

19、PC版本 和 Unix 版本均可在下列网站免费下载安装 www.haskell.org/hugs/ 开始运行Hugs, 执行hugs FirstScript.hs Main (在这里你可以运行你的程序)例如,Main double 23 square (double 4)- 18,Hugs 命令,:load first.hs 载入 Haskell 脚本 first.hs :reload 重新载入最近载入的文件 :type e 显示 e的类型 :edit first.hs 编辑文件 first.hs :? 列出 Hugs 命令 :quit 退出系统Hugs 命令还可以缩写为命令的第一个字母,如

20、:l 等价于 :load.,错误信息（Error messages）,语法错误（Syntax error）:Prelude 2-(3-4)ERROR: Syntax error in expression 程序错误（Porgram errors）: Prelude 4 div (double 2 4)Program error: primDiviInt 4 0,类型错误Type Error,Type error:main double squareERROR: Type error in application * expression : double square * term : squ

21、are * type : Int - Int * does not match : Int,标准引导库,运行hugs时，我们会看到Reading file: “C:HUGSlibPrelude.hs” 标准引导库 Prelude.hs 包含一些常用的算术函数和列表函数。 Haskell还提供一些其他标准函数库。,模块（Modules）,一个计算机软件由成千上万行定义（说明，命令，语句）构成。为了开发和维护大规模的软件，我们必须将一个软件系统分解成为相对独立的、较小的程序，称之为模块。 一个模块可以调用其他模块。 一个模块可以控制此模块输出那些定义。 一个Haskell 程序由一些模块构成，其中一个称为 Main ，并输出一个值main.,模块 (2),一个模块包含一系列Haskell定义. module Bee whereimport Ant,模块名,调用其他模块,模块体,作业: 下载安装hugs编辑FirstScript.hs, 并调入hugs运行找到Prelude.hs, 试着运行一些函数在FirstScript.hs中加入更多的函数,