高级程序设计

29 - 函数式和逻辑式程序设计

2020-06-04 14:00 CST
2020-06-06 22:47 CST
CC BY-NC 4.0

第28将为mfc专场,没有做笔记。

程序设计范式

从本质上说,程序 = 算法 + 数据结构。

如何看待和组织算法和数据结构存在不同的做法,从而形成不同的程序设计范式(programming paradigm):

  • 程序设计范式是设计、组织和编写程序的一种方式,往往基于一组概念、原则和理论。
  • 不同的范式将采用不同的程序结构和程序元素来描述问题。
  • 范式具有针对性,不同的范式往往适合于解决不同类型的问题。

过程式程序设计

Procedural Programming

  • 以功能为中心,基于功能分解和符合的程序设计范式
  • 程序由一些子程序构成,每个子程序对应一个子功能。子程序描述了一系列的操作,是操作的封装体,实现了过程抽象。
  • 程序的执行过程体现为一系列的子程序调用。
  • 在过程式程序中,数据处于附属地位,独立于子程序,在子程序调用时通过参数或全局变量传递给子程序使用。

面向对象程序设计

Object-oriented Programming

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

命令式程序设计范式

Imperative Programming

  • 过程式和面向对象程序设计属于命令式程序设计范式
  • 需要对“如何做”进行详细描述,包括操作步骤和状态变化
  • 和冯诺伊曼体系结构一致,使用较广泛,适合于解决大部分的实际应用问题

声明式程序设计范式

Declarative Programming

  • 只需要对“做什么”进行描述,而如何做则由实现系统自动完成
  • 有良好的数学理论支持,设计出的程序具有潜在的并行性
  • 适合于需要大量进行复杂的符号处理(非数值计算)的人工智能领域的应用
  • 函数式程序设计和逻辑式程序设计是声明式程序设计范式的典型代表

函数式程序设计

Functional Programming

  • 把程序组织成一组数学函数,计算过程体现为一系列的函数应用
  • 函数也被作为值来看待,即函数的参数和返回值也可以是函数
  • 基于的理论是递归函数理论和Lambda演算

函数式程序设计的基本特征:

  • 纯函数(引用透明):以相同的参数调用一个函数总得到相同的值(无副作用)
  • 没有状态(数据不可变):计算不改变已有数据,而是产生新的数据(无赋值操作)
  • 函数也是值(first-class citizen):函数的参数和返回值都可以是函数(高阶函数)
  • 表达式的惰性(延迟)求值:需要的时候才做计算
  • 潜在的并行性

函数式程序设计语言:

  • 纯函数式语言:Common Lisp、Scheme、Erlang、Haskell、F#
  • 对函数式编程提供支持的非函数式语言:Perl、PHP、C#、Java、Python、C++11

函数式程序设计的几个基本技术:

  • 递归:实现重复操作,不采用迭代方式
  • 尾递归:递归调用时递归函数的最后一步操作(编译器可对其优化)
  • 映射/规约(map/reduce):对一个集合中的元素做映射操作(得到另一个集合)和规约操作(得到一个值)
  • 柯里化(currying):把接收多个参数的函数变成接受单一参数(原函数的第一个参数)的函数,该函数返回一个接收剩余参数的函数(函数约简,提高函数的适用性)

Map操作:

  • Python:map(lambda, collection)
  • C++: transform(src.begin(), src.end(), dst.begin(), lambda)

Reduce操作:

  • Python:reduce(lambda, collection)
  • C++:accumulate(src.begin(), src.end(), value, lambda)

Currying操作:

def h(x):
    def g(y):
      return x + y
    return g

h(1)(2) # -> g(2) -> 3
add5 = h(5) # 体现适用性

C++中可用function对象来实现。

惰性和并行求值:

a = f1(1)
b = f2(2)

if (...):
  ... a + b ...
  • 惰性求值:用到的时候再计算,如果if没执行到,那么就可以不求值。
  • 并行求值:f1f2都是纯函数,谁先执行都可以,甚至可以并发执行。

逻辑式程序设计

  • 程序由一组事实和一组推理规则构成,在事实基础上运用推理规则来实现计算。
  • 给予的理论是谓词计算。
  • 特征:
    • 数据(事实和规则)就是程序。
    • 计算(匹配、搜索、回溯)由实现系统自动完成。
  • 语言:Prolog等