Principia El Lenguaje de Programación Stop

---

II.- Planteamiento del Problema.

1.- La Notación Polaca Inversa.

En 1951, Jan Lukasiewicz demostró por primera vez y de manera formal que expresiones arbitrarias pueden ser especificadas sin ambigüedad y sin hacer uso de paréntesis colocando los operadores inmediatamente después de sus operandos. Por ejemplo, la expresión.

(a+b)*(c-d)

se puede escribir en notación prefija como.

* + a b - c d

y leerse como la multiplicación de la adición de a más b por la diferencia de c menos d. Similarmente la expresión puede escribirse en notación postfija como

a b + c d - *

con el mismo significado. En honor a Lukasiewicz, las notaciones prefija y postfija se conocieron como polaca y polaca inversa, respectivamente.

Durante la siguiente década los méritos de la notación polaca inversa fueron estudiados y dos simplificaciones en la ejecución de aritmética por computadora fueron descubiertas. Primero, como la notación polaca inversa es explorada de izquierda a derecha, cada operador que es encontrado puede ser ejecutado inmediatamente. Esto contrasta con la notación con paréntesis donde la ejecución de los operadores puede ser pospuesta. Por ejemplo, en el caso anterior la ejecución de la multiplicación debe posponerse hasta obtenerse los resultados de la suma y diferencia, lo que obliga a tener que hacer uso de memoria y controles adicionales. Segundo, si una pila (la estructura de datos con un comportamiento de "primero en entrar - último en salir") se empleaba para almacenar los operandos conforme la expresión era explorada, los operandos requeridos por cada operador encontrado estarían inmediatamente al alcance de éste en la entrada de la pila, ya sea por recién inserción o como consecuencia de un cálculo previo.

2.- Procesando con Pilas.

Veamos con más detalle el procesamiento de estas expresiones. Tomando de ejemplo la expresión anterior.

Además del éxito de su uso en la compilación de programas, Hewlett-Packard popularizó enormemente este tipo de expresiones a través de la primera calculadora científica portátil, la HP-35. La representación RPN (siglas en inglés de Reverse Polish Notation) ha sido desde entonces sello característico de sus calculadoras.

Algunos ejemplos adicionales se presentan a continuación. Estos ilustran la importancia del orden en que los operandos aparecen.

Debe considerarse que mismos resultados pueden ser obtenidos con expresiones diferentes cuando el orden de los operadores no es importante, como también que hay operadores con un mismo peso jerarquico de evaluación en los que no es posible hacer esto.

Ejemplos adicionales son:

3.- La Manipulación de elementos en la pila.

En la sección anterior, la mayoría de los ejemplos han sido formados conforme la expresión infija es explorada. Sin embargo, si consideramos que en la pila es posible introducir operandos para después aplicar los operadores, es entonces posible que nos enfrentemos a situaciones muy particulares. Por ejemplo, si en la pila ya se tuviera

y la expresión a evaluar fuera

nos enfrentamos a un problema que con los elementos proporcionados hasta el momento no es posible solucionar. Forzosamente requeriririamos extraer los dos elementos de más abajo para ingresarlos en orden inverso al mostrado. Ya sea que explícitamente se haga esto, o a que contemos con circuitería especial (pensando en que esto será implementado para un dispositivo electrónico) que nos permita invertir las dos primeras posiciones de la pila, introduciremos el concepto de intercambio y le nombraremos SWAP.

Esto nos brinda enormes facilidades. Por ejemplo, si tuviéramos que calcular la expresión

pero el orden en que tuvieramos disponibles los operandos fuera 2, 3, 8 y 15, podríamos trabajar de la siguiente forma:

El hablar de la disponibilidad de los operandos debe hacernos considerar otros casos. Por ejemplo, contar con una pila

y determinar que debemos calcular el resultado equivalente a la expresión infija 15 / (8 - 5); expresión que con la disposición de elementos en la pila y sólo con la operación de intercambio no es posible calcular. Forzosamente requerimos llevar a cabo la reorganización de elementos de tal forma que involucremos al tercer nivel de la pila. De la misma forma que se trató el caso de la instrucción de intercambio SWAP, definiremos una acción para obtener el efecto deseado, que en este caso llamaremos de rotación y a la que identificaremos como ROTATE.

De esta forma, con la disposición inicial de elementos podremos llevar a cabo el cálculo solicitado con la secuencia de operaciones.

Sin duda esta nueva acción nos da mayor libertad de trabajo, pero nuestra capacidad de rotación de elementos está limitada por el sentido del giro, i.e. la rotación es hacia arriba, llevando el elemento del tercer nivel a la base y empujando a los dos inferiores en una posición. Por ejemplo, si con la misma pila inicial del ejercicio anterior tuviéramos que calcular 8 / (5 - 15) requeriríamos de dos operaciones ROTATE para colocar a los elementos de la pila en el orden adecuado. Pero, si pudiéramos contar con una operación de giro contrario como se ilustra:

haríamos sólo entonces.

En el cálculo de expresiones aritméticas es común encontrarse con resultados parciales o valores que se repiten. Por ejemplo en la expresión infija y su correspondiente transformación a sufija

encontramos la repetición de la subexpresión 2 + 3. Existen tres posibilidades a este respecto. La primera corresponde a aquella en la que el valor repetido ya fue obtenido, con lo que es de esperar que se encuentre en un nivel superior de la pila y del cual requeriríamos una copia, para este caso

y con lo que podemos hacer:

El segundo caso podría darse cuando se tiene un valor que se utilizaría en una operación posterior para la cual el valor ya debía encontrarse en la pila. Por ejemplo, calculando la misma expresión anterior

y así

Para el tercer caso es necesario hacer un comentario previo. Dos acciones básicas en el manejo de una pila son por supuesto la inserción y extracción de elementos. Hasta el momento no hemos hecho mención de la necesidad de una operación para explícitamente llevar a cabo la inserción de un elemento en la pila; por el contrario, hemos tomado esta acción de manera natural e implícitamente.

En la programación de nivel bajo (ensamblador, código máquina), se recurre a una pila para llevar a cabo el paso de parámetros entre subrutinas, para guardar el valor de registros y banderas, y para conservar valores de retorno. En este nivel de programación existen instrucciones para llevar a cabo de forma explícita la inserción y extración de datos de la pila, generalmente nombradas como PUSH y POP, respectivamente. Quienes estén familiarizados con la programación de nivel bajo conocerán este tipo de instrucciones. En un ambiente en donde la pila es un elemento secundario de donde tomar y poner datos esto es necesario pero en uno donde la pila es el medio principal, el necesitarlas para cada acción presenta algunos inconvenientes. Por ejemplo, si tuvieramos que introducir los elementos a la pila de manera explícita a través de una operación PUSH, la expresión anterior habría sido codificada como:

lo que resulta en una expresión recargada de operaciones, sin mencionar redundante en su significado. No hay ningún otro lugar a donde colocar nuestros operandos (no como el caso de la programación de nivel bajo en donde nuestro principal destino es memoria o los registros del procesador). Por este motivo, los lenguajes de programación de nivel intermedio y alto orientados al procesamiento con pilas dan por implícita la inserción de elementos en la pila y no requieren de un PUSH implícito. Seguiremos la misma idea.

Sin embargo, aún podemos sacar provecho del término y conceptos asociados a PUSH, por lo que en nuestro tercer caso, para una expresión como:

podríamos resolverla fácilmente si definimos a la instruccion PUSH como una forma de duplicar la base de la pila. Así tenemos

para dejar

Finalmente, hasta el momento hemos visto acciones encaminadas tomar valores o ingresarlos de o a la pila. El último punto que deberíamos cubrir es el de limpiar la pila. Esto lo logramos con la siguiente definición:

El concepto asociado a POP lo reservaremos para usarlo con algo más acorde a su tradicional significado y que veremos más adelante.