Mostly for grins, and partly to get a feel for Literate Coffeescript1, I thought I'd take a shot at working the exercises in SICP ( Structure and Interpretation of Computer Programs (pdf)) using Coffeescript.
If you'd like to play around with the code yourself, there are links to fiddles pre-loaded with appropriate code after each section.
Once you've worked through Smooth Coffeescript, or used the underscore.js functional library, it becomes essential to have a few functional basics available. They'll also help us keep the code more philosophically aligned with SICP.
# this function is shamelessly lifted from Smooth Coffeescript
forEach = (array, action) -> action element for element in arrayNote: The exercises related to LISP/Scheme's syntax and use will be skipped, for obvious reasons.
Exercise 1.3:
From SICP:
Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
A couple of support functions are obvious from the problem definition.
square = (x) -> x * x
# notice how unary function calls can look LISPy, if you're into
# that kind of thing.
sumOfSquares = (x, y) -> (square x) + (square y)The requirement to use the two larger of three numbers could be met with a specific function,
but I prefer to define more general functions that might be useful for composition with
other simple functions later on. We'll implement a few list helpers as we go, using
arrays instead of lists. The first and rest functions are lifted from Clojure.
first = (array) -> array[0]
rest = (array) -> array.slice 1Now we're ready to functionally compose our solution. We'll take our three parameters,
put them in an array, and sort it. Then the smallest of the three will be in first position
and we can return the sumOfSquares of the rest
ex_1_3 = (a, b, c) -> sumOfSquares.apply null, rest [a, b, c].sort()Exercises 1.4 and 1.5 elided.
The exercises following this example refer back to its code, so we'll need to implement the example as well.
average = (x, y) -> (x + y) / 2
improve = (guess, x) -> average guess, (x / guess)
abs = (x) -> if x < 0 then -x else x
good_enough = (guess, x) -> abs(square(guess) - x) < 0.001Before we get all recursive with the sqrt_iter function, we have to
compensate for Coffeescript's (actually JavaScript's) lack of tail call
optimization. I found the following workaround in this gist.
The tco function wraps the function passed to it in a closure and
provides a @recur function that can be used within the passed function
instead of recursively calling itself. Clear as mud, right? Suffice to
say that it turns a recursive function into an iterative one, provided
you use @recur.
Note: Due to the lack of language support, we have to be very
careful to only use the tco solution when the @recur is a tail
call.
tco = (fn) -> (args...) ->
if @recursed? or @args? or @recur?
unless arguments.callee.noWarn
# here we are taking precautionary measures to make sure we don't
# accidentally overwrite some important properties in the context named
# "recursed", "args" or "recur". The warnings can be disabled by setting
# the `noWarn` property of the function to true
throw new Error """
calling a tail-recursive function in this context will overwrite the
properties "recursed", "args" and "recur".
"""
@recursed = false
@args = []
@recur = (args...) =>
@recursed = true
@args = args
returnVal = fn.apply this, args
while true
if @recursed
tempArgs = @args
@args = undefined
@recursed = false
returnVal = fn.apply this, tempArgs
else
return returnValWith that out of the way, we can implement our recursive function without blowing the stack.
sqrt_iter = tco (guess, x) ->
console.log guess
if good_enough guess, x
guess
else
@recur (improve guess, x), x
# console.log sqrt_iter(1, 525)Exercise 1.7.
From SICP:
The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?
The small number problem can be seen in this fiddle. The reason this happens is that the tolerance value 0.001 is simply too large when finding the square root of numbers in or below the same range.
I'll spare you a fiddle of the large number problem because it would
hang your browser. The problem with sufficiently large numbers is that
the tolerance value of 0.001 is (you guessed it) too small, and the
algorithm can end up bouncing back and forth between two values (x, y)
such that improve(x) == y and improve(y) == x, at which point it's
never going to end. (If you play around with the previous fiddle and
large numbers, you'll find that they have to be very large before
becomes and issue).
Here's the new good_enough strategy implemented:
good_enough = (guess, x) ->
delta = abs((improve guess, x) - guess)
tolerance = 0.001
delta <= (tolerance * x)Exercise 1.8
From SICP:
Newton’s method for cube roots is based on the fact that if y is an
approximation to the cube root of x, then a better approximation is
given by the value (x/y^2 + 2y)/3 Use this formula to implement a
cube-root procedure analogous to the square-root procedure. (In Section
1.3.4 we will see how to implement Newton’s method in general as an
abstraction of these square-root and cube-root procedures.)
As the parenthetical implies, we can reuse a lot of code from
sqrt_iter. But first let's add a cube function:
cube = (x) -> x * x * xSo now we look through our square root guessing code and see that the
square function is used… nowhere?!
We had expressly used square in our first pass, but when we improved
good_enough, we didn't need it anymore.
But the square root nature of the problem is in there, it's just
hiding in our improve function:
improve = (guess, x) -> average guess, (x / guess)So in the end, we don't need the cube function at all. We just need to
change improve so that it converges towards the cube root:
improve = (guess, x) -> average guess, (x / (square x))In section 1.1.8, the authors rewrite the square root solution to be a
single, user friendly sqrt function, with the various functions we
used to build the original defined inside sqrt, so they don't
pollute the global namespace.
They also continue to use the less accurate version of good_enough,
so we will, too. While we could build a one-off version of tco as a
nested function, it's definitely general purpose enough to continue to
live at the global level.
sqrt = (x) ->
sqrt_iter = tco (guess, x) ->
improve = (guess, x) -> average guess, (x / guess)
good_enough = (guess, x) -> abs(square(guess) - x) < 0.001
if good_enough guess, x
guess
else
@recur (improve guess, x), x
sqrt_iter 1, xTheir first pass at factorial is recursive, but not in the tail position. If you play around with it a bit, it won't be hard to get an idea of your Javascript engine's stack limitation.
factorial = (n) ->
if n is 1
1
else
n * factorial(n -1)Example 1.2.1 Recursive Factorial Fiddle
If we wanted to bring tco into the situation to prevent stack overflow,
we would need to introduce an accumulator, like so:
factorial = tco (n, accum = 1) ->
if n is 1
accum
else
@recur n - 1, n * accumOr, to more closely resemble footnote 29:
factorial = (n) ->
iter = tco (product, counter) ->
if counter > n
product
else
@recur counter * product, ++counter
iter 1, 1Here's a straightforward translation, but don't bother running it unless you like seeing stack overflow messages.
The tco construct won't help us here, because the recursive calls to
cc aren't in the tail position. The addition of the two cc return
values is the problem.
The authors left a non-tree-recursive solution as a challenge, and for now I will, too.
first_denomination = (kinds_of_coins) ->
switch kinds_of_coins
when 1 then 1
when 2 then 5
when 3 then 10
when 4 then 25
when 5 then 50
cc = (amount, kinds_of_coins) ->
if amount is 0 then 1
if amount < 0 or kinds_of_coins is 0 then 0
cc(amount, kinds_of_coins - 1) +
cc((amount - first_denomination(kinds_of_coins)), kinds_of_coins)
count_change = (amount) ->
cc amount, 5to be continued as I find time...
1. In order to get the nice syntax
highlighting on Github, I had to depart a little from proper Literate
Coffeescript form. If for some reason you would like to compile the raw
form of this gist, you'll need to remove the Github code fence
directives. If you have standard Unix tools, it's as simple as sed '/^```/d' < sicp1.coffee.md > sicp1.litcoffee.