A bit of Racket potpourri lately as I am reading through some material as well as working on Euler problems; more on the latter after this.

One of the reasons I became interested in Racket was its apparent utility for writing domain-specific languages. Starting from there seemed like a tall order, so I've spent a good bit of time—not all of it, mind you—working on Euler problems in what little remains of my spare time.

In the interim, though, I've come across several reference works through some manufactured serendipity that are worth noting:

• On LISP — Paul Graham's classic. I haven't read through it all, but it struck me in the beginning of the read that many of his examples were not very well motivated. I felt the same way when reading ANSI Common Lisp during my undergrad days.

• Practical Common LISP — Peter Seibel's more recent work. This I haven't read in any detail, but I found his discussion of macros interesting. There are a number of good chapters here that show some fairly typical applications written in LISP.

• Automata Using Macros — An educational (!) paper by Shriram Krishnamurthi. I don't know how I happened upon it, but it's an excellent read and only 14 pages, including references. One of the hardest things to do in education, I've found, is to make examples that grow with the reader. In describing basic finite-state machines and a DSL to represent them, Krishnamurthi progresses very naturally through different representations and structures finally arriving at an implementation using macros.

• Creating Languages in Racket — an article in ACM Queue by Matt Flatt. This is the one that started it all for me.

• Higher-order List Operations in Racket and Haskell — from Matt Might's blog. This was one of the first articles I found that connected with me because it described me to the core:

There is a pattern with students learning functional programming.

First, they try to use loops and mutation; this ends with awkward, broken programs. There is confusion and aggravation. Even hostility.

Eventually, they accept and embrace recursion.

But, then they write too much.

This last article is the one that I kind of finally "got" when working through Euler 5, which is asking for the least common multiple of the numbers from 1 to 20 inclusive.

While there are undoubtedly more obvious solutions, the preceding questions about the prime factorization of numbers leads quite directly to a least common multiple implementation. Unfortunately my solutions all rely on hash tables—one of those foibles Dr Might mentions above—and I remain unpersuaded of their suitability.

Now the Least Common Multiple is related directly to the Greatest Common Divisor, which can be computed efficiently using Euclid's Method. The least common multiple of two numbers (say a and b) is the quotient of their product and their greatest common divisor (i.e., (a · b)/gcd(a,b)). It should be observed that the least common multiple of three numbers is simply lcm(lcm(a,b),c), and we can continue this down the line.

It was at this point that I said to myself, "That sounds a lot like the folding that Matt Might talked about, and I bet all of my other solutions are simply moronic." I was basically correct.

The key here is in the repeated applicaiton of the lcm function over accumulated results. That's the textbook implication for folding, I guess.

(define (euler5-3 rng)
  (letrec ([my-gcd (lambda (x y)
                     (if (= 0 (% x y)) y (my-gcd y (% x y))))]
           [my-lcm (lambda (x y)
                     (/ (* x y) (my-gcd x y)))])
    (foldl (λ (x result) (my-lcm result x)) 1 rng)))

The implementations of my-gcd and my-lcm are perhaps a bit superfluous given that they are features of the language already, but part of the exercise is in writing the elementary functions—and I haven't done that in years and years anyway (maybe since high school AP Computer Science?).

In brief, we see a lambda function passed to foldl: it takes two parameters, one which is the next item in the range (x) and the accumulated least common multiple (result). It calculates lcm(result,x). foldl takes two other parameters: the initial value (1) and the set of values over which to operate (rng). More nicely formatted:

(foldl
   (lambda (x result) (my-lcm result x))  ; the function to be folded
   1                                      ; the initial value
   rng                                    ; the range passed in to euler5-3
)

Lo-and-behold, it worked! It felt like learning, as though I'd kind of finally realized a little bit about how Racket is structured. I've had a similar experience with lexical scoping, but I don't know that I've grasped the full implications yet...and that's another topic for another day.