Стек-ориентированное программирование — это парадигма программирования , которая опирается на стек (или несколько стеков) для манипулирования данными и/или передачи параметров. Несколько языков программирования соответствуют этому описанию, в частности Forth , RPL и PostScript . Стек-ориентированные языки программирования работают с одним или несколькими стеками , каждый из которых может служить разным целям. Конструкции программирования в других языках программирования необходимо модифицировать для использования в стек-ориентированной системе. [1] Большинство стек-ориентированных языков работают в постфиксной или обратной польской нотации . Любые аргументы или параметры для команды указываются перед этой командой. Например, постфиксная нотация будет написана 2, 3, multiplyвместо multiply, 2, 3( префиксной или польской нотации ) или 2 multiply 3( инфиксной нотации ). Языки программирования Forth , Factor , RPL , PostScript , язык проектирования в стиле BibTeX [2] и многие языки ассемблера соответствуют этой парадигме.
Алгоритмы на основе стека манипулируют данными, извлекая данные из стека и помещая их в стек. Операторы манипулирования стеком управляют тем, как стек манипулирует данными . Чтобы подчеркнуть эффект оператора, часто используется комментарий, показывающий вершину стека до и после оператора. Это известно как диаграмма эффекта стека. PostScript использует отдельные стеки для дополнительных целей, включая переменные, словари, процедуры, некоторые типичные процедуры и операторы потока управления. Анализ модели языка позволяет просто интерпретировать выражения и программы.
PostScript — пример языка, основанного на постфиксном стеке. Пример выражения на этом языке: 2 3 mul('mul' — команда для операции умножения). Вычисление выражения требует понимания того, как работает ориентация стека.
Ориентация стопки может быть представлена в виде следующей аналогии с конвейерной лентой. В конце конвейерной ленты (вход ) последовательно размещаются пластины, обозначенные 2, 3и mul. Пластина в конце конвейера ( 2) может быть взята, однако доступ к другим пластинам невозможен, пока пластина в конце не будет удалена. Пластины можно хранить только в стопке и добавлять или удалять только сверху стопки, а не из середины или снизу. Можно поставлять пустые пластины (и маркер), а пластины можно навсегда выбросить.
Возьмите пластину 2и положите ее в стопку, затем возьмите пластину 3и положите ее в стопку. Далее возьмите mulпластину. Это инструкция для выполнения. Затем возьмите две верхние пластины из стопки, перемножьте их метки ( 2и 3) и запишите результат ( 6) на новой пластине. Выбросьте две старые пластины ( 2и 3) и пластину mul, и положите новую пластину в стопку. Поскольку на конвейере больше не осталось пластин, результат вычисления ( 6) отображается на пластине сверху стопки.
Это очень простой расчет. А что, если требуется более сложный расчет, например (2 + 3) × 11 + 1? Если его сначала записать в постфиксной форме, то есть , 2 3 add 11 mul 1 addрасчет можно выполнить точно таким же образом и получить правильный результат. Этапы расчета показаны в таблице ниже. Каждый столбец показывает входной элемент (пластину в конце конвейера) и содержимое стека после обработки этого ввода.
После обработки всех входных данных стек содержит 56, что и является ответом.
Из этого можно сделать следующий вывод: язык программирования на основе стека имеет только один способ обработки данных, беря один фрагмент данных сверху стека, называемый pop ping, и помещая данные обратно сверху стека, называемый push ing. Любое выражение, которое может быть записано традиционно или на другом языке программирования, может быть записано в постфиксной (или префиксной) форме и, таким образом, может быть интерпретировано языком, ориентированным на стек.
Поскольку стек является ключевым средством для манипулирования данными в стеко-ориентированном языке, такие языки часто предоставляют своего рода операторы манипулирования стеком. Обычно предоставляются dup, для дублирования элемента на вершине стека, exch(или swap), для обмена элементами на вершине стека (первый становится вторым, а второй становится первым), roll, для циклической перестановки элементов в стеке или на части стека, pop(или drop), для удаления элемента на вершине стека (push подразумевается) и другие. Они становятся ключевыми в изучении процедур.
В качестве помощи для понимания эффекта оператора используется короткий комментарий, показывающий вершину стека до и после оператора. Верхняя часть стека находится справа, если есть несколько элементов. Эта нотация обычно используется в языке Forth, где комментарии заключаются в скобки.
( до -- после )Например, описаны основные операторы стека Forth:
дублировать (a -- aa) падение (a --) замена (ab -- ba) на (ab -- aba) гниение (abc -- bca) fibНиже описана функция :
фиб (n -- n') Это эквивалентно предусловиям и постусловиям в логике Хоара . Оба комментария также могут упоминаться как утверждения , хотя и не обязательно в контексте языков на основе стека.
PostScript и некоторые другие стековые языки имеют другие отдельные стеки для других целей.
Оценка различных выражений уже была проанализирована. Реализация переменных важна для любого языка программирования, но для языков, ориентированных на стек, это вызывает особую озабоченность, поскольку существует только один способ взаимодействия с данными.
Способ реализации переменных в стековых языках, таких как PostScript, обычно включает в себя отдельный специализированный стек, который содержит словари пар ключ-значение . Чтобы создать переменную, сначала необходимо создать ключ (имя переменной), с которым затем связывается значение. В PostScript объект данных имени имеет префикс /, поэтому /xобъект данных имени может быть связан, например, с числом 42. defineКоманда — def, поэтому
/x 42 def
ассоциирует имя xс номером 42в словаре наверху стека. Существует разница между /xи x– первый является объектом данных, представляющим имя, и xобозначает то, что определено в /x.
Процедура в языке программирования на основе стека рассматривается как объект данных в своем собственном праве. В PostScript процедуры обозначаются между {и }.
Например, в синтаксисе PostScript
{ dup mul }
представляет собой анонимную процедуру копирования того, что находится наверху стека, а затем умножения результата – процедуру возведения в квадрат.
Поскольку процедуры рассматриваются как простые объекты данных, можно определить имена с процедурами. При их извлечении они выполняются напрямую.
Словари предоставляют средства управления областью действия, а также хранения определений.
Поскольку объекты данных хранятся в самом верхнем словаре, естественным образом возникает неожиданная возможность: при поиске определения в словаре проверяется самый верхний словарь, затем следующий и т. д. Если определена процедура, имеющая то же имя, что и другая, уже определенная в другом словаре, будет вызвана локальная.
Процедуры часто принимают аргументы. Они обрабатываются процедурой очень специфическим образом, отличным от других языков программирования.
Чтобы проверить программу чисел Фибоначчи в PostScript:
/fib { dup dup 1 eq exch 0 eq или нет { dup 1 sub fib exch 2 sub fib add } if } def Рекурсивное определение используется в стеке. Функция числа Фибоначчи принимает один аргумент. Сначала он проверяется на 1 или 0.
Разложение каждого из ключевых шагов программы, отражающее стек, предполагающее вычисление fib(4) :
Стек: 4 дубликат Стек: 4 4 дубликат Стек: 4 4 4 1 экв. стек: 4 4 ложно обмен стек: 4 ложно 4 0 экв. стек: 4 ложно ложно или стек: 4 ложных нет стек: 4 правда
Поскольку выражение оценивается как истинное, внутренняя процедура оценивается.
Стек: 4 дубликат Стек: 4 4 1 субтитр Стек: 4 3 выдумка
Стек: 4 Ф(3) обмен стек: F(3) 4 2 суб стек: F(3) 2 выдумка
стек: Ф(3) Ф(2) добавлять стек: Ф(3)+Ф(2)
что является ожидаемым результатом.
Эта процедура не использует именованные переменные, а только стек. Именованные переменные могут быть созданы с помощью конструкции /a exch def. Например,{/n exch def n n mul}
представляет собой процедуру возведения в квадрат с именованной переменной n. Предполагая, что /sq {/n exch def n n mul} defи 3 sqвызывается, процедура sqанализируется следующим образом:
стек: 3 /н обмен стек: /n 3 определение стек: пустой (он был определен) н Стек: 3 н стек: 3 3 муль Стек: 9
что является ожидаемым результатом.
Поскольку существуют анонимные процедуры, управление потоком может возникнуть естественным образом. Для оператора if-then-else требуются три элемента данных : условие, процедура, которая должна быть выполнена, если условие истинно, и одна, которая должна быть выполнена, если условие ложно. Например, в PostScript:
2 3 gt { (2 больше трех) = } { (2 не больше трех) = } ifelse выполняет почти эквивалент на языке C:
if ( 2 > 3 ) { printf ( "2 больше трех \n " ); } else { printf ( "2 не больше трех \n " ); } Циклы и другие конструкции аналогичны.
Простая модель, предоставляемая в стекоориентированном языке, позволяет легко интерпретировать выражения и программы и теоретически оценивать их гораздо быстрее, поскольку не требуется проводить синтаксический анализ , а требуется лексический анализ . Способ написания таких программ облегчает их интерпретацию машинами, поэтому PostScript хорошо подходит для использования принтерами. Однако несколько искусственный способ написания программ PostScript может стать первоначальным барьером для понимания стекоориентированных языков, таких как PostScript.
Хотя возможность затенения путем переопределения встроенных и других определений может затруднить отладку программ, а безответственное использование этой функции может привести к непредсказуемому поведению, она может значительно упростить некоторые функции. Например, при использовании PostScript show pageоператор может быть переопределен пользовательским, который применяет определенный стиль к странице, вместо того, чтобы определять пользовательский оператор или повторять код для генерации стиля.