Special Purpose Languages, parte 3

 En el número anterior definimos lo que es un lenguaje formal de la siguiente manera:

1. partimos de la definición del concepto de alfabeto como un conjunto finito de caracteres B = { b1 , b2 , …, bm }, y dijimos que B tiene una cardinalidad (cantidad de elementos) igual a m , lo cual escribimos como |B| = m ;
2. definimos la operación de concatenación ‘·‘ sobre caracteres (lo que nos permite construir b5· b4· b8· b8 ) y sobre conjuntos de caracteres (lo que nos permite construir B · A · C ) ;
3. definimos la exponenciación de la concatenación Bx sobre un alfabeto B como la aplicación de la concatenación x-1 veces sobre el alfabeto ( B · B · … · B , donde B aparece x veces) ;
4. definimos la cerradura de Kleene B* como la unión de todas las exponenciaciones sobre el alfabeto B (B* = U∞i=0 Bi ) ;
5. definimos que un lenguaje formal sobre un alfabeto B es cualquier subconjunto de B* .

De lo anterior se desprende que, dado un código ASCII extendido que llamaremos AE de cualquier cantidad de caracteres, podemos ver al lenguaje Java como el subconjunto de cadenas de cualquier longitud escritas utilizando ese AE que son aceptadas como “correctas” por el compilador de Java. Lo mismo es cierto si sustituimos “Java” por el nombre de cualquier lenguaje de computación.

Ahora bien, en AE* están incluidos no solo todos los lenguajes de programación existentes y por existir, sino también todos los compiladores (escritos y por escribirse) de todos esos lenguajes. De hecho, en AE* se encuentran todas las cadenas de caracteres que podamos escribir en esa extensión del ASCII, incluyendo los programas “incorrectos” en todos los lenguajes.

Contestemos ahora las primeras 2 preguntas que planteamos al final del número anterior, en el cual dijimos que dado un conjunto A que tiene i elementos, la cantidad de subconjuntos que pueden formarse sobre A es igual a 2i .

Dijimos también que B*, la Cerradura de Kleene sobre el alfabeto B, es un conjunto infinito pero contable, porque tiene la misma cardinalidad que el conjunto de los números naturales N. Esto implica en particular que, así como ocurre en el conjunto de los números naturales N, dada una de las cadenas de B*, siempre podemos definir cuál es la que le sigue y listar sus elementos en orden sin saltarnos alguno (en N , dado un número natural y, sabemos que el que le sigue es y+1).

Del penúltimo párrafo se sigue que la cantidad de lenguajes sobre cualquier alfabeto B es igual a 2N … El asunto es que 2N es una cardinalidad estrictamente mayor que la de N (siguiendo el Teorema de Cantor), lo que lo vuelve un conjunto no-contable (aquellos conjuntos en los que, dado un elemento x, no es posible decir cuál elemento es el que sigue, como en el caso de los números reales R : si tenemos el número 0.0004 no podemos decir que el que le sigue es 0.0005; tampoco que es 0.00041; en realidad, entre cualesquiera 2 números reales hay una cantidad infinita de números reales).

Una consecuencia importantísima de lo anterior es que la cantidad de lenguajes (2N) que pueden definirse sobre un alfabeto es estrictamente mayor que la cantidad de cadenas (N) que pueden construirse sobre ese alfabeto, así es que: independientemente del tamaño del alfabeto, siempre tendremos lenguajes sobre ese alfabeto para los que no podemos definir un compilador, esto es, siempre habrá lenguajes que no podremos procesar.

Para nuestro propósito de construir lenguajes propietarios, esto significa que para poder procesarlos, en principio debemos observar algunas restricciones para su diseño. El lado bueno de esto es que, dado que estamos acostumbrados a utilizar lenguajes de programación y sus estructuras obviamente son procesables, podemos incluir estructuras de ese tipo en nuestro lenguaje. El lado malo es precisamente eso mismo: como estamos acostumbrados a ello, probablemente no incluyamos otras estructuras que serian más adecuadas para las actividades que nuestros programadores automatizarán.

El punto no es para subestimarse: las estructuras que tenemos a nuestra disposición en un lenguaje (sea artificial o natural) pueden imponer límites a lo que podemos expresar (sea programar o pensar); como ejemplo tenemos el comentario del reconocido científico computacional C.A.R. Hoare sobre su método de ordenamiento Quick-Sort, después de que tomó un curso de Algol-60 (primer lenguaje en ofrecer la posibilidad de escribir subrutinas recursivas):

“Fue entonces que aprendí por primera vez sobre procedimientos recursivos y vi cómo programar el método de ordenamiento que previamente había tenido tanta dificultad para explicar.”

Para contestar la tercera pregunta necesitaremos elementos que revisaremos más adelante; pero antes, veamos algunos ejemplos.

Ejemplos con “especificaciones algebráicas”

Usando las definiciones arriba mencionadas y tomando como convención que escribiremos:

• bibj en lugar de bi· bj (concatenación de caracteres);
• bin en lugar de bi· … · bi (concatenación en la que bi aparece n veces);
• a en lugar de b1 , b en lugar de b2 , c en lugar de b3 , y d en lugar de b4 (haciendo concreto el alfabeto abstracto
  B = { b1 , b2 , …, b4 } ) ;

especifiquemos algunos lenguajes formales:

• am bn ci , para m, n, i enteros mayores a cero e independientes entre sí. Este sencillo lenguaje, que llamaremos L1 , especifica todas las cadenas que tienen una o más a’s seguidas por una o más b’s seguidas por una o más c’s.
• am bn cn dm , para m, n ≥ 0 . Obviando detalles, este lenguaje que llamaremos L2 (más complejo que L1 ), es una abstracción de los sublenguajes incluidos en prácticamente todos los lenguajes de programación, en los que por ejemplo, los paréntesis y las llaves deben venir por pares (uno de cierre por cada uno de apertura) y estar “emparejados adecuadamente” (por ejemplo, no se acepta “ ( … {… ( … ) … ) … } ” ) ;
• am bn cm dn , para m, n ≥ 0 . Obviando detalles, este lenguaje que llamaremos L3 (más complejo que L2 ), es una abstracción de la especificación del mecanismo de paso de parámetros que utilizan muchos lenguajes de programación para exigir que la cantidad de parámetros establecidos en la definición de una subrutina sea la misma que cuando ésta se utiliza.

Gramáticas

Después de esa primera definición de lenguaje en términos de concatenaciones sobre alfabetos, que podríamos llamar algebraica y que es más bien declarativa, tomaremos ahora un enfoque un poco más imperativo utilizando reglas (que pueden verse como una abstracción del concepto de patrones).

Podemos definir lenguajes utilizando gramáticas, las cuales son cuátruplas de la forma

< T, N, S0 , R > donde

T es el conjunto de los símbolos terminales del lenguaje (en adelante “Terminales”), los cuales podemos ver como el alfabeto con cuyos elementos finalmente se construyen las cadenas de caracteres;

N es el conjunto de los símbolos no-terminales del lenguaje (en adelante “no-Terminales”); aquellos símbolos abstractos que deben definirse en términos de Terminales y no-Terminales; nota: debe cumplirse que T ∩ N = {} ;

R es el subconjunto del producto cartesiano
(T ∪ N)* x (T ∪ N)* que define la relación matemática que denota las reglas de reescritura del lenguaje (en adelante “Reglas”);

S0 es el elemento distintivo de los no-Terminales llamado “Símbolo-inicial”, que es con el que inicia el “procesamiento” de R .

Escribiremos las Reglas utilizando el “meta-lenguaje” (llamado así porque es un lenguaje con el cual definimos lenguajes) llamado BNF (Backus-Naur Form). En él, para cada regla se coloca el primer elemento del producto cartesiano, seguido del símbolo “→” seguido del segundo elemento del producto cartesiano.

Ahora bien, cuando tengamos un conjunto de reglas como

α → β1
α → β2
…
α → βn , donde α y todas las βi son elementos de (T ∪ N)* (o sea, elementos de la cerradura de Kleene de la unión de los Terminales y no-Terminales; es decir, combinaciones de uno o Terminales y no-Terminales),

lo escribiremos como

α → β1 | β2 | … | βn

Si alguna βi contiene cero Terminales y cero no-Terminales, la escribiremos como λ (la letra griega lambda), que representará la cadena vacía.

Además, escribiremos los Terminales con minúsculas, los no-Terminales con MAYÚSCULAS, y S0 será el no-Terminal que aparece a la izquierda de “→” en la primer Regla. Con ello R define la gramática por sí sola, porque con las convenciones queda explícito cuáles son los Terminales, los no-Terminales y S0 . Entonces, en adelante podremos definir un lenguaje listando únicamente las reglas de R .

Una jerarquía de lenguajes

Tenemos la siguiente categorización de lenguajes, que se hace considerando la complejidad de la estructura de las reglas en la R particular que los define (por cuestiones de espacio, obviaremos algunos detalles):

• Llamaremos gramáticas regulares a aquellas cuyas reglas en R sean de la forma A→ B d | d (o menos compleja); y llamaremos lenguajes regulares (o de Tipo 3, o Lgs3 de manera corta) a aquellos que puedan definirse utilizando gramáticas regulares. Nota: las reglas pueden ser de la forma A→ d B | d , pero no se deben mezclar ambas formas.)
• Llamaremos gramáticas libres de contexto a aquellas cuyas reglas en R sean de la forma A→ α (o menos compleja), y lenguajes libres de contexto (o de Tipo 2, o Lgs2) a aquellos que puedan definirse utilizando gramáticas libres de contexto.
• Llamaremos gramáticas sensibles al contexto a aquellas cuyas reglas en R sean de la forma β1 A β2 → β1αβ2 (o menos compleja), donde α ≠ λ ; y lenguajes sensibles al contexto (o de Tipo 1, o Lgs1) a aquellos que puedan definirse utilizando gramáticas sensibles al contexto. Decimos que β1 y β2 representan el contexto en el que A se puede transformar en α .Ahora bien, como α ≠ λ , entonces la suma de la cantidad de Terminales y de no-Terminales en α es mayor o igual a uno; a esta cantidad la llamaremos la longitud de α y la denotaremos con |α|. Ahora podemos generar otra definición menos restrictiva (aunque una que no deja ver el atributo de “sensible al contexto”): llamaremos gramáticas sensibles al contexto a aquellas cuyas reglas en R sean de la forma
  θ → α (o menos compleja), donde θ ∈ (T ∪ N)* , θ ≠ λ y |θ| ≤ |α| ; y llamaremos lenguajes sensibles al contexto a aquellos que puedan definirse utilizando este tipo de gramáticas
• Por último, llamaremos gramáticas estructuradas por frases a aquellas cuyas reglas en R sean de la forma θ → α (o menos compleja), donde θ∈ (T ∪ N)* y θ ≠ λ ; y llamaremos lenguajes estructurados por frases (o Tipo 0, o Lgs0) a aquellos que puedan definirse utilizando gramáticas estructuradas por frases.

Lo anterior define lo que es conocido como la Jerarquía de Chomsky, en la cual ocurre, como se puede observar, que Lgs3 ⊂≠ Lgs2 ⊂≠ Lgs1 ⊂≠ Lgs0 (esto es, los Lgsi son subconjuntos propios de los Lgsi-1). Para el caso particular de Lgs3 ⊂≠ Lgs2 , esto significa que todos los lenguajes regulares (todas las gramáticas regulares) son libres de contexto, pero que hay lenguajes libres de contexto que no son regulares (para los que no existen gramáticas regulares que los definan).

La Jerarquía de Chomsky muestra con claridad un crecimiento significativo en la complejidad de la estructura de las reglas, o dicho de otra manera, una disminución significativa en las restricciones sobre esa estructura. Esto obviamente impacta en la complejidad (incluso en la posibilidad) de procesar todos esos tipos de lenguajes. Retomaremos el tema con más profundidad más adelante.

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
2. L. León. “Los Special Purpose Languages, parte 2”. Revista Software Guru #50.
   http://sg.com.mx/revista/50/los-special-purpose-languages-2