Wednesday, August 26, 2009
Modeling a Diff tool…
Ok, here's the problem:
"Given two array of characters (in real world situations, one would be modified version of the other), determine the set of substrings that are "additions", or "changes" or "deletes" w.r.t the first array".
Example: If the first array is “To understand the solution you must understand the Prototype” and the second one “To really understand the solution, you should see the prototype”. The analysis result of the second array w.r.t first would be (for simplicity, I’ve taken a word break view) :
| To - Common really - Addition understand - Common the - Common solution, - Update (comma) you - Common should - Update (Previously: must) see - Update (Previously: understand) the - Common prototype - Update (first letter casing changed) |
The problem is very well known in the computer algorithm world & there are algorithms that solves it in linear time [ O(n) ]. You could use these algorithms in making "Diff" tools (example - WinMerge ).
What you see above is a very simple model for the Diff operation. For any client (web, desktop or otherwise … as long as they can talk to an implementation of above model) the starting point is the DiffTool class. Set the Base and Target. One can easily map a string , file content, serialized objects or memory segments to a byte array representation. I had another reason to choose byte array over stream, the reason being I had to expose the DiffTool as a web-service, hence clients would be remote to this service. Rest of the design of this model is pretty straightforward … client calls the Process method & gets DiffResult instance which has collection instance for commons, additions, deletes and updates. The All collection in the DiffResult contains the ordered (top-down) list of all Diffs as they appear.
Saturday, August 22, 2009
Complexity In Simplicity Of Real World... A Programmer's View
Real world is so simple and yet so complex. We experience it daily without even realizing the complexity in realizing a world as simple as the one we live in. I was born and brought up in Hindu family, one thing we have been taught from beginning is that there is more to the world than what we see and live. Add to this the years of computer programming I've been doing (hmm... close to 19 yrs now since i touched the keyboard the first time), and you'll get a complicated mix of oriental and western thinking. Or is it simple but complex ! Like the Fractal curves, so amazing & may be perceived as complex (to the uninitiated) but yet so simple in its underlying principles.
Note: What you read below is just a record of my random thoughts. It'll be foolish to assume that these are my claims on how things work.... because frankly, I do not think there is an easy answer (or for that matter an single / absolute answer) to any of real world problems.
The UI + Model View - Look Beyond What You See.
In programming world, what the end user clicks, keys-in or views; are just the representation layer ,popularly known as the UI layer in the programming world. If you were to separate out the UI layer from an application, you'll see things but your clicks (or key inputs) will no longer bring the same results. Does this remind you of a dead body ? What you see may qualify the body to be of certain species, but no matter what you do (pinch, kick, talk ...) it wont react. The UI layer is important from the end user's interaction perspective, but its not sufficient by itself. There are different application architectures, but lets say we simplify them to a UI + Model architecture (in real implementation you'll need other modules like controller, and service manager). The Model is what your computer's processor works against. The Model drives the different stages & life cycle of the application. In sort, the Model "makes it happen for you". Ideally, a Model should be self-sufficient, it has all the necessary tools & knowledge to achieve its purpose. Also, the Model exposes certain channels ( APIs / methods and properties as we call them) for external clients (like the UI manager) to invoke different behaviors. These invocations usually results in change in the state of the Model which UI manger is made aware of & eventually results in change in UI. In a computer application, once you tie together a UI with a Model, the application comes to life ! It'll start responding to different inputs from end users.
Did God Create All The Species In This World ?
It is simple (and easy) to think that God is the creator of everything ... then what about evolution ? Does God let species evolve within certain set of rules and guidelines or He always intervenes & decide which new species should arrive & which ones should be gone ? Did God create only the first snap of the world with life sustaining infrastructure and few billions of amoeba & laid out the rules for cell combination, energy conservation etc.. etc... from there own the species were on their own ! Lets keep aside these question & take up a computer programming problem. The problem is similar to God's task of creating a universe, for simplicity sake lets say creation of Earth to start with. So, the problem is to write a program that simulates Earth (starting some point in time) & provide mechanisms for life to sustain, grow and evolve. Isn't this a daunting task ! God had a totally different level of challenge (Space, Time, Genes etc.) Luckily we have to do it in the virtual world of computers :). The world of Artificial Intelligence has progressed a lot [ofcourse no way close to what Nature can do ! ... but we humans made some humble progress :) ] & such simulation programs is not far fetched to be true. Here are few options:
Note: What you read below is just a record of my random thoughts. It'll be foolish to assume that these are my claims on how things work.... because frankly, I do not think there is an easy answer (or for that matter an single / absolute answer) to any of real world problems.
The UI + Model View - Look Beyond What You See.
In programming world, what the end user clicks, keys-in or views; are just the representation layer ,popularly known as the UI layer in the programming world. If you were to separate out the UI layer from an application, you'll see things but your clicks (or key inputs) will no longer bring the same results. Does this remind you of a dead body ? What you see may qualify the body to be of certain species, but no matter what you do (pinch, kick, talk ...) it wont react. The UI layer is important from the end user's interaction perspective, but its not sufficient by itself. There are different application architectures, but lets say we simplify them to a UI + Model architecture (in real implementation you'll need other modules like controller, and service manager). The Model is what your computer's processor works against. The Model drives the different stages & life cycle of the application. In sort, the Model "makes it happen for you". Ideally, a Model should be self-sufficient, it has all the necessary tools & knowledge to achieve its purpose. Also, the Model exposes certain channels ( APIs / methods and properties as we call them) for external clients (like the UI manager) to invoke different behaviors. These invocations usually results in change in the state of the Model which UI manger is made aware of & eventually results in change in UI. In a computer application, once you tie together a UI with a Model, the application comes to life ! It'll start responding to different inputs from end users.
Did God Create All The Species In This World ?
It is simple (and easy) to think that God is the creator of everything ... then what about evolution ? Does God let species evolve within certain set of rules and guidelines or He always intervenes & decide which new species should arrive & which ones should be gone ? Did God create only the first snap of the world with life sustaining infrastructure and few billions of amoeba & laid out the rules for cell combination, energy conservation etc.. etc... from there own the species were on their own ! Lets keep aside these question & take up a computer programming problem. The problem is similar to God's task of creating a universe, for simplicity sake lets say creation of Earth to start with. So, the problem is to write a program that simulates Earth (starting some point in time) & provide mechanisms for life to sustain, grow and evolve. Isn't this a daunting task ! God had a totally different level of challenge (Space, Time, Genes etc.) Luckily we have to do it in the virtual world of computers :). The world of Artificial Intelligence has progressed a lot [ofcourse no way close to what Nature can do ! ... but we humans made some humble progress :) ] & such simulation programs is not far fetched to be true. Here are few options:
- Mix of AI and Object Oriented Programming - Have a Entity definition model, evolution model (rules against how Entities can Create new Entities, Inheritance rules), Life/Survival rules. Attach a learning mechanism to each Entity (Genetic Algorithms !) ... that should be a good place to start with. Sounds difficult ? For the ones initiated in AI & OOPS, its not impossible. Ever played the game of Age of Empires :), assume the program we are talking about is similar, only that it runs autonomously without any players.
- Mathematical Models - An interesting model is of Conway's Game Of Life on Cellular Automation. You start with a initial state & the program takes on there ... you'll see cells combining, dying of hunger, splitting etc... all based on simple set of 4 rules !!!
Thursday, August 6, 2009
On Parsers & Turtle Graphics
Sometime back I took a session on Parser and Language development. It has become like a custom to talk about a math expression parser (simple operations like add, minus etc.) as an example of a simple Grammar. I wanted to deviate & demonstrate Parser development beyond simple expressions.
So, what did I talk about ? … a very interesting stuff that I’ve been working last two-three months. A parser to extract information from unstructured document. The interesting thing is that you can apply grammar based rules to almost all aspect of real life problems. With the advent many free Parser development tools, it has become very easy to write grammar and verify its effect. But lets keep the document parse aside and return back to an interesting question one of my audience asked -- “Can we have an example which is more complex than simple math expression but simpler than the document parser you talked about ?“
Of-course there wasn’t enough time to actually come up with a demo, but we talked about a simple language that facilitate Turtle Graphics based image drawing, which I implemented later. Coupled it up with L-Fractal based string manipulation drawing algorithm & we had a very solid example in-place. And its fun to see how simple strings can do so much to drawing … and some of the L-fractal curves are just breath-taking.
Subscribe to Posts [Atom]
