1

1.6 - Gramáticas complejas:De los sistemas-L a las

gramáticas de formaCarlos Reynoso

UNIVERSIDAD DE BUENOS AIREShttp://carlosreynoso.com.ar

Objetivos– Comprender aspectos de la complejidad– Definir complejidad gramatical– Profundizar en modelos gramaticales de tipo

sistemas-L• Idem en jerarquía de la complejidad y sus autómatas

– Ejemplificar investigaciones en arquitectura, arte, antropología y ciencias sociales que usanformalismos semejantes

– Identificar recursos bibliográficos y examinarherramientas de modelado

– Experimentar y producir objetos novedosos• Fachadas, caminos, edificios, ciudades o cosas complejas que

haya en ella• Proyectar transformaciones de objetos e híbridos estilísticos

ReferenciasReferencias•• Carlos Reynoso. 2006. Carlos Reynoso. 2006. Complejidad y caos: Una Complejidad y caos: Una

exploraciexploracióón antropoln antropolóógicagica. Bs. Aires, Editorial Sb. Bs. Aires, Editorial Sb

••AntropologAntropologííaa••Estudios culturalesEstudios culturales••LingLingüíüísticastica--SemiSemióóticatica••ComputaciComputacióónn

••Inteligencia ArtificialInteligencia Artificial••Modelos complejosModelos complejos••LenguajesLenguajes••Arquitectura de softwareArquitectura de software

••Ciencias cognitivasCiencias cognitivas••MusicologMusicologííaa

••http://http://carlosreynoso.com.arcarlosreynoso.com.ar

2

Referencias• Libros de Prusinkiewicz-Hanan & Lindenmayer

AgendaAgenda•• PrehistoriaPrehistoria –– Freeman: Freeman: chain codingchain coding•• DefinicionesDefiniciones de de sistemasistema--L L –– GramGramááticasticas

–– LenguajesLenguajes artartíísticossticos•• PosicionamientoPosicionamiento entre los entre los sistemassistemas basadosbasados en en

gramgramááticasticas (o (o reglasreglas de de reescriturareescritura de de stringsstrings, o , o gramgramááticasticas basadasbasadas en en formasformas))

•• TiposTipos de de sistemasistema--LL•• Software de Software de modeladomodelado•• EjemplosEjemplos culturalesculturales

–– ReconstrucciReconstruccióónn arqueolarqueolóógicagica, , disediseññosos, , patronespatrones de de asentamientoasentamiento, , simulacisimulacióónn musical, GIS, musical, GIS, gramgramááticasticasculturalesculturales, , disediseññoo de de edificiosedificios y y plantasplantas urbanasurbanas

•• ConclusionesConclusiones –– RecursosRecursos –– DesafDesafííosos –– TrabajosTrabajos

Sistemas-L

• Aristid Lindenmaier – Sistemas-L, ca. 1968

3

Prehistoria

• Chain coding (Freeman, 1961)– Correspondencias entre cadenas de

símbolos e imágenes– Narasinham (1970s) – Primera aplicación

• Reconocimiento de patrones en fotografía aérea, reconocimiento de firmas, OCR

• Almacenamiento de datos gráficos y su comparación

• Examinemos la nomenclatura

Ejemplo Ejemplo –– ChainChain codingcoding

•• Izquierda: BrIzquierda: Brúújula de referenciajula de referencia•• MeshMesh o malla regularo malla regular

–– Cartesiana Cartesiana 22020200 22020200 –– Circular Circular 221010 221010 –– De intersecciDe interseccióón n 221100 221100

SistemasSistemas--LL

4

Sistemas-L• Gramáticas recursivas de crecimiento• Smith, Prusinkiewicz: gráficos de

tortuga

Profundidad Cadena resultante 0 B 1 F[-B]+B 2 FF[-F[-B]+B]+F[-B]+B 3 FFFF[-FF[-F[-B]+B]+F[-B]+B]+FF[-F[-B]+B]+F[-B]+B

Axioma: BReglas: B F-[B]+B

F FF

Comando Acción F Dibujar hacia adelante un número determinado de

posiciones G Mover la tortuga hacia atrás un número de posicio-

nes, sin dibujar + Girar la tortuga hacia la derecha un ángulo determi-

nado. Si se especifica un número entero antes del signo, la tortuga realiza el giro esa cantidad de ve-ces.

- Idem, hacia la izquierda [ Guardar la posición y ángulo actual para uso ulte-

rior en una pila de estados guardados ] Eliminar el último estado guardado en la pila y res-

taurar la última posición y ángulo guardados | Mover la tortuga hacia adelante una longitud com-

putada, dibujando una línea desde la posición ante-rior hasta la nueva – En algunas aplicaciones, girar 90° o 180°

Ejemplos

• Generación de imágenes basadas en sistemas-L

• ...

5

SistemasSistemas--LL•• En principio fue un modelo topolEn principio fue un modelo topolóógicogico

–– No habNo habíía monitores gra monitores grááficos en 1968ficos en 1968•• Es posible aplicar una interpretaciEs posible aplicar una interpretacióón geomn geoméétrica (p. trica (p.

ej.ej. grgrááfico de tortuga*)fico de tortuga*)–– *Inventado por Seymour *Inventado por Seymour PapertPapert para Logo (1967) para Logo (1967) –– VersiVersióón n

simplificada de LISP simplificada de LISP –– Antecesor de Antecesor de StarLogoStarLogo•• TambiTambiéén interpretacin interpretacióón sonora (mn sonora (múúsica karnsica karnáática en tica en

base a modelos D0L)base a modelos D0L)•• Es un sistema de reEs un sistema de re--escritura, igual que una escritura, igual que una

gramgramáática tica chomskyanachomskyana contextcontext--freefree•• SzilardSzilard y Quinton (1979): Teorema y Quinton (1979): Teorema –– Los sistemas Los sistemas

D0L pueden generar fractalesD0L pueden generar fractales

Jerarquía de la complejidad - Chomsky• Gramáticas regulares (Tipo 3). Pueden consistir sólo de reglas de re-

escritura de tipo Ab, o AbC. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas deterministas de estado finito. Estos autómatas no tienen memoria. Reconocen o generan lenguajes regulares.

• Gramáticas independientes de contexto (Tipo 2). Sólo tienen reglas de forma A, y por lo tanto no tienen restricción en cuanto a la forma que pueden tomar las reglas de producción de la derecha. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas no deterministas de almacén o de pushdown (PDA). Estos autómatas tienen una memoria limitada y pueden, por ejemplo, llevar a cabo una comparación. Reconocen o generan lenguajes independientes del contexto.

• Gramáticas sensibles al contexto (Tipo 1). Pueden tener reglas de forma A, donde no es un elemento vacío. Corresponden a los lenguajes y conjuntos que pueden ser tratados por autómatas ligados linealmente. Poseen una memoria auxiliar semi-infinita, proporcional a la cantidad de elementos que deben tratar. Reconocen o generan lenguajes sensibles al contexto.

• Gramáticas irrestrictas (Tipo 0). Son idénticas a las anteriores, excepto por el hecho que puede ser nulo. Corresponden a los lenguajes y conjuntos susceptibles de ser tratados por máquinas de Turing. Poseen memoria irrestricta y pueden efectuar cualquier computación. Reconocen o generan lenguajes recursivamente enumerables.

6

Gramáticas - ¿No van más?

• Demostración de Stanley Peters y Robert Ritchie (1969)– Aún los autómatas más simples son

demasiado poderosos• Chomsky abandonó las gramáticas

ulteriormente• Ahora se definen más bien

constreñimientos (constraints)

Algunos tecnicismos

• Cuando se reescribe F o algunos de sus equivalentes, el sistema es “edgerewriting”

• Cuando se reescribe X, se habla de “node rewriting”

• Este último se utiliza generalmente para estructuras ramificadas.

• Recursividad...

Modelos procesuales

7

Ejemplares teóricos

• Benjamin Colby – El Contador de los Días.• Robert Randall – Modelo de toma de

decisiones (pesca Samal).• Young, 1980 – Modelo de decisiones de

diagnóstico de enfermedad entre los Tarasco.

• Schoepfle, Burton & Morgan 1984 – Los Navajo y el desarrollo energético – Decisióneconómica bajo incertidumbre política.

Colby – Gramáticas culturales• El contador de los

días (1981)• Los cuentos Ixil están

regidos por unagramática.

• Idones o unidadesnarrativas.

• Cartas eidocrónicas• Reynoso: Esta

gramática no tienevalor predictivo.

Colby – Gramática cultural

8

Crítica de la GC de Colby

• Una gramática consiste (básicamente) en un conjunto de reglas de reescritura:

• O SN+SV• SN A + N• SV V + SN

O

SN SV

A N V SN

A N

Los fenomenólogos distorsionan la antropología

Crítica (Continuación)

• Un template de posiciones posibles no es unagramática.

• Una gramática independiente de contexto no puedegenerar un texto.

• Sólo puede generar frases. Un texto no se reduce a un conjunto de frases.

• Al no especificarse constraints complejos y conocimiento enciclopédico, el relato de unagramática simple no tiene coherencia.

• En el caso de la GC de Colby, el protagonista se puede morir primero y casarse después, escaparsesin haber sido atrapado, resucitar sin haber muerto.

Alan Turing [1912-1954]

• Problemas computables• Máquinas de Turing – Modelos

ideales– Dispositivo de manipulación de símbolos

que puede simular la lógica de cualquier computadora– Proporciona una definición precisa de un algoritmo o

procedimiento mecánico

• Sistemas-L – Modelo de autómata mucho más simple que las máquinas de Turing (aunque extensible)

• Ejemplo: Visual Turing – Prueba: multiplicar2x2

Go...

9

Problemas formales• Prueba de [Kurt] Gödel (1931)

– Escasa consecuencia práctica• Problema de la detención (o decisión)

(Entscheidungsproblem)– Planteado por David Hilbert, 1928– 1936: Alonzo Church, Alan Turing– Es imposible decidirlo a priori, algorítmica y

generalmente– Inmensas consecuencias prácticas

• Problemas NP-completos, NP-duros, etc– Elaboración de métodos inspirados en evolución y

biología

Definición de problema(Hopcroft)

• Determinar si una expresión pertenece a un lenguaje (o si un elemento a un conjunto)– Gramática narrativa ixil de Benjamin Colby

• No se puede generar un texto con gramáticas independientes de contexto.

– Epistemología de la complejidad de Morin• No define problemas ni objetivos – El “método” no establece

procedimientos de resolución. No existen criterios de validación, ni implementaciones de referencia.

– Análisis estructural del mito (Lévi-Strauss)• La determinación de pertenencia de elementos a clases incluye

elecciones indecidibles, que tampoco pueden resolverse al azar.

– Modelo axiomático de matrimonio Kariera de Kemeny, Snell& Thompson

• Sistema axiomático mal construido.

Tipos de Sistemas-L

• Deterministas (D0L)– Formas más simples, trayectorias

• Sensible al contexto (IL)• L-Systems con corchetes [bracketed]

– Permiten modelar ramificación• Estocásticos• Paramétricos• Tabulados• Temporales, Propagativos, Ambientalmente

sensitivos, etc** Stelios Manousakis, tesis

10

Programas de gramProgramas de gramááticas ticas complejascomplejas

Programas de Sistemas-L• *Fractree• *Fractal Play (Fractal Games)• *Lyndyhop• Lsystems 4• LinSys 3D• LStudio (Prusinkiewicz)• *LS Sketch Book• *L-Systems Application applet• JFLAP – Programa de teoría de autómatas• A Musical Generator• *Visions of Chaos

*Fractree•• AntiguoAntiguo y y discontinuadodiscontinuado (1993), (1993), peropero decentedecente•• PermitePermite probarprobar iteracionesiteraciones con con tecladoteclado, lo , lo

cualcual eses prpráácticoctico•• No No poseeposee prestacionesprestaciones demasiadodemasiado

elaboradaselaboradas (p. (p. ejej. 3D) . 3D) peropero se se puedepuede avanzaravanzarsin sin escribirescribir

•• AdmiteAdmite unauna sola sola sustitucisustitucióónn•• No se No se puedepuede saber saber cucuááll eses la la secuenciasecuencia de de

comandoscomandos de de unauna iteraciiteracióónn•• A los A los archivosarchivos bbáásicossicos agreguagreguéé algunosalgunos queque

comienzancomienzan con BR con BR queque son son modelosmodelosculturalesculturales–– PolvoPolvo y y AlfombraAlfombra de Cantor, de Cantor, kkōōlalaṁṁ s, s, EspiralesEspirales

11

*Fractal Play (Fractal Games)

• Requiere JRE – No hay datos de autoría• Buen programa simple en 2D• Interface un poco incómoda, pero con

información sobre el estado del string– Útil para comprender la complejidad recursiva

• Formato de archivo y comando no documentado

• A los archivos originales, agregué modelosde kōlaṁ (Krishna y Serpiente) y espiralescomplejas

*Lyndyhop

• Requiere JRE• Muy simple pero práctico para aprender• Tiene visualización de evolución, mejor que

la de Fractal Play• También se visualiza el sistema a medida

que se lo compone con botones (único)• No tiene movimiento sin escritura (f) – No

puede modificarse el tamaño del paso• Ejercicio: Curva de Koch (F+F—F+F, 60°)

Go...

LSystemsLSystems 44

•• CapacidadCapacidad tridimensionaltridimensional•• PropPropóósitosito generalgeneral•• SintaxisSintaxis incompatibleincompatible•• FormatoFormato de de archivoarchivo imposibleimposible de de migrarmigrar•• TexturasTexturas, , peropero no no ray tracingray tracing (POV)(POV)

Go...

12

LinSys 3D

• Programado en 2001 y discontinuadoahora

• Sistema bracketed, sensible al contexto, estocástico y paramétrico

• Permite examinar evolución del sistema• Lenguaje de comandos complejo, con

alfabeto y reglas de producción• Cargar Spiral.lsys y examinar Go...

Fractal Studio

• El más elaborado y poderoso, tal vezdemasiado

• Evaluación expirada – Usar con fechaanterior a 2005

• Utiliza lenguaje L+C, que combinaconstructos de L-System (módulos y producciones) con C++

• Cargar objeto de directorio interno y probar

Modelos tri-dimensionales

13

Modelos tri-dimensionales

LS SketchBook

• Poderoso, profesional y bien documentado, pero un poco peculiar

• Discontinuado hace años, pero técnicamente vigente

• Sintaxis y formato de archivos incompatibles• Buena documentación geométrica y evolutiva• *Ejecutar secuencia de desarrollo una vez

visualizado (de buen efecto con espirales o con sympodial pruning)

Go...

14

LSystems Application Applet

• Interesante, con ejemplos raros• Puede procesar rectas o curvas

– Hermitte, Bspline• 38 muestras excelentes, incluidos

kōlaṁ s con curvas• No puede procesar muchas iteraciones

JFLAP

• Modelado de autómatas• No es particularmente apto ni bien

documentado, pero permite alineargramáticas y autómatas dentro de un mismo concepto

• L-Systems: Ejemplos de capítulo 10

15

*Visions of Chaos

• Programa de fractales de propósito general

• El módulo de L-Systems es excelente• Posee la mayor colección de ejemplos

de la industria• Único que puede generar música y

figuras simultáneamenteGo...

A Musical Generator 3.1

AplicacionesAplicaciones en en otrasotrasdisciplinasdisciplinas

16

Gift Siromoney[1932-1988]

• Matemático, teórico de la información, arqueólogo y etnógrafo

• Picture languages, 1972 – Array languages, 1974• Los L-Systems no tenían entonces implementación

gráfica• Identificó procedimientos regulares para el diseño de

kōlaṁ s:– kōlaṁ de matriz finita, kōlaṁ de matriz regular, kōlaṁ

regular independiente de contexto

• Los sistemas-L son más simples, pero las ideas de Siromoney fueron avanzadas para su época

kōlaṁ – Sistemas-L

kōlaṁ y simulación

17

kōlaṁ y simulación

kōlaṁ tamil

kōlaṁ tamil

18

Pongal kōlaṁ

kkōōlalaṁṁ rróómbicos y mbicos y nomenclaturanomenclatura

NomenclaturaNomenclatura

•• La matriz del La matriz del kkōōlalaṁṁ se considera como una serie de se considera como una serie de rombos de 5 rombos de 5 pullipulli, con 1 punto en cada extremo de la , con 1 punto en cada extremo de la cruz y un punto en el medio.cruz y un punto en el medio.

•• En figuras 1En figuras 1--55--1 hay 9 rombos1 hay 9 rombos•• Se empieza de arriba y de la izquierdaSe empieza de arriba y de la izquierda•• Se examina si existen cruzamientos de lSe examina si existen cruzamientos de lííneas en neas en

torno al rombo centraltorno al rombo central•• Cada cruzamiento vale 1, si no es 0.Cada cruzamiento vale 1, si no es 0.•• El 1El 1erer rombo es 1010 rombo es 1010 –– Eso es 10 decimal, A Eso es 10 decimal, A

hexadecimalhexadecimal•• La cantidad de variantes para rombos 1La cantidad de variantes para rombos 1--55--1 es 1 es

FFFFFFFFF=68.719.476.735FFFFFFFFF=68.719.476.735decdec + 1+ 1

19

Cómo se hace un kambi kōlaṁ•• Primero se construye la Primero se construye la

grillagrilla•• Luego se trazan lLuego se trazan lííneas neas

en un en un disdisññoo simsiméétrico, trico, dejando clarosdejando claros

•• DespuDespuéés se as se aññaden aden llííneas diagonalesneas diagonales

•• Desde cualquier punto Desde cualquier punto se traza una lse traza una líínea sobre nea sobre la grillala grilla

•• Se dobla cuando Se dobla cuando termina o cuando stermina o cuando sóólo lo hay dos lhay dos lííneas que se neas que se cruzancruzan

•• Cuando todos los Cuando todos los puntos se cierran, la puntos se cierran, la llíínea se encuentra nea se encuentra consigo misma.consigo misma.

Ejercicios posiblesEjercicios posibles

•• Establecer nomenclatura hexadecimal Establecer nomenclatura hexadecimal para dos para dos kambikambi kkōōlalaṁṁ definidos.definidos.

•• Trazar dos figuras de Trazar dos figuras de kkōōlalaṁṁ simsiméétricos tricos diferentes a los de los ejemplos.diferentes a los de los ejemplos.

Casos culturales

• Ron Eglash –African fractals, 1999 – Cruces etíopes

http://www.ccd.rpi.edu/Eglash/csdt/african/fractal/ethiop.htm

20

L-Systems, arquitectura, asentamientos y paisajes

Metáforas arquitectónicas• Christopher Alexander

– 1977. A Pattern Language: Towns, Buildings, Construction. Oxford, Oxford University Press.

– 1979. The Timeless Way of Building. Oxford, Oxford University Press.

• Patterns arquitectónicos• Revolución en técnicas de programación• Revolución en ingeniería y arquitectura de

software• AS – Promovido en CMU – SEI (Instituto de

ingeniería de sistemas de Carnegie Mellon)

Modular L-Systems

21

http://www.mh-portfolio.com/L_Systems/lsi.html

Arquitectura algorArquitectura algoríítmica tmica (cont.)(cont.)

•• SimulaciSimulacióónn–– SimulaciSimulacióón algorn algoríítmica de flujos para tmica de flujos para

evaluar funcionalidad de diseevaluar funcionalidad de diseññoo•• OptimizaciOptimizacióónn

–– Uso de algoritmo genUso de algoritmo genéético para optimizar tico para optimizar configuraciconfiguracióón y disen y diseñño de edificio/zonao de edificio/zona

•• PermutaciPermutacióónn–– Proceso de diseProceso de diseñño o paramparaméétricotrico

•• GeneraciGeneracióónn–– Desarrollo de lenguaje de diseDesarrollo de lenguaje de diseñño o

algoralgoríítmico generativo basado en tmico generativo basado en sistemassistemas--LL

•• TransformaciTransformacióónn–– DiseDiseñño mediante traslacio mediante traslacióón y visualizacin y visualizacióón n

de sitiode sitio

SimulaciSimulacióónn

22

OptimizaciOptimizacióón n -- Flujo de procesosFlujo de procesos

OptimizaciOptimizacióón n -- Flujo de procesosFlujo de procesos

PermutaciPermutacióónn

23

SelecciSeleccióón de variantesn de variantes

GeneraciGeneracióón de grn de grááfico de tortugafico de tortuga

GeneraciGeneracióón de grn de grááfico de tortugafico de tortuga

24

IntegraciIntegracióón con Maya, CAD, n con Maya, CAD, etcetc

25

26

Simulación de ciudades(CityEngine)

Simulación de ciudades(CityEngine)

27

Simulación de ciudades(CityEngine)

Modelo de Pompeya(Müller - CityEngine)

28

Müller & al – Shape grammars• Reconstrucción a partir de datos de GIS• Basada en la gramática de partición [split] de

Peter Wonka

29

Programas de Programas de shapeshape grammarsgrammars•• ShaperShaper 2D 2D –– Realizar ejercicioRealizar ejercicio

–– Generar un diseGenerar un diseñño islo isláámico en estrella (ver mico en estrella (ver TapratsTaprats))

Jerarquía (CityEngine)

30

SimulaciSimulacióón en 4 dimensiones (n en 4 dimensiones (WonkaWonka 2009)2009)

Derivaciones

• Combinaciones con AG y autómatas• Lechner & al – Modelos basados en agentes

31

Gramáticas de crecimiento• GroGra – Growth Grammar

Shape Grammars (Stiny)

32

Interpretación musical

• Longitud como duración, altura comoagudo/grave, espesorcomo volumen, color como timbre, líneasangulares comoglissando

• Ramificación comopolifonía

Axioma (fijo)

Reglas de producción

Interpretación de gráficosde tortuga (bidimensional)

Imagen

Intérprete musical (mapeadoespacial)

Partitura MIDI

Comandos de tortuga

Datos gráficos

Aplicaciones en música (1/2)

• Prusinkiewicz, Hanan, Siromoney – Músicakarnática, 1986

• Stefanie Mason, Michael Saffle – Música y L-Systems, 1994

• David Sharp – LMUSe, 1995-1998• John Belcher, James Murrel – Teorías

rítmicas africanas• Goodall y Watson – Lsys2MIDI, 1998• Luke DuBois – Jit.linden, 2003

33

Prusinkiewicz, Hanan

Aplicaciones en música (2/2)• Stelios Manousakis – Musical L-Systems (tesis),

2006• Peter Worth, Susan Stepney – Growing music

Programas L-System/Música

• *LMUSe• *A Musical Generator• The Symbolic Composer• FractMus 2000• Fractal Tune Smithy• Combinaciones diversas con autómatas

celulares y algoritmo genético• Etcétera

34

Conclusiones

35

Conclusiones

• Uno de los formalismos más poderosos en geometría fractal y ciencias de la complejidad

• Epistemológicamente importante, aunque no se lo utilice

• Infinidad de aplicaciones posibles• Un poco difícil de implementar, pero no

imposible

Tareas a realizar

• Averiguar si existen muchos diseños culturales regidos por “gramáticas”– Pongal kōlaṁ , rangoli, alpana, aripoma, lusona, mandala

• Verificar analogías en los métodos constructivos a través de las culturas

• Ejercitar definición de axiomas y reglas (no es fácil)– Es un problema inverso

• Realizar composición musical usando sistema-L• Investigar modelos derivados de simulación para

reconstrucción virtual de sitios, paisajes, objetos y patrones de asentamiento

Recursos

• Przemyslaw Prusinkiewicz, Aristid Lindenmayer. The algorithmic beauty of the plants. Springer, 2004

• Przemyslaw Prusinkiewicz. L-Systems and beyond. 2003.

• Prusinkiewicz, P., K. Krithivasan and M. G. Vijayanarayana. Application of L-systems to algorithmic generation of South India folk art patterns and Karnatic music, 1989

• Stelios Manousakis. Musical L-Systems, 2006

36

¿Preguntas?

Billyreyno@hotmail.com