Monday, November 7, 2011

Groovy Algorithms: Shunting Yard

Groovy's sugary syntax makes coding algorithms -- dare I say it -- fun.  The shunting yard algorithm, invented by Dutch computer scientist Edsger Dijkstra, is used to parse mathematical expressions.  You might have picked up on this already, but computers and people think differently.  We commonly use infix notation to write mathematical expressions.  It is what you learned in school.  For example: "3 * (2 + 3)".  Makes sense to you, but it is inefficient for a computer to process.  Things like operator precedent and nested parenthesis make infix rather messy.  A more efficient format is postfix or Reverse Polish notation.  In postfix, the operands are listed first, and then the operator.  For example: "2 3 + 3 *".  This eliminates the need for parenthesis, and allows you to calculate the expression using just a single stack to hold operands and intermediate results.  Why didn't we learn this in school?  I don't know.  Why aren't we using the metric system yet?  Why doesn't Siri on my iPhone understand anything I say even though it works great in the commericals?  Life's little mysteries.  Back to shunting yard.  Here is my Groovy implementation of it.

The main class is ExpressionSolver.  The computePostfix method (line 7) shows how easy it is to calculate a postfix expression with a single stack and single pass through the tokens in the expression.  It delegates the work of converting from infix to postfix to the appropriately named ShuntingYardAlgorithm class (line 21).

1:  package org.jadcon.expression  
2:  def infixExpression = '5.5 + ((6 + 2) * 4) - -3 * 1.5'  
3:  def postfixExpression = '5.5 6 2 + 4 * -3 1.5 * - +'  
4:  def expectedResult = 42  
5:  assert computePostfix(postfixExpression) == expectedResult   
6:  assert computeInfix(infixExpression) == expectedResult  
7:  def computePostfix(postfixExpression) {  
8:       def stack = []  
9:       postfixExpression.split().each { token ->  
10:            if (token.isNumber()) {  
11:                 stack.add(token)  
12:            } else {  
13:                 def b = stack.pop().toBigDecimal()  
14:                 def a = stack.pop().toBigDecimal()  
15:                 stack.add(Operator.valueFrom(token).calculate(a, b))  
16:            }  
17:       }  
18:       stack.pop()  
19:  }  
20:  def computeInfix(infixExpression) {  
21:       computePostfix(ShuntingYardAlgorithm.convertToPostfix(infixExpression))  
22:  }  

The ShuntingYardAlgorithm class coverts an expression from infix to postfix.  It requires two stacks: an output stack and a working stack.  The main logic is in the processToken method (line 14) which loops through each token.  Operands go directly on the output stack.  Operators and parenthesis are placed on the working stack to get correctly ordered when placed on the output stack.

1:  package org.jadcon.expression  
2:  class ShuntingYardAlgorithm {  
3:       def static convertToPostfix(infixExpression) {  
4:            def output = []  
5:            def stack = []  
6:            evenSpaceAroundParens(infixExpression).split().each { token ->  
7:                 processToken(token, output, stack)  
8:            }  
9:            while (!stack.isEmpty()) {  
10:                 output.add stack.pop()  
11:            }  
12:            output.join(' ')  
13:       }  
14:       def static processToken(token, output, stack) {  
15:            if (token.isNumber()) {  
16:                 output.add token  
17:            } else {  
18:                 switch (token) {                           
19:                      case "(":  
20:                           stack.add token  
21:                           break  
22:                      case ")":  
23:                           while (stack.last() != "(") {  
24:                                output.add stack.pop()  
25:                           }  
26:                           stack.pop() // pop the left paren and ignore it  
27:                           break  
28:                      default:  
29:                           def operator = Operator.valueFrom(token)  
30:                           while (!stack.isEmpty() &&  
31:                                     stack.last().is(Operator) &&  
32:                                     operator <= stack.last()) {  
33:                                output.add stack.pop()  
34:                           }  
35:                           stack.add operator  
36:                 }  
37:            }  
38:       }  
39:       def static evenSpaceAroundParens(string) {  
40:            def output = []  
41:            string.each { letter ->  
42:                 if (!output.isEmpty() && letter != ' ') {  
43:                      def last = output.last()  
44:                      if (isParen(letter) && last != ' ') {  
45:                           output.add ' '  
46:                      } else if (isParen(last)) {   
47:                           output.add ' '  
48:                      }  
49:                 }  
50:                 output.add letter  
51:            }  
52:            output.join()  
53:       }  
54:       def static isParen(letter) {  
55:            letter == '(' || letter == ')'  
56:       }  
57:  }  

The final class is Operator which is an enumeration of operators.  Groovy makes this code pretty tight using closures.  Even threw in a spaceship comparison operator for good measure (line 24).

1:  package org.jadcon.expression  
2:  enum Operator {  
3:       PLUS('+', 0, { a, b -> a + b }),   
4:       MINUS('-', 0, { a, b -> a - b }),   
5:       MULTIPLY('*', 1, { a, b -> a * b }),   
6:       DIVIDE('/', 1, { a, b -> a / b })  
7:       String value  
8:       int precedence  
9:       Closure calculate  
10:       private Operator(String value, int precedence, Closure calculate) {  
11:            this.value = value  
12:            this.precedence = precedence  
13:            this.calculate = calculate  
14:       }  
15:       def static valueFrom(string) {  
16:            for (operator in Operator.values()) {  
17:                 if (operator.value == string) {  
18:                      return operator  
19:                 }  
20:            }  
21:            throw new IllegalArgumentException("invalid operator ${string}")  
22:       }  
23:       def int compareTo(other) {  
24:            precedence <=> other.precedence       
25:       }  
26:       def String toString() {  
27:            value  
28:       }  
29:  }  

Coding the shunting yard algorithm was fun exercise in Groovyness.

Wednesday, October 26, 2011

Spring Roo 1.2 will be tipping point for RAD Java

I'm going to make a bold statement: Spring Roo is about to do for Spring developers what Ruby on Rails did for Ruby developers - make developer agility, and not mechanical, rigid architectural structures, the focus of daily developer productivity.

There. I've said it. But I have to step back for a minute and disclaim a few things. First, as some of you may know I've been working with Spring and Spring-related projects for a while. I'm also the education director here at Chariot, and Spring has been a mainstay of many of our Java-based consulting projects and course materials - we're also VMware Training Partner. Finally, I'm an author on Spring Roo in Action by Manning, which is undergoing the transformation from draft to publication by early 2012.

With the disclaimers aside, let's dig into my treatise.  First, a bit about what, exactly, Roo is...

Roo in a nutshell

Roo is a developer productivity tool that uses a simple command-line shell to configure projects, install features, and create various objects such as JPA entities, controllers, services, repositories, and tests.  Conceptually, it is similar to Rails, Grails, or even JBoss Seam, in that you use it to bootstrap a project.

Unlike these other frameworks, which lean heavily on dynamically generated code, Roo is a compile-time framework - no "Roo Runtime" exists to interpret your code.  The shell adjusts your code and configuration, based on changes made to annotations in source code (either by the Roo shell, or by the developer).  Roo even generates setters, getters, JPA code, transaction logic, scaffolded controller views, and a lot more.

Monday, October 17, 2011

Akka Scheduler: Actors with Heartbeats

Akka is an excellent platform for writing concurrent applications using the Actor model. Chariot architect Anatoly Polinsky describes the Akka scheduler and how you can use it to create a heartbeat for an actor. From Anatoly's blog:

AKKA Scheduler: Sending Message to Actor’s Self on Start

Akka has a little scheduler written using actors. This can be convenient if you want to schedule some periodic task for maintenance or similar. It allows you to register a message that you want to be sent to a specific actor at a periodic interval.

How Does AKKA Schedule Things?

Behind the scenes, AKKA scheduler relies on “ScheduledExecutorService” from the “java.util.concurrent” package. Hence when AKKA Scheduler needs to schedule “a message sent to an actor, given a certain initial delay and interval”, it just wraps the task of sending a message in a “java.lang.Runnable”, and uses a “ScheduledExecutorService” to schedule it:
service.scheduleAtFixedRate( createSendRunnable( receiver, message, true ),
                           initialDelay,                         
                           delay,                             
                           timeUnit).asInstanceOf[ScheduledFuture[AnyRef]]

“Heartbeat” Actor

Let’s look at the example of scheduling a message that should be sent to an Actor’s “self” as the Actor on start. Why? Because it is a cool use case : )
“Heartbeat” would be an ideal example of such use case => “When a ‘Hearbeat Actor’ starts, it should start sending heartbeats with a given interval (e.g. every 2 seconds)”

Creating a Message

First we need to create a message that will be scheduled to be sent every so often. We’ll call it a “SendHeartbeat” message:
sealed trait HeartbeatMessage 
case object SendHeartbeat extends HeartbeatMessage

Read the full post at: AKKA Scheduler: Sending Message to Actor's Self on Start

Tuesday, September 27, 2011

PhoneGap 1.0 Android Plugin updates

Kevin Griffin has been working with PhoneGap for some time now.  In this new blog post, Kevin discusses new features in PhoneGap 1.0.


With the upcoming release of PhoneGap 1.0 I thought I would point out a couple of nice additions coming for PhoneGap (Android) Plugin developers (and eventually PhoneGap as a whole).
The first addition is the propagation of lifecycle events (onPause, onResume and onNewIntent) to plugins. Plugin developers are now responsible for reacting appropriately if the app has multitasking turned on, but also have access to the lifecycle of the application. Developing the NFC plugin (https://github.com/chariotsolutions/phonegap-nfc) we found this an absolute necessity, so it’s great to see it added in.
Ah the power of Open Source software :)
The second is a new method of loading plugins. To register a plugin now you just need to add your plugin name and class to the plugins.xml (located in res/xml/)

Read more...



Thursday, September 22, 2011

Isobar Create 48 - A Solution to Parking Hassles Using NFC

 Recently, Chariot's Director of Consulting, Don Coleman, participated in the Isobar Create 48 NFC Hackathon in Boston. Below is an excerpt from his blog about his experience and his team's second place finish. 
 
My friend Chris Bernardi invited me to join his team for the Isobar Create 48 NFC Hackathon along with April DiMartino and Marc Neuwirth. The event kicked off on Tuesday around 3 PM at Space with a Soul. Before the hackathon there were some general Near Field Communication (NFC) presentations by Isobar, Nokia and ICS. After the NFC intro, they kicked out the people who came for the presentations so we could get started.
None of us came to the hackathon with the killer application idea. We brainstormed for a while, discarding lots of half-baked ideas and ended up deciding to build an NFC solution to make parking better. We came up with a bunch of scenarios, but decided to limit our initial implementation to garages with entrance and exit gates, so it was easier to track inventory.
April does an excellent job describing our application:
The working title of the app is “I Got Your Ticket Right Here” and is best understood when said with a Brooklyn NY accent ;-) We haven’t worked out a shorter and more appropriate title for it yet. So for purposes of this I will simply refer to it as the Parking app.

Read more...

Thursday, September 1, 2011

Checklists and Document Inspections

John Shepard, one of our architects, blogged some interesting thoughts on what makes a document inspection. Most developers will tell you that code reviews are good, and also tell you they aren't done regularly in their organization. But John goes beyond the scope of code to reviewing other documents such as requirements and technical specifications as well.

"While there is an ongoing debate on whether or not document inspections are useful, my experience is that on larger projects, they are very useful. They help maintain a minimum level of quality and help disseminate information among team members. Rather than continuing that debate here, I'm going to provide a starting point for checklists for those who have decided to use document inspections. While the checklists do end up being different for each project, I find it helpful to have an obvious place to start."

Read the full post here.

Tuesday, August 9, 2011

Full-Text Search For Relational Data

Thanks to internet search engines like Google, Yahoo, and Bing, everyone has become accustomed to searching their data effortlessly. Consequently, as developers of web-based applications, we increasingly find that our customers' requirements include being able to search their application's data in a "Google-like" way.

For a very small subset of applications that only need to do full-text search on a few database columns, there a some very simplistic solutions, ranging from using a SQL 'like' clause on every column to database-vendor supplied full-text search functionality for designated columns.

Frequently, however, these simplistic approaches are not enough, either because the data to be searched is large and complex, because the approach's search functionality is limited, or because database neutrality is desired. For these situations, a more advanced solution is needed. Fortunately, there are now a number of solutions available for all of the most popular platforms, languages, and frameworks, and several hosted solutions that are development stack-neutral.


Lucene and Compass
One of the most popular full-text search projects is Apache Lucene, a Java-based, open-source indexing and searching solution. Lucene itself targets indexing and searching of 'documents', but several other projects, most notably Compass, have adapted Lucene for indexing and searching relational data via integration with Object-Relational Mapping libraries such as Java's JPA, Hibernate, and others.

The combination of Lucene and Compass provides Java developers with an easy way to implement Google-like searching of their relational data, including fuzzy searching (spell-check / 'Did you mean...'), stemming ('fishing', 'fished', 'fish', and 'fisher' all match 'fish'), wildcards, and boolean logic.

For users of the Java JPA ORM, usage of Compass is fairly straightforward. For users of the Grails framework, the Grails Searchable Plugin makes implementation of full-text searching almost effortless. I recently added this plugin to a Grails application with a moderately complex data model, and had my full-text search functionality up and running in a few hours, with fine-tuning taking only a few more hours. As the application's data model has grown, very little time has had to be spent on keeping the search functionality up to date.

There are many other programming languages and platforms in use besides Java, so not surprisingly, Lucene has been ported to many of them, including C, C++, .NET, Objective-C, Python, Perl, and Ruby. The most popular of these, due to the popularity of the programming languages, are Lucene.net, which is a C# port targeted at the .NET runtime, and Ferret, which is a Ruby port targeted at the Ruby on Rails framework.

While Lucene and its variants currently dominate the open-source full-text search landscape, there are other well-known projects, including Xapian.


Hosted Solutions
There may be situations where it makes more sense move your full-text search functionality 'to the cloud'. Several hosted solutions are available, some based on Lucene or other open-source technologies, as well as other, proprietary offerings.

Websolr is a hosted version of Apache's Solr which is itself built on Lucene. Other offerings include Flying Sphinx for Rails (which uses the Sphinx search engine), and IndexTank, which is a proprietary offering.

Both Flying Sphinx and IndexTank are available as add-ons for the popular EngineYard and Heroku Ruby-based hosting platforms.

I recently tried out IndexTank on Heroku. IndexTank itself targets indexing and searching documents, but the Tanker gem does a great job of integrating IndexTank with Rails' ActiveRecord ORM. IndexTank's documentation doesn't mention it, and while not available "out of the box", IndexTank does support both fuzzy searching and stemming. All you need to do is send an email to their customer support address, and ask to have it turned on.

If your application can benefit from full-text search, there are plenty of interesting choices, regardless of your platform or programming language.