blog


18
Feb 12

Structural Pattern Matching using Exceptions

Back in college when I was first exposed to functional languages, I fell in love with algebraic data types and structural pattern matching. Now that I have joined the work-force I no longer have the freedom to work with those languages. So I decided to give a shot at emulating structural pattern matching in Java.

If this concept is new to you here’s a short intro. Let’s say we want to represent binary trees. We know that a tree has three kinds of structures:

  • A node that can have a left branch and right branch
  • A leaf that has a value
  • An empty tree with no value or branches

In Haskell, we can group these three structures under a single data type:

image

Now, whenever we do any kind of operation on trees, we can use pattern matching to find out which of these three structures we are dealing with. For example, here is function that calculates the depth of a tree.

image

This recursive function, tests the structure of the tree and returns different values depending on the pattern that matched.

Now, all that is good. But how do we implement the same in an object oriented language that does not support algebraic data types or pattern matching. Well, the closest thing to algebraic data types in an OOP language like Java is a class. And to simulate pattern matching we will use a feature called polymorphism.

Here’s our first implementation:

image

Nothing fancy is going on in this code snippet. I declared an interface called Tree which defines a method signature called “depth”. There are three classes that implement this interface. And each class provides it’s own implementation of depth. With this setup, the master depth function is trivial:

image

With the help of polymorphism, at each step of the recursion, the right implementation of depth is going to be called based on the class.

So? What’s the problem?  Well, it was trivial to write, but it’s going to be a nightmare to maintain this setup. Let’s say, tomorrow we want to add a function to flatten a tree, or a function to do an in-order traversal. We would have to add the methods to the tree interface. And then we would need to add an implementation of these methods to each of the three classes. Doesn’t sound like a lot of work. But imagine if we were distributing these classes as a library and there were hundreds of other people using it. Each time we add a couple of utility methods to the Tree interface we would need to recompile all the classes and deploy a new version of the library, and ask hundreds of users to update to the latest version.

So, we will need to think of a different approach. One that does not require us to change the original classes. We need an approach that empowers the library user to write his own implementation of “depth” without any fuss.

The quick and dirty way would be to use the instanceof operator to perform pattern matching manually.

image

This version works, but it has its problems. By using the instanceof operator we are giving up all compile-time guarantees on whether we are doing our cast correctly. That means, if you make any mistake, you’ll only find that out only at runtime. Moreover, our previous approach used interfaces. So we were guaranteed to have an implementation of depth for each possible structure. In our new approach, there are no such guarantees. If the library user, forgot to check for a particular variant of the tree structure he wouldn’t get any compile time warning, just an exception at runtime.

We need a new approach. One that takes advantage of compile time checks and also forces us to exhaustively check for all possible structures. We can do that using Exceptions and Try-Catch blocks. Here’s our new implementation of Tree:

image

Here are the important differences:

  • Tree is not an interface anymore, it’s a concrete class
  • Tree extends Exception, so it can be thrown
  • Node, Leaf, and Empty are also exceptions, so they can also be thrown
  • The match method can throw an exception corresponding to each possible structure

With our new approach, here is our new depth function:

image

Since the match method of the Tree class exhaustively lists all possible structures as throwable Exceptions, the depth function will even not compile unless there is a catch block for each structure. As a result, you are getting both exhaustiveness and compile time checks at the same time. To be honest, this does not guarantee 100% exhaustiveness. The developer of the library has to make sure he throws an Exception for each possible sub-class of his algebraic type. But at least, in this approach, the burden of responsibility lies on the API side, not on the user. Therefore, if any future release of the library introduces a new structure, users won’t have to read the documentation, or discover it at runtime. They can just rely on the compiler to do the check for them and identify the affected methods.

There’s just one thing that makes this approach less than perfect. Unfortunately, our tree class cannot be generic. Because of the way generics are implemented in Java, sub-classes of Exception are not allowed to be generic.

If this is a deal breaker for you, check out this excellent blog post that describes another approach using the Functional Java library.


17
Jan 12

A rant against “religious spam”

I don’t claim to be a religious person. However I do view religion as a part of my identity, just like my nationality. Just like I won’t tolerate racist behavior against Bangladeshis, I wouldn’t tolerate mistreatment of Muslims either. However the opposite scenario is also true. Just like how I am sickened when I hear about a Bangladeshi doing something stupid to ruin our reputation, I am also ashamed when a fellow Muslim make us all look misinformed. This is really what this rant is all about.

Since the olden days of “Hotmail” people have been forwarding emails containing scientifically inaccurate “proofs” of vague concepts mentioned in the Quran. Even with the advent of social networks, people haven’t changed much. I still see some of my Facebook friends copy and paste statuses that outrageously inaccurate. Here’s one of my recent favorites:

image

 

So “all the rays will emit from your brain to earth”, will it? As if electromagnetic waves are like water drops and will drip of your hair when you lower your head? So why I don’t see sunlight coming out of ears when you pray. Or why not the latest episode of America’s got Talent? They are all electromagnetic waves just like mobile signals.

I don’t mind people posting religious content on Facebook. In fact I actually encourage it because social networks are a great way of reaching out to people and I don’t see why religious scholars shouldn’t make use of it. I would just like to see authentic material. Quote something inspiring from the Quran, or a Hadith. Translate it into English or in your mother-tongue so others can understand. Just stop posting this non-scientific nonsense. You guys are all educated people. Just exercise your high-school science skills before copying statuses and spreading religious spam.

image

And if you would like to go the extra mile, click next to the post and mark it as spam to help stop spread this disease.


13
Jan 12

My First Cinegraph

Cinegraph_final

It’s not a perfect cinegraph, but she’s adorable nonetheless…


24
Sep 11

CS Reality Check : Deadlines

University professors want you to believe that if you are failing to meet your deadlines you are “not managing your time properly”. This is not true for a number of reasons.

In real life people hardly shove deadlines down your throat. The way it usually works is the project manager first lists all the activities that needs to be done. Then all the “owners” of each activity gives an estimate on how long each activity will take. And then, based on the program’s priorities, the PM assigns deadlines for every activity trying to respect the estimated durations as much as possible.

In a way, professors are actually doing more harm to you by giving you deadlines in the first place. The most important skill for a developer working in the real world, is the ability to reliably estimate the duration of work. Deadlines are okay during the freshmen and sophomore years. There isn’t any significant amount of coding in the first two years. But from your third year and onwards, you are faced with 4-6 week long programming assignments. This is something that requires a bit of planning. Depending on the courses you take in your Junior year, the deadlines for your 4-6 week long assignment may not be compatible with your workload from other courses. In real life, you would first look at all your assignments from all your courses, set priorities to them, and then *plan* for a 4-6 week long slot at some point during the semester. This kind of project management skill is vital for a developer to succeed in real life. A pre-determined schedule is not guaranteed to work for every student.


9
Jun 11

UI Design and Cosmetic Errors

Scenario 1

Alice: But the user selected X, but here the app says Y.

Bob: Ah ! Yes, it’s just a cosmetic error. We’ll fix that in the next release.

Scenario 2

Alice: We have revamped our UI to look pretty, but I think steps 2 and 4 of our check out process are very confusing.

Bob: I appreciate your feedback, but we have budget, resource, and time constraints. We cannot always strive to be perfectionists.

Scenario 3

Alice: I think we can design a better user experience by designing a custom page rather than relying on the templates provided by our BPM software.

Bob: But we paid so much for this BPM software. We must use its out-of-the-box features.

Wish I could say

  • A cosmetic error is when you display the right information but maybe the alignment is a bit off.
  • If we had spent our budget and resources on making steps 2 & 4 more intuitive, we would have a better product.
  • Three words: “Sunk Cost Fallacy”. You cannot get back what you already invested. The least you could do is to stop accumulating further expenses and making the right choices.

1
Apr 11

Customizing Auto-boxing Behavior

In Java, you can do this:

ArrayList<double> list = new ArrayList<double>();
list.add(5);
double d = list.get(0);

Since 1.5 you can assign Doubles to doubles and Integers to ints and so on. Also since the dawn of time you can do the following:

MyClass obj = new MyClass();
System.out.println(obj);

Passing an object reference to System.out implicitly calls the toString() method. Even though this is not considered auto-boxing, from a coding perspective they provide the same feature “implicit method calling”. I see why we shouldn’t be able to do this for any class we write. Just as would override the toString() method, I could also override default auto-boxing method.


4
Mar 11

Developing a rich UI in Java – 1

Welcome to a new series of blog posts dedicated to documenting my attempts at developing a high quality UI in Java. As a case study I am choosing to port the iPad version of the popular Things application to Java. My end result should look something like this:

From the looks of it, Things does not seem to be a very complicated application. The UI is fairly straightforward. The total number of interactions between different components also feels reasonable. But the devil is in the details. Implementing the same functionality in a Java application is a piece of cake, but getting all the subtle visual elements right is the tricky part.

Here are the things I would like to investigate over the next few days:

  1. Light to dark gray gradient around the edges.
  2. 3D emboss effect of the button
  3. Implementing the todo list pane as JTables

I started off, with the first task in my list: trying to mimic the gradient. And this what I got:

image

Not even close to the iPad version. The gradient has only been applied vertically whereas the original version applies it to all the edges. Moreover, there are visible bands of color instead of a smooth gradient. I read somewhere that this might be due to my monitor. But I have a nice HD screen, so I don’t think this is the case. Hopefully, when I use the LinearGradientPaint class in Java and restrict the gradient to near the edges, this won’t be much of a problem.


8
Feb 11

Calling Fortran Shared Library from C

1. Write the following piece of code in a F95 file

		/* foo.f95 */

        integer function add2i(x, y)
        integer, intent(in) :: x, y
        add2i = x + y
        end function add2i

2. Create a position independent object file (foo.o)

gfortran -c -fPIC foo.f95

3. Create a dynamic shared library (libfoo.so)

gfortran -shared foo.o -o libfoo.so

4. Write the following piece of C code that invokes the fortran function (test.c)

#include <stdio.h>
#include <stdlib.h>

extern int add2i_(int *x, int *y);

int main(int argc, char *argv[]){
  int x = 3;
  int y = 5;
  int z = add2i_(&x,&y);

  printf("result is %d\n", z);
}

Note that the you must append an underscore ‘_’ to the name of the Fortran function in the prototype. Moreover, Fortran uses a pass by reference mechanism. Therefore the arguments need to passed as pointers.

5. Compile the C code into an object code (test.o)

gcc -c test.c

6. Link the compiled object file with the Fortran shared library and create an executable (a.out)

gfortran test.o -L/path/to/dll -lfoo -Xlinker -rpath /path/to/dll

5
Feb 11

Accessing a dynamically linked shared library from Perl

1. Write the following piece of code in a C file:

/* foo.sh */
#include "stdio.h"
#include "stdlib.h"

int add(int x, int y){
    return x + y;
}

2. Create a Position Independent Code object file

gcc -fPIC -c foo.c

3. Create a shared library from the object file

gcc -shared foo.o -o libfoo.so

4. Create a C header file with the function prototypes of the shared library

/* libfoo.h */
extern int add(int x, int y);

5. Create a SWIG interface file that includes the header file

/* example.i */
%module example
%{
#include "libfoo.h"
%}
%include "libfoo.h"

6. Run Swig to generate glue code

swig -perl5 example.i

7. Compile glue code (example_wrapper.c) against Perl’s own shared libraries

gcc -c -fPIC example_wrap.c `perl -MExtUtils::Embed -e ccopts`

8. Link compiled glue object against our shared library (libfoo.so) and package it into a new shared library (example.so)

gcc -shared example_wrap.o -L/path/to/dll -lfoo -Xlinker -rpath /path/to/dll -o example.so

9. Write a perl script to use the shared library

use example;
my $result = example::add(3,5);
print "$result\n";

21
Dec 10

Don’t just write comments, tell a story

We all have our ways of writing comments in our code. Some prefer huge blocks of text at the beginning of a source file. Some prefer a paragraph before every chunk of code. Sometime we sprinkles a few one-liners here and there to explain a cryptic regular expression or two. But no matter how we write comments, they always get in our way of coding. That’s why we end up spending very little time documenting. It makes your code longer. Adding new code in between always messes up the comments and then you have to spend some more time realigning comments. Look at the following screenshot and see if any bright ideas come to mind.

Docco Screenshot

Dual-pane source/comment view

The HTML output was generated using a tool called Docco and provides a very clear separation of code from comment.. This little Javascript utility parses out comments from a source file and aligns them next to the syntax-highlighted code using plain old tables. But imagine, what if your IDE let you write your code like this. Imagine a two pane view, the left pane is the code view, and the right pane is the documentation view. For every chunk of code you write, you can move your cursor to the right pane and write documentation for it. Adding or removing lines from the code view automatically updates the position of the comments on the documentation view. So your documentation is always in sync with the code.
Most IDEs today have a way to run a program in “debug mode”. But what about running it in documentation mode ? In this mode, the IDE would automatically set a break-point at every block of comments. You step through the program’s execution and read your documentation as if it were a linear story. Once you have stepped through the entire program, the IDE would dump the entire thread of comments to the console in the order it was traversed. This is your program in pseudo-code. You know you have done a good job at documenting, when the pseudo-code tells a good uninterrupted story. This output is also your debugging log as the story would not make any sense if your logic went wayward.
I don’t know about you, but this would solve a lot of problems I regularly face at work. Every now and then, somebody decides to send me a huge code-base, asking me to add features to it or hunt down a cryptic bug. Naturally, as I am not the author of this code-base its hard for me to know where to start from. Most of the time I am not even sure what the program does. I can see comments sprinkled here and there. Only if I had some idea of what a class is doing, I would understand what the comments mean. The Documentation Mode would give you a temporal view of all the comments in the code. It would give you a context, it would tell you story. We humans are good at listening to stories. We are even better at making out when a story has holes in its plot. Thus this temporal view would be a useful indicator of which parts of the code need more documentation.
In my opinion, we need to move away from a pure writer-source centric view of the IDE to the more reader-documentation kind of view. It would probably require us to agree upon some kind of markup for source files. But hey, its almost 2011, its about time we move away from medieval ways of representing code in text files.

  • Twitter
  • Tumblr
  • Facebook
  • LinkedIn
  • YouTube