Tuesday, June 25, 2013

I recently submitted code for a job interview. Evaluation was on object orientation, test driven design, elegance, and production-like aspects. Solution to the core problem statement was in my opinion not the main evaluation criteria. However, I spent more time designing a nice solution. I submitted the code in Python, but my solution was influenced more by Haskell.

Problem statement was to convert between roman numerals, arabic numerals and another custom counting scheme.

The word algorithm has its origin in the technique for finding the value of a arabic numeral (more appropriately hindu arabic numerals). It is simple and elegant. "Start with zero. Consume individual numerals from right to left. Keep adding increasing powers of 10 times the individual number to the current count." Effectively:

"4221" = 1 + 2*10^1 + 2*10^2 + 4*10^3 = 1 + 20 + 200 + 4000 = 4221

In my opinion, it is NOT surprising that one of the earliest acknowledged algorithm is actually a fold in disguise (or reduce in python).

The algorithm for computing the value of a roman numeral on the other hand is more involved. Best explained in wikipedia.

There are many ways to convert roman to arabic numerals. My implementation was a parser combinator, designed ground up in python. Not industrial grade, never the less elegant. Here is a sketch.

At the lowest level are basic parser combinators. A parser by the way is a function which takes a string and returns a pair (value, unconsumed_string). Basic combinators which return such parsers are:

char c f - consume a character if equal to c, returning f(c) and rest of the string. otherwise return fail and the whole string unconsumed

empty f - always return f() and the whole string unconsumed 

and combiner p1 p2 - do p1, on success do p2 on rest of string, combine outputs with combiner. failure at any step returns fail and the whole string unconsumed

optional_upto combiner count p - apply p, count number of times. combine outputs with combiner

or - similar to "and" using a short circuited implementation

zero p f - is an or of p and empty(f())

ands p1 p2 p3 p4 ... -  similar to "and"

ors - equivalent to "ands" for "or"

Next level above are symbol combinators. Pretty simple to setup using the char combinator.

I = char( 'I' , id(1))

V = char( 'V', id(5))

Combinators for units follow.

IX = and(minus, I, X)

IV = and(minus, I, V)

Is = and(plus, I, optional_upto(plus, 2, I)    # an I followed by 2 optional I's

VIs = and(plus, V, optional_upto(plus, 3, I)  # a V followed by 3 options I's

units is an "ors" of the above in order

Implementing this using parser combinators created a mini DSL. Once setup, id, minus, and plus functions can either calculate the value, or produce the abstract syntax tree. With a bit more effort in meta-programming,  and, or can be implemented as overloaded operators using &, |, to make the code look even more DSLish.

Combinators for tens, hundreds, and thousands follow a similar pattern. Finally all these are threaded to produce the final result.

roman = ands( plus, zero(thousands), zero(hundreds), zero(tens), zero(units))

This is again a fold, albeit with more complications. NOT a surprise.

Obvious inefficiencies exist in the implementation. On seeing I, the parser looks for an X. Not finding X it discards the whole parse and again looks for I followed by a V.  Another aspect is that the basic combinators are not minimal. I did not optimize as verbose dode was preferred, given the context. I also wanted the code to resemble a recursive descent parser, to help me explain the code during the interview.



**Actual code not posted, as this was for submission @ thoughtworks. Did I make it? Yes, but rejected as the offer was not one I couldn't refuse.

Friday, December 11, 2009

Clojure is a multi-paradigm language. It is mix of imperative, functional and object-oriented programming. The parser, compiler/interpreter and runtime uses the Java Virtual Machine. Let me not get into any more details. The Clojure site is the best reference.

Functional programming finds its best implementation in the homoiconic language family. Clojure being a LISP (there is the LISP family and dialects like Scheme, Common Lisp, now Clojure) is homoiconic. The syntax in the LISP world is based on s-exprs; for the unitiated and haters it means the program looks like a big list of matching curly braces. Unlike Scheme, which strives towards minimalism, Clojure embraces expressionism. Traditional LISPs provide data structures as macros, functions or libraries. Clojure provides all this and in addition wraps them in syntactic sugar. I am biased towards Scheme's minimalism, but that is just me, and my fellow ivory tower academic hard-heads. This is not a shortcoming of Clojure. The goal of Clojure was to provide practical constructs for data structures and not just s-exprs.

There are however, a couple of idiosyncracies in Clojure which are distracting. Some of them create the feeling that "there is something wrong". Similar to Trinity fearing Neo's deja-vu on seeing the cat. I believe that these idiosyncracies need to be ironed out, maybe even eliminated. That will make the language mature. More important, it will make Clojure accepted outside of its niche community.

The attitude of the language and to a certain extent the language community is to be a better Java with functional forms. In this respect one will not appreciate Clojure for being a better LISP. Instead Clojure tries to be a better Java with LISP syntax. The documentation, the Clojure book (Programming Clojure) are never aimed towards a developer who wants to program. Instead it is addressed towards specifically Java developers, selling them the features of Clojure which is better when compared to Java (though the book says it can be used by experienced Python, Ruby, etc developers). Yes, this will help in attracting people who are Java cats who are searching for an ideal functional programming language. No, this will not make the language popular. If you look at Python or Ruby which also have Java based environments, the first class citizen is the language of Python or Ruby itself. Java is for performance and its large library. In Clojure it sometimes feels the other way around. Please note that I am not complaning about the language design here. I point at the attitude and the stance of the community.

Owing to the above attitude, many of the language constructs exist so that one can do what Java cannot do. The language introduces constructs because it cannot be achieved in the Java VM. For e.g. tail calls cannot be optimized in the Java, so we have recur and trampoline constructs. Obviously us Java developers will buy into it. But functional developers will never buy into that. Any programming language should have its own identity. In Clojure this identity is lost, because practical implementation difficulties are put ahead of clean design.

There is the PERL philosophy of "There are many ways to do it". And there is the Python philosophy of "There are many ways to do it, but there is one right idiom (pythonic)". Clojure is a mixed bag. There are many constructs - functions and macros - which achieve the same thing and you are encouraged to do; there you have the PERLish influence. However the functional programming principles of Clojure state that you should avoid direct recursion, or recur in place of sequence api; which is a pythonic attidute. Definitely the language community should have a stronger philosophy of their own.

I have read elsewhere Rich Hickey's comments on SICP. He says

And I don't think the core of Clojure is appreciably bigger than
Scheme's. What do Schemers think?

A lot of Schemers (including me) will have to spend a lot of time evaluating Clojure before we come to that conclusion. If the Clojure community can re-arrange their thoughts, as well as make those thoughts explicit, maybe then Clojure will be appreciated as being minimalist. Until then someone looking at the language will come away with the feeling that it has a very large core. That will definitely drive people away. (BTW Rich the only reason I was able to understand Clojure is because I know Scheme. I think others will agree.)

In summary if Clojure

• Tries to break away from being a better Java
• Establishes its own identity in the design of the language
• Improves its documentation, so that it can talk to everyone and not just seasoned Java developers
• Popularises the scaffold on which the language is designed - a small core, special forms, macros, the rich Clojure library, the Java interop and using Java libraries

it will definitely go mainstream. Not just Java developers looking for an alternate language, but Python/PERL/Ruby programmers, the newbies, and finally the enterprise developers/architects will give it a serious look, discover its merits and adopt it. I for one would surely be thrilled with this new LISP with the vast library of Java.

Disclaimer:
I am not a clojure developer. I am a programming language enthusiast and have learnt multiple languages with different programming paradigms; just for the fun of it. Programming languages which I know are Java, Python, Scheme, okie-dokie PERL, C# which for me is Java with a different library and idiom, C, C++ including the (in)famous STL, COBOL & FORTRAN purely because it was in my syllabus, Javascript both in its prototype and functional forms. I have tried to be unbiased; if it exists it might be due to my stronger background in Java, Python, Scheme.

I have reserved my analysis to the language and the language "attitude". I might post more on the libraries, concurrency, macros etc once I trudge through them.

Friday, July 17, 2009

I am reading The language instinct from Steven Pinker. Some of the examples he has are very familiar to compiler construction.

Shift/Reduce conflictis a conflict in LALR grammars (most programming languages) where in the parser has to decide between shifting a new token for a rule or reducing the rule. Quoting Stephen C. Johnson from the YACC paper

As an example of the power of disambiguating rules, consider a fragment from a programming language involving an ``if-then-else'' construction:

stat  :  IF  '('  cond  ')'  stat
|  IF  '(' cond ')'  stat  ELSE  stat ;

These two rules form an ambiguous construction, since input of the form

IF  ( C1 )  IF  ( C2 )  S1 ELSE  S2

can be structured according to these rules in two ways:

IF  ( C1 )  {
IF  ( C2 )  S1
}
ELSE S2

or

IF  ( C1 )  {
IF  ( C2 )  S1
ELSE  S2
}

The second interpretation is the one given in most programming languages having this construct.

That is during a shift/reduce conflict, LALR parsers chose shift over reduce, implying that clauses are always associated with the innermost clause.

On the human side of the equation, Steven Pinker talks about Chomsky's classic illustration of turning a declarative sentence into a question

A unicorn is in the garden
-> Is a unicorn    in the garden?

This is done by taking the auxiliary "is" and moving it. However, this is not a simple move as illustrated in the below case

A unicorn that is eating a flower is in the garden
->    Is a unicorn that is eating a flower    in the garden?

Chomsky argues that our mental algorithm does not pick words by their linear positions, but does so by grouping it into phrases, implying that during a conflict the mind chooses entire units together.

Does this mean that the designers of LALR were goaded by their mintal algorithm to chose shift instead of reduce? Or does this mean that language is an algorithm (albeit more powerful than any parser) that is wired into our brain - and evolution chose shift over reduce because that is the easier one to implement?

Wednesday, May 27, 2009

These days I have been thinking of why there is no framework which helps me develop a web application in its “natural state of being”.

Let me explain the natural state of being for a web application. First the browser is no more just a html display engine. Instead the browser has emerged to include user interaction (read javascript) and html display engine. No more is it taboo to have javascript in web applications. In fact web applications say good bye to anyone who has not turned on javascript. Even the html display features have upped the ante. No more table wrangling and poor UI design. The DOM has matured and CSS can do wonders. Grid based CSS frameworks have put web design on par (at least notionally) with print based design.

What about web frameworks? Have they acknowledged the fact that html and javascript have matured. That, it is no more the forgotten child in the family of enterprise frameworks from Java and .NET or web oriented frameworks from LAMP, with P fulfilled by Python, PHP, Ruby! I would say yes and no. Yes, because many frameworks natively support and integrate with a javascript framework, or provide components based UI, etc. But mainly No, because all the action is in the rear (no pun intended). Html generation, UI interaction is all in the web application logic which is never executed by the browser but executed by the server. You might point out GWT and its ilk, but I have a mixed feeling about GWT. I like the concept and architecture of GWT. It is one of the rare breeds which acknowledge the power of the browser. However I don’t like the fact that everything is java.

So what do I want from a new age web app framework? Here is my wish list

1. Allow development of html in ahem html. Yes, no fancy wrappers frameworks. Plain html is good enough.
2. Allow layout definition, color and fonts in CSS. Web designers like CSS. There are javascript frameworks which do layout management, CSS, etc, but doing it is CSS's raison d’être , and does a good job.
3. Allow development of user interaction using javascript. User interaction includes visual interaction like drag-drop, open-close, etc. It should also include functional user interaction (which we come to next).
4. Allow integration of functional user interaction with the server using javascript. I don’t want a component tree to be manipulated on the server. The UI is on the browser, let the browser take care of handing UI.
5. Allow development of the html, css and js as we saw in 1,2,3 in an easy to understand manner. Maybe go back to VB, Swing or even Small talk. Designing a UI and interaction for the web should be no different from designing it for a desktop application. I shudder at the thought of developing a tree table control using only server logic.
6. Allow development of business logic on the server using insert java, python, ruby, etc. No brainer. Javascript from the browser requests something from the server, and the server dispatches it.
7. Have features which can glue the disconnected html, js, css and backend server. For e.g. login state management, history, etc.

One might think that my wish list is a manifestation of NIH or even Can your language/framework do this syndrome. It is not. A web application is created by several thinking hats. First is the graphic designer hat where you do not care about the interaction or functionality. Second is the user interaction designer hat where your intent is to do both visual interaction and functional interaction. Third is the business logic designer hat where your intent is to fulfill business requests in the form of an API. My wish list is to

• Let each hat use the language best suited for the purpose. Do not force a new language and framework unless it is a DSL.
• Let simple things be simple and complex things possible.
• A web applications’ UI is on the browser. So, let the VC (capital C) of MVC be on the browser and let Mc (a small C) be on the server.

Should we build a new framework or stack to support such kind of development? I don’t think so. There are tons of libraries. A nifty way to glue them is what we need. We need to do what Maven did to Ant build scripts (I know I will be flamed for that). Eliminate ctrl-c ctrl-v and introduce macro'ish way of doing things.

Html and CSS do not need anything new. CSS frameworks are the new kids on the block, but I don’t know much about graphic design to comment on them.

jQuery and other DOM manipulation libraries can provide the user interaction we want. Yes, DOM manipulation libraries have a lot more features; they can create the whole html, CSS etc. But like I said let html be done in html, CSS in CSS.

Functionally user interaction is fulfilled by Ajax modules in DOM manipulation libraries.I feel that Ajax API do not have good semantics. For e.g. in relational theory and SQL, a SELECT does projection, FROM does joins and WHERE does selection (sic!). Something akin to that is needed in Ajax APIs (I hope I explained what I mean). Also, I don’t think you need to hide the fact that the server is remote. EJB did that for many years and then introduced local and remote interfaces. Programming to an interface and not an implementation is always better.

Server frameworks are dime a dozen. A simple one which functions like an API sending only data in the form of json, xml, yaml, is more than sufficient. Almost all the frameworks qualify, but they need to be stripped of all the excess fat.

The biggest job is creating a neat pattern which can glue all these different components, provide necessary and sufficient (i.e. orthogonal) helpers, provide a good set of defaults and extension points. I consider documentation to be as important as the framework. Documentation should teach usage of the framework and provide details on the design of the framework.

I love programming. I hope that someone (or me) develops something which brings the same joy to web programming.

Wednesday, March 29, 2006

An extended abstract that I submitted for a worshop in my company (www.infosys.com)

Relevancy ranking is a very important part of any search engine. Web search engines rank data using factors like natural language processing, popularity page ranks etc. Enterprise data generally being structured or semi-structured benefits immensely by using taxonomy categorization for ranking.

Traditionally categorization of data under various taxonomies is done by using meta-data. Data is associated with meta-data during data creation, with some flexibility to change the meta-data during the lifetime of the data. This approach has some difficulties. Categorization of data has to be done by an elite group - elite in the field of categorization & taxonomy as well as being subject matter experts - like authors, editors and librarians. This process is costly and also a bottleneck when the amount of data is huge and semi-structured. Sometimes the pre-defined set of taxonomies might not be sufficient. Adding/editing taxonomies either due to emergence of new kind of data or due to user feedback is fraught with difficulties.

One of the approaches to the above issues is the application of inversion of control to the above process. In the traditional process authors, librarians, editors i.e. produces categorize data. An inversion of control is to let readers, reviewers, users i.e. consumers categorize data by tagging taxonomy to the data. As the number of consumers of data are generally more than the number of producers this inversion will lead to better and relevant taxonomical categorization, at minimal cost and with no apparent bottlenecks. Taxonomy tags can be fluid enough to accomodate user preferences; this will ensure easy addition and updation of taxonomies and categorization. Finally, human intelligence being the best form of intelligence; this process will ensure that the collective intelligence of the consumers of the data is put to the task of taxonomy categorization - a very difficult task to achieve using natural language processing and artificial intelligence techniques.

The above can be achieved by following an approach similar to social networking web-sites like Del.icio.us, flickr, reddit, slashdot etc. These sites let users tag data and use these tags as a factor in relevancy ranking. Applying this technique - an enterprise can build a taxonomy database. This database not only stores the taxonomy, it also stores bi-directional mapping between taxonomy & data. Search results use the taxonomy database as a factor in relevancy ranking. Directory services uses the taxonomy database as a factor in browsing. Everytime a relevant document is choosen in a search or a directory browse result, the search engine provides the consumer a way to tag the data using relevant taxonomies, either existing or new. This information is added to the taxonomy database. During the lifetime of a document its taxonomical categorization will mature with each view and tagging combination. This will help in pushing the rank of the document up or down in a search result or directory browse based on its tagged taxonomies. The whole process acts in an endless loop.

The pros/cons as well as the cost/benefit of such an approach should be considered before implementation. The authors feel that this inversion of control in the process of taxonomy categorization will help enterprise search engines and prove to be beneficial in the long run

Thursday, March 23, 2006

Strong AI - The belief that a computational engine can show intelligence. A stronger form of belief is that the human mind is also a computation engine. Mathematically intelligence is equivalent to church-turning machine!!!

Weak AI - The belief that intelligence can be studied by the aid of a computational engine. Computation can help in also simulating intelligence. It does not believe in a computational engine showing true/indepent intelligence. The most famous theorem being Godel's theorem.

Traditional web search - People were trying to build intelligence into the search engine. Search engine had bulky logic to rank search results. This logic had to be AI.

Google Search - Identified that search ranking cannot be solved only AI. Instead of using AI for search ranking, they used social behaviour. Social measure of something being popular is based on how many people know about it. Google used this for their PageRank algorithm. Of course a lot of AI concepts were used, but not as the backbone. Inversion of Control!!

Taxonomy - The earlier trend was to categorize information using automation. Build natural language processing to categorize knowledge.

Tags - The current trend used in categorizing information. It does not use natural language processing, but uses social behaviour. You have a photo, you know about a web page - go ahead and tag it. Tags act like categories. Most of the people will use the same tags. Lo, you have your cateogory. Most popular being Flickr, del.ic.ious, where you tag photos, links.
Inversion of Control!!

Music Player - All music players arrange music either by directory, artist or genre. What if I could tag songs based on my mood, my category? That would be great!!