Avancez

This post is available in English too.

Si me seguís por Twitter/Facebook o te lo comenté en persona, sabrás que durante el último viaje que hice al viejo continente pasé unos días en Gotemburgo, Suecia. Lo que muy posiblemente no sepas es qué fui a hacer a tan remota ciudad.

Hace unos meses apliqué para una posición en Chalmers, como estudiante de doctorado. Tuve la suerte de quedar en la short-list, lo que implicaba que tenía que ir a hacer algunas entrevista in-situ. Y eso fue lo que hice durante esos 3 días. ¡Y me aceptaron! :-)

Así que a mediados del próximo Agosto me estaré reubicando en la linda ciudad de Gotemburgo. Quedan excitantes días en los próximos meses en Buenos Aires, con muchas cosas para hacer y mucha gente a la que me gustaría ver. Así que si estas leyendo esto y me conoces mínimamente, escribime un correo y vamos a por unas cervezas :)

Chalmers es una universidad muy prestigiosa. La gran mayoría de los papers que estudié durante los últimos meses, fueron escritos por estudiantes de ahí y estoy muy contento con la posibilidad de trabajar en semejante ambiente académico.

Avancez

Este post también está escrito en español.

If you follow me on Twitter/Facebook, you probably know that I went to Gothenburg, Sweden, during my last trip to Europe. But you probably don't know what I did in such remote city.

Few months ago, I applied to a PhD student position at Chalmers. I was lucky enough to be shortlisted, so I went to some in-situ interviews. And, incredibly, I have been accepted! :-)

Chalmers is a TOP 100 university. Most of the papers I read during the last months has been written by Chalmers researchers and for me is a great honor to be part of an academic institution with such prestige.

I'm going to move to the nice Gothenburg city in August. And I'm happy :)

parser para fórmulas de lógica proposicional (o una somera introducción a pyparsing)

La semana pasada empecé a cursar, de oyente, dos materias en Exactas: Lógica y Computabilidad y Teoría de Lenguajes. En la primera, empezamos a estudiar algunos conceptos de cálculo proposicional. Al final de la clase, el profesor sugirió escribir un pequeño parser que reconozca fórmulas de lógica proposicional. Dado que venía con ganas de entender mejor pyparsing, me pareció que podía ser una buena forma de empezar.

Primero, la teoría. Dado el alfabeto $latex A$, $latex A^*$ es el conjunto de palabras que pueden formarse combinando sus elementos.
$latex A=\{ \to , \wedge , \vee , \neg , ( , ) , p , \prime \}$
Existe un tipo particular de palabras, a las que llamamos variables.
$latex Var=\{p , p\prime, p\prime\prime , \ldots \}$
Es un conjunto infinito y, dado que puede ser tedioso contar la cantidad de primas, las variables pueden ser referenciadas como $latex p_n$, donde n es la cantidad de primas. Así, parece razonable pensar que no todas las palabras son válidas a la hora de escribir una fórmula (que es como llamaremos a las palabras válidas).

Ejemplos de fórmulas:

  • $latex p_2$
  • $latex ( ( p_3 \wedge p_5 ) \to ( \neg p_2 \vee p_5 ) )$
  • $latex \neg \neg ( p\prime \vee p_{1232} )$

Ejemplos de no-fórmulas (palabras que no forman una fórmula):

  • $latex \neg\prime$
  • $latex ( p_2 )$
  • $latex p_3 \vee \wedge $

Si bien es más o menos intuitivo qué es una fórmula y qué no, es necesario definirlo en un sentido formal. Así $latex Form \subset A^* $ y es el conjunto de las palabras que cumplen:

  1. si $latex \alpha \in A^*$ y $latex \alpha \in Var$, entonces $latex \alpha \in Form$
  2. si $latex \alpha \in Form$, entonces $latex \neg \alpha \in Form$
  3. si $latex \alpha,\beta \in Form$, entonces $latex ( \alpha \circledast \beta)\in Form$. Donde $latex \circledast=\vee,\wedge,\to $

Nada más es una fórmula.

Ahora, a la práctica. Queremos escribir un parser que, dada una palabra, reconozca si es una fórmula. Y para esto vamos a jugar con el módulo pyparsing, para python.

Lo primero es definir el conjunto de variables.

>>> from pyparsing import Word
>>> variable=Word('Pp',"0123456789'")
>>> variable.parseString('p1')
(['p1'], {})
>>> variable.parseString("P'")
(["P'"], {})

Así, variable reconoce los posibles nombres de variables. Toda expresión que sea parseable por variable, es una formula. Para el punto ii. hay que definir una estructura recursiva. Utilizaremos el bang (!) para la negación.
from pyparsing import Forward
formula=Forward()
ii='!' + formula

Caso similar en el punto iii.. Para esto hay que definir los operadores, que son and (&), or (|) y then (<).

operador=Word('&|>',max=1)
iii='('+formula+operador+formula+')'

Por último, definimos una fórmula cómo una variable (i.) o una negación de una fórmula (ii.) o una operación entre fórmulas (iii.).

formula << ( variable | ii | iii )

Y esto es, básicamente, nuestro parser:

>>> formula.parseString("(p1 | p4)")
(['(', 'p1', '|', 'p4', ')'], {})

Lo dicho, con un poco más de contexto y en un único archivo, a continuación: