F# CPS evaluation order

Question

I'm trying to understand the order of evaluation when using Continuation-passing style in F#. Take this function for example.

let rec CPSfunc n k c =
    if k = 0 then c 1
    else if k > 0 then CPSfunc n (k-1) (fun res -> c(2*res+k))

When running it with the arguments CPSfunc 4 3 id it evaluates to 19, but when I try to evaluate it by hand, I get different results, based on evaluating forward or backwards first.

CPSfunc 4 3 (fun res -> res)
CPSfunc 4 2 (fun res -> fun 2*res+3 -> res)
CPSfunc 4 1 (fun res -> fun 2*res+2 -> fun 2*res+3 -> res)
// Evaluating backwards
fun res -> fun 2*res+2 -> fun 2*res+3 -> 1
fun res -> fun 2*res+2 -> 2*1+3
fun res -> 2*5+2
// Evaluating forward
fun 1 -> fun 2*res+2 -> fun 2*res+3 -> res
fun 2*1+2 -> fun 2*res+3 -> res
fun 2*4+3 -> res
4

How do I properly calculate the correct output?

As given, F# infers the type of `CPSfunc` to `'a -> int -> (int -> unit) -> unit`, which then means that `CPSfunc 4 3 id` doesn't type-check. Did you leave out an `else` branch? — Mark Seemann, Apr 11 '22 at 15:40

Brian Berns · Accepted Answer · 2022-04-11T16:20:53.497

To see that 19 is the correct result, I think it's easiest to start with k = 0 and increment. Each result is simply twice the previous result, plus k. (Note that n is not used.) So we have:

k = 0 ->     1     =  1
k = 1 -> 2 * 1 + 1 =  3
k = 2 -> 2 * 3 + 2 =  8
k = 3 -> 2 * 8 + 3 = 19

Converting that simple logic into continuations gets complicated, though. Here's what the expansion looks like in F# for CPSfunc 4 3 id:

// unexpanded initial call
let c3 = (fun res -> res)
CPSfunc 4 3 c3

// expanded once, k = 3
let c2 = (fun res -> c3 (2 * res + 3))
CPSfunc 4 2 c2

// expanded again, k = 2
let c1 = (fun res -> c2 (2 * res + 2))
CPSfunc 4 1 c1

// expanded again, k = 1
let c0 = (fun res -> c1 (2 * res + 1))
CPSfunc 4 0 c0

// full expansion, k = 0
c0 1

P.S. To make c have the desired int -> int signature, you need to define CPSfunc slightly differently, so that's what I assume you've actually done:

let rec CPSfunc n k c =
    if k = 0 then c 1
    elif k > 0 then CPSfunc n (k-1) (fun res -> c(2*res+k))
    else failwith "k < 0"

Thank you, this makes sense! And you're right, I forgot to include the failwith statement in the post — Bassusour, Apr 11 '22 at 16:33

score 2 · Answer 2 · answered Apr 11 '22 at 16:33

CPSfunc 4 3 id
CPSfunc 4 2 (fun res -> id(2*res+k))
CPSfunc 4 2 (fun res -> 2*res+3)
CPSfunc 4 1 (fun res -> (fun res -> 2*res+2)(2*res + k))
CPSfunc 4 1 (fun res -> (2*(2*res + 2)+3))
CPSfunc 4 0 (fun res -> (fun res -> (2*(2*res + 2)+3))(2*res + k))
CPSfunc 4 0 (fun res -> 2*(2*(2*res+1) + 2)+3))
(fun res -> 2*(2*(2*res+1) + 2)+3)(1)
2*(2*(2*1+1)+2)+3
19

actually ive taken some liberties by evaluating some functions in the above before they would actually be evaluated, but it doesnt really matter

F# CPS evaluation order

2 Answers2