Clojure Loops in Ruby
I bet you’re intimately familiar with for
and while
loops. When was the last time you used one in Ruby, though? Ruby introduced me to a whole new world of loops called iterators. It was the first time I’d dabbled with each
and map
. We’ve been chummy ever since and I haven’t looked back.
Recently though, I’ve been spending time learning Clojure. Clojure favors value objects to mutable classes, provides rich immutable data structures, and emphasizes functional programming. As languages go, it’s a far cry from Ruby. During my studies, I was surprised to see yet another style of loop.
Feeling inspired I decided to port this new Clojure loop into Ruby. I settled on using continuations, a little known Ruby feature, to make it all work. Let’s walk through how these loops work, what continuations are, and what happens when these worlds collide.
Oh, before we begin, there’s just one thing. You’ll need to go through a crash course in Clojure. It’ll only take a minute and the rest of this won’t read like gobbledygook.
Clojure Basics
Let’s start off with function syntax. It’s important to know how a basic function call works. We’ll start with the familiar and add up an array of integers in Ruby:
> [1, 2, 3, 4].reduce(:+)
10
In Ruby, you start with an array and call reduce
on it. You tell reduce
that it should use +
on all of the elements in the array. It does the work and gives you back 10
.
I mentioned before that Clojure has a functional focus. That means you don’t just new
up an object and then call stuff on it. Instead, you pass everything being used right to function itself. Here’s the same code in Clojure:
[clojure]
> (reduce + [1 2 3 4])
10
[/clojure]
The first thing you’ll notice is that parentheses surround everything. Inside them, start with the function to call, which is reduce
in this example. Then, follow it up with the function to reduce with, +
, and the array to reduce.
With that knowledge you’re ready to learn loop
.
Clojure’s Loop
In Clojure, loop
has the same layout as a function. The first argument you provide is an array of initial values followed by the code to call during an iteration:
[clojure]
(loop [x 0]
(println x))
[/clojure]
The tricky part in the code above is [x 0]
. You see, loop
takes an array of pairs. Each pair consists of a variable and an initial value for the variable. That bit of code is setting x
to 0
for the first iteration of the loop. If we had more than one variable, we’d add one right after the other. It might look something like this:
[clojure]
[x 0
y 1
z 2]
[/clojure]
It could also be written as [x 0, y 1, z 2]
(commas are optional in arrays and act as whitespace) but the vertical style is a little easier on the eyes.
After setting the variables, give loop
at least one piece of code to run on each iteration. We’ll keep it simple and go with (println x)
, which is the Clojure equivalent of puts x
.
At this point you might be wondering how we stop this loop. I’ll let you in on a secret. Our code doesn’t actually loop at all. It’ll run one iteration and exit. If we want another iteration we’ll have to call recur
and pass in new values for our variables.
[clojure]
(loop [x 0]
(println x)
(recur (+ x 1)))
[/clojure]
The recur
function takes arguments and calls the nearest loop
or function
it finds while passing those arguments along. It’s how Clojure handles recursive functions and creates recursive loops. Our loop
needs one value for x
, so we send (+ x 1)
, which it uses that for the next iteration of the loop. You’ve probably figured out that (+ x 1)
is just x + 1
so the next iteration runs with x
as 2
. Now, we’ve created an infinite loop. I blame you.
Clojure works this way because you can’t reassign variables. We have to create a new iteration of the loop with its own scope where x
is 2
and only 2
and will never be anything other than 2
.
In the context of Ruby this feels very foreign. It does have an interesting advantage though: You can call recur
in as many different places as you want inside the loop.
Let’s see why that might be helpful.
Prime Factors
The prime factors of a number are the primes that can be multiplied together to reach that number. For 15, that means 3 and 5. In the case of 60 the prime factors are 2, 2, 3, and 5. Notice that you’re allowed to repeat a prime.
How would we go about computing the prime factors for a number? We’ll start with a divisor of 2, the first prime. We’ll see if our number is evenly divisible by the divisor. If so, we’ll store it on the list of primes and try again on our new smaller number. If not, we’ll increment the divisor and try that. When we hit 1, we’re done.
Here’s an implementation of the prime-factors
function in Clojure:
[clojure]
(defn prime-factors [number]
(loop [remaining number
primes []
divisor 2]
(cond
(= remaining 1) ;; stop at 1
primes
(= (rem remaining divisor) 0) ;; evenly divisible
(recur (/ remaining divisor) (conj primes divisor) divisor)
:else ;; not evenly divisible
(recur remaining primes (+ divisor 1)))))
[/clojure]
I used cond
, which you can think of like case
. Each condition is accounted for and paired with the appropriate action. The lines to keep an eye on are 9 and 11. On line 9, I call recur
with the new smaller number, a list of primes that has the divisor added to it (conj
means push
), and the same divisor.
On line 11, when the divisor fails to evenly divide the number, I increment the divisor and try again.
The implementation turns out to be pretty easy. The code reads a lot like the text describing how we compute prime factors.
Alright, that’s enough Clojure.
Let’s Ruby
How would we implement loop
/recur
in Ruby? I like to start with an example of how I want it to work.
Let’s write that same primes factors function in Ruby:
def prime_factors(number)
Clojure.loop(number, [], 2) do |remaining, primes, divisor|
case
when remaining == 1
primes
when remaining % divisor == 0
recur(remaining / divisor, primes.push(divisor), divisor)
else
recur(remaining, primes, divisor + 1)
end
end
end
Ruby already has its own loop
so I put ours inside a Clojure
class. I think that looks pretty good. Implementation time!
Down to Business
To start, let’s just see if we can get the block to run:
class Clojure
def self.loop(*initial_args, &block)
block.call(*initial_args)
end
end
This will get us one loop, just like the Clojure version.
> Clojure.loop(1) { |x| puts x }
1
We need a way to call it again with new arguments. Recursion seems like the obvious choice here, but that plan has problems. How are we going to provide the recur
method inside the block? Even if we figure out how to do that, Ruby isn’t optimized for lots of recursive calls. We might end up causing a stack overflow.
Continuations to the rescue! Ruby comes with continuations as part of the standard library. All you have to do is require 'continuation'
.
If you read that and thought, “A continuwhat?” don’t worry that’s a normal, healthy response. Now, allow me to warp your brain.
The basic principle of a continuation isn’t too complicated. You set a mark in the code, do some stuff, click your heels three times, and end up back on the line of code you originally marked.
Let’s look at an example that counts from 1 up to 10:
require 'continuation'
mark = nil
number = callcc { |continuation| mark = continuation; 1 }
puts number
mark.call(number + 1) unless number == 10
Let’s break it down starting on line 3. Start off by setting the variable mark
to nil
so when we assign it on the next line, it’s available in the correct scope. Speaking of the next line, a lot happens on line 4.
Continuations are created using callcc
. You’ll notice it requires a block. It will execute the block immediately and pass it a continuation object. In the block, set mark
to the continuation object so that we retain access to it. Then, return 1
, which callcc
uses as its return value.
By the time we hit line 5, mark
holds our continuation object and number
equals 1
. Line 5 speaks for itself. Line 6 is where the second half of the magic occurs.
Using call
on a continuation object returns you to the line on which the continuation was created. In this case, that’s line 4. The values passed into call
act as the new return value of callcc
on line 4.
When line 6 is done executing we’re returned to line 4, number
is set to 2
, and execution continues from line 4. It’ll run like this until number
equals 10
.
Back to our loop
code. We need a way to kick off another iteration of the loop. Using call
on a continuation gets us just that. We’ll create a continuation and then execute the block in the context of the continuation:
require 'continuation'
class Clojure
def self.loop(*initial_args, &block)
continuation = nil
callcc { |c| continuation = c }
continuation.instance_exec(*initial_args, &block)
end
end
If we use call
anywhere inside block
, it’ll send us back to line 5 in the above code. Now, we have code that can loop infinitely. Again, I blame you.
> Clojure.loop(1) { |x| puts x; call }
1
1
...
We’re getting closer but we still can’t pass values to the next iteration. Let’s fix that.
require 'continuation'
class Clojure
def self.loop(*initial_args, &block)
continuation = nil
args = callcc do |c|
continuation = c
initial_args
end
continuation.instance_exec(*args, &block)
end
end
Just like in our counting example, start on line 5 by preparing a variable to hold the continuation. Add an args
variable on line 6 and start by setting it to initial_args
. Now, when values are passed to call
they’ll end up in args
.
Once again counting from 1 to 10:
Clojure.loop(1) do |number|
puts number
call(number + 1) unless number == 10
end
At this point our loop
works. The only thing left to do is alias recur
to call
so we can use the method name we want.
require 'continuation'
class Clojure
def self.loop(*initial_args, &block)
continuation = nil
args = callcc do |c|
continuation = c
class << continuation
alias :recur :call
end
initial_args
end
continuation.instance_exec(*args, &block)
end
end
We’ve done it!
The Only Thing We Have to Fear…
If at any point during this you thought “GOTO” and ran from your desk screaming to the confusion of your co-workers, that’s not entirely unwarranted. Like GOTO, continuations can be used for evil. If you carelessly litter your code with continuations, you can expect an execution path that is impossible to follow. It’ll also mean that you’re doing it wrong.
We’ve seen the capabilities of continuations, jumping through code and carrying data along for the ride. They are an amazing tool, capable of building powerful control flow primitives. Continuations can be used to add exception handling to a language or create generators.
They’re not something you’ll reach for regularly, but when you want to do something like, say, build a Clojure style loop, they’ve got your back.