• 💬 写在前面：OCaml 是一种拥有静态类型系统的语言，本章我们就要探讨静态类型系统。

目录

0x00 静态类型系统

0x01 自动类型推断（automatic type inference）

0x02 多态类型和多态函数

0x03 let-多态类型系统（let-polymorphic type system）

---

0x00 静态类型系统（Static Type System）

OCaml 是一种拥有 静态类型系统 的语言。一般来说，编程语言可以分为两种：

1. 拥有静态类型语言（statically typed language）
2. 拥有动态类型语言（dynamically typed language）

OCaml 与 C, C++, Java, Scala 等语言一样，属于静态类型系统的语言。

这些语言在编译阶段进行静态类型检查，因此带有类型错误的程序无法通过编译器。

# 1 + true;;
Error: This expression has type bool but an
expression was expected of type int

然而，像Python、Lisp这样具有动态类型系统的语言在程序执行过程中执行类型检查。

它们不会预先检查程序中是否存在类型错误，而是在运行时监控类型不匹配的计算发生情况。

.

这两种类型具有相反的优缺点。

具有静态类型系统的语言可在开发过程中检测类型错误，非常适合需要高稳定性的程序开发。

相反具有动态类型系统的语言比静态语言更自由、更灵活。因此程序开发速度更快。

.

具有静态类型系统的语言可以进一步分为两种。

第一种是配备了安全类型系统的语言，

它们能够在编译阶段准确地找到程序执行期间可能发生的所有类型错误：

如 OCaml, Haskell, Scala 等函数式语言通常属于这一类。

第二种是虽然具有静态类型系统，但在运行时仍然可能发生类型错误的不安全语言，如C, C++。

.

OCaml 在静态检查程序类型的同时也能够自动推断类型。

例如，在 C 或 Java 中，必须始终显式地声明变量和函数的类型。

public static int f(int n) {
    int a = 2;
    return a * n;
}

0x01 自动类型推断（automatic type inference）

在 OCaml 中，可以如下定义该函数，而无需类型信息，并且编译器会自动推断类型。

# let f n =
let a = 2 in
a * n;;
val f : int -> int = <fun>

OCaml 可以自动推断类型，即使程序非常复杂也能做到。

为了方便大家了解 OCaml 执行器如何自动推断类型，让我们以前面定义的函数 sum 为例：

# let sum f a b =
(if f a then a else 0) + (if f b then b else 0)
val sum : (int -> bool) -> int -> int -> int = <fun>

OCaml 通过分析函数体来自动推断类型信息。

首先，在条件表达式 if e1 then e2 else e3 中，要求  和  的类型必须相同，

并且因为 0 的类型是整数，可以推断出参数 a 和 b 的类型为 int。

接下来，函数 `f` 被作为函数调用的形式（如 `f a` 或 `f b`）使用，因此应该具有函数类型。

.

根据 `f` 的参数是 `a` 或 `b`，以及 `f a` 和 `f b` 的结果作为条件表达式  的一部分使用，

可以推断出 `f` 的类型应该是 `int -> bool`。

最后，由于 `sum` 返回加法结果，可以推断其类型为 `int`。通过这样的过程：

OCaml 的自动类型推断算法能够在执行程序代码之前自动推断出类型，当然也可以手动指定：

# let sum (f : int -> bool) (a : int) (b : int) : int
= (if f a then a else 0) + (if f b then b else 0);;
val sum : (int -> bool) -> int -> int -> int = <fun>

在这种情况下，OCaml 会验证用户是否正确地指定了类型。

例如，如果用户指定的类型是错误的，它会自动找出对应错误。

# let sum (f : int -> int) (a : int) (b : int) : int =
(if f a then a else 0) + (if f b then b else 0);;
Error: The expression (f a) has type int but an
expression was expected of type bool

用户误将函数 f 的类型写成了 int -> int，但实际上 f 的结果类型应该是 bool，这是错误的。

由于 OCaml 的类型系统是安全的，因此如果用户在类型上犯了错，系统一定会指出来。

0x02 多态类型和多态函数

有时候，可能会存在某些情况下无法确定一个表达式的确切类型。

例如，下面定义的函数 id 是一个可以对任意类型使用的函数：

# let id x = x;;
val id : ’a -> ’a = <fun>
# id 1;;
- : int = 1
# id "abc";;
- : string = "abc"
# id true;;
- : bool = true

在这种情况下，使用像 'a 这样的类型变量来表示类型，以便函数可以针对任意类型进行操作。

这种类型称为 多态类型 (polymorphic type)，

而拥有多态类型的函数称为 多态函数 (polymorphic function) 。

这意味着这些函数可以适用于任意类型。

0x03 let-多态类型系统（let-polymorphic type system）

OCaml的多态类型系统并不完全自由，只支持通过 `let` 定义的多态函数。

这样的类型系统称为 let-多态类型系统 (let-polymorphic type system) 。

例如，如果像下面这样定义函数 f，它将被识别为多态函数，并且可以在没有问题的情况下执行：

# let f = fun x -> x in
let x = f 1 in
let y = f true in
3;;
- : int = 3

但如果不使用 let 语法，直接按以下方式编写具有相同意义的程序，将会导致类型错误。

# (fun f ->
    let x = f 1 in
        let y = f true in
            3) (fun x -> x);;
Error: The expression has type bool but an expression
was expected of type int

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2024.6.25
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！

📜 参考资料  - R. Neapolitan, Foundations of Algorithms (5th ed.), Jones & Bartlett, 2015. - T. Cormen《算法导论》（第三版），麻省理工学院出版社，2009年。 - T. Roughgarden, Algorithms Illuminated, Part 1~3, Soundlikeyourself Publishing, 2018. - J. Kleinberg&E. Tardos, Algorithm Design, Addison Wesley, 2005. - R. Sedgewick&K. Wayne，《算法》（第四版），Addison-Wesley，2011 - S. Dasgupta，《算法》，McGraw-Hill教育出版社，2006。 - S. Baase&A. Van Gelder, Computer Algorithms: 设计与分析简介》，Addison Wesley，2000。 - E. Horowitz，《C语言中的数据结构基础》，计算机科学出版社，1993 - S. Skiena, The Algorithm Design Manual (2nd ed.), Springer, 2008. - A. Aho, J. Hopcroft, and J. Ullman, Design and Analysis of Algorithms, Addison-Wesley, 1974. - M. Weiss, Data Structure and Algorithm Analysis in C (2nd ed.), Pearson, 1997. - A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2003. - A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983. - E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms/C++, Computer Science Press, 1997. - R. Sedgewick, Algorithms in C: 第1-4部分（第三版），Addison-Wesley，1998 - R. Sedgewick，《C语言中的算法》。第5部分（第3版），Addison-Wesley，2002