La programación orientada a pila es un paradigma de programación que se basa en un modelo de máquina de pila para pasar parámetros . Los lenguajes de programación orientados a pilas operan en una o más pilas , cada una de las cuales puede tener un propósito diferente. Las construcciones de programación en otros lenguajes de programación deben modificarse para su uso en un sistema orientado a pila. [1] La mayoría de los lenguajes orientados a pilas operan en notación postfija o polaca inversa . Todos los argumentos o parámetros de un comando se indican antes de ese comando. Por ejemplo, la notación postfija se escribiría 2, 3, multiplyen lugar de multiply, 2, 3( notación prefija o polaca ) o ( notación infija ). Los lenguajes de programación Forth , Factor , RPL , PostScript , lenguaje de diseño estilo BibTeX [2] y muchos lenguajes ensambladores se ajustan a este paradigma.2 multiply 3
Los algoritmos basados en pilas consideran los datos, utilizando un dato de la parte superior de la pila y devolviendo datos encima de la pila. La necesidad de operadores de manipulación de la pila permite que la pila manipule los datos . Para enfatizar el efecto de una declaración, se utiliza un comentario que muestra la parte superior de la pila antes y después de la declaración. Esto se conoce como diagrama de efecto de pila. Las pilas PostScript consideran pilas separadas para fines adicionales. Esto considera variables, diccionarios, procedimientos, anatomía de algunos procedimientos típicos, control y flujo. El análisis del modelo de lenguaje permite interpretar expresiones y programas de forma sencilla y teórica.
PostScript es un ejemplo de un lenguaje basado en pila Postfix. Un ejemplo de expresión en este lenguaje es 2 3 mul(siendo 'mul' el comando para la operación de multiplicación). Calcular la expresión implica comprender cómo funciona la orientación de la pila.
La orientación de la pila se puede presentar como la siguiente analogía de la cinta transportadora. al final de una cinta transportadora (la entrada ), las placas marcadas con 2, 3y mulse colocan en secuencia. 2Se puede tomar la placa al final del transportador ( ), sin embargo, no se puede acceder a otras placas hasta que se retire la placa al final. Los platos solo se pueden almacenar en una pila y solo se pueden agregar o quitar desde la parte superior de la pila, no desde el medio ni desde abajo. Se pueden suministrar placas en blanco (y un marcador) y las placas se pueden desechar permanentemente.
Tome el plato 2y colóquelo en la pila, luego tome el plato 3y colóquelo en la pila. A continuación, toma el mulplato. Esta es una instrucción para realizar. Luego, toma los dos platos superiores de la pila, multiplica sus etiquetas ( 2y 3) y escribe el resultado ( 6) en un plato nuevo. Deseche los dos platos viejos ( 2y 3) y el plato mul, y coloque el plato nuevo en la pila. Como no quedan más placas en el transportador, el resultado del cálculo ( 6) se muestra en la placa encima de la pila.
Este es un cálculo muy simple. ¿Qué pasa si se necesita un cálculo más complejo, como por ejemplo (2 + 3) × 11 + 1? Si se escribe primero en forma de sufijo, es decir, 2 3 add 11 mul 1 addel cálculo se puede realizar exactamente de la misma manera y lograr el resultado correcto. Los pasos del cálculo se muestran en la siguiente tabla. Cada columna muestra un elemento de entrada (la placa al final del transportador) y el contenido de la pila después de procesar esa entrada.
Después de procesar toda la entrada, la pila contiene 56, que es la respuesta.
A partir de esto, se puede concluir lo siguiente: un lenguaje de programación basado en pila tiene solo una forma de manejar datos: tomando un dato de la parte superior de la pila, denominado pop ping, y colocándolo nuevamente encima de la pila, denominado push ing. Cualquier expresión que pueda escribirse convencionalmente , o en otro lenguaje de programación, puede escribirse en forma de sufijo (o prefijo) y, por tanto, ser susceptible de ser interpretada por un lenguaje orientado a pila.
Dado que la pila es el medio clave para manipular datos en un lenguaje orientado a la pila, dichos lenguajes a menudo proporcionan algún tipo de operadores de manipulación de la pila. Comúnmente se proporcionan duppara duplicar el elemento en la parte superior de la pila, exch(o swap), para intercambiar elementos en la parte superior de la pila (el primero se convierte en el segundo y el segundo en el primero), rollpara permutar cíclicamente elementos en la pila o en parte de la pila, pop( o drop), para descartar el elemento encima de la pila (push está implícito), y otros. Estos se vuelven clave en el estudio de los procedimientos.
Como ayuda para comprender el efecto de una declaración, se utiliza un breve comentario que muestra la parte superior de la pila antes y después de la declaración. La parte superior de la pila está más a la derecha si hay varios elementos. Esta notación se usa comúnmente en el idioma Forth, donde los comentarios están entre paréntesis.
( antes después )Por ejemplo, se describen los operadores básicos de la pila Forth:
dup (a - aa) soltar (a -) intercambiar (ab - ba) sobre (ab - aba) rot (abc - bca) Y la fibfunción a continuación se describe:
mentira (n - n') Es equivalente a las condiciones previas y posteriores en la lógica de Hoare . También se puede hacer referencia a ambos comentarios como afirmaciones , aunque no necesariamente en el contexto de los lenguajes basados en Stack.
PostScript y algunos otros lenguajes de pila tienen otras pilas separadas para otros fines.
Ya se ha analizado la evaluación de diferentes expresiones. La implementación de variables es importante para cualquier lenguaje de programación, pero para los lenguajes orientados a pilas es de especial preocupación, ya que solo hay una forma de interactuar con los datos.
La forma en que se implementan las variables en lenguajes orientados a pilas, como PostScript, generalmente implica una pila separada y especializada que contiene diccionarios de pares clave-valor . Para crear una variable, primero se debe crear una clave (el nombre de la variable), a la que luego se asocia un valor. En PostScript, un objeto de datos de nombre tiene el prefijo a /, al igual /xque un objeto de datos de nombre que puede asociarse, por ejemplo, con el número 42. El definecomando es def, entonces
/x 42 def
asocia con el nombre xcon el número 42en el diccionario encima de la pila. Existe una diferencia entre /xy x: el primero es un objeto de datos que representa un nombre y xrepresenta lo que se define en /x.
Un procedimiento en un lenguaje de programación basado en pila se trata como un objeto de datos por derecho propio. En PostScript, los procedimientos se indican entre {y }.
Por ejemplo, en la sintaxis PostScript,
{ dup mul }
representa un procedimiento anónimo para duplicar lo que está en la parte superior de la pila y luego multiplicar el resultado: un procedimiento de elevación al cuadrado.
Dado que los procedimientos se tratan como objetos de datos simples, se pueden definir nombres con procedimientos. Cuando se recuperan, se ejecutan directamente.
Los diccionarios proporcionan un medio para controlar el alcance, así como para almacenar definiciones.
Dado que los objetos de datos se almacenan en el diccionario superior, surge naturalmente una capacidad inesperada: cuando se busca una definición en un diccionario, se comprueba el diccionario superior, luego el siguiente, y así sucesivamente. Si se define un procedimiento que tiene el mismo nombre que otro ya definido en un diccionario diferente, se llamará al local.
Los procedimientos suelen requerir argumentos. Son manejados por el procedimiento de una forma muy específica, diferente a la de otros lenguajes de programación.
Para examinar un programa numérico de Fibonacci en PostScript:
/fib { dup dup 1 eq exch 0 eq o no { dup 1 sub fib exch 2 sub fib agregar } si } def Se utiliza una definición recursiva en la pila. La función del número de Fibonacci toma un argumento. Primero, se prueba si es 1 o 0.
Descomponiendo cada uno de los pasos clave del programa, reflejando la pila, asumiendo el cálculo de fib(4) :
pila: 4 duplicar pila: 4 4 duplicar pila: 4 4 4 1 equivalente pila: 4 4 falso intercambio pila: 4 falso 4 0 equivalentes pila: 4 falso falso o pila: 4 falsos no pila: 4 verdadero
Dado que la expresión se evalúa como verdadera, se evalúa el procedimiento interno.
pila: 4 duplicar pila: 4 4 1 sub pila: 4 3 mentira
pila: 4 F(3) intercambio pila: F(3) 4 2 subs pila: F(3) 2 mentira
pila: F(3) F(2) agregar pila: F(3)+F(2)
cual es el resultado esperado.
Este procedimiento no utiliza variables con nombre, únicamente la pila. Las variables con nombre se pueden crear utilizando la /a exch defconstrucción. Por ejemplo,{/n exch def n n mul}
es un procedimiento de elevación al cuadrado con una variable nombrada n. Suponiendo que se llama /sq {/n exch def n n mul} defa y 3 sq, el procedimiento sqse analiza de la siguiente manera:
pila: 3 /n intercambio pila: /n 3 definición pila: vacía (ha sido definida) norte pila: 3 norte pila: 3 3 mul pila: 9
cual es el resultado esperado.
Al existir procedimientos anónimos, el control de flujo puede surgir de forma natural. Se requieren tres datos para una declaración if-then-else : una condición, un procedimiento a realizar si la condición es verdadera y uno a realizar si la condición es falsa. En PostScript, por ejemplo,
2 3 gt { (2 es mayor que tres) = } { (2 no es mayor que tres) = } si no realiza el equivalente cercano en C:
if ( 2 > 3 ) { printf ( "2 es mayor que tres \n " ); } else { printf ( "2 no es mayor que tres \n " ); } Los bucles y otras construcciones son similares.
El modelo simple proporcionado en un lenguaje orientado a pila permite interpretar expresiones y programas de manera simple y evaluar teóricamente mucho más rápido, ya que no es necesario realizar ningún análisis de sintaxis , solo análisis léxico . La forma en que se escriben estos programas facilita su interpretación por las máquinas, razón por la cual PostScript se adapta bien a las impresoras para su uso. Sin embargo, la forma ligeramente artificial de escribir programas PostScript puede constituir una barrera inicial para comprender los lenguajes orientados a pilas como PostScript.
Si bien la capacidad de sombra anulando definiciones incorporadas y de otro tipo puede hacer que los programas sean difíciles de depurar, y el uso irresponsable de esta característica puede causar un comportamiento impredecible, puede simplificar enormemente algunas funciones. Por ejemplo, en el uso de PostScript, el showpageoperador se puede anular con uno personalizado que aplique un determinado estilo a la página, en lugar de tener que definir un operador personalizado o repetir el código para generar el estilo.