OCaml Continuation Explained
Let start by refreshing our knowledge of tail-recursion.
Recall tail-recursion
Some common misunderstanding of tail-recursive are:
- ❌Any function with an accumulator is tail-recursive
- ❌Any function that has a inner recursive function and a outer non-recursive function is tail-recursive
True definition of tail-recursive
A function is tail recursive if it calls itself recursively but does not perform any computation after the recursive call returns
Quiz 1: Is the following function tail-recursive?
let rec some_function l = match l with
| [] -> []
| h :: t -> if h=1 then [1] else some_function tAnswer: Yes! There’s one recursive call some_function t and the evaluation result immediately becomes the return value of some_function .
Quiz 2: Is the following function tail-recursive?
let rec some_function l = match l with
| [] -> []
| h :: t -> if h=1 then 1 :: some_function t else some_function t(Notice the difference from the first function.)
Answer: No. When we have the result of the recursive call some_function t , it is not immediately returned — we have to ::it with 1 .
Quiz 3: Is the following function tail-recursive?
let rec rev l =
match l with
|[]->[]
|x::xs -> rev xs @ [x]Answer: No. After we have the result of the recursive call rev xs, it is not immediately returned. We still need to @ it with [x], in the recursion stack.
What is continuation?
With a correct understanding of tail-recursion, you are now ready to understand continuation. If you have used async/wait in other programming languages, OCaml Continuation is not completely new to you! It’s a similar idea: save the current state of execution into some object, so that you can restore the state from this object later.
Quiz 4: Why do we use stack of functions to do continuation in OCaml?
Answer: OCaml doesn’t have first-class support for Continuation.
Continuation as Composite Functions
In high school math, we learned composite functions. To calculate g(f(x)), we need to calculate f(x) first, let’s call the result r ,then the answer of g(f(x))would be g(r) .
Quiz 5: Consider the following code, can you write it in math, and explain the order of operation in words?
let f x = x + 1
let g x = 2 * (f x)Answer:
- Math: g(x) = f(x) * 2 = (x+1)*2
- Words: First calculate x+1, then times the result by 2.
Note the “then” here, it is a signal telling us we can write it using continuation:
let f x k = k (x + 1)
let g x = f x (fun r -> 2*r)Is it still working as we expected? Let test g(2)=(2+1)*2=6
g 2
- : int = 6Correct! What if we just want to use the function f ? Let’s test f(2) = 2+1=3
f 2 (fun r->r)
- : int = 3Right again! But wait, how does this work?
This is rather a simple example, without recursions. Let’s now look at continuation in recursive functions.
Top-down Approach to Understand Continuation
Consider this function, appending l2after l1, using continuation:
The key magical line of code is app’ t (fun r -> k (h :: r)) . Recall that in the naive version of append, the code here is h :: append t l2 . What’s the connection between these two different styles?
To understand, instead of diving into the call-stack (bottom-up), let’s interpret them top-down:
Before you read this line of text, go back and read the illustrations again. Make sure you get the idea. What seems unexplained in the graph?
Take your time to think about this. What is still unexplained?
Feel free to pause and ponder before we talk about failure continuation.
Quiz 6: The following function computes the product of elements in a list using continuation, fill out the missing code.
Answer: (fun r -> k (x*r))
Explanation: Assume we have the result r of sub-problem (product of all elements in xs) , we should just call the success continuation with x*r, which solves the whole problem. Btw, don’t forget parenthesis!
Quiz 7: Can you think of any optimization for the
listProdfunction?
Answer: When we see 0, we don’t need to call continuation — anything times 0 gives 0.
Quiz 8: Write a
sumfunction that sums a integer list, using continuation
Answer:
Why do we need failure continuation?
When we append two lists, as long as passing type-check, the function will always be able to give a result. Hence we didn’t need a failure continuation in append. But say we want to find a value in a list, a tree, or any data structure, you name it— there is always a case that we don’t find it. What shall we do? Sure, we can raise an NotFound exception, or returns a special value (404, if you prefer), or print a crying face (😢). Such thing we want to do after the function fail to achieve its goal (finding the value), can be wrapped in a failure continuation.
Quiz 9: Why is the return type of fail continuation
‘b?
Answer:'bis to differ from the input type of success continuation 'a . In fact, you can have a fail continuation that does not return anything, not even None : such fail continuation would just raise an Exception.
Quiz 10: Why is continuation slower on simple tasks?
Answer:
Naive recursion runs on stack memory: fast but small.
Continuation runs on heap memory: a bit slow, but huge!
The End
I hope this article is somehow helpful for you to better understand OCaml continuations😜. If you notice any error, or have any suggestions, please leave a comment. 😊
