Стек-ориентированное программирование

Стек-ориентированное программирование — это парадигма программирования , которая использует стек (или несколько стеков) для манипулирования данными и/или передачи параметров. Под это описание подходят несколько языков программирования, в частности 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, расчет можно выполнить точно таким же образом и получить правильный результат. Этапы расчета показаны в таблице ниже. В каждом столбце показан элемент ввода (табличка в конце конвейера) и содержимое стопки после обработки этого ввода.

Вход	2	3	добавлять	11	у меня есть	1	добавлять
Куча	2	3 2	5	11 5	55	1 55	56

После обработки всех входных данных стек содержит 56, что является ответом.

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

Манипулирование стеком

Поскольку стек является ключевым средством манипулирования данными в стекоориентированном языке, такие языки часто предоставляют своего рода операторы манипулирования стеком. Обычно предоставляются dup, чтобы дублировать элемент на вершине стека, exch (или swap), для обмена элементами в стеке (первый становится вторым, а второй — первым), roll, для циклической перестановки элементов в стеке или части стека, pop (или drop), чтобы отбросить элемент из стека (push неявно) и другие. Они становятся ключевыми в изучении процедур.

Диаграммы эффектов стека

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

( before -- after )

Например, описаны основные операторы стека Форта:

dup  ( a -- a a )
drop ( a -- )
swap ( a b -- b a )
over ( a b -- a b a )
rot  ( a b c -- b c a )

И fib ниже описана функция:

fib  ( n -- n' )

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

Стеки PostScript

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 or not
     {
        dup 1 sub fib
        exch 2 sub fib
        add
     } if
  } def

В стеке используется рекурсивное определение. Функция числа Фибоначчи принимает один аргумент. Сначала он проверяется на 1 или 0.

Декомпозиция каждого из ключевых шагов программы, отражающая стек, предполагающая вычисление fib(4) :

                stack: 4
   dup
                stack: 4 4
   dup
                stack: 4 4 4
   1 eq
                stack: 4 4 false
   exch
                stack: 4 false 4
   0 eq
                stack: 4 false false
   or
                stack: 4 false
   not
                stack: 4 true

Поскольку выражение имеет значение true, вычисляется внутренняя процедура.

                stack: 4
   dup
                stack: 4 4
   1 sub
                stack: 4 3
   fib

(рекурсивный вызов здесь)

                stack: 4 F(3)
   exch
                stack: F(3) 4
   2 sub
                stack: F(3) 2
   fib

(рекурсивный вызов здесь)

                stack: F(3) F(2)
   add
                stack: F(3)+F(2)

что является ожидаемым результатом.

Эта процедура не использует именованные переменные, а использует исключительно стек. Именованные переменные можно создать с помощью /a exch def построить. Например, {/n exch def n n mul}

это процедура возведения в квадрат с именованной переменной n. Предполагая, что /sq {/n exch def n n mul} def и 3 sq называется, процедура sq анализируется следующим образом:

               stack: 3 /n
   exch
               stack: /n 3
   def
               stack: empty (it has been defined)
   n
               stack: 3
   n
               stack: 3 3
   mul
               stack: 9

что является ожидаемым результатом.

Контроль и поток

Поскольку существуют анонимные процедуры, управление потоком может возникнуть естественным образом. требуются три части данных Для оператора if-then-else : условие, процедура, которая должна быть выполнена, если условие истинно, и одна процедура, которая должна быть выполнена, если условие ложно. В PostScript, например,

 2 3 gt { (2 is greater than three) = } { (2 is not greater than three) = } ifelse

выполняет почти эквивалент в C:

 if (2 > 3) { printf("2 is greater than three\n"); } else { printf("2 is not greater than three\n"); }

Циклы и другие конструкции аналогичны.

Анализ языковой модели

Простая модель, представленная на стек-ориентированном языке, позволяет просто интерпретировать выражения и программы, а теоретически оценивать их гораздо быстрее, поскольку не синтаксический анализ требуется выполнять , а только лексический анализ . Способ написания таких программ облегчает их интерпретацию машинами, поэтому PostScript хорошо подходит для использования принтерами. Однако несколько искусственный способ написания программ PostScript может стать начальным барьером для понимания языков, ориентированных на стек, таких как PostScript.

Хотя возможность скрытия путем переопределения встроенных и других определений может затруднить отладку программ, а безответственное использование этой функции может привести к непредсказуемому поведению, она может значительно упростить некоторые функции. Например, при использовании PostScript showpage Оператор можно переопределить пользовательским, который применяет определенный стиль к странице, вместо того, чтобы определять собственный оператор или повторять код для создания стиля.

См. также

Ссылки

^ Люервег, Т. (2015). Парадигмы программирования на основе стека. Концепции языков программирования – CoPL'15, 33.
^ Орен Паташник, Разработка стилей BibTeX (PDF) ^{[ мертвая ссылка ]}

[1] Люервег, Т. (2015). Парадигмы программирования на основе стека. Концепции языков программирования – CoPL'15, 33.

[2] Орен Паташник, Разработка стилей BibTeX (PDF) ^{[ мертвая ссылка ]}

[1]

[2]

v т и Типы языков программирования
Level	Machine Assembly Compiled Interpreted Low-level High-level Very high-level Esoteric
Generation	First Second Third Fourth Fifth