为什么 `id id` 不是 OCaml 中的值？
Why `id id` is not a value in OCaml?
我仍在努力理解 OCaml 中的值限制，并且我正在通读 Wright's paper。并且在其中声明 (fun x -> x) (fun y -> y) 不是语法值，同时它还声明 lambda 表达式应该是一个值。这里我有点疑惑，id id本质上不也是一个lambda表达式吗？在 OCaml 中什么才是真正的句法值？
我也在utop试过，发现了这些：
utop # let x = let x = (fun y -> y) (fun z -> z) in x ;;
val x : '_a -> '_a = <fun>
这里id id不是一个值，它不能逃脱值限制但是
utop # let x a = let x = (fun y -> y) a in x ;;
val x : 'a -> 'a = <fun>
这里id a好像是作为一个值来处理的。
都是函数应用，有什么区别？
这是一个应用程序，不是 lambda 表达式。左边的表达式是一个函数，右边的表达式是应用该函数的值。
值的概念（在值限制的意义上）是一个句法概念。这与值的类型无关。
所以，这里涉及到两个概念：let-polymoprhism和取值限制。 Let-polymorphism 不允许对所有非 let-bound 的值进行类型泛化。或者，在不使用双重否定的情况下，它仅在使用 let-binding 引入时才允许值是多态的。这是一个 over-approximation，即它可能不允许有效程序（存在误报），但它永远不会允许无效程序（它将保持健全性）。
值限制是另一个 over-approximation，它是保持命令式程序健全性所必需的。它不允许 non-syntactic 值的多态性。 OCaml 使用此 over-approximation 的更精确版本，称为 relaxed value restriction（实际上允许 某些 non-syntactic 值是多态的）。
但让我先解释一下什么是句法值：
非正式地，语法值是一个表达式，可以在不进行任何计算的情况下进行评估，例如，考虑以下 let 绑定：
let f = g x
这里的 f 不是句法值，因为为了得到你需要计算表达式 g x 的值。但是，在下面，
let f x = g x
值f是句法的，如果去掉糖会更明显：
let f = fun x -> g x
现在很明显，f 是句法的，因为它绑定到 lambda-expression。
该值被称为syntactic，因为它直接在程序中定义（在语法中）。基本上，它是一个可以在静态时间计算的常数值。稍微正式一点，以下值被认为是句法的：
- 常量（即整数和 floating-point 文字）
- 只包含其他简单值的构造函数
- 函数声明，即以 fun 或 function 开头的表达式，或等效的 let 绑定，
let f x = ...
- let 绑定形式为 let var = expr1 in expr2，其中 expr1 和 expr2 都是简单值
现在，当我们非常确定什么是句法什么不是时，让我们更仔细地查看您的示例。让我们从 Wright 的例子开始，实际上：
let f = (fun x => x) (fun y => y)
或者，通过引入 let id = fun x -> x
let f = id id
你可能会看到，这里的f不是句法值，虽然id是句法值。但是为了获得 f 的值，您需要计算 - 因此该值是在运行时定义的，而不是在编译时定义的。
现在，让我们对您的示例进行脱糖处理：
let x a = let x = (fun y -> y) a in x
==>
let x = fun a -> let x = (fun y -> y) a in x
我们可以看到，x是一个语法值，因为左边是一个lambda表达式。 lambda 表达式的类型是 'a -> 'a。你可能会问，为什么表达式的类型不是'_a -> '_a。这是因为只对top-level引入了取值限制，而lambda表达式还不是一个值，它是一个表达式。通俗地说，首先，在没有副作用的假设下推断出最一般的 Hindley-Milner 类型，然后通过（宽松的）值限制削弱推断出的类型。类型推断的范围是 let 绑定。
这都是理论，有时并不清楚为什么有些表达式是 well-type，而语义相同但写法略有不同的表达式不是很好的类型。直觉可能会说，这里有问题。是的，事实上，let f = id id 是一个被类型检查器拒绝的 well-formed 程序，这是 over-approximation 的一个例子.如果我们将这个程序转换为 let f x = id id x 它突然变成一个具有通用类型的类型良好的程序，尽管转换不会改变语义（并且两个程序实际上被编译为相同的机器代码）。这是类型系统的限制，它是简单性和精确性之间的折衷（健全性不能成为妥协的一部分——类型检查器必须是健全的）。因此，从理论上来说，为什么后一个例子总是安全的，这一点并不明显。只是为了实验，让我们尝试使用您的示例，并尝试破坏程序：
# let x = fun a -> let z = ref None in let x = (fun y -> z := Some y; y) a in x ;;
val x : 'a -> 'a = <fun>
所以，我们在这里添加了一个引用z，我们试图存储这个值，这样在不同的应用下，不同的类型，我们应该可以存储到不同的相同的引用值类型。但是完全是non-possible，因为x是句法值，所以保证了，每调用一个类型x k都会创建一个新的引用，这个引用永远不会泄露let-definition 的范围。希望这会有所帮助:)
我仍在努力理解 OCaml 中的值限制，并且我正在通读 Wright's paper。并且在其中声明 (fun x -> x) (fun y -> y) 不是语法值，同时它还声明 lambda 表达式应该是一个值。这里我有点疑惑，id id本质上不也是一个lambda表达式吗？在 OCaml 中什么才是真正的句法值？
我也在utop试过，发现了这些：
utop # let x = let x = (fun y -> y) (fun z -> z) in x ;;
val x : '_a -> '_a = <fun>
这里id id不是一个值，它不能逃脱值限制但是
utop # let x a = let x = (fun y -> y) a in x ;;
val x : 'a -> 'a = <fun>
这里id a好像是作为一个值来处理的。
都是函数应用，有什么区别？
这是一个应用程序，不是 lambda 表达式。左边的表达式是一个函数，右边的表达式是应用该函数的值。
值的概念（在值限制的意义上）是一个句法概念。这与值的类型无关。
所以，这里涉及到两个概念：let-polymoprhism和取值限制。 Let-polymorphism 不允许对所有非 let-bound 的值进行类型泛化。或者，在不使用双重否定的情况下，它仅在使用 let-binding 引入时才允许值是多态的。这是一个 over-approximation，即它可能不允许有效程序（存在误报），但它永远不会允许无效程序（它将保持健全性）。
值限制是另一个 over-approximation，它是保持命令式程序健全性所必需的。它不允许 non-syntactic 值的多态性。 OCaml 使用此 over-approximation 的更精确版本，称为 relaxed value restriction（实际上允许 某些 non-syntactic 值是多态的）。
但让我先解释一下什么是句法值：
非正式地，语法值是一个表达式，可以在不进行任何计算的情况下进行评估，例如，考虑以下 let 绑定：
let f = g x
这里的 f 不是句法值，因为为了得到你需要计算表达式 g x 的值。但是，在下面，
let f x = g x
值f是句法的，如果去掉糖会更明显：
let f = fun x -> g x
现在很明显，f 是句法的，因为它绑定到 lambda-expression。
该值被称为syntactic，因为它直接在程序中定义（在语法中）。基本上，它是一个可以在静态时间计算的常数值。稍微正式一点，以下值被认为是句法的：
- 常量（即整数和 floating-point 文字）
- 只包含其他简单值的构造函数
- 函数声明，即以 fun 或 function 开头的表达式，或等效的 let 绑定，
let f x = ... - let 绑定形式为 let var = expr1 in expr2，其中 expr1 和 expr2 都是简单值
现在，当我们非常确定什么是句法什么不是时，让我们更仔细地查看您的示例。让我们从 Wright 的例子开始，实际上：
let f = (fun x => x) (fun y => y)
或者，通过引入 let id = fun x -> x
let f = id id
你可能会看到，这里的f不是句法值，虽然id是句法值。但是为了获得 f 的值，您需要计算 - 因此该值是在运行时定义的，而不是在编译时定义的。
现在，让我们对您的示例进行脱糖处理：
let x a = let x = (fun y -> y) a in x
==>
let x = fun a -> let x = (fun y -> y) a in x
我们可以看到，x是一个语法值，因为左边是一个lambda表达式。 lambda 表达式的类型是 'a -> 'a。你可能会问，为什么表达式的类型不是'_a -> '_a。这是因为只对top-level引入了取值限制，而lambda表达式还不是一个值，它是一个表达式。通俗地说，首先，在没有副作用的假设下推断出最一般的 Hindley-Milner 类型，然后通过（宽松的）值限制削弱推断出的类型。类型推断的范围是 let 绑定。
这都是理论，有时并不清楚为什么有些表达式是 well-type，而语义相同但写法略有不同的表达式不是很好的类型。直觉可能会说，这里有问题。是的，事实上，let f = id id 是一个被类型检查器拒绝的 well-formed 程序，这是 over-approximation 的一个例子.如果我们将这个程序转换为 let f x = id id x 它突然变成一个具有通用类型的类型良好的程序，尽管转换不会改变语义（并且两个程序实际上被编译为相同的机器代码）。这是类型系统的限制，它是简单性和精确性之间的折衷（健全性不能成为妥协的一部分——类型检查器必须是健全的）。因此，从理论上来说，为什么后一个例子总是安全的，这一点并不明显。只是为了实验，让我们尝试使用您的示例，并尝试破坏程序：
# let x = fun a -> let z = ref None in let x = (fun y -> z := Some y; y) a in x ;;
val x : 'a -> 'a = <fun>
所以，我们在这里添加了一个引用z，我们试图存储这个值，这样在不同的应用下，不同的类型，我们应该可以存储到不同的相同的引用值类型。但是完全是non-possible，因为x是句法值，所以保证了，每调用一个类型x k都会创建一个新的引用，这个引用永远不会泄露let-definition 的范围。希望这会有所帮助:)