--- #scheme --- 13:51 Xcalibor - Are you still here, and do you still want help with a CPS factorial? 13:52 Riastradh: yup :) 13:53 What was your answer to my question about knowing anything about writing things in CPS? 13:54 Riastradh: i know a little bit 13:54 but really little 13:54 i think i know what's a continuation, but I have trouble thinking in terms of them 13:55 OK, so, first of all, I guess I ought to explain continuations in general. 13:55 ooh, goodie 13:55 When you have a function call (f (g x)), there are two continuations involved: the continuation of G and the continuation of F. 13:56 The continuation of G might be notated as hole: (f []) 13:56 When G returns a value Y, it puts that value into the continuation: (f [y]) or just (f y). 13:56 aha 13:56 (the square brackets aren't syntax in Scheme; they're just a way to notate the hole) 13:57 Likewise, when F returns, it puts a value into its own continuation. 13:57 right 13:57 But F's continuation is uninteresting to us right now. 13:57 okis 13:57 Would you rather that I explain call/cc or CPS now? 13:57 more about call/cc! 13:57 as you see fit 13:58 OK, I shall explain call/cc. 13:58 ok 13:58 though I understand the principle, certain things still bother me 13:58 The continuation as notated by a hole is, as I said, not really Scheme, and as such you can only look at continuations with your eyes and not deal with them in code. 13:58 Sometimes, you _do_ want to deal with them in code, though. 13:59 oh, Riastradh, i see know... CPS is not related to call/cc (CPS is the programs with the extra k parameter for the continuation to move around...) 13:59 For this reason, there is the call-with-current-continuation procedure, often shortened to call/cc. 13:59 CPS is related to call/cc, but I'll get to that. 13:59 cool 13:59 (my question was really 'which order would you rather that I explain them in?') 14:00 call/cc takes one argument, a receiver or a consumer argument. 14:00 That argument should itself take one argument. 14:00 The argument to the receiver is another procedure, but in this case, it's a rather special procedure. 14:00 should or must? 14:01 If it doesn't, a wrong number of arguments error will be signalled. 14:01 gotcha 14:01 Now, if you call (f (g x)), G is going to just return ordinarily and put a value into its continuation. 14:02 However, if you instead did (f (call/cc (lambda (k) ))), then you could call K and directly put a value into the continuation of (call/cc ...). 14:02 K puts its arguments into the continuation of where you called call/cc. Does that make sense? 14:02 ahh, gotcha 14:02 i.e. if you did: (f (call/cc (lambda (k) (k 5)))), that would put 5 into the [] in (f []), making (f [5]), or just (f 5). 14:02 right into the lambda? 14:03 What do you mean 'right into the lambda?' 14:03 aha, i meant that, inside the (lambda (k) ...) 14:03 ? 14:04 the k in the lambda that call/cc is fed with becomes its continuation, and as that lambda just makes (k 5) we get (f 5)? 14:05 because f is the continuation of the (call/cc ...)? 14:05 (note: you could also do something like (let ((foo (lambda (k) ))) (f (call/cc foo))) 14:05 No, F is not the continuation of the call to call/cc, but rather the [] in (f []) is. 14:06 mm... the [] is the continuation and (f []) is the context where it's executed? 14:06 Rephrase, please. 14:06 but why is 5? because the (k 5) in the lambda body? 14:07 sorry, english is not my first language and sometimes i mess it up big 14:07 In a function call (f (g x)), there are two continuations; the interesting continuation is the continuation of G, which we shall notate as a hole, []: (f []) 14:07 I mean, the call/cc makes the whole G call to return a 5 value because inside there's a (k 5) call? or is it some kind of let binding? 14:08 (in this example, G is call/cc, and X is (lambda (k) (k 5))) 14:08 Riastradh: ok, and... ah, ok, I see now 14:09 That simple example is no different from (f (call/cc (lambda (k) 5))), which is in fact no different from (f 5), because you're calling K to put a value into a continuation that you would put a value into _anyways_. 14:10 That is to say, (f (call/cc (lambda (k) (k 5)))) by calling K puts 5 into the [] in (f []); (f (call/cc (lambda (k) 5))) simply returns 5 into the [] in (f []). 14:10 aha... 14:10 Make sense? 14:10 yes... 14:10 Good. 14:10 but it puts 5 into the [] because of the code (k 5) inside the lambda, right? 14:10 Right. 14:10 cool 14:10 got it :-) 14:11 thanks... please go on :) 14:11 Now, suppose we were to write (f (call/cc (lambda (k) (+ 1 (k 5))))). 14:11 so, a simple function that returns a value is also a continuation? 14:11 K immediately puts 5 in the continuation of F's argument, so it immediately becomes (f [5]) or just (f 5). 14:12 The call to + never happens. 14:12 aha... because the continuation is inmediate, right? 14:12 Yes. You just put a 5 into the hole, and so now there's a value for F to deal with, and so it calls F, and control flow goes on with that. 14:13 i mean, the substitution... 14:13 This sort of example is called a 'non-local exit.' 14:14 You can emulate things like C's 'return' with it. 14:14 what happens to the (1 + _) code? 14:14 Nothing. 14:14 It's forgotten. 14:14 isn't (+ 1 _) the continuation of (k 5)? 14:14 (he has a point) 14:14 I guess that's what makes k special 14:15 Yes, but K itself never returns: it puts a value into the hole in (f []), and control flow goes on from there. 14:15 Yes, (+ 1 _ ) is the continuation of (k 5), but we never apply it 14:15 mmm... ok, never executed... is it eval'ed? (if I put (+ (/ 1 0) (k 5)) will it bump an error? 14:16 executed and evaled are different terms for the same thing 14:16 It may, but it also may not. It's unspecified by R5RS whether the (/ 1 0) or (k 5) shall be evaluated first. 14:16 ok, we should need another call/cc inside the lambda to make that continuation to be done and the substitution put inside the first lambda, I guess... 14:16 Riastradh: ok, swo "don't do that" right? :-) 14:17 I always thought scheme was evaluated left to right 14:17 this changes things 14:17 palomer: the order of evaluation is unspecified 14:17 I'll get to how you could get the call to + to happen. 14:17 Riastradh: ok, then please go on where you left it 14:17 Because K is just an ordinary procedure, you can manipulate it like an ordinary procedure. 14:18 You can pass it as arguments to other functions or even return it from the receiver. 14:18 sarahbot: eval (+ (begin (display #\a) 1) (begin (display #\b) 2)) 14:18 ba3 14:18 (call/cc (lambda (k) k)) is a perfectly valid use of call/cc. 14:18 mmm... interesting 14:19 what does call/cc return? 14:19 (f (call/cc (lambda (k) k))) will apply F to a procedure that puts its argument into the hole in (f []) -- i.e. you can call that procedure any number of times and jump back to (f []). 14:19 palomer, whatever the receiver returns. 14:19 (call/cc (lambda (k) 5)) returns 5. 14:19 palomer: or whatever is applied to the continuation 14:19 gotcha 14:20 (lambda (k) (k 5)) also returns 5! 14:20 it's identical in this case 14:20 palomer: remember, the continuation argument to the lambda passed to call/cc *is* the continuation of the call/cc expression itself, so returning a value from the lambda and applying the continuation are exactly the same thing 14:21 Since you can grab the continuation and then deal with it elsewhere, you might do: (f (call/cc (lambda (k) (+ 1 (call/cc (lambda (k*) (k k*))))))). 14:21 When it gets to the second call/cc, and the call to K, it immediately puts K*, which will return to the [] in (+ 1 []), into the [] in (f []) 14:21 ahhh, gotcha 14:22 Riastradh: nice :-) 14:22 erm, isn't that (f (+ 1 k*))? 14:22 that looks like what i commented before, so i'm hopefully not too far from the good path :) 14:23 Then F can call K* with, say, 5, and that will become (f (call/cc (lambda (k) (+ 1 [5])))), and then that will end up being (f 6), because the receiver will do (+ 1 5) and that's what F will be applied to. 14:23 palomer, huh? 14:23 oh no, its (f k*) 14:23 Yes. 14:24 Note that this is very different from a non-local exit. 14:24 Its a non-local *entrance*. 14:24 and if f is (lambda (k) (k 5)) you get 6! 14:24 You can do really complex stuff with this sort of thing, like implement coroutines. 14:24 palomer, no, you get the error of trying to call 6. 14:24 erm? 14:25 sarahbot: eval (let ((f (lambda (k) (k 5)))) (f (call/cc (lambda (k) (+ 1 (call/cc (lambda (k*) (k k*)))))))) 14:25 Error: attempt to apply non-procedure '6'. 14:25 why? 14:25 When you call (k 5) in F, you jump back to (+ 1 [5]). That returns 6, which is the return value of the first receiver, which in turn is the return value of the original call/cc. 14:25 That ends up being (f 6). 14:26 F applies its argument to 5. 14:26 ah yes 14:26 true 14:26 It therefore applies 6 to 5. 14:26 6 cannot be applied. 14:26 erm, isn't this a little obfuscated? 14:26 or is it regular run of the mill scheme code? 14:26 call/cc can produce very obfuscated code, yes. 14:26 ok... after defining call/cc in mit scheme, I do this: 14:26 (define f (lambda (x) x)) 14:27 (f (call/cc (lambda (k) (+ 1 (call/cc (lambda (k*) (k k*))))))) 14:27 call/cc can be used as harmfully as goto, but the difference is that call/cc is more powerful and it _can_ be cleaner. 14:27 ;Value 1: #[continuation 1] 14:27 Yes, Xcalibor -- F is returning K*. 14:27 so I get a continuation, as expected... 14:27 Yup. 14:27 Riastradh: how can I apply it to an argument now? 14:27 Xcalibor: store it in a variable and then apply it 14:27 Well, if, in MIT Scheme, you can grab the last printed value, then apply that. 14:28 Or do something like: (define k (f (call/cc (lambda (k) (+ 1 (call/cc (lambda (k*) (k k*)))))))) 14:28 (or maybe you should call it K** or something to avoid confusion) 14:29 What happens when you call K**, or whatever you just defined, with an argument of 5, now? 14:29 (define h (f (call/cc (lambda (k) (+ 1 (call/cc (lambda (k*) (k k*)))))))) 14:29 but (h 3) doesn't seem to work... 14:29 What does it do? 14:30 1 ]=> (h 3) 14:30 ;Value: h 14:30 whats f defined as? 14:30 Xcalibor: it works fine 14:30 But its not working how you think it is 14:30 the identity lambda? 14:30 yup 14:30 What is the continuation of (f ...) in the define you mentioned above? 14:30 ah, great 14:30 of course, the identity lambda returns h 14:31 It returns to (define h []). 14:31 wouldn't (h 3) set h to 4? 14:31 Yes 14:32 try evaluating h in mit scheme now 14:32 Riastradh: have you mentioned schemerepl yet? 14:32 No. 14:32 * Riastradh points at #schemerepl --- #schemerepl --- 14:32 -!- Riastradh [~user@pool-141-154-234-119.bos.east.verizon.net] has joined #schemerepl 14:33 -!- Xcalibor [~wiki@159.Red-81-40-162.pooles.rima-tde.net] has joined #schemerepl 14:33 (define f (lambda (x) x)) 14:33 (define f (lambda (x) x)) 14:33 (define k** (f (call/cc (lambda (k) (+ 1 (call/cc (lambda (k*) (k k*)))))))) 14:33 (k** 3) 14:33 k** 14:33 4 --- #scheme --- 14:33 no offence, but I never seen a use for all this, except as a generator 14:33 It has many uses, but they are rare compared to most code 14:33 palomer, coroutines are a common use of call/cc. 14:33 non-local exits are frequently used 14:33 non-local exits I can understand 14:33 I've used it for backtracking on several occasions too 14:34 ah 14:34 ok 14:34 ok, got it!!!! :-) 14:34 e.g., backtracking with AMB. 14:34 amb is fun:o) 14:34 Implementing exception systems, and returnable exceptions, can be done with call/cc. 14:35 Now, to CPS. 14:35 In most code, continuations are implicit. 14:35 We had to use a special notation for the continuation of G -- (f []). 14:35 violating encapsulation can be done with it! :) 14:36 Riastradh: cps, ok :) 14:36 CPSifying is making continuations explicit -- passing them explicitly, to be precise. 14:36 To CPSify (f (g x)), we would write: (g x (lambda (y) (f y))) 14:37 Instead of ordinarily returning, G would call its second argument with its return value. 14:37 where g is a continuation? 14:37 No, (lambda (y) (f y)) is the continuation. 14:37 G is just like it was before we CPSified it, except now it takes another argument, an explicit continuation. 14:38 ohmy, but the CPSified code won't do the same thing 14:38 Yes it will. 14:38 * Riastradh puts palomer into #schemerepl to demonstrate. --- #schemerepl --- 14:38 -!- palomer [~user@MTL-ppp-153689.qc.sympatico.ca] has joined #schemerepl 14:38 #flood for scheme? 14:38 #f 14:38 Error: undefined variable 'lood'. 14:38 Error: undefined variable 'for'. 14:38 Error: undefined variable 'scheme?'. 14:38 ; No, a REPL on IRC. 14:38 ; oh 14:39 (define f (lambda (y) (* y 2))) 14:39 (define g (lambda (x) (+ x 3))) 14:39 ; G is the ordinary G, with implicit continuations. 14:39 (f (g 1)) 14:39 8 14:39 (define g-cps (lambda (x k) (k (+ x 3)))) 14:40 ; G-CPS has an explicit continuation, which it calls to 'return' a value. 14:40 (g-cps 1 (lambda (y) (f y))) 14:40 8 14:40 ; ahh, so it's with a different g 14:40 ; I understood it as the same g --- #scheme --- 14:40 example understood 14:41 Suppose you CPSify _everything_. 14:41 Then everything has explicit continuations. 14:41 -- in which case you don't actually need call/cc, because the continuations are already there, and already explicit. 14:42 nod 14:42 hrm? 14:42 but how did you get g-cps on #schemerepl? are there any guidelines or something? 14:42 There's a pretty simple transformation process. 14:43 But in the case of G-CPS, it was rather simple: instead of return, call K with the result. 14:43 To make it explicit without CPS, I might have written: (define g (lambda (x) (call/cc (lambda (k) (k (+ x 3)))))) 14:43 mmm... I see... you pass the continuation explicitely in g-cps by calling the function... 14:44 But because the continuation is already there, call/cc isn't necessary. 14:44 i'll have to brood over this 14:44 CPS may not seem useful at first. 14:45 And in fact your code would look very odd indeed if you CPSified everything by hand. 14:45 But it's very useful to conceptualize about control flow. 14:45 And it's a very useful intermediate format in compilers, as demonstrated by Rabbit and Orbit. 14:45 so it's something to know that exists 14:45 and is useful to implement your own scheme 14:46 Now, let me use an example of how one might conceptualize with CPS: 14:46 one thing I still understand about continuations 14:46 Using CPS instead of the stack for your accumulator, which is what started this whole discussion. 14:46 something that bothers me 14:46 nod... we still ahve the factorial to be written... 14:46 if you call the continuation of f 14:47 Wait a moment. 14:47 let me give it a try in #schemerepl 14:47 then it will execute f, and will follow the train of thought until the toplevel, at which point it will return to the place you called the continuation 14:47 What do you mean 'call the continuation of F?' 14:47 (f 4) right? 14:47 erm, (call/cc (lambda (k) (set! foo k))) 14:47 ...(later on) 14:47 (k 5) 14:48 Do you mean (foo 5)? 14:48 yes, (foo 5) 14:48 You have to think down one more layer 14:48 OK. It will jump back to the continuation of that original call to call/cc. 14:48 mmm... okay, i dunno where to start :-) 14:48 Whats the continuation of typing an expression at the repl? 14:48 Xcalibor, I'll get to writing a CPS factorial. 14:48 then it will follow the control flow until the top level 14:48 and then return to the expression after (foo 5) 14:49 FoxFire: that's my question:o) 14:49 palomer: whats the continuation of EVAL in READ-EVAL-PRINT-LOOP 14:49 READ? 14:49 PRINT 14:49 So, it will print the result of the continuation foo, then loop 14:49 which is how you find yourself back at a prompt 14:49 (loop (print(eval(read x)))) ? 14:50 Riastradh: cool, it will serve as a good example to study 14:50 exactly 14:50 true 14:50 ahh, I understand everything 14:50 that's what I love about scheme, it's possible to understand the totality of the system 14:50 impossible in all other programming languages I know 14:51 Eventually yes. The beauty is really how it all fits together coherently, which is what I think you mean. --- #schemerepl --- 14:49 (define fact-orig (lambda (n) (if (< n 1) 1 (* n (fact-orig (- n 1)))))) 14:49 (fact-orig 5) 14:49 120 14:49 ; ok, this is the normal, not tail-recursive one 14:49 ; Yes. 14:50 ; Because you haven't seen any iterative CPS functions yet, I'll just write it out for you. I'll give you some other examples to CPSify, though. 14:51 ; great, i'll get to them diligently :) 14:51 (define (fact-cps n) (fact-cps-iter n (lambda (x) x))) ;; That (lambda (x) x) is the final continuation that will be called. It simply returns its argument, and that will be what FACT-CPS returns. 14:51 (define (fact-cps-iter n k) 14:51 (if (< n 1) 14:51 (k 1) 14:52 (fact-cps-iter (- n 1) 14:52 (lambda (r) (k (* n r)))))) 14:52 Now, it looks confusing at first, no doubt. 14:52 Error: undefined variable 'now\,'. 14:52 Error: undefined variable 'it'. 14:52 Error: undefined variable 'looks'. 14:52 Error: undefined variable 'confusing'. 14:52 Error: undefined variable 'at'. 14:52 ; Oops. 14:52 Error: undefined variable 'first\,'. 14:52 Error: undefined variable 'no'. 14:52 Error: undefined variable 'doubt.'. 14:52 ; oops :) ok, it looks like the tail-recursive version, only a bit more complex... 14:53 ; But note the similarity between FACT-CPS-ITER and FACT-ORIG. 14:53 ; i mean, the (lambda (r) (k (* n r))) is the accumulator (or works like it) 14:53 ; Instead of writing (* n (fact-ORIG (- n 1))), you're recurring with a continuation that does that. 14:54 ; xcal: Yes, but thats exactly what the stack is in all languages, its an accumulator for 'whats next' 14:54 ; mmm... well, yes 14:54 ; (lambda (r) (k (* n r))) -- R is the result of (fact-orig (- n 1)), or, more accurately, R is the next factorial to multiply the current N by. 14:55 ; (fact-cps-iter (- n 1) (lambda (r) (k (* n r)))) is just a rearrangement of (* n (fact-orig (- n 1))), in fact: all you're doing is making the continuation explicit, like in G-CPS. 14:55 ; Does that make sense? 14:56 ; mmm... why is it? fact-cps-iter applies n and k, which are (- n 1) and (lambda ...) how is it that R is (fact-orig (- n 1))? 14:56 (g-cps 1 (lambda (y) (f y))) 14:56 8 14:57 ; ah... yes, it's the same you wrote... 14:58 ; so the tail-recursive (non-CPS) version is a special case of this one where the continuation is in fact a single identity on the accumulator parameter? 14:58 ; Imagine R as Y. G-CPS returns Y; FACT-CPS-ITER returns R. After G-CPS returns Y, you apply F to Y; after FACT-CPS-ITER returns R, you apply the next continuation to (* n r). The only difference is that you're recurring with FACT-CPS-ITER while you're just calling F with G-CPS. 14:58 ; The identity function is only the last continuation. 14:58 ; i mean, we can write 15:00 (define (fact-tr-iter n m) (if (< n 1) m (fact-tr-iter (- n 1) (* n m)))) 15:00 (define (fact-tr n) (fact-tr-iter n 1)) 15:00 (fact-tr-iter 5) 15:00 120 15:00 (fact-cps 5) 15:00 120 15:01 ; it looks exactly the same as the CPS except for the identify and the last call to K with R, right? 15:03 ; It may look similar, but it's in fact rather different. FACT-ORIG versus FACT-CPS-ITER is just implicit versus explicit continuations. FACT-TR-ITER is a different algorithm, really, that just happens to vaguely resemble FACT-CPS-ITER. 15:04 ; ok... just surface similarity... 15:05 http://www.haskell.org/hawiki/CpsTransform 15:05 Error: undefined variable 'http://www.haskell.org/hawiki/cpstransform'. 15:05 ; Whoops, that should have gone into my #scheme buffer, anyways. 15:10 ; no prob... :-)