Lambda and Functional Programming

After I started looking at the core of functional programming here, more and more question followed their ways into my head. It’s pretty common now a days to face new and newer piece of reusable code components on a daily basis. They redefine how things ought to be done. I’m not complaining at all, it is indeed intriguing to see them come forward so fast. And the fun part is all of them follows the principles laid out years ago. Functional programming is no different.

Greek alphabet of coolness, 位

The reason the first word in the title of the blog is lambda because the character is聽 is almost synonymous with anonymous methods/functions, almost all the programming language around has the capabilities to create some form of support of constructing lambdas that contain a unit of work. Greek people made even their alphabets cooler than anyone else. And when I started thinking of actually learning a functional language, my first question was why would I need a language that enforces immutability? Can’t I myself keep immutability intact and yet code with the same principles in any other imperial programming language? The answer is yes, sure I can. The point lies somewhere else. Functional Programming is not something really new. It is not something refactored out of imperial programming. In fact, the tale is as old as general/state driven computing as we know it.

Turing and his states

The moment you start talking about computing, you will start living in Alan Turing‘s head. Whatever we build today, whatever we are doing is still following the principles of his infamous computational model Turing Machine. This was his work in 1936 and we still can’t imagine anything out of it. Amazing, isn’t it? A simple tape drive driven machine model is empowering every possible machine you see now. He is indeed the puppet master of computing.

If we look around carefully, everything around is state driven. Object Oriented programming is state driven. Every instance we write of a class is state driven. When you use a cool framework like redux to maintain your application state, you are doing nothing except following the same principles of a basic state machine, especially a DFA. I can’t emphasize this enough, Turing is synonymous to computation.

Now we get into the head of someone else. Someone else named Alonzo Church. Alonzo Church was building a computational model at the same time Turing was working on his own. His computational model was mathematical function driven where every function is a black box, takes an input and drives out an output. Functions can be sent as inputs and every logical relation is based on a simple domain to range mapping. Sounds familiar? Yes, his work was the father of Functional Programming published in the same year, 1936. Alonzo’s model was based off his work on聽Lambda Calculus. Fret not, the name is scary, the actual thing is way simpler than it sounds, I think it sounds way cooler because the damn name has lambda on it.

The last but not the least amazing part is, Turing didn’t know any of these. And Alonzo was his doctoral advisor. 馃槈 The whole hypothesis is named after both of them since Turing proved that Alonzo’s model is equivalent of his computational model. And thus Church-Turing Thesis was born.

What is Lambda Calculus?

We are going to take a very very quick tour of lambda calculus. It doesn’t have any traditional calculus-esque constructs in it. There are multiple variants of it. We will only take a quick tour of pure lambda calculus. Just enough to know how functional programming is devised so we can think alike.

The syntax is simple, in context free grammar:

expr ::= constant| variable | (expr expr)聽| 聽(位 .variable expr )

If you are not used to context free grammar, this construct tells how a lambda calculus expression is written. It says an expression can be a constant, a variable, a set of expressions and at the very end, the abstract form of lambda calculus that states a definition of a function like:

位x. e

Here, the聽x is the input parameter and聽 e is the expression. The input parameter is聽bound in that expression聽e.聽And the abstract form of lambda calculus defines a function. Remember this is the definition, it can be invoked and used with real arguments. If this is get all confusing for you, let’s jump into an example. Let’s say we want to define a function that adds 1 to a variable X.

From my perspective we are building a blackbox function that takes one input and converts it to a output.

BasicFunction

Now, to express it as a聽lambda calculus abstract聽we will use the character聽to define the function,聽x as the input parameter and the output will be聽x+1. So this will end up in the expression body聽e. So, it looks like

位x. x+1

We have our first lambda abstract! yay! This is the function definition. To invoke it, let’s say, we want to use 5 as an input argument. The invocation will look like

(位x. x+1) 5

If this is getting confusing again, remember, we don’t have a name for our function here. The definition itself is the name and the body. And the input parameter as聽x is 5 now. To deduce the next line, we replace聽x by 5 and we take the聽位x off.聽

(位x. x+1) 5
5 + 1
6

This is a very basic sample of beta reduction. Remember聽lambda calculus only have inputs, expression and the output. It is indeed that simple.

Now, back to programming world. Remember Javascript’s infamous self invoking method?

(function (x) {
    return x + 1;
})(x);

I hope now you see where the principles come from. Amazing. Isn’t it?

The notion of recursion

We are taking a pretty big jump here. Ever wondered how recursions work? We invoke the same method inside of it and we end up in the same place over and over again. Can聽lambda calculus define recursion?

It can. Lets assume that we have a function聽位x. x x. And we invoke it with itself as a parameter. So, it looks like:

(位x. x x)聽(位x. x x)
(位x. (位x. x x) (位x. x x))聽(位x. x x) 聽 聽聽
// replacing x x with the (位x. x x) itself
(位x. x x)聽(位x. x x) 聽 聽// 聽by the same rule of beta reduction, we take of the聽notation and the input

We applied beta reduction here but we still ended up in the same place we started. This is called聽Omega Combinator which is聽a聽divergent combinator since it has no normal form.聽If you apply beta reduction on it, you will end up in the same construct again. This is basically a simple mathematical model for an infinite loop…pointing to a recursion.

A combinator in a lambda calculus is defined by an lambda expression that has no free variables. What is a free variable you ask? Looks like you want a nice course on Lambda Calculus. 馃檪

I found these very helpful if they are read or viewed in order:

  1. Crash Course on Lambda Calculus by Ayaka Nonaka聽
  2. Lambda Calculus – Computerphile
  3. Lambda Calculus by Jim Grandpre
  4. Y combinator function. What is it?

If you read/viewed all these already, you probably know this already. The lambda calculus way to self reference a function inside itself is called the聽Y Combinator. Yeah, mind blown, isn’t it?

Computation is not really far from philosophy or history. It also starts from the聽alpha and ends in聽omega. I stay clear of religion but had to mention this. (It sounded cool in my head, doh!)

So, next time you write a lambda to look cool on your codebase or while you are talking to people about the nifty map, reduce and various unit of work methods, pay a little homage to Church and Turing. What they said years ago makes you look cool now.

Going functional: the journey begins!

For a long time, I really didn’t get to treat this blog as my own blog. I mean, sure, I said things I’m enthusiastic about. But I think the purpose of having a blog is not about catching attention rather having a safe place where you can have a dialogue with your mind.

I recently started dabbling with functional programming. I don’t know why though. For long I heard a lot over it from the constant stream of social networks. I never managed to find a reason why should I ever care about this. I think secretly I was afraid if I ever take this up, I might succumb to my curiosity and finally spend time learning things I really don’t need right now. Then again, knowledge never fails.

So, here I am. After spending around 8 or 9 hours of active reading, I barely made a scratch in the surface of it. But it’s a start. My major breakthrough was to be able to get back to that mindset where I could just play with something when I have the least knowledge backing it. It’s a scary game but boy is this fun to play.

 

Ahoy! functional programming!

The first and foremost notion of functional programming I got from watching people talk about it is that it probably has something to do with ‘functions’ being the first citizen in a programming language. And immutability plays a big part. That lead me to the same place where I started learning programming. 聽I mean I knew “what” was I learning, I did not know “why” I was learning that. I didn’t have the guts to ask because I didn’t know anything about the context. Now, I stand in a corner where I get to ask the question. Why?

 

Why functional programming is like this?

Surprisingly functional programming didn’t spawn from the concept of programming construct “function” being the first class citizen in a programming language. The fun thing is the word ‘functional’ in the very title doesn’t even point to programming functions. It actually points to mathematical functions. Before I go into that, please allow me to tell yourself to ‘unlearn’ programming as you know it. Especially if you are a person like me who knows imperative programming only. 聽The reason to unlearn what you know is to give you a clean fresh slate to work with. I know that is easier said than done. But as long as you know it and open to see things, you’d be fine!

So, let’s dive in. Let’s assume a simple, very simple mathematical function like the following:

let add1 x = x + 1

For reference I’m using F# here. The two programming languages I want to at least try out is F# and Scala. There’s a solid debate on Scala not being a total functional programming language. But, that is a story for another day. My goal is to understand Apache Spark better in the process too and Scala is just too friendly with it. In the process I’m trying to kill two birds with one bullet. This blog will roughly use F# for reference but nothing here is not understandable even if you haven’t seen F# in your life.

If we have a look at the function here we will see that we are adding 1 to another number here. Any programming language in existence is capable of doing that. What is the difference here except the syntax? This is where I send you back to the “unlearn” step. Let’s see how this is interpreted inside. The F# interpreter will read the function signature like the following:

val add1 : x:int -> int

the聽 val add1 part is self explanatory, we don’t want to worry about that part right now. What about the next part聽x:int -> int. This is where my聽imperative programming brain聽came into work and devised a misleading explanation. And it sounded something like :

The聽x:int -> int聽stands for a method signature that takes an input parameter聽x of type聽int and it returns another聽int.

Like I said, this is wrong but it felt legit when I devised it in my brain. The more I delved into it, the more I realized the wrongs in my ways. Years of imperative programming have assembled my neurons to reinforce these concepts as the general means of programming. Since functional programming resorts to mathematical functions, why can’t we see it from that specific aspect?

A mathematical function takes a set of values that are used as聽inputs into the聽function domain聽and the聽function maps it to a set of possible聽outputs. The set of the outputs are called聽range. All the functions do here is聽map the inputs to the聽outputs.

To visualize:

Functions_Add1

I’m not sure whether I have explained enough how my brain was convinced that it is different. To reinforce that the biggest difference here to look for is the process of doing things. We are聽transforming the聽inputs here. Not necessarily returning a value.聽Mathematical functions transforms inputs, they don’t produce聽any聽 side effect to the聽inputs. What I want to mean is if you add 5 and 1 you will get back 6. The input parameter 5 will not have any possible side effect on it. And a聽mathematical function always gives the聽same output for a specific given聽input. My聽imperative programming brain got it almost right. The right explanation for 聽x:int -> int is an int domain to int range mapping.

The function聽add1 maps an int input domain to an int range. And for the fact that mathematical functions DO NOT implicate any side effects, it was implicitly important聽to have聽immutability embedded inside them. Because if your programming function generates a state or a side effect then it will 聽not comply with mathematical functions. So the implementation layer will fail to comply with the theoretical counterpart. And that is why聽immutability聽is vital in functional programming.

 

I still don’t see the difference

This is really nice and all. But from my聽imperative programmer brain’s perspective, is it really that different? If I didn’t take this journey to figure out why functional programming is like this, won’t I be able to write anything in any possible functional programming language? And yes, for sure my brain will be able to. But here is the fun part. What our brain learns implicitly is really hard to explain using the same brain. Otherwise, machine learning will be a piece of cake. My point was to actually try to “know” it, not get habituated to it. Thus when I encounter a problem I can deduce a solution through what I know rather than just plugging constructs I have seen.

Still, I need an answer. Where is the difference? I still see inputs and outputs. Nothing else. My聽imperative programmer brain is quite right here, we聽assign a value to a聽variable and the聽function returns a聽result.聽

Now, wait a minute and lets see a bit into the word聽variable and聽assign. The word聽variable and聽assign points to the fact where we use the聽variable as a placeholder for the actual聽value聽. And the concept of聽assigning a聽value to a variable points to the concept of storing something in that placeholder. Is it the same here? No. Mathematical methods don’t imply placeholders. It creates a mapping and generalizes that mapping. So saying聽add1 5 is not assigning聽5 to x. It is actually聽binding 5 to聽x. The process of binding is not reusing聽add1.聽add1 5 is pointing to a method binding that says when聽I’m invoked you will end up in the range.聽 It looks really the same but it is not. Think of basically doing a string replace where the x is replaced with 5.

Hopefully now you will see more reasons reinforcing聽immutability.聽And thus the function name, 聽add1聽is not a reusable construct for the function. It’s just a shortcut expression for the聽range it returns. We are replacing a聽function value, not the聽function!

To sum it up the generic function value signature is聽

val functionName : domain -> range

So, here’s a trick question. How do we define constants then? The answer is writing a function where the range is just the value from any possible domain. 馃檪

The motivation behind starting to write again while I learn something goes straight to Chris Smith. He wrote Programming F#聽and his MSDN blog while he was writing F# is found here. They are highly entertaining and please don’t refrain yourself from looking into them.聽According to him it is one of the best ways to learn a language and I kind of agree with him despite the fact I lost the courage or interest to do that regularly before.

I also found Learn X in Y Minutes聽very very fun to have a blind date with a number of programming languages. If I ever get to talk about Scala (that depends on me having time to learn it), I will definitely talk more about this website.

The resources for this blog are taken from:

  1. F# for fun and profit
  2. Learn X in Y Minutes

Hope this was entertaining albeit it comprises of boring details! I intend to write a dummies note onthe church-turing hypothesis which essentially blossomed into lambda calculus. Functional Programming is almost directly derived from it. But, it all depends on how much time I will possibly have to cover that. Until then, see ya.

Making a simple Recommender System: Azure Cosmos Db and Apache Tinkerpop

Graph systems are one of the most聽ubiquitous models found in almost any natural and man-made structures we see everyday. Since computer science evolved around what we see and devise or deduce, graphs do play a huge role in day to day computation and programming techniques. It’s birth dates back to even before it was widely adopted in mathematics since mechanical computing was graph driven implicitly. If only we could get Alan Turing to talk over this.

Before I start, a big inspiration behind this write-up definitely goes to the work of Marko.A.Rodriguez聽. I was lucky to stumble upon his work while frolicking over the web and his works on graph computing systems and tinkerpop/gremlin is seriously inspiring.

What we are going to do today:

Let’s go right to what we want to do today. Our component of interest is the graph api of Azure Cosmos Db along with Apache Tinkerpop. Azure Cosmos Db has a graph api that allows us to store data as a graph or a network. In simple words, instead of storing data in a tabular format where you have row and column, you can store data as they describe each other in terms of relations. If the text here is not really doing it for you, let’s jump into some examples.

Let’s have a look into this sample graph I made from HIMYM. The big ellipses and boxes here are called vertices and the lines that connect them are called edges. Since we have a little arrow head telling the directions of them, this is actually a Directed Graph.聽If we look at the data behind the graph, then you can see, we can represent this in two ways. In a table, you can list up the vertices in one table and the edges in other. The edges table might look like:

From To Type
Ted Barney 聽friend
Ted Umbrella 聽found
Barney Robin 聽wife
Robin Barney 聽husband
Tracy Umbrella 聽lost
Ted Tracy 聽lost
….

I didn’t add all the rows of course and if you look at the design you can see it is not properly normalized. That means in understandable terms that we needed a Type table with all the edge types so we don’t write a Type twice. But that is not in this article’s scope. So, let’s ignore that. The thing here to see is, graph nodes/vertices can be of different types and the edges can mean different relationships. Like, here there are vertices that doesn’t represent a character from HIMYM, like the Umbrella and the MacLaren’s Pub. Storing these data in a regular database is possible and has been done many times. This way is called the ‘implicit’ way to store graph like data. Now one might think, by this rule all data in the world can be represented by a graph. And it is indeed true. But we use a graph database only when we see that the data itself focuses more on relations than the data content itself. Like friend graph in a social network website. Or a geographical model of all the offices of a big corporation. The vertices do carry data but the relations are really important here. In these case, a graph database comes in very handy.聽Azure Cosmos Db recently came up with a graph api and it can store graph data natively where the cost to聽traverse a graph is constant. In a regular database we have to join multiple tables to formulate these relations properly and in a lot of cases, these computational costs are not constant.

Apache Tinkerpop joins the party:

I hope by now we understand why we need a graph database and now is the right time we talk about Apache Tinkerpop. It was previously known as Apache Gremlin. This is essentially a fantastic graph computing engine which allows you to connect to multiple graph database using a single domain specific language construct. It has language supports for most of the popular languages and it is pretty native to groovy and java. Fret not, we have our way to use it over here with聽C# too. Before we start we need to create a simple graph database on Azure. The quickstart is here. You can also opt for java and nodejs. I personally used an Azure CosmosDb emulator. The quickstart to install that instead of an actual Azure CosmosDb is here. You can opt for any of these but I have to remind you, at the time this article is being written, Azure CosmosDb Emulator do not support creating graphs and browsing graph data through it’s local web portal. You have to use Gremlin Console to connect and talk to the local emulator. Gremlin Console is a command line REPL that you can use to traverse a local gremlin/tinkerpop graph or a remote one. It can connect to any gremlin servers anywhere as long as you have the credentials. You can use the gremlin console to talk to the actual Azure CosmosDb graph database. I suggest using聽Windows Subsystem For Linux (WSL), better known as “Bash on Ubuntu on Windows”聽for using gremlin-console. The gremlin console quickstart is here.

Our sample data set today:

We are going to use the movie review data set from grouplens from here聽. We are using the small dataset of about 100,000 ratings applied to 9,000 movies by 700 users. If you download and unzip the data you will see multiple csv fields. Of which I only used the movies.csv and聽ratings.csv files. I made a separate聽users.csv file for the users list. Don’t worry, all these are attached with the sample code. The movies csv comes with the聽movie id, movie name聽 and聽genres column. The聽ratings.csv comes with the聽user id, movie id聽and a聽rating column where the user has rated the movie from 0 to 5. The sample code has a simple command line uploader tool that will let you upload the data in your desired gremlin server and graph database connected to it. So, to understand how we talk to gremlin, let’s have a peek at the code, shall we?

Let’s talk code:

I’m not going to focus on the full source at a time. 聽Let’s have a look on how can we connect to an existing Azure CosmosDb Graph database. First, we create a DocumentClient.聽


DocumentClient client = new DocumentClient(
 new Uri(endpoint),
 authKey,
 new ConnectionPolicy { ConnectionMode = ConnectionMode.Direct, ConnectionProtocol = Protocol.Tcp });

Definitely the thing that you will notice missing is the authkey variable here. And that is actually the primary key of your graph database that you will find in your azure portal. If you use the emulator they use a fixed key which you will find in the quickstart link I shared above.

Now that we do have a聽DocumentClient let’s upload the sets of movies that we will use for reviews. I’m using the movie name and the movie id for the sake of simplicity here. In our graph, the movie vertices/nodes will have a label ‘movie’. This sets the type of the vertex and we will set the name and id as properties of this vertex. The聽id聽uniquely distinguish any vertex. So remember, no matter what the label of the vertex is the id has to be unique. Or Azure CosmosDb will let you know that it can not add a vertex because already a vertex of that same key exists. If you don’t provide an id property, Azure CosmosDb will generate one and put it on the vertex.

We make sure at the beginning of the upload to drop the existing graph database if there is any.

        private async Task NukeCollection(DocumentClient client)
        {
            try
            {
                Console.WriteLine("Nuking...");
                var response = await client.DeleteDocumentCollectionAsync(UriFactory.CreateDocumentCollectionUri("graphdb", "Movies"));
                Console.WriteLine(response.StatusCode);
            }
            catch (DocumentClientException ex)
            {
                Console.WriteLine(ex.Message);
            }
        }

The database name I used for these sample is聽graphdb and the collection name is聽Movies. Pardon me for my indecency to hard code these but it’s a sample code, so I put effectiveness in front of decency.

Adding vertices to our ‘Movies’ graph:

Now, we upload the movies. Of course make sure we create the database if it’s already not there.

        private async Task UploadMovies(DocumentClient client)
        {
            try
            {
                Console.WriteLine("Uploading movies");
                Database database = await client.CreateDatabaseIfNotExistsAsync(new Database { Id = "graphdb" });

                DocumentCollection graph = await client.CreateDocumentCollectionIfNotExistsAsync(
                    UriFactory.CreateDatabaseUri("graphdb"),
                    new DocumentCollection { Id = "Movies" },
                    new RequestOptions { OfferThroughput = 1000 });

                Console.WriteLine("Connected to graph Movies collection");

                Console.WriteLine("Reading movie list");
                using (TextReader reader = new StreamReader("movies2.csv"))
                using (CsvReader csv = new CsvReader(reader))
                {
                    while (csv.Read())
                    {
                        string idField = csv.GetField<string>(0);
                        string titleField = csv.GetField<string>(1);
                        titleField = JsonConvert.ToString(titleField, '\"', StringEscapeHandling.EscapeHtml);

                        Console.WriteLine("Uploading " + titleField);

                        IDocumentQuery<dynamic> query = client.CreateGremlinQuery<dynamic>(graph, $"g.addV('movie').property('id', '{idField}').property('title', {titleField})");
                        while(query.HasMoreResults)
                        {
                            await query.ExecuteNextAsync();
                        }
                    }
                }
            }
            catch (DocumentClientException ex)
            {
                Console.WriteLine(ex.Message);
            }
        }

For the collection, same strategy is followed. We get a聽DocumentCollection instance trying to create the聽Movies collection if it doesn’t exist or just fetching the existing one if there is one already. Then we start reading the csv file. We use the same聽DocumentClient instance to create a gremlin construct to add a vertex/node in the collection for each of the movies. We add a聽Movie label along with the聽title and聽id聽 property as promised. I want to focus a little bit in the gremlin/tinkerpop construct we used here.

The full construct in a more readable format is:

g.addV('movie')
    .property('id', '{idField}')
    .property('title', {titleField})

Let’s ignore the聽idField and聽titleField as we already know what is there. The first construct聽g stands for the graph in the collection.聽addV(‘label’) is the method construct to add a vertex. You can see the whole construct is design wise fluent. The next two聽property(propetyName, propertyValue) construct adds two properties in the newly added movie node. Nice builder interface, isn’t it? Pretty expressive. We are using the groovy standard constructs for gremlin. There are *other language constructs too, including聽javascript. And following the same approach, I uploaded the users in the sample code too.

By the time of writing this article, the whole connector library from nuget is in preview version and I don’t have one for .net core. So, we need to sit this one out for .net core. Sorry for that.

Connecting the vertices with edges:

The next thing in line is of course to add edges that represents the relationship between an user and a movie. We label the relationships with ‘rates’ and also will add a property named weight and it’s value will be the actual rating value given by that user.

        private async Task UploadReviews(DocumentClient client)
        {
            try
            {
                Console.WriteLine("Uploading movie reviews");

                DocumentCollection graph = await client.CreateDocumentCollectionIfNotExistsAsync(
                    UriFactory.CreateDatabaseUri("graphdb"),
                    new DocumentCollection { Id = "Movies" },
                    new RequestOptions { OfferThroughput = 1000 });

                Console.WriteLine("Connected to graph Movies collection");

                Console.WriteLine("Reading review list");
                using (TextReader reader = new StreamReader("ratings2.csv"))
                using (CsvReader csv = new CsvReader(reader))
                {
                    while (csv.Read())
                    {
                        string userId = "user" + csv.GetField<string>(0);
                        string movieId = csv.GetField<string>(1);
                        float rating = csv.GetField<float>(2);

                        Console.WriteLine("Uploading review for user " + userId + " to " + movieId + " with rating "+ rating);
                        IDocumentQuery<dynamic> query = client.CreateGremlinQuery<dynamic>(graph, $"g.V().hasLabel('user').has('id', '{userId}').addE('rates').property('weight', {rating}).to(g.V().has('id', '{movieId}'))");
                        while (query.HasMoreResults)
                        {
                            var result = await query.ExecuteNextAsync();
                            foreach (var item in result)
                            {
                                Console.WriteLine(item);
                            }
                        }
                    }
                }
            }
            catch (DocumentClientException ex)
            {
                Console.WriteLine(ex.Message);
            }
        }

The only noticeable change here in this snippet that we created edges between a movie and an user vertex. Like before, let’s zoom in the gremlin construct we used this time to create an edge between two nodes.

g.V()
    .hasLabel('user')
    .has('id', '{userId}')
    .addE('rates')
    .property('weight', {rating})
    .to(g.V()
    .has('id', '{movieId}'))

The first enumeration聽g.V() should enumerate all the vertices in the graph. We need to filter the user vertex first to create an edge from. The next聽hasLabel(”user) filters all the user vertices. Subsequently聽.has(‘id’, ‘{userId}’) filters the vertex of the user we want bearing that user id. Then we use聽addE(‘rates’) method to ensure that we add an edge labeled ‘rates’ from it. The following聽property(‘weight’, {rating}) should add the weight property with the rating as聽value on the edge we just created. The last thing we do is to tell where this edge points to. With聽to(g.V() .has(‘id’, ‘{movieId}’)) we filter out the movie node we want and use it to define which vertex the edge points to. Decent huh? You can find the full tinkerpop reference here.

By now a single user rating a movie should look something like:

Finally, we have all our data ready. Time to聽traverse this graph and make a simple movie recommendation for any user. 馃檪

The simplest movie recommender system in this world:

Let’s devise a simple movie recommender and we will follow the dumbest real life approach we see around. Usually when I pick a movie to see, I pick a movie based on the movies I have already seen and liked. If I liked聽Deadpool, there’s a very good chance I will like聽Deadpool 2 and other superhero movies like聽Logan. Remember we didn’t add/use any genre data in our graph. All we have here are the users, the movies and the ratings made by the users on these movies.

So, let’s find out the other users who likes the same movies as our reference user do. Our reference user is the user who has asked for a recommendation for movies that he should see from us. He has only given us a list of movies he saw and rated. Our current traversed graph should look like this:

We want to traverse the users who like the same movies our reference user likes using gremlin. To construct the query, first we need to get out of our user vertex and find out movies that our user likes. The gremlin construct for that will be:

g.V()
    .hasLabel('user')
    .has('id', 'user7')
    .outE('rates')
    .has('weight', gte(4.5))

Let’s assume our reference user id is聽user7. And at first we filter the vertices with label聽user and id聽user7. After that we use聽outE(‘rates’)to traverse edges that is labeled聽rates and has聽weight more than or equal to 4.5. That’s how we will land on the nodes that we think the user likes. But right now, we are standing on the edges. To land on the movie nodes, we have to use:

g.V()
    .hasLabel('user')
    .has('id', 'user7')
    .outE('rates')
    .has('weight', gte(4.5))
    .inV()
    .as('exclude')

inV() construct will enumerate all the attached movie nodes with the rates edges. The as(‘exclude’) construct is used for a specific purpose. For now, all I can say is, I’m marking all the movies I saw as ‘exclude’.聽 We will see why I’m doing this soon.

So, now we want to find out all the other users who likes the movies our reference user likes.

So, this is where we want to end up. We found user2 and user3 likes the same movies almost as much our reference user likes. To progress through gremlin, our new gremlin query is:

g.V()
    .hasLabel('user')
    .has('id', 'user7')
    .outE('rates')
    .has('weight', gte(4.5))
    .inV()
    .as('exclude')
    .inE('rates')
    .has('weight', gte(4.5))
    .outV()

We added a聽InE(‘rates’) construct since we want to know now which聽inward edges with label聽‘rates’聽are pointing to these movies our reference user likes. We also filter the edges more with聽weight property value greater than or equal to 4.5 since we only want users who likes the same movies. At last we added聽outV() to find the users attached to these edges. Now we are standing on the users who likes the same movies our reference user does.

We want to know what other movies these users likes that our reference user has not rated or seen yet. I’m assuming our reference user rated all the movies he has seen.

From the graph above we can clearly see that user3 and user2 likes聽movie4 and聽movie5 that our current user has not rated yet. These are viable candidates for our users movie recommendation. It definitely seems naive, but it’s a start. If you remember about the聽exclude nodes, we are going to use these now to make sure that our recommender doesn’t recommend the movies our user already has seen. Our desired gremlin query is:

g.V()
    .hasLabel('user')
    .has('id', 'user7')
    .outE('rates')
    .has('weight', gte(4.5))
    .inV()
    .as('exclude')
    .inE('rates')
    .has('weight', gte(4.5))
    .outV()
    .outE('rates')
    .has('weight', gte(4.5))
    .inV()
    .where(neq('exclude'))

We traveled the movies all these other user likes and made sure that we exclude the ones we have already seen using 聽where(neq(‘exclude’)). To fix our naivety a little bit, let’s take the distinct movies using dedup() and order it by the movies by the amount of ratings it has received.

g.V()
    .hasLabel('user')
    .has('id', 'user7')
    .outE('rates')
    .has('weight', gte(4.5))
    .inV()
    .as('exclude')
    .inE('rates')
    .has('weight', gte(4.5))
    .outV()
    .outE('rates')
    .has('weight', gte(4))
    .inV()
    .where(neq('exclude'))
    .dedup()
    .order().by(inE('rates').count(), decr)
    .limit(10)
    .values('title')

This has to be really really naive to survive any production requirement. But it is indeed an eye opener on how Apache Tinkerpop and Azure CosmosDB Graph databases can do.

If you look on the final query quickly you will see we ordered the final movie nodes by the count of incoming rates edges it has and ordered it in a descending order using聽order().by(inE(‘rates’).count(), decr). We limited the nodes to first 10 and we only took the titles of the movies.

Putting the system to test:

I wrote a simple REPL to try out various gremlin commands towards our Azure CosmosDb. 聽Our reference user id was ‘user7’. The list of the movies seen by our reference user is:聽MoviesSeenByUser

If it is too hard to read, let’s put out the movies here:

  • “Braveheart (1995)”
  • “Star Wars: Episode IV – A New Hope (1977)”
  • “Shawshank Redemption, The (1994)”
  • “Wallace & Gromit: The Best of Aardman Animation (1996)”
  • “Wallace & Gromit: A Close Shave (1995)”
  • “Wallace & Gromit: The Wrong Trousers (1993)”
  • “Star Wars: Episode V – The Empire Strikes Back (1980)”
  • “Raiders of the Lost Ark (Indiana Jones and the Raiders of the Lost Ark) (1981)”
  • “Star Wars: Episode VI – Return of the Jedi (1983)”
  • “Grand Day Out with Wallace and Gromit, A (1989)”
  • “Amadeus (1984)”
  • “Glory (1989)”
  • “Beavis and Butt-Head Do America (1996)”

The movies our simple recommender suggested are:

  • “Forrest Gump (1994)”,
  • “Pulp Fiction (1994)”,
  • “Fargo (1996)”,
  • “Silence of the Lambs, The (1991)”,
  • “Star Trek: Generations (1994) “,
  • “Jurassic Park (1993)”,
  • “Matrix, The (1999)”,
  • “Toy Story (1995)”,
  • “Schindler’s List (1993)”,
  • “Terminator 2: Judgment Day (1991)”

Clearly this is not the best recommender engine, but definitely one of the simplest. We can always reuse the genome data along with the dataset and the genre data and do a proper collaborative filtering. But the scope of this article was just to demonstrate the capabilities of a simple graph traversal.

Hope it was fun to read. Try out Azure Cosmos Db Graph Api and Apache Tinkerpop if you can. They are really fun together to use to and there’s so much you can do using simple graph traversals.

The sample code is hosted here in github. Until next time!

 

Building your own REST query language: An experiment with Azure Cosmos Db

For all the REST resources we deploy out every day, one of the most common scenario a developer ends up handling is designing a nice and effective search/filter/query endpoint for these aforementioned resources. Usually in these scenarios conventions play a big part and that starts from query filter parameters in the query string to using a full blown search engine like ElasticSearch, Lucene or Algolia. Vinay Sahni did a phenomenal job for putting out the gist for basic REST practices here. If you are new into REST and want to get yourself started talking REST, it’s worth a look.

Today, we will do a simple yet fun experiment. Our goal today is to create a simple nifty looking query language for a sample REST resource. We will try to mimic a couple of features Twitter Search Api聽provides and our sample data storage today will be Azure Cosmos Db: Document Db聽which previously was known as just Azure Document db. Recently it moved to the Azure Cosmos Db family and if you have missed it, here is the full details.

Therefore, the first thing we need is a set of sample data we can use as our REST resource. Since we are going to mimic the twitter public search api, we definitely need some sample data first. And of course github comes to the rescue. Download the sample data and put it to your own document db instance. If you don’t know how to create a document db instance, follow the quick start here. I’m referencing the link to the .net quick start, but there are node.js, Python, Java and Xamarin resources right by the side of it. For those of you who do not want to test your work against an Azure hosted document db and want to test Azure document db locally, you can always opt for the azure document db emulator.

Now, for the sake of this experiment I ported the github twitter sample data to an azure document db instance. It has 10 entries in that small data set and hosted here. If you want to browse the data, azure portal does allow it. But I suggest looking at this open source app here named Azure DocumentDB Studio. You can use the endpoint and the key written in the sample code in github聽to connect. The database is public just for you guys so you can test the sample code I have hosted in github and will list out in the end of this article. TL;DR people, this is your cue to go to the end of the article, but I highly suggest to stick around.

Features to be built:

Out of all the features twitters search api provides, I will port the to:UserAccount, from:UserAccount and “exact text”聽search capabilities. That means, We will be able to search tweets sent from one account to other and we will also be able to search tweets by mentioning a string we like to be present in the tweets. For an example if we want to find tweets

  1. from an user account named @terminator
  2. to another user account named @robocop聽
  3. or any tweet where the words “I’m back”
  4. or the hashtag #HastaLaVista聽is present,

our sample query language excerpt will be

http://our-awesome-api/search/q?to:robocop AND from:terminator OR “I’m back” OR #HastaLaVista”

If you have an eye for detail, you will notice that this is not exactly like the twitter search api since doesn’t use an聽and聽operator. But for the sake of the simplicity in this example this should be enough.

Tools we are going to use:

Our api stack will be written in asp.net core. We will use ANTLR聽as our query language lexer-parser. If you need an ANTLR primer and another experiment I did with it, please have a look here聽where I tried to gobble up a simple scripting language. If you are not really accustomed to any of .net stacks, fret not. All of these are totally doable in any other tech stack you will possibly prefer to use. Since ANTLR has targets for multiple languages, api can be built in basically any language and even for our sample storage solution azure document db here, you have access to multiple client SDKs.

The data:

As I mentioned above, we have a little data set of 10 entries. I’m posting a sample entry here so the rest of the tutorial makes sense. One entry points to a single tweet made by a sample user.

{
  "entities": {
    "user_mentions": [
      {
        "indices": [
          3,
          15
        ],
        "id_str": "178253493",
        "screen_name": "mikalabrags",
        "name": "Mika Labrague",
        "id": 178253493
      }
    ],
    "urls": [],
    "hashtags": [ "#Confused" ]
  },
  "in_reply_to_screen_name": null,
  "text": "RT @mikalabrags: Bipolar weather #Confused",
  "id_str": "210621130703245313",
  "place": null,
  "retweeted_status": {
    "entities": {
      "user_mentions": [],
      "urls": [],
      "hashtags": []
    },
    "in_reply_to_screen_name": null,
    "text": "Bipolar weather",
    "id_str": "210619512855343105",
    "place": null,
    "in_reply_to_status_id": null,
    "contributors": null,
    "retweet_count": 0,
    "favorited": false,
    "truncated": false,
    "source": "http://ubersocial.com",
    "in_reply_to_status_id_str": null,
    "created_at": "Thu Jun 07 06:29:39 +0000 2012",
    "in_reply_to_user_id_str": null,
    "in_reply_to_user_id": null,
    "user": {
      "lang": "en",
      "profile_background_image_url": "http://a0.twimg.com/profile_background_images/503549271/tumblr_m25lrjIjgT1qb6nmgo1_500.jpg",
      "id_str": "178253493",
      "default_profile_image": false,
      "statuses_count": 13635,
      "profile_link_color": "06544a",
      "favourites_count": 819,
      "profile_image_url_https": "https://si0.twimg.com/profile_images/2240536982/AtRKA77CIAAJRHT_normal.jpg",
      "following": null,
      "profile_background_color": "373d3a",
      "description": "No fate but what we make",
      "notifications": null,
      "profile_background_tile": true,
      "time_zone": "Alaska",
      "profile_sidebar_fill_color": "1c1c21",
      "listed_count": 1,
      "contributors_enabled": false,
      "geo_enabled": true,
      "created_at": "Sat Aug 14 07:31:28 +0000 2010",
      "screen_name": "mikalabrags",
      "follow_request_sent": null,
      "profile_sidebar_border_color": "08080a",
      "protected": false,
      "url": null,
      "default_profile": false,
      "name": "Mika Labrague",
      "is_translator": false,
      "show_all_inline_media": true,
      "verified": false,
      "profile_use_background_image": true,
      "followers_count": 214,
      "profile_image_url": "http://a0.twimg.com/profile_images/2240536982/AtRKA77CIAAJRHT_normal.jpg",
      "id": 178253493,
      "profile_background_image_url_https": "https://si0.twimg.com/profile_background_images/503549271/tumblr_m25lrjIjgT1qb6nmgo1_500.jpg",
      "utc_offset": -32400,
      "friends_count": 224,
      "profile_text_color": "352e4d",
      "location": "Mnl"
    },
    "retweeted": false,
    "id": 2.106195128553431E+17,
    "coordinates": null,
    "geo": null
  },
  "in_reply_to_status_id": null,
  "contributors": null,
  "retweet_count": 0,
  "favorited": false,
  "truncated": false,
  "source": "&amp;amp;amp;lt;a href=\"http://blackberry.com/twitter\" rel=\"nofollow\"&amp;amp;amp;gt;Twitter for BlackBerry庐&amp;amp;amp;lt;/a&amp;amp;amp;gt;",
  "in_reply_to_status_id_str": null,
  "created_at": "Thu Jun 07 06:36:05 +0000 2012",
  "in_reply_to_user_id_str": null,
  "in_reply_to_user_id": null,
  "user": {
    "lang": "en",
    "profile_background_image_url": "http://a0.twimg.com/profile_background_images/542537222/534075_10150809727636812_541871811_10087628_844237475_n_large.jpg",
    "id_str": "37200018",
    "default_profile_image": false,
    "statuses_count": 5715,
    "profile_link_color": "CC3366",
    "favourites_count": 46,
    "profile_image_url_https": "https://si0.twimg.com/profile_images/2276155427/photo_201_1_normal.jpg",
    "following": null,
    "profile_background_color": "dbe9ed",
    "description": "prot猫ge-moi de mes d茅sirs 铮 23107961 鈽",
    "notifications": null,
    "profile_background_tile": true,
    "time_zone": "Singapore",
    "profile_sidebar_fill_color": "ffffff",
    "listed_count": 2,
    "contributors_enabled": false,
    "geo_enabled": true,
    "created_at": "Sat May 02 13:55:49 +0000 2009",
    "screen_name": "yoursweetiethea",
    "follow_request_sent": null,
    "profile_sidebar_border_color": "91f50e",
    "protected": false,
    "url": "http://yoursweetiethea.tumblr.com",
    "default_profile": false,
    "name": "Althea Arellano",
    "is_translator": false,
    "show_all_inline_media": false,
    "verified": false,
    "profile_use_background_image": true,
    "followers_count": 306,
    "profile_image_url": "http://a0.twimg.com/profile_images/2276155427/photo_201_1_normal.jpg",
    "id": "37200018",
    "profile_background_image_url_https": "https://si0.twimg.com/profile_background_images/542537222/534075_10150809727636812_541871811_10087628_844237475_n_large.jpg",
    "utc_offset": 28800,
    "friends_count": 297,
    "profile_text_color": "fa3c6b",
    "location": "Christian's Heart"
  },
  "retweeted": false,
  "id": "210621130703245300",
  "coordinates": null,
  "geo": null
}

The ANTLR grammar:

The ANTLR grammar we are going to use here is:

grammar Search;

expr: term (op term)*;
term: exactText | hashText | toText | fromText;
op: AND | OR;

toText: 'to:'ID;
fromText: 'from:'ID;
hashText: '#'ID;
exactText: EXACTTEXT;

// lexer rule
EXACTTEXT: '"' ~'"'* '"';
OR: 'OR';
AND: 'AND';
ID: [a-zA-Z_] [a-zA-Z0-9_]*;
WS: [ \n\t\r]+ -> skip;

It’s a small and simple grammar like the one we used in our scripting language tutorial. Since our REST resource query is essentially an expression, our entry rule will be expr.聽The railroad diagram for聽expr looks like:

expr_rest
Rule expr

This means we can have a single search term or multiple search term chained by a聽op聽 rule. The聽op rule is nothing but the two relational operator we support: AND and OR.

relop
Rule op

Along side of the聽op聽rule we also need to know what the聽term聽rule stands for. The聽term rule stands for the search term format we are allowed to use. In our sample query stated above, we have terms like聽from:terminator,聽to:robocop,聽“I’m back”聽or a hashtag like聽#HastaLaVista.聽That’s why we have 4 rules defining all of these cases and the term rule is a OR relationship between them.

term_rest
rule term

I’m not going to post the railroad diagram for聽toText, fromText, hashText and exactText rules since they are pretty self-explanatory if you have a cursory look at the grammar.

So, what are we waiting for? Let’s start writing our little codebase that will parse this query string and translate it to an azure document db SQL that we can use to fetch the tweets. For that, we need a small repository that will connect to our desired database and collection in document db and will let us fetch some items. I only added methods that will allow us to read the tweets and connect to the database. I ignored the rest since you can always have a look at those in the quick start for azure document db.

Here’s our small rough database repository. Please remember to keep your endpoint and key strings somewhere secret and safe in production environment, since this is a tutorial, I went with what is easy and fast to go for a proof of concept.

namespace TweetQuery.Lib
{
    using System;
    using System.Collections.Generic;
    using System.Threading.Tasks;
    using Microsoft.Azure.Documents.Client;
    using Microsoft.Azure.Documents.Linq;

    public class CosmosDBRepository<T> where T : class
    {
        private readonly string Endpoint = "https://tweet.documents.azure.com:443/";
        private readonly string Key = "fjp9Z3qKPxSOfE0KS1aaKvUY27B8IoL347sdtMBMjkCQqPmoaKjGXoyltrItNXNN6h4QjAYLSY5nyb2djWWUOQ==";
        private readonly string DatabaseId = "tweetdb";
        private readonly string CollectionId = "tweets";
        private DocumentClient client;

        public CosmosDBRepository()
        {
            client = new DocumentClient(new Uri(Endpoint), Key);
        }

        public async Task<IEnumerable<T>> GetItemsAsync(string sql)
        {
            if (string.IsNullOrEmpty(sql))
                throw new ArgumentNullException(nameof(sql));

            FeedOptions queryOptions = new FeedOptions { MaxItemCount = -1 };

            var query = this.client.CreateDocumentQuery<T>(
                 UriFactory.CreateDocumentCollectionUri(DatabaseId, CollectionId),
                 sql, queryOptions)
                 .AsDocumentQuery();

            List<T> results = new List<T>();
            while (query.HasMoreResults)
            {
                results.AddRange(await query.ExecuteNextAsync<T>());
            }

            return results;
        }
    }
}

I opted for executing a SQL instead of a linq expression since constructing SQL is easier and simpler for a tutorial. Plus it decouples the query structure from compile time POCOs that we use as our models too.

I created a聽DocumentDbListener聽class based off the聽SearchBaseListener which was auto-generated from our ANTLR grammar. The sole purpose of this class is to generate a simple SQL against our search expression. To search inside nested arrays, I used a user defined function for azure document db. All of these are very crudely written, so forgive my indecency. Since this is just a tutorial, I tried to keep it as simple as possible.

function matchArrayElement(array, match) {
    for (var index = 0; index < array.length; index++) {
        var element = array[index];

        if (typeof match === "object") {
            for (var key in match) {
                if (match.hasOwnProperty(key) && element.hasOwnProperty(key)) {
                    var matchVal = match[key];
                    var elemVal = element[key];

                    return matchVal == elemVal;
                }
            }
        }
        else {
            return (element == match)
        }
    }

    return false;
}

All this method does is it tries to find nested array elements based on the match we send back. You can achieve the same result thorough JOINs in Azure Document Db or Array method ARRAY_CONTAINS, but I preferred a user defined function since it serves my purpose easily.

Constructing SQL from the query expression:

To understand how the SQL is generated from the query expression, let’s begin with the to:UserAccount expression. Since we start with the rule聽expr,聽let’s override the聽SearchBaseListener聽method聽EnterExpr first.

namespace TweetSearch.CosmosDb.DocumentDb
{
    using Antlr4.Runtime.Misc;
    using TweetSearch.CosmosDb.Util;

    public class DocumentDbListener : SearchBaseListener
    {
        private string projectionClause = "SELECT * FROM twt";
        private string whereClause;

        public string Output
        {
            get { return projectionClause + " " + whereClause; }
        }

        public override void EnterExpr([NotNull] SearchParser.ExprContext context)
        {
            this.whereClause = "WHERE";
        }
    }
}

The approach I took here is essentially the simplest. I handle the events fired the moment ANTLR enters a specific rule and I keep appending the SQL string to the聽whereClause. Since, entering the聽expr rule means that I will need a where SQL clause, I initialized it with “WHERE”. The thing to notice here is instead of concatenating I chose to initialize it because I expect this event to be fired exactly once since that is how the grammar is designed.

Following the same trail the next thing to handle will be the聽EnterTerm event. But,聽term is nothing but an OR relationship between 4 other rules. Handling them specifically gives me the edge since they produce simpler and smaller readable methods. For example, if we want to handle the聽to:UserAccount expression, a simple method like following should be sufficient for our use case.

        public override void EnterToText([NotNull] SearchParser.ToTextContext context)
        {
            var screenName = context.GetText().Substring(3).Enquote();
            this.whereClause = string.Concat(whereClause, " ", $"udf.matchArrayElement(twt.entities.user_mentions, {{ \"screen_name\" : {screenName} }} )");
        }

This is where our user defined function also comes in play though. I’m trying to find any tweet that has an user mention to the parsed user account I fetched from the query.

By following the same rule I completed the rest of the four rules and my full listener class looks like:

namespace TweetSearch.CosmosDb.DocumentDb
{
    using Antlr4.Runtime.Misc;
    using TweetSearch.CosmosDb.Util;

    public class DocumentDbListener : SearchBaseListener
    {
        private string projectionClause = "SELECT * FROM twt";
        private string whereClause;

        public string Output
        {
            get { return projectionClause + " " + whereClause; }
        }

        public override void EnterExpr([NotNull] SearchParser.ExprContext context)
        {
            this.whereClause = "WHERE";
        }

        public override void EnterFromText([NotNull] SearchParser.FromTextContext context)
        {
            var screenName = context.GetText().Substring(5).Enquote();
            this.whereClause = string.Concat(whereClause, " ", "twt.user.screen_name = ", screenName);
        }

        public override void EnterOp([NotNull] SearchParser.OpContext context)
        {
            var text = context.GetText();
            this.whereClause = string.Concat(this.whereClause, " ", text.ToUpper());
        }

        public override void EnterToText([NotNull] SearchParser.ToTextContext context)
        {
            var screenName = context.GetText().Substring(3).Enquote();
            this.whereClause = string.Concat(whereClause, " ", $"udf.matchArrayElement(twt.entities.user_mentions, {{ \"screen_name\" : {screenName} }} )");
        }

        public override void EnterHashText([NotNull] SearchParser.HashTextContext context)
        {
            var hashtag = context.GetText().Enquote();
            this.whereClause = string.Concat(whereClause, " ", $"udf.matchArrayElement(twt.entities.hashtags, {hashtag})");
        }

        public override void EnterExactText([NotNull] SearchParser.ExactTextContext context)
        {
            var text = context.GetText();
            this.whereClause = string.Concat(whereClause, " ", $"CONTAINS(twt.text, {text})");
        }
    }
}

We got our listener ready! Now, all we need is a context class that will bootstrap the lexer and parser and tokens so the input expression is transpiled and the output SQL is generated. Just like our last work on ANTLR, the聽TweetQueryContext class will look like the following:

namespace TweetSearch.CosmosDb.DocumentDb
{
    using Antlr4.Runtime;
    using Antlr4.Runtime.Tree;

    public class TweetQueryContext
    {
        private DocumentDbListener listener;

        public TweetQueryContext()
        {
            this.listener = new DocumentDbListener();
        }

        public SearchParser.ExprContext GenerateAST(string input)
        {
            var inputStream = new AntlrInputStream(input);
            var lexer = new SearchLexer(inputStream);
            var tokens = new CommonTokenStream(lexer);
            var parser = new SearchParser(tokens);
            parser.ErrorHandler = new BailErrorStrategy();

            return parser.expr();
        }

        public string GenerateQuery(string inputText)
        {
            var astree = this.GenerateAST(inputText);
            ParseTreeWalker.Default.Walk(listener, astree);
            return listener.Output;
        }
    }
}

Whew! That was easy, right?

Bootstrapping the api layer:

We have all we need except the api. Thanks to asp .net core, that is two clicks away. Open Visual Studio and open a .net core api project. Our聽TweetsController class looks like the following:

namespace TweetQuery.Controllers
{
    using Microsoft.AspNetCore.Mvc;
    using System.Threading.Tasks;
    using TweetQuery.Lib;
    using TweetQuery.Lib.Model;
    using TweetSearch.CosmosDb.DocumentDb;

    [Route("api/[controller]")]
    public class TweetsController : Controller
    {
        private CosmosDBRepository<Tweet> repository;
        private TweetQueryContext context;

        public TweetsController(CosmosDBRepository<Tweet> repository)
        {
            this.repository = repository;
            this.context = new TweetQueryContext();
        }

        [HttpGet("search")]
        public async Task<IActionResult> Search([FromQuery] string q)
        {
            if (string.IsNullOrEmpty(q))
                return BadRequest();

            var querySql = this.context.GenerateQuery(q).Trim();
            var result = await repository.GetItemsAsync(querySql);
            return Ok(result);
        }
    }
}

I reused the db repository we created earlier and as you see that is dependency injected in the controller which you have to configure in the聽ConfigureServices method in your聽Startup聽 class. I’m not adding that specific code here since it is already in the sample code and doesn’t belong to the scope of this tutorial. Same goes for the model class聽Tweet and the classes it uses inside.

Time to test!

The project is hosted here in github. Clone the code, and build and run it from your visual studio. As a sample query try the following:

http://localhost:5000/api/tweets/search?q=to:hatena_sugoi AND from:maeta_tw OR %23HopesUp OR "Surely June is a summer"

I url-encoded the hashtag here just to be nice on the REST client you might use. I highly suggest Postman聽if you don’t want anything heavy.

I only took the minimalists way of using ANTLR here, you can build your own expression tree based on the auto-generated listener and can do so much more if you want. A perfect example will be LinqToQuerystring聽written by Pete Smith. It generates the necessary LINQ expression for any IQueryable and thus allows you to write database agnostic Odata driven queries and it’s tons faster and lighter than the one Microsoft ships.

I hope this was fun. Happy RESTing!

Creating a nano scripting language using ANTLR and Roslyn

For everyone of us who wakes and codes everyday somewhere in this world, we often find ourselves pretty attached to the programming language we love most. All of us feels that point of idiosyncrasy when we try to break our boundaries and try to learn something new since this field is always expanding and evolving like a universe on steroids.

For those who still are newbies and is trying to find ways to understand how a programming language works, what could be better than trying to make one of your own?聽馃檪 This post is essentially a small proof of concept where we will go for a small nice fun looking esoteric programming language.

Before we jump into the very tidbits inside, allow me to explain what we will do here. We will write a small programming language that is parsed and lexed by ANTLR, transpiles to C# and the transpiled code is fed into Roslyn C# script api.

If the aforementioned words are looking too wordy for you, let me clear it right up for you. Like every language we use to talk every day, programming language comes with a grammar itself. It should be clear as a daylight to you if you have written a single line of code in your life. Every programming language follows a pretty defined structure and a dancing parade of words following that. So, since we are creating one, the first thing we need is that grammar for our language. Instead of doing it from scratch, our tool of choice is ANTLR, which stands for 鈥淎nother Tool for Language Recognition鈥. ANTLR will help us to define the grammar, generate the lexer and parser for it and we will eventually be able to reuse those components to transpile our code to C#. Remember ANTLR do support for javascript, java, python too. So, if you want to have your lexer and parser defined in those languages, please don鈥檛 refrain yourself from using this.

Now, even before we start talking about languages and everything else, we need to understand a bit about compiler theory. Now, I can go into gory details of lexer and parser but since this is an age of google, I will let that responsibility fall in your hand. We will take somewhat of an exploratory way to understand how everything works and take it from there.

Let’s assume that we have a language like this:

derp a = 20 ':)' #Initialization

# basic if-else
a > 2 ???
yep ->
    a = 5 ':)'
kbye

# print
dump a ':)'

The first thing we need is a grammar. To understand the programming language we need something that understands all the words here. And that guy is the lexer. A lexer eats up the whole code block we send to the compiler, chops that into little lexemes (read strings/words here). So we can understand when we have hit a specific keyword. Like for our dummy language here, we used the popular internet lingo derp to initialize a variable.

The next thing in line to do is making some meaningful excerpt from the words. Like when we write a if聽 block, the compiler needs to know what strings of characters or words should stand together to construct a meaningful statement or expression. That is the job of a parser. If you see closely, you will see that every block of code can be expressed as a tree. For example, the initialization block here 聽looks like the following:

Assignment

This is definitely a single branch tree, it says you need to write the word聽derp to start the statement and you should end it with a smiley ( 馃檪 ) to finish the statement. In the middle you use an identifier (name for your variable) and an ASSIGN operator (=) to define the flow of assignment from right to left. That tree is actually generated straight from the grammar we are going to use today.

So, why wait? Let’s have a look at the grammar we are going to be using today:

grammar Profane;

compilationUnit: statement* EOF;

statement:
        printstmt
        | assignstmt
        | ifstmt
		| setstmt;

printstmt	: 'dump' expr? SMILEY;
assignstmt	: 'derp' ID ASSIGN expr SMILEY;
setstmt		:  ID ASSIGN expr SMILEY;

ifstmt  :
        conditionExpr '???'
        'yep ->'
            statement*
        'kbye';

conditionExpr: expr relop expr;
expr: term | opExpression;
opExpression: term op term;
op: PLUS | ASSIGN | MINUS;
relop: EQUAL | NOTEQUAL | GT | LT | GTEQ | LTEQ;

term: ID | number | STRING;

number: NUMBER;

// Keywords
ID: [a-zA-Z_] [a-zA-Z0-9_]*;
SMILEY: ':)';
WS: [ \n\t\r]+ -> skip;

PLUS    :'+';
EQUAL   : '====';
ASSIGN  : '=';
NOTEQUAL: '!!==';
MINUS   : '-';
GT      : '>';
LT      : '<';
GTEQ    : '>=';
LTEQ    : '>=';

fragment INT: [0-9]+;
NUMBER: INT ('.'(INT)?)?;
STRING: '"' (~('\n' | '"'))* '"';

Now, my first advice here will be to not get confused by the size of the grammar and start taking out bits we do understand at first. If you refer to the first image in this and have a look at the grammar you will see that the rule聽assignstmt聽is defined the exact same way depicted in the picture. If you find the words ID, ASSIGN and SMILEY, you will also see that all of them are defined in the grammar below where they have their literal form. These聽tokenshelps the parser to understand what you have written. And the assignstmt聽is called a rule, which define relations among 聽different tokens or rules. See? this is how we build rules for our grammar. Because a grammar is nothing but a set of well defined rules.

By the very first rule named聽compilationUnit,our language is nothing but a set of statements ending with an EOF. Every聽statement can either be a聽printstmt (for printing),聽ifstmt (if-else) or the aforementioned聽assignstmt. Neat huh? You can even go down and find out how the rest of the tree is built.

I strongly suggest using Visual Studio Code and its ANTLR4 extension for writing ANTLR grammar files. You will have nice looking railroad diagram like the one I posted for every rule you write!

Time to get our hands dirty. Fret not since the whole project is publicly available over github so I will only point out excerpts of the code that we need to visit. And I’m going back to the same聽assignstmt. First thing we need to do is download ANTLR聽. Go to the download page and download the latest .jar. ANTLR is written in Java so you will need to have java installed in your machine. We will use .net core here for the rest of the work so you can download that for your OS too. When you are done downloading ANTLR you can generate the target code for C# from your grammar file. In our case the grammar file name was Profane.g4 and to generate the C# lexer and parser based off the code all we had to do is invoke :

java -jar antlr-4.7-complete.jar -Dlanguage=CSharp Profane.g4

It will generate the C# classes you need for walking through the grammar. You will see a lexer and a listener class being created. You don’t really need to touch the lexer class. The listener class is used to handle events that are fired when ANTLR encounters a rule. So, to make use of our assignment statement we need to handle the event that is fired when ANTLR encounters our聽assignstmt聽rule. But how will we ever understand which event is that? Here comes the ANTLR magic.

ANTLR will generate the event you need for all your rules every time you create a lexer and parser from your grammar. That means every time you change your grammar you need to regenerate the C# targets again, the lexer and listener class. I added the command in the build target for the sample project so it will automatically do it on build.

So, lets create a class inherited from ProfaneBaseListener聽 class which was auto generated by ANTLR and name it聽ProfaneListener.聽Since our rule was named聽assignstmt聽ANTLR will generate a method called聽EnterAssignstmt聽inside it which will be invoked every time ANTLR encounters that type of statement or that rule. Our target here is to generate equivalent C# code from it so

derp some = 10 ':)'

will be transpiled in C# equivalent code like the following.

dynamic some = 10;

And we are going to do that in the method聽EnterAssignstmt which ANTLR has built out for us. Let’s have a look at it.

        public override void EnterAssignstmt([NotNull] ProfaneParser.AssignstmtContext context)
        {
            string target = context.ID().GetText();
            dynamic value = this.ResolveExpression(context.expr());
            this.Output += "dynamic " + target + " = " + value + ";\n";
        }

This is really simple work here. We are asking the context class to give us the ID and the expression so we can generate the equivalent C# code string. The nice thing you can notice here is ANTLR has generated class for our assignment statement context itself. But what is that ResolveExpression method. If we remember the rule it was :

Assignment
Rule assignstmt

Here聽expr is another rule. Which looks like.

expr
Rule expr

That means, expr can either be a rule named聽term or a rule named聽opExpression.聽Let’s have a look at both of them.

First is the rule called term. A term can be an identifier (the name for your variable), a number (int or float) or a string. Either one of these.

term
Rule term

That means that term can also be a valid value for rule expr. Since expr is either聽term聽or聽opExpression

The opExpression on the other hand is a tad complex one. This is an example where you can reuse multiple rules to create a complex rule.

opExpression

The only thing that we don’t know here is the聽op rule. the聽opExpression rule says it is structured as term followed by a rule聽named聽op and there has to be another聽term in the end.

op
Rule op

The聽 op聽rule defines an OR relationship between PLUS, MINUS and ASSIGN which stands respectively for ‘+’, ‘-‘ and ‘=’. That means this rule says we can write things like

derp some = 10 + 2 + someOtherDerp 馃檪

Amazing! Isn’t it?

Before we look into the聽ResolveExpression聽method, let’s see a nice looking tree on how that previous statement actually gets parsed by all these rules.

assigngraph

This will hopefully help you to understand how things are happening here. Now, lets see the聽ResolveExpression聽method which transpiles the rule聽expr.聽

        private dynamic ResolveExpression(ProfaneParser.ExprContext exprContext)
        {
            var opExpression = exprContext.opExpression();
            if (opExpression != null)
            {
                return ResolveOpExpression(opExpression);
            }
            else
            {
                return ResolveTerm(exprContext.term());
            }
        }

        private dynamic ResolveOpExpression(ProfaneParser.OpExpressionContext plusContext)
        {
            var leftTerm = plusContext.term().First();
            var rightTerm = plusContext.term().Last();

            var left = ResolveTerm(leftTerm);
            var right = ResolveTerm(rightTerm);

            return left + plusContext.op().GetText() + right;
        }

        private dynamic ResolveTerm(ProfaneParser.TermContext termContext)
        {
            if (termContext.number() != null)
            {
                return termContext.number().GetText();
            }
            else if (termContext.ID() != null)
            {
                return termContext.ID().GetText();
            }
            else if (termContext.STRING() != null)
            {
                Regex regex = new Regex("/\\$\\{([^\\}]+)\\}/g");
                var contextText = termContext.GetText();
                var replacedString = regex.Replace(contextText, "$1");
                return replacedString;
            }
            else return default(dynamic);
        }

We also see two new methods the聽ResolveExpression method uses named聽ResolveTerm and聽ResolveOpExpression. They generate the transpiled C# code for term rule and opExpression rule. We keep adding the generated code in a string named output and when it’s done we have our C# transpiled code ready to be executed.

Executing C# as a script using Roslyn:

Now that we have our C# code to be executed, we will use another tool called Roslyn. It is a compiler tool for .net that gives you rich set of features regarding code analysis and compilation. We will specifically be using the C# scripting api.

First we need to generate the AST for our code. If you are scratching head on what an abstract syntax tree is, you already saw something like it in the tree we posted before. To generate the tree, you need your lexer. Your lexer will generate tokens. Your parser will use those tokens to start the execution unit you need to compile your code which is the root node for your tree. This is still done using ANTLR.

When you have your tree, you need to walk on it. When you walk on the AST, the listener fires the events we need to generate the transpiled code like we did minutes ago. So the listener output is our C# code which we need to feed to roslyn.

Roslyn C# script engine comes with a nifty class named聽CSharpScript which will do the trick for you. All we have to do is to feed the C# code and load the assemblies we will need. Then, it will do its magic and we will have our own scripting language talking to us.

So, our transpiler class looks like

    public class ProfaneTranspiler
    {
        private ProfaneListener listener;
        private static readonly MetadataReference[] References =
        {
            MetadataReference.CreateFromFile(typeof(object).GetTypeInfo().Assembly.Location),
            MetadataReference.CreateFromFile(typeof(RuntimeBinderException).GetTypeInfo().Assembly.Location),
            MetadataReference.CreateFromFile(typeof(System.Runtime.CompilerServices.DynamicAttribute).GetTypeInfo().Assembly.Location),
            MetadataReference.CreateFromFile(typeof(ExpressionType).GetTypeInfo().Assembly.Location),
            MetadataReference.CreateFromFile(Assembly.Load(new AssemblyName("mscorlib")).Location),
            MetadataReference.CreateFromFile(Assembly.Load(new AssemblyName("System.Runtime")).Location)
        };

        public ProfaneTranspiler()
        {
            this.listener = new ProfaneListener();
        }

        public ProfaneParser.CompilationUnitContext GenerateAST(string input)
        {
            var inputStream = new AntlrInputStream(input);
            var lexer = new ProfaneLexer(inputStream);
            var tokens = new CommonTokenStream(lexer);
            var parser = new ProfaneParser(tokens);
            parser.ErrorHandler = new BailErrorStrategy();

            return parser.compilationUnit();
        }

        public string GenerateTranspiledCode(string inputText)
        {
            var astree = this.GenerateAST(inputText);
            ParseTreeWalker.Default.Walk(listener, astree);
            return listener.Output;
        }

        public async Task&amp;amp;amp;amp;lt;TranspileResult&amp;amp;amp;amp;gt; RunAsync(string code)
        {
            var result = new TranspileResult();

            if (string.IsNullOrEmpty(code))
                return result;

            Stopwatch watch = new Stopwatch();
            watch.Start();

            try
            {
                ScriptOptions scriptOptions = ScriptOptions.Default;
                scriptOptions = scriptOptions.AddReferences(References);
                scriptOptions = scriptOptions.AddImports("System");

                var resultCode = this.GenerateTranspiledCode(code);
                if (resultCode == null)
                {
                    watch.Stop();
                    result.TimeElapsed = watch.Elapsed.ToString();
                    return result;
                }

                var outputStrBuilder = new StringBuilder();
                using (var writer = new StringWriter(outputStrBuilder))
                {
                    Console.SetOut(writer);
                    var scriptState = await CSharpScript.RunAsync(resultCode, scriptOptions);
                    result.output = outputStrBuilder.ToString();
                }
            }
            catch (Exception ex)
            {
                result.output = ex.Message;
            }
            finally
            {
                watch.Stop();
                result.TimeElapsed = watch.Elapsed.ToString();
            }
            return result;
        }
    }

I uploaded the full sample code in github here. You need to build and run the Profane project which is a console app. It will host a small web api in port 5000. If you POST your code to the endpoint as plain text in the POST body, you will get back the output of your code. Postman聽can be a nice client to do so.

Hope this was fun. Knowing the internals of your daily programming language essentially boosts up the confidence while you write it. So make your own esoteric language if you have time. It’s always fun to make em.

Confessions

Before I start writing this, I must say this is probably the first time I’m treating this blog like I want it to be treated. Most of the time I wrote things people only cares about when they want their problem fixed. For the last couple of months or a year I didn’t even write much. It seems that socials has taken a big chunk of my time and now I’m trying to get out of that addiction.

Money, papers with vengeance

Around 4 years ago, I gave into the concept of working for money. Money talks, doesn’t it? It talks louder than anything else. So, that was it for me. I went out with a little help of someone I know, went into an interview, practically said I would do anything to get some money and started working.

I started working on perl. It’s a nice little language (believe me, it took a long time for me to come to this verdict). Nice and amusing as it is, it was indeed mischievous. For a guy who doesn’t know much about linux or any unix per say, it was a hard time to cope up and get going. Boy, I hated it in the beginning. I used to mail my superior almost everyday to make sure that someday he ports me somewhere I can write something C#.

The fact I liked Windows so much wasn’t a fun party either. The internet is right now is full of sages. Sages who are so opinionated about everything so that unless you don’t come in terms with what they believe, they’d literally treat that act as a blasphemy. Boy, I even had a facebook page dedicated for trolling me and one of my very close mentors. Fun times, I still don’t know who was behind that. Wish I knew. But that’s another story for another day.

Present is a gift, a confusing gift indeed

Right at this point of my life, I’m probably the most confused as ever. When I was a kid, i saw my mom and dad work, work like hell. Just trying their best to put everything in place and make the ends meet. And the worst part of this is now I understand the necessity of it. I really didn’t at that time. Now I don’t have an excuse for being this person. Now, I don’t know what I am supposed to be.

It’s really funny. When I was a preteen or a teen all I ever wanted to become is a musician. That is of course before life came in and hit me in the nuts. That is when your dreams go down the drain and you start doing the thing you’re good at and the one that makes money. I was no different at all. I’m lucky that I’m passionate about it. Otherwise I don’t know what would happen.

Know thyself

When you start to understand who you are, two things will happen. You’d know your limits, you’d be a good friend to yourself. The worst part of all of this is, it would make you aware of everything. It would take away the spontaneous sets of emotions since now you can pretty much predict what your brain would do.

聽Love and its baggage

Boy, this shit confused me more than anything else ever did in my life. I lost and gained a lot through love. For me I think it had to do a lot with finding your own purpose. When one person becomes a lot more important than any goal you ever chased, when that very person becomes your prime directive. And your brain goes to a hyperdrive. It starts to calculate all possible memories you could make with her. Its a tree your brain loves to parse. But beware, it also comes with attachments. For me it was even scarier, my childhood was insanely lonely and I basically grabbed anyone I saw that I imagined can play a part in my life. Scary, huh? Well you haven’t heard the scariest part yet. The moment you drop your guards all the insecurities will show their ugly heads. A person you want you around would see you as you truly are. That is sometimes perceived wrong on the other side. At some point you’d get scared to open up. Because you don’t know what it will cost you. It would only make you feel no one wants to be around you just because it is you. And that thought itself would isolate you from the rest of the world just like that.

To obligations and beyond

Obligations are the shittiest thing you’d ever encounter. They’d make you pay, I tell you. You look at your family, you see obligations. You look at the person you love most, you feel a drive to make things better for her. Fuck me, I can’t find anyone with a pair of eyes I don’t have to pay anything. I don’t owe anything. For hell as I sure,I don’t owe anything to this world. I dont. People talk about priorities. Trust me priority is a two way street. It only meets when both of them starts to work towards each other. Much like a bidirectional a star search.

Freedom from life itself

Rules never worked on me. Probably never will. My brain is a child with always asking “Why”. And I hate the fact that it does that. Not that it helps it anyway , it still does that. Youd think Kurt Cobain was wrong. I don’t see it that way. I don’t know why I have a twisted sense of judgement. The pursuit of happiness is said to be started when you leave your expectations behind. What if I expect to find something that will unbind me from expectations?

Paradox indeed.

I thought I knew C# : Garbage collection & disposal. Part-II

Okay, we are back in to collect “garbage” properly. If you haven’t the first part of this post you might want to read it here. We are following norms and conventions from the first post here too.

聽Starting things from where we left off:

This write up continues after the first one where we ended things with SafeHandle class and聽IDisposable聽聽interface. I do see how intriguing this is of course. But before that, like a unexpected, miserable commercial break before the actual stuff comes on your TV, let’s go have a look on something called finalization.

What you create, you “might” need to destroy:

If you know a little bit of C++ you’d know that there is a thing called聽destructor and the name implies it does the exactly opposite of what a constructor does. C++ kind of needs it since it doesn’t really have a proper garbage collection paradigm. But that also raises the question of whether C# has a destructor聽and if it does what does it do and why do we even have one since we said managed resourced would be collected automatically.

Lets jump onto some code, shall we?

class Cat
{
    ~Cart()
    {
        // cleanup things
    }
}

Wait a minute, now this is getting confusing. I have聽IDisposable::Dispose() and I have a destructor. Both looks like to have same responsibility. Not exactly. Before we confuse ourselves more, lets dig a bit more in the code. To be honest, C# doesn’t really have a destructor, it’s basically a syntactic sugar and inside c sharp compiler translates this segment as

protected override void Finalize()
{
    try
    {
        // Clean things here
    }
    finally
    {
        base.Finalize();
    }
}

We can pick up to things here. First thing is the destructor essentially translates to a overridden聽Finalize() method. And it also calls the聽Finalize()base class in the finally block. So, it’s essentially a recursive聽finalize().Wait, we have no clue what is聽Finalize().

Finalize, who art thou?

Finalize is somebody who is blessed to talk with the garbage collector. If you have already questioning where the topics we discussed in last post comes in help, this is the segment. Lets start getting answers for all our confusions on last segment. First, why聽Finalizeis overridden and where does it gets its signature.聽Finalize gets its signature from Object class. Okay, understandable. What would be the default implementation then? Well, it doesn’t have a default implementation. You might ask why. A little secret to slip in here, remember the聽mark聽step of garbage collector. He聽marks a type instance for finalization if and only if it has overridden the聽Finalize() method. It’s your way of telling the garbage collector that you need to do some more work before you can reclaim my memory. Garbage collector would聽mark this guy and put him in a聽finalization queue which is essentially a list of objects whose finalization codes must be run before GC can reclaim their memory. So, you are possibly left with one more confusion now. And that is, you understood garbage collector uses this method to聽finalize things, i.e. doing the necessary cleanup. Now, then why do we need聽IDisposable where we can just override finalize and be done with it, right?

Dispose, you confusing scum!

Turns out dispose intends to point out a pattern in code that you can use to release unmanaged memory. What I didn’t tell you about garbage collectorbefore is you don’t really know when he would essentially do that, you practically have no clue. That also means if you write an app that uses unmanaged resources like crazy like reading 50-60 files at a time, you are using a lot of scarce resources at the same time. And in the end you are waiting for GC to do his job but that guy has no time table. So, hoarding these resources is not a good idea in the meantime. Since releasing unmanaged resources are developers duty, putting that over a finalize method 聽and waiting for GC to come and invoke that is a stupid way to go. Moreover, if you send an instance to a finalization queue, it means, GC will essentially do the memory cleanup in the next round, he will only invoke finalize this round. That also means GC has to visit you twice to clear off your unused occupied memory which you kinda need now. And the fact that you might want to release the resources NOW is a pretty good reason itself to not wait for GC to do your dirty work. And, when you actually shut down your application, Mr. GC visits you unconditionally and takes out EVERYONE he finds. I hope the need of聽Dispose()聽is getting partially clear to you now. We need a method SomeMethod()聽that we can call which would clean up the unmanaged resources. If we fail to call that at some point, just to make sure garbage collector can call that we will use that same method inside聽Finalize() so it is called anyhow. If I have not made a fool out of myself at this point, you have figured out the fact that聽SomeMethod() is聽Dispose(). Okay, so we know what we are going to do. Now we need to act on it. We will implement the dispose pattern we have been talking about. The first thing we would do here is we would try to write code that reads a couple of lines from a file. We would try to do it the unmanaged way, then move it to slowly to the managed way and in the process we would see how we can use IDisposable there too.

Doing things the unsafe way:

I stole some code from a very old msdn doc which describes a FileReader class like the following:

using System;
using System.Runtime.InteropServices;
public class FileReader
{
    const uint GENERIC_READ = 0x80000000;
    const uint OPEN_EXISTING = 3;
    IntPtr handle;
[DllImport("kernel32", SetLastError = true)]
    static extern unsafe IntPtr CreateFile(
            string FileName,                    // file name
            uint DesiredAccess,                 // access mode
            uint ShareMode,                     // share mode
            uint SecurityAttributes,            // Security Attributes
            uint CreationDisposition,           // how to create
            uint FlagsAndAttributes,            // file attributes
            int hTemplateFile                   // handle to template file
            );
[DllImport("kernel32", SetLastError = true)]
    static extern unsafe bool ReadFile(
            IntPtr hFile,                       // handle to file
            void* pBuffer,                      // data buffer
            int NumberOfBytesToRead,            // number of bytes to read
            int* pNumberOfBytesRead,            // number of bytes read
            int Overlapped                      // overlapped buffer
            );
[DllImport("kernel32", SetLastError = true)]
    static extern unsafe bool CloseHandle(
            IntPtr hObject   // handle to object
            );
    public bool Open(string FileName)
    {
        // open the existing file for reading
        handle = CreateFile(
                FileName,
                GENERIC_READ,
                0,
                0,
                OPEN_EXISTING,
                0,
                0);
if (handle != IntPtr.Zero)
            return true;
        else
            return false;
    }
    public unsafe int Read(byte[] buffer, int index, int count)
    {
        int n = 0;
        fixed (byte* p = buffer)
        {
            if (!ReadFile(handle, p + index, count, &amp;n, 0))
                return 0;
        }
        return n;
    }
    public bool Close()
    {
        // close file handle
        return CloseHandle(handle);
    }
}

Please remember you need to check your聽Allow Unsafe Code checkbox in your build properties before you start using this class. Lets have a quick run on the code pasted here. I don’t intend to tell everything in details here because that is not the scope of this article. But we will build up on it, so we need to know a little bit. The聽DllImport attribute here is essentially something 聽you would need to use an external dll (thus unmanaged) and map the functions inside it to your own managed class. You can also see that’s why we have used the聽extern keyword here. The implementations of these methods doesn’t live in your code and thus your garbage collector can’t take responsibility of clean up here. 馃檪 The next thing you would notice is the聽fixed聽statement. fixed statement essentially link up a managed type to an unsafe one and thus make sure GC doesn’t move the managed type when it collects. So, the managed one stays in one place and points to the unmanaged resource perfectly. So, what are we waiting for? Lets read a file.

static int Main(string[] args)
{
    if (args.Length != 1)
    {
        Console.WriteLine("Usage : ReadFile &lt;FileName&gt;");
        return 1;
    }
    if (!System.IO.File.Exists(args[0]))
    {
        Console.WriteLine("File " + args[0] + " not found.");
        return 1;
    }
    byte[] buffer = new byte[128];
    FileReader fr = new FileReader();
    if (fr.Open(args[0]))
    {
        // Assume that an ASCII file is being read
        ASCIIEncoding Encoding = new ASCIIEncoding();
        int bytesRead;
        do
        {
            bytesRead = fr.Read(buffer, 0, buffer.Length);
            string content = Encoding.GetString(buffer, 0, bytesRead);
            Console.Write("{0}", content);
        }
        while (bytesRead &gt; 0);
        fr.Close();
        return 0;
    }
    else
    {
        Console.WriteLine("Failed to open requested file");
        return 1;
    }
}

So, this is essentially a very basic console app and looks somewhat okay. I have created a byte array of size 128 which I would use as a buffer when I read. FileReader returns 0 when it can’t read anymore. Don’t get confused seeing this.

while (bytesRead > 0)

It’s all nice and dandy to be honest. And it works too. Invoke the application (in this case the name here is 聽TestFileReading.exe) like the following:

TestFileReading.exe somefile.txt

And it works like a charm. But what I did here is we closed the file after use. What if something happens in the middle, something like the file not being available. Or I throw an exception in the middle. What will happen is the file would not be closed up until my process is not closed. And the GC will not take care of it because it doesn’t have anything in the聽Finalize() method.

Making it safe:

public class FileReader: IDisposable
{
    const uint GENERIC_READ = 0x80000000;
    const uint OPEN_EXISTING = 3;
    IntPtr handle = IntPtr.Zero;
    [DllImport("kernel32", SetLastError = true)]
    static extern unsafe IntPtr CreateFile(
            string FileName,                 // file name
            uint DesiredAccess,             // access mode
            uint ShareMode,                // share mode
            uint SecurityAttributes,      // Security Attributes
            uint CreationDisposition,    // how to create
            uint FlagsAndAttributes,    // file attributes
            int hTemplateFile          // handle to template file
            );
    [DllImport("kernel32", SetLastError = true)]
    static extern unsafe bool ReadFile(
            IntPtr hFile,                   // handle to file
            void* pBuffer,                 // data buffer
            int NumberOfBytesToRead,      // number of bytes to read
            int* pNumberOfBytesRead,     // number of bytes read
            int Overlapped              // overlapped buffer
            );
    [DllImport("kernel32", SetLastError = true)]
    static extern unsafe bool CloseHandle(
            IntPtr hObject   // handle to object
            );
    public bool Open(string FileName)
    {
        // open the existing file for reading
        handle = CreateFile(
                FileName,
                GENERIC_READ,
                0,
                0,
                OPEN_EXISTING,
                0,
                0);
        if (handle != IntPtr.Zero)
            return true;
        else
            return false;
    }
    public unsafe int Read(byte[] buffer, int index, int count)
    {
        int n = 0;
        fixed (byte* p = buffer)
        {
            if (!ReadFile(handle, p + index, count, &amp;n, 0))
                return 0;
        }
        return n;
    }
    public bool Close()
    {
        // close file handle
        return CloseHandle(handle);
    }
    public void Dispose()
    {
        if (handle != IntPtr.Zero)
            Close();
    }
}

Now, in our way towards making things safe, we implemented聽IDisposable聽here. That exposed聽Dispose() and the first thing I did here is we checked whether the handle is IntPtr.Zero and if it’s not we invoked聽Close(). Dispose() is written this way because it should be invokable in any possible time and it shouldn’t throw any exception if it is invoked multiple times. But is it the solution we want? Look closely. We wanted to have a聽Finalize() implementation that will essentially do the same things if somehow聽Dispose()聽is not called. Right?

Enter the Dispose(bool) overload. We want the parameter less聽Dispose() to be used by only the external consumers. We would issue a second聽Dispose(bool) overload where the boolean parameter indicates whether the method call comes from a聽Dispose method or from the finalizer. It would be true if it is invoked from the parameter less聽Dispose() method.

With that in mind our code would eventually be this:

    public class FileReader: IDisposable
    {
        const uint GENERIC_READ = 0x80000000;
        const uint OPEN_EXISTING = 3;
        IntPtr handle = IntPtr.Zero;
        private bool isDisposed;

        SafeHandle safeHandle = new SafeFileHandle(IntPtr.Zero, true);

        [DllImport("kernel32", SetLastError = true)]
        static extern unsafe IntPtr CreateFile(
              string FileName,                  // file name
              uint DesiredAccess,              // access mode
              uint ShareMode,                 // share mode
              uint SecurityAttributes,       // Security Attributes
              uint CreationDisposition,     // how to create
              uint FlagsAndAttributes,     // file attributes
              int hTemplateFile           // handle to template file
              );

        [DllImport("kernel32", SetLastError = true)]
        static extern unsafe bool ReadFile(
             IntPtr hFile,                // handle to file
             void* pBuffer,              // data buffer
             int NumberOfBytesToRead,   // number of bytes to read
             int* pNumberOfBytesRead,  // number of bytes read
             int Overlapped           // overlapped buffer
             );

        [DllImport("kernel32", SetLastError = true)]
        static extern unsafe bool CloseHandle(
              IntPtr hObject   // handle to object
              );

        public bool Open(string FileName)
        {
            // open the existing file for reading
            handle = CreateFile(
                  FileName,
                  GENERIC_READ,
                  0,
                  0,
                  OPEN_EXISTING,
                  0,
                  0);

            if (handle != IntPtr.Zero)
                return true;
            else
                return false;
        }

        public unsafe int Read(byte[] buffer, int index, int count)
        {
            int n = 0;
            fixed (byte* p = buffer)
            {
                if (!ReadFile(handle, p + index, count, &amp;n, 0))
                    return 0;
            }
            return n;
        }

        public bool Close()
        {
            // close file handle
            return CloseHandle(handle);
        }

        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        protected virtual void Dispose(bool isDisposing)
        {
            if (isDisposed)
                return;

            if (isDisposing)
            {
                safeHandle.Dispose();
            }

            if (handle != IntPtr.Zero)
                Close();

            isDisposed = true;
        }
    }

Now if you focus on the changes we made here is introducing the following method:

protected virtual void Dispose(bool isDisposing)

Now, this method envisions what we discussed a moment earlier. You can invoke it multiple times without any issue. There are two prominent block here.

  • The conditional block is supposed to free managed resources (Read invoking Dispose() methods of other IDisposable member/properties inside the class, if we have any.)
  • The non-conditional block frees the unmanaged resources.

You might ask why the conditional block tries to dispose managed resources. The GC takes care of that anyway right? Yes, you’re right. Since garbage collector is going to take care of the managed resources anyway, we are making sure the managed resources are disposed on demand if only someone calls the parameter less Dispose().聽

Are we forgetting something again? Remember, you have unmanaged resources and if somehow the Dispose() is not invoked you still have to make sure this is finalized by the garbage collector. Let’s write up a one line destructor here.

 ~FileReader()
 {
    Dispose(false);
 }

It’s pretty straightforward and it complies with everything we said before. Kudos! We are done with FileReader.

Words of Experience:

Although we are safe already. We indeed forgot one thing.聽If we invoke聽Dispose() now it will dispose unmanaged and managed resources both. That also means when the garbage collector will come to collect he will see there is a destructor ergo there is a Finalize() override here. So, he would still put this instance into Finalization Queue. That kind of hurts our purpose. Because we wanted to release memory as soon as possible. If the garbage collector has to come back again, that doesn’t really make much sense. So, we would like to suppress the garbage collector to invoke Finalize() if we know we have disposed it ourselves. And a single line modification to the Dispose() method would allow you to do so.

public void Dispose()
{
    Dispose(true);
    GC.SuppressFinalize(this);
}

We added the following statement to make sure if we have done disposing ourselves the garbage collector would not invoke聽Finalize() anymore.

GC.SuppressFinalize(this);

Now, please keep in mind that you shouldn’t write a GC.SupperssFinalize() in a derived class since your dispose method would be overridden and you would follow the same pattern and call聽base.Dispose(isDisposing) in the following way:

class DerivedReader : FileReader
{
   // Flag: Has Dispose already been called?
   bool disposed = false;

   // Protected implementation of Dispose pattern.
   protected override void Dispose(bool disposing)
   {
      if (disposed)
         return; 

      if (disposing) {
         // Free any other managed objects here.
         //
      }

      // Free any unmanaged objects here.
      //
      disposed = true;

      // Call the base class implementation.
      base.Dispose(disposing);
   }

   ~DerivedClass()
   {
      Dispose(false);
   }
}

It should be fairly clear to now why we are doing it this way. We want disposal to go recursively to base class. So, when we dispose the derived class resources, the base class disposes its own resources too.

To use or not to use a Finalizer:

We are almost done, really, we are. This is a section where Im supposed to tell you why you really shouldn’t use unmanaged resources whenever you need. It’s always a good idea not to write a Finalizer if you really really don’t need it. Currently we need it because you are using a unsafe file handle and we need to close it manually. To keep destructor free and as managed as possible, we should always wrap our handles in SafeHandle class and dispose the SafeHandle as a managed resource. Thus, eliminating the need for cleaning unmanaged resources and the overloaded聽Finalize() . You will find more about that here.

“Using” it right:

Before you figure out why I quoted the word聽using here, let’s finally wrap our work up. We have made our FileReader class disposable and we would like to invoke dispose() after we are done using it. We would opt for a try-catch-finally block to do it and will dispose the resources in the聽finally block.

FileReader fr = new FileReader();
try
{
    if (fr.Open(args[0]))
    {
        // Assume that an ASCII file is being read
        ASCIIEncoding Encoding = new ASCIIEncoding();
        int bytesRead;
        do
        {
            bytesRead = fr.Read(buffer, 0, buffer.Length);
            string content = Encoding.GetString(buffer, 0, bytesRead);
            Console.Write("{0}", content);
        }
        while (bytesRead &gt; 0);
        return 0;
    }
    else
    {
        Console.WriteLine("Failed to open requested file");
        return 1;
    }
}
finally
{
    if (fr != null)
        fr.Dispose();
}

The only difference you see here that we don’t explicitly call Close() anymore. Because that is already handled when we are disposing the FileReader instance.

Good thing for you is that C# has essentially made things even easier than this. Remember the using statements we used in Part-I? An聽using statement is basically a syntactic sugar placed on a try-finally block with a call to Dispose() in the finally block just like we wrote it here. Now, with that in mind, our code-block will change to:

using (FileReader fr = new FileReader())
{
    if (fr.Open(args[0]))
    {
        // Assume that an ASCII file is being read
        ASCIIEncoding Encoding = new ASCIIEncoding();
        int bytesRead;
        do
        {
            bytesRead = fr.Read(buffer, 0, buffer.Length);
            string content = Encoding.GetString(buffer, 0, bytesRead);
            Console.Write("{0}", content);
        }
        while (bytesRead &gt; 0);
        return 0;
    }
    else
    {
        Console.WriteLine("Failed to open requested file");
        return 1;
    }
}

Now you can go back to part-I and try to understand the first bits of code we saw. I hope it would make a bit better sense to you now. Hope you like it. Hopefully, if there’s a next part, I would talk about garbage collection algorithms.

You can find the code sample over github here.