I wonder if it is possible to define a recursive function without calling the function itself in its body but somehow using call/cc instead? Thanks.
3 Answers
You can implement a Y combinator using call/cc, as described here. (Many thanks to John Cowan for mentioning this neat post!) Quoting that post, here's Oleg's implementation:
Corollary 1. Y combinator via
call/cc-- Y combinator without an explicit self-application.(define (Y f) ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n))))) (call/cc (call/cc (lambda (x) x)))))Here, we used a fact that
((lambda (u) (u p)) (call/cc call/cc))and
((lambda (u) (u p)) (lambda (x) (x x)))are observationally equivalent.
2 Comments
day
Amazing, exactly what I want. Thanks a lot.
C. K. Young
@wberry I've decided to find a way to quote that code snippet that's hopefully more "fair use"-compliant.
Your question is a bit vague. In particular, it sounds like you want a system that models recursive calls without directly making recursive calls, using call/cc. It turns out, though, that you can model recursive calls without making recursive calls and also without using call/cc. For instance:
#lang racket
(define (factorial f n)
(if (= n 0) 1 (* n (f f (- n 1)))))
(factorial factorial 3)
That may seem like cheating, but it's the foundation of the Y combinator. Perhaps you can tighten up the set of restrictions you're thinking of?
P.S.: if this is homework, please cite me!
6 Comments
day
Well, I have already known this trick to do recursion. What I wonder is if a non-self-referring way using call/cc exists to define a recursive function, say your
factorial. This is not a homework exercise! Thanks.
Sam Tobin-Hochstadt
@plmday John's solution is already not self-referencing. What more would you need from
call/cc?day
@SamTobin-Hochstadt Well, it is,
f refers to itself, doesn't it? I wanna see how far we can go with call/cc, in particular, given its ability, can we employ it to simulate the usual or unusual way of defining a recursive function.
Luis Casillas
What do your mean by "refer to itself"? Self-reference in a (self-) recursive function definition is of this form: you have a function definition whose body contains an occurrence of an identifier that's lexically bound to the enclosing function itself. The definition of
factorial that John provides does not have factorial appearing in the body, nor any identifier that's lexically bound to it.day
Ah, OK, you are right. I mixed it with self-application. Thanks for clarifying it.
|
I'm afraid call/cc doesn't really have much to do with this. There really are only two ways of defining a recursive function:
- Suppose your language allows recursive function definitions; i.e., a function body can refer to the enclosing function, or the body of a function
fcan refer to a functiongwhose body refers tof. In this case, well, you just write it in the usual way. - If your language forbids both of these, but it still has first-class functions and lambdas, then you can use a fixed-point combinator like the Y combinator. You write your function so that it takes as an extra argument a function that's meant to represent the recursive step; every place where you would recurse, instead you invoke that argument.
So for factorial, you write it like this:
(define (factorial-step recurse n)
(if (zero? n)
1
(* n (recurse (- n 1)))))
The magic of the Y combinator is that it constructs the recurse function that would be fed to factorial-step.
Comments
