Kerflyn's Blog

Well… It's a blog!

Archive for the ‘Programming’ Category

“Is this point inside this rectangle?” without IF

The class Point is given below. The hasCode() method uses an helper that you can find in guava. The method equals() contains the only if in this post (promised ;)).

public class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(x, y);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == null || !(obj instanceof Point)) {
            return false;
        }
        Point point = (Point) obj;
        return x == point.x && y == point.y;
    }
}

Here is the class Rectangle:

public class Rectangle {
    public final Point start;
    public final Point end;

    public Rectangle(Point start, Point end) {
        this.start = start;
        this.end = end;
    }
}

I suppose that start.x < end.x and that start.y < end.y

I define the minimum and the maximum of two points as the point which coordinates are respectively the minimum and the maximum of the coordinates of the given points. For example, the minimum of the points (1, 4) and (3, 2) is (1, 2), and the maximum is (3, 4).

public class Points {
    // it's an utility class
    private Points() { throw new UnsupportedOperationException(); }

    public static Point min(Point p1, Point p2) {
        return new Point(Math.min(p1.x, p2.x), Math.min(p1.y, p2.y));
    }

    public static Point max(Point p1, Point p2) {
        return new Point(Math.max(p1.x, p2.x), Math.max(p1.y, p2.y));
    }
}

Now, I give the method Rectangle.contains() that checks if a point is inside a rectangle. The idea is to use the methods min() and max() between the given point and the rectangle edges as filters: if the computed point is different from the given point, then the given point is not in the rectangle.

import static Points.*;

public class Rectangle {
    // see code above...

    public boolean contains(Point point) {
        return point.equals(max(start, min(end, point)));
    }
}

Written by fsarradin

2011/05/04 at 07:01

Posted in Programming

Tagged with ,

Playing with Scala’s pattern matching

How many times have you been stuck in your frustration because you were unable to use strings as entries in switch-case statements. Such an ability would be really useful for example to analyze the arguments of your application or to parse a file, or any content of a string. Meanwhile, you have to write a series of if-else-if statements (and this is annoying). Another solution is to use a hash map, where the keys are those strings and values are the associated reified processes, for example a Runnable or a Callable in Java (but this is not really natural, long to develop, and boring too).

If a switch-case statement that accepts strings as entries would be a revolution for you, the Scala’s pattern matching says that this is not enough! Indeed, there are other cases where a series of if-else-if statements would be generously transformed into a look-alike switch-case statement. For example, it would be really nice to simplify a series of instanceof and cast included in if-else-if to execute the good process according to the type of a parameter.

In this post, we see the power of the Scala’s pattern matching in different use cases.

Notice that the pattern matching is not something new. It is something that appears already in some other languages like OCaml, Haskell. A kind of pattern matching also exits in Prolog, but it uses a far different mechanism (unification in this case).

Traditional approach

There is an approach to the Scala’s pattern matching that looks similar to the switch-case structure in C and Java: each case entry use an integer or any scalar type. Here is an example:

def toYesOrNo(choice: Int): String = choice match {
    case 1 => "yes"
    case 0 => "no"
    case _ => "error"
  }

So if  you enter toYesOrNo(1), Scala says “yes”. And if you enter toYesOrNo(2), Scala says “error”. Notice that the symbol _ is used to formulate the default case.You also have to remark that there is no need to use the break statement.

But if you want that Scala says “yes” when you enter toYesOrNo(1), toYesOrNo(2), or toYesOrNo(3), you will write the function like this:

def toYesOrNo(choice: Int): String = choice match {
    case 1 | 2 | 3 => "yes"
    case 0 => "no"
    case _ => "error"
  }

Now, you can use a string for each case entry. Using strings is interesting when you want to parse options of your applications:

def parseArgument(arg: String) = arg match {
    case "-h" | "--help" => displayHelp
    case "-v" | "--version" => displayVerion
    case whatever => unknownArgument(whatever)
  }

So if you enter parseArgument(“-h”) or parseArgument(“–help”), Scala calls the displayHelp function. And if you enter parseArgument(“huh?”), Scala calls unknownArgument(“huh?”).

Notice that I have not used _ for the default case. Instead, I have put an identifier as its value is used in the associated instruction.

Typed pattern

Sometimes in Java, you have to deal with an instance of something that appears like an Object or any high level classes or interfaces. After checking for nullity, you have to use series of if-else statements and instanceof-cast to check the class or the interface that the instance extends or implements, before using it and processing the instance correctly. This the case when you have to override the equals() method in Java. Here is the way Scala sees the thing:

def f(x: Any): String = x match {
    case i:Int => "integer: " + i
    case _:Double => "a double"
    case s:String => "I want to say " + s
  }
  • f(1) → “integer: 1”
  • f(1.0) → “a double”
  • f(“hello”) → “I want to say hello”

Is not it better than a succession of if+instanceof+cast?

This kind of pattern matching is useful to walk through a structure using the composite design pattern. For example, you can use it to explore the DOM of an XML document or the object model of a JSON message.

Functional approach to pattern matching

A side effect of such a matching is that it provides an alternative way to design functions. For example, consider the factorial function. If you choose the recursive version, usually, you would define it like this:

def fact(n: Int): Int =
    if (n == 0) 1
    else n * fact(n - 1)

But you can use Scala’s pattern matching in this case:

def fact(n: Int): Int = n match {
    case 0 => 1
    case n => n * fact(n - 1)
  }

Notice the use of the variable n in this case. It is matched with any value that does not appears in the preceding cases. You have to understand that the n in the last case is not the same as the one used in the function signature. If you wanted to use the parameter n and not a new variable with the same name, you have to delimit the variable name with back-quote in the case definition, like this: `n`

Here is a simple way to build you factorial function in Scala:

def fact(n) = (1 to n).foldLeft(1) { _ * _ }

Pattern matching and collection: the look-alike approach

Pattern matching may be applied to the collections. Below is a function that computes the length of a list without pattern matching:

def length[A](list : List[A]) : Int = {
    if (list.isEmpty) 0
    else 1 + length(list.tail)
  }

Here is the same function with pattern matching:

def length[A](list : List[A]) : Int = list match {
    case _ :: tail => 1 + length(tail)
    case Nil => 0
  }

In this function, there are two cases. The last one checks if the list is empty with the Nil value. The first one checks if there is at least one element is the list. The notation _ :: tail should be understood “a list with whatever head followed by a tail”. Here the tail can be Nil (ie. empty list) or a non-empty list.

To go further, we will use this approach with tuples in order to improve our method parserArgument() above:

  def parseArgument(arg : String, value: Any) = (arg, value) match {
    case ("-l", lang) => setLanguageTo(lang)
    case ("-o" | "--optim", n : Int) if ((0 < n) && (n <= 5)) => setOptimizationLevelTo(n)
    case ("-o" | "--optim", badLevel) => badOptimizationLevel(badLevel)
    case ("-h" | "--help", null) => displayHelp()
    case bad => badArgument(bad)
  }

Notice first the use of the operator | that allows to match alternative forms of arg inside the tuple. Notice also the use of two patterns for options -o and --optim. These patterns are distinguished by the use of a guard condition. The guard conditions help you to get fine tuned pattern matching when pattern matching alone is not enough.

Advanced pattern matching: case class

Case classes are classes with part of their behavior predefined in order to make easier their construction and their use in a pattern. Case classes enables you to manipulate parameterized symbols for example, parsed by a compiler or used by your internal Domain Specific Language (DSL).

The example below shows how to use case classes and pattern matching in order to build simple mathematical expressions, evaluate them, and compute their derivative. First, lets define the symbol to represent expressions: the variable X, constants, addition, multiplication, and the negative operator (for the fun!). Here sealed means that there is no other children of the class Expression outside of the namespace.

  sealed abstract class Expression
  case class X() extends Expression
  case class Const(value : Int) extends Expression
  case class Add(left : Expression, right : Expression) extends Expression
  case class Mult(left : Expression, right : Expression) extends Expression
  case class Neg(expr : Expression) extends Expression

Now, lets define a function to evaluate expressions with a given value for the variable by using pattern matching.

  def eval(expression : Expression, xValue : Int) : Int = expression match {
    case X() => xValue
    case Const(cst) => cst
    case Add(left, right) => eval(left, xValue) + eval(right, xValue)
    case Mult(left, right) => eval(left, xValue) * eval(right, xValue)
    case Neg(expr) => - eval(expr, xValue)
  }

Lets try the eval() function:

val expr = Add(Const(1), Mult(Const(2), Mult(X(), X())))  // 1 + 2 * X*X
assert(eval(expr, 3) == 19)

Now, we define a function that compute the (unreduced) derivative of an expression:

  def deriv(expression : Expression) : Expression = expression match {
    case X() => Const(1)
    case Const(_) => Const(0)
    case Add(left, right) => Add(deriv(left), deriv(right))
    case Mult(left, right) => Add(Mult(deriv(left), right), Mult(left, deriv(right)))
    case Neg(expr) => Neg(deriv(expr))
  }

Lets try the deriv() function:

val df = deriv(expr)

Here is what you get in df:

Add(Const(0),Add(Mult(Const(0),Mult(X(),X())),Mult(Const(2),Add(Mult(Const(1),X()),Mult(X(),Const(1))))))
// = 0 + (0 * X*X + 2 * (1*X + X*1)) = 4 * X
assert(eval(df, 3), 12)

Other advanced pattern matching features

There are some special notations used in the Scala’s pattern matching. Scala allows to put aliases on patterns or on parts of a pattern. The alias is put before the part of the pattern, separated by @. For example, in the expression address @ Address(_, _, "Paris", "France"), we want any addresses in Paris/France, but we do not care about its content after the match is done. So after, we just use the alias address.

There is also a specific notation to match sequences with _*. It matches zero, one or more elements in a sequence to its end.

In Scala, pattern matching does not appears only after a the function match. You can put pattern matching in any closure and also in a catch block.

You can provide your own behavior for pattern matching. This is called extractor. To do so, you have to provide your own implementation of the unapply() method (and/or unapplySeq() for a sequence).

Conclusion

In this post, we have seen different ways to use the pattern matching with Scala. The main advantage of such a feature is to provide an easy way to build alternative structures based the matching of scalar values, strings, collections, but also types and parameterized symbols. For me, pattern matching is one of the sexiest alternatives to if statements! A good use of pattern matching can make your program really readable and helps you to build an internal DSL.

Written by fsarradin

2011/02/14 at 18:52

Posted in Programming

Tagged with , ,

[FAQ] Learn To Program In Python

Here is a small FAQ about how to become a programmer in Python and making progress. Do not expect this FAQ to be completely logical. Python’s name comes from Monty Python’s Flying Circus. So you have to experience the language to appreciate it… before to think ;p

Python is simple, so becoming a Python programmer is simple too!

How to learn to program in Python?

The answer is simple! Go to the address http://www.python.org/doc/ and click on the Tutorial link.

Once you have done with the tutorial, you will not be a strong Python programmer. In fact, at the end, you will be able to put most of your ideas into a Python script. It helps if you have experienced programming with another language and if you have some knowledge in object-oriented programming (OOP) — the last is optional. But, above all, it is necessary to have a sufficient open mind.

How to be a better Python programmer?

The answer is simple! Practice Python and read the source code of the files in the Python standard library ($PYTHONPATH/Lib).

Do not fear that kind of code, it will not bite you! By doing this, you will learn some patterns and some idioms used in Python. The bulk of the source code in the standard library is sufficiently clear.

How to become a strong Python programmer?

The answer is simple! Read the PEPs (Python Enhancement Proposals) starting from this one http://www.python.org/dev/peps/ and use google.

Here the goal is to explore what is unknown by most of the programmer or by other language. Do you know what is a generator or a decorator? Can the list comprehension make my life as a developer better? And what about the database API? The answers are in the PEPs and google.

For example, to learn more about Python’s decorators, take a look at http://www.python.org/dev/peps/pep-0318/.

Is this enough?

The answer is simple! Absolutely not!

All the answers here should be considered as starting points. After that, there are many things to explore. But, you have to do the same thing you would do with another language to improve your skill: explore forums, listen to conferences, answer to questions, and contribute.

To Infinity And Beyond

$ python -c "import this"
The Zen of Python, by Tim Peters

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

Written by fsarradin

2010/09/26 at 16:06

Posted in Programming

Tagged with ,

Homemade context management

A stateless application component is a component that looks like a mathematical function. By definition, a mathematical function always returns the same result providing that you enter the same parameters. If a component follows such a definition, it is easier to test, because the component is decoupled from the rest of the application. Moreover, it is safer in case of concurrency.

If you want application components as stateless as possible, you have to manage a context, in order to export and manipulate the component state outside of the component. A context can be a complex structure that contains all the configuration elements needed by a component or more to run.

There are two kinds of context:

  • The application context is a context that is built during the load time and that do not change during the application life. Spring and Java CDI have such an approach.
  • The session context is a context that is built dynamically at a specific phase during the runtime.

In this post, we see this last case of context: the session context.

Interface

A context can be seen as a set of objects. Each object is identified by a name.

Here is an interface to represent contexts:

public interface Context {
    void register(String name, Object o);
    Object get(String name);
    <T> T get(String name, Class<T> contract);
    <T> T get(Class<T> contract);
    Context getParent();
}

Contexts can be organized in a hierarchical structure. A context has a parent context. All registered objects in the parent context is accessible to the child context. This help not to redefine abusively previously registered objects.

There are three methods to get a registered object in a context or its parent:

  • get(name) is the easiest one, but its drawback is to return an Object and not something more specific like a String, a Date, a BigDecimal, or anything else. So, if you know what it is, you have to cast the result. Otherwise, the result might not be directly useful.
  • get(name, contract) applies a check on the returned type according to the contract. The contract may be a class, a super-class, or an interface. What is return is of the type of the contract. Notice that get(name, Object.class) is the same as get(name).
  • get(contract) searches the first registered object which type matches or inherits of the given contract.

Implementation

Here is the class to generate contexts.

public class Contexts {
    public static final NULL = new NullContextImpl();

    private Contexts() {
        throw new UnsupportedOperationException();
    }

    public static Context create() {
        return new ContextImpl(NULL);
    }

    public static Context create(Context parent) {
        return new ContextImpl(parent);
    }

    /* Implementation of context classes (see later...) */
}

You can get or create three types of contexts:

  • A null context that is the parent of all contexts.
  • A top-level context with create(), which is a context without parent (more exactly, a context which parent is the null context).
  • An ordinary context with create(parent), which has a parent context.

A null context is defined. In fact, it is the top parent of all contexts. The null context is built according to the Null Object pattern. Every get() method throws a NoSuchElementException.

private static class NullContextImpl implements Context {
    public Context getParent() { return this; }

    public void register(String name, Object o) {
        throw new UnsupportedOperationException();
    }

    public Object get(String name) {
        throw new NoSuchElementException();
    }

    public <T> T get(String name, Class<T> contract) {
        throw new NoSuchElementException();
    }

    public <T> T get(Class<T> contract) {
        throw new NoSuchElementException();
    }
}

Here is a simple implementation of a context. It is not intended to be thread-safe nor to be scalable. In order to be improved, cache can be used in the method get(contract).

private static class ContextImpl implements Context {

    private final Context parent;

    private final Map<String, Object> objects;

    public ContextImpl(Context parent) {
        this.parent = parent;
        this.objects = new HashMap<String, Object>();
    }

    public void register(String name, Object o) {
        objects.put(name, o);
    }

    public Object get(String name) {
        if (objects.containsKey(name)) {
            return objects.get(name);
        }
        return parent.get(name);
    }

    public <T> T get(String name, Class<T> contract) {
        if (objects.containsKey(name)) {
            return contract.cast(objects.get(name));
        }
        return parent.get(name, contract);
    }

    public <T> T get(Class<T> contract) {
        for(Object o : objects.values()) {
            if (contract.isInstance(o)) {
                return (T) o;
            }
        }
        return parent.get(contract);
    }

    public Context getParent() { return parent; }
}

We can notice that for each get() method, either the method internally succeeds or it calls the get() method of the parent. And as the null context is the parent of every context, if each get() fails, a NoSuchElementException is thrown.

Example

Here is some examples that use our context implementation:

Context context = Context.create();

context.register("message-en", "hello");
context.register("message-fr", "salut");

System.out.println(context.get("message-en"));               // display: hello
System.out.println(context.get("message-fr", String.class)); // display: salut
System.out.println(context.get(String.class));               // display "hello" or "salut"

Now, let’s get a more concrete example. Suppose that you manage message persistency through a DAO. We have a DAO based on the interface MessageDao and using the XML medium. Here is the preparation of the DAO in a main context.

public void init() {
    Context mainContext = Context.create();

    MessageDao messageDao = new XmlMessageDao(file);
    mainContext.register("messageDao", messageDao);
}

In the main context, the element lifespan is the same as the main component one.

Now, to call the sub-component, we have to prepare a specific context. But we do not want to copy/paste the main context. So, we set the parent of the newly created context as the main context and build the new context.

public void callComponent() {
    Context context = Context.create(mainContext);

    // specific context composition for the sub-component call...

    component.call(context);
}

Now, we wanted to use the DAO in a sub-component.

public void call(Context context) {
    // create an entity
    Message myMessage = new Message():

    // save it
    context.get(MessageDao.class).save(myMessage);
}

For the last line above, we can notice that if an object is a singleton inside a context, there are different ways to access it, especially if it is part of an inheritance tree. Indeed, we might use the class XmlMessageDao, instead of MessageDao. But in this case, the use of MessageDao is better because it helps to decoupled the application from the implementation of its components.

Annexe

Written by fsarradin

2010/09/15 at 01:24

About Sustainable Software Development

I try to explore some aspect around sustainable development applied to IT. At present, I see two ways of understanding this term.

Green IT: respect to the environment

This is the first thing I think of when I hear “sustainable development”: adopt a behavior that take care of the environment. We are not at the level of the infrastructure, that is the usual field when we speak about green IT. Here, I think about the way we program: the choice should be made across the algorithms and the patterns that do not increase so much the computer temperature and that consume less resources.

  • Choose a low-consumption algorithm
  • Have a behavior that conducts to respect the environment
  • Choose a greener language implementation

The language and more specifically the way it is implemented (i.e. the way your source code is compiled and interpreted) has its importance in relation to green IT. One day, I have heard of a company that has abandoned PHP. Indeed, at this time, the way the PHP engine was implemented implied a high-rate in energy consumption.

But green IT drives us to difficult equations. Certain modifications in the code, in order to turn it to green code, can turn the other part of the code to high-rate in energy consumption. What are the good behavior that a developer should adopt in order to become a green developer? May we, one day, see a label for eco-software craftsman?

IT craftsmanship

There is another aspect behind the “sustainable development” that can be represented by a question: How long will your code last? It is of the interest of a project to create a code that last in time. Not only for the developer himself but also for others. So, there is the question to become a perfect “software craftsman“.

  • The code source is a document that describes how the software works. Thus, write your code so that any other sources of document (specifications, code comments, tests) become useless. By acting like this, any developer will not spent too many time to understand your code and it will not require heavy maintenance in order to evolve.
  • Use of: best practices, design pattern, struggle against anti-pattern, some idioms. Do not use them without a preliminary reflexion, because a pattern can easily turned to a anti-pattern or an idiom can make your code unreadable.

Again, the software craftsmanship is a difficult exercise. On the one side, it requires a strong experience in software development. On the other side, more and more techniques or practices emerge in order to help you create a clean code. I think specifically about TDD, TDR, refactoring, and other practices. Furthermore, IT tools to analyze your code (Checkstyle, PMD, or Sonar in the Java world) help you to make progress in order to provide a better code.

Conclusion

Regardless on how “sustainable IT development” is understood, it requires experience and practice, because we have to think about a wide range of parameters that acts on how the resources are consumed or how the other developers will perceive our code. Nevertheless, there are tools to help us producing clean code and if you are confident in the future, tools will be created to help us producing green code.

Written by fsarradin

2010/08/02 at 18:06

List Comprehension in Groovy

At present, I am discovering the language Groovy. It is a flexible language. You can choose between dynamic or static type. It provides closures. And above all, it produces Java bytecode after a compilation. These points make Groovy an exciting language.

For me, Groovy is a language that stands between Python and Java. And I really like these two languages. But I was a bit disappointed because there is no explicit syntax to express list comprehension. What a shame! This is really useful because you can create, for example, many kind of lists in one line in a intuitive way… In fact, I was wrong.

Here, we will see how to express the list comprehension in Groovy. We will generate lists in one line of code and even mappings.

List comprehension and Groovy

A list comprehension is syntactic construct that enables you to built lists (or even all kind of collections) in a declarative way. That is to say that you do not have to put values one by one in the list by hand or with the help of a loop and a set of instructions. In fact, the values are automatically computed through a generic description you have provided. For example, you want L be the set of all square integers, for even integers between 1 and 10. This is the mathematical way of expressing it:

L = {  x² | x ∈ {1, …, 10} ∧ x mod 2 = 0 }

Thus, L is the set {4, 16, 36, 64, 100}.

In Python, you will write this:

L = [x**2 for x in range(1, 11) if x % 2 == 0]

But how to write this in Groovy? In Groovy, you can create list in a declarative way by specifying a range. A range is declared by using the double-point notation (..):

assert 1..10 == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The method collect() can apply a closure on each element of a list in order to built a new list that contains the results of the closure.

assert (1..10).collect { it**2 } == [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Now, we have to reduce this list in order to meet the definition of L, describes above. To apply a filter on the list elements, I use the method findAll().

L = (1..10).findAll({ it % 2 == 0 }).collect { it**2 }

Or, in order to have a more explicit notation:

L = (1..10).findAll({ x -> x % 2 == 0  }).collect { x -> x**2 }

Thus, at the end, L is equal to [4, 16, 36, 64, 100].

Now suppose that you have the function randomString(n) that generate strings of size n with random content. You want to generate a list with 10 random strings of size 5:

println((1..10).collect { randomString(5) })

Convert a map into a list

Let’s go beyond! Suppose we have a set of characters: C = { ‘A’, …, ‘J’ }. You want to produce a map between each character of C and its number in the alphabet. Thus, you to have M = { ‘A’: 1, ‘B’:2, …, ‘J’: 10 }.

In Python, you write something like that:

M = dict([(C[i], i) for i in range(len(C))])

In Groovy, we need the help of the method inject(). inject() is a method that takes two arguments: an initial value and a closure. inject() iterates through the element of a collection. these elements are used by the closure in order to produce a new value from the preceding one, starting with the initial value. For example, with an initial value to 0 and a closure that adds two elements, the result of inject() is the sum of all elements in the collection:

assert (1..5).inject(0) { oldValue, element -> element + oldValue } == 15

With an initial value to 1 and a closure that multiplies two elements, the result is the product of all the element of the collection (it is also a Groovy way to have a simple implementation of the factorial function).

Now here is the answer to our initial problem. Let C be declared as def C = 'A'..'J'. The idea is to start with an empty map and to add an entry in this map for each visited element.

(1..C.size()).inject([:]) { m, i -> m[C[i-1]] = i; m }

The result is [A:1, B:2, C:3, D:4, E:5, F:6, G:7, H:8, I:9, J:10].

Conclusion

The bad news are that there is no syntactic sugar in Groovy in order to implement the list comprehension. But I do not say that you cannot implement such a structure. Indeed, we have seen that with methods like findAll(), collect(), or inject() and with the help of closures, we are able to express the list comprehension without adding extra language features.

Written by fsarradin

2010/06/25 at 12:51

Posted in Programming

Tagged with ,