Jake McCrary

Reflections on Stanford's online class experiment

This past fall I took part in Stanford’s online learning experiment. For those of you who are not aware, Stanford gave anyone with Internet access the opportunity to enroll in three different online courses. This was free of charge, not even books were required. Each was an introductory level class, with the three subjects being artificial intelligence, machine learning, and databases (links may die as offered classes change). As far as I know, this was the first time that lecture videos have been paired with scheduled homework, quizzes, and programming assignments at this scale. I only vaguely remember numbers for the AI (artificial intelligence) and ML (machine learning) classes but I believe before classes began there were greater than 100,000 students enrolled apiece. The number of active students was approximately a third of the enrolled number. Even still, this is teaching at an unheard of scale.

I enrolled in both the AI and ML courses. Enrolling in two was more work, but I’m glad I did it. The classes followed slightly different formats and taking both provided a perspective in what style worked better for me.

AI Class

The AI class had video lectures, in video quizzes, homework, and two exams. The videos for this class were short. Each video lasted approximately one to four minutes. This was a nice length as you could easily go back and pick out specific topics to re-watch without jumping around a longer video. The videos showed the professor hand writing notes on pieces of paper. This style made it seem like you were receiving one-on-one tutoring.

At the end of some of the videos a quiz question was asked. These questions did not count towards your final grade. They existed to help you think and learn about the material as it was being presented.

The homework usually consisted of a fewer than 10 questions. You had until the due date to submit or change your answers. You did not get any feedback on the homework until it was graded.

For both of the exams you had about three days to finish the 15 or so questions that were asked.

ML Class

The ML class had video lectures, in video quizzes, homework, and programming assignments. In contrast to the AI class, the ML video lectures were usually five to thirteen minutes long. This made it harder to re-watch specific parts as you had to jump around the video to find different topics. On the plus side, the ML videos could be easily downloaded and watched on any device (you could not do this with the AI lectures). The ML videos also had controls for speeding up playback. I watched the vast majority of the videos at 1.5 times the normal speed.

The video questions for the ML class were similar to the AI class in that they didn’t count towards a final grade and there was usually a max of one per video. Because of the fewer number of videos, there were fewer quizzes than in the AI class. More quizzes would be good, as it forces the student to think instead of simply zoning out while watching the lectures.

The homework in the ML class was different from the AI class in a couple of ways. The largest difference was that you received feedback immediately when you submitted your answers. You were allowed to attempt the homework as often as you liked and your highest score became your score for that assignment. The questions were somewhat different between different attempts to minimize memorization of answers. There was also a minimum waiting period of ten minutes between attempts, but in order to reduce reliance on simply remembering previous attempts I usually waited a few hours to a day between attempts.

The ML class had programming assignments. In these exercises you filled in some Octave code to implement an aspect of machine learning. These exercises where great. Most of the time they made you think about the techniques you were learning that week. It was also nice to get some hands-on experience solving sample machine learning problems. It was rewarding watching my simple spam filter flag email as spam. The programming exercises were best when they weren’t simply a task in translating math to code.

Thoughts on the differences

I enjoyed the ML class homework style, instant feedback upon submission, better than the AI because it provided a quicker feedback cycle. Instead of submitting homework answers and waiting to review mistakes you were able to review instantly. I found this, and being able to repeat homework, to be more effective for learning than the single shot style of the AI class.

I preferred the shortness of the AI lectures. It allowed for easier repetition of lectures and provided more opportunities for quizzes. I also preferred the handwritten style of the AI lectures. The ML lectures felt like I was back in a classroom watching a professor go through some power point slides, adding handwritten notes as the lecture progressed. That isn’t very engaging. The one-on-one style of the AI lectures was more engaging.

I enjoyed both the programming exercises of ML class and the exams in the AI class. Both added an interesting way of learning to their respective class.

Recommendations

If I were designing a course for myself, I found the short videos with many quiz questions style of lecturing to be the more effective style. I would offer homework in a fashion similar to the ML class. Submit as many times as you want, but with a minimum time between submissions. I would up that time to be at least one hour to minimize memorization of answers. My ideal class would also have both programming exercises and exams.

Both classes had some student run question and answer boards (similar to stackoverflow). This was alright but I would look into adding a type of forum that is more suited towards discussions. A Q&A style board is not a great environment for having a discussion that is ordered by time. I think normal forums style with replies ordered by time would be effective and worth an experiment.

Conclusion

I greatly enjoyed taking these two Stanford classes. I think online lectures and homework were an extremely effective way of delivering information and reinforcing learning. I found taking these two classes to be a manageable amount of work. I did pretty much stop reading books while taking these classes and instead focused on watching lectures and doing homework. Had I only taken one class or spent breaks at work watching videos, I think I would have been able to maintain my other activities while taking these classes.

There are quite a few classes being offered at Stanford that start in the near future. Scroll to the bottom of this page to take a look at what Stanford is offering starting in January. I would highly recommend taking a class. MIT also just announced MITx. I haven’t heard a ton of information about it, but it sounds similar and I look forward to its launch.

Continuous testing with Clojure and expectations

I’ve recently started using Jay Fields' Clojure testing library, expectations. I’m not going to explain expectations, Jay already did a great job on his blog, but I will quote its Github page.

expectations is a minimalist’s testing framework

The above quote is absolutely true, which is one of the major reasons I’m liking expectations. It hasn’t been all sunshine though, when I first started using it I had a major problem. It slowed down my usual Clojure workflow.

Up until this point I had stuck to using clojure.test. Combined with emacs, slime, swank, and clojure-test-mode I found the time between making a change to code and running tests to be minimal.

When I switched to expectations the time it took between making a code change and running tests increased. With expectations I couldn’t reevaluate my buffer to get the new tests in my repl environment. Doing so caused the new tests to be there along with the old tests. This meant I needed to switch to the command line to run my tests. This caused me to incur the startup costs of the jvm simply to run my expectations (tests). This was a huge cost compared to what I was used to before.

Introducing lein-autoexpect

To fix my problem I wrote lein-autoexpect. lein-autoexpect is a Leiningen plugin that monitors a project’s source and test directory and when a Clojure file changes it reloads the affected namespaces and runs all the expectations. Using this plugin my turn around time from modifying code to running all of my expectations is practically nothing. Without the cost of the jvm startup there is practically no time wasted between when code is saved and tests are run.

To use lein-autoexpect simply add [lein-autoexpect "0.0.2"] to your project.clj file and fetch the dependency. Then at the command line run lein autoexpect. You’ll see your tests run and then it will just hang there, eagerly waiting for code to change.

1
2
3
4
5
$ lein autoexpect
*********************************************
*************** Running tests ***************
Ran 3 tests containing 3 assertions in 16 msecs
0 failures, 0 errors.

Next time you end up saving you’ll see your tests run again and the following example output appears.

1
2
3
4
*********************************************
*************** Running tests ***************
Ran 4 tests containing 4 assertions in 3 msecs
0 failures, 0 errors.

lein-autoexpect tries to clearly delimit each test session with the banner made of *. This helps keep different runs separate when scrolling through your terminal.

This style of testing is called continuous testing. If you haven’t tried it, I would highly recommend giving it a shot. Even just using it for the last few days changed how I think testing should be done.

Source can be found on Github.

Utilities I like: autojump

autojump is a nifty command line tool that enables quicker jumping between directories. I’ve been using it for a few months now and miss it when I work other machines.

To jump to a directory you type j SUBSTRING_OF_DIR. Example:

1
2
3
4
5
6
$ pwd
/Users/jmccrary
$ j jake
/Users/jmccrary/src/github/jakemcc/jakemccrary.com
$ pwd
/Users/jmccrary/src/github/jakemcc/jakemccrary.com

Above I jumped from my home directory to the root of this website’s code. Being able to jump between directories by just remembering a name (or part of a name) is great. This frees me from having to remember full paths or set up aliases.

autojump works by keeping a database of “time” spent in directories and jumps to the most frequently visited one that match SUBSTRING_OF_DIR. If you are curious as to what that database looks like the tool jumpstat will give you a view.

I used to set up aliases for jumping between projects but now that I’ve trained myself to use autojump I don’t think I’ll ever go back. Not having to do any extra work besides simply entering the root directory of new projects to setup efficient directory movement is great. I think that if you give it a shot for a while you’ll find the same benefits.

If you are on a Mac and use homebrew you can install by doing brew install autojump. For other platforms check out the github page.

A simple way of testing disconnect logic

I’m guessing that software you write connects to some other server. I’m also guessing that how it handles disconnects is tested (if ever tested) by either killing the process it connects to or by pulling out your network cable. I recently stumbled across a nifty Linux command line tool that makes causing disconnects significantly easier.

This tool is tcpkill. To use tcpkill you specify an interface and a tcpdump style filter and it kills traffic on that interface that matches the filter.

For example, if your application has a connection to 192.168.1.130, then to force a disconnect you would execute tcpkill -i eth0 host 192.168.1.130.

tcpkill can be used for more than forcing disconnects. It can also be used as a simple website filter. If Stack Overflow wastes too much of your time then you could simply leave tcpkill -i eth0 host stackoverflow.com running and enjoy your increased productivity.

tcpkill is a pretty useful tool. If you want to install it in Ubuntu it is found in the dsniff package (apt-get install dsniff).

Command line arguments in Clojure

This post is now out of date. The library recommended by this post is now a contrib library. Check out tools.cli for great documentation about handling command line arguments in Clojure.


Write enough Clojure and eventually you will need to handle command line arguments. There are numerous ways of doing this. Keep reading for a brief introduction to three.

Using built-in features

There exists a sequence named *command-line-args* which contains the arguments to your application. Using it is simple, it is just a sequence after all, and it is always available to you. No need to pull in external dependencies that others may not be familiar with.

This simplicity is also a downside. Because only a sequence is provided for you it is up to you to actually figure out the arguments. If you want to do any sort of verification that certain arguments are supplied you write the code that does the verifying. If you want to move away from positional arguments to using command line flags once again it is up to you to write it.

Because of the amount of code required to do any sort of advanced argument handling I tend to use *command-line-args* only for applications that take a single type of argument, for example a file path, and require one or more of this type of argument.

Setup for next two sections

For the next two sections I’m using version 1.5.0 of Leiningen and the specified versions of libraries as stated in the below project.clj file.

1
2
3
4
5
6
7
(defproject blogpost "1.0.0-SNAPSHOT"
  :dependencies [[org.clojure/clojure "1.2.0"]
                 [org.clojure/clojure-contrib "1.2.0"]
                 [clargon "1.0.0"]]
  :dev-dependencies [[swank-clojure "1.2.1"]]
  :run-aliases {:clargon clargon-example
                :cc command-line-example})

I’m using lein run to run the examples. lein run :cc runs the clojure.contrib example. Likewise, running lein run :clargon will run the clargon examples. Both of these commands can be followed by additional arguments that get passed to the application.

Using clojure.contrib.command-line

The next step after using *command-line-args* is to use the library clojure.contrib.command-line. This library provides the function with-command-line that allows you specify requirements and then handles the parsing of the command line arguments for you.

Positives of using clojure.contrib.command-line: * Part of clojure.contrib. Probably extremely low friction to start using it. * No longer need to write your own command line parsing code. * Responds to -h and --help.

A negative of using clojure.contrib.command-line is that the documentation is pretty sparse. This can lead to some fumbling around as you learn how to use it. Another downside is that there isn’t a way of specifying whether an argument is required or optional. This means you must manually check for required arguments and give appropriate error messages to the user.

Below is an example of using clojure.contrib.command-line. It specifies a few different arguments. The --cow argument has a default value of “cow”. --chicken has no default value, if it is left unspecified it will be nil. The line with milk? specifies a boolean value. If --milk (or -m because of the m? specification) is specified at the command line then milk? will be true. extras will collect any additional arguments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(ns command-line-example
  (:require [clojure.contrib.command-line :as ccl]))

(defn -main [& args]
  (ccl/with-command-line args
    "Command line demo"
    [[cow "This is the cows name" "cow"]
     [chicken "This specifies the chickens name"]
     [milk? m? "Should you milk the cow?"]
     extras]
    (println "cow's name: " cow)
    (println "chicken's name: " chicken)
    (println "milk?: " milk?)
    (println "extra args: " extras)))

And here is an example of calling that -main function from the repl.

1
2
3
4
5
$ lein run :cc --cow Herb --milk other args
cow's name:  Herb
chicken's name:  nil
milk?:  true
extra args:  [other args]

Using some other library

Another option is to use some library that isn’t found in clojure.contrib. One example of this is clargon. Clargon is a library that Gaz Jones (his blog post here) wrote. The documentation (both in his blog post and through the github page and tests) is the primary reason I started using it.

Pros of clargon: * Great documentation. Makes it quick to get started. * Can specify functions to transform arguments prior to gaining access to them * You specify if an argument is required or optional. * Responds to -h and --help.

One potential negative of using clargon is that it isn’t a clojure.contrib library. This means there is slightly more friction to start using it on your project as, unlike clojure.contrib, you are probably not already depending on it.

Below is an example similar to the above clojure.contrib.command-line example. One important difference is that some arguments are now specified as either required or optional. If a required argument is not specified then an error is printed and execution stops.

1
2
3
4
5
6
7
8
9
10
11
12
13
(ns clargon-example
  (:require [clargon.core :as c]))

(defn -main
  [& args]
  (let [opts
        (c/clargon
         args
         (c/optional ["--cow" "Specify the cow's name" :default "cow"])
         (c/required ["--chicken" "Chicken's name"])
         (c/optional ["-m?" "--milk?" "should you milk the cow?"]))]
    (println args)
    (println opts)))

optional and required both take a vector that defines the specification of a flag. Starting with the first element in that vector, each element that is a string and starts with a ‘-’ is considered a potential flag for that argument. The last flag is stripped of leading ‘-’ characters and is considered the name of that flag (unless a :name option is specified later). The name is used to look up the value of the argument in the option map that is returned by the clargon function. If the next element after the last flag is a string then it is considered the documentation for that flag. When clargon runs into a non-string element then it and everything after it are considered options and should be specified as key value pairs. Options that do something are :default, :name, and :required.

optional and required both can take a function as a second argument. This function will be passed the argument for that flag and should return a transformed version of it. Below is an example using this functionality to specify a required flag that takes a comma separated list of files. These comma separated files are split apart and stuck into a vector.

1
2
3
4
5
6
7
8
9
10
(ns clargon-example
  (:require [clargon.core :as c]))

(defn -main
  [& args]
  (let [opts (c/clargon
              args
              (c/required ["--files" "Files to process"]
                          #(vec (.split % ","))))]
    (println "Parsed opts: " opts)))

Below is the above example being ran.

1
2
$ lein run :clargon --files one.txt,two.txt,three.txt
Parsed opts:  {:files [one.txt two.txt three.txt]}

Clargon supports some more advanced nested argument handling that I’m not going to go into here. If you want to know more about clargon I’d recommend reading reading Gaz’s blog post and the clargon readme and tests.

End

There are many more ways to handle command line parsing in Clojure. You are not limited to any of the three above. I’ve personally found clargon to hit all of my needs and plan on continuing to use it.

Creating a SQL table with a composite primary key in Clojure

I was interacting with a SQL database using Clojure and needed to create a table so I turned to create-table from clojure.contrib.sql. Looking at the docs for create-table it seemed pretty straight forward. To create a table with columns date, id, symbol, price, and quantity you would write the following.

1
2
3
4
5
6
(create-table "orders"
              [:date     "date"]
              [:id       "integer"]
              [:symbol   "char(10)"]
              [:price    "integer"]
              [:quantity "integer"])

The above works. I also wanted to specify that columns date and id to form a composite primary key. I wasn’t sure how to specify a composite primary key with create-table and ended up diving into its code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defn create-table
  "Creates a table on the open database connection given a table name and
  specs. Each spec is either a column spec: a vector containing a column
  name and optionally a type and other constraints, or a table-level
  constraint: a vector containing words that express the constraint. All
  words used to describe the table may be supplied as strings or keywords."
  [name & specs]
  (do-commands
   (format "CREATE TABLE %s (%s)"
           (as-str name)
           (apply str 
             (map as-str
              (apply concat 
               (interpose [", "]
                (map (partial interpose " ") specs))))))))

Looking at create-table we can see it creates a SQL statement which is then executed by do-commands. In order to have a composite key we need do-commands to execute a SQL statement that looks similar to below.

1
2
3
4
5
6
7
8
CREATE TABLE track(
  date date,
  id integer,
  symbol char(10),
  price integer,
  quantity integer,
  PRIMARY KEY (date, id)
)

Let’s break down create-table to figure out what we need to pass it to make do-commands run the above statement. The code for create-table is repeated below with comments pointing out what step lines up the code.

1
2
3
4
5
6
7
8
9
10
(defn create-table
  [name & specs]
  (do-commands                                              ; step 7
   (format "CREATE TABLE %s (%s)"                           ; step 6
           (as-str name)
           (apply str                                       ; step 5
             (map as-str                                    ; step 4
              (apply concat                                 ; step 3
               (interpose [", "]                            ; step 2
                (map (partial interpose " ") specs))))))))  ; step 1
  1. First create-table takes the sequences in specs and puts a space between each element in each sequence.
  2. The result of step 1 then has a vector containing a comma and a space interposed between each element of it.
  3. concat combined with apply is used to combine each element of the result of step 2 into a single sequence.
  4. as-str (from c.c.string) is mapped over the result of step 3 to make sure every element is a string.
  5. str is used to make one string out of the sequence of strings from step 4.
  6. format is used to substitute in name and the result of step 5 to create the SQL statement.
  7. do-commands executes the statement created in step 6.

Knowing how create-table works now allows us to specify the arguments that will create the orders table with the composite primary key of date and id.

1
2
3
4
5
6
7
(create-table "orders"
              [:date     "date"]
              [:id       "integer"]
              [:symbol   "char(10)"]
              [:price    "integer"]
              [:quantity "integer"]
              ["PRIMARY KEY" "(date, id)")

Generating test cases in Clojure

Recently I was writing some data mining Clojure code which needed to parse a log file and do some transforms of the data. Some of the transforms were dependent on data found across multiple lines. There was no ordering or proximity guarantees to these lines.

This required the code to handle a variety of situations. After writing a couple simple tests and getting those passing I wanted to more extensively test my solution. I was lazy though and did not want to hand code all of the potential orderings. Enter permutations.

permutations is a function out of clojure.contrib.combinatorics. As the name suggests, you give it a collection and it returns a lazy sequence containing all the different permutations of the elements in that collection. An example is below.

1
2
3
4
5
user>(ns generate)
generate>(use '[clojure.contrib.combinatorics :only [permutations]])
nil
generate> (permutations [:a :b :c])
((:a :b :c) (:a :c :b) (:b :a :c) (:b :c :a) (:c :a :b) (:c :b :a))

You can already see where this is going. I was able to use permutations to generate all the potential different orderings of the input. This saved me the trouble of having to do that by hand.

One difficulty of generating test inputs pragmatically is telling what sort of inputs caused it to fail. To get around this I used the rarely used (at least in code I’m working on) second argument of clojure.test’s is. This second argument is a message that prints on a failure.

Below is a contrived example of using permutations to test an obviously wrong silly-add function. silly-add is defined below.

1
2
3
4
5
6
generate> (defn silly-add
              [x & xs]
              (if (zero? x)
                  (apply + 40 xs)
                  (apply + x xs)))
#'generate/silly-add

Below is a test that uses permutations to exercise silly-add with all the potential orderings three input numbers. Note that it takes advantage of the second argument to is. Without this we would not know what input caused the failure.

1
2
3
4
5
6
7
generate> (use 'clojure.test)
nil
generate> (deftest generate-some-tests
            (doseq [input (permutations [1 0 9])]
                   (is (= 10 (apply silly-add input))
                       (str "Failed on input: " (seq input)))))
#'generate/generate-some-tests

Running the test we see that there is clearly an error.

1
2
3
4
5
6
7
8
9
10
11
12
generate> (run-tests)
Testing generate

FAIL in (generate-some-tests) (NO_SOURCE_FILE:1)
Failed on input: (0 1 9)
expected: (= 10 (apply silly-add input))
  actual: (not (= 10 50))

FAIL in (generate-some-tests) (NO_SOURCE_FILE:1)
Failed on input: (0 9 1)
expected: (= 10 (apply silly-add input))
  actual: (not (= 10 50))

permutations saved me a bit of time and let me test some situations that I otherwise would not have tested. This actually exposed a subtle bug in my code. Hopefully it can do the same for you.

Quickly starting a powerful Clojure REPL

I often find myself browsing the Internet and then suddenly I want to have a Clojure REPL at my fingertips. As I’ve become better with emacs and paredit I’ve become dependent on the powerful editing this combo affords. The rest of this post details how I changed my five step process into a two step process. It does not explain basic emacs/slime setup but rather explains how I cut a few steps out of a suboptimal workflow for getting a powerful Clojure REPL up and running in emacs.

My previous workflow was the following:

  1. Open a terminal
  2. Change to the root of Clojure project where I use Leiningen and have swank-clojure as a dependency.
  3. Run the command lein swank
  4. Start emacs
  5. Run M-x slime-connect

This five step process was terrible. From me seeing something interesting to try to having a REPL open took too much time.

Today I changed my process so it on takes two steps. They are:

  1. Start emacs
  2. Run M-x clojure-swank

This is a much better. I’ll admit had a lot of room for improvement so it wasn’t too hard to make it better. Below are the steps I took to cut three steps.

First, using Leiningen 1.4.0, I ran lein install swank-clojure 1.3.0-SNAPSHOT. This installed a script called swank-clojure into $HOME/.lein/bin. When run, this script starts a swank server waiting for connections on port 4005.

Next I wrote a function in elisp that gives emacs the ability to call the newly installed swank-clojure script, wait for the swank server to start, and then connect to it. This function, clojure-swank, can be seen below. It creates a buffer named *clojure-swank*, runs the newly installed script, and captures the output in the freshly created buffer. When the “Connection opened” line appears slime-connect is called, connecting emacs to the freshly started swank server. After this we are at the REPL with all the advantages that emacs and paredit give us.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defun clojure-swank ()
  "Launch swank-clojure from users homedir/.lein/bin"
  (interactive)
  (let ((buffer (get-buffer-create "*clojure-swank*")))
    (flet ((display-buffer (buffer-or-name &optional not-this-window frame) nil))
          (bury-buffer buffer)
          (shell-command "~/.lein/bin/swank-clojure &" buffer))
    (set-process-filter (get-buffer-process buffer)
                        (lambda (process output)
                           (with-current-buffer "*clojure-swank*" (insert output))
                           (when (string-match "Connection opened on local port +\\([0-9]+\\)" output)
                             (slime-connect "localhost" (match-string 1 output))
                             (set-process-filter process nil))))
    (message "Starting swank.. ")))

I’ve also written a clojure-kill-swank function for stopping the swank server.

1
2
3
4
5
6
7
8
9
10
11
12
(defun clojure-kill-swank ()
  "Kill swank process started by lein swank."
  (interactive)
  (let ((process (get-buffer-process "*clojure-swank*")))
    (when process
      (ignore-errors (slime-quit-lisp))
      (let ((timeout 10))
        (while (and (> timeout 0)
                    (eql 'run (process-status process)))
          (sit-for 1)
          (decf timeout)))
      (ignore-errors (kill-buffer "*clojure-swank*")))))

Both of those functions need to be added to a location where they will get defined on emacs start-up. Once this is done the powerful REPL you are used to emacs providing can be at your finger tips in practically no time at all.

Trampolining through mutual recursion with Clojure

The other day I stumbled across some Clojure code that used mutual recursion. Mutual recursion can be a valuable tool when solving a problem. Unfortunately because of the lack of tail call optimization on the JVM this can be a dangerous technique when writing Clojure code. It can be easy to forget about this limitation and end up writing code that blows the stack.

Take the classic even/odd checking code from the Wikipedia page. If we just translate it to Clojure it will cause a stack overflow error when we pass in a large number. The massive number of function calls require before returning causes too much memory to be consumed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(declare my-odd?)

(defn my-even? [n]
  (if (zero? n)
    true
    (my-odd? (dec (Math/abs n)))))

(defn my-odd? [n]
  (if (zero? n)
    false
    (my-even? (dec (Math/abs n)))))

user> (my-even? 1000000)
; Evaluation aborted. <- this is a result of java.util.StackOverflowError

Luckily since Clojure 1.0 there has been a useful function for dealing with this. trampoline, with minor modifications to your code, can be used to get around the lack of tail call optimizations (docs here).

trampoline takes a function (and, if needed, arguments to pass into the function) and calls it. If the function returns a function then trampoline calls that. As long as functions are returned trampoline will continue calling them. When a non-function value is returned trampoline returns, passing through the value.

To make our sample code work with trampoline we simply change our functions to return a closure which wraps the call that was previously being executed. This just entails putting a # before the final s-exp. This takes advantage of Clojure’s anonymous function syntax to change the function call into a closure which is returned.

1
2
3
4
5
6
7
8
9
(defn my-even? [n]
  (if (zero? n)
    true
    #(my-odd? (dec (Math/abs n)))))

(defn my-odd? [n]
  (if (zero? n)
    false
    #(my-even? (dec (Math/abs n)))))

By doing this we’ve changed how the caller interacts with my-even? and my-odd?. It now needs to be called by trampoline.

1
2
user> (trampoline my-even? 1000000)
true

Now we no longer suffer from the stack overflow error.

I think we can still do better though, because now the caller of my-even? and my-odd? suffers since they are forced to remember to use trampoline. By forcing this on the caller, we’ve pushed what should be hidden implementations details into the callers code. We can fix this by pushing the use of trampoline into our functions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defn my-even? [n]
  (letfn [(e? [n]
              (if (zero? n)
                true
                #(o? (dec (Math/abs n)))))
          (o? [n]
              (if (zero? n)
                false
                #(e? (dec (Math/abs n)))))]
    (trampoline e? n)))

(defn my-odd? [n]
  (not (my-even? n)))

user> (my-even? 1000000)
true
user> (my-odd? 1000000)
false

Now we have the best of both worlds. Mutual recursion without the worry of a stack overflow and functions that don’t force the caller to be aware of the implementation details.

Inserting values into a nested map in Clojure

Recently I was writing some Clojure with a coworker and we needed to insert values into a nested map structure. Our first solution (and example of using it at the repl) looked something like this.

1
2
3
4
5
6
7
8
9
(defn add-to-cache [cache key1 key2 data]
  (let [entry (get cache key1 {})
        new-entry (assoc entry key2 data)]
    (assoc cache key1 new-entry)))

user> (-> (add-to-cache {} :chicago :lakeview :jake)
          (add-to-cache :sf :mission :dan)
          (add-to-cache :chicago :wickerpark :alex))
{:sf {:mission :dan}, :chicago {:wickerpark :alex, :lakeview :jake}}

This worked but seemed overly verbose for doing what (in our minds) should have been a simple operation. After some digging around in the docs we found the function assoc-in. This useful function allowed us to greatly simplify the code.

1
2
3
4
5
6
7
(defn add-to-cache [cache key1 key2 data]
  (assoc-in cache [key1 key2] data))

user> (-> (add-to-cache {} :chicago :lakeview :jake)
          (add-to-cache :sf :mission :dan)
          (add-to-cache :chicago :wickerpark :alex))
{:sf {:mission :dan}, :chicago {:wickerpark :alex, :lakeview :jake}}

Much simpler and easier to read. The next person to look at the code will be able to quickly skim and tell what the code is doing.

assoc-in can also be used with nested associative structures like vectors.

1
2
3
4
user> (assoc-in [[0 1] [:a :b]] [0 1] :z)
[[0 :z] [:a :b]]
user> (assoc-in [[0 1] [:a :b]] [1 1] :z)
[[0 1] [:a :z]]

Hopefully this post makes searching for how to insert into nested maps slighly easier for the next person who thinks there must be a better way for doing this.