Programación orientada a pilas

La programación orientada a pilas es un paradigma de programación que se basa en una o más pilas para manipular datos y/o pasar parámetros. 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 : los argumentos o parámetros de un comando se enumeran antes de dicho comando. Por ejemplo, la notación postfija se escribiría en lugar de ( notación prefija o polaca ) o ( notación infija ). Los lenguajes de programación Forth , Factor , RPL , PostScript , el lenguaje de diseño de estilo BibTeX ^[²^] y muchos lenguajes ensamblador se ajustan a este paradigma.2 3 multiplymultiply 2 32 multiply 3

Los algoritmos basados en pilas manipulan datos extrayéndolos e insertándolos en la pila. Los operadores rigen cómo la pila manipula los datos . Para enfatizar el efecto de una instrucción, se suele usar un comentario que muestra la parte superior de la pila antes y después de la instrucción; esto se conoce como diagrama de efectos de pila. Algunos lenguajes orientados a pilas pueden usar varias pilas para diferentes propósitos; por ejemplo, PostScript usa pilas separadas para variables, diccionarios, procedimientos, algunos procedimientos típicos y sentencias de control de flujo. El análisis del modelo del lenguaje permite interpretar expresiones y programas de forma sencilla.

Algoritmos basados en pilas

PostScript es un ejemplo de lenguaje posfijo basado en pila. Un ejemplo de expresión en este lenguaje es 2 3 mul(donde 'mul' es el comando para la operación de multiplicación). Calcular la expresión requiere comprender cómo funciona la orientación de la pila.

La orientación de la pila se puede representar mediante la siguiente analogía de una cinta transportadora. Al final de la cinta (la entrada ), se colocan en secuencia placas marcadas con 2, 3, y mul. La placa del final de la cinta ( 2) se puede tomar, pero no se puede acceder a las demás 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, no desde el medio ni desde la parte inferior. Se pueden suministrar placas en blanco (y un marcador) y las placas se pueden desechar permanentemente.

Toma el plato 2y colócalo en la pila, luego toma el plato 3y colócalo en la pila. A continuación, toma el mulplato. Esta es una instrucción a realizar. Luego, toma los dos platos superiores de la pila, multiplica sus etiquetas ( 2y 3), y escribe el resultado ( 6) en un plato nuevo. Desecha los dos platos viejos ( 2y 3) y el plato mul, y coloca el plato nuevo en la pila. Sin más platos en la cinta transportadora, el resultado del cálculo ( 6) se muestra en el plato que está en la parte superior de la pila.

Este es un cálculo muy sencillo. ¿Qué ocurre si se necesita un cálculo más complejo, como por ejemplo ? Si se escribe primero en notación posfija, es decir, , 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 tabla siguiente. 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 dicha entrada.(2 + 3) × 11 + 12 3 add 11 mul 1 add

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 solo tiene una forma de manejar datos, tomando un dato de la parte superior de la pila (lo que se denomina "pop ") y volviéndolo a colocar en la parte superior (lo que se denomina "push "). Cualquier expresión que pueda escribirse de forma convencional , o en otro lenguaje de programación, puede escribirse en forma posfija (o prefija) y, por lo tanto, ser interpretada por un lenguaje orientado a pila.

Manipulación de pilas

Dado que la pila es el medio clave para manipular datos en un lenguaje orientado a pilas, estos lenguajes suelen proporcionar operadores de manipulación de pilas. Los más comunes son dup: duplicar el elemento en la cima de la pila exch, swapintercambiar elementos en la cima de la pila (el primero se convierte en el segundo y el segundo en el primero), rollpermutar cíclicamente elementos en la pila o en una parte de ella pop, dropdescartar el elemento en la cima de la pila (el push es implícito), entre otros. Estos operadores son fundamentales para estudiar los procedimientos.

Diagramas de efecto de pila

Para facilitar la comprensión del efecto de la instrucción, se incluye un breve comentario que muestra la parte superior de la pila antes y después de la instrucción. Si hay varios elementos, la parte superior de la pila se encuentra a la derecha. Esta notación se usa comúnmente en el lenguaje Forth, donde los comentarios se encierran entre paréntesis.

(antes -- después)

Por ejemplo, se describen los operadores básicos de la pila Forth:

dup ( a -- aa ) drop ( a -- ) swap ( ab -- ba ) over ( ab -- aba ) rot ( abc -- bca )

fibA continuación se describe la función:

fib ( n -- n' )

Es equivalente a las precondiciones y postcondiciones en la lógica de Hoare . Ambos comentarios también pueden ser referenciados como aserciones , aunque no necesariamente en el contexto de lenguajes basados en pila.

Pilas PostScript

PostScript y otros lenguajes de pila tienen pilas separadas para otros propósitos.

Variables y diccionarios

La evaluación de diferentes expresiones ya ha sido analizada. La implementación de variables es importante para cualquier lenguaje de programación, pero para los lenguajes orientados a pilas, reviste especial importancia, ya que solo existe una forma de interactuar con los datos.

La forma en que se implementan las variables en lenguajes orientados a pila 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 un prefijo /, por lo que /xes un objeto de datos de nombre que se puede asociar con, por ejemplo, el número 42. El definecomando es def, por lo que

/x 42 def

se asocia con el nombre xcon el número 42en el diccionario 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.

Procedimientos

En un lenguaje de programación basado en pila, un procedimiento se trata como un objeto de datos por derecho propio. En PostScript, los procedimientos se denotan entre {y }.

Por ejemplo, en la sintaxis de 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 simples objetos de datos, se pueden definir nombres para los 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 de forma natural una funcionalidad inesperada: al buscar una definición en un diccionario, se consulta primero el diccionario superior, luego el siguiente, y así sucesivamente. Si se define un procedimiento con el mismo nombre que otro ya definido en un diccionario diferente, se llamará al local.

Anatomía de algunos procedimientos típicos

Los procedimientos suelen recibir argumentos. Estos son gestionados por el procedimiento de una manera 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 exch 0 eq or not { dup 1 sub fib exch 2 sub fib add } if } def

Se utiliza una definición recursiva en la pila. La función de números de Fibonacci toma un argumento. Primero, se comprueba 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 equivalente pila: 4 4 falso intercambio pila: 4 falso 4 0 eq pila: 4 falso falso o pila: 4 falso no pila: 4 verdadero

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

(llamada recursiva aquí)

 pila: 4 F(3) intercambio pila: F(3) 4 2 sub pila: F(3) 2 mentira

(llamada recursiva aquí)

 pila: F(3) F(2) agregar pila: F(3)+F(2)

que es el resultado esperado.

Este procedimiento no utiliza variables con nombre, solo 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 con nombre n. Suponiendo que /sq {/n exch def n n mul} defy 3 sqse llama, el procedimiento sqse analiza de la siguiente manera:

 pila: 3 /n intercambio pila: /n 3 definición pila: vacía (ya ha sido definida) norte pila: 3 norte pila: 3 3 mul pila: 9

que es el resultado esperado.

Control y flujo

Como existen procedimientos anónimos, el control de flujo puede surgir de forma natural. Se requieren tres datos para una instrucció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 una función casi equivalente 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 estructuras son similares.

Análisis del modelo lingüístico

El modelo sencillo que ofrece un lenguaje orientado a pila permite interpretar expresiones y programas de forma simple y, en teoría, evaluarlos mucho más rápido, ya que no se requiere análisis sintáctico, sino léxico . La forma en que se escriben estos programas facilita su interpretación por parte de las máquinas, razón por la cual PostScript resulta idóneo para su uso en impresoras. Sin embargo, la forma algo artificial de escribir programas PostScript puede suponer una barrera inicial para comprender lenguajes orientados a pila como PostScript.

Si bien la capacidad de modificar definiciones predefinidas y externas puede dificultar la depuración de programas, y el uso irresponsable de esta función puede provocar un comportamiento impredecible, también puede simplificar enormemente algunas funciones. Por ejemplo, en PostScript, showpagese puede reemplazar el operador predeterminado por uno personalizado que aplique un estilo determinado a la página, en lugar de tener que definir un operador personalizado o repetir código para generar dicho estilo.

Véase también

Referencias

↑ Luerweg, T. (2015). Paradigmas de programación basados en pilas. Concepts of Programming Languages–CoPL'15, 33.
↑ Oren Patashnik, Diseño de estilos BibTeX (PDF)