Continuations Explained with Ruby (Series)
In my PLP class (Pragmática das Linguagens de Programação/Programming Language Pragmatics) we’ve been talking about continuations in Scheme and how they allow us to do some pretty interesting stuff.
As they say, in order to understand something properly, you’ve gotta be able to explain it to someone else. So I’m going to give it a shot and try to explain what Continuations are and how they can be used using Ruby as my language of choice.
Before we continue, let me just get a few things straightened out:
- I do not claim to be an expert on this subject, so if you happen to find an error, please let me know. I’m just explaining what I learnt in class and by reading up on it (Programming Language Pragmatics book by Michael L. Scott and Wikipedia).
- I don’t plan to cover everything about continuations. For the moment I’m just going to focus on explaining Continuation-Passing style (CPS) using Ruby. Other things like Ruby Fibers or Call-with-Current-Continuation (call/cc) won’t be discussed for the time being (but may come at a later stage).
Table of Contents
- Introduction to Continuation-Passing Style
Recursion vs. Iteration; Tail Recursion; Transforming a non-tail recursive function into a tail recursive one using CPS; Saving computations and avoiding the stack (kinda like Prolog). - 4 Queens Problem with CPS
4 Queens Problem; Recursive Solution; Solution using CPS that uses backtracking like Prolog and is capable of returning more than one solution (without duplicating calculations).
Posted on 09 October 2009 under Programming