根据其自身的部分应用定义的柯里化函数

Question

以下 SML 代码取自华盛顿大学课程的家庭作业。（具体来说，它是所提供代码的一部分，以便学生可以使用它来完成课程网页上列出的作业 3上列出的作业 3。 ）我不是在这里寻求作业帮助\xe2\x80\x93我想我理解代码的含义。我不太明白的是如何允许柯里化函数根据其自己的部分应用程序来定义。

\n

 datatype pattern = \n     WildcardP\n   | VariableP of string\n   | UnitP\n   | ConstantP of int\n   | ConstructorP of string * pattern\n   | TupleP of pattern list\n\nfun g f1 f2 p =\n  let \n    val r = g f1 f2      (* Why does this not cause an infinite loop? *)\n  in\n    case p of\n        WildcardP         => f1 ()\n      | VariableP x       => f2 x\n      | ConstructorP(_,p) => r p\n      | TupleP ps         => List.foldl (fn (p,i) => (r p) + i) 0 ps\n      | _                 => 0\n  end\n

\n

函数绑定是一个递归定义，它利用 的数据类型绑定中的递归结构pattern。但是当我们到达该行时val r = g f1 f2，为什么这不会导致执行思考，“等等，这是什么g f1 f2？这就是我通过传递f2给创建的函数得到的结果。所以让我们f1回去g的定义g并进入无限循环？

\n

Answer 1

通过 lambda 演算抽象，柯里化函数g是g = (^f1. (^f2. (^p. ...body...)))这样的

g a b = (^f1. (^f2. (^p. ...body...))) a      b 
      =       (^f2. (^p. ...body...)) [a/f1] 
      =             (^p. ...body...)  [a/f1] [b/f2]

部分应用程序仅生成内部 lambda 函数，并与两个封闭的参数绑定配对——根本不进入主体。

因此，定义r = g f1 f2就像将其定义为 lambda 函数一样r = (^p. g f1 f2 p)（这又是基于 LC 的，因此不处理任何 SML 特定的内容，例如类型）。

而定义 lambda 函数（闭包）只是一个常量时间操作，它不会进入g函数体，因此根本不存在循环，更不用说无限循环了。