Century Minds

Never, ever try to do this:

sudo cpan VIM::Packager

It will download the whole internet on your computer!

It’s been a while since the last time I wrote something here. It turns out that I have been tinkering with ANTLR for the last nine months as part of my new job. So my idea is to write a series of posts to teach you how to create your own languages with ANTLR.

ANTLR is a pretty good top-down LL(*) lexer and parser that allows us to define languages/DSLs without the restrictions of developing it inside a host language, as Java. As a drawback, writting a language with a parser is much more complicated that hosted DSLs.

I really think that the best way of learning any technology is to practice. That is why I am going to do it in a practical way, building a small language: a dependency injection language.

We are going to implement a language to define beans and give values to its attributes via setters or contructors. The value types allowed for attributes will be:

• References to other beans
• Basic types: String, Integer, Long, boolean.
• Lists
• Maps

In addition, it will allow us to define a default prefix package for beans that will ease the declaration of the bean type. So for example, we might define a bean type as “dao.UserDAO” instead of the more verbose “com.centuryminds.tutorial.dao.UserDAO”.

# This is a comment
default package prefix com.centuryminds.tutorial

def bean userDAO1 of type dao.UserDAO as
   tableName: "test"
   cacheSize: 200
end

def bean userDAO2 of type dao.UserDAO as
   init "test", 200 # constructor params
   otherAttribute: "other"
end

def bean userManager of type manager.UserManager as
   userDAO: userDAO1
end

def bean myBean of type com.nodefaultpackage.bean.Mybean as
   listVar: ["test", "othertest"]
   mapVar: {"test": 3, "another": 4}
end

ANTLR basics

A parser constructed with a tool like ANTLR needs to be splitted into several phases. In this way each part keeps simpler. These phases generally are the following:

• Lexer: It reads a character stream and generates a sequential list of recognized tokens.
• Parser: It receives a list of tokens and identifies the structure of the sentences according to the grammar. Once we have identified the structure we can generate two kinds of outputs: 1) Simply generate the final compiler output or 2) Go further and generate an Abstract Syntax Tree (AST henceforth) for later validations/manipulations.
• AST Semantic Validation Phase: Once we’ve finished validating the source structure, we have to validate it semantically. A semantic error means something is grammatically correct but completly meaningless. This phase can be invoked plenty of times and/or work in association with a pre-semantic phase, depending on the grammar complexity.
• AST Manipulation Phases: Once we know that what the source code “says” is correct and meaningful, we can pass it through a set of AST manipulation phases that transform the tree representing the code into something more specialized, optimized, etc. For example, removing unused variables, adding extra functionality, static check for nulls, and so forth.
• Output Generation Phase: This is the last phase of a compiler, in which we generate the output: x86 code, Java code, bytecode, xml, whatever you want.

Do we need all the phases? Of course not, it depends totally on the complexity of the grammar. The mandatory ones are lexer and parser.

As for our small language, we’ll implement the following phases:

• Lexer/Parser: With ANTLR you can define both in the same grammar file.
• Pre-semantic phase: We are going to identify all the beans present in a file and its associated class types. This will permit us to not depend on the order the beans are defined (without this phase we wouldn’t be able to reference another bean that is defined below in the file, since we haven’t parsed that bean yet).
• Semantic validation: Validation of all the types of the code. Has UserManager a field “dao” that is of type UserDAO? Does UserDAO has a field named “table” of type string that we can assign the literal “myTable”?
• Output generation phase: In our case it is going to be a Java object structure ready to be accessed by our DI framework. Other options comprise the generation of a Spring XML file, Guice code, etc.

Basic ANTLR Examples

To develop with ANTLR I recommend ANTLRWorks. This tool is a specialized IDE that supports the definition of ANTLR based languages. Furthermore, with it (and with its built-in debugger!) we’ll be able to test our lexer/parsers.

Let’s start off with a basic example:

grammar Injector;
options {
 output=AST;
}
tokens{
 BEANS;
 BEAN;
 PACKAGE_LIST;
}
@header {
package com.centuryminds.injector;
}
@lexer::header
{
package com.centuryminds.injector;
}

beans	:	beanDef+ -> ^(BEANS beanDef+)
;

beanDef: 'def' Identifier 'of' 'type' packageName -> ^(BEAN Identifier packageName)
;

packageName
	: Identifier ('.' Identifier)*	-> ^(PACKAGE_LIST Identifier+)
;

Identifier    : LETTER ( LETTER | '0'..'9' | '_' )*
;

fragment
LETTER: ('a'..'z' | 'A'..'Z')
;

WS  :  (' '|'\t') {$channel=HIDDEN;}
    ;
NEWLINE : ('\n'|'\r' ) {$channel=HIDDEN;}
    ;

LINE_COMMENT
    : '#' ~('\n'|'\r')* '\r'? NEWLINE {$channel=HIDDEN;}
    ;

This grammar recognizes this kind of source code:

def bean1 of type one.example.Example
def bean2 of type another.example
def bean3 of type NoPackage

This is the AST generated one the code above has been parsed using our grammar:

But, let’s take a look at each statement in the grammar file:

First of all, we define the grammar name:

grammar Injector;

It’s vital that the grammar file is named accordingly to the grammar name. In this case the file would be named “Injector.g”

In the next line we define that the output of the parser will be an AST:

options {
 output=AST;
}

These lines:

tokens{
 BEANS;
 BEAN;
 PACKAGE_LIST;
}

describe tokens that have not been read from the input -aka virtual tokens, but generated by the parser. In the example, we create three virtual tokens, one for the Beans list, one for each bean definition and one for a Java package definition.

The following lines set the Java package for the generated Lexer and Parser:

@header {
package com.centuryminds.injector;
}
@lexer::header
{
package com.centuryminds.injector;
}

After this header code, we have two kinds of statements: token definitions and rules definitions. Tokens are recognized by the lexer. Rules are applied by the parser to identify the structure of the source code.

Tokens can be defined in two ways:

• As a named token:

  WORD: ('a'..'z' | 'A'..'Z')+

  It might be referenced by other Tokens/Rules as to avoid repeated code. The name of the tokens must start with an upper case letter. E.g. “Word” is a valid token identifier, “word” is not ( It will be identified as an action).

• As an anonymous token inside a rule:

  rule: 'define' 'alias' WORD 'as' WORD

  where ‘define’, ‘alias’ and ‘as’ are anonymous tokens.

We can also define fragment tokens. These are not really tokens by themselves, but fragments to avoid repetition. For example, LETTER fragment in the following code:

Identifier    : LETTER ( LETTER | '0'..'9' | '_' )*
;

fragment
LETTER: ('a'..'z' | 'A'..'Z')
;

Oftentimes, we don’t want some tokens to be visible for the parser, so that it doesn’t have to deal with them. In this case, we can ignore them or locate them inside a different token channel. There is a special channel named HIDDEN that maintains the information but hides it to the parser. In our example we hide the whitespaces, new lines and comments.

WS  :  (' '|'\t') {$channel=HIDDEN;}
    ;
NEWLINE : ('\n'|'\r' ) {$channel=HIDDEN;}
    ;

LINE_COMMENT
    : '#' ~('\n'|'\r')* '\r'? NEWLINE {$channel=HIDDEN;}
    ;

Finally, we define the rules:

beans	:	beanDef+ -> ^(BEANS beanDef+)
;

beanDef: 'def' Identifier 'of' 'type' packageName -> ^(BEAN Identifier packageName)
;

packageName
	: Identifier ('.' Identifier)*	-> ^(PACKAGE_LIST Identifier+)
;

A rule has the following syntax for AST generation:

ruleName : ruleAction  -> ^(ROOT_ELEMENT child1 child2 ...);

For example:

beanDef: 'def' Identifier 'of' 'type' packageName -> ^(BEAN Identifier packageName);

Here you are a rule named beanDef that recognizes “def myBean of type a.b.c”-like strings. In order to recognize the package name it invokes a sub-rule called packageName that in turn returns a sub-AST. Once we parse the structure, we build its corresponding AST with the virtual token BEAN as root, Identifier as the first child and packageName sub tree as the second one.

Of course a rule can have more options: rule parameters, return types, init blocks, etc. I recommend to take a look at the documentation, or await the next tutorial :).

Arbitrary Java code can be attached at any moment of the parsing:

beanDef: 'def' {System.out.println("after def");}
              Identifier  {System.out.println("Identifier: "+ $Identifier.text);}
              'of' 'type' packageName  {System.out.println("end of the rule");}
               -> ^(BEAN Identifier packageName);

The ANTLR tokens and rules can be accessed from this Java code: 1) The token text can be retrieved in the form $Identifier.text. 2) The AST corresponding to the sub-rule using $packageName.start

I’m wrapping it up. In the second part of this tutorial we will see the complete grammar file and the pre-semantic phase. Meanwhile, you can try to complete the grammar as an exercise.

Links:

• ANTLR official site
• “The Definitive ANTLR Reference” book written by Terence Parr, the creator of ANTLR

We are going to learn a bit about a useful tool to help us make decisions prioritizing some traits of our work over the remainder ones. Let me introduce you to the cost-time-quality triangle:

The triangle itself is nothing new or recently discovered, I am sure every manager worldwide is aware of it, or at least should be! Basically, what we have is a set of three properties (quality, cost and time), and the point here is that, at a given point in time, you can only count on two of them. In other words, if we applied this to a wide range of ways to accomplish with a task, it tells us that we can´t wind up with a cheap and high-quality result in a short time. I will refer to the title of this post: you can only have two. With three elements at play, picking them two by two, we get three possibilities:

A) Quality & Time

High-quality solutions in short times. A steal? Uhmm, beware the available budget!

B) Cost & Time

Cheap and swift, then? The quality will suffer!

C) Quality & Cost

Cheap and good? Be sure you finish it in a realistic span of time! Crackin’ the whip would help …

No combination is better than the others, it depends on your situation. Personally, I find the hardest part to find a balance between the three of them so that you feel sort of successful when you finish the task.

Hace tiempo que tengo ganas de escribir algo. Después de las presiones recibidas por Rubén y tras ver que Colin y Mikel también se han animado a escribir, no tengo más excusas. Aunque para mi primer post no hablaré sobre Java. De momento, no voy a escribir nada sobre: OSGi, Java 6, Apache Mina, Aplicacione distribuidas, etc. Aunque estoy deseando empezar a hablar sobre estos temas.

Para mi debut en el blog, voy a contar brevemente mis primeras impresiones con mi nueva consola: Nintendo Wii. Soy un jugador casual de videojuegos a quien le gusta, sobre todo, jugar con sus amigos de vez en cuando. Aunque en estos momentos no tengo demasiado tiempo libre (tengo pendiente por leerme el Java Concurrency In Practice y la especificación de OSGi) me he comprado la consola sin dudarlo.

Después de estar una horas jugando la RedSteel en el salón, tipico mata-mata en primera persona, sólo puedo decir que es una pasada. La capacidad de inmersión en el juego es espectacular, gracias al mando. Esto de poder apuntar con el mando como si fuera una pistola le da una nueva vida a los “shot´em up”. Estoy deseando ver las aplicaciones del Wiimando en otro tipo de juegos.

Por otro lado, no he visto ningún problema para jugar con un proyector. Leí hace poco un post que decía que había problemas para jugar con la Wii en un proyector. Al parecer comentaba que existía perdida de precisión en el mando, debido a las distancia y al tamaño de la pantalla generada por el proyector. Yo he encontrado insignificante la perdida de precisión del mando en un proyector y queda compensada por el tamaño de la imagen

Por ultimo, este fin de semana voy a comprobar como de divertido es jugar con los amigos. Veremos si la consola pasa la prueba de la jugabilidad. Va a tener un duro juez, un amigo que piensa que el último juego divertido es el Emilio Butrageño del Amstrad CPC y que los juegos actuales son demasiado complicados.

Bueno, espero seguir contando más cosas, aunque creo que después de esto no me van a dejar volver escribir. A por cierto, este es mi Mii. He salido muy favorecido.

Loser (Beck)

“En todo sistema siempre puede encontrarse un cuello de botella”. Amén.

Esto es, a grandes rasgos, lo que dice la Teoría de las Restricciones (Theory of Constraints). Parece que hubiera sido Murphy el que tuvo la feliz idea de establecer esta teoría. Sin embargo, tal y como se dice aquí, la concepción inicial se atribuye al Dr. Eliyahu M. Goldratt, en concreto lo explica en su libro “The Goal” (que por supuesto no me he leído).

Como bien dice en su definición, la teoría se basa en la idea de que en un sistema dado existe siempre una restricción que limita (mina quizás se ajuste mejor a lo que se quiere expresar) la capacidad del propio sistema para cumplir con sus objetivos. La productividad global no es óptima debido a dicha restricción.

Intentaré explicar esta teoría (muy por encima) utilizando un ejemplo ilustrativo:

En el dibujo (pulsa en el él si quieres verlo maximizado) se refleja, de forma simplificada, el proceso de almacenamiento y distribución de productos de la empresa SGAE S.A. (Suministro de Grabaciones y Artículos de Extorsión, Sociedad Anónima), desde que llegan de la planta de fabricación hasta que llegan a los diversos clientes. Si tomamos esto como un sistema, podremos decir que está formado por 3 elementos (transporte, almacén y clientes) y que su cometido principal es obtener las máximas ventas posibles. Como podemos ver en la figura, los productos llegan al almacén transportados por un camión, y a continuación son distribuidos a los diversos clientes de la firma (dos en este caso): Peter Malgin y Walter Rible. Ambos están muy satisfecho con el servicio prestado
El Sr. Pérez Oso, presidente de la compañía, ha invertido una importante suma de dinero a lo largo del pasado trimestre en actividades publicitarias, y como resultado directo ha conseguido 2 nuevos clientes que prometen convertirse en importantes consumidores de su producto. Éstos se llaman Juanjo Dío y Marta Rada, que empiezan a realizar pedidos inmediatamente. Desde el Departamento de Organización y Gestión de Procesos de SGAE, previa aprobación por parte de Finanzas, se decide la compra de un nuevo trailer que permitirá satisfacer las necesidades de las dos nuevas incorporaciones a la cartera de clientes.

No pasan ni dos semanas cuando en el Departamento de Atención al Cliente se empiezan a recibir llamadas de los clientes (tanto nuevos como antiguos) quejándose por la lentitud y los contínuos retrasos en la recepción de sus pedidos. ¿Qué habrá pasado? Se compró un nuevo transporte para poder absorber el aumento de producción en la planta y aligerar el proceso de distribución a cliente final. Algo se escapa.

Se ordena un análisis del proceso de distribución a Organización y Gestión de Procesos, y al cabo de 3 días la conclusión es la siguiente:

“Desde que aumentamos la producción, el almacén está constantemente a su máxima capacidad”

He aquí lo que venía prediciendo la Teoría de las Restricciones. Ningún sistema se salva de tener un punto donde el trabajo se amontona (indicativo de dónde está el cuello de botella). En este caso, el problema evidentemente es el almacén. Inicialmente podía absorber la cantidad de material entrante, sin embargo, al aumentar éste, el almacén no puede despachar productos a más velocidad de la que llegan. Conclusión: almacén lleno. La consecuencias inmediatas de esto son 2:

• Los clientes no reciben la cantidad pedida del producto, por lo que su nivel de satisfacción y confianza en SGAE S.A. disminuye

• No se aprovecha el nivel de producción de la planta, esto es, visto en conjunto, en la práctica no se produce lo que potencialmente se es capaz de producir

La consecuencia global se puede resumir en 3 simples palabras: PÉRDIDA DE DINERO. Puesto que este sistema de distribución se había concebido para obtener los máximos beneficios posibles (y no es que no se consiga, ¡sino que se pierde dinero!), ha surgido un problema que hay que solucionar.

La solución inicial, tras un análisis minucioso de Organización y Gestión de Procesos, pasa por aumentar la capacidad del almacén (incluso se ha proyectado la construcción de uno nuevo mucho más grande). Se consideró otras opciones válidas, como disminuir el nivel de producción en planta, o incluso alguien del departamento propuso eliminar por completo el almacén y llevar los productos directamente de planta a cliente. Sin embargo, ambas se desestimaron finalmente, ya que la opción de aumentar la capacidad del almacén es la más económica a corto plazo. Así que, tras un mes de obras, SGAE S.A. cuenta con un almacén más grande con el que espera se solucionen los problemas de aprovisionamiento.
Aquí es donde la Teoría de las Restricciones alcanza su máximo esplendor. Si retomamos la definición, vemos que dice: “..SIEMPRE existe un cuello de botella”. Siempre. Pero, ¿cómo es posible si ya hemos aumentado la capacidad del almacén y éste nunca se llena? La Teoría de las Restricciones asegura que cuando se elimina una restricción, se crea otra en otra parte. Los cambios locales (o micro-optimizaciones) en el proceso nunca son suficientes. La mejora en la eficiencia se ha de realizar analizando el proceso como un todo y decidiendo en consecuencia qué cambiar.

En el ejemplo, al aumentar la capacidad del almacén evitando que éste se colapse, se ha desplazado el cuello de botella a otro lugar, ya sea a la capacidad de distribución del transporte o al nivel productivo de la planta. Quizás se podría poner otro camión que aumente el caudal de distribución entre la fábrica y el almacén, o se podría aumentar el nivel de producción en planta. Esto podría llevar nuevamente a un almacén lleno. Y vuelta a empezar… ¿se entiende por dónde va el asunto?

Por último, queda la gran pregunta del millón, ¿cómo encaja la Teoría de las Restricciones en el mundo de la Ingeniería del Software?

Después de esta breve introducción a la Teoría de las Restricciones, en próximos capítulos daremos un nuevo repaso a los flecos que hayan quedado pendientes y profundizaremos en la relación entre esta teoría y un proceso clásico de desarrollo de software como es RUP.

Mi primo Juan (Chambao)

Mi primer post. No me voy a enrollar, así que diré que aquí intentaré tratar temas relacionados con la Ingeniería del Software, Metodologías de Desarrollo y lenguajes como Java. La frecuencia de publicación será indefinida (depende de las ganas y la constancia de cada uno), pero no voy a postear todos los días ni una vez cada 6 meses. El objetivo principal de este blog es mejorar mi capacidad para ordenar y contar las ideas que me vayan surgiendo. Espero poder aprender de la experiencia. Pues eso, a ver qué sale de esto.

Un saludo!!

Pending …