Samrat Man Singh

Hi, I’m Samrat. I’m a backend programmer. I am also interested in compilers and low-level systems.

Book (mini)review- "Amusing Ourselves to Death"

2016-12-28


Just finished reading “Amusing Ourselves to Death” by Neil Postman. I think I put the book in my to-read list after Alan Kay recommended in a talk of his(I don’t remember which one).

The book is about how any communication medium dictates the kind of discourse taking place in that medium. It was written in 1985, and so it is very much focussed on television and how in that medium, which is so dedicated to turning everything into entertainment, critical thinking and rational discourse are endangered. Despite having been written more than 30 years ago, however, I think it is still relevant today, perhaps even more so. Obviously, television is still around but social media dominates a large part of the social conversation. Postman’s point is that no medium should go unexamined. That is, we need to think about how any form of media— be it typography, television or the Internet— affects the information it carries, the culture at large, and the minds of the people who consume that form of media.

Postman talks only briefly about computers— recall that in 1985, personal computers were just taking off and the Internet wasn’t even a thing yet. It is surprising that he foresaw one issue that today is very much talked about(emphasis mine):

Thus, a central thesis of computer technology—that the principal difficulty we have in solving problems stems from insufficient data—will go unexamined. Until, years from now, when it will be noticed that the massive collection and speed-of-light retrieval of data have been of great value to large-scale organizations but have solved very little of importance to most people and have created at least as many problems for them as they may have solved.


Miscellaneous updates(2016-11-23)

2016-11-23


Some random updates:

I’ve been reading Neal Stephenson’s Quicksilver. This is the second time I’ve started to read the book and I must say that I’m just having a lot of trouble getting into the book. That said, I haven’t abandoned it yet- I’ve enjoyed all of the other Stephenson novels I’ve read so far. Also, the last book I read, Gore Vidal’s Creation got me excited about the genre of historical fiction. I’m still hoping Quicksilver gets better eventually.



The other book I’ve been working through is Compiler Construction by Niklaus Wirth. This is a concise, and in my opinion, great introduction to compilers. I have also been building a small compiler written in C. It doesn’t have much yet, but here’s the test program, which it can successfully compile:

a := 11;
b := a+12;
if a > b then c := b*5 
    elsif a > 20 then c := b + 5
    elsif 0 > 1 then c := 2*b
    else c := 101
end;

repeat
    a := a - 1;
    b := b + 3
until a < 1;

d := 14

No procedures, arrays or types yet(of course, it doesn’t have plenty of other stuff missing, these three just happen to be on my immediate backlog). But hey, baby steps!


Some recent reads

2016-07-27


I haven’t posted here in quite a while, and I’d like to re-boot the site with something easy. So I wrote up “mini book reviews” of some books that I read recently and liked quite a lot.

Bringing Down The House by Ben Mezrich

This is a book about an MIT blackjack team who were counting cards in Las Vegas casinos. They were quite successful at it too.

The movie “21” is based on this book and I had really enjoyed it, so this book was on my to-read list for a while. I enjoyed the book just as much as the movie.

The Cuckoo’s Egg by Clifford Stoll

The Cuckoo’s Egg is an awesome account of how Stoll tracks down a hacker who was breaking into his lab’s computer to access military computers, apparently searching for classified information.

What I liked best about this book is Stoll’s writing style: it’s simple and honest- he keeps you in the loop about how he’s trying to get his next lead, and his frustrations too. And you can tell he’s an interesting guy. You should check out this Numberphile video about how he manages the warehouse for his Klein bottle business.

Oh, and even though it is non-fiction, the book feels very much like a thriller. Highly recommended.

Stories of Your Life and Others by Ted Chiang

This is a collection of short science fiction stories. I’d never heard of the author and in fact, he has very few stories published, which is a real shame.

In all of the stories, Chiang has taken what is the essence of science-fiction and really run with it. He shows you a universe where things work differently, or some technology that doesn’t really exist, and imagines how such a world would look like. And the intricacies of how these universes and technologies work is what Chiang seems to have focussed on. After he’s happy with that, he treats the plot as secondary and just drops it off. Bold, but effective.


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