Special Purpose Languages, parte 2

En el número anterior hice alusión a la plática que ofrecí en el pasado SG Conference & Expo. Durante ella analizamos brevemente la problemática que dio origen a la llamada “Crisis del software” (a partir de la cual se acuñó por cierto el término “Ingeniería de Software” en los 60), y describimos algunos enfoques que se han aplicado para abatirla, entre ellos los métodos formales, los cuales definimos y describimos brevemente en el número anterior y vimos que utilizan lenguajes formales (que definimos de manera no-formal) procesados por compiladores.

El “estado del arte” de nuestra industria ha estado fuertemente influenciado por el desarrollo de los que llamo: “lenguajes de computación”, que incluyen tanto los lenguajes de programación (de bajo y alto nivel; de primera, segunda, tercera, cuarta y quinta generación; procedurales, funcionales y lógicos, etc.), como los lenguajes de documentación, de especificación, y de arquitectura, entre otros.

En general, dichos lenguajes nos sirven para formalizar patrones que posibilitan la automatización.

Un caso un tanto distinto es el que comenzamos a revisar en el número pasado, en el que les pedí aplicar 3 veces la siguiente regla/patrón haciendo las sustituciones siempre en paralelo.

Por cuestión de espacio expongo aquí solo las primeras 2 transformaciones, en las que los colores tienen la intención de ayudar al seguimiento de las sustituciones (noten que hay ligeras variaciones en algunas inclinaciones de las figuras; finalmente las plantas son sistemas adaptativos).

Como pueden observar, este pequeño patrón, descrito con esa sencilla y única regla, parece describir el crecimiento de una planta (solo en 2 dimensiones). Lenguajes en los que las reglas se aplican en paralelo, se han utilizado para describir fenómenos de este tipo, y han dado lugar a toda una jerarquía de lenguajes conocida como Sistemas Lindenmayer (L-Systems), los cuales a su vez tienen relación con los fractales (el todo contenido en cada parte). Este enfoque viene de la biología (su creadora, Aristid Lindenmayer, era bióloga).

Por otro lado, los lenguajes que utilizamos en la computación utilizan reglas que se aplican no tanto en paralelo, sino más bien secuencialmente, y se definen con un marco conceptual que proviene de la Lingüística (Chomsky es lingüista).

Pero antes de entrar más en detalle con este último enfoque, déjenme abordar algunas cuestiones fundamentales utilizando el enfoque de conjuntos. Por favor, no pierdan de vista que estamos haciendo esto porque queremos describir cómo construir special purpose languages propietarios para incrementar la productividad y la calidad de nuestros procesos de desarrollo (y prueba) de software.

Definiciones

Un alfabeto es un conjunto finito de letras. En el caso del Español, ese conjunto tiene 30 letras (contando la ch, ll y la ü), con las cuales podemos construir palabras, oraciones y textos “correctos” en ese idioma, pero también frases que no se consideran parte del mismo (como “añu is morgen”). Podemos decir entonces que el Español es un conjunto de frases consideradas “correctas”, el cual a su vez es un subconjunto del de todas las frases que pueden escribirse con su alfabeto.

Generalicemos un poco y definamos el alfabeto B = {b₁, b₂, …, b_n}, un conjunto finito que contiene n caracteres. Diremos que tiene una cardinalidad de n, y lo escribiremos |B| = n.

Definamos ahora la concatenación entre caracteres de un alfabeto B como sigue:

b_i · b_j = b_ib_j
b_i · λ = λ · b_i = b_i (λ es la “cadena vacía: una cadena sin letras)
( b_i · b_j ) · b_k = b_i · (b_j · b_k ) = b_ib_jb_k

Adicionalmente, definamos el alfabeto C = {c₁, c₂, …, c_m}; C es también finito, con |C| = m.

Definamos la concatenación entre conjuntos de caracteres:

B · C  =        {  b₁c₁ , b₁c₂ , …, b₁c_m ,
    b₂c₁ , b₂c₂ , …, b₂c_m , 
    …,
    b_nc₁ , b_nc₂ , …, b_nc_m  }

B · C es también un conjunto finito, con cardinalidad |B·C | = n * m.

Definamos ahora la exponenciación de la concatenación aplicada a un conjunto de caracteres:

B^x = B · B^x-1
B⁰ = { λ } (El conjunto que tiene un solo elemento, que es la cadena vacía.)

B^x es un conjunto finito, de cardinalidad |Bx | = |B |x + 1 (por la cadena vacía).

Ahora definamos la operación conocida como Cerradura de Kleene:

B*  =  U^∞_i=0  Bⁱ
      =  B⁰ U B¹ U B² U B³ U ...     
      =  {  λ ,                               (λ cadena de tamaño 0)
             b₁, b₂, …, b_n ,               (n cadenas de tamaño 1)
             b₁b₁ , b₁b₂ , …, b₁b_n ,          (n2 cadenas de tamaño 2),
                 b₂b₁, b₂b₂ , …, b₂b_n ,
                    …,
                    b_nb₁ , b_nb₂ , …, b_nb_n , 

                 ...         }

Ciertamente, B* es un conjunto infinito, pero de los que llamamos “contable”, pues podemos utilizar los números naturales IN (IN = {0, 1, 2, …}) para listar todos sus elementos en orden: para i = 0 (un número natural) sabemos que hay 1 cadena (otro número natural), para i = 1 sabemos que hay n cadenas, para i = 2 hay n², y así sucesivamente. Esto permite decir que la cardinalidad de B* es la misma que la de IN. En otras palabras: dado el alfabeto finito B, podemos construir tantas cadenas con sus caracteres como números naturales hay.

Lo anterior es cierto independientemente de la cantidad de elementos de B. Si B fuera la más grande extensión del código ASCII, esto implica que la cantidad de cadenas de caracteres que podemos escribir en una computadora (o en cualquier dispositivo para procesar información) es infinita, pero es contable.

Finalmente: dado el conjunto A, ɚ(A) (“el conjunto potencia del conjunto A”) denota el conjunto conformado por los subconjuntos de A. Algunos ejemplos:

  Si A = { }, entonces ɚ(A) = {{}},                                             y |ɚ(A)| = 1.
  Si A = { a₁ }, entonces ɚ(A) = {{}, {a1 }},                                y |ɚ(A)| = 2.
  Si A = { a₁, a₂ }, entonces ɚ(A) = {{}, {a₁ }, {a₁ }, {a₁, a₂} },     y |ɚ(A)| = 4.

Podemos demostrar que en general, |ɚ(A)| = 2^|A|.

Ahora estamos en posición de definir con mucha precisión qué es un lenguaje en términos de conjuntos:

Dado un alfabeto finito B, un lenguaje formal sobre B es cualquier subconjunto de B*. (Dado un código ASCII extendido de 256 caracteres, Java es un subconjunto especial de cadenas escritas utilizando ese ASCII.)

Preguntas

Regresaremos al punto anterior más adelante, pero antes, quisiera hacer notar que a partir de lo descrito anteriormente se desprenden varias preguntas interesantes:

• Dado un alfabeto B, ¿cuántos lenguajes podemos construir con sus caracteres?
• ¿Podríamos procesarlos todos? (v.gr. mediante compiladores o intérpretes)
• ¿Qué tan complejo y eficiente sería ese procesamiento? (en términos computacionales)

Piensen sus respuestas; continuaremos abordando este tema en el siguiente número.

Referencias

1. L. León. “Los Special Purpose Languages, parte 1”. Revista Software Guru #48. 
   http://sg.com.mx/revista/48/los-special-purpose-languages-0