- Обратная польская нотация, или постфиксная нотация, размещает операторы после операндов, что устраняет необходимость использования скобок.
- Она была разработана на основе польской префиксной нотации, созданной Яном Лукасевичем для упрощения пропозициональной логики.
- Эта технология получила огромную популярность благодаря компании Hewlett-Packard и была реализована в таких культовых калькуляторах, как HP-9100A и HP-35.
- В вычислительной технике это реализуется с помощью стеков, являющихся основополагающими в таких системах, как Unix, и в языках программирования, ориентированных на стек.
Вы, наверное, задавались вопросом, как работали старые научные калькуляторы или почему некоторые языки программирования, кажется, записывают математические вычисления наоборот. Хотя нас еще со школы учили, что символы сложения и вычитания всегда располагаются посередине чисел, существует удивительный мир, называемый обратной польской записью, который противоречит всему, что мы знаем.
Эта система не является современным изобретением; она берет свое начало в чистой логике и стремлении сделать алгебраические выражения более эффективными. В отличие от того, что мы обычно делаем, здесь порядок множителей меняет способ их записи, позволяя нам полностью игнорировать скобки и упростить ввод данных в компьютерные системы.
Происхождение: От Яна Лукасевича к информатике
Всё началось в 1924 году благодаря блестящему польскому математику, логику и философу Яну Лукасевичу . Он поставил перед собой задачу упростить пропозициональную логику и создал так называемую префиксную нотацию (или польскую нотацию), где оператор ставится перед операндами. Например, если мы хотим сложить 3 и 4, вместо 3 + 4 мы напишем + 3 4.
Хотя поначалу эта идея казалась любопытной для логиков и философов и даже упоминалась Алонзо Чёрчем в его текстах по математической логике, в конечном итоге она проникла в мир информатики. Фактически, синтаксис языка программирования LISP основан именно на этой префиксной модели, демонстрируя, что то, что зародилось в логике, в итоге стало мощным инструментом для программирования.
Что же такое обратная польская нотация?
В то время как в префиксной записи оператор располагается перед операндом, в обратной польской записи (также известной как RPN или постфиксная запись) операторы располагаются после операндов. Таким образом, наша обычная сумма 2 и 5 становится 2 5 +.
Самое мощное преимущество этой системы заключается в том, что, пока количество операндов в операторах фиксировано, скобки можно опустить . Возьмем, к примеру, операцию 5 * (12 + 4). В традиционной системе скобки необходимы для принудительного сложения; однако в обратной польской записи это просто записывается как 5 12 4 + * . Это гораздо чище и проще для машины.
Золотой век Hewlett-Packard и калькуляторов.
В середине 60-х годов австралийский учёный Чарльз Леонард Хэмблин усовершенствовал алгоритмы для реализации этой системы в электронных устройствах. Именно тогда компания Hewlett-Packard решила инвестировать в неё, выпустив в 1968 году HP-9100A — настольный калькулятор, изменивший правила игры. Вскоре после этого появился легендарный HP-35 — первый карманный научный калькулятор, благодаря которому обратная польская запись (RPN) стала доступна тысячам инженеров и студентов в период с 1972 по 1975 год.
Использование этих машин требовало немного дополнительных умственных усилий для интерпретации результата, но было гораздо эффективнее с точки зрения количества нажатий клавиш . Вместо того чтобы набирать длинное уравнение и нажимать кнопку «равно», вы вводили числа и операторы, которые обрабатывались мгновенно, что значительно повышало эффективность рабочего процесса.
Техническая реализация: трубы и переходы.
С точки зрения программирования, обратная польская запись (RPN) замечательна тем, что её чрезвычайно легко реализовать, используя структуру данных, называемую стеком . Система хранит числа в стеке и, как только появляется оператор, извлекает последнее введенное значение, выполняет вычисление и помещает результат обратно в стек.
Именно благодаря этой эффективности, хотя мы больше не видим так много физических калькуляторов, использующих эту систему, обратная польская запись (RPN) остается актуальной в современных технологиях. Она широко используется в стеково-ориентированных языках программирования и в операционных системах, основанных на конвейерах или потоке данных, классическим примером чего является ее присутствие в среде Unix.
Интересные факты о Лукасевиче и логике
Ян Лукасевич оставил нам не только этот способ записи математики. Он был пионером в многозначной логике и модальной логике. Он даже занимался интеллектуальными задачами, такими как парадокс лжеца (фраза «это ложно»). Его решение было блестящим: он утверждал, что логические принципы применимы только к объектам, которые могут быть значениями переменных, а поскольку эта противоречивая фраза не может быть значением переменной, она просто находится за пределами логики и не может быть проанализирована с помощью традиционных логических методов.
Это увлекательное путешествие от ума польского логика до схем калькуляторов HP и ядра Unix показывает нам, как альтернативный способ организации информации может оптимизировать обработку данных. Устраняя необходимость в скобках и опираясь на использование стеков, обратная польская нотация остается невидимой, но фундаментальной опорой в архитектуре многих современных компьютерных систем.