La programación orientada a pilas es un paradigma de programación que se basa en una pila (o varias pilas) para manipular datos y/o pasar parámetros. Varios lenguajes de programación se ajustan a esta descripción, en particular Forth , RPL y PostScript . 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 pilas. [1] La mayoría de los lenguajes orientados a pilas operan en notación postfija o polaca inversa . Cualquier argumento o parámetro para un comando se indica antes de ese comando. Por ejemplo, la notación postfija se escribiría 2, 3, multiplyen lugar de multiply, 2, 3( prefijo o notación polaca ), o 2 multiply 3( infijo notación ). Los lenguajes de programación Forth , Factor , RPL , PostScript , lenguaje de diseño de estilo BibTeX [2] y muchos lenguajes ensambladores se ajustan a este paradigma.
Los algoritmos basados en pilas manipulan los datos extrayendo datos de la pila y empujándolos hacia ella. Los operadores de manipulación de pila controlan cómo la pila manipula los datos . Para enfatizar el efecto de una declaración, a menudo 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. PostScript utiliza pilas separadas para propósitos adicionales, incluidas variables, diccionarios, procedimientos, algunos procedimientos típicos y declaraciones de flujo de control. El análisis del modelo de lenguaje permite interpretar expresiones y programas de manera sencilla.
PostScript es un ejemplo de lenguaje basado en pila de sufijos. Un ejemplo de expresión en este lenguaje es 2 3 mul('mul' es el comando para la operación de multiplicación). Para calcular la expresión es necesario 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 2, 3, y mulse colocan en secuencia. La placa al final de la cinta transportadora ( 2) se puede tomar, sin embargo, no se puede acceder a otras placas hasta que se retire la placa del final. Las placas 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 o la parte inferior. Se pueden suministrar placas en blanco (y un marcador) y las placas se pueden descartar de forma permanente.
Tome la placa 2y colóquela en la pila, luego tome la placa 3y colóquela en la pila. A continuación, tome la mulplaca. Esta es una instrucción para realizar. Luego, tome las dos placas superiores de la pila, multiplique sus etiquetas ( 2y 3) y escriba el resultado ( 6) en una placa nueva. Descarte las dos placas viejas ( 2y 3) y la placa mul, y coloque la nueva placa en la pila. Como no quedan más placas en la cinta transportadora, el resultado del cálculo ( 6) se muestra en la placa en la parte superior de la pila.
Este es un cálculo muy simple. ¿Qué sucede si se necesita un cálculo más complejo, como (2 + 3) × 11 + 1? Si primero se escribe en forma de sufijo, es decir, 2 3 add 11 mul 1 add, el cálculo se puede realizar exactamente de la misma manera y obtener 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 de la cinta transportadora) 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.
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 volviendo a colocar los datos en la parte superior de la pila, denominado push ing. Cualquier expresión que se pueda escribir de forma convencional o en otro lenguaje de programación se puede escribir en forma de posfijo (o prefijo) y, por lo 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 suelen proporcionar algún tipo de operadores de manipulación de la pila. Los que se proporcionan habitualmente son dup, para duplicar el elemento que se encuentra en la parte superior de la pila, exch(o swap), para intercambiar elementos que se encuentran en la parte superior de la pila (el primero se convierte en segundo y el segundo en primero), roll, para permutar cíclicamente elementos en la pila o en parte de la pila, pop(o drop), para descartar el elemento que se encuentra en la parte superior de la pila (la inserción está implícita), y otros. Estos se vuelven clave en el estudio de los procedimientos.
Para ayudar a comprender el efecto de la declaración, se utiliza un comentario breve 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 utiliza comúnmente en el lenguaje Forth, donde los comentarios se incluyen entre paréntesis.
(antes - después)Por ejemplo, se describen los operadores básicos de la pila Forth:
duplicar (a--aa) soltar (a--) intercambiar (ab--ba) sobre (ab--aba) rotar (abc--bca) La fibfunción se describe a continuación:
mentira ( n -- n' ) Es equivalente a las condiciones previas y posteriores en la lógica de Hoare . Ambos comentarios también pueden mencionarse como afirmaciones , aunque no necesariamente en el contexto de lenguajes basados en pila.
PostScript y algunos otros lenguajes de pila tienen otras pilas separadas para otros propósitos.
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 importancia, ya que solo hay una forma de interactuar con los datos.
La forma en que se implementan las variables en lenguajes orientados a la pila, como PostScript, generalmente implica una pila especializada separada que contiene diccionarios de pares clave-valor . Para crear una variable, primero se debe crear una clave (el nombre de la variable), con la que luego se asocia un valor. En PostScript, un objeto de datos de nombre tiene como prefijo /, por lo que /xes un objeto de datos de nombre que se puede asociar, por ejemplo, con el número 42. El definecomando es def, por lo que
/x 42 def
se asocia con el nombre xy el número 42en el diccionario que se encuentra en la parte superior 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.
En un lenguaje de programación basado en pila, un procedimiento se considera 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 cuadratura.
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 consulta 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 aceptar argumentos, que son gestionados por el procedimiento de una forma muy específica, diferente a la de otros lenguajes de programación.
Para examinar un programa de números de Fibonacci en PostScript:
/fib { dup dup 1 eq intercambio 0 eq o no { dup 1 sub fib intercambio 2 sub fib agregar } si } def Se utiliza una definición recursiva en la pila. La función de 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 Duplicado pila: 4 4 Duplicado pila: 4 4 4 1 ecualizador pila: 4 4 falso intercambio pila: 4 falsos 4 0 equivalente pila: 4 falso falso o pila: 4 falsos no pila: 4 verdaderos
Dado que la expresión se evalúa como verdadera, se evalúa el procedimiento interno.
pila: 4 Duplicado pila: 4 4 1 sub pila: 4 3 mentira
pila: 4 F(3) intercambio pila: F(3) 4 2 sub pila: F(3) 2 mentira
pila: F(3) F(2) agregar pila: F(3)+F(2)
Cuál es el resultado esperado.
Este procedimiento no utiliza variables con nombre, sino ú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 , el procedimiento se analiza de la siguiente manera:3 sqsq
pila: 3 /n intercambio pila: /n 3 definición pila: vacía (se ha definido) norte pila: 3 norte pila: 3 3 mul pila: 9
Cuál es el resultado esperado.
Como existen 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 que se debe realizar si la condición es verdadera y otro que se debe 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) = } ifelse 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 que proporciona un lenguaje orientado a pila permite interpretar expresiones y programas de forma sencilla y evaluarlos teóricamente de forma mucho más rápida, ya que no es necesario realizar un análisis sintáctico sino un análisis léxico . La forma en que se escriben dichos programas facilita su interpretación por parte de las máquinas, por lo que PostScript se adapta bien a las impresoras para su uso. Sin embargo, la forma ligeramente artificial de escribir programas PostScript puede formar una barrera inicial para la comprensión de lenguajes orientados a pila como PostScript.
Si bien la capacidad de aplicar sombras anulando definiciones incorporadas y otras puede dificultar la depuración de programas y el uso irresponsable de esta función puede causar un comportamiento impredecible, puede simplificar en gran medida algunas funciones. Por ejemplo, en el uso de PostScript, el show pageoperador se puede anular con uno personalizado que aplique un estilo determinado a la página, en lugar de tener que definir un operador personalizado o repetir el código para generar el estilo.