I hit upon closures first (well at least I thought so until I knew what they were and realized that I had used them before) when coding in Ruby. Closures are blocks of code that can be passed as arguments to other methods. In this sense they are similar to function pointers in C. But closures are a tad more powerful in that they also extend the scope of variables in the lexical scope of where they are used. Refer http://www.eclipsezone.com/eclipse/forums/t86911.html for a precise definition.
I recently completed a project involving Ruby on Rails. Having worked with Java for the last three years, I could not help but compare it with Java. I was wondering if any of the language and framework features could be implemented in Java and the numerous frameworks based on it. Blocks and closures are impressive language constructs that allow customization and extension of other language constructs (like the looping constructs) and APIs.
Gafter, Gosling et al's proposal to add closures in Java seems to be a good bet. This would put an end to the addition of more new statements like 'for each' that was added in J2SE 5.0.
Am keeping an eye on the numerous forums and blogs abuzz with discussions on Java and Ruby. It's interesting how Ruby and more importantly the Rails framework is causing so much flutter.
Pointer:
http://www.javac.info/closures-v04.html
-Ashish.
Tuesday, December 26, 2006
Wednesday, June 28, 2006
Ruby on Rails
I got hold of this stone when I attended a presentation organized in the geeknight at ThoughtWorks. The presenters (ThoughtWorkers) were highly enthuisiastic about this project that they had just developmed using the Rails framework. I had only vaguely heard about this new opensource framework and had put it aside as another addition to the slurry of web frameworks that are already in use. The claim that it achieves ten times faster development appeared fantastic - a conclusion drawn from one-off occurence! It was only when I attended this presentation that I got to appreciate the beauty of this precious framework (read stone :)) and how it gets near zero turnaround time.
So what is Ruby and what is Rails? And what then is Ruby on Rails!
Ruby is a dynamically typed object oriented programming language inspired by other languages like Perl and Smalltalk. And Rails is an open source web framework developed in Ruby. Within a short period, it has gained in popularity for its reduced development time and higher productivity. It is known to be one of the most well thought-out frameworks in existence today.
Rails’ support for agile web development can be attributed to various features and its guiding principles - Do not Repeat Yourself (DRY) and Convention over Configuration. Database backed enterprise applications developed today have quite a few things in common. A UI component, a controller component a model component, and an ORM layer. Frameworks like Struts, Spring while providing these components, leave the configuration part to the developers. The developers have to do the menial task of building the configurations and the bunch of XMLs that are common in any application. This leads to a copy paste mentality and repeatative code across applications. It is precisely this that Rails tries to eliminate.
Ruby by its very design makes it easy to create domain-specific languages and metaprograms leaving the developers to just focus on the business logic. Also, Rails has its self defined convention for integrating the various components that form part of this full stack framework (ohh yes, its a full stack framework so no need to manage the idiosyncracies of different frameworks at different layers). Thus no more XML configuration files! Talking of the full stack support, Rails has various components that map to the M, V and C. Active Record maps to the model. The programmer is only required to subclass the ActiveRecord: : Base class; and the program by itself determines the table and column details! View is implemented by Embedded Ruby with syntax close to JSP. Controller is taken care of by the Action Pack classes.
What more but new technologies like Ajax and Web Services have been integrated with Rails making it convenient to implement applications requiring their use. Among its other features, good programming practices forming a part of this framework result into easily maintainable code.
All this might sound like I am painting a rosy picture but try it out now... get your hands dirty and you will see that they don't get all that dirty after all :-). Of course RoR can't be without its drawbacks; nevertheless its promising features were convincing enough for me to choose it as the topic of my final year MS dissertation!
Pointers-
http://www.rubyonrails.org/
http://wiki.rubyonrails.com/rails
-Ashish.
So what is Ruby and what is Rails? And what then is Ruby on Rails!
Ruby is a dynamically typed object oriented programming language inspired by other languages like Perl and Smalltalk. And Rails is an open source web framework developed in Ruby. Within a short period, it has gained in popularity for its reduced development time and higher productivity. It is known to be one of the most well thought-out frameworks in existence today.
Rails’ support for agile web development can be attributed to various features and its guiding principles - Do not Repeat Yourself (DRY) and Convention over Configuration. Database backed enterprise applications developed today have quite a few things in common. A UI component, a controller component a model component, and an ORM layer. Frameworks like Struts, Spring while providing these components, leave the configuration part to the developers. The developers have to do the menial task of building the configurations and the bunch of XMLs that are common in any application. This leads to a copy paste mentality and repeatative code across applications. It is precisely this that Rails tries to eliminate.
Ruby by its very design makes it easy to create domain-specific languages and metaprograms leaving the developers to just focus on the business logic. Also, Rails has its self defined convention for integrating the various components that form part of this full stack framework (ohh yes, its a full stack framework so no need to manage the idiosyncracies of different frameworks at different layers). Thus no more XML configuration files! Talking of the full stack support, Rails has various components that map to the M, V and C. Active Record maps to the model. The programmer is only required to subclass the ActiveRecord: : Base class; and the program by itself determines the table and column details! View is implemented by Embedded Ruby with syntax close to JSP. Controller is taken care of by the Action Pack classes.
What more but new technologies like Ajax and Web Services have been integrated with Rails making it convenient to implement applications requiring their use. Among its other features, good programming practices forming a part of this framework result into easily maintainable code.
All this might sound like I am painting a rosy picture but try it out now... get your hands dirty and you will see that they don't get all that dirty after all :-). Of course RoR can't be without its drawbacks; nevertheless its promising features were convincing enough for me to choose it as the topic of my final year MS dissertation!
Pointers-
http://www.rubyonrails.org/
http://wiki.rubyonrails.com/rails
-Ashish.
Thursday, January 19, 2006
Sudoku
Sudoku has become the buzz word around. Small or big, everyone seems to have been enchanted by this apparently simple number game. Like most of us, I stumbled upon this game a few days back in the Times, and have become its avid fan ever since. The only game that had driven me nuts like this before was the Rubik's cube! Basically of Japanese origin (or is it US!) the aim of the game is pretty straight forward. You have to arrange numbers from 1 - 9 in a 9 x 9 sqaure such that each number appears exactly once in every row, column and every 3 x 3 block. [Something similar to Euler's magic quare but not quite same]. It involves no luck, no math, but sheer logic, and there lies the beauty of this game.
Solving it requires patience, and with practice one can crack it in a few minutes. Well, to be frank it's not just the matter of practice, but about applying your mind, and learning with every game - a neat test of your logical skills. Try it out right away - http://www.sudoku.com/ - and you would know what I mean!
For all those programmers out there, this could be a challenging coding problem. Simple as it might seem, this in fact belongs to one of the tuffest class of problems. By that I don't mean that it cannot be solved, but just that it might not be solvable in polynomial time, so to speak. Those with a little background in algorithmics would have guessed that it has non-polynomial complexity. It is actually NP-complete and thus belongs to the league of Knapsack, graph coloring and 8-queens problem! A trivial approach to it would of course be the good old backtracking! Starting with the first blank sqaure, fill it up with a 1, move on to the next blank... continue in a similar fashion, until you break one of the constraints. As soon as you do, backtrack and fill up the last sqaure with the next possible number. Wait for a sufficiently long time and you will eventually have a solution for sure.
There are better approaches. Every blank sqaure can be associated with a list of possible values. This list will be finite and could be set to the universal set [1-9 here] to start with. Now scan the matrix, apply the contraints to each row, column and 3 x 3 block and keep reducing the set of possible values for each blank square until you are left with just one value. This approach would require many scans and updates to the lists before we have a solution. However it can be made faster if we carefully observe the pain points. Those of you who have solved a few sudoku's would be able to relate this approach to how a human mind would solve it. Note how you scan the matrix and you would soon realize that if you scan it for maximally occuring number, the count of subsequent scans would be less. In other words, if you store the frequency of occurence of numbers (currently on board), and scan the matrix for the number with max. frequency, not only would the updates be less, but so would be the required scans. I believe that applying backtracking for sufficiently small sizes of the lists would also be faster. This is so, as we would be saving on the time spent on scanning. Note also, that there's a significant time spent searching for blank squares. This could easily be eliminated by storing references to the neighboring blank squares!
It might interest you that this problem belongs to a class of problems called the Exact Cover problem. Knuth gives an elegant algorithm (which he calls the X algorithm) and an equally elegant implementation approach called Dancing Links (so called because of the way in which the doubly linked lists change links as the solution proceeds). For details, here's Knuth's paper on the Dancing Links solution - http://xxx.lanl.gov/PS_cache/cs/pdf/0011/0011047.pdf
It's implementation in java can be found in this Sudoku solver.
Keep Sudoking!
-Ashish.
Solving it requires patience, and with practice one can crack it in a few minutes. Well, to be frank it's not just the matter of practice, but about applying your mind, and learning with every game - a neat test of your logical skills. Try it out right away - http://www.sudoku.com/ - and you would know what I mean!
For all those programmers out there, this could be a challenging coding problem. Simple as it might seem, this in fact belongs to one of the tuffest class of problems. By that I don't mean that it cannot be solved, but just that it might not be solvable in polynomial time, so to speak. Those with a little background in algorithmics would have guessed that it has non-polynomial complexity. It is actually NP-complete and thus belongs to the league of Knapsack, graph coloring and 8-queens problem! A trivial approach to it would of course be the good old backtracking! Starting with the first blank sqaure, fill it up with a 1, move on to the next blank... continue in a similar fashion, until you break one of the constraints. As soon as you do, backtrack and fill up the last sqaure with the next possible number. Wait for a sufficiently long time and you will eventually have a solution for sure.
There are better approaches. Every blank sqaure can be associated with a list of possible values. This list will be finite and could be set to the universal set [1-9 here] to start with. Now scan the matrix, apply the contraints to each row, column and 3 x 3 block and keep reducing the set of possible values for each blank square until you are left with just one value. This approach would require many scans and updates to the lists before we have a solution. However it can be made faster if we carefully observe the pain points. Those of you who have solved a few sudoku's would be able to relate this approach to how a human mind would solve it. Note how you scan the matrix and you would soon realize that if you scan it for maximally occuring number, the count of subsequent scans would be less. In other words, if you store the frequency of occurence of numbers (currently on board), and scan the matrix for the number with max. frequency, not only would the updates be less, but so would be the required scans. I believe that applying backtracking for sufficiently small sizes of the lists would also be faster. This is so, as we would be saving on the time spent on scanning. Note also, that there's a significant time spent searching for blank squares. This could easily be eliminated by storing references to the neighboring blank squares!
It might interest you that this problem belongs to a class of problems called the Exact Cover problem. Knuth gives an elegant algorithm (which he calls the X algorithm) and an equally elegant implementation approach called Dancing Links (so called because of the way in which the doubly linked lists change links as the solution proceeds). For details, here's Knuth's paper on the Dancing Links solution - http://xxx.lanl.gov/PS_cache/cs/pdf/0011/0011047.pdf
It's implementation in java can be found in this Sudoku solver.
Keep Sudoking!
-Ashish.
Wednesday, January 18, 2006
Escape Analysis
The idea of implementing Escape Analysis in Mustang (J2SE 6) seems to be an impressive bet and finds a mention in this developerworks article -
http://www-128.ibm.com/developerworks/java/library/j-jtp09275.html?ca=dgr-jw22JavaUrbanLegends
Escape analysis refers to the analysis done on a program to determine those dynamically allocated objects and their references that "escape" or are likely to escape the method or thread scope. This has many applications with potential implications on the program performance. The knowledge of objects being bound by the method scope opens up the possibility of allocating them in the method stack frame rather than on the heap as is typically done for any dynamically allocated objects. Dynamic memory allocation (& deallocation) comes at a price. It comes with the associated problems of fragmentation, data locality and overcoming these is costly both in terms of time and space. Talking within the Java perspective, the garbage collector takes care of reclaiming the dead object space, but even the most recent generational copying collectors can "stop-the-world" for significant amount of time. Stack allocation is not only free of these idiosyncrasies but also the deallocation happens implicitly on method return. Moreover, better data locality means that there would be less cache misses.
Knowledge of local objects also gives the compiler/optimizer a chance to get rid of the object altogether in some cases. The link above has a code snippet justifying the same.
If an object does not escape the thread, the overhead associated with its synchronization can be eliminated. This is significant because forgetting to synchronize objects being accessed by multiple threads can pose serious issues like race condition, spurious and unexpected results etc. Compilers and optimizers often reorder instructions for efficient execution. While this is acceptable in a typical sequential execution, this might cause unexpected results in a multithreaded multiprocessor environment. To add to this, the java memory model does little to ensure the data atomicity, visibility and ordering in such cases. And it is not to blame... with new environments coming up every other day, it is next to impossible to ensure correct execution. Needless to say, thread local objects are desirable and anything that can be done to identify them in a multi threaded program is worth the effort.
Okay, so escape analysis seems to be desirable. How do we go about implementing it? The short answer could be - Do it however you like! :)
Basically, what this would require is an understanding of the relationship between the various dynamically allocated objects and references... something similar to what a compiler would do in the dataflow analysis. We need to track the object right from it's inception to how it is accessed in a method to how it gets passed to other methods to whether it would be accessed by other threads until it is reclaimed by GC. There are ample articles to peruse varying in details on escape analysis in general, it's application in Java and various implementation strategies. Here's a pointer -
http://citeseer.ist.psu.edu/choi99escape.html
Whether or not escape analysis is implemented in Mustang is still being debated and you will find many forums dedicated to this topic. But then nothing stops us from delving into the code and contributing to the build!
Happy Coding :)
- Ashish.
http://www-128.ibm.com/developerworks/java/library/j-jtp09275.html?ca=dgr-jw22JavaUrbanLegends
Escape analysis refers to the analysis done on a program to determine those dynamically allocated objects and their references that "escape" or are likely to escape the method or thread scope. This has many applications with potential implications on the program performance. The knowledge of objects being bound by the method scope opens up the possibility of allocating them in the method stack frame rather than on the heap as is typically done for any dynamically allocated objects. Dynamic memory allocation (& deallocation) comes at a price. It comes with the associated problems of fragmentation, data locality and overcoming these is costly both in terms of time and space. Talking within the Java perspective, the garbage collector takes care of reclaiming the dead object space, but even the most recent generational copying collectors can "stop-the-world" for significant amount of time. Stack allocation is not only free of these idiosyncrasies but also the deallocation happens implicitly on method return. Moreover, better data locality means that there would be less cache misses.
Knowledge of local objects also gives the compiler/optimizer a chance to get rid of the object altogether in some cases. The link above has a code snippet justifying the same.
If an object does not escape the thread, the overhead associated with its synchronization can be eliminated. This is significant because forgetting to synchronize objects being accessed by multiple threads can pose serious issues like race condition, spurious and unexpected results etc. Compilers and optimizers often reorder instructions for efficient execution. While this is acceptable in a typical sequential execution, this might cause unexpected results in a multithreaded multiprocessor environment. To add to this, the java memory model does little to ensure the data atomicity, visibility and ordering in such cases. And it is not to blame... with new environments coming up every other day, it is next to impossible to ensure correct execution. Needless to say, thread local objects are desirable and anything that can be done to identify them in a multi threaded program is worth the effort.
Okay, so escape analysis seems to be desirable. How do we go about implementing it? The short answer could be - Do it however you like! :)
Basically, what this would require is an understanding of the relationship between the various dynamically allocated objects and references... something similar to what a compiler would do in the dataflow analysis. We need to track the object right from it's inception to how it is accessed in a method to how it gets passed to other methods to whether it would be accessed by other threads until it is reclaimed by GC. There are ample articles to peruse varying in details on escape analysis in general, it's application in Java and various implementation strategies. Here's a pointer -
http://citeseer.ist.psu.edu/choi99escape.html
Whether or not escape analysis is implemented in Mustang is still being debated and you will find many forums dedicated to this topic. But then nothing stops us from delving into the code and contributing to the build!
Happy Coding :)
- Ashish.
Subscribe to:
Posts (Atom)
