Каково значение обратной польской записи?

21

Я преподаю информатику до 18 лет. После объяснения им обратной польской записи один из них спросил, почему это достаточно важно для участия в государственном экзамене. Я объяснил историческое значение калькуляторов 70-х годов, но это не помогло решить проблему. Так есть и параллельные практические или теоретические применения RPN.

Мэтт Скотт
источник
3
Я программировал почти десять лет и закончил магистратуру по CS, но я не думаю, что когда-либо видел или использовал обратную полировку в каком-либо серьезном контексте. Вы уверены, что это актуально, в частности, для обучения студентов?
Рафаэль
Вот реализация механизма регулярных выражений, который использует постфиксную нотацию: swtch.com/~rsc/regexp/regexp1.html#thompson . Кен Томпсон также использовал его в своей первой реализации. Кроме того, это популярный метод оценки выражений во время выполнения (если вы создаете компилятор).
saadtaame
В RPN вы можете записать любое выражение без использования скобок.
Ошибка Сег
3
Статья в Википедии о RPN охватывает много вопросов. Логические тексты иногда ссылаются на польскую нотацию (потому что она без скобок), когда объясняют, что может быть опущено в доказательствах как чистый «синтаксический сахар». Тем не менее, RPN важен из-за его тесной связи со стеками. Понимание стеков важно для интерактивной отладки, потому что знаменитая «обратная трассировка» обычно является просто дампом стека. Чистые функциональные языки все еще пытаются предложить что-то сравнимое с дампом стека для отладки, даже если бы они могли предложить гораздо более подробную информацию (если бы они могли это представить).
Томас Климпел
Я должен частично отозвать свой прежний комментарий. Я уже видел использовать кто - то после починки обозначения для строк дампа деревьев. Это было ужасно читать, но легко кодировать. Так что в очень специфических случаях использования RP может быть полезным, но я не уверен, распространяется ли это на образование (в целом). Вы можете использовать это, чтобы показать, что синтаксис не фиксирован, я думаю.
Рафаэль

Ответы:

9

Я использовал RPN несколько раз для быстрого создания прототипов, например, программ, которые должны читать и интерпретировать предоставленное пользователем математическое выражение.

В то время как обычные математические обозначения потребовали бы по крайней мере рекурсивного синтаксического анализатора (думаю, скобки, порядок операторов и т. Д.), Парсер RPN в основном представляет собой стек с оператором, switchподобным. Я предполагаю, что именно это сочетание простоты и выразительной силы привело к тому, что HP использовала его изначально.

Это, однако, обычно для быстрого прототипирования и для удобства. Я бы никогда не предположил, что пользователь может или хочет понять RPN.

Pedro
источник
8

Просто чтобы расширить предыдущие ответы / комментарии: не забывайте, что RPN жив и находится в отличной форме ... на самом деле он в настоящее время используется в стековых машинах, таких как виртуальная машина Java.

Из Википедии: «... стековая машина реализует стек с регистрами. Операнды арифметического логического блока (ALU) всегда являются двумя верхними регистрами стека, а результат из ALU сохраняется в верхнем регистре стека . «Машина стека» обычно относится к компьютерам, которые используют стек «последний пришел - первый пришел» для хранения кратковременных временных значений при выполнении отдельных программных операторов. Набор команд выполняет большинство действий ALU с операциями постфикса ( обратная польская запись ), которые работать только со стеком выражений, а не с регистрами данных или ячейками основной памяти ... »

В преимущества / недостатки такого подхода описаны также в статье Википедии .

Вор
источник
Хм, глядя на байт-код, вы не видите RPN как таковой; конечно, инструкции отображаются в порядке «после исправления», но это не похоже на RPN в арифметике, и его причина довольно ясна. Регистрировать машины нужно так же: загружать значения, затем объединять.
Рафаэль
5

Forth и PostScript (и, следовательно, PDF, который IIRC начал как двоичное кодирование подмножества PostScript) являются более известными языками постфикса, чем один карманный калькулятор HP.

Тогда это также относительно распространенный выбор в качестве промежуточного представления в простых компиляторах.

Более простая ВМ, как правило, также имеет постфиксный «машинный» язык.

AProgrammer
источник
Кстати, фраза «более простая ВМ» включает в себя JVM. Что интересно в RPN, так это то, что это самый простой и полезный стековый компьютер. Стековые машины - это то, что действительно интересно, полезно и актуально.
псевдоним
4

Что касается калькуляторов: см. Что такое RPN?

  • Преимущества: RPN экономит время и нажатия клавиш. Вы избегаете использования и отслеживания скобок при выполнении расчетов. Процесс похож на то, как вы изучали математику на бумаге.

  • Вы можете видеть промежуточные результаты при выполнении вычислений, а не только ответ в конце. Это чрезвычайно полезно для изучения логики. Учителя математики используют эту функцию для улучшения понимания студентами математики.

  • Промежуточный результат позволяет пользователю легче проверять ответ и исправлять ошибки. Проще следить за потоком расчетов. Пользователь определяет приоритет операторов.

  • RPN логичен, потому что пользователь сначала дает число, а затем говорит, что с ним делать.

Гай Кодер
источник
3

Как видно из названия, обратная польская нотация или прямая польская нотация являются нотациями. Это синтаксис для представления чего-либо и фактически эффективный синтаксис, если учесть требования к памяти. Они представляют собой корневые деревья, которые могут быть формулами, абстрактными синтаксическими деревьями (AST) и другими видами сущностей, которые каждый имеет конституционное право считать абсолютно бесполезным.

Иногда нужно хранить такие объекты в файле. Например, существуют системы, которые могут редактировать или преобразовывать программы как AST, и, возможно, потребуется хранить такие представления. Польская форма удобна. Он имеет ограниченную читаемость для людей, особенно для больших деревьев, но это очень удобное представление для машин.

Другим аспектом этого является то, что я считаю, что изучение деревьев и их элементарного использования и представления, а также связанных с ними устройств (стеков), педагогически полезно как введение в будущие исследования более продвинутых понятий (синтаксис, анализ, логика, лингвистика). ...).

Преимущество этого подхода заключается в том, что он концептуально довольно прост, и его легко экспериментировать на бумаге. Это также хороший повод обсудить синтаксис и тот факт, что синтаксис является представлением, и что представления могут различаться, представляя одну и ту же вещь, и что могут использоваться разные представления в зависимости от необходимости выполнения (оптимизация пространства, простое изменение, удобочитаемость человека, читаемость компьютера, ...).

Но я удивлен, что этот вопрос и его ответы рассматриваются только в RPN, и никто не рассматривает прямую польскую запись.

Это, конечно, отлично, что студенты спрашивают. Но ответ на такой вопрос всегда имеет разные аспекты. Это полезно для самого знания? Я думаю, что это. Это полезно в качестве педагогического упражнения? Я думаю, что это так, но это во многом зависит от предполагаемой аудитории, и только учитель может оценить то, что он способен понять. Полезно ли понимать некоторые концептуальные вопросы? Я думаю, что это так, но опять же это зависит от оценки учителем того, какие концепции можно объяснить их ученикам.

Babou
источник
2

Ваш ученик был абсолютно прав. Обратная польская запись не настолько значительна в информатике, чтобы на нее стоило проводить очень ограниченное время. Вместо этого есть много других замечательных концептуальных идей, которым вы могли бы научиться, с глубокими интеллектуальными идеями: стабильный брак, разрезание торта, диагонализация и неразрешимость проблемы остановки, интерактивные доказательства и доказательства без знания и т. Д., И т. Д., И т. Д. Да, все это можно сделать доступным для 18-летних.

И я очень надеюсь, что вы похвалили своего ученика за то, что он был достаточно смел, чтобы задать вопрос! Им пришлось поставить себя на уступ, чтобы поднять вопрос. Это говорит о вашем стиле преподавания, что они чувствовали себя комфортно, задавая вам этот вопрос.

DW
источник
1
Польская запись почти не тратит время на обучение. Линеаризация стандартных структур, таких как деревья, также важна, учитывая, что массовое хранение часто является последовательным, а не произвольным доступом. Вы также можете сохранить его эффективно или понять, как получить его полностью или частично. Он соединяет деревья, прогулки по деревьям, встроенные структуры и опускание. Абстрактно рассказывает, как сделать кодировки Гёделя для данных. По сравнению с огромной тратой времени и энергии, представленной разбором LR и LL, и другими мусорными технологиями, я бы даже сказал, что время, потраченное на польскую запись, хорошо потрачено.
Бабу
«недостаточно значительный в информатике» - невероятно самоуверенный
Дмитрий Зайцев
1

Обратная польская нотация была хорошим инструментом в моем образовании для понимания деревьев разбора и структур данных дерева в целом. Это также полезно, если кто-либо вообще интересуется программированием на любом из языков семейства Lisp (Clojure, emacs-lisp, схема и т. Д.).

user21796
источник
Почему Лисп и Схема? Они полны скобок.
Бабу