Cornell CS3110, Functional/Ocaml Programming.

Tail Recursion

尾递归（Tail Recursion）是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。在尾递归中，函数在进行递归调用之前不会做任何其他操作，这使得尾递归可以被优化，以避免使用过多的调用栈空间。

这样的优化是通过重用当前的栈帧来实现的，而不是在每次递归调用时创建一个新的栈帧。这意味着尾递归函数可以在有限的栈空间内执行大量的递归调用，从而避免了常规递归中可能遇到的栈溢出问题。

Steele Jr G L. Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, lambda: The ultimate goto[C]//Proceedings of the 1977 annual conference. 1977: 153-162.

例如在Ocaml中定义一个factorial递归函数：

1
2
let rec factorial n = 
    if n = 0 then 1 else n * factorial (n - 1);;
1
val factorial : int -> int = <fun>

然而Ocaml中integer在64 bit系统中，int类型通常是63位，最高位用于标记（tagging）来区分数据为指针还是整数，这意味Ocaml的integer能表示的最大整数是2^63 - 1，即4,611,686,018,427,387,903。发生了integer overflow，这样就没办法验证栈溢出的问题：

1
factorial 100;;
1
- : int = 0

要先解决integer overflow的问题，使用opam install zarith来安装Zarith（主要用于处理大数和有理数的高效算术运算。这个库提供了对大整数和有理数的支持，可以进行加减乘除等基本运算，以及更复杂的数学运算，比如幂运算和模运算。Zarith库使用C编写的底层代码来优化性能，特别是在处理非常大的数字时）。

确保不会发生integer overflow：

1
2
let rec factorial n = 
    if Z.equal n Z.zero then Z.one else Z.mul (factorial (Z.pred n)) n;;
1
val factorial : Z.t -> Z.t = <fun>
1
factorial (Z.of_int 100);;
1
2
- : Z.t =
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

当n = 1,000,000时发生栈溢出：

1
factorial (Z.of_int 1_000_000);;
1
Stack overflow during evaluation (looping recursion?).

使用tail recursion来防止栈溢出：

1
2
let rec factorial n acc= 
    if Z.equal n Z.zero then acc else factorial (Z.pred n) (Z.mul acc n);;
1
val factorial : Z.t -> Z.t -> Z.t = <fun>

之后可正常进行运算不发生栈溢出：

1
factorial (Z.of_int 1_000_000 Z.one);;

Defensive Programming

比方说要实现一个random_int函数，为函数的输入设置一个上限bound来使得当输入过大时抛出Exception。

1
2
3
4
5
6
7
(** [random_int bound] is a random integer between 0 (inclusive)
    and [bound] (exclusive).  Raises: [Invalid_argument "bound"]
    unless [bound] is greater than 0 and less than 2^30. *)

let random_int bound =
  assert (bound > 0 && bound < 1 lsl 30);
  Random.int bound;;
1
2
random_int (1 lsl 30);;
Exception: Assert_failure ("//toplevel//", 2, 2).

lsl为二进制左移位(logical shift left)，lsr为二进制右移位(logical shift right)。

另外两种方法：

1
2
3
4
let random_int bound =
  if not (bound > 0 && bound < 1 lsl 30)
  then invalid_arg "bound";
  Random.int bound;;
1
2
3
4
let random_int bound =
  if not (bound > 0 && bound < 1 lsl 30)
  then failwith "bound";
  Random.int bound;;

Equality

  • = : Structural Equality

结构相等表示两个值的内容相同，且结构上相等。

当使用=运算符时，OCaml会递归地比较复杂数据类型的内容，例如列表、元组、数组等，检查每个元素的值是否相同。即使两个对象位于内存中的不同位置，只要它们的内容完全一样，结构相等判断为真。

1
2
"hi" = "hi";;
- : bool = true
  • == : Physical Equality

物理相等表示两个值在内存中是否是同一个对象，换句话说，它们的引用是否指向相同的内存地址。

使用==运算符时，OCaml不会比较值的内容，而是直接比较它们的内存地址是否相同。

1
2
"hi" == "hi";;
- : bool = false

NotImplemented

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章