notación polaca

La notación polaca ( PN ), también conocida como notación polaca normal ( NPN ), ^{[ 1 ]} notación de Łukasiewicz , notación de Varsovia , notación prefija polaca , notación oriental o simplemente notación prefija , es una notación matemática en la que los operadores preceden a sus operandos , a diferencia de la notación infija más común , en la que los operadores se colocan entre los operandos, así como de la notación polaca inversa (RPN), en la que los operadores siguen a sus operandos. No necesita paréntesis siempre que cada operador tenga un número fijo de operandos . La descripción "polaca" se refiere a la nacionalidad del lógico Jan Łukasiewicz , ^{[ 2 ] : 24 [ 3 ] : 78 [ 4 ]} quien inventó la notación polaca en 1924. ^{[ 5 ] : 367, nota al pie 3 [ 6 ] : 180, nota al pie 3}

A veces, el término notación polaca se refiere colectivamente a la notación polaca normal y a la notación polaca inversa (notación prefija y notación postfija, las dos alternativas a la notación infija ). ^{[ 7 ]}

Cuando los intérpretes de lenguajes de programación utilizan la notación polaca como sintaxis para expresiones matemáticas, esta se analiza fácilmente en árboles sintácticos abstractos y, de hecho, puede definir una representación biunívoca de las mismas. Por este motivo, Lisp (véase Implementaciones , más abajo) y lenguajes de programación relacionados definen toda su sintaxis en notación prefija (y otros utilizan notación postfija).

Una cita de un artículo de Jan Łukasiewicz de 1931 ^{[ 5 ] : 367, nota al pie 3 [ 6 ] : 180, la nota al pie 3} indica cómo se inventó la notación:

Se me ocurrió la idea de una notación sin paréntesis en 1924. Utilicé esa notación por primera vez en mi artículo Łukasiewicz (1), pág. 610, nota al pie.

La referencia citada por Łukasiewicz, es decir, Łukasiewicz (1), ^{[ 8 ]} es aparentemente un informe litografiado en polaco . El artículo de referencia ^{[ 5 ]} de Łukasiewicz fue revisado por Henry A. Pogorzelski en el Journal of Symbolic Logic en 1965. ^{[ 9 ]} Heinrich Behmann , editor en 1924 del artículo de Moses Schönfinkel , ^{[ 10 ]} ya tenía la idea de eliminar los paréntesis en las fórmulas lógicas. En uno de sus artículos, Łukasiewicz afirmó que su notación es la más compacta y la primera notación sin paréntesis escrita linealmente, pero no la primera, ya que Gottlob Frege había propuesto su notación Begriffsschrift sin paréntesis en 1879. ^{[ 11 ]}

Alonzo Church menciona esta notación en su libro clásico sobre lógica matemática como digna de mención en los sistemas de notación, incluso en contraste con la exposición y el trabajo de notación lógica de Alfred Whitehead y Bertrand Russell en Principia Mathematica . ^{[ 12 ]}

En el libro de Łukasiewicz de 1951, El silogístico de Aristóteles desde el punto de vista de la lógica formal moderna , menciona que el principio de su notación era escribir los functores antes de los argumentos para evitar los corchetes y que había empleado su notación en sus trabajos de lógica desde 1929. ^{[ 3 ] : 78} Luego procede a citar, como ejemplo, un artículo de 1930 que escribió con Alfred Tarski sobre el cálculo sentencial . ^{[ 13 ]}

Aunque ya no se usa mucho en lógica, ^{[ 14 ]} la notación polaca ha encontrado desde entonces un lugar en la informática .

La expresión para sumar los números 1 y 2 se escribe en notación polaca como + 1 2 (prefijo), en lugar de como 1 + 2 (infijo). En expresiones más complejas, los operadores siguen precediendo a sus operandos, pero los operandos pueden ser expresiones que incluyan nuevamente operadores y sus operandos. Por ejemplo, la expresión que se escribiría en notación infija convencional como

se puede escribir en notación polaca como

Suponiendo una aridad dada de todos los operadores involucrados (aquí el "−" denota la operación binaria de resta, no la función unaria de cambio de signo), cualquier representación de prefijo bien formada es inequívoca, y los corchetes dentro de la expresión de prefijo son innecesarios. Por lo tanto, la expresión anterior se puede simplificar aún más a

El procesamiento del producto se pospone hasta que sus dos operandos estén disponibles (es decir, 5 menos 6 y 7). Como en cualquier notación, las expresiones más internas se evalúan primero, pero en la notación polaca esta "internitud" se puede transmitir mediante la secuencia de operadores y operandos en lugar de mediante paréntesis.

En la notación infija convencional, se requieren paréntesis para anular las reglas de precedencia estándar , ya que, refiriéndonos al ejemplo anterior, moverlos

o eliminándolos

cambia el significado y el resultado de la expresión. Esta versión está escrita en notación polaca como

Cuando se trata de operaciones no conmutativas, como la división o la resta, es necesario coordinar la disposición secuencial de los operandos con la definición de cómo el operador toma sus argumentos, es decir, de izquierda a derecha. Por ejemplo, ÷ 10 5 , con 10 a la izquierda de 5, significa 10 ÷ 5 (que se lee como "dividir 10 entre 5"), o − 7 6 , con 7 a la izquierda de 6, significa 7 − 6 (que se lee como "restar de 7 el operando 6").

La notación prefija/postfija es especialmente popular por su capacidad innata para expresar el orden de las operaciones sin necesidad de paréntesis ni otras reglas de precedencia, como suele emplearse con la notación infija . En cambio, esta notación indica de forma unívoca qué operador evaluar primero. Se asume que cada operador tiene una aridad fija y que todos los operandos necesarios se proporcionan explícitamente. Una expresión prefija válida siempre comienza con un operador y termina con un operando. La evaluación puede proceder de izquierda a derecha o en sentido contrario. Comenzando por la izquierda, la cadena de entrada, compuesta por tokens que representan operadores u operandos, se apila token a token hasta que las entradas superiores de la pila contienen el número de operandos que se ajusta al operador superior (inmediatamente debajo). Este grupo de tokens en la parte superior de la pila (el último operador apilado y el número correspondiente de operandos) se reemplaza por el resultado de ejecutar el operador sobre este o estos operandos. A continuación, el procesamiento de la entrada continúa de esta manera. El operando más a la derecha en una expresión de prefijo válida vacía la pila, excepto por el resultado de evaluar toda la expresión. Al comenzar desde la derecha, el apilamiento de tokens se realiza de manera similar, solo que la evaluación se activa mediante un operador, que encuentra el número apropiado de operandos que se ajusta a su aridad ya en la parte superior de la pila. Ahora, el token más a la izquierda de una expresión de prefijo válida debe ser un operador, que se ajuste al número de operandos en la pila, lo que nuevamente produce el resultado. Como se puede ver en la descripción, un almacenamiento de pila descendente sin capacidad de inspección arbitraria de la pila es suficiente para implementar este análisis .

La manipulación de pilas esbozada anteriormente funciona, con entrada reflejada, también para expresiones en notación polaca inversa .

La tabla que aparece a continuación muestra el núcleo de la notación de Jan Łukasiewicz en la lógica moderna, que también se utilizó, por ejemplo, en la Lógica Formal de Arthur Prior . ^{[ 15 ]} Algunas letras de la tabla de notación polaca representan palabras específicas en polaco , como se muestra:

En la obra de Łukasiewicz sobre lógicas multivaluadas, los cuantificadores abarcaban valores proposicionales.

Bocheński introdujo un sistema de notación polaca que nombra los 16 conectores binarios de la lógica proposicional clásica . ^{[ 20 ] : 16} Para la lógica proposicional clásica, es una extensión compatible de la notación de Łukasiewicz. Pero las notaciones son incompatibles en el sentido de que Bocheński utiliza${\displaystyle L}$y${\displaystyle M}$(para la no implicación y la no implicación recíproca) en lógica proposicional y usos de Łukasiewicz${\displaystyle L}$y${\displaystyle M}$en lógica modal.

La notación prefija se ha aplicado ampliamente en las expresiones S de Lisp , donde los paréntesis son necesarios ya que los operadores del lenguaje son datos en sí mismos ( funciones de primera clase ). Las funciones de Lisp también pueden ser variádicas . El lenguaje de programación Tcl , al igual que Lisp, también utiliza la notación polaca a través de la biblioteca mathop. El lenguaje de programación Ambi ^{[ 21 ]} utiliza la notación polaca para operaciones aritméticas y construcción de programas. La sintaxis de los filtros LDAP utiliza la notación prefija polaca. ^{[ 22 ]}

La notación posfija se utiliza en muchos lenguajes de programación orientados a pilas, como PostScript y Forth . La sintaxis de CoffeeScript también permite llamar a funciones mediante notación prefija, sin dejar de ser compatible con la sintaxis posfija unaria común en otros lenguajes.

El número de valores de retorno de una expresión es igual a la diferencia entre el número de operandos en una expresión y la aridad total de los operadores menos el número total de valores de retorno de los operadores.

La notación polaca, generalmente en forma posfija, es la notación elegida por ciertas calculadoras , en particular las de Hewlett-Packard . ^{[ 23 ]} En un nivel inferior, los operadores posfijos son utilizados por algunas máquinas de pila como los grandes sistemas Burroughs .

• Fothe, Michael; Wilke, Thomas, eds. (2015) [2014-11-14]. Escrito en Jena, Alemania. Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [ Bodega, pila y memoria automática: una estructura con potencial ] (PDF) (Tagungsband zum Kolloquium, 14 de noviembre de 2014 en Jena). Serie GI: Apuntes de conferencias sobre informática (LNI) - Temáticas (en alemán). vol.  T-7. Bonn, Alemania: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH. ISBN 978-3-88579-426-4. ISSN 1614-3213 . Archivado (PDF) del original el 12-04-2020 . Recuperado el 12-04-2020 . (77 páginas)
• Langmaack, Hans [en alemán] (2015) [14 de noviembre de 2014]. Escrito en Kiel, Alemania. Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat [ Trabajos de Friedrich L. Bauer y Klaus Samelson en la década de 1950 sobre la introducción de los términos principio de bodega y autómata de bodega ] (PDF) (en alemán). Jena, Alemania: Institut für Informatik, Christian-Albrechts-Universität zu Kiel. págs. 19 a 29. Archivado (PDF) desde el original el 14 de noviembre de 2022 . Consultado el 14 de noviembre de 2022 . (11 páginas) (Nota: Publicado en Fothe & Wilke .)
• Goos, Gerhard [en alemán] (7 de agosto de 2017). Geschichte der deutschsprachigen Informatik - Programmiersprachen und Übersetzerbau [ Historia de la informática en los países de habla alemana - Lenguajes de programación y diseño de compiladores ] (PDF) (en alemán). Karlsruhe, Alemania: Fakultät für Informatik, Instituto Tecnológico de Karlsruhe (KIT). Archivado (PDF) desde el original el 19 de mayo de 2022 . Consultado el 14 de noviembre de 2022 .(11 páginas)

• Contenido multimedia relacionado con la notación polaca en Wikimedia Commons.