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.