函数式编程（Ocaml）

Posted on | In
Words count in article 1.9k | Reading time 8

Abstract

最近在实验室实习的过程中学到了很多有意思的东西，对Programming Languages也有了更深的了解，Ocaml是一门支持多范式的函数式编程语言。程序描述计算，但是又不仅仅是计算。Ocaml的学习带给我的不仅仅是语言本身，这个系列记录了其中的部分心得:

  • 关于scripting/imperative/object-oriented/functional PL的基本概念
    • Higher-order Functions
    • State-Full vs State-Free Computation
    • Modelling Objects and Closures
    • Exceptions/Continuations to Defer Control
    • Polymorphism
    • Partial Evaluation/Lazy Programming/Modules
  • 关于reason about programs的方法
    • Type Checking
    • Induction
    • Operational Semantics
    • QuickCheck
  • 关于设计一门语言的基本规则

FP's Basic Concepts

Ocaml is a statically typed functional programminng language。函数式编程中，function永远是一等公民，程序中只有expression的概念，通过functions递归处理values来完成computations。Ocaml通过pattern matching模式匹配的方式来定义递归数据结构和函数，进而写出更简洁的程序。

在函数式中还有一个和imperative PL.中不同的概念称为effect-free programming。在命令式语言中，我们通过给variables/fields赋值来修改程序状态并将赋值行为的结果看成是effects。但是比如函数式就不会explicitly的分配内存，甚至没有exception handling来改变控制流状态——不支持effect被称为pure functiional比如Haskell。Ocaml不是纯函数式语言。所以支持effectful/state-full programming和pure FP。

最后一个关键字就是statically typed静态类型。Types statically approximate the runtime behaviour of an expression.意思就是static type checking本身是在程序运行之前进行类型检查——通过syntatic structure of expressions。它可以保证通过静态类型检查的程序在运行时一定不会core dump。这样的statically typed PL.比如Ocaml/Java/ML/Haskell/Scala等也被称为是type-safe的。

Expressions, Names, Values and Types

在函数式中没有语句statements，最基本的expression就是numbers/strings/booleans。

1
2
3
4
# 2 + 3;;
- : int = 5
# 4.0 /. 2.0;;
- : float = 2.0

上面代码中的格式为<name> : <type> = <value> 。我们将;;之前的式子称为expressions，将整个计算过程称为evaluation，而将计算的结果称为values。

注意在Ocaml中基础运算符并没有被重载，故浮点运算都是在后面有一个,。这主要是因为Ocaml是静态类型的，不会在运行时去根据运算符参数来推导重载的operators。

通过类型检查的程序，其evaluation要么更新到一个新的state要么报一个built-in runtime error。比如:

1
2
# 3 / 0;;
Exception: Division_by_zero

Variables, Bindings and Functions

Ocaml是一个call-by-value的语言——it binds values to variable names not expressions。这里有一个binding的概念，区分于assignment。我们只是在values和name之间建立了“链接”——并没有新的state被创建——我理解和imperative PL.不同的应该是内存模型比如C中对局部变量是放在栈上的但是确实创建了内存。当然这种“链接”也是可以更新的。在Ocaml中用let表达式来建立一个绑定。

1
2
3
4
# let x = 3 * 3;;
val x : int = 9
# let x = 42;;
val x : int = 42

变量的作用域是根据binding stack来确定的。局部或者临时创建的binding都会被push进binding stack中，在不需要的时候会被GC清除。

1
2
3
4
5
6
# let k = 4;;
val k : int = 4
# let k = 3 in k * k ;;
- : int = 9
# k;;
- : int = 4

这里有一个新的let <name> = <expression 1> in <expression 2>结构——将expression1的value绑定到name上，然后继续使用这个新的绑定对expression 2进行evalutions。

在函数式中let不仅可以绑定基本类型，还可以绑定函数。

1
2
3
4
let area : float -> float = function r -> pi *. r *. r;;
let area : float -> float = fun r -> 3.14 *. r *. r;;
let area (r:float) = pi *. r *. r;;
let a1 = area(2.0);;

上面的三种写法是等价的，都得到函数类型val area : float -> float = <fun>。有意思的是函数作为一种绑定，也是在binding stack中的，所以它只能看到过去的绑定：

1
2
3
4
5
6
7
8
9
10
# let (pi*float) = 3.0
val pi : float = 3.14
# let area (r:float) = pi *. r *.r;;
val area : float -> float = <fun>
# let a1 = area(2.0);;
val a1 : float = 12.0
# let (pi*float) = 4.0
val pi : float = 4.0
# let a2 = area(2.0);;
val a2 : float = 12.0

最后介绍一下递归函数。在Ocaml中递归函数使用let rec来声明。比如定义factorial:

1
2
3
4
5
# exception Domain;;
# let rec fact n = 
	if n < 0 then raise Domain
	else if n = 0 then 1
	else n * fact(n - 1);;

在函数式中所有的函数都可以被写成尾递归的形式然后进一步优化——这是因为尾递归函数的栈帧可以被优化掉。比如:

1
2
3
4
5
# let fact_tr n = 
	let rec f n acc = 
		if n = 0 then acc else f (n - 1) (n * acc)
	in
		f n 1

Data Types and Pattern Matching

这一节可以在Ocaml中定义自己的递归/非递归的数据类型。

Ocaml使用type来定义有限无序的非递归集合，这里举一个扑克牌的例子:

1
2
3
4
5
6
7
8
9
10
11
# type suit = Clubs | Spades | Hearts | Diamonds;;
type suit = Clubs | Spades | Hearts | Diamonds
# type rank = Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King | Ace;;
# type card = rank * suit;;
type card = rank * suit
# type hand = Empty | Hand of card * hand;;
type hand = Empty | Hand of card * hand
# let rec dom (s1, s2) = match (s1, s2) with 
| (Spades, _) -> true
| (Hearts, Diamonds)  -> true
| (s1, s2) -> s1 = s2

Ocaml使用pattern matching模式匹配来操作这些数据结构。这里有两个概念——patterns和constructors。每一个pattern由不同的constructors填充——这里的构造器指的是每一个和类型元素同名的构造器比如Clubs。Ocaml规定构造器首字母必须大写，且匹配是从上到下的顺序。

进一步的，为了简化代码而支持inductively的deep pattern构造形式如下:

1
2
3
4
# let rec add c1 c2 = match c1 c2 with
| (Hearts, v1), (Hearts, v2) -> v1 + v2
| _, _ -> 0;;
val add : ('a -> (suit * int) * (suit * int)) -> 'a -> int = <fun>

这里会发现构造了一个比较复杂的类型('a -> (suit*int)*(suit*int)) -> 'a -> int。其中type1 * type2为一个pair，而`a为任意类型。

上述函数的基本类型推导过程为两个任意类型为输入参数，int为输出。其中任意类型为(suit*int)*(suit*int)的。

上面扑克牌的例子中hand定义一组无限递归集合。在hand类型中，Empty和Hand分别为两个constructors。Empty没有输入参数，而Hand以a tuple of a card and another hand的一个tuple为输入参数。看下面的实例化例子:

1
2
3
4
5
6
7
8
9
# let hand0: hand = Empty
let hand1: hand = Hand((Ace, Hearts), Empty)
let hand2: hand = Hand((Queen, Diamonds), hand1)
let hand3:hand = 
Hand((Ace, Spades),
			Hand((Ten, Diamonds), 
					Hand((Seven, Clubs),
							Hand((Queen, Spades),
									Hand((Eight, Clubs), Empty)))));;

这个hand类型实际上就是一棵退化的二叉树（只能靠右生长）——叶子是Empty， 而Hand构造器使用两个参数来建树。

下面我们定义一个函数，这里函数的类型是suit -> hand -> hand，功能是给定一个suit -> hand的输入，然后从hand中找有匹配到suit类型的hand然后返回。

1
2
3
4
5
# let rec extract (s:suit) (h:hand) = match h with 
	| Empty -> Empty
	| Hand ((_, s') as c, h') ->
		if s = s' then Hand(c, extract s h')
		else extract s h'

上一个函数中的Empty实际上就是一个终结符，意味着如果hand类型都不匹配的话就直接返回Empty。但是如果我要匹配一个card的话，没有匹配上该怎么返回呢？Ocaml引入一个optional data type。比如下面的函数:

1
2
3
4
5
6
7
# type 'a option = None | Some of 'a
type 'a option = None | Some of 'a
# let rec find (r, h) = match h with
	| Empty  -> None
	| Hand((r', s'), h') -> if r = r' then Some s'
													else find(r, h')
val find: rank * hand -> suit option = <fun>

其中option type表示由Some构造器实现的类型为`a的元素集合，是符合多态的任意类型。

本文标题:函数式编程（Ocaml）

文章作者:HaotianMichael

发布时间:2021年04月18日 - 09:04

最后更新:2022年03月16日 - 17:03

原始链接:http://haotianmcihael.github.io/2021/04/18/函数式编程（Ocaml）/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。