Grammars and Parsers

Image via Wikipedia

If one wants to interpret a sentence of a language, whether English, Portuguese or a math expression, the Interpreter design pattern is available to help with the task. I’m interested in having a parser to math expressions to use it in one of my personal projects called Ptolomeu. An interpreter to binary math expressions, like addition, subtraction, multiplication, etc, is already available. The interpreter process the abstract syntax tree (AST), what is only the half of the history, since it is still needed obtain the abstract syntax tree somehow. Now it’s time to continue the saga in search of a parser to math expressions.

First we’ll have to define a grammar to the sentences that the parser will process. Then we must decide what kind of parser is better to use implement. Therefrom we’ll implement the parser to build the AST (but not yet in this post). It’s better start the job in a simplified way: the parser will process addition expressions like ’1 + 1′. Uouuuu!!

Apolo, my friend, with ear standing full of wonder

Well… As the old Chinese saying goes, “a journey of one thousand miles begins with one tiny step”, or something like that.

I Studied Portuguese Grammar in the School

“Parsing is the process of structuring a linear representation in accordance with a given grammar. [..] This ‘linear representation’ may be a sentence, a computer program, [..]  in short any linear sequence in which the preceding elements in some way restrict the next element”^{[1, p. 3]}. “To a computer scientist ’3 + 4 * 5′ is a sentence in the language of ‘arithmetics on single digits’ [..], its structure can be shown, for instance, by inserting parentheses: (3 + (4 * 5)) and its semantics [i.e. its meaning] is probably 23″^{[1, p. 7]}.

What we’re trying to do here is, still according to Grune and Jacobs^[1], to describe a possible infinite set of sequence of symbols (the language) through the grammar (a finite recipe). Our grammar to generate sentences like ’9 + 2 + 3′ is:

1. Exp -> Add | Int
2. Add -> Add + Int | Int
3. Int -> 0 | 1 | ... | 9

“A formal grammar is a set of rules of a specific kind, for forming strings in a [..] language” ^[2]. The -> in the notation means that you can substitute the symbols on the left-hand side with the ones on the right-hand side; the | can be read as “or else”. The grammars are composed by terminals and nonterminals symbols^[1].

Terminals “are the elementary symbols of the language defined by a formal grammar”^[3]; in our case, the digits ’0′, ’1′, ’2′, ’3′, etc., until ’9′, and the plus sign (‘+’).

Nonterminals “are the symbols which can be replaced” ^[3]: the Exp can be replaced by an Add or an Int, both nonterminals as well; an Add may be replaced by another Add followed by the plus sign (‘+’) followed by the other nonterminal Int, or just by an Int. The grammar definition above states that an Int must be replaced by single digits from ’0′ to ’9′.

What we have here is a Type 2 grammar from the Chomsky hierarchy, also called a context-free grammar. This type of grammar requires only one nonterminal on the left-hand side.

Follows the derivation of the sentence ’9 + 2 + 3′ from the grammar we just defined:

Intermediate Form	Application of Rule…
Exp	The start symbol
Add	Exp -> Add
Add + Int	Add -> Add + Int
Add + Int + Int	Add -> Add + Int
Int + Int + Int	Add -> Int
9 + Int + Int	Int -> 9
9 + 2 + Int	Int -> 2
9 + 2 + 3	Int -> 3

 

And here is the production tree (and my graphical skills as well):

A production tree for the sentence '9 + 2 + 3'

 

An abstract parser tree

The duty of a parser is to reconstruct the parser tree (the other name for the production tree^[1]). This tree contains the elements of a sentence according with the structure of a given grammar and in the correct order. The interpreter uses the production tree to extract the semantic of the sentence.

With this grammar for simple addition operations in hands, it’s possible to think in implementing a parser. The idea is to have a table-driven parser since this kind of parser can return an AST (a kind of parser tree) and is very well know by the computer science community. Two of the most common table-driven parsers are the LL and LR parsers.

A LR parser is a bottom-up parser that “reads input from Left to right [..] and produces a Rightmost derivation”^[4] for a context-free grammar; in its turn a LL parser is a top-down parser that also reads input from Left to right but produces a Leftmost derivation “for a subset of the context-free grammar”. An LL parser can alternatively be implemented as a recursive descent parser^[5]. Both LL and LR parsers are deterministic, which are more efficient than parsers that use search algorithms – videlicet breadth-first and depth-first – because the firsts don’t have to predict (or choose) how to derive a sentence; however non-deterministic parsers can process much more types of grammars. Deterministic parsers do not have to choose because there’s only one course of action to take while parsing a sentence^[1].

Although a LR parser is more powerful and flexible, capable of handling much more languages than a LL parser, with better error handling and detection, it’s more difficult to construct a table for LR parsers, what is often done by a parser generator (a program to build parser tables)^[4]. Moreover there are some restrictions for a context-free grammar target to a LL parser, what we shall see later. Yet, all this powerful and flexibility is not necessary for my purposes and, considering that a LL parser is easier to implement than a LR, I’ll stick with the first.

LL(1) Grammar

The parser we’ll implement is more specifically called a LL(1) parser, which means that the parser will use only one token of lookahead “when parsing a sentence”^[5]. A LL(1) parser needs a LL(1) grammar. A LL(1) grammar is context-free, but not every context-free grammar is a LL(1) grammar; it’s well-known that isn’t possible to convert every context-free grammar in a LL(1) grammar, but whether there’s an equivalent LL(1) grammar for any context-free grammar is still subject of study.

Basically, a context-free grammar without left recursion and without left common factors is a LL(1) grammar. These restrictions aim to avoid conflicts and therefore backtracking, whereas an efficient parser “select the correct rule so that it constructs the tree without having to go back and try a different rule (i.e. backtracking) if the one it selects is not part of the derivation of the input sentence”^[6]. A general context-free grammar can become a LL(1) grammar when eliminating left recursion and applying left factoring.

Our grammar has a left recursion on the second rule (Add) that must be obliterated. (Note that, if the rule Add is derived to 'Add + Int‘, there’s still the same non-terminal Add on the left and this situation certainly will lead to an infinite recursion.) Eliminating left recursion means:

1) For every rule that exist a left recursion (Add), move the non-recursive part of this rule (+ Int) to a new rule called Add'.

Add' -> + Int

2) Put Add' in the end of this new rule.

Add' -> + Int Add'

3) Place a special symbol called epsilon, which means nothing, as an alternative substitution.

Add' -> + Int Add' | epsilon

4) Do the same for every rule that has a left recursion^[7].

Here’s our grammar for addition operations converted into a LL(1) grammar; this is the grammar we’ll use from now on:

1. Add -> Int Add'
2. Add' -> + Int Add' | epsilon
3. Int -> 0 | 1 | ... | 9

Observe that there’s no need to change the Int production rule because it isn’t left recursive. Get rid of left recursion in this grammar is sufficient since it does not contains left common factors.

Who’s this Table that Drives the Parser?^[7]

This post is becoming large for my taste so we’ll not construct the parser now. (You cannot even imagine how Apolo is disappointed with this situation. The poor thing will not use the parser yet.) Nevertheless, there’s enough space here to begin building the table.

The LL(1) Parser Table

A parser table is a lookup table that parsers use to know the next action to take, i.e. how to derive the next token of the input string. Every lookup table has a key associated with a value. In a LL(1) parser table, the key is formed by the terminals on the top and nonterminals on the left.

	+	0	1	2	...	9	$
Add
Add'
Int

 

The terminals of our grammar are the plus sign (‘+’), the digits from zero to nine and ‘$’ (end-of-file). There’s also the special symbol ‘epsilon’ (vazio). The nonterminals are Add, Add' and Int. This small grammar is capable of generate an infinite set of sentences like ’2 + 2′ and ’7 + 4 + 6 + 4′; however sentences like ’3 4′, ‘+1′, ’1 ++ 3′ or even ’44′ is not allowed here. We’ll fill this table using two functions called First and Follow on every nonterminal of the grammar.

The First Function

The First function evaluates which terminals can appear first when deriving a nonterminal.The result of First(Add) is First(Int) because the right side (the production rule) for the start symbol Add is Int Add'. The first terminal that appears when deriving Add can only be the same as First(Int).

First(Add) -> First(Int)

The derivation rule for Add' is + Int Add' | epsilon, so the first function value in this case is ‘+’ or ‘epsilon’.

First(Add') -> + | epsilon

The digits from zero to nine are the terminals that appear first when deriving the nonterminal Int:

First(Int) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Therefore we have:

First(Add) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
First(Add') -> + | epsilon
First(Int) -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The Follow Function

The Follow function for a given nonterminal reveals which terminals can appear after the derivation of this same nonterminal. It is difficult to see the value for the Follow(Add) function, thus we create an imaginary production rule to help us see which terminals can appear immediately after the derivation of Add:

S -> Add $

This imaginary newly created start rule S derive the original start production rule Add followed by the end-of-line symbol ‘$’, so:

Follow(Add) -> $

Follow(Add') is a little trickier. It may also seem difficult to see what follows Add' once there isn’t a nonterminal after the Add' in the rules of the grammar. However, consider that Add' can be derived from Add -> Int Add', so whatever comes after Add' it comes after Add too. Then we have:

Follow(Add') -> Follow(Add)


Finally, the value of Follow(Int) is First(Add') whereas Int is always followed for Add':

Follow(Int) -> + | epsilon

Ops! A value ‘epsilon’ for a Follow function doesn’t exist; after all at least an end-of-line (‘$’) must follow in the sentence. This ‘epsilon’ came from First(Add'). If Add' -> epsilon, then the terminal that follows Int can only be what follows Add', that is the ‘$’ symbol. Then:

Follow(Int) -> + | $

The Follow function application in all nonterminals results in:

Follow(Add) -> $
Follow(Add') -> $
Follow(Int) -> + | $


Filling the Parser Table

Let’s fill the table with the values of the First and Follow functions .

Take the results of the First function to fill the table and, when the value for a given nonterminal is an ‘epsilon’, use the result of the Follow function for this same nonterminal.

	+	0	1	2	...	9	$
Add	-	Add -> Int Add'	Add -> Int Add'	Add -> Int Add'	...	Add -> Int Add'	-
Add'	Add' -> + Int Add'	-	-	-	...	-	Add -> epsilon
Int	-	Int -> 0	Int -> 1	Int -> 2	...	Int -> 9	-

 

It’s kind of easy. Kicking off with the first line of the table, First(Add), remember, results in terminals from ’0′ until ’9′, thus we take the intersections of the line of the nonterminal Add (the first line) with the columns with header from ’0′ up to ’9′ (the values of First(Add)) and fill them with the production rule of Add, that is Add -> Int Add‘.

First(Add') results in an ‘epsilon’ besides ‘+’. For the reasons mentioned above, there’s no epsilon on the parser table (epsilon is neither a terminal nor a nonterminal). Instead of apply the value of First direct, in this case the proper value to use is Follow(Add'), that is ‘$’.

Proceeding that way will lead to the table above. There’s a software called ParsingEmu that you can use to check your grammar definition, the correctness of a parser table, the values of First and Follow functions and more.

Derivation Revisited

The tableau below shows how the derivation of the sentence ’9 + 2 + 3′ takes place inside a LL(1) table-driven parser.

Input stream	Stack	Action to take...
9 + 2 + 3 $	Add	Add -> Int Add'
9 + 2 + 3 $	Add' Int	Int -> 9
9 + 2 + 3 $	Add' 9
+ 2 + 3 $	Add'	Add' -> + Int Add'
+ 2 + 3 $	Add' Int +
2 + 3 $	Add' Int	Int -> 2
2 + 3 $	Add' 2
+ 3 $	Add'	Add' -> + Int Add'
+ 3 $	Add' Int +
3 $	Add' Int	Int -> 3
3 $	Add' 3
$	Add'	Add’ -> $
$	$	Yesss!! Bananas!

 

So long!

References

1. Dick Grune, Ceriel Jacobs. Parsing Techniques: A Practical Guide. Ellis Horwood Ltd., 1990. ISBN: 0136514316.
2. Formal grammar. (2011, February 3). In Wikipedia, The Free Encyclopedia. Retrieved 01:45, February 8, 2011, from http://en.wikipedia.org/w/index.php?title=Formal_grammar&oldid=411737777
3. Terminal and nonterminal symbols. (2011, January 20). In Wikipedia, The Free Encyclopedia. Retrieved 03:59, February 8, 2011, from http://en.wikipedia.org/w/index.php?title=Terminal_and_nonterminal_symbols&oldid=408996680
4. LR parser. (2010, November 28). In Wikipedia, The Free Encyclopedia. Retrieved 20:25, February 11, 2011, from http://en.wikipedia.org/w/index.php?title=LR_parser&oldid=399248916
5. LL parser. (2010, November 27). In Wikipedia, The Free Encyclopedia. Retrieved 21:01, February 11, 2011, from http://en.wikipedia.org/w/index.php?title=LL_parser&oldid=399215667
6. Predictive Parser. (2005, September 9). In Worcester Polytechnic Institute. Retrieved 21:27, February 11, 2011, from http://web.cs.wpi.edu/~gpollice/cs544-f05/CourseNotes/maps/Class5/PredictiveParsers.html
7. LL (1) Parsing. In Microsoft Research. Retrieved o4:44, February 12, 2011, from http://research.microsoft.com/en-us/um/people/abegel/cs164/ll1.html

Rest, Json and Spring

This text is about developing RESTful web services using Java, Maven, Json and Spring 3. You can read instructions of how to setup the development environment of this kind of project here. The source code is available on GitHub.

Rest

As stated in this text,

[With Rest], requests and responses are built around the transfer of representations of resources. Resources are identified by global ID’s that typically use a uniform resource identifier (URI). Client applications use Http methods (such as GET, Post, PUT, or Delete) to manipulate the resource or collection of resources. Generally, a GET method is used to get or list the resource or collection of resources, Post is used to create, PUT is used to update or replace, and Delete is for removing the resource.

The Amazing Salume Application™

You work at a small business, a supplier company specialized in the finest salumes in the world, with a few clients, mostly bistros and restaurants (actually, there are only two clients, one bistro and one restaurant, but describing the company in that way makes it looks larger). They both are good clients and the sales of the company is quite impressive. As the sales are expected to continue to grow, it is time to use a software application to aid the sale process. You decided to provide a RESTful web service to allow clients to manipulate their salumes orders through requests/responses in Json format.

A Very Simple Example

This a simple example of how to implement a Rest service with Spring 3 and Json. The base URI of this web service is http://localhost:8080/Salume/restService/order/.

GET Http Method

There goes a silly findOrder method which will return a mortela as an order no matter the id passed as argument.

@Controller
@RequestMapping("/order")
public class OrderController {

    // . . . Other services...

    @RequestMapping(method = RequestMethod.GET, value = "/{id}")
    public @ResponseBody Order findOrder(@PathVariable("id") long id) {
        Order order = new Order();
        order.setProduct("mortadela");
        return order;
    }
}

The {id} defined in the @RequestMapping is an URI template variable which will be replaced by the value passed through the id parameter thanks to the PathVariable.

@ResponseBody Annotation will bound the Order instance returned by findOrder to the web response body (in a Json format in this case).

Just to illustrate, here is the Order class:

public class Order {
    private final long id = 1;
    private String product;

    public long getId() {
        return id;
    }

    public String getProduct() {
        return product;
    }

    public void setProduct(String product) {
        this.product = product;
    }
}

Then simply add the Jackson Maven Plugin to the pom.xml and let the Spring automagically convert Order to a Json format.

        <dependency>
            <groupId>org.codehaus.jackson</groupId>
            <artifactId>jackson-mapper-asl</artifactId>
            <version>1.9.5</version>
        </dependency>

cURL

Use cURL to test findOrder Rest service. If you are new to cURL, I  suggest the reading of REST-esting with cURL to get started with it. A good alternative to cURL to debug RESTful web services is a nice Firefox plug-in, the RESTClient

Type:

curl -HAccept:application/json http://localhost:8080/Salume/restService/order/2

and the result will be:

{"id":1,"product":"mortadela"}

The same result is achieved if one types in the browser http://localhost:8080/Salume/restService/order/2.

Post

Clients will request a new order using the Post method.

@Controller
@RequestMapping("/order")
public class OrderController {

    // . . . Other services...

    @RequestMapping(method = RequestMethod.POST)
    @ResponseBody
    public Order add(@RequestBody Order order) {
        // . . . business rules implementation here, like security, whatever
        // . . . Add the order somewhere (it could be a database, memory...
        // ... or somewhere behind the cloud)
        return order;
}

Since we are using the @RequestBody in order to let Spring convert a Json text to an Order instance, we must configure MappingJacksonHttpMessageConverter to be used as a HttpMessageConverter. (In the Salume project, the MappingJacksonHttpMessageConverter is configured in the restDispatcher-servlet.xml.)

<bean class="org.springframework.web.servlet.mvc.annotation.AnnotationMethodHandlerAdapter">
    <property name="messageConverters">
        <list>
            <ref bean="jsonConverter" />
        </list>
    </property>
</bean>

<bean id="jsonConverter" class="org.springframework.http.converter.json.MappingJacksonHttpMessageConverter">
    <property name="supportedMediaTypes" value="application/json" />
</bean>

Now we can Post a new order; follows an example using cURL:

curl -v -H "Accept:application/json" -H "Content-Type:application/json;charset=UTF-8" -X POST -d '{"product":"columbus"}' http://localhost:8080/Salume/restService/order

Note the Content-Type header set to application/json;charset=UTF-8, which is necessary besides defining "Accept:application/json".

PUT

When updating an order, clients use the PUT method:

@Controller
@RequestMapping("/order")
public class OrderController {

    // . . . Other services...

    @RequestMapping(method = RequestMethod.PUT, value = "/{id}")
    @ResponseBody
    public Order update(@PathVariable("id") long id, @RequestBody Order order) {
        // . . . business rules here
        // . . . Update the order with a given id
        return updated;
    }
}

Note that it is necessary specify the id in the URL of the order being updated (the order id is 2 in the example below).

curl -v -H "Accept:application/json" -H "Content-Type:application/json;charset=UTF-8" -X PUT -d '{"product":"speciale"}' http://localhost:8080/Salume/restService/order/2

Delete

Not surprisingly, the Delete method is used to remove an order.

@Controller
@RequestMapping("/order")
public class OrderController {

    // . . . Other services...

    @RequestMapping(method = RequestMethod.DELETE, value = "/{id}")
    @ResponseBody
    public Order remove(@PathVariable("id") long id) {
        // . . . business rules here
        // . . . Remove the order with a given id
        return removed;
    }
}

Try something like:

curl -i -v -HAccept:application/json -X DELETE http://localhost:8080/Salume/restService/order/2

A More Plausible Domain Model

Piece of cake until now. Let’s reformulate the domain model. A order contains one to many items and each item specifies a product and its quantity.

public class Order {

    private long id;

    private List<Item> items = new ArrayList<Item>();

    // . . . getters and setters
}

public class Item {

    private int quantity;

    private Product product;

    // . . . getters and setters
}

public class Product {

    private String name;

    private String description;

    private BigDecimal price;

    // . . . getters and setters
}

There’s no need to do any modification in the OrderController. What will change is the Json format to reflect the new order modeling. Thus, for example, when a client sends a PUT request to update an Order, it may send a Json string like this:

  {
     "id": 1,
     "items": [
       {
         "quantity": 2,
         "product": {
           "name": "Mortadela",
           "description": "Carne defumada",
           "price": 23.4
         }
       },
       {
         "quantity": 5,
         "product": {
           "name": "Salume Speciale",
           "description": "Gusto incredibile",
           "price": 53.9
         }
       }
     ]
   }

Unit and Integration Tests

Unit Tests

Here’s an example of the use of Spring MVC Test project to implement unit tests.

@RunWith(SpringJUnit4ClassRunner.class)
// @ContextConfiguration defaults to OrderControllerTest-context.xml in the same package
@ContextConfiguration
public class OrderControllerTest {

    @Test
    public void testFindOrder() throws Exception {
        standaloneSetup(new OrderController())
                .build()
                .perform(get("/order/2").accept(MediaType.APPLICATION_JSON))
                .andExpect(status().isOk())
                .andExpect(content().type(MediaType.APPLICATION_JSON))
                .andExpect(content().string(findOrderJsonResult()))
                .andExpect(jsonPath("$.id").value(1)).andDo(print());
    }

    // . . .

Note the #findOrderJsonResult method. Instead of inline a Json String, which can be very awkward especially in the case of long ones, the expected result is defined in a file and then extracted with a couple utility methods. For example, definition of the expected result in the testFindOrder is below.

  {
     "id":1,
     "items":[
       {
         "quantity":2,
         "product":{
           "name":"Mortadela",
           "description":"Carne defumada",
           "price":23.4
         }
       },
       {
         "quantity":5,
         "product":{
           "name":"Salume Speciale",
           "description":"Gusto Incredibile",
           "price":53.9
         }
       }
     ]
   }

Follow the utility methods to extract the expected Json String from a file.

    // . . .

    private String findOrderJsonResult() throws IOException {
        return jsonResultFromFile("expectation/OrderControllerTest-findOrder-json.txt");
    }

    private String jsonResultFromFile(String filePath) throws IOException {
        final URL url = getClass().getResource(filePath);
        final List<String> lines = FileUtils.readLines(new File(url.getFile()));
        final StringBuilder builder = new StringBuilder();
        for (String line : lines) {
            // You can find StringUtils in the Commons Lang library
            builder.append(StringUtils.trim(line));
        }
        return builder.toString();
    }

    // . . .

This is the content of OrderControllerTest-context.xml till now.

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:context="http://www.springframework.org/schema/context"
    xmlns:mvc="http://www.springframework.org/schema/mvc"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
	    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
        http://www.springframework.org/schema/context
        http://www.springframework.org/schema/context/spring-context-3.0.xsd">

    <context:component-scan base-package="com.github.rafaelfiume.salume.web.rest" />

</beans>

Integration Tests

The RestTemplate is a good choice to implement integration tests for Rest services. Follows an example:

@Category(IntegrationTest.class)
@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration("OrderControllerTest-context.xml")
public class OrderControllerIT {

    private static final String REST_SERVICE = "http://localhost:8080/Salume/restService/order";

    @Autowired
    private RestTemplate restTemplate;

    @Test
    public void testFindOrder() {
        Order expected = // . . . fixture here

        Order result = restTemplate.getForObject(REST_SERVICE + "/{id}", Order.class, 2);
        Assert.assertEquals(expected, result);
    }
}

Configure the RestTemplate in the OrderControllerTest-context.xml.

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xmlns:context="http://www.springframework.org/schema/context"
    xmlns:mvc="http://www.springframework.org/schema/mvc"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
	    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
        http://www.springframework.org/schema/context
        http://www.springframework.org/schema/context/spring-context-3.0.xsd">

    <context:component-scan base-package="com.github.rafaelfiume.salume.web.rest" />

    <bean id="restTemplate" class="org.springframework.web.client.RestTemplate  ">
        <property name="messageConverters">
            <list>
                <ref bean="jsonConverter" />
            </list>
        </property>
    </bean>

    <bean id="jsonConverter"
        class="org.springframework.http.converter.json.MappingJacksonHttpMessageConverter">
        <property name="supportedMediaTypes" value="application/json" />
    </bean>
</beans>

Fonts

• Build RESTful web services using Spring 3
• Build RESTful web services with the Spring 3 MVC HttpMessageConverter feature
• Spring 3 MVC and JSON example
• REST-esting with cURL
• REST in Spring 3: @MVC

Development Environment Setup with Maven 3, Spring 3 and Jetty 8

Many of my colleagues developers often ask me for help to setup a development environment (one of them once even begged for help, I swear… it was really funny!). I do not want avoid surprising comic Greek-Tragedy-like episodes at work, however this text is intended to help me and others save time during the setup of a common Java environment consisting of Maven, Spring and Jetty.

Of course this is not an original piece of art, it’s is more like an aggregate of quotes and links to useful resources in the Internet.

Maven

According to Maven 3 Tutorial – Project Setup:

Maven is a software project management and comprehension tool that includes: build tools, dependency management, project reporting and much more. I say “much more” because at the core Maven is a plugin execution framework.  There are plugins supported by the Maven project, plugins supported by Mojo Project, and third party plugins.

About the comparisons between Ant and Ivy, the same tutorial linked above says that they all are different tools:

Ant is a build tool and Ivy is a dependency management tool. Maven is not just a build tool or just a dependency management tool. On the contrary, Maven is a project management tool that embodies software development best practices.

1. Download and install Maven. (Refer to this thread if there’s some problem configuring PATH variables.)
2. Then install the m2eclipse plugin.

m2eclipse Plugin

This says that m2eclipse was included in the release of Eclipse Indigo. However “m2e comes prepackaged in the latest Eclipse IDE for Java Developers“, but it’s not shipped with Eclipse IDE for Java EE Developers package. Here are instructions on how to install this plugin in Eclipse.

Spring

This text has a good explanation on how to configure a Spring project. The Spring modules dependencies of a project must be included in pom.xml, like:

<dependency>
    <groupId>org.springframework</groupId>
        <artifactId>spring-test</artifactId>
        <version>${org.springframework.version}</version>
        <scope>test</scope>
</dependency>

There is an example of a definition of the most common dependencies required to start a Spring project with Maven in the section Basic Project Resources below. More info about how to obtain Spring 3 artifacts with Maven can be found here.

Jetty

In order to use Jetty with Maven, maven-war-plugin and maven-jetty-plugin are prerequisites.

According to Jetty Maven Plugin documentation, all one needs to do in order to use Jetty (7 and above) is to add the Jetty Plugin to the pom.xml.

<plugin>
  <groupId>org.mortbay.jetty</groupId>
  <artifactId>jetty-maven-plugin</artifactId>
</plugin>

In the project directory, the command mvn jetty:run will cause the Jetty to start running on http://localhost:8080.

See the section Debugging with the Maven Jetty Plugin in Eclipse to see how to configure Eclipse to debug applications deployed in a Jetty instance via Maven.

Path Variables Configuration in Mac OS X Lion

This is done with the export command, as:

export M2_HOME=/usr/share/maven

It will load the newly configured M2_HOME in the memory. In order to make it persistent, save it in a bash_profile file (in your home directory) and reload the profile.

First update the path variable:

echo "export M2_HOME=/usr/share/maven" >> .bash_profile

Then make it persistent:

. .bash_profile

Basic Project Resources

This section contains all the configuration files that an initial project that uses Maven 3, Spring 3 and Jetty (7 and above) needs, that is:

• pom.xml
• web.xml
• restDispatcher-servlet.xml (a project specific Spring configuration file)
• business-context.xml (idem)

The pom.xml

Usually a pom.xml begins with the project definition.

    <modelVersion>4.0.0</modelVersion>
    <groupId>com.github.rafaelfiume</groupId>
    <artifactId>SalumeSupplier</artifactId>
    <version>0.0.1-SNAPSHOT</version>
    <packaging>war</packaging>
    <name>Salume Supplier</name>
    <description>Server-side application to help sell mortadelas</description>

Dependencies

Dependencies, like JUnit and Commons Lang libraries, are defined in a project through the dependency element in a pom.xml file:

    <dependencies>
        <dependency>
            <groupId>commons-lang</groupId>
            <artifactId>commons-lang</artifactId>
            <version>20030203.000129</version>
        </dependency>

        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.10</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

Follows the most common necessary dependencies to start a project that uses Spring 3 artifacts with Maven:

        <!-- Check how to obtain Spring 3 artifacts at http://blog.springsource.org/2009/12/02/obtaining-spring-3-artifacts-with-maven/ -->
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-context</artifactId>
            <version>${org.springframework.version}</version>
        </dependency>

        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-web</artifactId>
            <version>${org.springframework.version}</version>
        </dependency>

        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-webmvc</artifactId>
            <version>${org.springframework.version}</version>
        </dependency>

        <!-- Notice the'test' scope -->
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-test</artifactId>
            <version>${org.springframework.version}</version>
            <scope>test</scope>
        </dependency>

The ${org.springframework.version} variable is definided as a property element. Another property defined is the source encoding:

   <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <org.springframework.version>3.1.1.RELEASE</org.springframework.version>
    </properties>

Plugins

Maybe the most basic Maven plugin one may use is the maven-compiler-plugin, which is necessary to configure the target JVM.

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>2.3.2</version>
                <configuration>
                    <target>1.6</target>
                    <source>1.6</source>
                </configuration>
            </plugin>
        </plugins>
    </build>

According to Maven War Plugin webpage, it “is responsible for collecting all artifact dependencies, classes and resources of the web application and packaging them into a web application archive”.

            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-war-plugin</artifactId>
                <version>2.2</version>
                <configuration>
                    <archive>
                        <manifest>
                            <addClasspath>true</addClasspath>
                            <classpathPrefix>lib/</classpathPrefix>
                        </manifest>
                    </archive>
                </configuration>
            </plugin>

The Jetty Maven Plugin is added and configured as follows:

            <plugin>
                <groupId>org.mortbay.jetty</groupId>
                <artifactId>jetty-maven-plugin</artifactId>
                <version>8.1.2.v20120308</version>
                <configuration>
                    <scanIntervalSeconds>10</scanIntervalSeconds>
                    <stopKey>stop</stopKey>
                    <stopPort>9999</stopPort>
                </configuration>
            </plugin>

web.xml

<web-app version="2.5" xmlns="http://java.sun.com/xml/ns/javaee"
	xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
	xsi:schemaLocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_2_5.xsd">

	<display-name>Salume Supplier</display-name>

	<context-param>
		<param-name>contextConfigLocation</param-name>
		<param-value>WEB-INF/business-context.xml</param-value>
	</context-param>

	<listener>
	    <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
	</listener>

	<servlet>
	    <servlet-name>restDispatcher</servlet-name>
	    <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
	</servlet>
	<servlet-mapping>
	     <servlet-name>restDispatcher</servlet-name>
	     <url-pattern>/restService/*</url-pattern>
	</servlet-mapping>

</web-app>

restDispatcher-servlet.xml

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:context="http://www.springframework.org/schema/context"
    xmlns:mvc="http://www.springframework.org/schema/mvc"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
        http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
        http://www.springframework.org/schema/context
        http://www.springframework.org/schema/context/spring-context-3.0.xsd
        http://www.springframework.org/schema/mvc
        http://www.springframework.org/schema/mvc/spring-mvc-3.0.xsd">

    <context:component-scan base-package="foo.web" />

    <mvc:annotation-driven />

    <bean
        class="org.springframework.web.servlet.view.InternalResourceViewResolver">
        <property name="prefix" value="/WEB-INF/views/" />
        <property name="suffix" value=".jsp"></property>
    </bean>
</beans>

business-context.xml

<beans xmlns="http://www.springframework.org/schema/beans"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:context="http://www.springframework.org/schema/context"
    xmlns:mvc="http://www.springframework.org/schema/mvc"
    xsi:schemaLocation="http://www.springframework.org/schema/beans
	    http://www.springframework.org/schema/beans/spring-beans-3.0.xsd
        http://www.springframework.org/schema/context
        http://www.springframework.org/schema/context/spring-context-3.0.xsd
        http://www.springframework.org/schema/mvc
        http://www.springframework.org/schema/mvc/spring-mvc-3.0.xsd">

    <context:component-scan base-package="com.github.rafaelfiume.salume.web.rest" />

    <mvc:annotation-driven />

</beans>

Debugging with the Maven Jetty Plugin in Eclipse

Note: this section (including the section title) is a literal extraction of the content originally posted here with a very small modification (added the goal clean to the Arguments: in the Step 1).

Step 1

Go to the Run/External Tools/External Tools ... menu item on the Run menu bar. Select Program and click the New button. On the Main tab, fill in the Location: as the full path to your mvn executable. For the Working Directory: select the workspace that matches your webapp. For Arguments: add clean jetty:run.

Move to the Environment tab and click the New button to add a new variable named MAVEN_OPTS with the value:

-Xdebug -Xnoagent -Djava.compiler=NONE -Xrunjdwp:transport=dt_socket,address=4000,server=y,suspend=y

If you supply suspend=n instead of suspend=y you can start immediately without running the debugger and launch the debugger at anytime you really wish to debug.

Step 2

Then, pull up the Run/Debug/Debug ... menu item and select Remote Java Application and click the New button. Fill in the dialog by selecting your webapp project for the Project: field, and ensure you are using the same port number as you specified in the address= property above.

Now all you need to do is to Run/External Tools and select the name of the maven tool setup you created in step 1 to start the plugin and then Run/Debug and select the name of the debug setup you setup in step2.

From instructions provided by Rolf Strijdhorst on the Maven mailing list

Stopping Jetty

In order to stop the jetty server the Allow termination of remote VM should be checked in debug dialog in Step 2. When you have the jetty server running and the debugger connected you can switch to the debug perspective. In the debug view, right click on the Java HotSpot(TM) Client VM[localhost:4000] and chose terminate. This will stop the debugger and the jetty server.

Conclusion

After all that, executing the command mvn jetty:run and navigating to localhost:8080, the browser will display an index.html if such page exists.

You can download a project along these lines here. And you can continue reading about the Salume project development in Rest, Json and Spring text.

Implementing a Feature With TDD

A few days ago, I heard somebody ask “How do I start developing a functionality with TDD?” and I thought immediately that it would be a good idea to write about it.

A History

Suppose you are really popular, with thousands of friends in the Facebook, everybody in your neighborhood knows you and enjoys your company. In fact everyone in your city does.

You possess a huge LP collection, ranging from Van Halen to John Coltrane, art pieces, a vast library containing books (some people believe you own an original first edition Shakespeare’s Romeo and Julieta), comics, CDs, DVDs.

João Gilberto en Mexico (Photo credit: Wikipedia)

Of course your friends are always asking to borrow Tom Jobim‘s and B.B. King‘s LPs, rare books, the most beloved CDs, DVDs and even daddy’s 1964 Rolls-Royce, which you lent to one of your closest friend to impress a girl.

But sometimes people forget to give back the books you lent (another version of the legend says that your grandfather lost that Shakespeare’s original first edition to a sheik that never returned it); it’s painful to remember that no one knows who took an amazing João Gilberto LP. Daddy’s 1964 Rolls-Royce is in the garage now… Although its entire left side is scratched.

Most of the time, however, people borrowing your stuff is a very good business. You get tickets for theater, sports, concerts and so on almost every week, are often invited to great parties and there’s that nice friend of yours that is always willing to let you spend holidays in his house at Italian Riviera.

So, how to make the most of this situation?

Just denying everything to everyone may hurt the feelings of good (and more generous) friends, right? A software to help determine if you’ll ever see that Lennon’s pair of socks again and will gain cuban cigars in return is what you need.

What we want to know is how correct are our your friends based on their historic. The application indicates a conservative position to those who have a bad or no historical at all, so the more trouble a friend causes, the worse is his credibility and vice-versa. On the other hand, generous fellows gain “trust points”.

The system will advise you calculating risks and opportunities based on the credibility of your friends and the degree of importance of the items in your collection.

So, where to begin?

Let’s start writing a test for the feature we want: check a friend’s credibility.

// Using JUnit 4
public class ScoreTest {
    @Test public void adviceAboutMyFriends() {
        score.checkCredibilityOf(thisFriend);
    }
}

It’s a good idea to write exactly what we’re testing and what we expect to achieve.

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        score.checkCredibilityOf(thisFriend);
    }
}

To lend or not to lend what? The advice will vary according to the friend and the item he wants to borrow, hence it’s necessary to consider items too.

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        score.checkCredibilityOf(thisFriend, thisItem);
    }
}

The word “this” is redundant and is becoming quite annoying, thereby we should avoid it for now on.

What will score#checkCredibilityOf returns? A boolean whose value would mean “go ahead and lend it” if true, or “don’t even think about it” otherwise? How about a class instance representing the general friend’s credibility and responsible to calculate whether someone is reliable enough to take a certain item, then finally returns a boolean? Something like…

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        boolean reliable = score.checkCredibilityOf(friend).to(item);
    }
}

Interesting, easy to read, but a little stilted for my taste. We just get started, so let’s keep things as simple as we can. Another alternative is to dispense the score instance to rate your fellows and implement this feature directly in Friend or Item class.

        . . .
        item.canBeBorrowedBy(friend); // 1st option
        // or
        friend.canBorrow(item); // 2nd
        . . .

The first option is in the passive voice, which some editors argue that it is more difficult to read and understand. The second one is more concise and describes better what we want, so I’ll pick it (note, however, that it’s an entirely subjective choice). Then we finish implementing the first version of this unit test.

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        Friend friend = new Friend();
        Item item = new Item();
        boolean reliable = friend.canBorrow(item);
        assertTrue(reliable); // static import of org.junit.Test.Assert.assertTrue
    }
}

This code doesn’t even compiles…

… therefore we begin implementing it creating Friend and Item classes, then the #canBorrow method.

1) First

public class Friend {
}

2) Then

public class Item {
}

3) At long last

public class Friend {

    public boolean canBorrow(Item item) {
        return true;
    }
}

Run the test and you’ll see that it works fine (the JUnit green bar appears). However it only expects reliable friends so far, disconsidering the unreliable ones.

The application, obviously, must distinguish well both kind of friends

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        Item item = new Item();
        Friend reliable = new Friend();
        assertTrue(reliable.canBorrow(item));
        Friend unreliable = new Friend();
        assertFalse(unreliable.canBorrow(item));
    }
}

Run it again. The test fails on the line 7. Up to now, our system is unable to say who is or isn’t trustworthy. What’s the simplest way possible to implement #canBorrow and make the test green? (By the way, “make the test green” or “get the test from red to green” are examples of expressions often used meaning “make the test works”. Again, green and red are references to the JUnit bar, which appears green when everything is ok or red when some test fail. But you already knew that. )

Here goes our first attempt.

public class Friend {
    private final boolean reliable;

    public Friend(boolean reliable) {
        this.reliable = reliable;
    }
    public boolean canBorrow(Item item) {
        return reliable;
    }
}

Fix the test which was broken by the changes in Friend.

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        Item item = new Item();
        Friend reliable = new Friend(true);
        assertTrue(reliable.canBorrow(item));
        Friend unreliable = new Friend(false);
        assertFalse(unreliable.canBorrow(item));
    }
}

Yes! Green bar, baby! What? How so? Do you think we could move faster towards a final implementation without these tiny steps?

A little pause to think about tiny steps

Borrowing Kent Beck words (p. 9)^[1]:

Do these steps seem to small to you? Remember, TDD is not about taking teeny-tiny steps, it’s about being able to take teeny-tine steps. Would I code day-to-day with steps this small? No. But when things get the least bit weird, I’m glad I can. Try teeny-tyne steps with an example of your own choosing. If you can make steps too small, you can certainly make steps the right size. If you only take larger steps, you’ll never know if smaller steps are appropriate.

It’s time to think about the algorithm a little more carefully

The algorithm has to take into account both friends and items. There are many ways to calculate a score based on historical data, foreseeing risks and opportunities. You could call a specialist but you’d rather to do it by yourself and improve it as necessary.

A good start is to define the degree of important of your stuff and rank your friends. Items are classified as disposable, ordinary, day-to-day use, cool stuff, expensive, proud of the family, piece of art and eighth wonder of the world.

public class Item {

    public enum Importance {
        DISPOSABLE, ORDINARY, DAY_TO_DAY_USE,
        COOL_STUFF, EXPENSIVE,
        PROUD_OF_THE_FAMILY, PIECE_OF_ART, EIGHTH_WONDER_OF_THE_WORLD;
    }

    private final Importance importance;

    public Item(Importance importance) {
        this.importance = importance;
    }

    /*
     * This class isn't designed to be a JavaBean, so you can omit the 'get'
     * prefix if you want. It's a matter of taste.
     */
    public Importance importance() {
        return importance;
    }
}

Surely you don’t call your friend names, but it’s perfectly acceptable to rank their attitudes, maybe from 0 (pleasant yet understands the verb “lend” as “give”) to 100 (Dalai Lama).

public class Friend {
    private final int rank; // ranked from 0 (Zé Ruela) to 100 (Dalai Lama)

    public Friend(int rank) {
        // validate(rank) omitted for brevity
        this.rank = rank;
    }
    public boolean canBorrow(Item item) {
        // validate(item) omitted for brevity
        return true; // just returns false for now
    }
}

Pause to think about invariants

Don’t forget to unit test and implement Friend class’s invariants: rank cannot be less than 0 or greater than 100, while item cannot be null.

We’re back

These last changes broke the test. Next step is to make it work again.

public class ScoreTest {
    @Test public void adviceAboutMyFriendsShouldHelpMeDecideWhetherOrNotToLend() {
        Item item = new Item(Importance.EXPENSIVE);
        Friend reliable = new Friend(98);
        assertTrue(reliable.canBorrow(item));
        Friend unreliable = new Friend(10);
        assertFalse(unreliable.canBorrow(item));
    }
}

The test code above says that a friend with 98 points can borrow expensive items, but those with 10 cannot. As we’re testing the rule for expensive items, it would be better to clearly state what we’re doing.

public class ScoreTest {
    @Test public void canLendExpensiveItemsOnlyToFriendsRankedWith98OrMorePoints() {
        Item art = new Item(Importance.EXPENSIVE);
        Friend reliable = new Friend(98);
        assertTrue(reliable.canBorrow(art));
        Friend unreliable = new Friend(10);
        assertFalse(unreliable.canBorrow(art));
    }
}

Ok, it’s compiling and red (failing). We’re doing like Kent Back said (p. 7)^[1]:

1. Run a little test
2. Run all test and fail
3. Make a little change
4. Run the tests and succeed
5. Refactor to remove duplication.

A possible solution to make the test green again is to change Friend as follows:

public class Friend {
    private final int rank;

    public Friend(int rank) {
        this.rank = rank;
    }
    public boolean canBorrow(Item item) {
        // This fix the test
        return (item.importance() == Item.Importance.EXPENSIVE) && (rank >= 98);
    }
}

The rule for disposable items is extremely easy to implement, since you don’t mind lend them to any one – unfortunately (or fortunately, depending how you see it) there’s not much of these items in your collection. Besides that, nobody wants to borrow them.

    . . .
    // add test for disposable items
    @Test public void canLendTrashToEveryOne() {
        Item trash = new Item(Importance.DISPOSABLE);
        Friend reliable = new Friend(98);
        assertTrue(reliable.canBorrow(trash));
        Friend unreliable = new Friend(10);
        assertTrue(unreliable.canBorrow(trash));
    }

The cycle repeats. #canLendTrashToEveryOne is red. You need to implement Friend#canBorrow in order to make both tests succeed as well as programming the other rules:

1. Friends with 43 or more points may borrow ordinary items
2. With 75 or greater, they’re able to take home day-to-day use
3. Cool-stuff, only who has 82 points or greater
4. After the scratch in daddy’s car, no one can grab “proud of the family” and “piece of arts” (at least for a while)
5. Wonders never come out from where they’re hidden (since your grandpapa lost that book, says the legend).

Everything pretty straightforward to implement…

… and yet not completely useful. We’ve been ranking your friends manually, therefore your next step will probably focus on the machinery that estimates friends’ score. There are other facts you may consider as well, like:

1. who already picked objects, and what kind, when asking you to lend something
2. those who are generous with you probably deserve extra points in their scores
3. the app can even suggest you to offer another nice stuff when a very good friend of yours ask for something…

References

1. ^Back, Kent. Test-Driven Development: by Example. Boston, MA: Addison-Wesley, 2003. ISBN: 0321146530.

Developing an Interpreter to Math Expressions

Image via Wikipedia

We’ll start slowly, only dealing with the four binary basic operations: addition, subtraction, multiplication and division. Even though we defined a concise set of operations, I need to be even more humble in order to achieve our goals, and that’s why I’ll choose one of these operations to get started with the fun.

How about we begin with the addition operation? Sounds easy good to me. Doing that will lead the way to the remainder operations (I mean subtraction, multiplication and division operations). We can represent our math expression with a limited context-free grammar like this:

MathExp -> VariableExp | Constant | AddExp | '(' MathExp ')'
AddExp -> MathExp + MathExp
VariableExp -> a | b | ... | z
Constant -> 0 | 1 | ... | 9


Let’s write a test first (using JUnit 4): if an ordinary ‘a + b’ expression with ‘a = 2′ and ‘b = 4′ must be solved, one could think in the following API (specially if you read about the GoF Interpreter pattern):

@Test
public void testAddExpression() {
    final VariableExp a = new VariableExp("a");
    final VariableExp b = new VariableExp("b");
    final AdditionExp add = new AdditionExp(a, b);
    final Context context = new Context();
    context.assign(a, 2);
    context.assign(b, 4);
    final Integer result = add.evaluate(context);
    Assert.assertSame(6, result);
}

This code will not work, since VariableExp, AdditionExp and Constant classes doesn’t even exist yet. The next step is to create these classes with its constructors and methods, and hence compile the source without errors. After that let’s implement this code with help of the tests we have written and the Interpreter pattern.

“The Interpreter pattern uses a class to represent each grammar rule. Symbols on the right-side of the rule are instance variables of these classes” (Gamma et al, 1995, p. 243).

public class VariableExp {

    private final String name;

    public VariableExp(String name) {
        this.name = name;
    }

    public Integer evaluate(Context context) {
        return context.lookup(name);
    }

    String getName() {
        return name;
    }
}

public class Context {

    private final Map map = new HashMap();

    public void assign(VariableExp var, int value) {
        map.put(var.getName(), value);
    }

    public Integer lookup(String varName) {
        return map.get(varName);
    }
}

public class AdditionExp {

    private final VariableExp operand1;

    private final VariableExp operand2;

    public AdditionExp(VariableExp operand1, VariableExp operand2) {
        this.operand1 = operand1;
        this.operand2 = operand2;
    }

    public Integer evaluate(Context context) {
        return operand1.evaluate(context) + operand2.evaluate(context);
    }
}

This is a very simple implementation of such a thing with a fancy name like an “interpreter to math expression” (that maybe sounds like an Einstein thing), but we got it: the test runs smoothly. It happens that often we deal with constants besides variables in expressions, like ‘a + (-5) = -3′. This thing of writing tests before implementing code seems just fine, so I will stick with it.

@Test
public void testAddExpressionWithConstant() {
    final VariableExp a = new VariableExp("a");
    final AdditionExp add = new AdditionExp(a, new Constant(-5));
    final Context context = new Context();
    context.assign(a, 2);
    final Integer result = add.evaluate(context);
    Assert.assertSame(-3, result);
}

Again we need first to make the code compile and, to do that, create the class Constant. But this time only creating a class doesn’t solve all our problems. The AdditionExp constructor demands a VariableExp and Constant isn’t one. In fact, the Interpreter pattern ask for us to define an interface representing the expressions, something we have not done yet. We proceed creating the MathExp interface.

public interface MathExp {

    Integer evaluate(Context context);
}

The MathExp interface defines the evaluate method, an API already part of VariableExp and AddExp, what makes sense whereas both are expressions.

public class VariableExp implements MathExp {

    private final String name;

    public VariableExp(String name) {
        this.name = name;
    }

    @Override
    public Integer evaluate(Context context) {
        return context.lookup(name);
    }

    String getName() {
        return name;
    }
}

public class AdditionExp implements MathExp {

    private final MathExp operand1;

    private final MathExp operand2;

    public AdditionExp(MathExp operand1, MathExp operand2) {
        this.operand1 = operand1;
        this.operand2 = operand2;
    }

    @Override
    public Integer evaluate(Context context) {
        return operand1.evaluate(context) + operand2.evaluate(context);
    }
}

The Constant implementation is also straightforward:

public class Constant implements MathExp {

    private final Integer value;

    public Constant(Integer value) {
        this.value = value;    }

    @Override
    public Integer evaluate(Context context) {
        return value;
    }
}

That’s enough to make the testAddExpressionWithConstant succeed. Until now, we saw only the simplest forms of addition expressions, hence let’s try something more evolved. How difficult would be implemented ‘a + b + c’, given ‘a = 2, b = 4, c = 10′? The test below shows what we want to do.

@Test
public void testCompositeAddExpression() {
    final VariableExp a = new VariableExp("a");
    final VariableExp b = new VariableExp("b");
    final VariableExp c = new VariableExp("c");
    final AdditionExp add = new AdditionExp(a, new AdditionExp(b, c));
    final Context context = new Context();
    context.assign(a, 2);
    context.assign(b, 4);
    context.assign(c, 10);
    final Integer result = add.evaluate(context);
    Assert.assertSame(16, result);
}

Now we run the test, which already works without additional implementation! That’s because “the abstract syntax tree is an instance of the Composite pattern” (Gamma et al, p. 255).

new AdditionExp(a, new AdditionExp(b, c))

At this point we achieved the basis for the math expressions. And enough of addition operations! Following the same steps that brought us here should lead us very easily to subtraction, multiplication and division interpreters (although a division operation returning only Integer‘s is not useful at all, something we’ll have to get along for now). Simply replace the plus sign (‘+’) in the evaluate method by the subtraction sign (‘-’) to implement the SubtractionExp class and so on. Now, we are able to play with a more complex expression like ‘((a * c) + (b – c))’:

AdditionExp moreComplexExpression = new AdditionExp(new MultiplicationExp(a, c), new SubtractionExp(b, c));

In that case it’s also necessary to expand the grammar definition for the math expressions:

MathExp -> VariableExp | Constant | AddExp | SubtractionExp |
              MultiplicationExp | DivisionExp | '(' MathExp ')'
AddExp -> MathExp + MathExp
SubtractionExp -> MathExp - MathExp
MultiplicationExp -> MathExp * MathExp
DivisionExp -> MathExp / MathExp
VariableExp -> a | b | ... | z
Constant -> 0 | 1 | ... | 9

Currently we have a simple interpreter to the simplest math expressions. However we are responsible for creating the abstract syntax tree, what on the other hand can be done with a table-driven parser (as LL or LR parser).

That’s it for the time being.

Bibliography

Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995. ISBN: 0201633612.

Kent Back. Test-Driven Development by Example. Addison-Wesley, 2003. ISBN: 0321146530.

Pteco – A Prototype of Modeling Tool

Pteco is a software intended for mathematical modeling. Anyone can use it or collaborate with its development.

The mathematical modeling objective is to understand, and even to foresee, system behaviors, being used in a broad spectrum of human knowledge areas, like physics, engineering, chemistry, biology, meteorology, administration, economy, and others.

 

 

 

 

 

 

 

 

 

This project is divided in two parts:

• the core system, responsible for the execution of the mathematical algorithms;
• the GUI (graphical user interface), that deals with data input from diverse sources and the output of modeling results.

This separation is important to allow the core system to be reused in others softwares, and to make possible the separation of interests: some people enjoy GUI development, while others prefer to research mathematical algorithms.

Currently, Pteco can do only linear and non-linear regression. Your development began at FATEC – JD.

An Example of Use

A company could use Pteco to try to find some relation between a product’s price and its market-share. The relationship between this two variables could indicate that sales increase when the product’s price decrease and vice-versa, providing valuable information to define the company’s marketing strategy.

The Future…

We plan to implement more algorithms for mathematical modeling in the core system, like Multiple Linear Regression, non-Linear Regression, Logistic Regression, Diffuse Logic, among others.

The GUI will provide charts, capacity to import/export data to spreadsheet softwares and it will count on more complete reports about the constructed mathematical models.

Involving Yourself

If you want it, you can access the source code repository for this project and start coding.

References

• Mathematical Model – Wikipedia