scheme - 是否可以在不使用 call/cc 的情况下等效地重写任何 case？

Question

任何使用call/cc 的情况都可以在不使用它的情况下等效地重写吗？

例如

1. 在(g (call/cc f))中，f的目的是求值 一些 expression，以便 g 可以应用于该值？

   (g (call/cc f)) 是否总是能够等价地重写 没有 call/cc 例如(g 表达式)?

2. 在 ((call/cc f) arg) 中，f 的目的是评估 一些函数 g 的定义，所以函数 g 可以是 应用于 arg 的值？

   ((call/cc f) arg) 是否总是能够被等价地重写 没有 call/cc 例如(g arg)?

如果答案是肯定的，为什么我们需要使用call/cc？ 我试图通过将其与不使用进行对比来理解使用 call/cc 的目的。

Answer 1

这里直接回答的关键是“图灵等价”的概念。也就是说，基本上所有常用的编程语言(C、Java、Scheme、Haskell、Lambda Calculus 等)在某种意义上都是等价的，因为对于其中一种语言的任何程序，每种语言都有相应的程序具有相同含义的其他语言。

不过，除此之外，这些等价物中的一些可能“不错”，而另一些可能真的很糟糕。这表明我们重新定义了这个问题:哪些功能可以以“很好”的方式重写为没有该功能的语言，哪些不能？

对此的正式处理来自 Matthias Felleisen，他在 1991 年的论文“关于编程语言的表达能力”(https://www.sciencedirect.com/science/article/pii/016764239190036W) 中引入了宏可表达性的概念，指出某些功能可以重写为本地方式，有些需要全局重写。