 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
| Парадигмы программирования |
|---|
|
Стек-ориентированное программирование или программирование на основе стека - это парадигма программирования, которая полагается на модель стековой машины для передачи параметров . Языки, ориентированные на стек , работают с одним или несколькими стеками , каждый из которых может служить разным целям. Программные конструкции на других языках программирования необходимо модифицировать для использования в стек-ориентированной системе. [1] Некоторые стек-ориентированные языки работают в постфиксной или обратной польской нотации . Перед этой командой указываются все аргументы или параметры команды. Например, постфиксная запись будет написана 2, 3, multiplyвместо multiply, 2, 3( префиксили польская запись ), или 2 multiply 3( инфиксная запись ). Языки программирования Forth , RPL , PostScript , язык дизайна стиля BibTeX [2] и многие языки ассемблера соответствуют этой парадигме.
Алгоритмы на основе стека рассматривают данные, используя один фрагмент данных на вершине стека и возвращая данные обратно на вершину стека. Необходимость в операторах манипулирования стеком позволяет стеку манипулировать данными . Чтобы подчеркнуть эффект от оператора, используется комментарий, показывающий вершину стека до и после оператора. Это известно как диаграмма стекового эффекта.
Стеки
Postscript рассматривают отдельные стеки для дополнительных целей. При этом учитываются переменные, словари, процедуры, анатомия некоторых типичных процедур, управление и поток. Анализ языковой модели позволяет просто и теоретически интерпретировать выражения и программы.
Алгоритмы на основе стека [ править ]
PostScript - это пример языка на основе стека постфиксов. Пример выражения в этом языке 2 3 mul. Вычисление выражения требует понимания того, как работает ориентация стека.
Ориентацию стопки можно представить как следующую аналогию с конвейерной лентой. в конце конвейерной ленты (The вводе ), пластины помечены 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 неявно) и другие. Они становятся ключевыми в процедурах изучения.
Диаграммы эффектов стека [ править ]
Чтобы помочь понять эффект оператора, используется короткий комментарий, показывающий вершину стека до и после оператора. Если элементов несколько, верхняя часть стопки - крайняя правая. Эта нотация обычно используется в языке Forth, где комментарии заключаются в круглые скобки.
( до после )Например, описаны основные операторы стека Forth:
dup (a - aa) drop (a -) поменять местами (ab - ba) на (ab - aba) rot (abc - bca)И fibфункция ниже описана:
фиб (п - п ')Это эквивалентно предусловиям и постусловиям в логике Хоара . На оба комментария можно также ссылаться как на утверждения , не обязательно в контексте языков на основе стека.
Стеки PostScript [ править ]
PostScript и некоторые другие языки стека имеют другие отдельные стеки для других целей.
Переменные и словари [ править ]
Оценка различных выражений уже была проанализирована. Реализация переменных важна для любого языка программирования, но для стек-ориентированных языков это вызывает особую озабоченность, поскольку существует только один способ взаимодействия с данными.
Способ реализации переменных в стек-ориентированных языках, таких как PostScript, обычно включает отдельный специализированный стек, в котором хранятся словари пар ключ-значение. Чтобы создать переменную, сначала необходимо создать ключ (имя переменной), с которым затем связывается значение. В PostScript к объекту данных имени добавляется префикс a /, так /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 выдумать
- (здесь рекурсивный вызов)
стопка: 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 шт. обменять стек: / п 3 def стек: пустой (определено) п стопка: 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оператор может быть заменен пользовательским, который применяет определенный стиль к странице, вместо того, чтобы определять пользовательский оператор или повторять код для создания стиля.
См. Также [ править ]
- Список языков программирования на основе стека
- Обратная польская запись
- Возвратно-ориентированное программирование
Ссылки [ править ]
- ^ Luerweg, Т. (2015). Парадигмы программирования на основе стека. Концепции языков программирования - CoPL'15, 33.
- ^ Орен Паташник, Разработка стилей BibTeX (PDF)[ мертвая ссылка ]
