Wednesday, April 17, 2013

Moved to GitHub!

Sorry Blogger, you are not a warm place for a programmer. What is the use of a blog for a programmer if one cannot even share a small snippet of code. Finally, I moved my personal web page to GitHub. Check it out at http://vy.github.io/.

Saturday, March 2, 2013

Vehbi Koç and Influencing the Industrial Advancement of a Country

A couple of weeks ago, I heard one of our family relatives talking about the biography of Vehbi Koç, who started business in a small storefront and raised his legacy to a multi-billion dollar enterprise in Turkey. I had long wanted to read his auto-biography My Life Story: The Autobiography of a Turkish Businessman. But first, I wanted to learn about his life from an objective perspective. For that purpose, I started looking for a website to purchase the Özel Arşivinden Belgeler ve Anılarıyla Vehbi Koç [Vehbi Koç with Documents From His Private Archive and Memories] by Can Dündar, who is a well-known Turkish journalist, columnist and documentarian. Unfortunately, the book was out of order in every bookstore and website I visited. Then I wrote an e-mail to Can Dündar and asked him if does he have any extra copies of the book that he could share with me. He kindly mailed me the books without requesting any fees. Here I would like to express my gratitude to him for his courtesy.

Thanks to the long waiting hours in traffic while going to the work in İstanbul, I have managed reading the books in two weeks. (In the foreword, Can Dündar tells that this is a 3 books series and the last book is still under development.) Due to my previous experiences with other works of Can Dündar, it was no surprise that the work was well organized and composed of (mostly) private documents, writings, and mails stating the events and related developments in a cohesive and expressive manner. Besides the parts directly related with Vehbi Koç, the books shed significant light to the industrial, economical and political evolutions of Turkey at that time. Further, prior to reading the books, I did not know how Vehbi Koç was so influential on the development of Turkey in many aspects, some of which can be listed as introduction of new fundamental laws enabling the presence of holding and charity companies, first car industry, first local hotels in the line of Hilton, marvelous hospital, railway, industry constructions that are still standing up and are well respected in their fields today. In addition, the books mention about the struggles he had, the industrial and political obstacles that are put in front of him by other people, how he always managed to surmount by his honesty and hard working.

All in all, now I see Vehbi Koç as not just a business man, but a pioneer in the advancement of Turkey who contributed many artwork that are ground breaking and exposing new potentials in their fields, even now. While Koç Holding A.Ş. is still one of the top industrial conglomerates in the world, his achievements were ahead of his time and something that, in addition to his own children, even I am proud of.


Edit: Today, I had chance to finish reading My Life Story: The Autobiography of a Turkish Businessman as well. Majority of the content is in line with what was presented in Can Dündar's books.

In the section, where Vehbi Koç mentions about his visit to Japan in 1970, I found a pointer to a journal article series (dating back to 24, 25, 26 March, 1970) that he shares his notes and comments about the visit. I found the articles quite important in terms of understanding the development history of Japan and its comparison with Turkey at that time. But more importantly, it gives hints about the way Vehbi Koç thinks while analyzing a whole new country with an extraordinary cultural, governmental, economical and industrial structure.

I hope others interested in the subject would find them useful as well.

Friday, November 30, 2012

Merging Two Binary Search Trees in O(logn) Space

In a recent coding interview, I was asked to merge two Binary Search Trees (BSTs) without modifying the given trees. This was the first time I was exposed to this question and for an hour or so I tried to come up with a linear time algorithm of O(1) space complexity. The defeat was inevitable. (To tell the truth, if a hint would be given like O(m+n) storage is allowed, I could easily figure out the solution without breaking a sweat.) As usual, I could not sleep that night and scratched dozens of papers to come up with a better solution. But as night passed, I started to realize the fact that the space complexity is lower bounded by the tree height. This blog post is set to keep a cyber-record of this pursuit.

Related Work

You can first start by checking the Google results. But, as usual, I am kind enough to provide you a tl;dr version: In order to merge two BSTs of size m and n nodes, there are a couple of common approaches of fixed O(m+n) processing time and space complexity, some of which are listed as follows.

  • Insert given BSTs into a newly created BST.
  • Create an array of elements of the first BST in sorted order, and use this array to merge the results to a new BST while traversing the second BST.

Further exposure to the higher doses of the problem is available through this and this StackOverflow threads.

On Complexity

You will definitely need an O(m+n) processing complexity to visit each node, that's for sure. But what about O(m+n) space complexity? It means that you need to store one (or both) of the given trees in a vector in order to proceed with the merge. As it will turn out in the following paragraphs, actually space complexity is lower-bounded by the height of the tree, that is, O(h), where h=logn for a balanced tree.

The Trick

In its most basic form, we flatten both trees into two separate vectors. Next, we consume one element at a time from either of the trees with the smallest element. This scheme deserves a figure of its own.

It is certain that we effectively don't need the whole elements of a tree packed into a single vector at once. At each step, what we ask for is the next smallest element. That is, we just need a stream of nodes traversed in-order.

Let's further investigate the possibility of implementing a stream of nodes. In order to consume the elements of a binary search tree in sorted order, we need to traverse the tree in left-center-right node order. Assume that we have below traversal function. (Yes, it is in C++ and I shamelessly used templates.)

template <class T>
void traverse(Node<T>* root, queue<T>& items) {
  if (root) {
    traverse(root->left());
    items.push(root->data());
    traverse(root->right());
  }
}

What if I can suspend the execution at any point in time while pushing the data to a queue? In that case, what would be the maximum possible height of a recursive traverse() call stack? I know you like figures, so I took another photo of the board.

That is, the maximum call stack depth of a traverse() recursion is upper-bounded by the tree height. Coupled with the fact that successive traverse() calls are sufficient to consume the nodes of a tree in sorted order, we should be able to stream the nodes of tree with at most O(logn) node pointers.

Streaming Nodes

Since actual traverse call stack is bounded, we can emulate the recursive traverse using a stack of the nodes traversed so far from the root. The outline of the streaming algorithm is as follows.

The Prestige

Now we can stream a tree in sorted order using at most O(logn) storage. The rest is easy: Stream both trees and merge them while streaming.

The Code

I have implemented a streamer (NodeStream), stream merger (MergeNodeStream), and a vector merger (MergeNodeVector) in C++ and Scala. Code is accessible through this Gist. You can also find implementations of the algorithm in C++ using Boost Coroutines and Haskell written by Remko.

Wednesday, November 28, 2012

Setting up a Scala Development Environment for Intellij IDEA and SBT

Resisting against the Functional Programming Principles in Scala buzz was meaningless. After all, this or that way I know I would be repeating those steps on my own regardless of the presence of such a lecture. To warm up, I looked around for an appropriate development environment for Scala. The last time (~2 years ago) I repeated this same step ended up with a desperate search. Fortunately, reading dozens of blog posts, forum/mailing-list threads, GitHub README's, repeating try-and-fail procedures leaded me to a working setup. To mitigate the friction at least to an extent for new comers, I put up this blog post to make a list of steps in order to setup a working Scala development environment on top of IntelliJ IDEA with SBT integration.

Is there a Scala plugin available for IDEA?

Good news, yes. It is under active development, works way better than its alternatives, has a responsive maintainer and an active community. Plugin lets you create Scala projects, compile/run/debug Scala source files, scripts, and worksheets. Navigation, refactoring, tab-completion, code snippets are included as well. (Note that it is strongly advised to use an EAP version for a smooth experience.)

Is there a quick start guide for IDEA Scala plugin?

Yes, see Getting Started with IntelliJ IDEA Scala Plugin.

How do I manage project dependencies?

While one can setup a Maven/Ivy/Ant configuration for a Scala project, SBT is known to be the de-facto tool for build management throughout the Scala community. (Otherwise, you will need to set explicit scala-compiler and scala-library dependencies in XML mazes.) Fortunately, there is an SBT plugin for IDEA. It offers a console where SBT commands can be entered interactively, and a Before Launch task to delegate project compilation to SBT, as an alternative to the built in IntelliJ Make.

Is there a quick start guide for SBT?

Yes, see Hello, World in SBT documentation.

How can I integrate libraries installed by SBT to IDEA?

At its core, SBT uses Apache Ivy, which has its own nasty ways of dealing with downloaded JARs under ~/.ivy2. Instead of manually defining IDEA module dependencies for each JAR a project uses, lucky for us, there exists an SBT plugin for this purpose: sbt-idea. Basically, sbt-idea enhances SBT with a new task, called gen-idea, which creates IDEA project files with necessary module dependencies induced by SBT. That is,

  1. Add your dependencies to your SBT configuration,
  2. Call sbt update to download/update project dependencies,
  3. Call sbt gen-idea to create IDEA project files,
  4. Open created project from IDEA.

What are the IDEA modules created by sbt-idea?

In addition to below directories, SBT dependencies are added to the IDEA module configuration.

  • Source Folders: src/main/{scala,java,resources}
  • Test Source Folders: src/test/{scala,java,resources}

What about testing?

SBT supports a couple of testing frameworks, i.e., specs2, ScalaCheck, and ScalaTest. See Testing section of the SBT documentation for a detailed discussion.

What about my .gitignore?

Here you go.

/.idea
/.idea_modules
target/

I read enough, gimme the code!

Create a project directory.

$ export PROJECT_DIR=~/scala/ScalaHelloWorld
$ mkdir $PROJECT_DIR

Create $PROJECT_DIR/build.sbt as follows. (In this example, I used ScalaTest framework.)

Create $PROJECT_DIR/project directory and add below lines to $PROJECT_DIR/project/plugins.sbt to add sbt-idea plugin.

Run sbt in $PROJECT_DIR and execute gen-idea task.

$ sbt
[info] Loading project definition from /home/vy/scala/ScalaHelloWorld/project
[info] Updating {file:/home/vy/scala/ScalaHelloWorld/project/}default-70d248...
[info] Resolving org.scala-sbt#precompiled-2_10_0-m7;0.12.1 ...
[info] Done updating.
[info] Set current project to ScalaHelloWorld (in build file:/home/vy/scala/ScalaHelloWorld/)
> gen-idea
[info] Trying to create an Idea module ScalaHelloWorld
[info] Updating {file:/home/vy/scala/ScalaHelloWorld/}default-3005c4...
[info] Resolving org.scalatest#scalatest_2.9.2;1.8 ...
[info] Done updating.
[info] Resolving org.scalatest#scalatest_2.9.2;1.8 ...
[info] Excluding folder target
[info] Created /home/vy/scala/ScalaHelloWorld/.idea/IdeaProject.iml
[info] Created /home/vy/scala/ScalaHelloWorld/.idea
[info] Excluding folder /home/vy/scala/ScalaHelloWorld/target
[info] Created /home/vy/scala/ScalaHelloWorld/.idea_modules/ScalaHelloWorld.iml
[info] Created /home/vy/scala/ScalaHelloWorld/.idea_modules/ScalaHelloWorld-build.iml
>

In src/main/scala/Main.scala, create a main() stub with a testable function in it.

In src/test/scala/MainSuite.scala, create a sample test suite.

Enjoy the rest by either creating your own IDEA run configurations, or manually running tasks within the SBT console. (As a final note, while creating IDEA run configurations, you can use SBT Before Launch task provided by IDEA SBT plugin.)

Sunday, September 30, 2012

Sequential Chaining of Nested Callbacks

Back in the old days of programming, the days we used to have blocking function calls, things were easy: first do this, and then do that, and finally clean things up. While this sequential style of programming has its own advantages in terms of human perception, it imposes certain concurrency related limitations. That is, each expression in a program is supposed to wait for the completion of the execution flow up until the line above, regardless of if it has anything to do with the current expression or not. Asynchronious programs are known to solve this problem of concurrency, (at least, to some extent) with the cost of sacrificing the sequential program flow. At its most basic form, functions are provided interfaces to specify dependencies between each other and hence, independent functions are allowed to execute concurrently. These interfaces are generally provided in the form of callback functions, that is, when f() gets completed do g(), and when g() completes do h(), and so on. The premise of this blog post is to investigate whether it is possible to still preserve the dependency between functions by still allowing the programmer to syntatically structure the program sequentially.

In the context of asynchronious programming, JavaScript is an exceptional example, where almost every functionality in the language is shaped according to asynchronous callbacks, which eventually enforces you to program in a totally top-down callback-oriented style. In this post, I prefered to use CoffeeScript (which is a programming language compiled to JavaScript) to enhance the plain text the explanations.

Ok, enough talk. Let's start with working on a small sequential program snippet.

Simple and intuitive. You just grab the logic behind at first sight: First, connect to the database, and then query the rows of a table, and finally close the connection and return the results. And as a bonus you can catch errors that would occur during this sequence. Here is its asynchronious, callback-driven counterpart:

Um... Not as intiutive as its sequential counterpart. And the nested callback chains expands the code to the right, which makes it harder to understand as well. But, not that bad... with a serious glitch: Orphan exceptions. That is, for instance, who is supposed to catch a connection error exception after db.open completes gracefully and the execution passes over the try-catch block? While code will be get polluted a little bit, this problem can be tackled by returning an error, instead of raising an exception.

Better now, at least in terms of correctness.

So far, we always beforehand knew the callbacks that will be nested into each other. That is, we knew that a simple query will follow just after the database connection gets established. What if we wouldn't? What if the next callback is to be dynamically determined according to a runtime variable? Think about this scenario: You need to query the database multiple times depending on the input passed by the user. A pretty common day-to-day practice. Terrorizing the code with unknown number of nested callbacks would buy us no credits.

On the other hand, forming nested callbacks using a recursive function solves the problem.

I admit that this is not intuitive, also more error-prone. (I also could not be sure if I wrote it right. But anyway, you get the idea.) There must be some other way. Wouldn't it be cute if there would exist some sort of sequencer mechanism that allows me to sequentially chain my nested callbacks?

This Aha! moment helped me to come up with below tiny helper class.

SequentialExecutor helps you to push your functions into an array and executes them in order for you. Specifically, it passes you the pointer to the next function (i.e., next) that is supposed to be executed after current function. So, it is up to you to execute it or not. Here is an example using this cute SequentialExecutor class:

Yes, now we have something! Let's also try to implement the case where the total number of queries are dynamically determined on the run.

Oops! That is not what we were expecting. Database connection is supposed to be closed at the end of the execution flow. Hrm... Can't we enhance SequentialExecutor to label tasks with priorities? Here is the poor man's sequential executor with priority support.

Let's give our new gear, PrioritizedSequentialExecutor, a try.

Mission accomplished! Now we have a fully-fledged sequencer where we can dynamically push tasks with different priorities.

Note that while PrioritizedSequentialExecutor is quite good at doing what it is advertised for, especially compared to the lines of code written, there exists other libraries (e.g., seq, chainsaw, futures, async, windjs, streamlinejs, etc.) with similar flow-control purposes. While you are at it, you might want to check them out too.

Sunday, September 16, 2012

An Authentication Service for AngularJS

I am so tired to form up explanatory, coherent sentences, but at the same time I really like to share a user authentication service that I wrote for AngularJS. Hence, pardon my brevity.

In this example I use RailwayJS with CoffeeScript both at the client- and server-side. (See my previous post on auto-compiling assets with connect-assets.) Here is the scenario: You have assignments.html such that only authenticated users are allowed.

First things first, here is our /config/routes.coffee:

Then we implement our controller /app/controllers/home_controller.coffee as follows.

Note that the authenticate used in login action handler is meant to be provided by you.

Later, we write /app/views/home/index.ejs to fire up AngularJS:

We first start by implementing app.js of AngularJS in /assets/js/app.coffee:

The extra bit for listening on $rootScope for $routeChangeStart is to check access to authentication required pages.

After app.js, we implement /assets/js/controllers.coffee:

For each controller, we implement a view, that is, /public/partials/login.html and /public/partials/assignments.html:

And here goes the magic, /assets/js/services.coffee:

Hope it works for you as well.

Auto-Compiling Assets with connect-assets

I have been using RailwayJS for a couple of weeks with great satisfaction and joy. Its built-in support for CoffeeScript files is fantastic. That being said, like a majority of other NodeJS web frameworks (e.g. Geddy, Tower.js, SocketStream, FlatIron) it doesn't provide a way to ship client-side CoffeeScript files. (In this context, Meteor represents a notable exception, where it is capable of handling CoffeeScript files both at the server- and client-side.)

To establish a complete CoffeeScript experience both at the server- and client-side, one can use connect-assets by Trevor Burnham to auto-compile assets (i.e., CoffeeScript, Stylus, LESS files) on-the-fly. For this purpose, you just need to (1) add a app.use require('connect-assets')() line to your environment.coffee, (2) create js and css folders under assets directory, and you are ready to go.

One minor glitch that you need to pay attention is, while using connect-assets, you must include asset files using accessor functions ‐ js() and css() ‐ provided by connect-assets. These functions in addition to generating necessary <script src="..."></script> tag, also register the file into the asset processor service. connect-assets auto-compiles an asset the first time it is called and caches the produced output in memory; later calls will be served from the cache. (It also provides options to write produced outputs to disk and watch file changes.) For instance, say you want to use /assets/js/main.coffee in /app/views/main/index.ejs file. For this purpose, you need to add <%- js('main') %> into your view for enabling connect-assets serving your main.coffee file.

As a final note, since connect-assets is a Connect plugin, you should be able to run it on any other web framework that runs on Connect or ExpressJS.