Now that ES6 supports Proper Tail Call, and since according to Wikipedia, "In any language which supports closures and proper tail calls, it is possible to write programs in continuation-passing style and manually implement call/cc.", we should be able to properly implement call/cc
in JavaScript, without using tricks to empty the call stack.
(EDIT: sadly, most web browsers don't support PTC, but we can still use the tricks described in that question)
According to this article, it should look like this:
function callcc (f,cc) {
f(function(x,k) { cc(x) },cc)
}
As I tried to understand continuations and their usecases, I wanted to implement the second example in call/cc
's page on Wikipedia in JavaScript, but failed:
;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
(define (generate-one-element-at-a-time lst)
;; Both internal functions are closures over lst
;; Internal variable/Function which passes the current element in a list
;; to its return argument (which is a continuation), or passes an end-of-list marker
;; if no more elements are left. On each step the function name is
;; rebound to a continuation which points back into the function body,
;; while return is rebound to whatever continuation the caller specifies.
(define (control-state return)
(for-each
(lambda (element)
(set! return (call-with-current-continuation
(lambda (resume-here)
;; Grab the current continuation
(set! control-state resume-here)
(return element))))) ;; (return element) evaluates to next return
lst)
(return 'you-fell-off-the-end))
;; (-> X u 'you-fell-off-the-end)
;; This is the actual generator, producing one item from a-list at a time.
(define (generator)
(call-with-current-continuation control-state))
;; Return the generator
generator)
(define generate-digit
(generate-one-element-at-a-time '(0 1 2)))
(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end
How would you do it? Is it even possible?
(EDIT: as explained in the comments, this is not a duplicate of call/CC with closures, which is about implementing call/cc in JS; my question is about implementing the Wikipedia example in JS assuming that call/cc is already implemented (with or without tricks to empty the call stack), which is not trivial)
EDIT: Here is my final working JS implementation, thanks to that answer and its comments, which put me in the right direction:
const callcc = (f,cc) => { f(cc,cc) }
const forEach = (f, lst, cc) => {
const partialForEach = (f, lst, start, cc) => {
if (start === lst.length) {
cc();
} else {
f(lst[start], () => partialForEach(f, lst, start+1, cc));
}
}
partialForEach(f, lst, 0, cc)
};
const generate_one_element_a_time = lst => {
let control_state = (ret) => {
forEach(
(element, cc) => {
callcc(
(resume_here) => {
control_state = resume_here
ret(element)
},
c => {
ret = c
cc()
}
)
},
lst,
() => ret("you-fell-off-the-end")
)
}
let generator = (cc) => {
callcc(control_state, cc)
}
return generator
}
const generate_digit = generate_one_element_a_time([0,1,2])
generate_digit(console.log) // 0
generate_digit(console.log) // 1
generate_digit(console.log) // 2
generate_digit(console.log) // you-fell-off-the-end
This code:
(define (sum-even n)
(call/cc (lambda (exit)
(let loop ((n n))
(cond ((= n 0) 0)
((< n 0) (exit 0))
(else (+ n (loop (- n 2)))))))))
(sum-even 6) ; ==> 12
(sum-even 5) ; ==> 0
So the two first uses never actually uses the continuation, but what happens is that you have this in the first (+ 6 (+ 4 (+ 2 0)))
while in the second we have (+ 5 (+ 3 (+ 1 (exit 0))))
and the inner expression just kills the rest of the calculations. That is the whole purpose of call/cc
.
Same in JavaScript:
const sumEven = (n) => {
callCc((exit) => {
const loop = (n) => {
if (n === 0) {
return 0;
} else if (n < 0) {
exit(0);
} else {
return n + loop(n - 2);
}
};
return loop(n);
});
};
sumEven(6); // 12 because 6 + 4 + 2 + 0
sumEven(5); // 0 because 5 + 3 + 1 + exit(0)
That doesn't work since JavaScipt doesn't provide callCc
. The second best would be to use rewrite it to CPS:
const callCCK = (f, k) => f((v, ignoredK) => k(v), k);
const sumEvenK = (n, ek) => {
callCCK((exitK, k) => {
const loopK = (n, k) => {
if (n === 0) {
k(0);
} else if (n < 0) {
exitK(0, k);
} else {
loopK(n - 2, loopResult => k(n + loopResult));
}
};
loopK(n, k);
}, ek);
}
sumEvenK(6, v => console.log(v)); // prints 12
sumEvenK(5, v => console.log(v)); // prints 0
When your code already is in CPS using callCc isn't really needed since instead we could write it like this:
const sumEvenK = (n, ek) => {
const loopK = (n, k) => {
if (n === 0) {
k(0);
} else if (n < 0) {
ek(0);
} else {
loopK(n - 2, loopResult => k(n + loopResult));
}
};
loopK(n, ek);
}
sumEvenK(6, v => console.log(v)); // prints 12
sumEvenK(5, v => console.log(v)); // prints 0
Since again, the whole reason why we have call/cc
in Scheme is to get the power of CPS without having to write the tedious CPS.
So there you go. You need to rewrite your generateOneElementAtATime
into CPS so that it can use the CPS version of your callcc
. Good luck!