Parseando en Scala (4): Combinator Parsing en acción

Leemos en el scaladoc del trait Parsers:

(...) El término "parser combinator" se refiere al hecho de que estos parsers son construidos a partir de parsers primitivos y operadores de composición, como secuenciación, alternación, opcionalidad, repetición, etc. Un parser primitivo es un parser que acepta o rechaza una porción de la entrada, en base a cierto criterio. (...)

En la segunda parte de esta serie mencionábamos estas posibilidades de "composición" al definir la sintaxis: que algo se pueda repetir, que algo sea opcional, etc. EBNF utiliza determinados símbolos para esos operadores de composición. Este es un ejemplo de Wikipedia donde se define la sintaxis para escribir un número en un lenguaje hipotético.

number = [ "-" ] , digit , { digit } ;

Esta definición se lee así:

• Opcionalmente se comienza con un guión (signo menos). Los corchetes indican opcionalidad.
  
• Se sigue con un dígito. La coma indica sucesión de elementos.
  
• Se sigue con 0 a n dígitos. Las llaves indican repetición arbitraria.
  

Esto asume que en alguna otra parte se definió lo que es un "digit" de la misma manera que aquí se define lo que es un "number".

En Scala se traduciría más o menos a algo así:

def number: Parser[Number] = opt("-") ~ digit ~ rep(digit) // luego completamos lo que falta

Este sencillo ejemplo ilustra cómo se traduce en forma bastante directa desde la notación EBNF.

• Opcionalidad: método opt()
  
• Sucesión: símbolo ~ (que en realidad es un método)
  
• Repetición arbitraria: método rep()
  

Con una vuelta de tuerca más: el método rep1() es similar a rep() pero requiriendo que exista como mínimo una ocurrencia (1 a n). La misma definición se puede simplificar a:

def number: Parser[Number] = opt("-") ~ rep1(digit)  // ...

El tipo de retorno es Parser[X] donde X es una clase del modelo. En este caso supongamos que se definió la clase Number como parte del modelo.

También vamos a usar el símbolo | para indicar alternativas. Si contempláramos también el signo + para escribir un número positivo, haríamos así:

def number: Parser[Number] = opt("-" | "+") ~ rep1(digit)  // ...

Como se puede ver, combinamos los operadores según nuestra necesidad: opcionalmente habrá un signo, y el signo puede ser - o +.

Estamos listos para parsear PL/SQL. Como primer ejemplo veamos la definición del LOOP:

def loop: Parser[Loop] = "loop" ~ rep1(code) ~ ("end" ~ "loop" ~ ";")  // ...

Desde luego, esto requiere la definición de code retornando un Parser[Code], y así con todas las dependencias.
Todo lo que sea whitespace no es necesario especificarlo: entre elementos puede haber cualquier cantidad de espacios, tabs o line feeds. Observar que como fin del loop usamos ("end" ~ "loop" ~ ";"), porque si usáramos "end loop;" estaríamos reconociéndolo solamente si se escribe exactamente así.

Sigamos con este ejemplo. Esta definición, así como está, no retorna un Parser[Loop]: vamos a completarla. Tenemos que agregar una función (una closure para mayor comodidad) que levante esos elementos parseados y genere un objeto del modelo, en este caso Loop. Pero antes, tenemos que usar variantes del operador ~. Las variantes ~> y <~ son equivalentes a ~ en tanto que indican secuencia de elementos, la diferencia está en que "señalan" el elemento que nos interesa recuperar a fines de construir un nodo del AST, lo que implica que la parte no señalada será ignorada. Para armar el nodo Loop, lo único que necesito de esa definición es la colección de objetos Code. Entonces "señalemos" lo que realmente importa:

def loop: Parser[Loop] = "loop" ~> rep1(code) <~ ("end" ~ "loop" ~ ";")  // esto arroja un List[Code] 

Ahora sí: rep1(code) produce un List[Code], y eso es lo que la closure tomará como entrada. La closure en cuestión es sencillísima:

{ c:List[Code] => Loop("loop", c) }

(Uso el string "loop" para indicar que no es un FOR ni un WHILE, este es un detalle de mi implementación que no tiene mucha importancia).
Terminamos juntando la definición de la sintaxis y la closure de generación del nodo con el simpático operador ^^.

def loop: Parser[Loop] = "loop" ~> rep1(code) <~ ("end" ~ "loop" ~ ";")  ^^ { c => Loop("loop", c) }

Voilà! Y simplificamos la closure dejando que el compilador infiera el tipo del argumento. Todo esto es type-safe, el compilador chilla si nos equivocamos con los tipos.
Insisto, nada de esto es magia, estamos usando una librería estándar. Estos operadores raros son métodos de la clase Parser. Y si bien a primera vista el código parece un jeroglífico, es sólo cuestión de aprender el API como un "sublenguaje": todo cobra sentido, y de hecho parsear termina siendo una pavada. Cada elemento se define con una parte declarativa (equivalente a un EBNF), el operador ^^, y una closure que toma lo necesario de esa declaración para crear un nodo del AST.

Para parsear los FOR y WHILE utilizo una definición unificada porque son muy similares, y también genero un nodo Loop:

def forWhileLoop: Parser[Loop] = ("while" | "for") ~ (regularStr <~ "loop") ~ (rep1(code) <~ ("end" ~ "loop" ~ ";")) ^^     { (t:String, h:String, c:List[Code]) => Loop(t + " " + h, c) }

Esta declaración produce tres cosas relevantes, tomadas como parámetro por la closure: un String que será "while" o "for", un String con la condición o secuencia del FOR, y la correspondiente List[Code].

En la próxima entrega muestro el contexto donde se define todo esto y vamos cerrando lo que es parseo, para más adelante empezar a explotar el AST.

Parseando en Scala (3): Modelo

Retomando, decíamos que el resultado de parsear es generar un abstract syntax tree (AST). Vamos a ser un poco más gráficos, para que no queden dudas de que se trata de algo bien facilongo.

Si el código PL/SQL a parsear fuera éste:

PROCEDURE myproc IS
BEGIN
s1;
s2;
IF cond1 THEN
 s3;
ELSE
 s4;
 WHILE cond2 LOOP
    s5;
    s6;
    IF cond 3 THEN
       s7;
    END IF;
 END LOOP;
 s8;
END IF;
END;

...nuestro objetivo lo vemos plasmado en este garabato:

Se ve bien clarita en el árbol la estructura sintáctica del código parseado. El árbol no es más que un grafo, compuesto por nodos y relaciones entre ellos.

Podemos identificar distintos tipos de nodos. En el dibujito, cada tipo de nodo está pintado de un color diferente (las sentencias en amarillo, etc.) Las relaciones (líneas) indican los subnodos. Las sentencias son nodos terminales, nunca tienen subnodos.

Para armar el AST necesitamos modelar los tipos de nodo, cada uno con sus características. Verán cómo la orientación a objetos convive en armonía con la programación funcional: el modelo es una jerarquía de clases. Todos los tipos de nodo son subclase de un nodo abstracto, pero también identifiqué una abstracción en el medio a la que llamé Code, ya veremos por qué. Este sería un pseudo-UML del modelo:



Y en Scala:

abstract class Node
abstract case class Code extends Node
case class Stmt(s: String) extends Code
case class Cond(c: String, cThen: List[Code], cElse: List[Code]) extends Code
case class Loop(head:String, body: List[Code]) extends Code
case class WhenExcep(e: String, body: List[Code]) extends Node
case class ExcepSection(ee: List[WhenExcep]) extends Node
case class Block(content: List[Code], exceps:Option[ExcepSection]) extends Code
case class Module(typ: ModuleType, name: String, pars: Option[Stmt],
       returns: Option[String], vars: List[Stmt], body: Block) extends Node

Como se puede ver, ninguna de estas clases define métodos; sólo atributos, que son seteados como parámetros del constructor. Además, son inmutables. El contenido relevante de cada tipo de nodo está en los parámetros: esto determina qué tipo de relaciones con subnodos puede tener en el grafo.

Para las colecciones de elementos, usamos List[T], la lista inmutable de la librería estándar de Scala. Para los elementos opcionales, usamos Option[T], cuyos posibles valores son Some[T] (con un valor de T específico) o None. Es mejor que manejar la opcionalidad chequeando por la referencia en null, pero no nos vayamos por las ramas. Vamos a comentar un poco el modelo (los que no conozcan PL/SQL, podrán imaginárselo más o menos).

El tipo de nodo "sentencia" (Stmt) sólo contiene un String, que es la sentencia misma en PL/SQL (no nos interesa la estructura interna, nuestro modelo es simplificado). No puede haber subnodos, como decíamos recién.

Las condiciones (Cond) son más complejas: tienen un String (que es la condición en sí), una sección para el "then" y otra para el "else". Cada una de estas secciones podría ser, en principio, una colección de sentencias, pero lo cierto es que puede haber cosas más diversas... ¡por eso fue necesaria la abstracción Code! Estos "elementos de código" pueden ser varias cosas (las cuatro subclases), pero no cualquier Node. El mismo Cond es un Code, y claro, porque puede haber condiciones anidadas.

Podría decirse que la sección "then" debe ser modelada diferente a la sección "else", porque en un IF de PL/SQL, la primera es obligatoria y la segunda opcional. Pero el modelo no necesariamente debe reflejar todas las reglas de sintaxis que aplican al parseo. Mi parser va a dar error si falta el "then", pero no si falta el "else"; eso está contemplado. Pero con una List vacía (Nil) puedo representar un "else" ausente. Asimismo el modelo tampoco refleja que el "then" tendrá por lo menos un elemento.

Con la clase Loop modelo los distintos tipos de loop, no me interesa diferenciarlos. Cada uno contendrá un encabezado (tipo de loop y condición), y un contenido que es lista de Code.

WhenExcep es el "catch" de excepciones de PL/SQL: contiene el nombre de la excepción y la lista de Code asociada.

ExcepSection es la sección final (dentro de un bloque) que contiene una sucesión de WhenExcep.

Block es un bloque BEGIN / END. Consiste en una lista de Code, y opcionalmente una sección de excepciones.

Finalmente, Module representa, obviamente, un módulo, que puede ser un procedimiento, una función o un bloque anónimo de PL/SQL. Tiene un tipo de módulo, un nombre, opcionalmente parámetros (aquí usamos Stmt, no porque los parámetros sean una sentencia, sino por simplificar), opcionalmente un tipo de retorno (aplicable a módulos función), declaraciones / variables (una lista de Stmt, también por simplificar), y un Block, que es el bloque de código de mayor nivel en el módulo.

Para los tipos de módulo uso esta definición:

abstract class ModuleType
case object MTProcedure extends ModuleType { override def toString = "procedure" }
case object MTFunction extends ModuleType { override def toString = "function" }
case object MTAnonymousBlock extends ModuleType { override def toString = "anonymous block" }

En la próxima: vamos a parsear de una vez.

Parseando en Scala (2): Metasintaxis y AST

Demás está decir que, antes de pretender parsear un lenguaje determinado, tenemos que conocer su sintaxis. Y si la conocemos, debemos ser capaces de expresarla formalmente con una metasintaxis, como podría ser BNF o EBNF. Vamos a poner unos ejemplos del tipo de cosas que podemos definir, y los ilustramos con ejemplos de PL/SQL, nuestro lenguaje a parsear.

símbolos	:= (asignación)
palabras clave	PROCEDURE
sucesión de elementos	IF (seguido de) condición (seguido de) THEN ...
elementos alternativos	En una asignación, del lado derecho de := puede haber un identificador o un literal
repetición de elementos (0 a n)	En la sección de declaración de variables puede no haber ninguna, una, o varias
repetición de elementos (1 a n)	En la sección EXCEPTION debe haber al menos un catch (con la forma WHEN excepción THEN ...)

Con este metalenguaje podemos definir el lenguaje completo. Por si no queda claro, cuando decimos "elemento" podemos estar hablando de definiciones de cualquier nivel en la entrada de texto, desde un carácter "A" hasta un bloque de código BEGIN / END. Es decir, en alguna parte definimos en qué consiste un bloque de código y le ponemos un nombre. Luego podemos definir que un PROCEDURE contiene, además de parámetros opcionales, declaración de variables, etc., un bloque de código. Y como las definiciones pueden ser recursivas, también podremos definir que dentro de un bloque de código puede haber bloques de código. ¿Se va entendiendo lo de "combinators"?

Como decía en el post anterior, los parser combinators en Scala son un ejemplo de DSL (domain specific language), ya que "se sienten" como un BNF, o digamos que se presta a una traducción directa desde un BNF. Si no contamos previamente con el BNF del lenguaje que queremos parsear, como para hacer esa traducción, podemos directamente expresar el lenguaje con los parser combinators. Eso es lo que hice yo en este caso, con la salvedad de que no necesitaba parsearlo en profundidad, sino que para mis fines bastaba con capturar la estructura lógica. Esto simplificó la tarea: no necesito interpretar el contenido de una sentencia simple, para reconocerla me basta con que haya una sucesión de caracteres comunes terminados en punto y coma. No importa si hay una asignación, una llamada a un procedimiento, un query, etc.; las sentencias simples las muestro en mi diagrama tal como vienen.

Nuestro cuasi-BNF en Scala no es una mera declaración sino que es a la vez el código que parsea. Lo que tenemos que agregarle es qué hacer con las estructuras que va reconociendo. El que pensó en renderizar la salida, que se retire por favor. Dijimos que vamos a separar las responsabilidades como corresponde.

Con ustedes, el AST

El objetivo inmediato de parsear debe ser obtener el abstract syntax tree, es decir, una representación de la estructura parseada. Una vez que conseguimos esto, nos olvidamos del texto de entrada y las reglas del lenguaje. Piensen en los compiladores de .NET: la plataforma soporta varios lenguajes, y para cada uno hace falta un parseador diferente. Sin embargo todos conducen a lo mismo, el MSIL, una representación del programa que no mantiene dependencia con el lenguaje de origen. Es un AST. Luego desde el AST generamos la salida deseada. Si nos da el cuero podemos generar byte code ejecutable.

El AST consistirá en un grafo de objetos de un modelo que debemos definir, según la estructura que necesitamos capturar. Ese modelo se define como una serie de clases "nodo". A medida que el cuasi-BNF parsea y detecta estructuras en el texto, indicaremos también qué nodos instanciar en cada caso.

Se está poniendo bueno, sigue en la próxima. 

Parseando en Scala (1): Intro

Voy a compartir un ejemplo de programación funcional aplicado en la vida real, para resolver un problema concreto que tuve como desarrollador. Más de una vez me tocó descifrar el fuente de un programa ajeno con una lógica tirada de los pelos (a quién no). Cuando el lenguaje en cuestión es PL/SQL, se me complica tener una buena perspectiva de la estructura del código.
Allá por los '80 en la facultad me enseñaron los diagramas estructurados de Nassi-Schneiderman. Estos diagramas están buenos para leer código estructurado, y a veces garabateo alguno si tengo que armar una lógica complicada. Pero el código ajeno nunca existe en forma de diagrama, así que estaría bueno tener una herramienta que lo genere. Esa herramienta, además de ser útil, podría ser interesante de programar.

Problema #1: Generar el diagrama

Lo más práctico me pareció generar la salida en HTML con tablas, para ver algo parecido al diagrama Nassi-Schneiderman con un browser. Fue una buena opción. Las principales estructuras a visualizar son los condicionales (IF, THEN, ELSE) y los ciclos (FOR, WHILE, LOOP), y la forma en que se anidan.

Problema #2: Interpretar el código original

Dicho de otra manera: parsear. En la primera encarnación de la herramienta, en C++, parseaba a lo guapo, por no decir a lo bestia. No es que no se pueda parsear bien con C++, pero terminé con una implementación con limitaciones absurdas. Me metí en un berenjenal. Antes de parsear me veía obligado a toquetear el código de entrada para adecuarlo a ciertos requisitos inexcusables... por ejemplo, si había una cadena de ELSIF's:

 IF cond1 THEN
   sentencia1;
 ELSIF cond2 THEN
   sentencia2;
 END IF;

...para que fuera parseable, tenía que modificarlo manualmente a:

 IF cond1 THEN
     sentencia1;
 ELSE
     IF cond2 THEN
         sentencia2;
     END IF;
 END IF;

Creo que también hice una versión en C# que andaba mejor, pero el problema de fondo no estaba resuelto.

Combinator parsing al rescate

La técnica funcional salvadora fue combinator parsing, en este caso en Scala. No voy a incluir acá un tutorial de Scala ni voy a explicar cómo está implementada la librería (si bien vale la pena empaparse en el tema). Voy a enfocarme en el uso de la librería usando mi proyecto como ejemplo. Van a notar que parece un lenguaje con soporte especial para parsing, pero es solo una ilusión: el lenguaje es lo suficientemente flexible, porque permite definir operadores como | y ~ en forma de métodos, tiene conversiones implícitas, y un toque de syntax sugar que lo hace óptimo para crear DSLs (domain specific languages). 

Combinator parsing viene incluido en la librería estándar de Scala, y más que un API, parece un sublenguaje. Su implementación puede resultar un tanto sesuda para el no iniciado; pero su utilización, prometo, está al alcance de cualquier programador.

Otro problema que tenían las soluciones anteriores era el acoplamiento entre el parsing y la generación de la salida. Vamos a separar las responsabilidades para que, una vez resuelto el parseo, podamos generar todas las salidas que se nos antoje.

Continuará

Guía para el código testeable

Siguiendo con los posts "de referencia", hoy traduzco un resumen de la Guía para el Código Testeable utilizada en Google y publicada en el blog de Miško Hevery. Esta guía consiste en 4 fallas de diseño a evitar, y las señales de advertencia que indicarían que las cometimos. Como siempre, se trata de reglas generales, no para seguirlas dogmáticamente, sino para tenerlas presente y considerar el costo de ignorarlas.

Quizás más adelante me ponga a traducir la cosa más a fondo, porque se explica todo con mayor detalle, con argumentos y ejemplos. Mientras tanto, quienes puedan leer inglés, háganse un favor y vayan a la fuente.

Falla #1: El constructor hace trabajo
Señales de advertencia:

• Se usa el operador new en el constructor o en la declaración de campos
  
• Llamadas a métodos static en el constructor o en la declaración de campos
  
• Cualquier cosa en un constructor más allá de asignación de campos
  
• Objetos que no queden completamente inicializados una vez terminado el constructor (atención con los métodos initialize)
  
• Flujo de control (lógica condicional o cíclica) en un constructor
  
• Se construye un complejo grafo de objetos dentro de un constructor, en lugar de usar una factory o un builder
  
• Bloques de inicialización
  

Falla #2: Hurgar en los colaboradores
Señales de advertencia:

• Se pasan objetos pero nunca son utilizados directamente (sólo para obtener acceso a otros objetos)
  
• Violación de la ley de Demeter: la cadena de llamadas a métodos recorre un grafo de objetos con más de un punto (.)
  
• Nombres sospechosos: context, environment, principal, container, o manager
  

Falla #3: Estado global riesgoso y Singletons
Señales de advertencia:

• Uso de singletons
  
• Uso de campos static o métodos static
  
• Uso de bloques de inicialización static
  
• Uso de registries
  
• Uso de service locators
  

Falla #4: La clase hace demasiado
Señales de advertencia:

• Al describir lo que la clase hace usamos la palabra "y"
  
• Sería complicado para un nuevo programador leer la clase y rápidamente comprenderla
  
• La clase tiene campos que son usados solamente en algunos métodos
  
• La clase tiene métodos static que solamente operan sobre los parámetros
  

Miško responde a los lectores que dejan sus comentarios, acá va una muestra interesante:

En la falla #3 mencionás que el "uso de registries" es una señal de advertencia. Pero la mayoría de las aplicaciones tienen algunos objetos que necesitan ser accedidos desde todas partes, o al menos en base a algún contexto. ¿Cómo manejaríamos tales objetos sin un registry? (...)

Y la respuesta:

(...) Registry, Context, ServiceLocator, o como quieras llamarlo, es un problema. En primer lugar, ¿cómo obtenés su referencia? ¿Variable global?

Las variables globales son problemáticas:
http://misko.hevery.com/2008/08/25/root-cause-of-singletons/
http://misko.hevery.com/2008/08/17/singletons-are-pathological-liars/

Los locators son problemáticos:
http://misko.hevery.com/2008/10/21/dependency-injection-myth-reference-passing/

Y la solución es Inyección de Dependencias aun si es un objeto ampliamente necesitado:
http://misko.hevery.com/2008/10/21/dependency-injection-myth-reference-passing/
(...)

Diseño orientado a objetos: The S.O.L.I.D. principles

Acá van los principios propuestos por el Tío Bob para un buen diseño orientado a objetos, en versión ultra condensada. No los sigo a rajatabla pero son una guía que conviene tener presente, como mínimo. En otro post voy a resumir las reglas de testeabilidad, que son un buen complemento a estos principios (y en parte se superponen).

Single Responsibility Principle (Principio de Responsabilidad Única)

Nunca debe haber más de un motivo por el cual modificar una clase.

Este principio se ve violado por todas partes. Un ejemplo típico es cuando un Servlet hace más de lo que debe. Ya de por sí trabajar directamente con servlets sin un framework que los esconda es una mala idea, pero cuando los usamos, debe ser solamente para dar acceso web a nuestra aplicación: levantar parámetros del request y elementos posteados, invocar las validaciones y servicios que corresponda (en otra capa) y manejar el response.

Open / Closed Principle (Principio Abierto / Cerrado)

Los elementos de software (clases, módulos, funciones, etc.) deben estar abiertos a la extensión, pero cerrados a la modificación.

En realidad, no podemos evitar completamente las modificaciones, pero el diseño puede tener en cuenta qué tipo de modificaciones contemplar, y permitir que cierto cambio de comportamiento se resuelva con nuevas implementaciones o subclases. De acá podemos derivar la regla general de "programar a interfaces", que las dependencias sean sobre abstracciones.

Liskov Substitution Principle (Principio de Sustitución de Liskov, o "Diseño por Contrato")

Los módulos que usen referencias a clases base deben poder utilizar objetos de subclases sin saberlo.

Las subclases deben seguir el comportamiento que se espera de la superclase. La superclase define un contrato. Si las subclases lo respetan, la superclase es sustituible por una subclase, y las subclases son intercambiables. Una regla relacionada con este principio es tratar de que el diseño permita a los usuarios del mismo prescindir del operador instanceof.

Interface Segregation Principle (Principio de Segregación de Interfaces)

Los clientes no deben verse obligados a depender de interfaces que no utilizan.

Las interfaces "gordas" producen acoplamiento entre clientes que deberían estar aislados. Un cliente no tiene por qué "ver" más de lo que necesita de una clase, entonces debería poder accederla a través de una interfaz particular. Por ejemplo, si tenemos una PavaElectrica, y la interfaz Pava define una dependencia con Agua, puede haber clientes para los cuales la PavaElectrica interesa sólo en tanto que ArtefactoElectrico. Y esos clientes deberían poder reutilizarse en proyectos donde haya otras implementaciones de ArtefactoElectrico pero donde no exista la definición de Agua.

Dependency Inversion Principle (Principio de Inversión de Dependencias, también conocido como "Inversión de Control")

Los módulos de alto nivel no deben depender de módulos de bajo nivel: ambos deben depender de abstracciones. Las abstracciones no deben depender de detalles: los detalles deben depender de las abstracciones.

El término "inversión" se debe a que este principio propone dar vuelta las dependencias con respecto a la tradición procedural: módulos de alto nivel que llaman a módulos de bajo nivel. En OOP creamos estas dependencias hardcodeadas cuando usamos el operador new. Cuando dependemos de abstracciones, las dependencias pueden ser inyectadas, en un módulo de inicialización o con un framework de inyección de dependencias.