L-System

Hoy por la noche, cuando navegaba por la red me encontre con algo interesante. Y decidi iniciar un proyecto pequeño, un L-System en Haskell.

Este proyecto me trae recuerdos cuando estaba en la materia de Interfaces de Usuario con el Lic. Boris Calancha, en la que desarrollamos fractales con Java, de una forma recursiva. En aquel entonces no tenia la menor idea de que existia una generalizacion en la forma de generar fractales, pues hoy aprendi que si hay una generalizacion muy interesante, me intereso mas que todo por que esta relacionado con el campo de estudio que sigo, gramaticas, compiladores y haskell.

Pues resulta que un L-System es una tri-tupla, (muy parecido a las gramaticas que estudiamos en automatas)

G (V, w, P)

donde:

V: Alfabeto o conjunto de Simbolos
w: Simbolo Inicial
P: Reglas de Produccion o de re-writing

Asi, esta tri-tupla es capaz de generar fractales. La forma de hacerlo es atraves de derivaciones empezando con el simbolo inicial (no olviden que para hacer una derivacion usamos las reglas de produccion). Entonces de acuerdo al fractal que queramos, podemos aplicar (derivar) varias veces.

Veamos un ejemplo de wikipedia,

Example 1: Algae
variables : A B => alfabeto

constants : none

start  : A                      => simbolo inicial

rules  : (A → AB), (B → A)      => 2 reglas de produccion

which produces:

n = 0 : A

n = 1 : AB

n = 2 : ABA

n = 3 : ABAAB

n = 4 : ABAABABA

n = 5 : ABAABABAABAAB

n = 6 : ABAABABAABAABABAABABA

n = 7 : ABAABABAABAABABAABABAABAABABAABAAB

Cuando vemos este ejemplo, no parece animar ni convencer para seguir con el proyecto, sin embargo, si vale la pena seguir cuando se ve las imagenes que se puede generar (fractales), y eso se logra con la ayuda de una libreria grafica y un sistema denominado turtle para interpretacion de strings. Si quieres convencerte al igual que yo, debes ver las imagenes de wikipedia.

Bueno, y esta oportunidad queria compartirles la implementacion de una parte basica de este sistema L,

la forma en que represento un sistema L es asi:

type L = (V, W, P)              -- Sistema L

type V = [String]

type W = String

type P = [(Char, String)]       -- simbolo -> resultado == (simbolo, resultado)

genero un parser de acuerdo a las producciones:

--genParser :: [(Char, String)] -> Parser ? ?

genParser lst = if null lst

                then usererror "GenParser: the argument my not be empty list."

                else foldr1 (<|>) (map fun lst)

    where fun (val, res) = (res <$ pSym val)

y genero las iteraciones enviandole el sistema L y un N que indica el numero de iteraciones, esta funcion imprime el resultado en la pantalla.

generate :: L -> Int -> IO ()

Veamos algunos ejemplos de sistemas L:

{-

Example 1: Algae

variables : A B

constants : none

start  : A

rules  : (A → AB), (B → A)

-}
algae = (["A", "B"], "A", [('A', "AB"),('B',"A")])
{-

Example 2: Fibonacci numbers
variables : A B

constants : none

start  : A

rules  : (A → B), (B → AB)

-}
fib = (["A","B"], "A", [('A', "B"),('B',"AB")])
{-

Example 3: Cantor dust
variables : A B

constants : none

start  : A

rules  : (A → ABA), (B → BBB)

-}
cantor1 = (["A","B"], "A", [('A', "ABA"),('B',"BBB")])

cantor2 = (["-"," "], "-", [('-', "- -"),(' ',"   ")])

Ahora mostremos algunos ejemplos:

*Parser> generate fib 7
BABABBABABBABBABABBAB

*Parser> generate algae 7
ABAABABAABAABABAABABAABAABABAABAAB

*Parser> generate cantor1 4 ABABBBABABBBBBBBBBABABBBABABBBBBBBBBBBBBBBBBBBBBBBBBBBABABBBABABBBBBBBBBABABBBABA

*Parser> generate cantor2 4
- - - - - - - - - - - - - - - -
(Nota.- este utlimo no se grafico bien, pero se genera correctamente en consola)

Bueno eso es todo por hoy, si quieres ver el codigo y el proyecto, te invito que sigas este link.