functional-programming - 在Continuation Passing样式中定义定点组合器-6ren

functional-programming - 在Continuation Passing样式中定义定点组合器

转载作者：行者123 更新时间：2023-12-04 03:57:13

25

4

fix-point combinators是引入递归的非常有用的工具。

Continuation-Passing style是lambda演算的一种样式，函数从不返回。相反，您将程序的其余部分作为lambda参数传递给函数，然后继续执行它们。它使您可以更好地控制执行流程，并更轻松地定义各种更改流程的构造(循环，协程等)。

但是，我想知道您是否可以互相表达？我见过的所有CPS风格的语言都有一个明确的 FIX构造来定义递归。

是因为没有FIX不可能在普通CPS中定义定点组合器吗？如果是这样，您知道这种事情的证据吗？

还是仅由于键入问题？

也许有可能，但是由于某种原因不切实际？

还是我根本没有找到解决方案……？

我希望像Y组合器的CPS函数 CPSY可以这样工作:
如果我定义了一个支持Y的CPS功能，例如:

function Yready(this, return) = 
    return (lambda <args> . <body using 'this' as recursion>);

然后，我将其放入 CPSY中以产生一个递归到其自身中的函数:

function CPSY(F, return) = ?????

CPSY(Yready,
    lambda rec . <body where 'rec' names 'lambda <args>' from above, but with the loop closed>
)

CPSY应该是一个简单的连续传递样式函数，而本身不依赖任何递归。可以在没有内置递归的情况下以纯lambda演算定义Y组合器。它也可以某种形式存在于CPS中吗？

重申一下:我正在寻找类似组合器的函数 CPSY:

将启用CPS函数的递归

它的定义不依赖于递归

以连续传递样式给出它的定义(在CPSY体内的任何地方都没有返回的lambda)

最佳答案

首先，让我们得出CPS-Y以便在Lambda演算中进行正序评估，然后将其转换为应用阶。

Wikipedia page通过以下公式定义定点组合器Y:

Y f = f (Y f)

在CPS形式中，此等式看起来像这样:

Y f k = Y f (λh. f h k)

现在，考虑以下Y的非CPS正态定义:

Y f = (λg. g g) (λg. f (g g))

将其转换为CPS:

Y f k = (λg. g g k) (λg.λk. g g (λh. f h k))

现在，使用beta减少此定义几次，以检查它是否确实满足上述“CPS定点”条件:

Y f k = (λg. g g k) (λg.λk. g g (λh. f h k))
      = (λg.λk. g g (λh. f h k)) (λg.λk. g g (λh. f h k)) k
      = (λg.λk. g g (λh. f h k)) (λg.λk. g g (λh. f h k)) (λh. f h k)
      = Y f (λh. f h k)

瞧!

现在，对于应用顺序评估，我们当然需要对此稍作更改。此处的推理与非CPS情况下的推理相同:我们需要“简化”递归 (g g k)调用，仅在下次调用时继续进行:

Y f k = (λg. g g k) (λg.λk. f (λx.λk. g g (λF. F x k)) k)

这是直接转换为 Racket :

(define (Y f k)
  ((λ (g) (g g k))
   (λ (g k) (f (λ (x k) (g g (λ (F) (F x k)))) k))))

我们可以检查它是否确实有效—例如，这是CPS中的递归三角数计算(为简单起见，算术运算除外):

(Y (λ (sum k) (k (λ (n k) (if (< n 1)
                              (k 0)
                              (sum (- n 1) (λ (s) (k (+ s n))))))))
   (λ (sum) (sum 9 print)))
;=> 45

我相信这可以回答问题。

关于functional-programming - 在Continuation Passing样式中定义定点组合器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35918279/

25

4

0

文章推荐： scala - Spark SQL 未正确转换时区

文章推荐： r - 如何在 R 中最好地结合独特和匹配？

文章推荐： mongodb - 如何在 MongoDB 中填充嵌套的引用数组？

function - 命名空间::function cannot be used as a function
main.cpp #include "Primes.h" #include int main(){ std::string choose; int num1, num2; w
c - 为什么调用此函数会产生错误 " is not a function or function pointer"？
似乎函数 qwertyInches() 应该可以工作但是当我在 main() 中调用它时它给了我 [Error] called object 'qwertyInches' is not a funct
c++ - object.function().function().function().......这是如何工作的？
我无法理解 C++ 语法的工作原理。 #include using namespace std; class Accumulator{ private: int value; public:
function - dart 中的 Function() 和 Function 有什么区别？
在类中声明函数成员时，我们可以同时执行这两种操作； Function first; Function() second; 它们之间有什么区别？最佳答案 Function 代表任意函数: void
jquery错误: a function is not a function?
“colonna”怎么可能是一个简单的字符串: $('td.' + colonna).css('background-color','#ffddaa'); 可以正确突出显示有趣单元格的背景，并且: $
javascript - 如何将传递到 function() 的动态参数中继到 function() 中调用的 function()
我正在尝试将网页中的动态参数中继到函数中，然后函数将它们传递给函数内部的调用。比如下面这个简化的代码片段，现在这样，直接传入参数是没有问题的。但是，如何在不为每个可能的 colorbox 参数设置 s
C++ Lambdas : function that returns a function that returns a function . ..？
C++ 中是否有一种模式允许您返回一个函数，它返回一个函数本身。例如 std::function func = ...; do { func = func(); } while (func);
c - 错误 : function declared as function returning function
我正在将 Windows 程序集移植到 Linux。我有一些代码要移植。我实际上是 linux 中 C 的新手。我知道 C 基础知识是一样的! typedef struct sReader {
javascript - 何时使用 function() 、 function 或 () => function(callback)
我一直在寻找一个很好的解释，所以我很清楚。示例: this.onDeleteHandler(index)}/> 对比对比 this.nameChangedhandler(event, perso
javascript - 为什么 function(){}.__proto__ === Function.prototype 和 Function.prototype === function(){}.__proto_ 返回不同的结果
function(){}.__proto__ === Function.prototype 和 Function.prototype === function(){}.__proto__ 得到不同的结
javascript - 'Function' 上的 MDN 描述感到困惑，Function.length 是 Function 或 Function.prototype 的属性
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function 据说 Propert
function - Excel VBA : Special Types - Functions as Arguments of Functions
VBA 中的函数没有特殊类型。我很难理解如何在 Excel VBA 中将函数作为参数添加到函数中。我想要完成的是这样的事情: function f(g as function, x as strin
r - Tidyeval in own functions in own functions inside own functions with the pipe 管道
所以我正在尝试制作一个包(我没有在下面包含我的 roxygen2 header ): 我有这个功能: date_from_text % dplyr::mutate(!!name := lubr
c++ - 从 std::function 继承构造函数时为 "function returning a function"
尝试从 std::function 派生一个类，对于初学者来说，继承构造函数。这是我的猜测: #include #include using namespace std; template cla
javascript - 错误: function is not defined when calling a function returned by another function
我正在尝试编写一个返回另一个函数的函数。我的目标是编写一个函数，它接受一个对象并返回另一个函数“search”。当我使用键调用搜索函数时，我想从第一个函数中给定的对象返回该键的值。 propertyO
functional-programming - "Functional programming"有明确的含义，但是 "functional language"吗？
我非常清楚函数式编程技术和命令式编程技术之间的区别。但是现在有一种普遍的趋势是谈论“函数式语言”，这确实让我感到困惑。当然，像 Haskell 这样的一些语言比 C 等其他语言更欢迎函数式编程。但即
JavaScript美学: "function foo() {}" vs "var foo = function() {};" in AMD functions
关闭。这个问题是opinion-based 。目前不接受答案。想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 . 已关闭 8 年前。 Improv
javascript - Function.call、Function.prototype.call、Function.prototype.call.call 和 Function.prototype.call.call.call 之间的区别
我在stackoverflow上查过很多类似的问题，比如call.call 1 , call.call 2 ，但我是新人，无法发表任何评论。我希望我能找到关于 JavaScript 解释器如何执行这些
google-cloud-functions - 从 Cloud Function 本身获取 Cloud Function 名称
向 Twilio 发送 SMS 时，Twilio 会向指定的 URL 发送多个请求，以通过 Webhook 提供该 SMS 传送的状态。我想让这个回调异步，所以我开发了一个 Cloud Functio
azure-functions - 如何获取使用 Terraform 部署的 Function-App 中的 "Function Url"？
作为 IaC 的一部分，A 功能应用，让我们将其命名为 FuncAppX 是使用 Terraform 部署的，它有一个内置函数。我需要使用 Terraform 在函数应用程序中访问相同函数的 Ur

首页

博学

6Ren·AI

商城

functional-programming - 在Continuation Passing样式中定义定点组合器