Machine Learning: a review

During my hiatus from this blog I completed two Coursera courses. I thought a brief review might be in order.

The first course I took was Machine Learning. The course was taught by Andrew Ng of Stanford University. Machine Learning (hereafter, ML) was my first exposure to the world of massive open online courses. I had heard good thing about the ML course, so I decided to take the plunge.

I was very curious about one thing. A course on machine learning would presumably require the prospective student to have some level of mathematical sophistication, and some ability to program. I have known very good mathematicians who could not program at all, and some very good programmers who were either indifferent to or afraid of math. It seemed unlikely that the ML course would be populated solely by students skilled in both mathematics and programming. I had heard that Professor Ng was a gifted instructor; I wanted to see how he would tackle the difficult task of teaching both math and programming to a large audience of widely varying backgrounds.

The ML course was ten weeks long. Each week featured multiple brief video lectures, say between 5 and 20 minutes long. Along with the lectures, there were weekly quizes and programming assigments. The programming language for the course was GNU Octave. There was also a discussion forum where one could ask questions, talk about the assignments, etc.

Here is a brief outline of the topics covered.

  • linear regression, 1 variable
  • linear regression, multiple variables
  • logistic regression
  • neural networks
  • design of machine learning systems
  • support vector machines
  • clustering
  • dimensionality reduction
  • anomaly detection

Along the way we had a very brief review of some ideas from linear algebra, some tutorials on the Octave language, and many valuable protips (practical advice from a seasoned machine learning practitioner).

A typical (supervised) machine learning problem represents its data as points in a high dimensional space. The task of identifying the points with some property P is cast as the problem of finding a surface (a plane, for instance) that separates the points with property P from those without. Typically there is no such surface, so the problem is to constuct an appropriate cost function, and then find a surface that minimizes the cost. Minimization is often handled through some flavor of gradient descent.

Professor Ng’s approach was very pragmatic. In the time available he could not begin to teach the mathematical methods of optimization, particularly in a class where neither calculus nor linear algebra was a prerequisite. Instead he presented plausible appeals to geometric intuition, and urged us to trust that appropriate Octave librabaries could be used to perform the harder minimizations. He put practice ahead of theory, which I believe is the correct pedagogical approach.

The heart of the course was a collection of extremely well thought out programming problems. Professor Ng and his staff prepared problem sets, presented as detailed pdf instructions along with enough Octave scaffolding so that the student programmer only had to consider the essential core of the task at hand. The grunt work was already taken care of. The problems were graded by a well tuned automated system. One submits answers to it, it lets you know whether your response was correct.

My overall assesment? The class was outstanding. Professor Ng’s reputation is well deserved. My thanks and congratulation to him and to everyone involved. A formidable amount of IT support was required to construct the course, the forums, the video production, and the automated grading. A lot of people did good work there, they deserve recognition.

If you are interested in machine learning, the course is offered again starting Oct 14th. If you decide to go for it, here is a bit of advice.

First, brush up on your linear algebra. Nothing fancy is required, just matrix multiplication. I was amazed at the clarity that framing neural networks in terms of matrices produced. What had been a tangle of nested loops and multiple indices became much simpler. Simpler to work with, and simpler to understand.

Second, and this applies especially to programmers, take the time to learn the rudiments of Octave. Time invested up front on learning Octave, especially its methods for constructing and manipulating arrays, will be repaid in time saved during the assigments. Here’s how Doug Crockford puts it in “JavaScript: the Good Parts”

Most people … don’t even bother to learn JavaScript first, and then they are surprised when JavaScript turns out to have significant differences from SOME OTHER LANGUAGE they would rather be using, and that those differences matter.

Don’t be that guy.

Swap alt and ctrl keys

Another addition to the cybernetic memory: how to use xmodmap to swap the alt and ctrl keys on linux. A very useful change if you happen to use Emacs, especially on a laptop.

Step zero

Use the xev program to determine the keycodes for all four keys to be swapped. On my system they were as follows:

  • right-alt 108
  • right-ctrl 105
  • left-alt 64
  • left-ctrl 37

Step one

Create a .Xmodmap file. Here’s mine; if your key codes are not the same as mine
adjust accordingly.

clear control
clear mod1
keycode 37 = Alt_L Meta_L
keycode 64 = Control_L
keycode 105 = Alt_R Meta_R
keycode 108 = Control_R
add control = Control_L Control_R
add mod1 = Alt_L Meta_L Alt_R Meta_R

Profit

Find a way to get the .Xmodmap file to run at startup. This is unfortunately distro and version specific. I am running Linux Mint 14, the following worked for me. Open menu::preferences::Starup Applications. Then add a new entry containing the command xmodmap ~/home/drc/.Xmodmap (adjust path to your .Xmodmap as needed). I suspect using ~/.Xmodmap would have worked, but I did not bother to try.

A quine in SAS

I’ve been playing around with quines in various languages. I searched for one written in SAS, but had no luck. So in accordance with the principle of plentitude, I wrote one. Here it is; tested under SAS versions 9.2 and 9.3.

data _null_;
q = put(byte(34),$char1.);
length C1-C10 $ 80;
array C{10} $ C1-C10 (
" data _null_; " ,
" q = put(byte(34),$char1.); " ,
" length C1-C10 $ 80; " ,
" array C{10} $ C1-C10 ( " ,
" ) ; " ,
" do i = 1 to 4; put C{i}; end; " ,
" do i = 1 to dim(C)-1; put q C{i} q ','; end; " ,
" put q C{dim(C)} q ; " ,
" do i = 5 to dim(C); put C{i}; end; " ,
" run; "
) ;
do i = 1 to 4; put C{i}; end;
do i = 1 to dim(C)-1; put q C{i} q ','; end;
put q C{dim(C)} q ;
do i = 5 to dim(C); put C{i}; end;
run;

xft enabled dmenu

This is a note re getting an xft capable version of dmenu, so that I won’t have to dig next time.

Grab dmenu from http://tools.suckless.org/dmenu/. Current version at time of this post is 4.5. Download, unzip.

Out of box, dmenu does not support xtf fonts. There is a patch for this at http://tools.suckless.org/dmenu/patches/xft. Grab the patch matching the version of dmenu you are using.

Apply the patch:

beavis::  ~/Downloads/dmenu-4.5 
λ patch -p1 < ../dmenu-4.5-xft.diff 
patching file config.mk
patching file dmenu.1
patching file dmenu.c
patching file draw.c
patching file draw.h

Build and install:

beavis::  ~/Downloads/dmenu-4.5 
λ sudo make clean install

Initially, I saw this:

cleaning
dmenu build options:
CFLAGS   = -std=c99 -pedantic -Wall -Os -I/usr/X11R6/include 
-I/usr/local/include/freetype2 -D_BSD_SOURCE 
-D_POSIX_C_SOURCE=2 -DVERSION="4.5" -DXINERAMA
LDFLAGS  = -s -L/usr/X11R6/lib -lX11 -lXinerama -lXft -lXrender -lfreetype -lz -lfontconfig
CC       = cc
CC -c dmenu.c
In file included from /usr/include/X11/Xft/Xft.h:39:0,
                 from draw.h:3,
                 from dmenu.c:14:
/usr/include/ft2build.h:56:38: fatal error: 
freetype/config/ftheader.h: No such file or directory
compilation terminated.
make: *** [dmenu.o] Error 1

This fixed it for me:

λ sudo ln -s /usr/include/freetype2/freetype /usr/include/freetype

Two remarks: The xft version of dmenu looks great, well worth the effort. The lambda character, λ, is not part of the various commands. It is part of my two-line zsh prompt.

Installation and configuration of Clojuratica

Summary: notes on the installation/configuration of Clojuratica.

I recently picked up a copy of the home edition of Mathematica version 8. Clojure and Mathematica are my favorite programming environments, so what could be more natural than to try to get them interoperating? As it happens, there’s a project for that, Clojuratica. I did get manage to get Clojuratica working, but encountered a bump along the way. I want to share my notes in case they may be of use to someone else.

Before starting I took a look at Clojuratica’s github repo. Hmm, no updates in three years. The Clojuratica Google group is also pretty quiet. Not a good sign, but for the purpose at hand Clojuratica is the only game in town.

The Clojuratica install instructions are simple enough. Basically, you have to put a few Mma files somewhere in the Mma path, and a couple of jar files on the Java classpath. Dealing with the classpath is something I prefer to leave to leiningen, and I did manage to make that happen.

Some specifics. My target machine, which goes by the hostname of beavis, is an x86_64 box running Linux Mint Maya 13. The home edition of Mma is 32 bit software. I wondered whether that might cause any issues, but it did not. All references to leiningen refer to

beavis :: ~/
»❯ lein -version
Leiningen 2.0.0-preview10 on Java 1.6.0_35 Java HotSpot(TM) 64-Bit Server VM

Step 0: Grab the software.
You have some choices to make. You could get Clojuratica from the original distribution, here. That software contains (among other things) a jar file built against Clojure 1.2. That jar won’t work with Clojure 1.3 and above.

Instead, I suggest you grab the source from my fork (or Stuart Halloway’s). The changes needed to make Clojuratica compatible with Clojure 1.4 and 1.5 are very simple. Three ear-muffed variables have to be declared dynamic. That’s it. Stu put in a pull request for those changes, but so far no response from the original author. I forked from Stu’s version because I don’t know whether Stu intends to make further changes. My immediate plan is to change as little as possible consistent with Clojuratica working with current Clojure.

These instructions are for building from source. So, lets grab the source and build the Clojuratica jar.

beavis :: ~/src 
»❯ git clone https://github.com/drcabana/Clojuratica
Cloning into 'Clojuratica'...
remote: Counting objects: 999, done.
remote: Compressing objects: 100% (493/493), done.
remote: Total 999 (delta 481), reused 998 (delta 480)
Receiving objects: 100% (999/999), 1.69 MiB | 2.50 MiB/s, done.
Resolving deltas: 100% (481/481), done.

beavis :: ~/src 
»❯ cd Clojuratica 

beavis :: ~/src/Clojuratica ‹master› 
»❯ ant jar
Buildfile: /home/drc/src/Clojuratica/build.xml

init:

compile:

jar:
     [jar] Building jar: /home/drc/src/Clojuratica/clojuratica.jar
     [echo] JAR written to /home/drc/src/Clojuratica/clojuratica.jar

BUILD SUCCESSFUL
Total time: 0 seconds

Step 1: We need to put some Mma source files on the Mma path. To determine what that path is, evaluate $Path in an Mma session. Out of the various path components, I chose what struck me as the most likely suspect:

/home/drc/.Mathematica/Autoload

We need to copy three files.

beavis :: Clojuratica/src/mma ‹master*› 
»❯ ls
ClojurianScopes.m   FunctionalExtras.m  HashMaps.nb
ClojurianScopes.nb  HashMaps.m

beavis :: Clojuratica/src/mma ‹master*› 
»❯ cp *.m  /home/drc/.Mathematica/Autoload/

Step 2: Next, shave a yak. We want to put the clojuratica.jar and the JLink.jar (more on that later) in the java classpath. One way to do that in a leiningen friendly way is to set up a local maven repository. I have no maven-fu, so I installed the lein-localrepo plugin. I installed the plugin by putting it into my profiles.clj file, as follows:

beavis :: ~/.lein 
»❯ cat profiles.clj 
{:user {:plugins [
   [marginalia "0.7.1"]
   [lein-marginalia "0.7.1"]
   [lein-pprint "1.1.1"]
   [lein-localrepo "0.4.1"] ]}}

You only need lein-localrepo for the purpose at hand.

Step 3: Put clojuratica.jar in the local repository. Note that in the snippet below, I inserted line breaks for legibility. Everything after the ‘»❯’ prompt was originally on one line.

beavis :: ~/.lein 
»❯ lein localrepo install 
   ~/src/Clojuratica/clojuratica.jar
   local.repo/clojuratica 2.0_alpha3

Step 4: Put the JLink.jar in the local repository. Some background here. The JLink.jar file is distributed with Mma; it makes Java-Mma integration possible. Again, in the snippet below I inserted line breaks for legibility. Everything after the ‘»❯’ was originally on one line.

beavis :: ~/.lein 
»❯ lein localrepo install 
   /usr/local/Wolfram/Mathematica/8.0/SystemFiles/Links/JLink/JLink.jar 
   local.repo/JLink 8.0

Step 5: Create a lein project, and update the project.clj file to pull in JLink and Clojuratica. Here’s my project file.

beavis :: code/juratica/mmaclj 
»❯ cat project.clj 
(defproject mmaclj "0.1.0-SNAPSHOT"
  :description "Test of Clojure-Mathematica interop via Clojuratica"
  :url "http://example.com/FIXME"
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :dependencies [[org.clojure/clojure "1.5.0-alpha7"]
                 [local.repo/JLink "8.0"]
                 [local.repo/clojuratica "2.0_alpha3"] ])

Finally, here’s the code to get Clojure talking to Mma.

beavis :: mmaclj/src/mmaclj 
»❯ cat connect.clj

(ns mmaclj.connect
  (:use clojuratica)
  (:import [com.wolfram.jlink MathLinkFactory]))

(defn init-mma
  "Connect to Mathematica."
  [mma-command]
  (defonce math-evaluate
    (math-evaluator
     (doto (MathLinkFactory/createKernelLink mma-command)
       (.discardAnswer)))))

;; On my system 'math' is a symlink to '/usr/local/Wolfram/Mathematica/8.0/Executables/math'
(init-mma "-linkmode launch -linkname math")

(def-math-macro math math-evaluate)

At this point we should be ready to fire up a repl and connect to Mma. But there is a problem. I have a fix, but I don’t understand the cause of the problem. If you do, please let me know.

Here’s the problem. I start a repl and try to connect, and get a stacktrace. I’ll spare you most of it.

; nREPL 0.1.6-preview
user> (use 'mmaclj.connect)
UnsatisfiedLinkError com.wolfram.jlink.NativeLink.MLOpenString(Ljava/lang/String;
[Ljava/lang/String;)J  com.wolfram.jlink.NativeLink.MLOpenString (NativeLink.java:-2)
...

Here's the fix, which I discovered using a technique I call "monkey pokes at it with a stick". Back in step 4 we put the JLink.jar file into the local maven repo. Inside the repo we see:

beavis :: repository/local/repo 
»❯ pwd
/home/drc/.m2/repository/local/repo

beavis :: repository/local/repo 
»❯ tree JLink
JLink
├── 8.0
│   ├── JLink-8.0.jar
│   └── _maven.repositories
└── maven-metadata-local.xml

I used diff to compare the JLink-8.0.jar to the original at /usr/local/Wolfram/Mathematica/8.0/SystemFiles/Links/JLink/JLink.jar. They are identical.

Step 5: Fix the problem by replacing the JLink-8.0.jar inside the local repo with a symlink to the original.

beavis :: repo/JLink/8.0 
»❯ rm JLink-8.0.jar 

beavis :: repo/JLink/8.0 
»❯ ln -s /usr/local/Wolfram/Mathematica/8.0/SystemFiles/Links/JLink/JLink.jar JLink-8.0.jar

Step 6: Profit.

; nREPL 0.1.6-preview
user> (use 'mmaclj.connect)
nil

user> (math (FactorInteger 24))
[[2 3] [3 1]]

user> (time (math (FactorInteger 987654321123456789)))
"Elapsed time: 9.042132 msecs"
[[3 2] [11 1] [37 1] [79 1] [139 1] [73589 1] [333667 1]]

user> (time (math (Prime (* 1000 1000 1000))))
"Elapsed time: 3.457082 msecs"
22801763489

The billionth prime in 4 msecs is pretty snappy. You can grab the mmaclj code here.

I am impressed that a project that had not been updated in three years still works. It is a testament to the stability of both Clojure and Mathematica, and to the work of Clojuratica author Garth Sheldon-Coulson.

The Devil and the language designers

The reader may be surprised to learn that the Devil is an accomplished programming language designer. Indeed, he has made significant contributions to the field. But the Devil takes no credit for his work, because it is a strategic desideratum of applied deviltry that devilish involvement in human affairs should go unnoticed. This strategy of concealment has been so effective that most readers will take the story I am about to tell as allegory. By all means, believe that. You’ll sleep better.

A long, long time ago, in a land far away, the Devil approached the great language designer Mr. C with an idea.

Devil: Mr. C, I have a delightful notational innovation I’d like to share. May I show it to you?

Mr. C: By all means.

Devil: It is a modest extension to your own work, but one of great power. Consider a simple expression, say

λxy.x+y

My proposed extension is

λxy.δz.x+y+z

Mr. C: What does this new expression mean?

Devil: The δ symbol is used to introduce an additional ‘special’ value z, which takes on random values.

Mr C: I see. This would make it difficult to reason about the value of the resultant expression, would it not?

Devil: Yes, exactly. You have grasped the matter immediately. Are you on board?

Mr. C, an old-fashioned mathematician obsessed with mere correctness, was not on board. The Devil was disappointed, but he is nothing if not patient. He spent some years thinking about the matter and approached another language designer, the celebrated Mr. S.

Devil: Mr. S, I have a wonderful notational advance I’d like to share. May I show it to you?

Mr. S: Please do.

Devil: It is a simple extension to your own work, but one of transformative power. Consider a simple expression, say

(define (f x y) (+ x y))

My proposed extension is

(define (f x y [z]) (+ x y z))

Mr. S: What does your proposed extension accomplish?

Devil: The [z] notation is used to introduce an additional ‘special’ value z, which can effectively take on random values. At runtime, any process whatsoever is allowed to change the value of z, at any time. The caller does not even have to provide a value for z, the runtime will do it. Or if a value is provided, the runtime may change it. Or not.

Mr S: An interesting idea. Would this not lead to pain, madness, chaos, and despair among users of this new feature?

Devil: Why yes, yes it would. I can see you have insight, and are a man after my own heart.

Alas, the Devil had misjudged Mr. S, who was not tempted.

The Devil could hardly believe Mr S would turn down such an opportunity. He had a nagging suspicion that his wonderful idea was being rejected for essentially syntactic reasons. Language designers are funny that way. Besides, what else could it be? So the Devil waited and thought, and redesigned, and waited.

Eventually the Devil approached another language designer, one whom propriety bids I must leave nameless.

Devil: My good fellow, I have a most wonderful construct I’d like to show you.

Designer: What do you have?

Devil: Check this out.

Class Foo {
  int z;
  void set_z (int w){this.z = w;}
  int bar(int x, int y){return x+y+z;}
}

Designer: You do realize the language is multi-threaded?

Devil: Why yes, yes I do. I’m counting on it. Allows mutation too, as I recall.

Designer: The syntax may need a bit of work, but I think we have something here.

The rest is history.

On the shattering of sacred yaks

It is a bitter pain to have one’s beloved illusions stripped away.

I was nearly broken when I first found out that Java is not C++. For months I immersed myself in the writings Epictetus and Marcus Aurelius, hoping to find the strength to put my life back together. It was almost a year before I could sleep through the night.

Then I was blindsided by the news that Python is not Ruby. I was overcome by self-loathing. I should have known. I had known, somewhere in a place I had feared to go. I became a nihilist, and turned to Nietzsche. I was determined to stare into the face of the abyss.

Layers upon layers of self-deception. I was not ready when the abyss stared back. I learned that Clojure is not Common Lisp. Nothing could have prepared me. Even now, I can scarce believe I have repeated those monstrous words.

I remain a sentimental fool, clutching at straws, taking solace in this fragment from the Meditations of St. Emo.

I was walking across a bridge one day, and I saw a man standing on the edge,
about to jump off. So I ran over and said, “Stop! don’t do it!”

“Why shouldn’t I?” he said.

I said, “Well, there’s so much to live for!”

He said, “Like what?”

I said, “Well…are you religious or atheist?”

He said, “Religious.”

I said, “Me too! Are you Christian or Buddhist?”

He said, “Christian.”

I said, “Me too! Are you Catholic or Protestant?”

He said, “Protestant.”

I said, “Me too! Are you Episcopalian or Baptist?”

He said, “Baptist!”

I said, “Wow! Me too! Are you Baptist Church of God or Baptist Church of the Lord?”

He said, “Baptist Church of God!”

I said, “Me too! Are you original Baptist Church of God, or are you Reformed
Baptist Church of God?”

He said, “Reformed Baptist Church of God!”

I said, “Me too! Are you Reformed Baptist Church of God, reformation of 1879,
or Reformed Baptist Church of God, reformation of 1915?”

He said, “Reformed Baptist Church of God, reformation of 1915!”

I said, “Die, heretic scum”, and pushed him off.

A note on fractions

I ran across a blog post called Why 0.1 Does Not Exist In Floating-Point. The author uses long division in binary to demonstrate his point. This is understandable, given that the host blog is called Exploring Binary, but there is a an easier way to determine whether the fraction p/q has a terminating floating point representation for a given base.

Say we want to know whether p/q = 20/24 terminates in when expressed in base B=18. First divide out any common factors of p/q; in our case we are left with p/q = 5/6. Now we can forget p; it plays no further role. The fraction terminates if and only if every prime factor of q is a factor of B. Here q = 6 = 2*3. Since B = 18 = 2*3*3, the fraction does terminate. On the other hand, 5/6 does not terminate in base 10, because 3 is not a factor of 10.

Let’s see why this works. What I’m going to show you works in any base, so we might as well use the familiar base 10.

Consider 1/8 = .125 ; what that means is that 1/8 = 125/1000. To say that the fraction p/q has a terminating representation in base B means that p/q = x/(B^k) for some integers x and k. By looking at the prime factors of q and B, it is easy to either construct x and k, or see that the construction fails. Here are some examples.

1/8 = (1/2)(1/2)(1/2)
    = (1/2)(5/5) (1/2)(5/5) (1/2)(5/5)
    = (5/10)(5/10)(5/10)
    = 125/(10^3)

Here’s the 5/6 in base 18 example.

5/6 = (5/2)(1/3)
    = (5/2)(9/9) (1/3)(6/6)
    = (45/18)(1/18)
    = 45/(18^2)

I mentioned that 5/6 does not terminate in base 10. Here’s what happens if you try as above.

5/6 = (5/2)(1/3)
    = (5/2)(5/5) (1/3)
    = (25/10)(1/3)

There is no integer x such that 3x = 10, so the process fails. I hope this intuitively clear.

The failure case is the more interesting one, so I say want to say a bit more about it. We tried to show that p/q = x/(B^k), where all the variables must be integers. This is the same as saying that p(B^k)/q is an integer, and so q must be a divisor of p(B^k). Let m be an integer. It is a trivial fact that if m divides q and q divides p(B^k), then m divides p(B^k). Now suppose m is a prime divisor of q. It is a deep and non-trivial fact that if a prime m divides a product p(B^k), then either m divides p or m divides B^k (or both). Recall that we began by dividing out common factors of p and q, so m does not divide p. Then m must divide (B^k), and by the same argument, m must divide B. To recap, the only way q can be a divisor of p(B^k) is if each of its prime factors divides B

That’s all folks.

Equational Reasoning

Alan Dipert tweeted an interesting puzzle:

pop quiz: solve http://www.4clojure.com/problem/107 point-free. answer must be a function value! #clojure

The 4clojure version of the problem is simple enough, but the added requirement of a point-free solution makes Alan’s version of the problem harder. And harder to resist. So I took a shot at it.

My plan was simple: solve the problem in the natural way, and then transform the solution into the point-free style. Piece of cake. Not.

Here’s my starting place:

   (fn [x] (fn [y] (reduce * (repeat x y))))

That solves the 4clojure version of the problem, but I need to get rid of the arguments x and y, and the lambdas. To make a long story short, I couldn’t do it. The best I could manage was this:

   #(comp (partial reduce *) (partial repeat %))

I managed to rid of one lambda and one variable, but could not get rid of the remaining argument, now slightly disguised as %, and the remaining lambda, disguised as #().

I wanted to know the answer, so I asked Alan, who directed me to a tweet by Baishampayan Ghose. Now the story starts to get interesting. This was @ghoseb’s answer:

   (partial partial (comp (partial reduce *) repeat))

Yow! I would not want to run into that in the wild. No matter how hard I stared at that code, I could not get a clear understanding of how it works. But there are methods other than staring, say abstraction and equational reasoning. Let’s use them to analyze @ghoseb’s code.

I mentioned equational reasoning, so let’s introduce a couple of equations that describe the action of the functions partial and comp.

  • P: ((partial f g) x) == (f g x)
  • C: ((comp f g) x) == (f (g x))

I have labelled the equations P and C, so that I can refer to them later. The equations combine infix and prefix notation. Don’t let that bother you; it’s ok to be less than rigorous in meta-language. Mathematicians do it all the time. The symbols f, g, and x are just variables.

Each equation states that two expressions are equivalent. Here are concrete examples of P and C, written in executable Clojure.

   (= ((partial * 2 3) 4)  ;; illustrates P
      (* 2 3 4))

   (= ((comp #(* % % ) inc) 1) ;; illustrates C
      (#(* % %) (inc 1)) )

Now let’s put P and C to work on @ghoseb’s code. We’ll start by writing out what we know from the problem. We know, and can test by execution, that the following expression evaluates to 256.

   (((partial partial (comp (partial reduce *) repeat)) 2) 16)

I mentioned that we would use abstraction; by abstraction I mean giving things names. There is one chunk of code in there, enclosed in the innermost parens, that is easy to understand. Let’s give it a name.

   (def mult (partial reduce *))

The mult function applied to a finite sequence of numbers returns their product:

   user> (mult [1 2 3 4])
   24

We can rewrite our expression using mult and get a slightly simpler expression that still evaluates to 256.

   (((partial partial (comp mult repeat)) 2) 16)

Next we’ll simplify a sub-expression. P allows us to infer that

  ;; ((partial partial (comp mult repeat)) 2) == (partial (comp mult repeat) 2)

Protip: forget the semantics for a moment, and just look at the syntax. P allows us to drop one set of parens, and one instance of partial.

Now we go back to our expression that evaluates to 256, and substitute the simplified subexpression.

   ((partial (comp mult repeat) 2) 16)

The P rule has been working for us, let’s use it again. Think symbolically, algebraically. Lose a set of parens, and a partial.

   ((comp mult repeat) 2 16)

We have eliminated all instances of partial. So let’s use C to get rid of the comp.

   (mult (repeat 2 16))

This expression is easy to understand, provided you understand mult and repeat.

Just one thing. Did you buy that last substitution? I claimed above that the C rule works as follows:

   ((comp f g) x) == (f (g x))

But the rule I actually used was this:

   ((comp f g) x y) == (f (g x y))

The thing to understand is that because Clojure functions can be variadic, C is really a pattern of rules, dependent on the arity of g.

  • ((comp f g) x) == (f (g x))
  • ((comp f g) x y) == (f (g x y))
  • ((comp f g) x y z) == (f (g x y z))
  • … etc …

Similarly, P is also a family of rules:

  • ((partial f g) x) == (f g x)
  • ((partial f g) x y) == (f g x y)
  • ((partial f g) x y z) == (f g x z)
  • … etc …

The situation with P is even trickier, because we have to also account for the fact that partial is variadic:

  • ((partial f g) x) == (f g x)
  • ((partial f g h) x) == ((partial f g) h x) == (f g h x)
  • … etc …

In general, P allows us to transform (f x1 x2 … xn) into ((partial f x1 …. xk) xk+1 … xn) for our choice of 1 <= k < n.

Something to note is that the P and C rules are bidirectional. We can take advantage of that to run the analysis of @ghoseb’s code backwards, and maybe get some insight into how to construct a point free solution in the first place.

The solution will have to implement exponentiation. Whatever the implementation, it will have to be true that ((solution 2) 16) evaluates to 256. We don’t know the details, but we see the shape of it. We can start with a fairly natural solution with the wrong shape, below, and use the P and C rules to mold the solution into the right shape.

   (mult (repeat 2 16)) ;; now use C
   ((comp mult repeat) 2 16) ;; use P
   ((partial (comp mult repeat) 2) 16) ;; use P
   (((partial partial (comp mult repeat)) 2) 16) :; use def of mult 
   (((partial partial (comp (partial *) repeat)) 2) 16)

And done. The trick, as in algebra, is to know which rule to apply when. Practice helps, as does a clear understanding of what rules apply, and why. I hope anyone who got this far finds some value in this analysis.

My thanks to @alandipert and @ghoseb for the lovely puzzle. It was instructive, in more than one way.

Years ago I made a promise to my wife that I would not allow my daughter to “check out from math”. I have kept that promise, and in so doing have tried to bear in mind that it is hard to learn to think with symbols. This fall my daughter came home first day of school with a math assignment, a variety of simple algebra problems. It was a diagnostic, the problems were nothing she hadn’t seen before, but she was out of practice after a summer off. I walked her through the assignment, but I too was out of practice. Not with the math, that I could do without thinking. And I did, without thinking. And without the patience and understanding that I should have shown. My daughter thought I was disappointed with her. My fault. This problem reminded me of what it’s like to struggle with symbolic thinking. I hacked without plan or self-awareness, and I floundered.

After I saw @ghoseb’s solution I took the time to think systematically, and was rewarded with insight. I learned a bit about programming, and a bit about humility and patience. It was a good day.

An invitation to FP for Clojure noobs

I’ve heard newcomers to Clojure ask how to get started with functional programming. I believe that learning to program in the functional style is mostly a matter of practice. The newcomer needs to become familiar with a handful of higher order functions, and how they are used in common idioms. This can be done by practice with simple, well defined problems. I assume that the prospective reader already has a grasp of the rudiments of Clojure, and can operate the Leiningen build tool.

Here is what I propose. I have prepared a set of annotated exercises illustrating typical Clojure fp idioms. The exercises are the first 31 Project Euler problems, one for each day of the month. I believe these problems are ideal for the purpose at hand. Each problem is succinctly stated, interesting, and well defined. Each lends itself to a natural functional solution.

I have packaged the problems as a Leiningen project. Each problem is stated, and then solved. Each problem is in its own name space, to enable code reuse across problems. Each problem is documented using the fabulous Marginalia literate programming tool. Running commentary tries to point out common idioms, and provides links to ClojureDocs documentation for newly introduced functions. Unit tests are provided to check the provided solution against the official Project Euler solution. The solutions use current Clojure (1.4.0 beta). Nothing is used from the old clojure.contrib. Each solution is written in an explicitly functional style. Many of the solutions consist solely of function definitions. Vars are used only to name data given as part of a problem statement, or data structures constructed from such data. All data is treated as immutable.

What I recommend is deceptively simple. Read each problem statement. Think about how you might solve it; do so if you like. Then read the provided solution. Read it actively: take the time to run the code, and to understand every function and every construct in the solution. Play with the code. Make changes, run things in the repl. Use ‘lein test’ to see whether your modifications still get the same answer.

Here’s the important point: once you understand the solution, delete it and then reconstruct it. Type it in. Look up functions you don’t remember. Did I mention you should type the code in? Knowledge enters the mind through the fingers, not just the eyes. Do this and I believe you will quickly jump-start your understanding of functional programming in Clojure.

Here are a few things to avoid.

Do not attempt to learn Clojure and new tooling, say Emacs+slime, at the same time. Keep it simple. Edit code using whatever editor you normally use, and run a Clojure repl in whatever terminal emulator you normally use. No fancy IDE or editor hacking is required. Separation of concerns applies to learning as much as to coding.

Don’t worry about parts of Clojure not immediately related to functional programming. In particular, don’t worry about concurrency constructs, STM, protocols, multi-methods, macros, transients, or whatever. Instead, worry about knowing how to define functions using any and all of (defn …), (def …), #(…), and (fn …). Learn map, filter, reduce, for, let, letfn, and iterate.

The Project Euler problems do require a bit of math. Don’t let that put you off. Worst comes to worst, I have already done the math for you. The goal here is to learn fp not math, so don’t get hung up on solving the problems ab initio. The problems are a device to present solutions written in a functional style. If a particular problem hangs you up, skip it.

Don’t worry about lambda calculus, type theory, category theory, monads, morphisms, or any such abstract concerns. Your functional programming journey may eventually take you to those, but you need not start there. Abstraction is best appreciated in the light of experience with concrete examples. Begin by reading and writing code to solve many small, concrete problems. See what the solutions have in common. That is what you want to learn. The more these solutions seem like variations on a theme, the better.

When I first started learning Clojure, I did so by working Project Euler problems. PE is a lovely and tasteful collection of problems, one that has provided countless hours of instruction and fun to many, many people. While the PE problems are outstanding, I do not claim any special virtue for my solutions. But they should not require any special virtue, that is the point. I want you to see functional programming as a simple and natural way to express intent, as one more way to get things done. If these solutions seem routine, then I have done what I set out to do.

The project repository is is available here. If you want a preview, you can jump straight to the Marginalia docs. Enjoy.