El impacto de los lenguajes propietarios de propósito particular: Una visión panorámica

Suele ser difícil percibir el impacto que tienen los lenguajes en nuestra civilización, pues es algo que vivimos cotidianamente. En el ámbito de los lenguajes naturales, Koen DePryck (en su libro sobre “The Ontology of Language”) nos dice:

“Our language has its historical roots in the world, so that the history of the world is the history of our language, and so that the world is language.”
 

Ya en nuestro campo, el reconocido computer scientist C.A.R. Hoare comentó en algún momento, refiriéndose a su método de ordenamiento Quick-Sort y después de tomar un curso de Algol-60 (primer lenguaje en ofrecer la posibilidad de escribir subrutinas recursivas):
 

“It was there that I first learned about recursive procedures and saw how to program the sorting method which I had earlier found such difficulty in explaining.”

 

Los lenguajes nos proveen de muchas estructuras que facilitan que hagamos eficientemente muchas cosas, pero que al mismo tiempo pueden dificultar ver otras que pudieran ser igualmente importantes. 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).

En los últimos números de esta columna hemos abordado los lenguajes formales desde distintos puntos de vista, buscando generar el contexto para mostrar la utilidad y el impacto de contar con lenguajes propietarios en nuestras organizaciones para documentar, especificar, programar, o probar productos de software. En el caso de la programación, el contar con un lenguaje propietario de más alto nivel que el que usa actualmente una organización permitiría destinar más tiempo al diseño del producto que a la escritura del programa, lo que facilitaría el incremento de la calidad; al no ser necesario atender tantos detalles, habría menos probabilidad de introducir errores, lo cual también facilitaría el incremento de la calidad; y al ser estos lenguajes más expresivos, se podría entregar el producto más rápidamente, facilitando el incremento de la productividad.

En este número abordaremos un ejemplo con el que buscaremos evidenciar los beneficios anteriores. Para ofrecer aquí la idea adecuadamente, permítannos primero retomar los puntos más relevantes que expusimos en otros números y que contextualizan la presentación del ejemplo.

1. Lenguajes - Patrones

Comenzamos abordando el concepto “lenguaje” como algo muy general, en términos de “patrones” en SG#48 (“el número 48 de la revista”):

En la figura de abajo, consideren que la sustitución de lo que está a la izquierda del símbolo “⇒” por lo que está a su derecha ocurre siempre “en paralelo”; es decir: que todas las apariciones de lo que está a la izquierda de “⇒” deben sustituirse por lo que está a la derecha simultáneamente.

Si aplicamos 3 veces esa regla/patrón (en paralelo) tenemos:

                              

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”).
 

2. Lenguajes formales

Luego, en SG#50, abordamos “lenguaje” desde una perspectiva más bien matemática (algebraica):

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 .

 

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 ⋅ D ).

 

Luego 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 ≥ 0  veces).

 

Después definimos la cerradura de Kleene  B*  como la unión de todas las exponenciaciones sobre el alfabeto B  (B*  =  U∞i=0  Bi ).

Finalmente definimos que un lenguaje formal sobre un alfabeto B  es cualquier subconjunto de B*.   Definimos la cerradura positiva  B+  como B+  = B ⋅  B*    (B+ contiene cadenas con al menos un caracter).
 

Explicitamos que, dado un código ASCII extendido que aquí llamaremos AE, que extienda el usado hoy en día con cualquier cantidad (finita) 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.

 

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.
 

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).  

 

De lo anterior 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.

 

3. Gramáticas

En SG#51, revisamos “lenguaje” desde un punto de vista un poco más “computacional”, pero aún “declarativo”, utilizando reglas (que pueden verse como una abstracción del concepto de patrón):

 

Dijimos que 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”); son finalmente los elementos constituyentes de las secuencias de símbolos de una cadena del lenguaje;

λ es con lo que designamos la “cadena nula” (aquella que no contiene símbolos);

N es el conjunto de los símbolos no-terminales del lenguaje (en adelante “no-Terminales”); no constituyen necesariamente cadenas finales, pues son definidos en términos de una combinación de Terminales y no-Terminales.        

Nota: En estas definiciones, debe cumplirse que T ∩ N = {} ;

R es el subconjunto del producto cartesiano  (T ∪ N)* ×  (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 .

 

Escribimos 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.



4. Jerarquías de Lenguajes

Con la definición anterior, en SG#51 y SG#52 revisamos una Jerarquía de Lenguajes Formales (que dijimos, incluye la Jerarquía de Chomsky):

La siguiente categorización de lenguajes 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):

1. Llamamos gramáticas regulares a aquellas cuyas reglas en  R  sean de la forma    A→ B d  | d    (o menos compleja); y llamamos lenguajes regulares (o de Tipo 3, o Lgs3 de manera corta) a aquellos que puedan definirse utilizando gramáticas regulares.
2. Llamamos 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. Dentro de estos lenguajes existen varias divisiones. Una de las más relevantes es la que diferencia entre los lenguajes determinísticos y los lenguajes no-determinísticos (un ejemplo de estos últimos es  an bn  ∪ an b2n  , que como podrán intuir, para procesarlo es necesario que el compilador asociado realice backtracking).
3. Llamamos 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 denotamos con|α|. Ahora podemos generar una definición equivalente pero menos restrictiva (aunque no hace evidente el atributo “sensible al contexto”):  Llamamos también gramáticas sensibles al contexto a aquellas cuyas reglas en  R  sean de la forma    θ → α   (o menos compleja), donde θ ∈ (T ∪ N)* ,  θ ≠ λ  y |θ| ≤ |α| ; y llamamos lenguajes sensibles al contexto a aquellos que puedan definirse utilizando este tipo de gramáticas.
4. Llamamos gramáticas estructuradas por frases a aquellas cuyas reglas en  R  sean de la forma  θ → α  (o menos compleja), donde θ ∈ (T ∪ N)*  y θ ≠ λ ; y llamamos lenguajes estructurados por frases (o Tipo 0, o Lgs0) a aquellos que puedan definirse utilizando gramáticas estructuradas por frases. Dentro de estos lenguajes se encuentra la importantísima clase los Lenguajes Decidibles (o Recursivos, o Lgsdec), que son  aquellos para los que es posible construir programas (por ejemplo compiladores) que siempre terminan y anuncian si la cadena es elemento del lenguaje o si no lo es (aunque para ello requieran enormes cantidades de tiempo y/o memoria). Las reglas con las que se definen tienen la misma forma que los Lgs0.   Podemos ver a los Lgs0 como lenguajes semi-decidibles: los programas que los procesan (por ejemplo compiladores) pueden determinar cuando las cadenas sí son elementos del lenguaje, pero cuando no es así continúan su procesamiento indefinidamente (“se ciclan”).
5. Llamamos Lenguajes Generales (o Lgsgral) a aquellos que incluyen a todos los anteriores y a los que no son susceptibles de ser definidos mediante reglas.

La Jerarquía muestra 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). En ella ocurre (obviando algunas precisiones) que  Lgs3 ⊂≠ Lgs2 ⊂≠ Lgs1 ⊂≠ Lgsdec ⊂≠ Lgs0 ⊂≠ Lgsgrals.

También revisamos los siguientes lenguajes “prototípicos” expresados en forma algebraica:

• L1 :  a m b n c k d i  ,  para m, n, i, k  ≥  0 e independientes entre sí:

Se trata de una Gramática Regular. Este tipo de gramáticas tienen el mismo poder expresivo para definir lenguajes que las conocidas expresiones regulares, y son suficientes para especificar los “scanners” de los compiladores, los cuales se encargan del análisis lexicográfico.

• L2 :  a m b i c i d m  ,  para m, i  ≥  0  que aparecen por pares y están “anidadas”:

Este es un ejemplo “clásico” de una Gramática Libre de Contexto.

Este tipo de gramáticas tienen el mismo poder expresivo para definir lenguajes que los conocidos grafos de sintaxis, y son suficientes para especificar los “parsers” de los compiladores, los cuales se encargan del análisis sintáctico.

• L3 :  a m b i c m d i  ,  para m, i  ≥  0 , que aparecen por pares pero no están “anidadas”:

Con este tipo de lenguajes se podrían especificar (al menos buena parte de) los Sistemas de Tipos de los lenguajes de programación, los cuales definen sus aspectos semánticos (de significado, como los del paso de parámetros que mencionamos, o la equivalencia de tipos). Sin embargo, dado que el procesamiento de estos lenguajes es más complejo y costoso en tiempo que el de las Libres de Contexto, y que la mayoría de los constructos de los lenguajes de computación son de este último tipo, los aspectos semánticos se suelen abordar apoyándose en gramáticas Libres de Contexto y en una Tabla de Identificadores en la cual suele almacenarse, entre otras cosas, el nombre, la clase (si es variable, procedimiento, función, etc.), el tipo (v.gr. integer, string, 〈char, real〉 → boolean), y la dirección de cada identificador.

 

Después, en SG#53 mencionamos que existen también otras jerarquías de lenguajes, y revisamos la de las Left-Assotiative-Grammars:

En nuestra primera columna sobre el tema del desarrollo de lenguajes propietarios mencionamos un enfoque sobre lenguajes formales llamado Sistemas Lindenmayer (proveniente de la Biología), dado nuestro interés en encontrar mecanismos para eficientar el desarrollo de software, en números posteriores estudiamos los lenguajes formales utilizando principalmente los trabajos sobre gramáticas del lingüista Noam Chomsky, las cuales se conocen como Gramáticas Estructuradas por Frase, y en un número reciente presentamos una jerarquía de las mismas. Se presume que, en esa jerarquía, los lenguajes naturales se encuentran en la clase de los Lenguajes Sensibles al Contexto.

En realidad, las Gramáticas Estructuradas por Frase son un tipo particular de las llamadas Gramáticas Generativas, que son sistemas (“recursivos”) de reglas provenientes de trabajos en Lógica Matemática.

Algunos de los enfoques más relevantes que han sido utilizados para abordar las Gramáticas Generativas son:

1. Gramáticas Categóricas (“C-Grammars”): desarrolladas inicialmente en 1929 por el polaco Lesniesvsky, y aplicadas al los natural lenguajes por primera vez por Bar-Hillel en 1953.
2. Gramáticas Estructuradas por Frase (PS-Grammars): basadas en los “Rewrite Systems” de Emil Post desarrollados en 1936, aplicadas a los lenguajes naturales por primera vez por Chomsky en 1957.
3. Gramáticas Asociativas por la Izquierda (Left-Assotiative-Grammars): desarrolladas en 1985 por Roland Hausser para procesar lenguajes naturales.

Los dos primeros enfoques presentan el problema de que los recursos requeridos (tiempo y/o memoria) para hacer el procesamiento de lenguajes naturales son demasiado grandes como para llevarlos a la práctica. El tercero muestra algunas bondades al respecto.

Formalmente, una Gramática-LA (del Inglés Left-Associative Grammar, LAG) es una séptupla de la forma:
 

〈 W, C, LX, CO, RP, SI , SF 〉    donde
 

W es un conjunto finito de las llamadas Word surfaces ;

C es un conjunto finito de Category segments ;

L ⊃  ( W × C+ ) es un conjunto finito conteniendo el Léxico ;

CO = ( co1, …, con-1 ) es una secuencia finita de funciones recursivas totales (entiéndase “programas”) de (C* × C+) a (C* ∪ {⊥})  llamadas Categorial Operations ;

RP = ( rp1, …, rpn-1 ) es una secuencia finita ( igualmente larga que CO ) de subconjuntos de n  ( donde n = { i | 0 ≤ i < n} )  llamada Rule Packages ;

SI = { ( cs1   rps1 ) … ( csk   rpsk ) } es un conjunto finito de eStados Iniciales, donde cada c ∈ C+ y cada rp es un subconjunto de n llamado paquete de reglas de inicio;

SF = { ( cf1   rpf1 ) … ( cfk   rpfk ) } es un conjunto finito de eStados Finales , donde cada c ∈ C* y cada rp ∈ RP .

Así como con las Gramáticas Estructuradas por Frase de Chomsky que estudiamos,  en el conjunto de lenguajes generados por Gramáticas-LA también tenemos subclases:

• Las Gramáticas-LA generales (Allgemeine (general en alemán)), o A-LAGs, corresponden a la definición de arriba.
• Las Gramáticas-LA limitadas (Bounded) linealmente, o B-LAGs, son la subclase de las A-LAGs en las cuales la longitud de las categorías está limitada linealmente con respecto a la longitud de la cadena de entrada.
• Las Gramáticas-LA limitadas por una constante (Constant), o C-LAGs, son la subclase de las B-LAGs en las cuales la cantidad de cálculos requerida por operaciones categóricas individuales está limitada por una constante.

Dentro de estas C-LAGs tenemos las subclases de C3-LAGs , C2-LAGs , y C1-LAGs .
 

La siguiente es la relación de las LAGs con la Jerarquía de Chomsky (incluimos algunos aspectos de rendimiento, que eventualmente abordaremos en números posteriores).

El conjunto de Gramáticas-LA…

• generales o A-LAGs, aceptan y generan todos los Lenguajes Recursivos (o “Decidibles”), algo relevante, pues como vimos en un número anterior, en la Jerarquía de Chomsky no había un tipo de gramática específica que definiera exactamente este tipo de lenguajes.
• bounded o B-LAGs, aceptan y generan todos los Lenguajes Sensibles al Contexto (LSC).
• constant o C-LAGs, constan de 3 subclases:
• C3-LAGs contiene los Lenguajes Libres de Contexto (LLC) más complejos y algunos LSC que son “NP-Complete” (la clase de problemas para los cuales no se han descubierto algoritmos eficientes que los resuelvan, y se piensan que no existen). Para procesar estos lenguajes se requiere tanto tiempo que hacerlo se vuelve prohibitivo en la práctica (técnicamente: requieren “tiempo exponencial”, lo que significa que pueden procesarse en un tiempo expresado como una base elevada a un exponente el cual está en función de la cantidad de datos de entrada).
• C2-LAGs contiene varios LLC “no-deterministas” (su procesamiento implica backtracking) y varios LSC simples. Para procesarlos se requiere tiempo polinomial.
• C1-LAGs contiene todos los LLC “deterministas” (no requieren backtracking para procesarlos) y varios LSC simples. Su procesamiento solo requiere tiempo lineal, lo que los vuelve muy útiles en la práctica.

Dijimos que se piensa que en esta jerarquía, los lenguajes naturales están dentro de la clase C1-LAG, lo cual significaría que su procesamiento sí puede realizarse en la práctica, aún con altos volúmenes de datos de entrada.

 

5. Semántica formal

Todo el análisis anterior estuvo más bien orientado a la Sintaxis de lenguajes formales, pero en SG#56 también abordamos el tema de la Semántica de los lenguajes formales:

La sintaxis de un lenguaje –que se refiere a su estructura– es un aspecto muy importante del mismo y se utiliza ampliamente en el desarrollo de compiladores.

La “Semántica Formal” –que se refiere al significado de un lenguaje (aunque hay quien dice que “Semantics is what we have in our minds; when one writes it down, it is not semantics any more.”)– es muy importante también porque agrega precisión a la definición del lenguaje, pero actualmente no es tan común que se utilice en la construcción de compiladores (lo cual puede conducir a que v.gr. un programa dado a 2 compiladores diferentes para el mismo lenguaje tenga comportamientos distintos).

La Semántica define el significado de un lenguaje a partir de los constructos del mismo, y con ello también el de los programas escritos en él. Existen varios enfoques para hacerlo; entre los más importantes se encuentran:

• El Operacional: se especifica la semántica proporcionando (el código fuente de) un intérprete que define el comportamiento de los programas de ese lenguaje. Este enfoque, al ser tan operativo, no permite razonar sobre el lenguaje (mediante mecanismos lógico-matemáticos).
• El Axiomático: la semántica se especifica definiendo una “teoría matemática” para el lenguaje con la cual se puedan probar propiedades de programas escritos en ese lenguaje. Más que en lo que significa el lenguaje, el énfasis está en lo que puede probarse acerca de él.
• El Denotacional: se especifica la semántica asociando a cada constructo del lenguaje un conjunto de funciones matemáticas que definen los significados denotando conjuntos. La semántica está dada en términos de conjuntos, funciones, relaciones, tuplas, predicados, y operaciones sobre estos elementos. Este enfoque tiene un nivel de abstracción aún mayor al del enfoque Axiomático.

6. Máquinas Abstractas y Lenguajes

En SG#54, tomamos un punto de vista muy procedural y revisamos el concepto “lenguaje” a la luz de las llamadas Máquinas con (conjuntos de) Estados Finitos (o Finite States Machines), MEFs, que pueden procesarlos:

Las MEFs que presentamos tienen en común que:

• están constituidas por un conjunto finito de estados (S) en los que la MEF puede encontrarse cuando procesa la cadena de entrada; hay un estado inicial (ι ) en que la MEF comienza su procesamiento y un estado (h) (o más (F), dependiendo del tipo de MEF) en el (los) que puede terminarlo;
• los símbolos que conforman la cadena de entrada son elementos de un conjunto finito (el “Alfabeto” A);
• las operaciones de la MEF se definen mediante una relación (en el sentido matemático) de transición ρ  , que toma el estado en el que se encuentra la MEF en ese momento y el símbolo actual de la cadena de entrada (y, como veremos, eventualmente otras cosas, dependiendo del tipo de MEF), y regresa el estado al que la MEF debe moverse (y eventualmente otras cosas, como veremos); si la relación de transición ρ  es una función (en el sentido matemático), entonces se le denota con δ  y se dice que la MEF es determinística, en caso contrario se que la MEF es no-determinística.

 

Vimos MEFs particulares:
 

Los Autómatas Finitos (AFs) (ó Finite Automata) se definen como quíntuples de la forma      AF = 〈 S,ι, F, A, ρ 〉  . Pueden procesar los Lenguajes Regulares (como  am bn ek d  ,  para m, n, k, i  ≥ 1 e independientes entre sí).

Los Autómatas de Pila (APs) (ó Push Down Automata) se definen como séxtuples de la forma    AP = 〈 S,ι, F, A, Σ, ρ 〉 ,    

en los cuales   Σ   es el alfabeto de la pila.  Pueden procesar los Lenguajes Libres de Contexto (como  ai bn en d i  ,  para n, i ≥  1 ).

Las Máquinas de Turing (MTs) (ó Turing Machines) se definen como séxtuples de la forma    MT = 〈 S,ι, h, A, Π, ρ 〉 ,    

en los cuales   Π  es el alfabeto de la cinta de Procesamiento. Pueden procesar los Lenguajes Estructurados por Frases.

Los Autómatas Delimitados Linealmente (ADLs) (ó Linear Bounded Automata) son MTs que para procesar una cadena solo requieren una cantidad de celdas en la cinta de procesamiento prácticamente igual a la de la cadena de entrada. Pueden procesar los Lenguajes Sensibles al Contexto (como ai bn ei d n  ,  para n, i ≥ 1 ).

Las Máquinas de Turing que terminan (MTtsterm) son MTs que siempre culminan el procesamiento de cualquier cadena  –aunque eventualmente después de mucho tiempo.  Las MTsterm pueden procesar los Lenguajes Decidibles.
 

7. Lenguajes y Compiladores

En SG#52, asumimos una actitud más “práctica”  y abordamos el concepto “lenguaje” desde la construcción de programas que los procesan y hablamos sobre la estructura y funcionamiento de los compiladores:

Obviando algunas precisiones, un compilador suele tener una estructura general como la siguiente:

 

Grosso modo, su funcionamiento es como sigue:             

 

Cada vez que el scanner (Analizador Léxico) es llamado, reanuda su lectura de caracteres del Código Fuente escrito en el Lenguaje1; se salta caracteres irrelevantes (como una secuencia de comentarios, blancos, y/o saltos de línea) y luego concatena los que sí son relevantes hasta completar una cadena que tenga significado por sí misma (por ejemplo “{“, “main” y “contador” en el lenguaje C); en seguida detecta si la cadena es una palabra reservada (como “main”), un símbolo (como “{“), un identificador (como “contador”) –en cuyo caso  lo busca en la Tabla de Identificadores y si no lo encuentra lo da de alta–, o un error léxico (en cuyo caso también emite el mensaje correspondiente); finalmente, regresa esta información a la subrutina que lo llamó,–usualmente el parser– conteniendo al menos 2 elementos: la cadena en sí misma (el “lexema”), y un código (el “token”) que representa el tipo genérico de la cadena (como “Identificador”, “número” o “paréntesis de cierre”).

 

El parser (Analizador Sintáctico) suele ser el componente central del procesamiento de un compilador. Manda llamar al scanner, el cual como dijimos regresa la cadena que acaba de completar y la información mencionada. Con esos datos, el parser busca seguir alguna de las reglas gramaticales del lenguaje; en caso de no encontrar alguna emite un mensaje de error sintáctico. En su procesamiento va utilizando y actualizando la Tabla de Identificadores (por ejemplo, escribiendo si el Identificador es el nombre de una subrutina o de una variable, así como su tipo), va construyendo el Árbol Sintáctico del programa en cuestión (ver figura abajo), y va ejecutando instrucciones que tiene “embebidas”… A) del Analizador Semántico, que entre otras cosas revisa cuestiones relacionadas con tipos de datos y paso de parámetros (para lo cual se apoya en la Tabla de Identificadores); B) del Mecanismo de Recuperación de Errores,  que al detectar un error emite el mensaje correspondiente y hace lo necesario para permitir que se pueda continuar con el análisis (como saltar secciones de código “problemáticas”);  y C) del Generador de Código (el cual también se apoya en esa Tabla) para construir el Código Objeto con instrucciones en el Lenguaje2 (aunque es usual generar primero código en un lenguaje intermedio, realizar un proceso de Optimización y luego generar el Código Objeto).

 

El árbol sintáctico para la cadena a2 b3 c3 d 2  del lenguaje L2, se muestra en la siguiente figura; en ella se se parte de S0 y se van generando ramificaciones sustituyendo no-Terminales mediante la aplicación de alguna regla de la gramática; las hojas del árbol acaban siendo Terminales o λ.

 

Lenguajes de Computación (LCs) y Lenguajes de Programación (LPs)

En SG#55, revisamos el concepto de “Computer Languages” como una generalización de los “Programming Languages”:

Todos estamos familiarizados con el concepto de Lenguajes de Programación (LPs) y existe bastante literatura sobre el tema. Sin embargo, si buscamos incrementar nuestra productividad deberíamos abrir nuestra panorámica y considerar no solo los LPs, sino lo que llamaremos aquí “Computer Languages” o “Lenguajes de Computación” (LCs), concepto que incluye los LPs, pero también los Lenguajes de Documentación (como LaTeX y HTML), Lenguajes de Arquitectura (como ABACUS y CBabel),  Lenguajes de Especificación (v.gr. de sanners/parsers como lex/YACC), Lenguajes de Documentación de Procesos (como XPDL y JPDL), y Lenguajes para la Prueba (como LoadRunner y Selenium), entre otros. Desarrollar lenguajes propietarios de propósito particular para estas áreas también puede incrementar significativamente nuestra productividad.

Los LCs (y los LPs en particular) se desarrollan a lo largo de un proceso de sistematización–formalización–automatización durante el cual se va conociendo mejor el área para la cual se diseña el lenguaje (el “Application Domain” o “Dominio de Aplicación”), detectando patrones útiles y repetidos en la construcción de programas.

Profundizamos en los Lenguajes de Programación (LPs):

Cuando los LPs son de propósito general (general purpose languages) tienen constructos que son comunes a muchos otros LPs, tales como mecanismos de secuenciación, alternación y repetición de instrucciones, definidos en el marco de lo que llamamos un Sistema de Control (Control System);  y mecanismos para construir, combinar, comparar, y descomponer tipos, definidos en el marco de un Sistema de Tipos (Type System). Cuando los LPs son de propósito particular (special purpose languages) tienen además una parte diseñada especialmente para abordar más efectivamente problemas del Dominio de Aplicación, como tipos de datos y estructuras de control ad hoc (v.gr. si el dominio fuera la Matemática, el LP podría tener construcciones y operaciones nativas sobre matrices, entre otras cosas).

El Sistema de Control

La estructura del Sistema de Control está fuertemente influenciada por el paradigma del LP (ver más adelante), pero podemos hablar en general de constructos (o “abstracciones”) como los descritos en la siguiente tabla.

 

 

El Sistema de Tipos

La estructura del Sistema de Tipos también está influenciada por el paradigma del LP, pero podemos igualmente hablar en general de constructos como los descritos en la siguiente tabla.

 

 

El diseño del Sistema de Tipos es una actividad en sí misma por su complejidad y relevancia (define elementos vitales de la semántica del lenguaje). Su definición incluye cuestiones muy importantes como las siguientes:

1. Chequeo de tipos: Distinguimos entre strongly-typed y weakly-typed languages, dependiendo respectivamente de la menor o mayor tolerancia a que a las variables de un programa no se les haya asociado explícitamente un tipo de dato. Si el chequeo de esta asociación se realiza en tiempo de compilación hablamos de statically-checked languages; si ocurre en tiempo de ejecución hablamos de dynamically-checked languages.
2. Equivalencia de tipos: Se definen criterios para determinar cuándo se considera que dos variables tienen el mismo tipo, aunque eventualmente hayan sido declaradas de manera distinta. Algunas alternativas son:

• Declaration Equivalence: Dos variables tienen tipos equivalentes cuando remiten a la misma declaración de tipo.

• Name Equivalence: Dos variables tienen tipos equivalentes si fueron declaradas usando el mismo nombre de tipo en el mismo ámbito (scope).

• Structural Equivalence: Dos variables tienen tipos equivalentes si fueron definidas partiendo de los mismos tipos básicos y utilizando los mismos constructores de tipos.

3. Conversión de tipos: Para combinar variables de varios tipos se aplican mecanismos como los siguientes:

• Conversión implícita (promotion), como cuando una variable entera es convertida automáticamente a real por aparecer en una expresión real.

• Conversión explícita (casting): la que realiza el programador ya sea mediante la utilización de funciones predefinidas, o utilizando facilidades del lenguaje para “asignar tipos”, como el conocido casting.

• Generalización del tipo de una variable a un tipo genérico, como el void del lenguaje C.

4. Inferencia de Tipos: Permite deducir el tipo adecuado de v.gr. una subexpresión dentro de una expresión; es particularmente importante en los weakly-typed languages. El conocido mecanismo de Unificación presente en ProLog es un interesante ejemplo de inferencia de tipos.

Enunciamos los siguientes Criterios de Clasificación de LPs y abundamos en los 2 últimos, mostrados en la figura de abajo.

Una manera de ganar perspectiva es mediante una clasificación, pero una taxonomía presupone criterios bajo los cuales clasificar. Para los LP podríamos tomar alguno(s) de los siguientes:

1. Su aspecto ante el programador, lo que permite v.gr. distinguir entre lenguajes visuales y textuales.
2. Su “composición estructural” (y la complejidad de procesar cada lenguaje), lo cual es el origen de jerarquías como la Jerarquía de Lenguajes de Chomsky.
3. El “marco conceptual” detrás de los programas que se escriben en un lenguaje particular, lo que facilita la clasificación en Paradigmas de LPs.
4. El “origen cronológico” en el que fueron creados, lo que da pie al concepto de Generaciones de LPs.

 

 



También hablamos de Criterios de Diseño para desarrollar LPs que pueden aplicarse también a LCs:

1. Simplicidad, que facilita su aprendizaje y uso.
2. Legibilidad, que permite a un novato entender programas rápidamente.
3. Expresividad, que permite expresar procesos y estructuras complejos con poco código.
4. Uniformidad, que brinda consistencia en apariencia y comportamiento de constructos.
5. Generalidad, que permite combinar constructos estrechamente relacionados en uno más general.
6. Ortogonalidad, que permite combinar constructos cuando haga sentido, pero lo impide cuando causarían comportamientos inadecuados.
7. Extensibilidad, que permite añadir nuevos constructos.

---

 

Ejemplo Integrador

Ahora abordaremos nuestro ejemplo, en el que incorporaremos mucho de lo que hemos visto hasta ahora en nuestra columna. El ejemplo tiene que ver con Métodos Formales, Lenguajes y Compiladores.  

Métodos Formales

En términos generales, los Métodos Formales (MF) son una tecnología mediante la cual podemos:

1. Escribir una especificación del sistema a desarrollar utilizando un lenguaje formal L1 (usualmente un lenguaje de especificación altamente expresivo), que luego es verificada con intervención humana y procesada mediante un compilador C1 para así generar el código en otro lenguaje formal L2 que representa un diseño de alto nivel.
2. Tomar este diseño (quizás escrito en un Lenguaje de Arquitectura), verificarlo con intervención humana y procesarlo mediante un compilador C2 que genera el código en otro lenguaje formal L3 que representa un programa susceptible de ser optimizado.
3. Este programa (escrito quizás en un lenguaje de programación procedural de alto nivel) se procesa mediante un compilador C3 (que eventualmente optimiza el programa) para obtener finalmente el código objeto (quizás en lenguaje máquina).

Las verificaciones mencionadas suelen ser demostraciones matemáticas de que el código correspondiente muestra ciertas propiedades.

En realidad, podríamos pensar que en el desarrollo de software siempre utilizamos algún tipo de MF, pues finalmente se escribe el sistema en algún lenguaje Lx que es procesado por un compilador Cx, el cual usualmente genera código ejecutable. Sin embargo, esta transformación suele realizarse solamente para el tercer numeral de los arriba descritos (la generación del sistema ejecutable a partir del programa escrito en un lenguaje de programación), no para todo el ciclo de desarrollo Requerimientos-Diseño-Programación, como buscan hacerlo los MFs.

Por otro lado, y como ya hemos comentado, los analizadores sintácticos (o “parsers”) suelen definirse mediante una gramática. Para ello se utiliza alguna nomenclatura especializada como BNF o Grafos de Sintaxis; aquí utilizaremos esta última como lenguaje de diseño de lenguajes.

Grafos de Sintaxis

Los Grafos de Sintaxis (GSs) tienen una definición formal inductiva que suele resultar muy intuitiva:

Los siguientes son GSs básicos:

1. (el grafo nulo)
2.  donde t es un Símbolo Terminal
3.   donde N es un Símbolo no-Terminal

 

 Si      son GSs, entonces también lo son los siguientes:

 

la secuenciación de GSs

   

 

la alternación de GSs

   

la repetición de GSs

   

 

Además, consideraremos que a un GS   se le puede asignar un nombre con el                                             que luego puede ser referenciado:    .

 

Como ya hemos dicho, con los GSs pueden especificarse los Lenguajes Libres de Contexto. Ahora bien, dentro de esa clase hay un tipo de lenguajes (los descendentes predictivos) para los cuales es relativamente fácil escribir parsers que los procesen, pero las gramáticas que los definen deben presentar ciertas características, en particular las siguientes (que por razones de espacio, no describiremos aquí de manera formal):

1. La definición de la gramática no puede tener recursión izquierda (el procesamiento se ciclaría indefinidamente), sea directa o indirecta;
2. En una alternación de grafos, no puede ocurrir que un par de ellos comience con la misma cadena (se requeriría backtracking).

Un pequeño Método Formal

Las reglas para construir un parser descendente predictivo son relativamente sencillas y pueden ser automatizadas como bosquejamos a continuación, utilizando la rutina recursiva C() que recibe como parámetro un GS y genera su código asociado (aquí en Pseudocódigo).

En el código de estas reglas, err_msg() es una rutina que solo imprime un mensaje de error (sintáctico) y eventualmente hace abortar el proceso de análisis sintáctico (pero es posible sofisticarla sistemáticamente para que sea el elemento central de un mecanismo de Recuperación de Errores, de manera que detecte y anuncie errores sin interrumpir ese análisis).

Por otro lado, start() es una rutina recursiva que, dado un GS, regresa el conjunto de símbolos terminales con los que puede iniciar ese GS. Defiendo esa rutina de manera semi-formal (por cuestiones de espacio), y obviando algunas precisiones (como si un GS es nulo), tenemos que:

• El start de un GS que es un símbolo terminal es el conjunto con ese no-terminal como único elemento.
• El start de un GS que es un símbolo no-terminal es el start del GS que lo define.
• El start de un GS que es una secuenciación de GSs es el start del primero de esos GSs.
• El start de un GS que es una alternación de GSs es la unión de los start de cada uno de esos GSs.
• El start de un GS que es una repetición de GSs es el start del primero de esos GSs.

 

Las reglas para la generación de parsers a partir de GSs son las siguientes:

 

Con los elementos anteriores podríamos tener un pequeño MF para los últimos 2 numerales listados en la definición de MF:

1. Escribiríamos el diseño del lenguaje utilizando el  lenguaje formal de los GS, el cual sería verificado por un compilador de GS para detectar recursión izquierda y/o alternaciones de GS no permitidas (además de otras cosas como no-Terminales indefinidos o caracteres inválidos); en caso de haberlas, el diseño sería corregido con intervención humana. Una vez corregido y verificado nuevamente, el compilador de GS podría generar el parser en pseudocódigo como lenguaje intermedio.
2. Este parser “correcto”  a su vez sería procesado (y optimizado, fase que no abordaremos aquí) mediante un compilador de pseudocódigo que generaría el programa en algún lenguaje de alto nivel, a elección del usuario (v.gr. Java, ADA o LISP), para luego ser procesado por el compilador correspondiente que generaría el código ejecutable.



Ejemplo

Las expresiones en los lenguajes de computación son muy importantes. En lenguajes de programación de alto nivel procedurales aparecen en asignaciones, en condiciones de instrucciones como if y while, y en el paso de parámetros; en LISP –el lenguaje funcional por antonomasia– tanto datos como programas son un tipo especial expresiones.

Apliquemos nuestro MF para desarrollar un parser que procese expresiones algebraicas simples como   a+3*2,  (a+b)*2  ó  ((a+b) /3*(b-c))  , en las que la precedencia de los operadores es la usual: + y - tienen igual precedencia, la cual es inferior a la de * y / , que también tienen la misma precedencia.

Uno podría iniciar definiendo la siguiente gramática:

Sin embargo, esa gramática presenta inconvenientes importantes: no garantiza que para cada “(“ haya un “)”, y todos los operadores tienen la misma precedencia. Desgraciadamente, nuestro pequeño MF no podría ayudarnos con estos problemas.

 

Buscando resolver los problemas anteriores, y generalizando para que en lugar del “Elm" de la gramática anterior, tengamos Identificadores y Números podríamos proponer esta otra gramática:

 

Esta gramática también presenta inconvenientes, pero esta vez nuestro MF sí puede ayudarnos: nos diría que el no-terminal “Opr" no está definido (el grafo que le correspondía está tiene el nombre “Oprr”), y –más grave aún para efectos del funcionamiento del parser– que existe recursión izquierda (“Xpn").

Podríamos entonces proponer la siguiente gramática:

Pero el MF nos diría que dos de las alternativas en el GS “Xpn” comienzan con la misma cadena (“Opnd”).

 

Por ello podríamos proponer la siguiente gramática, que es una buena alternativa:

El MF no se quejaría, pues en particular no hay recursión izquierda, no existen dos subgrafos que comiencen con la misma cadena, y no hay no-terminales indefinidos. Y, dado que los operadores aparecen en una jerarquía de grafos, se tienen las precedencias deseadas. Además, los operadores presentan la precedencia deseada.

 

Con esta gramática que tiene las características que requiere el MF, éste podría proceder a generar el pseudocódigo del parser aplicando la rutina  C():

Para “Xpn” el código se iría generando sistemáticamente como se muestra a continuación (el resultado de los start se muestran explícitamente):

 

 

 

Para “Sum” el código que finalmente se generaría sería el siguiente (podrán apreciar varias oportunidades de optimización):

 



Para “Fact” el código que finalmente se generaría sería el siguiente (también con varias oportunidades de optimización):

 

Por definición, el programa principal del parser llamaría a la rutina Xpn() (dado que es el símbolo no-terminal que actúa como símbolo inicial de la gramática), la cual llamaría a Sum() cuando fuera necesario y ésta de igual manera a Fact(). Ustedes podrán constatar que ese programa procesa el tipo de expresiones que definimos.

Conclusiones

Utilizando este MF para desarrollar parsers podemos destinar más tiempo al diseño de una gramática que procese el lenguaje que nos interesa, que a la escritura de un programa que lo haga con lo cual podemos desarrollar un lenguaje de mejor calidad; y al no ser necesario atender tantos detalles, habría menos probabilidad de cometer errores (el parser también podría tener mejor calidad), y terminaríamos más rápidamente (la productividad se incrementaría). Además, los GSs son más expresivos, simples y legibles que el pseudocódigo, con lo cual ganaríamos una mejor “mantenibilidad”.

Lo anterior es posible porque se introduce un lenguaje formal de mayor nivel de abstracción (GS), que nos permite no tener que atender detalles poco importantes (como instrucciones en y con if’s, while’s, switch’s, conjuntos, recursiones, etc.) para desarrollar software de una manera más abstracta y sistemática.

Si medimos el “tamaño” de del input (cantidad de GSs) y del output (cantidad de líneas de pseudocódigo) de la subrutina  C(),  podríamos ver que en general, cuando crece la complejidad del input, la complejidad del output puede crecer en un orden de magnitud (10x). Esto es: cuando usamos el MF para desarrollar el parser asociado a una gramática definida con GSs que contienen muchas alternaciones y repeticiones de GSs, la proporción entre el input (GSs) y el output (líneas de pseudocódigo) puede exceder las 10 veces (1,000%).

Y esa es precisamente la idea detrás del desarrollo de lenguajes propietarios: introducir un lenguaje formal que nos permita subir el nivel de abstracción de lo que hacemos para centrarnos más en actividades como el diseño, y dejar que el compilador del lenguaje propietario genere los detalles (como ocurrió con los lenguajes de alto nivel, que generaban el código en lenguaje máquina asociado a constructos como if’s, while’s).

Hacer esto es particularmente relevante en un mundo en el que actualmente en muchas grandes transnacionales tecnológicas, “Robots”  realizan funciones como las anteriores y generan la misma cantidad de código (en lenguajes de alto nivel) que el que generan sus ingenieros.