20 July, 2014

    Book writeup: Makers by Chris Anderson

    This weekend I started and finished reading Makers by Chris Anderson. The book is about how designing and manufacturing physical things is about to undergo the same revolution that the internet brought about to digital content and software. It was a short and fairly interesting read.

    This was an exciting book to read, not just because it talks about how the future will look like but how things have already begun to change. 3D-printers and other "desktop"-manufacturing tools which allows anyone to manufacture any physical object. Crowdsourcing sites like Kickstarter has allowed bold, eccentric projects to take life while still allowing creators to stay in-charge, directing the creative path of the project. And all these "open-source hardware" projects like the Arduino and Raspberry Pi are starting to crop up. So, the book will have you easily convinced that change is indeed underway. And the book communicates the author's excitement about this pretty well. And it did indeed get me excited about what the future would look like.

    One thing that did get annoying about the book was that it was quite repetitive about some of the "sound-bites". Still, the book was interesting enough, and I'd recommend it.


    16 June, 2014

    Drawing Fractals with Elm

    I just pushed a small, quick toy project on Github called elm-fractals to draw fractals using Elm. Elm itself is a really interesting functional reactive programming (FRP) language, but my project itself is not reactive. I chose Elm because I found Elm to be a fun idea and it makes drawing on the browser super-easy. I might write a blog post on Elm soon, once I get a better handle on it, but do check it out if you're interested- there is already a lot of cool stuff out there.

    A fairly low-res Mandelbrot fractal drawn by the Elm code I wrote: Mandelbrot fractal

    I started playing around with fractals, mainly the Julia fractal, after reading two amazing blog posts explaining complex numbers and how they form these intriguing patterns called fractals. The first one is by Steven Wittens and the second one is by Jeremy Kun.

    Check the project out on Github: elm-fractals.


    11 April, 2014

    Image diffing in Clojure

    I recently wanted to try diffing two images ie. given two images show what is different in those two images. I'll explain the approach I took, which is really pretty inefficient, in this blog post.

    The diff images produced: /images/AlienA.jpg /images/AlienB.jpg

    First off, we'll be using javax.imageio to read the image and we'll create a "patch" in a java.awt.image.BufferedImage so import those two:

    (ns imdiff.core
      (:require [clojure.java.io :as io])
      (:import javax.imageio.Image IO
               java.awt.image.BufferedImage))
    

    And I've written some helper functions on top of these:

    (defn read-image
      [path]
      (ImageIO/read (io/file path)))
    
    
    (defn write-image
      [img path file-format]
      (ImageIO/write img file-format (io/file path)))
    

    Each pixel will give us an ARGB value: an alpha value which is the transparency of that pixel and the plain old red, green, blue components of the pixel:

    (defn px->argb
      [px]
      (let [a (bit-and (bit-shift-right px 24) 0xff)
            r (bit-and (bit-shift-right px 16) 0xff)
            g (bit-and (bit-shift-right px 8) 0xff)
            b (bit-and px 0xff)]
        [a r g b]))
    
    
    (defn argb->px
      [[a r g b]]
      (bit-or (bit-shift-left a 24)
              (bit-or (bit-shift-left r 16)
                      (bit-or (bit-shift-left g 8)
                              b))))
    

    These functions were pulled from Nurullah Akkaya's blog post on Steganography.

    Based on these functions, here is another helper functions we will be using while diffing:

    (defn transparent-px
      "Returns a pixel with transparency reduced"
      [px transparency]
      (let [[_ r g b] (px->argb px)]
        (argb->px [(int (* transparency 128)) r g b])))
    

    Color difference

    Initially I was checking if two images were equal, however this yielded in some weird diffs where the images would be identical but because of small changes in the pixel value, would give a noisy diff. So, instead I'm now taking the Euclidean distance of two pixels and checking if they are close enough:

    (defn color-difference
      [pxA pxB]
      (let [pxAargb (px->argb pxA)
            pxBargb (px->argb pxB)]
        (/ (Math/sqrt (apply + (map (comp #(Math/pow % 2) -) pxAargb pxBargb)))
           510)))
    
    
    (defn compare-colors
      "Check if the `color difference` of two pixels is less than the
      tolerance. Difference and tolerance can be any value between 0.0 and
      1.0."
      [pxA pxB tolerance]
      (if (= 1.0 tolerance)
        (= pxA pxB)
        (< (color-difference pxA pxB) tolerance)))
    

    Generating the diff

    Finally, the diff is actually two files which show what is different in each of those images. I call these two output files "patches". I also assume for the sake of simplicity that the two files have the same dimensions:

    (defn write-diff
      "Write `patches` between imgA and imgB into the patch paths."
      [imgA imgB patchA-path patchB-path & {:keys [tolerance transparency]
                                            :or {tolerance 1.0
                                                 transparency 0}}]
      (let [imgA-height (.getHeight imgA)
            imgA-width (.getWidth imgA)
            imgB-height (.getHeight imgB)
            imgB-width (.getWidth imgB)
    
            h imgA-height
            w imgB-width
    
            patchA (BufferedImage. w h BufferedImage/TYPE_INT_ARGB)
            patchB (BufferedImage. w h BufferedImage/TYPE_INT_ARGB)]
        (assert (and (= imgA-height imgB-height)
                     (= imgA-width imgB-width))
                "Height and width need to be equal")
        (doall (map deref
                (for [row (range h)]
                  (future (doseq [col (range w)]
                            (let [a (.getRGB imgA col row)
                                  b (.getRGB imgB col row)]
                              (if (util/compare-colors a b tolerance)
                                (do (.setRGB patchA col row (util/transparent-px a transparency))
                                    (.setRGB patchB col row (util/transparent-px b transparency)))
                                (do (.setRGB patchA col row a)
                                    (.setRGB patchB col row b)))))))))
        (write-image patchA patchA-path "png")
        (write-image patchB patchB-path "png")))
    

    As I mentioned above, this writes the pixels that are not the same in the two images into the patch files, whereas for pixels that are the same it writes the pixel with its opacity reduced.

    Notice also, that the processing for each row of pixels happens in a future. I've noticed this to improve performance, especially for larger images- comparing two 2880×1800 PNG files which took ~47s without the parallelization took ~14s to complete.

    You can try this function by first reading in images:

    (def cat (read-image "cat_orig.png"))
    (def cat-red (read-image "cat_red.png"))
    

    And then generating their diff:

    (write-diff cat cat-red "A.png" "B.png"
                :tolerance 0.1
                :transparency 0.2)
    

    24 March, 2014

    First impressions on nand2tetris

    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.


    15 March, 2014

    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
      (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)))
    

Archives