¿Cuál es el significado de la notación polaca inversa?

21

Enseño computación a jóvenes de 18 años. Después de que se les explicara la notación polaca inversa, uno preguntó por qué es lo suficientemente significativo como para estar en el examen público. Le expliqué el significado histórico de las calculadoras de los años 70, pero esto no logró abordar el problema. También existen aplicaciones prácticas o teóricas simultáneas de RPN.

Matt Scott
fuente
3
He estado programando durante casi diez años y he completado una maestría en CS, pero no creo haber visto o usado el esmalte inverso en ningún contexto serio. ¿Estás seguro de que es relevante, en particular para enseñar a los estudiantes?
Raphael
Aquí hay una implementación de un motor de expresiones regulares que usa notación postfix: swtch.com/~rsc/regexp/regexp1.html#thompson . Ken Thompson lo usó en su primera implementación también. Además, es una técnica popular para evaluar expresiones en tiempo de ejecución (si está compilando un compilador).
saadtaame
En RPN puedes escribir cualquier expresión sin usar corchetes.
Seg Fault
3
El artículo de wikipedia sobre RPN cubre mucho terreno. Los textos lógicos a veces se refieren a la notación polaca (porque no tiene corchetes), cuando explican lo que se puede omitir de las pruebas como "azúcar sintáctico" puro. Sin embargo, RPN es importante debido a su estrecha relación con las pilas. Comprender las pilas es importante para la depuración interactiva, porque la famosa "traza inversa" normalmente es solo un volcado de pila. Los lenguajes funcionales puros todavía están luchando por ofrecer algo comparable a un volcado de pila para la depuración, aun así tendrían información mucho más detallada que ofrecer (si pudieran representarlo).
Thomas Klimpel
Tengo que retractar mi comentario anterior parcialmente. Yo he visto a alguien el uso post-fix notación para árboles cadena de volcado. Fue horrible de leer, pero fácil de codificar. Entonces, en casos de uso muy específicos, la RP puede ser útil, pero no estoy seguro de si esto se extiende a la educación (en general). Supongo que puede usarlo para mostrar que la sintaxis no es fija.
Raphael

Respuestas:

9

He usado RPN varias veces para la creación rápida de prototipos, por ejemplo, de programas que tienen que leer e interpretar una expresión matemática proporcionada por el usuario.

Mientras que la notación matemática regular requeriría al menos un analizador recursivo (paréntesis, orden del operador, etc.), un analizador RPN es básicamente una pila con una switchdeclaración similar. Supongo que es esta combinación de simplicidad y poder expresivo lo que llevó a HP a usarlo inicialmente.

Sin embargo, esto suele ser para la creación rápida de prototipos y para mayor comodidad. Nunca asumiría que un usuario puede o quiere entender RPN.

Pedro
fuente
8

Solo para expandir las respuestas / comentarios anteriores: no olvide que RPN está vivo y en buena forma ... de hecho, actualmente se usa en máquinas apiladas como la máquina virtual Java.

De Wikipedia: "... una máquina de pila implementa una pila con registros. Los operandos de la unidad lógica aritmética (ALU) son siempre los dos registros superiores de la pila y el resultado de la ALU se almacena en el registro superior de la pila . 'Máquina apiladora' se refiere comúnmente a computadoras que usan una pila Último en entrar, Primero en salir para mantener valores temporales de corta duración mientras se ejecutan declaraciones de programas individuales. El conjunto de instrucciones lleva a cabo la mayoría de las acciones de ALU con operaciones postfix ( notación polaca inversa ) que funciona solo en la pila de expresiones, no en registros de datos o celdas de memoria principal ... "

Las ventajas / desventajas de dicho enfoque también se describen en el artículo de Wikipedia .

Vor
fuente
Hm, mirando el código de bytes no ves RPN per se; por supuesto, las instrucciones aparecen en orden "post-arreglo", pero eso no parece RPN en aritmética, y su razón es bastante clara. Las máquinas de registro deben proceder de la misma manera: cargar valores, luego combinar.
Raphael
5

Forth y PostScript (y, por lo tanto, PDF que IIRC comenzó como una codificación binaria de un subconjunto de PostScript) son lenguajes de postfix más conocidos que uno de HP calculadora de bolsillo.

Entonces también es una opción relativamente común como representación intermedia en compiladores simples.

Las máquinas virtuales más simples tienden a tener también un lenguaje "máquina" de postfix.

Un programador
fuente
Por cierto, la frase "VM más simple" incluye la JVM. Lo interesante de RPN es que es la máquina apiladora más simple y útil. Las máquinas apiladoras son lo que es realmente interesante, útil y relevante.
Seudónimo
4

Con respecto a las calculadoras: Vea ¿Qué es RPN?

  • Beneficios: RPN ahorra tiempo y pulsaciones de teclas. Evita usar y hacer un seguimiento de los paréntesis mientras hace los cálculos. El proceso es similar a la forma en que aprendiste matemáticas en papel.

  • Puede ver los resultados intermedios a medida que realiza sus cálculos en lugar de solo la respuesta al final. Esto es extremadamente útil para aprender la lógica. Los maestros de matemáticas están utilizando esta función para mejorar la comprensión de las matemáticas por parte de los estudiantes.

  • Un resultado intermedio permite al usuario verificar la respuesta y corregir errores más fácilmente. Es más fácil seguir la corriente de cálculo. El usuario define la prioridad de los operadores.

  • RPN es lógico porque el usuario primero da el número y luego le dice qué hacer con él.

Guy Coder
fuente
3

Como su nombre indica, la notación polaca inversa o la notación polaca directa son anotaciones. Son sintaxis para representar algo, y una sintaxis realmente eficiente si considera los requisitos de memoria. Lo que representan son árboles enraizados, que pueden ser fórmulas, árboles de sintaxis abstracta (AST) y otros tipos de entidades, que cualquier persona tiene el derecho constitucional de considerar absolutamente inútil.

Ocasionalmente, uno tiene que almacenar tales entidades en el archivo. Por ejemplo, hay sistemas que pueden editar o transformar programas como AST, y pueden necesitar almacenar tales representaciones. La forma polaca es conveniente. Tiene una legibilidad limitada para los humanos, especialmente para árboles grandes, pero es una representación muy conveniente para las máquinas.

Otro aspecto es que creo que el estudio de los árboles y sus usos y representaciones elementales, así como los dispositivos asociados (pilas), son pedagógicamente útiles como introducción a futuros estudios de conceptos más avanzados (sintaxis, análisis, lógica, lingüística). , ...)

También tiene la ventaja de ser conceptualmente bastante simple y fácil de experimentar en papel. También es una buena ocasión para discutir la sintaxis y el hecho de que la sintaxis es una representación, y que las representaciones pueden variar, mientras que representan la misma cosa, y que se pueden usar diferentes representaciones dependiendo de la necesidad de cumplir (optimización del espacio, fácil modificación, legibilidad humana, legibilidad informática, ...).

Pero me sorprende que esta pregunta, y sus respuestas, consideren solo RPN, y ninguna considere la notación polaca directa.

Ciertamente es excelente que los estudiantes pregunten. Pero responder a esa pregunta siempre tiene diversos aspectos. ¿Es útil para el conocimiento mismo? Creo que es. ¿Es útil como ejercicio pedagógico? Creo que lo es, pero eso depende mucho de la audiencia prevista, y solo el maestro puede evaluar lo que puede entender. ¿Es útil entender algunos problemas conceptuales? Creo que sí, pero de nuevo depende de la evaluación del profesor sobre qué conceptos se pueden explicar a sus alumnos.

babou
fuente
2

Tu estudiante tenía toda la razón. La notación polaca inversa no es lo suficientemente significativa en informática como para que valga la pena dedicarle un tiempo de clase muy limitado. En cambio, hay muchas otras ideas conceptuales maravillosas que podría haber enseñado, con ideas intelectuales profundas: matrimonio estable, corte de pastel, diagonalización e indecidibilidad del problema de detención, pruebas interactivas y pruebas de conocimiento cero, etc., etc. Sí, todo eso se puede hacer accesible a los jóvenes de 18 años.

¡Y espero que haya elogiado a su estudiante por ser lo suficientemente valiente como para hacer la pregunta! Tuvieron que ponerse sobre una repisa para plantear el problema. Habla bien por su estilo de enseñanza que se sintieron cómodos haciéndole esta pregunta.

DW
fuente
1
La notación polaca no tarda casi en enseñar. La linealización de las estructuras estándar, como los árboles, también es importante, dado que el almacenamiento masivo a menudo es secuencial en lugar de acceso aleatorio. También es posible que desee almacenarlo de manera eficiente o comprender cómo recuperarlo en su totalidad o en parte. Conecta árboles, arboles, estructuras empotradas y pushdown. Abstractamente, le dice cómo hacer codificaciones de Gödel para datos. En comparación con la tremenda pérdida de tiempo y energía representada por el análisis LR y LL, y otras tecnologías basura, incluso diría que el tiempo dedicado a la notación polaca es un tiempo bien empleado.
babou
"no lo suficientemente significativo en informática" - increíblemente obstinado
Dmitri Zaitsev
1

La notación polaca inversa fue una buena herramienta en mi educación para comprender los árboles de análisis y las estructuras de datos de los árboles en general. También es útil si alguien tiene algún interés en la programación en cualquiera de la familia de lenguajes Lisp (Clojure, emacs-lisp, esquema, etc.).

usuario21796
fuente
¿Por qué Lisp y Scheme? Están llenos de paréntesis.
babou