CODEWITHSUNDEEP
lambdaschemeracketcallcc
chamibuddhika
chamibuddhika

Reputation: 1439

Funky call/cc usage. How does it work?

Consider following definitions. I am using Racket.

(define fact/k
  (lambda (n k)
    (cond
      ((zero? n) (call/cc (lambda (f) (k f))))
      (else (* n (fact/k (sub1 n) k))))))

(define five (call/cc (lambda (k) (fact/k 5 k))))

Now if it invoked as follows

(five 1)

It gives out nothing. Having done that if five is invoked directly it gives 120.

$five

120

But if I retry (five 1) it fails saying 120 is not a procedure.

I understand that initially five points to the continuation captured at (zero? n) base case. But I am not sure how above behavior can be explained.

Another run with different parameter

$ (five 4)

$ five

480

Upvotes: 1

Views: 300

Answers (1)

Sylwester
Sylwester

Reputation: 48765

NB: You code is not allowed in the last version of #!racket without changing the language opetion. Go in Language > Choose language and uncheck "Enforce constant definitions". You'll loose some optimization wit this unchecked.

five is a continuation similar to (lambda (n) (set! five (* 5 4 3 2 1 n))) and by using two continuations you mamage to redefine five after one call. Evaluating five afterwards revieals the answer of (* 5 4 3 2 1 1) when the argument is 1 and (* 5 4 3 2 1 4) when it's 4.

Variables in Scheme/Racket does not have type but values have. That means a variable five can be a procedure/continuation first and just a number second. That is what you see happening.

EDIT To recap I rename a little: 

(define fact/k
  (lambda (n k)
    (cond
      ((zero? n) (call/cc (lambda (f) (k f))))
      (else (* n (fact/k (sub1 n) k))))))

(define five (call/cc (lambda (k) (fact/k 5 k)))) ; #1
five ; ==> #<continuation>, f to be precise         #2
(five 4)                                            #3
five ; ==> 480                                      #4

Considering marked line #1. In fact/k the default case is run for n 5..1 so you can substitute the line with (define five (call/cc (lambda (five-k) (* 5 4 3 2 1 (fact/k 0 five-k))))). Instead of fact/k returning a number it uses the continuation call with and what it passes as value is the continuation from within fact/k called f. If you then evaluate five on #2 you get the f continuation. Calling f with a numeric argument becomes the last answer to the calculation that never happened since we aborted it and returned f instead. In #3 you call five with 4 as argument. Continuations is time traveling so you're now back to (define five (call/cc (lambda (five-k) (* 5 4 3 2 1 (fact/k 0 five-k))))) where you just know that (fact/k 0 five-k) evaluated to 4. What happens next is that (* 5 4 3 2 1 4) becomes 480``and that is set tofivesince setting the variable is done *after the calculation of it's value*. On line #4 you verify thatfive` has indeed been changed from a continuation to a value. It's value is changed to one of a totally different type. You cannot call a number.

In DrRacket you can hit the debug button and step through it. I recommend you try it out.

Upvotes: 1

Related Questions