I've been checking out the legendary MIT Structure and Interpretation of Computer Programs course from 1986 on YouTube, and it's fascinating for many reasons, not least the hypnotic synthesized Bach that bookends each lecture. I don't think I will ever be able to hear Jesu, joy of man's desiring again without seeing that purple wizard. What's really striking to me is how quickly the course gets into territory that I (coming from a self-taught Perl/Java background) think of as pretty advanced. In the first three lectures we are introduced to:

• Recursive subroutines
• big-O notation
• passing functions around as variables
• building functions using higher-order programming

Anyway, I thought that the example used to illustrate higher-order programming was pretty cool, so I decided to see if I could implement it in Groovy. The example involves writing a function to calculate the square root of a number using the Babylonian method - start with a guess and repeatedly average the guess with the number divided by the guess, until the answer is close enough.

Here it is in Groovy:

def abs(x){  
    if (x < 0)  
        -x  
    else  
        x  
}

def sqrt2(guess){  
    println "guess is $guess"  
    def difference = abs((guess * guess) - 2)  
    if (difference < 0.001){  
        return guess  
    }  
    else{  
        def new_guess = ((2 / guess) + guess) / 2  
        return sqrt2(new_guess)  
    }  
}

sqrt2(1)

and the output:

guess is 1  
guess is 1.5  
guess is 1.41666666665  
guess is 1.414215686275 

I've defined an abs() closure because the built-in .abs() method complains about different types of numbers. The sqrt2() method itself is easy to read – given a guess, calculate how far off it is by squaring it, and either return the guess (it it's close enough) or use the averaging procedure to make a new guess and call sqrt2() again. We could make it a bit more concise by leaving off the explicit return statements – a Groovy method returns the value of the last expression that was evaluated, so we don't really need them (this is what I've done with my abs() method). Note that when we call the method in the last line, we have to supply it with an initial guess.

The first step in abstraction is pretty obvious – let's do away with the hard-coded 2 and let the method take the number for which we want to take the square root as an argument.

def sqrt_iter(x, guess){  
    println "guess is $guess"  
    def difference = abs((guess * guess) - x)  
    if (difference < 0.001){  
        guess  
    } else {  
        def new_guess = ((x / guess) + guess) / 2  
        sqrt_iter(x, new_guess)  
    }  
}

def sqrt = { x ->  
    sqrt_iter(x, 1)  
}  
sqrt(5)

To make things a a little more convenient I’ve moved the iterative code to a closure called sqrt_iter(); the job of sqrt() now is just to supply the initial guess. Now we can ask for the square root of exotic numbers like five:

guess is 1  
guess is 3  
guess is 2.33333333335  
guess is 2.238095238095  
guess is 2.2360688956435

Up to this point there’s no higher-order programming going on. But now it starts to get interesting; we can extract the bits of code that are responsible for checking if the answer is good enough and for generating the next guess:

def improve(x, guess){  
    ((x / guess) + guess) / 2  
}

def goodEnough(x, guess){  
    def difference = abs((guess * guess) - x)  
    difference < 0.001  
}

def sqrt_iter(x, guess){  
    println "guess is $guess"  
    if (goodEnough(x, guess)){  
        guess  
    }  
    else{  
        def new_guess = improve(x, guess)  
        sqrt_iter(x, new_guess)  
    }  
}

def sqrt(x){  
    sqrt_iter(x, 1)  
}  
sqrt(5)

Now, what we are left with in sqrt_iter() is a generic procedure for solving a problem by generating successively better guesses until we get close enough. We can make this abstraction explicit by turning our improve / good enough methods into closures and having them as arguments to the main iteration method:

sqrt_improve = { x, guess ->  
    ((x / guess) + guess) / 2  
}

sqrt_goodEnough = { x, guess ->  
    def difference = abs((guess * guess) - x)  
    difference < 0.001  
}

def generic_iter(goodEnough, improve, x, guess){  
    println "guess is $guess"  
    if (goodEnough(x, guess)){  
        guess  
    }  
    else{  
        def new_guess = improve(x, guess)  
        generic_iter(goodEnough, improve, x, new_guess)  
    }  
}

def sqrt(x){  
    generic_iter(sqrt_goodEnough, sqrt_improve, x, 1)  
}  
sqrt(5)

I’ve changed the names of the closures to make things clearer. sqrt_improve() and sqrt_goodEnough() are the particular type of improve and goodEnough routines that are for solving square roots. Our iteration routine is now a generic one that take four arguments – a closure that can tell if a guess is good enough; a closure that can improve an existing guess, a number for which we’re trying to find the answer, and a guess. Note that the generic_iter() method now contains absolutely no logic to do with calculating square roots – it is completely generic. We can use it to solve any problem which we can express in terms of a way of checking if a guess is good enough, and a way of improving a guess.

Here’s a completely brain-dead example; using the generic_iter() method to solve the problem of finding the smallest integer that is bigger than a given number:

biggerThan_improve = {x, guess ->  
    guess + 1  
}

biggerThan_goodEnough = {x, guess ->  
   guess > x  
}

def biggerThan(x){  
    generic_iter(biggerThan_goodEnough, biggerThan_improve, x, 0)  
}

biggerThan(5)

The improve closure just increments the guess by one; the good enough closure just checks whether the guess is bigger than the target number. The output is not particularly surprising:

guess is 0  
guess is 1  
guess is 2  
guess is 3  
guess is 4  
guess is 5  
guess is 6 

One final point: because we can return closures as values from methods in Groovy, we can redefine generic_iter so that rather than executing the iteration procedure, it returns it. So we can assign the result to another variable and use it later on:

def generic_iter(goodEnough, improve){  
    def returnClosure  
    returnClosure = { x, guess ->  
        println "guess is $guess"  
        if (goodEnough(x, guess)){  
            guess  
        }  
        else{  
            def new_guess = improve(x, guess)  
            returnClosure(x, new_guess)  
        }  
    }  
}

def sqrt = generic_iter(sqrt_goodEnough, sqrt_improve)

sqrt(5, 1)

Note that here we have to define returnClosure before we assign a value to it, because we want to refer to it inside the closure body. generic_iter now takes only two arguments – the two closures that will do the work – because its job is not to actually carry out the calculation, but to build the routine that will.