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

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

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

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

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

Диаграммы эффектов стека [ править ]

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

( до после )

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

dup    (a — aa) 
 drop   (a —) 
 поменять местами   (ab — ba) 
 на   (ab — aba) 
 rot    (abc — bca)

И 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   или   нет 
      { 
         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 верно

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

стек: 4
    обман
                 стек: 4 4
    1 суб
                 стек: 4 3
    выдумка

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

стопка: 4 Ф(3)
    обмен
                 стек: F(3) 4
    2 суб
                 стек: F(3) 2
    выдумка

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

стек: F(3) F(2)
    добавлять
                 стек: 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 анализируется следующим образом:

стек: 3 /n 
     обмен 
                 стек: /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 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