Samrat Man Singh


Hi! I’m Samrat, a programmer from Nepal.


Arithmetic with Instaparse


Last week I started playing around with the Instaparse library, which makes writing parsers really easy in Clojure. What Instaparse does is take the formal definition of a language and give you a parser for that language. You can then use that parser on a string, possibly containing something in that language. You need to write the grammar in one of two forms: Extended Backus-Naur Form(EBNF) or Augmented Backus-Naur form(ABNF). You can read about these grammars in Matt Might’s excellent blog post: The language of languages. I’ve picked EBNF as my grammar of choice for now, admittedly without having studied the nuances of each. Instaparse does let you mix up EBNF and ABNF in your grammar but you might end up unnecessarily complecting things for yourself.

If the string contains a syntactically correct string, the parser gives you a tree. Instaparse also provides you with the tools to transform that tree into something else, say a Clojure form, so that it can get evaluated. To get familiar with the Backus-Naur form(and its descendants, EBNF and ABNF), I recommend going through Matt’s blog post linked above.

In this post, we’ll write a grammar for parsing arithmetic expressions, so that we can turn something like "11*1-1/5" into:

(clojure.core/- (clojure.core/* 11 1) (clojure.core// 1 5))

Notice that the parser has spit out the Clojure form with the correct precedence, that is multiplicative operators get evaluated before additive operators.

The grammar

Here is the grammar that I came up with. It handles the four basic arithmetic operators: +, -, * and /. + and - have the same precedence, as do * and /. The multiplicative operators(* and /) have higher precedence than the additive operators(+ and -).

(def arithmetic
   "<expr> = additive-expr | multiplicative-expr | number
    additive-expr = expr (('+' | '-' ) expr)
    multiplicative-expr = number ( ('*' | '/') (multiplicative-expr|number) )
    number = #'-?[0-9]+'"))

Let us now take a closer look at the grammar. Starting from the bottom-up, a number is any integer. A multiplicative-expr is any number multiplied or divided by another multiplicative-expr or a number. Notice that a multiplicative-expr cannot contain an additive-expr.

Next, an additive-expr is any expr added or subtracted with any other expr. expr is defined in the first line to be one of additive-expr, multiplicative-expr or number. The angled brackets around expr means that the :expr tag will be hidden in the parse tree Instaparse produces.

The definitions of additive and multiplicative expressions implicitly specify that multiplicative operators have higher precedence.

Trying out the parser

Let us now try out the parser to see if it actually works:

First, let’s try the simplest possible operation:

user> (arithmetic "42")
([:number "42"])

A bit more compound expression:

user> (arithmetic "2+2")
([:additive-expr [:number "2"] "+" [:number "2"]])

And now a slightly ridiculous expression:

user> (clojure.pprint/pprint (arithmetic "2+2-2/2*2-1/1+1"))
  [:number "2"]
   [:number "2"]
     [:number "2"]
     [:multiplicative-expr [:number "2"] "*" [:number "2"]]]
     [:multiplicative-expr [:number "1"] "/" [:number "1"]]
     [:number "1"]]]]])

Transforming the parse tree

Like I mentioned above, we really want to have the arithmetic expression parsed into a Clojure form. To do this we will specify what transformations we want:

(def parse-tree->sexp
  {:additive-expr (fn [operand operator & rest]
                    (if (= operator "+")
                      `(+ ~operand ~@rest)
                      `(- ~operand ~@rest)))
   :multiplicative-expr (fn [operand operator & rest]
                          (if (= operator "*")
                            `(* ~operand ~@rest)
                            `(/ ~operand ~@rest)))
   :number read-string})

And finally to get the Clojure form we can run the insta/transform functions like this:

user> (insta/transform parse-tree->sexp (arithmetic "2+2*2-2"))
((clojure.core/+ 2 (clojure.core/- (clojure.core/* 2 2) 2)))

Parts-of-speech tagging with Clojure


One of the classical problems in Natural Language Processing is parts-of-speech tagging i.e. given a sentence of length n, find the sequence of part-of-speech tags for each word in the sentence. For example,

$$\text{POS(“the”,“man”,“walks”) = (“article”,“noun”,“verb”)}$$

There are several approaches to parts-of-speech tagging, and I’ve managed to build a fairly simple tagger based on something called Hidden Markov Models. There are several resources explaining HMMs out there already so I won’t try explaining that in detail here.

Basically what you need to know is that we model the tag sequence to be a first-order Markov process. This means that the likelihood of a tag occurring is determined by what the previous tag was. So we’re going to have to obtain a map that looks like this:

{:noun {:verb 0.7
        :article 0.1
        :noun 0.2}
 :article {:noun 0.8
           :verb 0.1
           :article 0.1}
 :verb {:noun 0.4
        :verb 0
        :article 0.6}

The probability of a verb following a noun is 0.7, an article following a noun is 0.1, and so on. These are called the transition probabilities.

The next thing we need to obtain is called the emission probabilities, which is the probability of a tag emitting a word. When represented in a Clojure map, this looks something like:

{:noun {"man" 0.04
        "samrat" 0.001
 :verb {"walks" 0.002}
} ;; and so on

The Brown tagged corpus

To obtain these two maps, we will use the Brown corpus which is a pretty substantial collection of sentences tagged painstakingly by humans way back in the 60s. A sentence in the Brown corpus looks like this:

 The/at three/cd men/nns stepped/vbd out/rp to/in the/at side/nn
 to/to wait/vb for/in Captain/nn-tl Clemens'/np$ signal/nn ./.

Here, “The” is tagged with “at”, “three” with “cd”, and so on. To understand what these tags mean, you could open up this reference but that is unnecessary for now.

Instead of dealing with the raw Brown corpus, we will use a file containing the processed information we need. The contents of this file looks like this:

2 WORDTAG nns 1880s
9 WORDTAG in underneath
1 WORDTAG vbn agitated
13510 1-GRAM cd 
3282 1-GRAM bed 
49 1-GRAM rb-hl
265 2-GRAM vb wrb 
20 2-GRAM jj-tl jj 
5 3-GRAM in jj-tl jj 
6 3-GRAM cc rbr vbn 
1 3-GRAM beg pp$ nn 

The code used to obtain these counts is here. I won’t discuss that here either. You can find the counts file here.

The code

The namespace declaration:

(ns pos-tagger.hmm
  (:require [clojure.string :as str]
            [clojure.core.match :refer [match]]))

Next is the code to read brown.counts file mentioned above:

(defn read-brown-counts
  (with-open [rdr ( counts-file)]
    (reduce (fn [[ngram-counts word-tag-counts] line]
              (let [split-line (str/split line #"\s")]
                (match split-line
                       [c "3-GRAM" t u v] [(assoc ngram-counts [t u v] (Integer/parseInt c))
                       [c "2-GRAM" t u] [(assoc ngram-counts [t u] (Integer/parseInt c))
                       [c "1-GRAM" t] [(assoc ngram-counts [t] (Integer/parseInt c))
                       [c "WORDTAG" t word] [ngram-counts
                                             (assoc-in word-tag-counts [t word] (Integer/parseInt c))])))
            [{} {}]
            (line-seq rdr))))

This is simply loading what was in the counts file into memory. This gives us a vector of two maps which we’ll use next:

(let [counts (read-brown-counts "brown.counts")]
  (def ngram-count (first counts))
  (def word-tag-count (second counts))
  (def tag-space (conj (keys word-tag-count) "START")))

tag-space is the set of all possible tags. The "START" tag is something the code producing brown.counts adds to the beginning of sentences. It is useful to have that because it makes the job of calculating the transition probability of the first tag($t(\text{START}\Rightarrow{t_1})$, which is really called the initial state probability) easier.

With this we can obtain the transition and emission probabilities we wanted:

(defn transition-probability
  (try (/ (ngram-count ngram)
          (ngram-count (butlast ngram)))
       (catch Exception _ 0)))

(defn emission-probability
  "Probability of tag emitting word."
  [[tag word]]
  (try (/ (get-in word-tag-count [tag word])
          (apply + (vals (word-tag-count tag))))
       (catch Exception _ 0)))

Now, using these two functions it is possible to calculate the probability of any tag sequence, $t_1,t_2,..t_n$ for a given sentence, $x_1,x_2,..x_n$:

$$P(t_1,t_2\vert{x_1,x_2}) = t(START\Rightarrow{t_1})
e({t_1}\Rightarrow{x_1}) t({t_1}\Rightarrow{t_2})

However, what we want to find is the most likely tag sequence, which is simply the tag sequence for which $P(t_1,t_2,..t_n\vert{x_1,x_2,..x_n})$ is the maximum. Now, if given a sentence, an index(posn) and the tag at posn, the following function gives the probability of the most likely tag sequence upto posn:

(def viterbi
  "Returns the probability of the most likely tag sequence upto posn."
   (fn [sentence tag posn]
     (if (= posn 1)
       (* (emission-probability [tag (first sentence)])
          (transition-probability ["START" tag]))
       (* (emission-probability [tag (nth sentence (dec posn))])
          (apply max (map (fn [prev-tag]
                            (* (transition-probability [prev-tag tag])
                               (viterbi sentence prev-tag (dec posn))))

The function is memoized in order to avoid doing repeated computations which occur due to the recursive calls to itself.

To find the most likely tag for a posn, we find the $argmax$ of viterbi:

(defn viterbi-tag
  "Return the most likely tag for word at posn."
  [sentence posn]
  (apply max-key (fn [tag] (viterbi sentence tag posn))

Finally, to get the tag sequence:

(defn tag-sequence
  (map (partial viterbi-tag sentence)
       (range 1 (inc (count sentence)))))

Making a streaming API from scraped data using Clojure


I recently found myself having to play around with some stock exchange data. The stock exchange in Nepal, unsurprisingly, doesn't provide a data API so I had to scrape their website. The non-realtime data isn't very interesting, just regular old scraping made a little more tedious by the fact that whoever designed the website didn't know about how to use HTML id attributes.

Now, to the live trading data. For the live data, the website shows a ticker of stock prices, which I think is a really bad representation of the data. If you want to know at what price ZXY was traded at, you have to wait till the end of the ticker. If the ZXY stock was all you were interested in, you'd still have to bear with the rest of the ticker. And to get the actual live data, you have to hit refresh. This is kind of okay on TV, but having to do this on a computer is terrible. Computers are more interactive than TV sets and should be treated as such. Bret Victor has given a great talk titled "Stop Drawing Dead Fish" that conveys this in a much more articulated way. The talk is about art, but I think having data represented on a ticker is like drawing dead fish.

So, I got around to thinking about how to build a better interface for the live trading data. To do that, I first had to build a streaming API which pushes stock prices as the trades happen. And doing that wasn't all that complicated, thanks to, watches and http-kit.

The first step is to pull in the page and scrape out the ticker data to get a map of the latest trades for each company like this:

{"ABC" {:price 100
        :volume 12} 
 "FOO" {:price 432
        :volume 22}
 "BAR" {:price 94
        :volume 34}}

I used laser for the scraping- you could use that; Enlive seems to be great too. I won't go into the details of the scraping.

Store this into an atom, lets call this atom current-prices. After, say, 5 seconds when we scrape again, new trades will have happened and the map we get will be different than the one above:

{"ABC" {:price 100
        :volume 12}
 "FOO" {:price 434 ;; this has changed
        :volume 300}
 "BAR" {:price 90 ;; this too
        :volume 25}}

Since we called our atom current-prices, it would be sensible to reset! it now to hold the second, more recent map of trading data. Its nice that we now have the trading data in a Clojure data structure but note that reset!-ing our atom is really just the equivalent of refreshing our browser- we aren't done yet.

Now, Clojure comes with a handy function called diff which is in the namespace. Here's how it works:

(require '

( {:a 42 :b "foo"}
                   {:a 43 :b "foo"})
;; ({:a 42} {:a 43} {:b "foo"})

The diff function tells how one data structure varies from another. The first map shows the key-value pairs that exist in the first map but not in the second; the second map shows the pairs existent in only the second map. And the third map shows the pairs that exist in both of the maps.

diff works on seqs too, but we won't bother with that right now.

Let's see what we get when we diff the older and newer versions of our current-prices atom:

( {"ABC" {:price 100
                           :volume 12} 
                    "FOO" {:price 432
                           :volume 22}
                    "BAR" {:price 94
                           :volume 34}}

                   {"ABC" {:price 100
                           :volume 12}
                    "FOO" {:price 434 ;; this has changed
                           :volume 300}
                    "BAR" {:price 90 ;; this too
                           :volume 25}})
;; ({"FOO" {:price 432, :volume 22},  "BAR" {:price 94, :volume 34}}
;;  {"FOO" {:price 434, :volume 300}, "BAR" {:price 90, :volume 25}}
;;  {"ABC" {:price 100, :volume 12}})

Great. This is telling us that no trade happened for ABC. For FOO and BAR this is showing the older and newer trading data.

Now, lets add a watch to our current-prices atom, so that whenever we pull in new data, the watch function finds out the stocks for which new trades happened and pushes its prices to the appropriate clients.

(add-watch current-prices :send
           (fn [key identity old new]
             (let [diff ( old new)
                   new-trades (second diff)]
               (doseq [client @clients
                       trade new-trades]
                 (send! client (str (key trade)
                                    " traded for "
                                    (:price (val trade))))))))

Every time the current-prices atom is reset! or swap!-ed, the function above gets called.

Here we're simply sending all our clients a string. In practice, you'd probably pass JSON or EDN to only those clients who are interested in a specific company. The send! function is from http-kit which has a unified API for WebSockets, HTTP long polling and streaming. I wrote about using Websockets with http-kit in a previous post.

And that's it. We have now built a streaming API using just a watch function and I think that's pretty cool.

Websockets with Clojure and http-kit


Table of Contents

Websocket is a relatively new network protocol that enables a connection between client and server to have long-living connections. What this means is that servers can push things to clients and vice-versa through the same connection.

In this post, I'll provide a brief walkthrough to setting up a small dashboard web app using Clojure and http-kit. I am assuming that you are familiar with Clojure and already have Leiningen installed. You can find the final codebase in this Github repo.

1 A (fake) realtime happiness gauge

Lets say that one of your main goals in life is to maximize happiness in this world. Well, you'd want a way to measure what the happiness level in the world is right now so that you can go save the day by making some pissed people happy. Which is why we'll build a happiness meter of sorts.

But this post isn't really about how to go about measuring happiness so we'll just use Clojure's handy rand function to create some random happiness data.

2 Project setup

We'll be sending our data to the browser using JSON which will be parsed using Javascript and drawn into a graph. The first thing you need to do is create a new project:

lein new happy-dashboard

And add some dependencies to your project:

(defproject happy-dashboard "0.1.0-SNAPSHOT"
  :description "A dashboard that shows how happy the world is."
  :url ""
  :license {:name "Eclipse Public License"
            :url ""}
  :dependencies [[org.clojure/clojure "1.5.1"]
                 [ring/ring-json "0.2.0"]
                 [http-kit "2.0.0"]
                 [ring/ring-devel "1.1.8"]
                 [compojure "1.1.5"]
                 [ring-cors "0.1.0"]]
  :main happy-dashboard.core)

You are probably already familiar with compojure and cheshire. http-kit might be new to you. http-kit is an alternative to the Ring Jetty adapter(this is what you probably use if you create your web apps using lein new compojure myapp). The main reason I'm using http-kit here is because it provides an easy interface to Websocket.

ring-devel is required for hot code reloading, so that you won't have to restart the server each time you make a change. ring-cors is required to enable CORS, so that the whole world has open access to our happiness data.

3 Websocket server

Because we decided to delegate our happiness-measuring to Clojure's rand function, our program actually turns out to be quite small so we'll just use one namespace; here is our program in its entirety:

(ns happy-dashboard.core
  (:use [compojure.core :only (defroutes GET)]
  (:require [compojure.route :as route]
            [compojure.handler :as handler]
            [ring.middleware.reload :as reload]
            [cheshire.core :refer :all]))

(def clients (atom {}))

(defn ws
  (with-channel req con
    (swap! clients assoc con true)
    (println con " connected")
    (on-close con (fn [status]
                    (swap! clients dissoc con)
                    (println con " disconnected. status: " status)))))

(future (loop []
          (doseq [client @clients]
            (send! (key client) (generate-string
                                 {:happiness (rand 10)})
          (Thread/sleep 5000)

(defroutes routes
  (GET "/happiness" [] ws))

(def application (-> (handler/site routes)
                      :access-control-allow-origin #".+")))

(defn -main [& args]
  (let [port (Integer/parseInt 
               (or (System/getenv "PORT") "8080"))]
    (run-server application {:port port :join? false})))

At this point if you start the server using lein run and point your browser to http://localhost:8080/happiness, you'll see the pushing going on. But note that this isn't Websocket. What happened was because you opened that page in your browser, with a http:// http-kit magically used HTTP long-polling instead. Its a similar technology to Websocket that was common before Websocket came along. To use Websocket you have to use the ws:// URI scheme, which usually won't work in your browser's address bar. We'll get to that in just a minute.

The most interesting function is the ws function. When it gets a request it assoc's it into the clients atom and tells us that someone connected. You'll notice it also has an (on-close …) form in which we tell it to dissoc the function when our user closes his/her browser tab.

Besides that the future form simply sends a small piece of JSON every 5 seconds to all connected clients. I think the call to (send! …) is pretty obvious except for the false part, which tells the server to keep the connection open after sending our message. By default, send! closes the connection after it has sent a message.

Note that we are able to send! messages any time, as long as the connection hasn't closed.

4 Front end

Now that we are successfully pushing all of that happiness data around, we can finally represent it in a neat little chart. In the last section, we found that its not possible to open a Websocket connection like we usually open up HTTP connections. The way we usually open Websocket connection from inside a browser is using the Websocket Javascript API, like this:

var socket = new WebSocket("ws://localhost:8080/happiness");

And that will open a Websocket connection instead of an HTTP one. Then, you can tell Javascript what to do with the messages it receives:

socket.onmessage = function(event) {

Now to draw those happiness charts: we could couple it with our Clojure app and that would work but since we have CORS enabled we'll instead put it anywhere we want.

Here is our frontend code:

<!DOCTYPE html>
<script type="text/javascript" src=""></script>
<script type="text/javascript" src="chartkick.js"></script>

<script type="text/javascript">
var data = [], timestamps = [];
var socket = new WebSocket("ws://localhost:8080/happiness");

socket.onmessage = function(event) {
            timestamps.push(new Date);

function refreshChart(){
    new Chartkick.LineChart("chart", zip([timestamps,data]));

function zip(arrays) {
    return arrays[0].map(function(_,i){
        return{return array[i];});

  <div id="chart" style="height: 300px;"></div>

I'm using chartkick.js with Google Charts to produce a chart but you could use your favorite Javascript chart library instead.

And that's it. If you open the HTML file, it should start getting messages from the Websocket server and you should see a graph that's being updated:


Building a database-backed Clojurescript app


In my previous post, I gave a pretty quick introduction to Clojurescript. If you haven’t already, I recommend you read through that post. This post assumes that you have some Clojure knowledge and already have Leiningen running.

In this post, I’ll show how to create a SQL database-backed Clojurescript app(you were expecting NoSQL, weren’t you?). For the lack of a better idea, I’m going to walk you through building a trivial app that helps keep track of books you’ve read. You can view the source code for the app on Github.

The Setup

We’ll use Noir as the back-end(with Hiccup generating the HTML); on the front-end besides using Clojurescript we’ll also use a Clojurescript library called Fetch, which makes client-server communication(as in AJAX) really easy and another one called enfocus for DOM manipulation(mainly stuff like event-handling). For dealing with the database we’ll use To compile our Clojurescript we’ll use a Leiningen plugin called lein-cljsbuild.

So, first create a Noir project called books(I’m assuming you’re using Leiningen 2):

lein new noir books

Now, let’s add some dependencies and some Clojurescript-specific settings to our project.clj:

(defproject books "0.1.0-SNAPSHOT"
            :description "Books- A database-backed Clojurescript app."
            :dependencies [[org.clojure/clojure "1.4.0"]
                           [noir "1.3.0-beta3"]
                           [fetch "0.1.0-alpha2"]
                           [org.clojure/java.jdbc "0.2.3"]]
            :plugins [[lein-cljsbuild "0.2.8"]]
            :cljsbuild {
                        :builds [{
                                  :source-path "src/cljs"
                                  :compiler {
                                             :output-to "resources/public/js/main.js"
                                             :optimizations :whitespace
                                             :pretty-print true}}]}
            :main books.server)

If you’ve gone through the first post, this should be pretty self-explanatory.

Adding a database

The first thing we’re going to do is set up our database. For the sake of simplicity, in this post I’ll use SQLite, however I think its safe to advise you guys not to use SQLite in production. Anyway, you’ll also need to add [org.xerial/sqlite-jdbc "3.7.2"] to the list of dependencies.

Pull in the newly added dependency using lein deps, then create a file in src/books/models called db.clj. To that file add:

(ns books.models.db
  (:require [ :as sql]))

(def db
  {:classname   "org.sqlite.JDBC"
   :subprotocol "sqlite"
   :subname     "db/database.db"

(defn init-db []
    (sql/with-connection db
       [:title "varchar(250)"]
       [:review "varchar(500)"]))
    (catch Exception ex
      (.getMessage (.getNextException ex)))))

We’ve set the path of the SQLite database to db/database.db, so you’ll need to create a folder called db at the root of the project. Now, to initialize the database, run lein repl then

=> (use 'books.models.db)
=> (init-db)

If you don’t get an error the database file should have been created. You can check if its present inside db/. The database will have a table called :books with just two fields- :title and :review.

Now, we’ll add some helper functions to db.clj to make our dealings with our database a lot simpler:

(defn add-book
    (sql/insert-record :books book)))

(defn db-read-all
  (sql/with-connection db
    (sql/with-query-results result
      ["SELECT * FROM books"]
      (into [] result))))

The add-book function does exactly what you’d expect and the code should be pretty easy to understand. The argument to the function should be a Clojure hash-map, so a call to that function would look like:

(add-book {:title "Clojure Programming" :review "Great book. I really need to work on completing this one, though."})

The db-read-all function pulls all entries from the :books table and returns a vector of the entries.


Now, we’ll work on our views. Open src/books/views/welcome.clj to edit it. This is what it should look like:

(ns books.views.welcome
  (:require [books.views.common :as common])
  (:use [noir.core :only [defpage]]

(defpage "/" []
          [:h1 "Books"]
           (label {} "title" "Title: ")
           (text-field {:class "title"} "title")
           (label {} "review" "Review: ")
           (text-area  {:class "review"} "review")
           [:button {:class "submit"} "Submit"]]))

(defremote add-book-to-db [book]
  (println book)
  (add-book book))

The most important part of this is the defremote definition. Its defining a fetch remote, which simply calls the add-book function from the books.models.db namespace that we defined above. The little println call is simply there to help us see in a short while whether our program is working.


Now, we finally get to writing some Clojurescript code. Create a new file inside src/cljs/main.cljs and into it type in the following:

(ns books.cljs.main
  (:require [enfocus.core :as ef]
            [fetch.remotes :as remotes])
  (:require-macros [enfocus.macros :as em]
                   [fetch.macros :as fm]))

(defn get-book-title []
  (em/from (em/select ["#title"]) (em/get-prop :value)))

(defn get-book-review []
  (em/from (em/select ["#review"]) (em/get-prop :value)))

(defn get-book-data []
  {:title (get-book-title)
   :review (get-book-review)})

(defn push-book []
  (fm/remote (add-book-to-db (get-book-data))))

(em/defaction setup []
  [".submit"] (em/listen :click push-book))

(set! (.-onload js/window) setup)

In the namespace declaration you’ll notice that we’re bringing in stuff into our namespace from the Clojurescript libraries that we talked about in the beginning- Fetch and Enfocus. You’ve already seen how the server-side of our Fetch remote works, now you’ll see how the other half of it, the client-side works.

Starting from the top, the two functions get-book-title and get-book-review use enfocus to extract the value of the “title” and “review” fields in the browser. Read the enfocus docs to find out exactly how that works.

The function get-book-data simply puts the title and review into a Clojure map and returns it. push-book then pushes this map to the remote function we defined in our welcome.clj file.

The next block of code sets up a listener that calls the push-book function if the submit button is clicked. And the last line loads this listener when the web page loads.

Compile the Javascript using lein cljsbuild once and make sure you’ve added the Javascript file to your template(in common.clj). If you visit the browser now, you should see the form as expected. Fill in the title and review and hit “Submit”. And what happens? Nothing! Well, actually something does happen. If everything worked fine, the little println call in our remote function should have printed out some text in the process where you’re running the Noir server. Also, if you try running the db-read-all function we defined, you should see that a book was in fact added when you hit “Submit”.

Congratulations! You’ve created a Clojurescript application backed by a database. I know its a really trivial app, silly even but I do hope this post helped at least a few people get started with Clojurescript. And if you are interested in moving forward with this app, here are a few thoughts: