南京大学计算机科学与技术系：《程序设计（C++）》课程教学资源（PPT讲稿，基础篇）10 f函数式、逻辑式程序设计 unctional & logic programming

函数式&逻辑式程序设计

函数式&逻辑式程序设计

程序设计范式 (Programming Paradigms) 从本质上说，用计算机来解决实际问题就是通过对反 映问题本质的数据进行处理来实现的： 。程序=算法+数据结构 如何看待和组织算法和数据结构却存在着不同的做法 从而形成不同的程序设计范式(programming paradigms 程序设计范式是设计、组织和编写程序的一种方式，它往 往要基于一组理论、原则和概念。 ·不同的范式将采用不同的程序结构和程序元素来描述程序。 范式具有针对性，不同的范式往往适合于解决不同类型的 问题

程序设计范式 （Programming Paradigms） ◼ 从本质上说，用计算机来解决实际问题就是通过对反 映问题本质的数据进行处理来实现的： • 程序 = 算法 + 数据结构 ◼ 如何看待和组织算法和数据结构却存在着不同的做法， 从而形成不同的程序设计范式（programming paradigms）： • 程序设计范式是设计、组织和编写程序的一种方式，它往 往要基于一组理论、原则和概念。 • 不同的范式将采用不同的程序结构和程序元素来描述程序。 • 范式具有针对性，不同的范式往往适合于解决不同类型的 问题

典型的程序设计范式 过程式程序设计(procedural programming.) 一种以功能为中心、基于功能分解和复合的程序设 计范式。 程序由一些子程序构成，每个子程序对应一个子功 能。子程序描述了一系列的操作（操作步骤），它 是操作的封装体，实现了过程抽象。 程序的执行过程体现为一系列的子程序调用。 在过程式程序中，数据处于附属地位，它独立于子 程序，在子程序调用时通过参数或全局变量传给子 程序使用

典型的程序设计范式 ◼ 过程式程序设计(procedural programming) • 一种以功能为中心、基于功能分解和复合的程序设 计范式。 • 程序由一些子程序构成，每个子程序对应一个子功 能。子程序描述了一系列的操作（操作步骤），它 是操作的封装体，实现了过程抽象。 • 程序的执行过程体现为一系列的子程序调用。 • 在过程式程序中，数据处于附属地位，它独立于子 程序，在子程序调用时通过参数或全局变量传给子 程序使用

面向对象程序设计(object-oriented programming.） 。一种以数据为中心、基于数据抽象的程序设计范式。 程序由一些对象构成，对象是由一些数据及可施于 这些数据上的操作所组成的封装体 对象的特征由相应的类来描述，一个类描述的对象 特征可以从其它的类获得（继承） 程序的执行过程体现为各个对象之间相互发送和处 理消息。 在面向对象程序中，数据表现为对象的属性，对数 据的操作是通过向包含数据的对象发送消息（调用 对象提供的操作)来实现

◼ 面向对象程序设计(object-oriented programming) • 一种以数据为中心、基于数据抽象的程序设计范式。 • 程序由一些对象构成，对象是由一些数据及可施于 这些数据上的操作所组成的封装体。 • 对象的特征由相应的类来描述，一个类描述的对象 特征可以从其它的类获得（继承）。 • 程序的执行过程体现为各个对象之间相互发送和处 理消息。 • 在面向对象程序中，数据表现为对象的属性，对数 据的操作是通过向包含数据的对象发送消息（调用 对象提供的操作）来实现

·函数式程序设计(functional programming ·程序由一组数学函数构成，计算过程体现为一系列 的函数应用（把函数作用于数据）。 ·基于的理论是递归函数理论和ambda演算。 逻辑式程序设计(logic programming) ○程序由一组事实和一组推理规则构成，在事实基础 上运用推理规则来实施计算。 0 基于的理论是谓词演算

◼ 函数式程序设计（functional programming） • 程序由一组数学函数构成，计算过程体现为一系列 的函数应用（把函数作用于数据）。 • 基于的理论是递归函数理论和lambda演算。 ◼ 逻辑式程序设计（logic programming） • 程序由一组事实和一组推理规则构成，在事实基础 上运用推理规则来实施计算。 • 基于的理论是谓词演算

命令式v声明式程序设计 命令式程序设计(imperative p programming 强调对“如何做”的描述，要对操作步骤和状态变 化给出明确的描述。例如，过程式和面向对象程序 设计。 与冯诺依曼体系结构一致，是使用较广泛的程序设 计范式，适合于解决大部分的实际应用问题。 声明式程序设计(declarative programming 强调对“做什么”的描述，而如何做则由实现系统 自动完成。例如，函数式和逻辑式程序设计 有良好的数学理论支持，并且，设计出的程序具有 潜在的并行性。适合于需要大量进行复杂的符号处 理（非数值计算）的人工智能领域的应用

◼ 命令式程序设计（imperative programming） • 强调对“如何做”的描述，要对操作步骤和状态变 化给出明确的描述。例如，过程式和面向对象程序 设计。 • 与冯诺依曼体系结构一致，是使用较广泛的程序设 计范式，适合于解决大部分的实际应用问题。 ◼ 声明式程序设计（declarative programming） • 强调对“做什么”的描述，而如何做则由实现系统 自动完成。例如，函数式和逻辑式程序设计。 • 有良好的数学理论支持，并且，设计出的程序具有 潜在的并行性。适合于需要大量进行复杂的符号处 理（非数值计算）的人工智能领域的应用。 命令式v声明式程序设计

函数式程序设计简介 程序由一组数学函数构成， 计算过程体现 为一系列的函数应用（把函数作用于数 据) 函数也被作为值（数据）来看待， 即函数 的参数和返回值也可以是函数。 基于的理论是递归函数理论和ambda演算

函数式程序设计简介 ◼ 程序由一组数学函数构成，计算过程体现 为一系列的函数应用（把函数作用于数 据）。 ◼ 函数也被作为值（数据）来看待，即函数 的参数和返回值也可以是函数。 ◼ 基于的理论是递归函数理论和lambda演算

函数式程序设计的例子 。计算： a b c/d 传统的命令式编程： t1 a b; t2 c/d; r t1 t2; 函数式编程： multiply(...)... divide(...)...} add(.){..} ..add(multiply(a,b),divide(c,d))

函数式程序设计的例子 ◼ 计算： a * b + c / d ◼ 传统的命令式编程： t1 = a * b; t2 = c / d; r = t1 + t2; ◼ 函数式编程： multiply(...) { ... } divide(...) { ... } add(...) { ... } ... add(multiply(a,b),divide(c,d))

■ 计算字符串的逆序： "abcd"-->"dcba" 传统的命令式编程： void reverse(char str[]) int len=strlen(str); for (int i=0;i<len/2;i++) char t=str[i]; str[i]str[len-i-1];str[len-i-1]t; } 函数式编程： string reverse(string str) if (len(str) ==1) return str; else return concat(reverse(substr(str,1,len(str)-1)),substr(str,0,1)); } 注意：不是写成函数就是函数式编程！

◼ 计算字符串的逆序： "abcd" --> "dcba" ◼ 传统的命令式编程： void reverse(char str[]) { int len=strlen(str); for (int i=0; i<len/2; i++) { char t=str[i]; str[i] = str[len-i-1]; str[len-i-1] = t; } } ◼ 函数式编程： string reverse(string str) { if (len(str) == 1) return str; else return concat(reverse(substr(str,1,len(str)-1)),substr(str,0,1)); } ◼ 注意：不是写成函数就是函数式编程！

函数式程序设计的几个基本特征 “纯”函数： 引用透明（无副作用，以相同的 参数调用函数总得到相同的值) 没有状态（数据不可变）：计算不改变已有数 据，而是产生新的数据。（无赋值操作） 函数也是值(first-class citizen):函数的 参数和返回值都可以是函数。一（高阶函数） 表达式的惰性（延迟）求值(Lazy evaluation):需要的时候才计算。 潜在的并行性

函数式程序设计的几个基本特征 ◼ “纯”函数：引用透明（无副作用，以相同的 参数调用函数总得到相同的值） ◼ 没有状态（数据不可变）：计算不改变已有数 据，而是产生新的数据。（无赋值操作） ◼ 函数也是值（first-class citizen) ：函数的 参数和返回值都可以是函数。（高阶函数） ◼ 表达式的惰性（延迟）求值（Lazy evaluation）：需要的时候才计算。 ◼ 潜在的并行性