Qual é o significado da notação polonês reversa?

21

Ensino computação a jovens de 18 anos. Depois de ter explicado a notação polonesa reversa, perguntamos por que é significativo o suficiente para participar de um exame público. Expliquei o significado histórico das calculadoras dos anos 70, mas isso não conseguiu realmente resolver o problema. Portanto, existem aplicações práticas ou teóricas concorrentes da RPN.

Matt Scott
fonte
3
Faço programação há quase dez anos e concluí um mestrado em CS, mas acho que nunca vi ou usei polonês reverso em nenhum contexto sério. Você tem certeza de que é relevante, principalmente para ensinar os alunos?
Raphael
Aqui está uma implementação de um mecanismo de expressões regulares que usa a notação postfix: swtch.com/~rsc/regexp/regexp1.html#thompson . Ken Thompson também o usou em sua primeira implementação. Além disso, é uma técnica popular para avaliar expressões em tempo de execução (se você estiver criando um compilador).
saadtaame 23/09/12
No RPN, você pode escrever qualquer expressão sem usar colchetes.
Seg Fault
3
O artigo da Wikipedia sobre RPN cobre muito terreno. Os textos lógicos às vezes se referem à notação polonesa (porque é livre de colchetes), quando explicam o que pode ser omitido das provas como puro "açúcar sintático". No entanto, o RPN é importante devido à sua estreita relação com as pilhas. Entender pilhas é importante para a depuração interativa, porque o famoso "backtrace" é normalmente apenas um despejo de pilha. Linguagens funcionais puras ainda estão lutando para oferecer algo comparável a um despejo de pilha para depuração, mesmo assim elas teriam informações muito mais detalhadas para oferecer (se pudessem representá-lo).
Thomas Klimpel 23/09/12
Eu tenho que retirar meu comentário anterior parcialmente. Eu vi alguém usar a notação pós-correção para despejar árvores em seqüência. Era horrível de ler, mas fácil de codificar. Portanto, em casos de uso muito específicos, o RP pode ser útil, mas não tenho certeza se isso se estende à educação (em geral). Você pode usá-lo para mostrar que a sintaxe não é fixa, eu acho.
Raphael

Respostas:

9

Eu usei o RPN várias vezes para prototipagem rápida, por exemplo, de programas que precisam ler e interpretar uma expressão matemática fornecida pelo usuário.

Enquanto a notação matemática regular exigiria pelo menos um analisador recursivo (colchetes, ordem do operador, etc ...), um analisador RPN é basicamente uma pilha com uma switchinstrução semelhante. Eu acho que é essa combinação de simplicidade e poder expressivo que levou a HP a usá-lo inicialmente.

Isto é, no entanto, geralmente para prototipagem rápida e por conveniência. Eu nunca assumiria que um usuário pode, ou quer entender, RPN.

Pedro
fonte
8

Apenas para expandir as respostas / comentários anteriores: não esqueça que o RPN está ativo e em ótima forma ... na verdade, atualmente é usado em máquinas de pilha como a máquina virtual Java.

Da Wikipedia: "... uma máquina de pilha implementa uma pilha com registradores. Os operandos da unidade aritmética lógica (ALU) são sempre os dois primeiros registradores da pilha e o resultado da ALU é armazenado no registro superior da pilha 'Stack machine' geralmente se refere a computadores que usam uma pilha Last-in, First-out para manter valores temporários de curta duração enquanto executam instruções de programa individuais.O conjunto de instruções executa a maioria das ações da ALU com operações de postfix ( notação polonesa reversa ) que trabalhe apenas na pilha de expressões, não nos registros de dados ou nas células principais da memória ... "

As vantagens / desvantagens de tal abordagem também são descritas no artigo da Wikipedia .

Vor
fonte
Hm, olhando para o código de bytes, você não vê RPN por si só; é claro que as instruções aparecem na ordem "pós-correção", mas isso não se parece com o RPN em aritmética, e seu motivo é bastante claro. As máquinas de registro precisam proceder da mesma maneira: carregar valores e depois combinar.
Raphael
5

Forth e PostScript (e, portanto, PDF que o IIRC iniciou como uma codificação binária de um subconjunto de PostScript) são linguagens postfix mais conhecidas que a calculadora de bolso HP.

Também é uma escolha relativamente comum como representação intermediária em compiladores simples.

A VM mais simples também possui uma linguagem de "máquina" do postfix.

AProgrammer
fonte
Aliás, a frase "VM mais simples" inclui a JVM. O interessante do RPN é que é a máquina de pilha útil mais simples. Máquinas de empilhar são o que é realmente interessante, útil e relevante.
Pseudônimo
4

Com relação às calculadoras: consulte O que é RPN?

  • Benefícios: O RPN economiza tempo e pressionamentos de teclas. Você evita usar e acompanhar parênteses ao fazer cálculos. O processo é semelhante ao modo como você aprendeu matemática no papel.

  • Você pode ver os resultados intermediários ao executar seus cálculos, em vez de apenas a resposta no final. Isso é extremamente útil para aprender a lógica. Os professores de matemática estão usando esse recurso para melhorar a compreensão dos alunos sobre matemática.

  • Um resultado intermediário permite ao usuário verificar a resposta e corrigir erros mais facilmente. É mais fácil seguir o fluxo de cálculo. O usuário define a prioridade dos operadores.

  • O RPN é lógico, porque o usuário primeiro fornece o número e depois diz o que fazer com ele.

Guy Coder
fonte
3

Como o nome indica, notação polonesa reversa ou notação polonesa direta são notações. Eles são uma sintaxe para representar algo e são realmente eficientes se você considerar os requisitos de memória. O que eles representam são árvores enraizadas, que podem ser fórmulas, árvores sintáticas abstratas (AST) e outros tipos de entidades, que qualquer pessoa tem o direito constitucional de considerar absolutamente inútil.

Ocasionalmente, é necessário armazenar essas entidades em arquivo. Por exemplo, existem sistemas que podem editar ou transformar programas como AST e podem precisar armazenar essas representações. Formulário polonês é conveniente. Possui legibilidade limitada para humanos, especialmente para árvores grandes, mas é uma representação muito conveniente para máquinas.

Outro aspecto é que acredito que o estudo de árvores e seus usos e representações elementares, bem como dispositivos associados (pilhas), sejam pedagogicamente úteis como introdução a estudos futuros de conceitos mais avançados (sintaxe, análise, lógica, linguística). , ...).

Tem também a vantagem de ser conceitualmente bastante simples e fácil de experimentar no papel. Também é uma boa ocasião para discutir a sintaxe e o fato de que a sintaxe é representação, e que as representações podem variar, enquanto representam a mesma coisa, e que diferentes representações podem ser usadas dependendo da necessidade a ser atendida (otimização de espaço, modificação fácil, legibilidade humana, legibilidade do computador, ...).

Mas estou surpreso que esta pergunta e suas respostas estejam considerando apenas a RPN e nenhuma considere a notação de polimento direto.

Certamente é excelente que os alunos perguntem. Mas responder a essa pergunta sempre tem aspectos diversos. É útil para o próprio conhecimento? Eu acho que é. É útil como exercício pedagógico? Eu acho que é, mas isso depende muito do público-alvo, e apenas o professor pode avaliar o que é capaz de entender. É útil entender algumas questões conceituais? Eu acho que é, mas novamente depende da avaliação do professor sobre quais conceitos podem ser explicados aos seus alunos.

babou
fonte
2

Seu aluno estava absolutamente certo. A notação polonesa reversa não é significativa o suficiente na ciência da computação para valer a pena gastar um tempo de aula muito limitado nela. Em vez disso, existem muitas outras idéias conceituais maravilhosas que você poderia ter ensinado, com profundas idéias intelectuais: casamento estável, corte de bolo, diagonalização e indecidibilidade do problema da parada, provas interativas e provas de zero conhecimento, etc. etc. Sim, tudo isso pode ser acessado por crianças de 18 anos.

E espero que você tenha elogiado seu aluno por ser corajoso o suficiente para fazer a pergunta! Eles tiveram que se colocar em uma borda para levantar a questão. É bom para o seu estilo de ensino que eles se sintam confortáveis ​​em fazer essa pergunta.

DW
fonte
1
A notação polonesa não leva quase tempo para ensinar. A linearização de estruturas padrão, como árvores, também é importante, uma vez que o armazenamento em massa costuma ser seqüencial, e não aleatório. Você também pode armazená-lo com eficiência ou entender como recuperá-lo no todo ou em parte. Ele conecta árvores, caminhada de árvores, estruturas incorporadas e empilhamento. Abstratamente, ele mostra como fazer codificações Gödel para dados. Comparado ao tremendo desperdício de tempo e energia representado pela análise de LR e LL e outras tecnologias de lixo eletrônico, eu diria até que o tempo gasto em notação polonesa é um tempo bem gasto.
babou 21/06/2015
"não é significativo o suficiente em ciência da computação" - incrivelmente opinativo
Dmitri Zaitsev
1

A notação polonesa reversa foi uma boa ferramenta na minha educação para entender árvores de análise e estruturas de dados de árvores em geral. Também é útil se alguém tiver algum interesse em programar em qualquer uma das línguas da família Lisp (Clojure, emacs-lisp, schema etc.).

user21796
fonte
Por que Lisp e Scheme? Eles estão cheios de parênteses.
babou 16/09/14