Can any case of using call/cc be rewritten equivalently without using it?

Question

Can any case of using call/cc be rewritten equivalently without using it?

For example

1. In (g (call/cc f)), is the purpose of f to evaluate the value of some expression, so that g can be applied to the value?

   Is (g (call/cc f)) always able to be rewritten equivalently without call/cc e.g. (g expression)?

2. In ((call/cc f) arg), is the purpose of f to evaluate the definition of some function g, so that function g can be applied to the value of arg?

   Is ((call/cc f) arg) always able to be rewritten equivalently without call/cc e.g. (g arg)?

If the answers are yes, why do we need to use call/cc? I am trying to understand the purpose of using call/cc, by contrasting it to not using it.

Answer 1

The key to the direct answer here is the notion of "Turing equivalence". That is, essentially all of the commonly used programming languages (C, Java, Scheme, Haskell, Lambda Calculus etc. etc.) are equivalent in the sense that for any program in one of these languages, there is a corresponding program in each of the other languages which has the same meaning.

Beyond this, though, some of these equivalences may be "nice" and some may be really horrible. This suggests that we reframe the question: which features can be rewritten in a "nice" way into languages without that feature, and which cannot?

A formal treatment of this comes from Matthias Felleisen, in his 1991 paper "On the Expressive Power of Programming Languages" (https://www.sciencedirect.com/science/article/pii/016764239190036W), which introduces a notion of macro expressibility, pointing out that some features can be rewritten in a local way, and some require global rewrites.

Answer 2

The answer to your original question is obviously yes. Scheme is Turing-complete, with or without call/cc, so even without call/cc, you can still compute anything that is computable.

Why "it is more convenient than writing the equivalent expression using lambda"?

The classic paper On the Expressive Power of Programming Languages by Matthias Felleisen gives one answer to this question. Pretty much, to rewrite a program with call/cc to one without it, you might potentially need to transform your whole program (global transformation). This is to contrast some other constructs that only need a local transformation (i.e., can be written as macro) to remove them.

Answer 3

The key is: If your program is written in continuation passing style, you don't need call/cc. If not, good luck.

I whole-heartedly recommend:

Daniel P. Friedman. "Applications of Continuations: Invited Tutorial". 1988 Principles of Programming Languages (POPL88). January 1988

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

If you enjoy reading that paper, then check out: https://github.com/scheme-live/bibliography/blob/master/page6.md

Answer 4

Of course anything that is written with call/cc can be written without it, because everything in Scheme is ultimately written using lambda. You use call/cc because it is more convenient than writing the equivalent expression using lambda.

Answer 5

There are two senses to this question: an uninteresting one and an interesting one:

The uninteresting one. Is there some computation that you can do with call/cc that you can't do in a language which does not have it?

No, there isn't: call/cc doesn't make a language properly more powerful: it is famously the case that a language with only λ and function application is equivalent to a universal Turing machine, and thus there is no (known...) more powerful computational system.

But that's kind of uninteresting from the point of view of programming-language design: subject to the normal constraints on memory &c, pretty much all programming languages are equivalent to UTMs, but people still prefer to use languages which don't involve punching holes in paper tape if they can.

The interesting one. Is it the case that call/cc makes some desirable features of a programming language easier to express?

The answer to this is yes, it does. I'll just give a couple of examples. Let's say you want to have some kind of non-local exit feature in your language, so some deeply-nested bit of program can just say 'to hell with this I want out', without having to climb back out through some great layer of functions. This is trivial with call/cc: the continuation procedure is the escape procedure. You can wrap it in some syntax if you want it to be nicer:

(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 ...)

Can you implement this without call/cc? Well, yes, but not without either relying on some other special construct (say block and return-from in CL), or without turning the language inside out in some way.

And you can build on things like this to implement all sorts of non-local escapes.

Or, well, let's say you want GO TO (the following example is 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)))

Or, with some syntax around this:

(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)))

So, OK, this perhaps is not a desirable feature of a programming language. But, well, Scheme doesn't have GO TO right, and yet, here, it does.

So, yes, call/cc (especially when combined with macros) makes a lot of desirable features of a programming language possible to express. Other languages have all these special-purpose, limited hacks, Scheme has this universal thing from which all these special-purpose hacks can be built.

The problem is that call/cc doesn't stop with the good special-purpose hacks: you can also build all the awful horrors that used to blight programming languages out of it. call/cc is like having access to an elder god: it's really convenient if you want dread power, but you'd better be careful what comes with it when you call, because it may well be an unspeakable horror from beyond spacetime.

Answer 6

An easy use of call/cc is as a bail out. eg.

;; (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)))))))))

So to understand this. If we are doing (double-numbers '(1 2 r)) the result is #f, but the helper has done (cons 1 (cons 2 (exit #f)))

Without call/cc we see the continuation would be whatever called double-numbers since it actually return normally from it. Here is an example without 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

I imagine it gets harder pretty quick. Eg. my generator implementation. The generator relies on having access to continuations to mix the generator code with where it's used, but without call/cc you'll need to do CPS in both the generator, the generated generator and the code that uses it.