Parser combinators (briefly explained)

Parser combinators allow you to create complex parsers from simpler ones, by combining them as if they were arithmetic operands.

As very well defined at Wikipedia:

In functional programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing locations in the string where parsing stopped successfully. Parser combinators enable a recursive descent parsing strategy that facilitates modular piecewise construction and testing. This parsing technique is called combinatory parsing.

The arithmetic operators you can use are:

  • a ~ b parse a sequence made of a then b
  • a | b introduce an alternative parser that parses a or b
  • a? introduce an optional parser
  • a* introduce on optional and repeatable parser
  • a+ introduce a repeatable parser
  • a ~> b like ~ but ignore the left member (a)
  • a <~ b like ~ but ignore the right member (b)

And that’s pretty much everything you need to know about parser combinators!
A very simple parser could be:

import scala.util.parsing.combinator._
import scala.util.matching.Regex
val parser = new RegexParsers {
  def mySuperSimpleParser= """\s*_end_$""".r ^^ { _.toString }
}

(which would recognice any string that ends with zero or more blank spaces and _end_, and return that string)

Here, what is enclosed between the curly brackets is a semantic action that is going to be executed.

So basically

a ^^ f

will parse a, and apply function f to the result (semantic action)

To parse a string we would simply do this:

parse(myParser, "my input string           _end_") match {
  case Success(matched,_) =>
    matched match{
      case "hello"=>
        println "hello world"
      case listOfArgs@h::t=> 
        MyParserHelper.executeAction(listOfArgs)
      case _=> 
        println( s"string $matched has been recognized, but I don't know what to do with it" )
    }
  case Failure(msg,_) =>   
    println("FAILURE PARSING STRING " + msg)
}

And will define myParser right now.

So far, we haven’t combined mySuperSimpleParser with anything, so let’s make it a little bit more complicated:
A still simple example coud be somethig like this:

def myParser = 
  (pHelp | pThreeArgs) <~ mySuperSimpleParser

where mySuperSimpleParser would (as we saw before) match any string ending in zero or more blanks plus the “_end_” string at the end of the input, but wouldn’t do anything with it, and would continue on the left side on the input either parsing pHelp or pThreeArgs:
pHelp could be something like this:

def pHelp=  
  "(help|helpMe)".r ^^ { _=> HelpCommand }

HelpCommand is a case class that, for the sake of simplicity we will not define here, but we could also do something like:

def pHelp = 
  "(help|helpMe)".r ^^ { _=>"the recogniced command is help" }

Or even:

def pHelp = 
  "(help|helpMe)".r

We don’t even need to take any semantic action on it if we do not want to.

The only thing left now is the pThreeArgs parser. This parser will recognice a secuence of three words (first one word, then another, and then another) and put the three of them, sequencially into a list, and that list is what will be returned:

def pThreeArgs: Parser[List[Any]] = {
  var paramsCtx=mutable.ListBuffer[String]()
  pListParam(paramsCtx) ~> pListParam(paramsCtx) ~> pListParam(paramsCtx) ^^ {_.toList}
}

Note, that I created a mutable ListBuffer, which will act as a “global” context to each of the three parsers that we are combining, so that they only worry about parsing one parameter and storing it on the global context that they have received as a function parameter (these parsers are functions).
At the end, the whole List, containing the three parameters, will be returned 🙂

Can you think of a better (or more functional way of doing it? 😉 )
pListParam would be something like that:

def pListParam(l:mutable.ListBuffer[String])= 
  """\S+""".r ^^ {l+=_.toString}

For a more complete example, please look here

Anuncios

Parser combinators (brevemente explicados)

Los parser combinators te permiten crear parser más complejos a partir de otros más sencillos, combinándolos como si fuesen operadores aritméticos.

Perfectamente definido queda en Wikipedia:

En programación funcional, un parser combinator es una función de orden superior que acepta múltiples parsers como entrada y devuelve un nuevo parser como salida. En este contexto, un parser es una función que acepta strings como entrada y devuelve una cierta estructura como salida, típicamente un árbol de parseo o un conjunto de índices que representan las localizaciones en el string donde el parser paró satisfactoriamente. Los parser combinators habilitan una estrategia recursiva descendente de parseo, estrategia que facilita la construcción y testeo modular. Esta técnica de parseo se denomina parseo combinatorio.

Los operadores aritméticos que puedes usar son:

  • a ~ b Parseo de una sequencia compuesta de ‘a’ y después ‘b’
  • a | b Parser alternativo de ‘a’ o ‘b’
  • a? Parser opcional de ‘a’
  • a* Parser opcional y repetible
  • a+ Parser repetible
  • a ~> b Como el operador ~ pero ignorando el miembro izquierdo (a)
  • a <~ b Como el operador ~ pero ignorando el miembro derecho (b)

Y en esencia, eso es lo que necesitas saber sobre parser combinators 🙂
Un parser muy sencillo podría ser:

import scala.util.parsing.combinator._
import scala.util.matching.Regex
val parser = new RegexParsers {
  def mySuperSimpleParser= """\s*_end_$""".r ^^ { _.toString }
}

Debería reconocer cualquier string que termine con cero o más espacios y la cadena “_end_”, y devolver el string.

Lo que se encuentra entre llaves es la semántica, la acción se va a ejecutar cuando nos encontremos con un elemento parseado.

Así que básicamente,

a ^^ f

parseará a (sintáxis), y aplicará la función f al resultado(semántica).

Para parsear un string simplemente haríamos como sigue:

parse(myParser, "my input string           _end_") match {
  case Success(matched,_) =>
    matched match{
      case "hello"=>
        println "hello world"
      case listOfArgs@h::t=> 
        MyParserHelper.executeAction(listOfArgs)
      case _=> 
        println( s"string $matched has been recognized, but I don't know what to do with it" )
    }
  case Failure(msg,_) =>   
    println("FAILURE PARSING STRING " + msg)
}

Hasta ahora, no hemos cominado mySuperSimpleParser con nada, así que compliquémoslo un poco más.
Un ejemplo (todavía simple) podría ser:

def myParser = 
  (pHelp | pThreeArgs) <~ mySuperSimpleParser

donde mySuperSimpleParser encajaría (como vimos antes) con cualquier string que termina en cero o más espacio y la cadena “_end_”, pero no haría nada con ello y continuaría con la parte izquierda en el input, parseando pHelp o pThreeArgs.

pHelp podría ser algo como:

def pHelp=  
  "(help|helpMe)".r ^^ { _=> HelpCommand }

HelpCommand es una case class que, for cuestión de simplicidad, no definiremos aquí, pero que se podría sustituir por:

def pHelp = 
  "(help|helpMe)".r ^^ { _=>"the recogniced command is help" }

Incluso no necesitaríamos añadir ninguna semántica si no es necesario:

def pHelp = 
  "(help|helpMe)".r

Nos falta ahora definir el parser pThreeArgs. Este parser reconocerá una secuencia de tres palabras y las pondrá secuencialmente en una lista (la cual devolveremos):

def pThreeArgs: Parser[List[Any]] = {
  var paramsCtx=mutable.ListBuffer[String]()
  pListParam(paramsCtx) ~> pListParam(paramsCtx) ~> pListParam(paramsCtx) ^^ {_.toList}
}

Nótese que he creado un ListBuffer mutable, que actuará como un contexto “global” para cada uno de los tres parsers que estamos combinando, de manera que solo se tengan que ocupar de parsear un parámetro y almacenarlo en el contexto global que han recibido como parámetro de la función (estos parsers son funciones).
Al final, la lista completa se devuelve conteniendo los tres parámetros 🙂

¿Se os ocurre de una mejor (o al menos más funcional) forma de resolverlo? 😉
pListParam sería algo del estilo:

def pListParam(l:mutable.ListBuffer[String])= 
  """\S+""".r ^^ {l+=_.toString}

Para un ejemplo más complejo, visitad el siguiente enlace.

Distributed key-value registry with Akka Clustering

Almost a year ago, I wanted to see how good Akka was, and how easy it would be to create a distributed hash with Akka Clustering…

So I created a sample project to play with it a little bit (https://github.com/roclas/akka-distributed-hash – I actually changed a couple of things just before writing this post).

It consist of a distributed key-value registry supported by different akka instances with the same code launched on different nodes.

39a0aab0c5b10c7204bc38788dfac55d02140c91f8b07ea4f036d673eec97379

The idea behind it is very straight forward: you run the application a few times simultaneously (passing a different port number as a parameter) and once the first node (if it is in the seeds list) has started, you can connect as many nodes to the cluster as you want. Nodes (in this case, actors) have a hash that is modified through HTTP requests, and that hash’s changes are propagated across the cluster, so that every node ends up having the same information.

The seed nodes are on src/main/resources/application.conf

When the application starts, one of the first thing it does is trying to join the cluster. In order to do that, it goes through the list of seeds and tries to connect to the first available node.

A very interesting fact is that if the node is the first element of the seeds list, and it is not the first node we start, we will most likely end up having an island in the cluster (when it finds itself as the first element of the seeds list, it will connect to itself and will create an island). The previously started nodes will be in their own sub-cluster, and the subsequently created nodes will get connected to this node, creating an isolated second sub-cluster.

akka clustering graph

I have avoided this problem by doing a trick (maybe you could find a more elegant way?):

val selfAddress = Cluster(system).selfAddress
val seeds= system.settings
  .config.getList("akka.cluster.seed-nodes")
System.setProperty("akka.cluster.seed-nodes",
seeds filter(!_.toString.contains(selfAddress.toString)) toString)

As a general rule, we could say it is not a bad idea to remove your own address from the seeds list before joining the cluster (by doing that, you would not have any problem; but I did not want to keep a different config file for each node I create and that’s why each of them programmatically removes itself from the seeds list).

Once the actor is connected to the cluster, I can receive cluster messages such as:

MemberUp (when a new node joins the cluster)
MemberRemoved (when a node leaves the cluster)

Each actor will have a hash object and a tiny HTTP server (that will respond to get, put and delete requests). Put requests will add elements to the actor’s internal hash, and remove requests will delete them.

And from this point on, you can let your imagination run wild:

  • Every time we modify an actor’s hash, it will send a message  notifying its peers of the change, so that they can change their hash too
  • After actualizing the hash, by another actors request, it sends a message back with its hash’s md5 so that the original actor can check if the changes were successfully made
  • When a new member joins the cluster, it synchronizes its state (its hash) with the other nodes

Please download the zip or clone (git@github.com:roclas/akka-distributed-hash.git) the project, and try it yourselves; it is so easy to try and very fun to play with. It’s a very simple example that you can use as a base for more complex projects. Everything is explained on the README.md file.

Also, don’t forget to tell us of useful things you think you could do with Akka Clustering. Fork, use and improve the project, and suggest us things we could do with this awesome technology.

 

 

Registro clave-valor distribuido con Akka Clustering

Hace casi un año, quise poner a prueba cómo de bueno era Akka y lo sencillo que sería crear un registro distribuido con Akka Clustering…

De modo que creé un proyecto de prueba para cacharrear un poco con ello (https://github.com/roclas/akka-distributed-hash – de hecho, he cambiado un par de cosas para dar forma a este post).

Se trata de un registro clave-valor distribuido quese apoya en distintas instancias de Akka con el mismo código, lanzadas en diferentes nodos.

39a0aab0c5b10c7204bc38788dfac55d02140c91f8b07ea4f036d673eec97379

La idea, en esencia, es muy sencilla: lanzas varias instancias de la aplicación al mismo tiempo (especificando puertos distintos como parámetros) y, una vez el primer nodo (se se encuentra en la lista de nodos semilla) ha empezado, puedes conectar tantos nodos del cluster como quieras. Los nodos (en este caso, actores) tienen una clave o hash que se modifica a través de peticiones HTTP, y dichos cambios se propagan por el cluster, de manera que todo nodo acaba por tener la misma información replicada.

Los nodos semilla se especifican en src/main/resources/application.conf

Cuando la aplicación ha arrancado, una de las primeras cosas que hace es intentar unirse al cluster. Para hacer esto, comprueba la lista de nodos semilla e intenta conectarse al primer nodo disponible.

Un dato muy interesante es que si el nodo se encuentra en la primera posición de la lista de semillas, si no es el primer nodo que arrancamos, es muy probable que acabe por generar una isla en el cluster (cuando se encuentra a si mismo como el primer nodo disponible en la lista de semillas sin ser el primero de dicha lista, se conecta a sí mismo creando así una isla). Los nodos que hayan arrancado previamente se encontrarán en su propio subcluster, y los nodos creados a partir de entonces se conectaran a este último, creando así un segundo sub-cluster aislado.

akka clustering graph

He evitado este problema usando un pequeño truco (es probable que haya una forma más elegante de hacerlo):

val selfAddress = Cluster(system).selfAddress
val seeds= system.settings
  .config.getList("akka.cluster.seed-nodes")
System.setProperty("akka.cluster.seed-nodes",
seeds filter(!_.toString.contains(selfAddress.toString)) toString)

Como normal general, podríamos decir que no es una mala idea eliminar la propia dirección de la lista antes de unirse al cluster (así evitamos el problema, pero sin tener que mantener un fichero de configuración distinto por cada nodo que cree, eliminándose a sí mismo de manera programática de la lista).

Una vez que el actor se ha conectado al cluster, pueden recibirse mensajes como:

MemberUp (when a new node joins the cluster)
MemberRemoved (when a node leaves the cluster)

Cada actor tiene un objeto registro y un servidor HTTP ligero (que responderá a peticiones de GET, PUT y DELETE. Las peticiones PUT añadirán elementos al registro interno del actor y las peticiones DELETE los eliminarán.

Y a partir de este punto, podéis hacer tanto como os imaginéis:

  • Cada vez que se modifique el registro de un actor, enviar un mensaje a los compañeros para notificarles el cambio y que así modifiquen su registro interno
  • Después de actualizar el registro, mediante otra petición de actor, mandar un mensaje de vuelta con su md5 para que el actor original compruebe si los cambios se han realizado correctamente.
  • Cuando un nuevo miembro se una al cluster, sincronizar su estado (su registro) con el resto de nodos.

Podéis descargaros el zip  o clonar (git@github.com:roclas/akka-distributed-hash.git) el proyecto, y probarlo por vosotros mismo; es muy sencillo cacharrear con ello y se puede usar como código base para proyectos más complejos (se explica todo en el fichero README.md.

Por último, contadnos que cosas útiles se podrían hacer con Akka Clustering. Forkead, usad y mejorad el proyectoFork, use and improve the project, y sugeridnos que cosas se podrían hacer con esta tecnología tan alucinante.