escribiendo una calculadora en erlang parte uno

buscando una excusa para seguir aprendiendo erlang encontré una interesante, escribir algo así como un lenguaje de juguete paso a paso y ver para donde dispara (o donde lo abandono)

en una serie de posts (espero seguir escribiéndolos) voy a ir desde cero hasta un interprete interactivo que permita hacer cosas como estas (y mas)

< a = 10 + (2 * 3) # calculo totalmente innecesario
> 16
< b = a * 2
> 32
< a
> 16
< b
> 32
< a == b or b > a
> true


este post es la patada de inicio asi que vamos a ver la herramientas.

Como lenguaje de programación obviamente vamos a usar erlang (que es lo que quiero aprender :D).

para el análisis léxico vamos a usar leex y para el análisis sintáctico y generación del árbol vamos a usar yecc.

para tener erlang hagan algo similar a:

sudo aptitude install erlang

(adaptenlo a su distro)

yecc viene incluido en erlang así que andamos con suerte, a donde no andamos con suerte es con leex, que lo tendremos que bajar de aquí:

http://forum.trapexit.org/download.php?id=184&sid=9eba63c4011e517629e8d5a73e4e2ff5

pueden buscar si hay una versión mas nueva acá:

http://forum.trapexit.org/viewtopic.php?p=43924#43924

lo bajan, descomprimen y ejecutan make en el directorio, luego para poder usarlo en erlang lo que hice (quizás no muy bueno pero anda :P) es crear un directorio llamado /usr/lib/erlang/lib/leex-0.3 y poner adentro leex.beam y el directorio include.

ahora con todo instalado vamos a largarnos con nuestro primer intento (remito a la documentación de cada uno para darse una mejor idea de que hacen y como se usan).

vamos a definir un lenguaje que nos permita sumar y restar números enteros

creemos un directorio llamado match-1-add-sub-ints

y adentro creamos un archivo llamado calc_lexer.xrl con el siguiente contenido

Definitions.

D   = [0-9]
AOP   = (\+|-)
WS  = ([\000-\s]|#.*)

Rules.

{AOP}   : {token,{add_operator,TokenLine,list_to_atom(TokenChars)}}.
{D}+   : {token,{integer,TokenLine,list_to_integer(TokenChars)}}.
{WS}+  : skip_token.

Erlang code.

este archivo lo que hace es separar un string en partes (o tokens) que identifican distintos componentes de nuestro lenguaje. En el caso de un lenguaje para sumar números enteros lo que queremos dividir son los números, los signos + y - y descartar los espacios (y también todo lo que venga después de # ya que son comentarios)

en la sección de definiciones definimos las distintas expresiones regulares.

definimos una expresión regular para números enteros

D = [0-9]

una para los signos + y -

AOP = (\+|-)

y una para los blancos y los comentarios

WS = ([\000-\s]|#.*)

luego en la sección Rules. definimos que debe generar (la parte de la derecha) cuando se encuentre con las expresiones de la izquierda.

si se encuentra con un signo + o - que genere una tupla que dice que es un operador de suma, que ponga la posición en donde encontró el token y que convierta lo que matchea la expresión a un atomo.

{AOP} : {token,{add_operator,TokenLine,list_to_atom(TokenChars)}}.

si se encuentra con uno o mas dígitos que genere una tupla que dice que es un entero, la posición del token y el numero entero que encontró.

{D}+ : {token,{integer,TokenLine,list_to_integer(TokenChars)}}.

si encuentra blancos que los salte.

{WS}+ : skip_token.

ahora ya podemos dividir el texto de entrada en pedazos mas manejables gracias a leex, ahora vamos a ver como salio esto. Iniciamos un interprete de erlang y le decimos a leex que genere un modulo de erlang para manejar los tokens que definimos, luego compilamos el modulo generado y lo probamos con un string valido

$  erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
1> leex:file(calc_lexer).
{ok,"calc_lexer.erl"}
2> c(calc_lexer).
{ok,calc_lexer}
3> {ok, Tokens, _Endline} = calc_lexer:string("1 + 2 - 3 # esto es un comentario").
{ok,[{integer,1,1},
     {add_operator,1,'+'},
     {integer,1,2},
     {add_operator,1,'-'},
     {integer,1,3}],
    1} 

como vemos nos devolvió una estructura de datos con las partes que definimos.

ahora vamos a definir un modulo para poder hacer algo con ese árbol que definimos.

creamos un archivo que se llame calc_parser.yrl con el siguiente contenido:

Nonterminals
predicate.

Terminals
add_operator integer.

Rootsymbol predicate.

Left 300 add_operator.

predicate -> predicate add_operator predicate : {unwrap('$2'), '$1', '$3'}.

predicate -> integer : unwrap('$1').

Erlang code.

unwrap({_,_,V}) -> V.

este documento define los nodos no terminales, los nodos terminales el símbolo raíz, la asociatividad de los operandos y luego define la sintaxis (para mas datos sobre las primeras secciones leer la documentación en linea de yecc o algun libro sobre lenguajes, otra opción es ponerse a romper esto y aprender :D).

la parte mas interesante es la que define que un predicado puede estar compuesto por la suma de dos predicados:

predicate -> predicate add_operator predicate : {unwrap('$2'), '$1', '$3'}.

o puede ser solo un entero

predicate -> integer : unwrap('$1').

lo que esta después de los dos puntos es el código erlang ejecutado cuando esa expresión es encontrada. Lo que hacemos es generar otra estructura de datos que vamos a manipular en erlang.

luego tenemos una función de utilidad en erlang para sacar un valor de interés de una tupla.

ahora generamos el modulo erlang que va a parsear la salida de leex y convertirla en otra estructura:

$  erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
1> yecc:file(calc_parser).
{ok,"calc_parser.erl"}
2> c(calc_parser).
{ok,calc_parser}
3> {ok, Tokens, _Endline} = calc_lexer:string("1 + 2 - 3").
{ok,[{integer,1,1},
     {add_operator,1,'+'},
     {integer,1,2},
     {add_operator,1,'-'},
     {integer,1,3}],
    1}
4> {ok, Tree} = calc_parser:parse(Tokens)                                                       
4> .
{ok,{'-',{'+',1,2},3}}

para los curiosos, si se fijan el resultado que nos dio es muy parecido a una expresión de lisp :)

{'-',{'+',1,2},3}

[1]> (- (+ 1 2) 3)
0

bueno, ahora tenemos algo que se parece mucho a lisp, podríamos escribir lisp! pero no :D vamos a interpretarlo con un programa de erlang.

creen un archivo calc.erl que contenga lo siguiente:

-module(calc).
-export([solve/1]).

solve(String) ->
    {ok, Tokens, _Endline} = calc_lexer:string(String),
    {ok, Tree} = calc_parser:parse(Tokens),
    matches(Tree).

matches(A) when is_integer(A) -> A;
matches({'+', A, B}) -> matches(A) + matches(B);
matches({'-', A, B}) -> matches(A) - matches(B);
matches(_) -> error.

lo que hace este modulo es definir una función que recibe un string por parámetro con el calculo que queremos realizar, lo pasar por el analizador lexicografico, le da la salida de este como entrada al parser y con el árbol sintáctico resultante llama a la función matches que gracias al pattern matching se encarga de ejecutar recursivamente la instrucción correcta y devolver el resultado final (o un error en caso de que algo no matchee).

ahora vamos a compilar esto y probarlo un poco:

$  erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
1> c(calc).
{ok,calc}
2> calc:solve("1 + 2 - 3 # deberia dar 0").
0
3> calc:solve("1 + 2 - 3 - 4").            
-4

bueno, ya tenemos la primera versión de nuestra calculadora, en la próxima vamos a agregar soporte para números de punto flotante con algunos leves cambios.

para los fiacosos como yo, el codigo de este ejemplo (y de los subsiguientes) esta en github aca:

http://github.com/marianoguerra/match