Samrat Man Singh

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

First impressions on nand2tetris

2014-03-24


I recently started reading a very interesting book called The Elements of Computing Systems by Noam Nisan and Shimon Schocken. The book is nicknamed “nand2tetris”, so called because the reader starts off with a NAND gate and using it as a building block for more complex systems builds a modern computer(on which he or she implements the game of Tetris).

I’ve only just finished the first chapter and am currently diving into the second, but I can already say that the book is quite remarkable in both what it sets out to do and its pedagogy.

What the book is about

As I mentioned above, the book has you build a computer from scratch. Just so you don’t get the wrong idea, the entire computer is built in a simulator running on your “actual computer”.

The idea here is to learn how computers work by actually building one. In the process, you’ll encounter everything from the low-level, implementing logic gates to writing compilers to high-level object-oriented programming. And of course, the most fun part is that everything from the base will be something you built. I really liked this idea.

The abstraction-implementation paradigm

All in all, the computer you build in the book can be divided into 12 or so “layers”, roughly a chapter is dedicated to each of these layers. Each layer is built on top of the one below it. For example, in the first chapter you build logic gates out of NAND gates. Then, in the second chapter using the gates built in the first chapter, the book has you building an Arithmetic Logic Unit.

This way of layering abstractions is very important in computer science. The idea is to implement each layer such that the layer above it has a clear way of interfacing with it to get the required functionality. The benefit here is that by being able to think about just one level of abstraction at a time, complexity is reduced.

Hands-on Learning

The other big idea I’ve noticed so far in this book is that it tends to be brutal about having the reader do the exercises. Whereas most books which claim to follow a “hands-on” will throw you a problem every once in a while, this book is mostly exercises. For each layer, the book gives you a specification and you are the one who needs to implement each layer.

Of course, some guidance is provided but expect to get stuck at problems. This can be frustrating but the central premise of the book is that you learn by doing things yourself.

Afternote

Like I said before I’ve only just dipped my toes here so far, but I can already say that this is going to be an interesting experience. Not only will it help fill a gap in my knowledge regarding computer architecture, I think it will be interesting book to study because of the very different pedagogical approach the authors have taken.


Arithmetic with Instaparse

2014-03-15


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
  (insta/parser
   "<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"))
([:additive-expr
  [:number "2"]
  "+"
  [:additive-expr
   [:number "2"]
   "-"
   [:additive-expr
    [:multiplicative-expr
     [:number "2"]
     "/"
     [:multiplicative-expr [:number "2"] "*" [:number "2"]]]
    "-"
    [:additive-expr
     [: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

2013-12-29


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
  [counts-file]
  (with-open [rdr (clojure.java.io/reader 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))
                                           word-tag-counts]
                       [c "2-GRAM" t u] [(assoc ngram-counts [t u] (Integer/parseInt c))
                                         word-tag-counts]
                       [c "1-GRAM" t] [(assoc ngram-counts [t] (Integer/parseInt c))
                                       word-tag-counts]
                       [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
  [ngram]
  (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})
e({t_2}\Rightarrow{x_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."
  (memoize
   (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))))
                          tag-space)))))))

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))
  tag-space))

Finally, to get the tag sequence:

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

Making a streaming API from scraped data using Clojure

2013-08-14


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 clojure.data/diff, 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 clojure.data namespace. Here's how it works:

(require 'clojure.data)

(clojure.data/diff {: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:

(clojure.data/diff {"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 (clojure.data/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 clojure.data/diff. I think that's pretty cool.


Websockets with Clojure and http-kit

2013-07-04


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 "http://example.com/FIXME"
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :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)]
        ring.util.response
        ring.middleware.cors
        org.httpkit.server)
  (:require [compojure.route :as route]
            [compojure.handler :as handler]
            [ring.middleware.reload :as reload]
            [cheshire.core :refer :all]))

(def clients (atom {}))

(defn ws
  [req]
  (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)})
                   false))
          (Thread/sleep 5000)
          (recur)))

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

(def application (-> (handler/site routes)
                     reload/wrap-reload
                     (wrap-cors
                      :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) {
            console.log(JSON.parse(event.data)["happiness"])}

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>
<html>
<head>
<script type="text/javascript" src="https://www.google.com/jsapi"></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) {
            data.push(JSON.parse(event.data)["happiness"]);
            timestamps.push(new Date);
            refreshChart();}

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

function zip(arrays) {
    return arrays[0].map(function(_,i){
        return arrays.map(function(array){return array[i];});
    });
}
</script>
</head>

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

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:

happychart.png