3

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

例如

  1. 在(g (call/cc f)), 的目的是f评估 some 的价值expression，以便g可以应用于价值？

    是否(g (call/cc f))总是能够在没有call/cceg的情况下等效地重写(g expression)？

  2. 在((call/cc f) arg)中，目的是f为了评估某个函数的定义g，以便g可以将函数应用于 的值arg？

    是否((call/cc f) arg)总是能够在没有call/cceg的情况下等效地重写(g arg)？

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

4

6 回答 6

4

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

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

对此的正式处理来自 Matthias Felleisen，在他 1991 年的论文“On the Expressive Power of Programming Languages”（https://www.sciencedirect.com/science/article/pii/016764239190036W）中，引入了宏可表达性的概念，指出有些功能可以本地重写，有些则需要全局重写。

于 2019-08-06T15:50:34.180 回答
2

你原来的问题的答案显然是肯定的。Scheme 是图灵完备的，不管有没有call/cc，所以即使没有call/cc，你仍然可以计算任何可计算的东西。

为什么“它比使用 lambda 编写等效表达式更方便”？

Matthias Felleisen的经典论文On the Expressive Power of Programming Languages为这个问题提供了一个答案。几乎，要重写call/cc一个没有它的程序，您可能需要转换整个程序（全局转换）。这是为了对比其他一些只需要局部转换（即可以写成宏）来删除它们的结构。

于 2019-08-06T15:45:24.997 回答
2

关键是： 如果你的程序是用延续传递风格编写的，你就不需要call/cc. 如果没有，祝你好运。

我全心全意地推荐：

丹尼尔·弗里德曼。“延续的应用：特邀教程”。1988 年编程语言原理 (POPL88)。1988 年 1 月

https://cs.indiana.edu/~dfried/appcont.pdf

如果您喜欢阅读那篇论文，请查看： https ://github.com/scheme-live/bibliography/blob/master/page6.md

于 2019-08-06T16:42:34.533 回答
1

当然，任何用它编写的东西call/cc都可以不用它来编写，因为Scheme 中的所有东西最终都是用lambda. 您使用call/cc它是因为它比使用 编写等效表达式更方便lambda。

于 2019-08-06T13:48:51.293 回答
1

一个简单的使用call/cc是作为一种救助。例如。

;; (1 2) => (2 4)
;; #f if one element is not a number
(define (double-numbers lst)
  (call/cc
   (lambda (exit)
     (let helper ((lst lst))
       (cond ((null? lst) '())
             ((not (number? (car lst))) (exit #f))
             (else (cons (* 2 (car lst)) (helper (cdr lst)))))))))

所以要明白这一点。如果我们在做(double-numbers '(1 2 r))，结果是#f，但是助手已经做了(cons 1 (cons 2 (exit #f)))

如果没有call/cc我们看到，延续将是任何调用double-numbers，因为它实际上从它正常返回。这是一个没有的例子call/cc：

;; (1 2) => (2 4)
;; #f if one element is not a number
(define (double-numbers lst)
  (define (helper& lst cont)
    (cond ((null? lst) (cont '()))
          ((not (number? (car lst))) #f) ; bail out, not using cont
          (else (helper& (cdr lst)
                         (lambda (result)
                           (cont (cons (* 2 (car lst)) result)))))))
  (helper& lst values)) ; values works as an identity procedure

我想它会很快变得更难。例如。我的生成器实现。生成器依赖于访问延续来将生成器代码与其使用位置混合，但如果没有，call/cc您将需要在生成器、生成的生成器和使用它的代码中执行 CPS。

于 2019-08-08T09:23:21.400 回答
1

这个问题有两种意义：一种无趣和一种有趣：

无趣的那一个。是否有一些你可以用call/cc没有它的语言做不到的计算？

不，没有：call/cc不会使语言更强大：众所周知，只有 λ 和函数应用程序的语言等效于通用图灵机，因此没有（已知...）更强大的计算系统。

但从编程语言设计的角度来看，这有点无趣：受内存和 c 的正常限制，几乎所有编程语言都等同于 UTM，但人们仍然更喜欢使用不涉及打孔的语言如果可以的话，用纸胶带。

有趣的一个。是不是这种情况call/cc使得编程语言的一些理想特性更容易表达？

答案是肯定的，确实如此。我只举几个例子。假设您想在您的语言中使用某种非本地退出功能，因此一些深度嵌套的程序可以说“我想退出这个地狱”，而不必爬回一些很棒的层功能。这是微不足道的call/cc：继续过程是转义过程。如果你想让它更好，你可以用一些语法包装它：

(define-syntax with-escape
  (syntax-rules ()
    [(_ (e) form ...)
     (call/cc (λ (e) form ...))]))

(with-escape (e)
  ... code in here, and can call e to escape, and return some values ...)

你可以在没有的情况下实现这个call/cc吗？嗯，是的，但不是不依赖其他一些特殊结构（比如CL 中的blockand return-from），或者不以某种方式彻底改变语言。

你可以在这样的基础上实现各种非本地转义。

或者，好吧，假设您想要 GO TO（以下示例是 Racket）：

(define (test n)
  (define m 0)
  (define start (call/cc (λ (c) c)))
  (printf "here ~A~%" m)
  (set! m (+ m 1))
  (when (< m n)
    (start start)))

或者，使用一些语法：

(define-syntax-rule (label place)
  (define place (call/cc identity)))

(define (go place)
  (place place))

(define (horrid n)
  (define m 0)
  (label start)
  (printf "here ~A~%" m)
  (set! m (+ m 1))
  (when (< m n)
    (go start)))

所以，好吧，这可能不是编程语言的理想特性。但是，好吧，Scheme 没有 GO TO 权限，但在这里，它确实有。

所以，是的，call/cc（尤其是与宏结合使用时）可以表达编程语言的许多理想特性。其他语言有所有这些特殊用途的、有限的 hack，Scheme 有这个通用的东西，所有这些特殊用途的 hack 都可以从中构建。

问题在于，良好call/cc的特殊用途黑客并不止于此：您还可以构建所有曾经破坏编程语言的可怕恐怖。 就像接触上古之神：想要恐惧之力确实很方便，但召唤的时候要小心它带来的东西，因为它很可能是来自时空之外的无法形容的恐怖。call/cc

于 2019-08-07T13:08:54.973 回答