Lenguaje de programación basado en pila
Un lenguaje de programación basado en pila es aquél que se basa en el modelo de una máquina de pila para pasar parámetros. Varios lenguajes de programación se ajustan a esta descripción, siendo más conocidos Forth y PostScript, además de varios lenguajes ensambladores (pero a un nivel mucho más bajo).
Un lenguaje orientado a pila se trabaja mediante operaciones sobre una o varias pilas, que pueden servir para varios propósitos. Debido a esto, las estructuras de programación de otros lenguajes han de ser modificadas para poder usarlas en un lenguaje orientado a pila. Además de esto, algunos de estos lenguajes operan en notación polaca inversa o postfija (RPN); es decir, los argumentos o parámetros de algunas órdenes se indican antes de la propia orden. Por ejemplo, en RPN, diríamos "2, 3, multiplicar" en lugar de "multiplicar, 2, 3" (notación prefija o Polaca) o "2 multiplicar 3" (notación infija).
Operación sobre la pila
[editar]
Asumamos que tenemos un lenguaje postfijo basado en pila. PostScript es uno de dichos lenguajes. Para comprender cómo "trabaja" un lenguaje orientado a pila al calcular una expresión tal como "2 3 multiplicar", podemos usar un sencillo experimento mental.
Digamos que estamos al principio de una cinta transportadora y alguien ha puesto en ella "2", "3" y "multiplicar". El problema es que sólo podemos ver la primera cosa que viene por la cinta, el 2, y nada más. Sólo se nos permite: realizar un cálculo, tomar lo que vemos en la cinta (la primero que haya) y poner algo de vuelta en la cinta justo enfrente nuestra. ¿Podemos realizar el cálculo?
Sí podemos. Tomamos el 2 de la cinta, luego el 3 y luego la orden para multiplicar, momento en que multiplicamos lo que tenemos, 2 y 3, y luego ponemos el resultado (6) de vuelta en la cinta.
Por supuesto esto es un cálculo muy sencillo. ¿Qué pasaría si quisiéramos calcular algo como (2 + 3) × 11 + 1? Si lo escribimos primero en forma postfija, o sea,
- 2 3 sumar 11 multiplicar 1 sumar
podemos realizar el cálculo exactamente de la misma manera y conseguir el mismo resultado. Tras cada operación, ponemos el resultado de vuelta en la cienta (la pila), y continuamos como antes. La pila se transformaría entonces como sigue
- 5 11 multiplicar 1 sumar
- 55 1 sumar
- 56
que es el resultado.
De esto podemos concluir lo siguiente: un lenguaje de programación basado en pila sólo tiene una manera de gestionar datos, tomando una cosa por vez de la cima de la pila, operación conocida como pop, y poniendo datos de vuelta en la cima de la pila, que se conoce como push. Cualquier expresión que se pueda escribir "de formaq convencional" o en cualquier otro lenguaje de programación, se puede escribir de forma postfija (o prefija), susceptible de ser interpretada por un lenguaje orientado a pila.
Manipulación de la pila
[editar]Dado que la pila es el medio clave para la manipulación de datos en los lenguajes orientados a pila, éstos proporcionan a menudo algún tipo de operadores para manipulación de la pila. Por lo común se proporcionan dup, para duplicar el elemento en la cima; exch (o swap), para intercambiar los dos elementos de la cima (el primero se convierte en segundo y viceversa); roll, para permutar de forma cíclica elementos de la pila o de parte de la pila; pop, para descargar los elementos de la cima (push viene implícita) y otras. Son cruciales al estudiar procedimientos.
Variables y diccionarios
[editar]Hemos examinado la manera de evaluar diferentes expresiones. La implementación de variables es importante para cualquier lenguaje de programación, pero es un asunto de interés especial en los lenguajes orientados a pila, ya que sólo tenemos una manera de interactuar con los datos.
La manera de implementar las variables en lenguajes orientados a pila tales como PostScript suelen implicar una pila aparte, especializada, que mantiene diccionarios, que mantienen pares clave-valor. Para crear una variable, creamos una clave (el nombre de la variable), a la que asociamos un valor. En PostScript, un objeto "nombre de dato" se prefija con una "/", así que "/x" es un objeto nombre de dato que podemos asociar, por ejemplo, al número "42". La orden "definir" es def, así
/x 42 def
asocia el nombre "x" con el número 42 en el diccionario que está en la cima de la pila. Observe que hay diferencia entre "/x" y "x": el primero es un objeto de dato que representa un nombre, "x" representa aquello que está definido bajo "/x".
Procedimientos
[editar]En un lenguaje basado en pila un procedimiento se trata como un objeto de datos de pleno derecho. En PostScript, los procedimientos se señalan entre { y }.
Por ejemplo, en sintaxis de PostScript,
{ dup mul }
representa un procedimiento anónimo que duplica lo que hay en la cima de la pila y luego multiplica el resultado (un procedimiento que eleva al cuadrado).
Dado que los procedimientos se tratan como simplos objetos de datos, podemos definir nombres con procedimientos, y cuando los recuperamos, se ejecutan directamente.
Los diccionarios proporcionan medios para controlar el ámbito, así como formas para almacenar definiciones.
Dado que los objetos de datos se almacenan en el diccionario que está en la cima, aparece de forma natural una capacidad inesperada: cuando buscamos una definición en un diccionario, se comprueba primero el que está en la cima, luego el siguiente, y así seguimos. Si definimos un procedimiento que tiene el mismo nombre que otro ya definido en un diccionario diferente, se invoca al "local".
Anatomía de algunos procedimientos típicos
[editar]A menudo, los procedimientos toman argumentos. El procedimiento trata con ellos de una manera muy específica, diferente a la de otros lenguajes de programación.
Examinemos el programa para números de Fibonacci en PostScript:
/fib
{
dup dup 1 eq exch 0 eq or not
{
dup 1 sub fib
exch 2 sub fib
add
} if
} def
Usamos una definición recursiva, y también lo hace la pila. La función de números de Fibonacci toma un argumento. Primero probamos si es 1 o 0.
Descompongamos cada uno de los pasos clave del programa, reflejados en la pila. Asumamos que calculamos F(4).
pila: 4
dup
pila: 4 4
dup
pila: 4 4 4
1 eq
pila: false 4 4
exch
pila: 4 false 4
0 eq
pila: false false 4
or
pila: false 4
not
pila: true 4
Dado que la expresión se evalúa a verdadero (true), se evalúa el procedimiento interior.
pila: 4
dup
pila: 4 4
1 sub
pila: 3 4
fib
- (aquí entramos en recursividad)
pila: F(3) 4
exch
pila: 4 F(3)
2 sub
pila: 2 F(3)
fib
- (aquí entramos en recursividad)
pila: F(2) F(3)
add
pila: F(2)+F(3)
que es el resultado que queríamos.
Este procedimiento no usa variables con nombre, sino sólo la pila. Podemos crear variables con nombre usando la estructura
/a exch def
Por ejemplo,
{/n exch def n n mul}
es un procedimiento para elevar al cuadrado con una variable llamada n. Asumimos
/sq {/n exch def n n mul} def
y que se invoca
3 sq
Analicemos este procedimiento.
pila: 3 /n
exch
pila: /n 3
def
pila: vacía (realizada la definición)
n
pila: 3
n
pila: 3 3
mul
pila: 9
que es el resultado que queríamos.
Control y flujo
[editar]Dado que tenemos procedimientos anónimos, puede aparecer el contro de flujo de manera natural. Necesitamos tres datos para una sentencia if-then-else: una condición, un procedimiento a realizar si es cierta, y uno para realizar si es falsa. En PostScript por ejemplo,
2 3 gt { (2 es mayor que tres) = } { (2 no es mayor que tres) = } ifelse
ejecuta el equivalente aproximado en C:
if(2 >= 3) { printf("2 es mayor que tres\n"); } else { printf("2 no es mayor que tres"); }
Los bucles y otras estructuras son similares.
Análisis del modelo de lenguaje
[editar]El modelo sencillo proporcionado en un lenguaje de programación orientado a pila permite que las expresiones y programas sean interpretados de forma sencilla y que los evalúen teóricamente mucho más rápido, ya que no hay necesidad de hacer un análisis sintáctico, sino sólo análisis léxico. La manera en que se escriben los programas se presta a ser interpretada por máquinas, razón por la que PostScript se ajusta al uso en impresoras. Sin embargo, la forma ligeramente artificial de escribir programas en PostScript puede resultar una barreraq inicial para comprender el lenguaje, o cualquier otro orientado a pila.
Mientras que la capacidad de oscurecimiento (shadowing) mediante reemplazo y otras definiciones puede dificultar la tarea de depuración (y el uso irresponsable de esta característica puede dar lugar a comportamientos impredecibles), también puede hacer mucho más sencillo alcanzar cierta funcionalidad. Por ejemplo, en PostScript se puede reemplazar el operador showpage con uno personalizado que aplique un cierto estilo a la página, en lugar de tener que definir un operador nuevo o repetir código para generar el estilo.
Véase también
[editar]- PostScript
- Lenguaje de programación Forth
- Lenguaje Lapis (un lenguaje orientado a objetos basado en pila)
- Máquina virtual Java
- Pila (estructura de datos)
- Notación polaca inversa
- Lenguaje de programación RPL