О самой концепции стека

Перейти вниз

О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 8:58 pm

ДВА ЗАБЛУЖДЕНИЯ

Это пожалуй два самых больших FORTH-заблуждения:

1. Стек данных - то, что отличает FORTH, как язык, от большинства других языков, причем, отличает в лучшую сторону.
2. Стек данных очень удобен для вычислений.

Для того, чтобы их развеять надо задать себе вопрос: а откуда взялась идея стека данных?


Последний раз редактировалось: Gudleifr (Пт Июл 28, 2017 11:15 am), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:03 pm

СТЕК - СТАТИЧЕСКАЯ СТРУКТУРА МЕЖПРОЦЕДУРНОГО ОБЩЕНИЯ

Допустим, у нас имеется два куска кода: А и Б. Природа и уровень "кода" нам безразличны: подпрограммы, процессы, приложения, роботы, даже, люди-работники... Нам нужно обеспечить передачу какой-то информации от А к Б. Есть два очевидных способа такой передачи:

- Создать некий "почтовый ящик" В - на время "разговора" А с Б. Назовем такой выделяемый для обмена объект динамическим.
- Иметь некоторую общую "доску объявлений" Г , к которой имеют доступ все куски кода. Такой объект, выделенный для обмена заранее, назовем статическим.

Посмотрим, что получается (очень приблизительно и, заодно, отмечая, что где-то надо хранить информацию о самом факте взаимодействия А с Б и о том, что делать потом):

Вид кода (А и Б)Динамическая информация (В)Статическая информация (Г)Информация о порядке исполнения
Программы UNIXпромежуточный текстовый файлпеременные окруженияпамять родительского процесса
Процедуры языка Спараметры, передаваемые процедуре при вызовеглобальные переменныестек возвратов
Люди-работникиустные инструкциируководящие документыраспоряжения начальника
Слова FORTHзначения на стекезначения, запомненные в других словахстек возвратов

Можно сделать два замечания. Даже, если для обмена организуется динамический объект В, для его реализации необходим некий статический объект-оболочка - Г'. И стек - это как раз пример очень удачного объекта-оболочки - Г'. В него очень удобно добавлять информацию порциями (и так же извлекать). Сам по себе он статический, но каждая процедура может считывать из него куски-кадры (В), оставленные процедурами-предшественниками, и оставлять свои кадры - для связи с потомками. И стек гарантирует, что то что кадр не будет извлечен раньше, чем все, что было положено после него. Другими словами, Б может спокойно снимать со стека все, что положил туда А, но обычно не интересуется тем, что там есть еще (т.е. информацией, адресованной А). Второе замечание, которое может сделать программист, глядя на таблицу выше, состоит в том, что обычно удается сэкономить и разместить эти три компоненты информации в двух структурах. Например, язык C использует для хранения параметров (В) и информации о том, что делать дальше, одно и то же место - стек возвратов. Люди тоже экономят, используя много для чего "канал передачи" устной информации.
***

Каким же должен быть стек для того, чтобы обеспечить общение А и Б? Таким, чтобы на нем можно было легко распознать отдельные кадры информации В? Так обстоит дело во многих языках программирования. В них каждый кадр имеет жесткую привязку к конкретной процедуре (иначе возвраты не реализовать). В FORTH от этого отказались, к конкретной процедуре относится только кадр стека возвратов. Сколько чего слово берет со стека данных и что туда кладет, оно решает само. Значит, одним стеком не обойтись, если только мы не напишем FORTH, слова которого не будут общаться иначе, чем через значения других слов (переменных). Такое, в принципе, возможно - работали же так первые BASIC.
По крайней мере, создавая свой FORTH "с нуля" не стоит начинать с реализации стека, он не относится к коду первой необходимости.
***

Стек FORTH имеет как бы три ипостаси:

1. с точки зрения отдельно взятого слова: стек, это - массив данных, причем слово должно заранее знать, на каком месте массива, какие данные находятся. Вспомогательного средства обычных языков - осмысленных имен параметров здесь нет. С другой стороны, не нужно придумывать именам всяким вспомогательным переменным, живущим только в течение времени выполнения пары-тройки операторов.
2. с точки зрения последовательности выполнения: т.к. мы разделили стеки данных и возвратов, FORTH снимает с себя всякую ответственность за целостность стека данных, именно как стека. Т.е. своевременное заполнение его данными и уборка мусора - целиком на совести программиста. Ч.Мур сам признается, что выбор политики очистки стека - использование слов, удаляющих со стека считанные данные ("разрушающих"), или записывающих свой результат после них ("неразрушающих") - был сделан им достаточно произвольно.
3. с точки зрения вычислительных возможностей: т.к. стек данных был нами искусственно отделен от стека возвратов и т.к. стек является "природной" структурой для многих удачных алгоритмов, то некоторые трюки с использованием стека в обычных языках, такие, как рекурсия или локальные переменные работают и в нем.


Последний раз редактировалось: Gudleifr (Пт Июл 28, 2017 11:16 am), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:05 pm

СКОЛЬКО СТЕКОВ В ЯЗЫКЕ C?

С точки зрения реализации, разумеется, один. А с точки зрения теории вычислений? Создадим какую-либо глобальную переменную, например X. Теперь определим новую функцию, а в ней локальную переменную X. Теперь, когда мы вызываем эту функцию, наша глобальная переменная закрывается локальной, а когда выходим - опять становится видимой. А если подобная функция вызывается рекурсивно? Или подобные функции вызывают друг друга? Очевидно, ситуация лучше всего описывается нашим любимым стеком - на вершине текущая локальная переменная, которая только одна и видима, а на самом дне стека - глобальная переменная Х, ждущая своего часа.
Т.о. мы видим, что формально, в программе на C может быть организовано много стеков, которых программист просто не замечает. (О них вспоминают только при оценке правильности программы). Заботится об этих виртуальных стеках (размещая в одном-единственном реально существующем) сам компилятор.
FORTH же подобным фокусам приходится "учить".
***

А сколько нужно стеков? Все зависит от решаемой задачи. Заранее говорить, что FORTH положен один стек данных - глупо. Во-первых, как только FORTH начинает работать с каким-то новым видом данных, удобнее создавать новые виды стеков: вещественных чисел, Windows-регистров и т.п. Альтернатива - использование стека каким-то образом специально стрктурированного, т.е. более сложного, а, значит, и более медленного. Во-вторых, создания стека (как, впрочем, и других структур данных) требуют многие часто используемые алгоритмы.
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:08 pm

А УДОБЕН ЛИ СТЕК ДЛЯ ВЫЧИСЛЕНИЙ?

По большому счету, есть только один способ что-то вычислить - записывая промежуточные результаты на бумажке. Регистры, локальные переменные, стек и электронная таблица (ЭЛТ) - это лишь варианты этой "бумажки". У каждого из них есть свои достоинства и недостатки.

- Регистры очень хорошо ложатся на структуру процессора, но их чертовски мало. А если процессор еще пытается (подобно x86) их по-разному трактовать, то совсем весело.
- Локальные переменные - это способ придумывания промежуточным результатам каких-то осмысленных имен. С ними связаны две проблемы - алгебраическая и программистская. Алгебраическая состоит в том, что имена нужны, в общем-то, только до тех пор, пока задача не приведена к стандартному виду, после этого даже завзятые алгебраисты переходят к векторам и матрицам, где вместо имен - номера позиций в нормальной форме записи выражения. Программистская проблема заключается в том, что как только возникает именованная область в памяти программ, теоретики сразу начинают выяснять ее область видимости. Каких только турусов тут не понавозводили. Язык C никогда не имел бы такого успеха, если бы не отмел заранее все эти разносолы. Преимущество же локальных переменных - возможность производить вычисления не только математику, но даже, например, бухгалтеру.
- ЭЛТ - честная визуализация пресловутой "бумажки". Кроме возможности наглядно разместить записи на листе (заголовки, данные, результаты, итоги), позволяют и выполнение некоторых агрегатных ф-ий (т.е. работающих с целым столбцом, строкой или матрицей значений). Недостаток очевиден - этот абак только для ручного счета.

Наконец, стек. Чем он хуже перечисленного?
- По сравнению с регистрами, стек реализуется регистрами не прямо, а косвенно (в обоих смыслах этого слова). Хотя, на хороших процессорах (типа Motorolla), достаточно удобно.
- Стек хуже, чем локальные переменные, тем, что при незнании программистом азов арифметики и алгебры, последний постоянно испытывает потребность залезть "вглубь", к чему стек не предрасположен. Если отсутствует ясная и понятная дисциплина использования стека (каковая в FORTH, все-таки, сложилась), то к этой проблеме добавляется и проблема запоминания программистом "где что лежит".
- Ну с ЭЛТ сравнивать совсем просто. ЭЛТ круче тем, что двумерная.

Чем стек лучше?
- Стек лучше регистров тем, что практически неисчерпаем. Более того, он решает проблемы запоминания чего-то пока неактуального, с последующем его извлечением, "когда подойдет очередь". Недаром, все разработчики очень быстро пришли к выводу необходимости поддерживать его аппаратно (инженеры IBM тормозили до последнего) для "унутренних нужд".
- Стек "лучше" локальных переменных тем, что требует от программиста осмысления решаемой вычислительной задачи. "Сначала попробуем перемножить это на то, а затем, если не сойдется, разделим это на это" (как любят рассуждать двоечники) здесь не прокатит. Самый же большой плюс стека в том, что не нужно изобретать дурацкие имена для всякой дребедени. Использовать имена типа "переменная по смещению N"? Двойная глупость - и смысл именования пропадает, и имя вводить приходится. А если вычисления такие сложные, что приходится весь кадр стека туда-сюда по несколько раз лопатить? Значит, вы не понимаете задачи и, может даже, нужны вам не локальные имена стековых ячеек "на всю глубину", а один операнд - ссылка на нужную структуру данных. Вспомним напоследок, что без стека не было бы и локальных переменных.
- Может ли стек быть лучше ЭЛТ? Как ни странно, да. Он сам себя чистит и сам себя сдвигает, по мере надобности. В стеке всегда к вашим услугам новый кадр - чистый листок для вычислений.

Опять же, уже говорил, что стековая организация данных является родной для многих задач (и вычисления с промежуточными результатами - одна из них), например, рекурсивного перебора, обработки прерываний и т.д. Так, что очень часто задача ложится на стек сама, без усилий программиста.

Т.о. мы видим, что стек - структура достаточно средняя (еще бы, ведь она универсальная). Так задумаемся, стоит ли нам при решении сложной вычислительной задачи изобретать какой-то способ перетасовки стека, либо отвести в памяти место под структуру, наиболее подходящую для нашей задачи?
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:13 pm

КАК РЕАЛИЗОВАТЬ СТЕК?

Обычно программист на каком-нибудь C пишет просто: массив из, допустим, сотни целых чисел. Казалось бы, все правильно. А, нет. Что мы знаем о стеке данных? Что его заполняет и чистит не сам FORTH, и даже не программа, а команды пользователя. Следовательно, никаких гарантий, что указатель стека не вылетит за пределы отведенного массива нет и быть не может. Проверять допустимость каждой операции со стеком? Слишком накладно, особенно, если учесть, что пользователь вполне может переопределить слова работы со стеком, выкинув все наши проверки. Значит, надо проверять состояние стека только в каких-то ключевых точках (Ч.Мур рекомендует - в начале каждого Цикла Управления FORTH). Но ведь, в этом случае возможно, что какое-нибудь особо вредное слово успеет нагадить. Правильно. Именно поэтому надо окружить наш стек-массив зонами безопасности, которые не слишком чувствительны к порче, например, буферами вывода. В общем случае можно добавить по паре-другой пустых ячеек к обоим концам массива. Есть вероятность вылезти и за их пределы? А вы умножьте ее на вероятность того, что Вы сделаете такую глупую ошибку именно в тот момент, когда вылет программы особенно критичен. Должно получиться не очень много.
***

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

Какого размера буфера достаточно для стека? (Конечно, в наше время экономить на стеке вынуждены, разве что, разработчики аппаратуры). Опыт подсказывает, что стек растет в зависимости от сложности программ логарифмически, т.е. заведомо более медленно. Оцените, насколько вы любите конструкции типов:

ВЫЧИСЛИТЬ ОТЛОЖИТЬ-РЕЗУЛЬТАТ ВЫЧИСЛИТЬ-ЧТО-ТО-ДРУГОЕ ВСПОМНИТЬ-СТАРЫЙ-РЕЗУЛЬТАТ

или

ФУНКЦИЯ(ПАРАМЕТР-1, ПАРАМЕТР-2,.. ПАРАМЕТР-N)

и прикиньте. Обычно хватает пары-тройки десятков ячеек.

Я отвожу больше по одной простой причине: будучи очень ленивым программистом, люблю писать рекурсивные программы. Впрочем, и тут здравый смысл подсказывает, что перебор дерева решений глубиной более 20-30 - вещь достаточно редкая.
Кто-то, быть может, любит размещать в стеке данных какие-то большие массивы, но, наверное, будет правильно для каждого вида больших и сложных структур данных организовывать в памяти свои специальные хранилища.
***

От чего зависит, где размещать стек? Рассмотрим на примере процессоров xхх-86, которые у нас в IBM-персоналках. Они славятся тем, что рассчитаны на аппаратную поддержку только одного стека. Кому его отдать - стеку данных или стеку возвратов? Если Вы используете подпрограммный шитый код, то по необходимости аппаратный стек придется отдать под возвраты. Если Вы хотите активно вызывать функции операционной системы, например Win-API, то удобнее в аппаратном стеке хранить данные. Есть и другие резоны, которые сами всплывут по мере проектирования... Тут главное помнить, что способ использования аппаратного стека диктуется структурой Вашего FORTH, а не наоборот.
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:23 pm

ПРИМЕР ИСПОЛЬЗОВАНИЯ СТЕКА ПО НАЗНАЧЕНИЮ

Рассмотрю простую задачу, в которой стек используется не потому, что ничего другого нет, а потому, что он для подобных задач и предназначен: всем известная задача о перевозке через реку.

ЗАДАЧАЛОДОЧНИКИПАССАЖИРЫВМЕСТИМОСТЬ ЛОДКИЗАПРЕТЫ
ВОЛК, КОЗА И КАПУСТАмужикволк, коза и капустамужик и один пассажирволк в отсутствие мужика съедает козу, коза - капусту
ТРИ МИССИОНЕРА И ТРИ ЛЮДОЕДАвсе-2 человекаесли на одном берегу людоедов оказывается больше, чем миссионеров, последних съедают
ТРИ РЫЦАРЯ И ТРИ ОРУЖЕНОСЦАвсе-2 человекаоруженосец боится остаться с другими рыцарями без своего
HELP THE SAILпапа, мама, коп2 сына, 2 дочери, бандит2 человекапапа без мамы обижает дочерей, мама - сыновей, бандит без копа - всех

В чем особенность данного класса задач? Согласно книге С.Осуга "Обработка знаний":

1. число состояний конечно, одно из состояний принимается за начальное и одно или несколько состояний (сюда не входит начальное) определяются как искомые (терминальные);
2. заданы правила перехода между группами состояний;
3. для каждого состояния заранее заданы определенные условия допутимости (оценки) состояний.

Я попытался изобрести универсальный решатель таких задач - вводишь в него правила задачи - и он путем перебора пытается получить решение задачи.
Причем тут стек?
При том, что для задач, решаемых перебором (по научному - рекурсивным поиском), он и предназначен. Промежуточные состояния накапливаем в стеке - недопустимые удаляем (согласно п.3), небезнадежные - используем для построения новых состояний (согласно п.2). Если не брать расширенные условия подобных задач (наличие острова для пересадки), то для изображения любого состояния достаточно одного числа - битовой шкалы, где 1 в каком-либо разряде будет означать, что соответствующий объект на левом берегу (0 - на правом). Положение лодки тоже, очевидно, надо учитывать. Да, еще хорошо бы сразу отбрасывать ранее рассмотренные состояния (иначе решение зациклится). Получается следующее:

: АНАЛИЗ ДОПУСТИМО? IF НОВЫЙ? IF НОВЫЙ! ЗАМЕНА THEN THEN ;
: РЕШЕНИЕ ЗАДАЧА BEGIN ПОБЕДА? IF EXIT THEN АНАЛИЗ AGAIN ;

где:

ЗАДАЧА ( -- состояние-0 ) -- инициализация
ДОПУСТИМО? ( состояние -- состояние, -1 | 0) -- отбрасывание негодных состояний
НОВЫЙ? ( состояние -- состояние, -1 | 0) -- рассматривалось ли ранее это состояние?
НОВЫЙ! ( состояние -- состояние) -- запоминаем состояние как рассмотренное
ЗАМЕНА ( состояние -- состояние-n, ..., состояние-1) -- строим состояния, получаемые из текущего
ПОБЕДА? ( состояние -- состояние, 0 | -1) -- подходит ли состояние под условия победы?

Не правда ли, удобно, что мне не пришлось отводить где-то место под стек, если у меня есть стандартный? Полное решение у меня заняло четыре стандартных 1k-байтных блока: первый для описания больших битовых массивов, по которым решатель будет проверять, допустимо ли состояние и не встречалось ли оно ранее; второй - для кой-каких операций с состояниями (вывод, перегон лодки); третий отвел для собственно правил задачи (при переходе от задаче к задаче нужно поменять только один этот блок) - какими буквами обозначаются персонажи, как проверить, допустима ли ситуация, кто помещается в лодку; четвертый - описанный выше решатель. Для более аккуратного решения, точнее, его более симпатичного отображения, допускаю добавление в программу пятого блока (например, для представления стека не одним стековым значением, а парой - для хранения ссылки на родительское состояние). Но не более.
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:24 pm

ПРИМЕР ИСПОЛЬЗОВАНИЯ СТЕКА НЕ ПО НАЗНАЧЕНИЮ

Одна моя знакомая компания "фортеров" озаботилась компактной записью стековых операций: например "3/12321" означает, если не ошибаюсь, то же, что и " >R 2DUP R> ROT ROT SWAP ", только путем неявных вызовов PICK . Нужен ли такой язык? (На настоящий момент он уже настолько развит, что в нем можно решать подобные задачи "не опускаясь" до использования обычных FORTH-слов).
Совсем не нужен! Хотя бы потому, что использование подобных конструкций, свидетельствует о крайне низкой культуре фортописания. Как только у вас в программе начинают появляться такие монстры, значит, надо срочно пересмотреть структуру своей программы!
***

Я, кстати, предложил этим поклонникам "расширения операторами стековых манипуляторов" решить приведенную выше задачу (мол, пусть красиво опишут на своем языке арифметику состояний), но они начали "гнать дурочку".
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:26 pm

ВСЕ-ТАКИ, FORTH СТЕК НУЖЕН!

Но не "стек данных", а стек "буферизации ПОТОКА" - "стек ввода"! Ведь, в этом и состоит идея FORTH - выполнять команды пользователя по мере их ввода. И стек - самый удобный способ их накопления. То, что "стек ПОТОКА" и "стек данных" обычно одно и то же, только удачный финт реализации.
Разница между двумя стеками (данных и ввода) трудноуловима. Можно ориентироваться так: если для обработки того, что говорит пользователь, нужен стек - это стек ввода. Если же мы используем стек вместо передачи параметров вызова функции или локальных переменных, то это стек данных.
Можно привести примеры:

1. вычисления в стеке ввода/данных - см. пример выше;
2. вычисления "где-то рядом" - при выполнении WORD и FIND через стек данных передаются адрес слов и флаг, а само слово - через область словаря (тоже, ведь, стек);
3. вычисления в стеке возвратов - реализация конструкции DO ... LOOP;
4. вычисления в специальном стеке - инфиксная арифметика по Муру;
5. вычисления вообще без стека - пример Мура для обработки таблиц.
***

Следствие этого "тонкого" различия - избыточность усилий по оптимизации стека данных. Стеку ввода они не нужны - ввод штука медленная. А стек данных - не нужен сам.
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:29 pm

ЕЩЕ НЕМНОГО ПРОБЛЕМ

Начнем с удачного решения.
Оказывается, "структуризация" стека данных, это не просто, а очень просто. Достаточно организовать в нем что-то, навроде (взято из DOS-версии FOBOS, откуда взялось название ARENE, не помню):

N.( Стековые списки ARENE: связь+данные)
VARIABLE ARENE
\ New: Stack <= Arene; Arene <- Stack; Stack <= N(0);
: ARENE-NEW ( N->SA,N*0) SP@ ARENE @ >R ARENE ! R> SWAP
0 DO 0 LOOP ;
\ Free: Stack <- Arene; Arene <= Stack;
: ARENE-FREE ( SA,...->) ARENE @ SP! ARENE ! ;
: (ARENE) ( N->SA) 2* ARENE @ + ;
: ARENE@ ( N->W) (ARENE) S@ ; : ARENE! ( W,N->) (ARENE) S! ;
\ Link: Stack <= Arene[N1]; Arene[N1] <- Stack; Stack <= N2(0);
: ARENE-LINK ( N1,N2->SA,N1*0) >R >R R@ ARENE@ SP@ R> ARENE!
R> 0 DO 0 LOOP ;
\ List: For(; SA; CFA(SA), SA <- Stack[SA-2]);
: ARENE-LIST ( CFA,SA->) BEGIN ?DUP WHILE 2DUP
S@ SWAP EXECUTE ( W->) 2- S@ REPEAT DROP ;

Чем-то это напоминает связь словарных статей через поле связи. Такая простейшая конструкция позволяет:

- очищать стек разом, а не постепенным вычерпыванием. Например, отметить положение вершины стека перед началом решения задаче о перевозке через реку, а потом разом удалить всю информацию о промежуточных удачных/неудачных решениях. Или вызывать таким образом функции в C-стиле - с неопределенным числом параметров;
- размещать в стеке буфера произвольного размера. В простых одноразовых задачах нас не будет даже беспокоить, будут ли они когда-либо освобождены...
- работать с выделенными буферами, как с массивами (или другими структурами данных). Это, например пригодилось бы уже при реализации слова NUMBER - ведь, как известно, там постоянно приходится "крутить" на стеке достаточно много данных.

Но, если "немного улучшить" обычные FORTH-структуры так просто и соблазнительно, а их взаимное проникновение часто столь велико (например, ЗНАЧЕНИЕ часто хранится частично на СТЕКЕ, а частично - в СЛОВАРЕ), то возникает очень филосовский вопрос:
Должны ли, в конечном итоге, FORTH-структуры - ПОТОК, ЗНАЧЕНИЕ, СТЕК и СЛОВАРЬ - быть изоморфными (т.е. устроенными сходным образом и потенциально содержащими одну и ту же информацию) или ортогональныими (вынужденными разделять информацию на части, каждую из которых способна усвоить тоько одна из структур)?
Например, это может разрешить вечный спор фортеров: что лучше, подгружать в СЛОВАРЬ заранее откомпилированные фрагменты-оверлеи или, наоборот, хранить большинство кода в текстовой форме и компилировать его только по мере надобности?
Впрочем, возможно, ответ прост - эти структуры данных просто не существуют. Точнее, существуют только в виде процедур обращения к ним, и, даже, не к ним, а к другим процедурам, "думающим", что обращаются к даннм. Не структуры, а названия типов интерфейсов.
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Чт Июл 27, 2017 9:54 pm

СТЕК И WIN API

Классификации вызовов WIN API

А. Возвращаемые значения. Эта классификация дана нам в ощущениях:
- Простое. Имеется в виду ситуация, когда функция возвращает нам в точности то, что мы просили. В дикой природе практически не встречается, почти всегда есть необходимость проверки происшествия ошибки.
- Зависимое от результата. Уже упоминавшиеся выше случаи проверки результата на ошибочность. Вплоть до вызова дополнительной функции - анализатора ошибки. Другой пример - функция MessageBox, которая возвращает различные значения в зависимости от параметров ее вызова.
- Заполнение буфера. Очень неприятный случай, требующий отслеживания состояния заполненности и готовности достаточно сложно устроенных областей памяти. Особенно, если при первом вызове буфер должен быть частично заполнен вручную.
- Подтвержденное имя. Например, регистрация оконного класса. Немного проще предыдущего, т.к. обычно сам буфер, связанный с именем, больше никому не нужен.

Б. Тип вызова. Здесь уже возможны различные варианты реализации:
- Вызов функции. Ни к чему никого не обязывает.
- Запрос ресурса. Обязана иметь пару - освобождение ресурса. Альтернатива - написание охватывающего слова, содержащего внутри DOER-тело. Последняя конструкция особенно необходима, если требуется обработка неудачного выделения ресурса. С другой стороны, освобождение ресурса может быть физически отделено от его выделения сложными условными и/или управляемыми пользователем конструкциями.
- Регистрация простой call-back функции. Последняя вызывается в результате перебора, сортировки, чтения/записи и т.д. Конечно, хотелось объединить и сам call-back и процедуру его использования в одну конструкцию, но это еще никому не удалось.
- Регистрация обработчика оконных сообщений. Здесь сложность состоит в в трех проблемах. Во-первых, отношение "окно - функция окна" не взаимно однозначно: может быть несколько окон с одной функцией, да одно окно может "играть" своей функцией. Во-вторых, подразумевается наличие у приложения цикла обработки сообщений, который очень редко, но все же требуется модифицировать. В-третьих, в зависимости от вида окна, используются различные варианты функций "по умолчанию".

В. Типы параметров:
- Стековое значение. Сложности с восстановлением стека, подобные следующему варианту существуют только для одной функции - wsprintf. Кроме того, часто возможна ситуация вызова дополнительной функции для получения одного из параметров.
- Стековая структура. Явно непригодна для вызовов, требующих сохранения возвращаемых данных (А3, часто Б2). Кроме того, сложности с восстановлением стека и сохранением порядка полей в структуре и параметров на стеке. Универсальный набор слов - сохранения стека, заполнители полей (задом наперед), помещения адеса на стек, восстановления стека.
- Выделенный однородный буфер. Может применятся там же (А3, Б2), где и однородный буфер в словаре. Плюс, возможность использовать массив буферов.
- Указатель на словарь (строка). Естественный способ передачи строк - причем, и в одноразовом, и в многоразовом вариантах.
- Указатель на словарь (однородный буфер). Если лень выделять маленький часто используемый и один на все случаи буфер в памяти.
- Буфер, имеющий ассемблер. Под ассемблером здесь подразумевается процедура заполнения сложно устроенного буфера значениями, хранящимися во внутренних структурах программы (по возможности избегая заполнения поля за полем и/или огульного копированя структур из памяти - в идеале поля должны заполнять себя сами).
- Буфер последовательного заполнения. Здесь создается обычный набор слов: адрес выделенного однородного буфера, переменная-указатель, ее обнулятель, запись в буфер элемента, запись в буфер разделителя, запись завершителя.

Г. Тип ассемблеров, генерирующих блоки параметров:
- Переопределяемые. Перед каждым новым вызовом функции они переопределяются, по необходимости, так, как надо.
- Восстанавливаемые. Призваны уменьшить необходимость переопределения. После вызова функции приводятся к наиболее часто встречающемуся виду.
- Декораторы. Подразумевается проведение некоторого дополнительного анализа состояния системы.
***

Рассмотрим, например, функцию MessageBox (все слова условные):

: MESSAGE
OP-CODE HEADER PHRASE HWIND MESSAGEBOX CALL RES? ;

С точки зрения вызова, случай почти простейший - А2, Б1.
Параметры HEADER и HWIND имеют очень малые области значения (домены) - HEADER обычно выдает указатель на строку имени приложения, а HWIND имеет значение либо 0, либо указатель на текущее окно (не совсем понятно, есть ли в этом хоть какой-либо смысл, но, кажется, второе предпочтительнее).
Т.о. HEADER логично смотрится как восстанавливаемый параметр (Г2), который может быть переопределен (очень редко) перед вызовов MESSAGEBOX, но тут же восстанавливаемый в стандартное значение - имя приложения.
HWIND - явно декоратор (Г3). Он проверяет, существует ли окно, к которому стоит привязать нашу функцию и возвращает его handle, иначе - 0.
PHRASE - типичный переопределяемый параметр (Г1), т.к. заранее предугадать его значение трудно. Еще точнее - это наверняка должен быть единственный параметр нашего слова MESSAGE.
OP-CODE - пример еще одного восстанавливаемого параметра (Г2). Стандартное значение - MB_OK. Другие варианты должны устанавливаться подобно авторским ремаркам в театральных пьесах:

Люк: [Возмущенно.] Я же ничего так не вижу!
Оби Ван: [Поучает.] Используй силу!

Т.к. результат выполнения MESSAGEBOX сильно зависит от OP-CODE, то слово, его переопределяющее, должно заодно переопределять и RES? (значение по умолчанию - DROP). Например, в случае закрытия окна редактора (пример 33):

Файл изменялся?
Нет: Вернуть 1 (разрешение стереть содержимое).
Иначе:
Вызвать MESSAGEBOX с MB_YESNOCANCEL
Результат - IDYES? Сохранить файл, вернуть 1.
Результат - IDCANCEL? Вернуть 0.
Другой результат (IDNO)? Вернуть 1.

Не вникая глубоко в смысл происходящего:

MAKE OP-CODE ИЗМЕНЕНИЯ? IF
MAKE RES DUP IDNO = IF ( ЧТОБЫ ПОДОШЛО ПО СМЫСЛУ)
DROP СОХРАНИТЬ 1 ELSE IDCANCEL = IF 0 ELSE 1 THEN THEN
MAKE RES? DROP ( ВНИМАНИЕ! ВОЗМОЖНА ПУТАНИЦА СО СТЕКОМ) ;AND
MB_YESNOCANCEL ELSE MB_OK THEN MAKE OP-CODE MB_OK ;
MAKE PHRASE Z" ЩАС СОТРУ!" ;
***

Пример сложных параметров - RegisterСlass и CreateWindowEx:

: CLASS ( -- ..., a)
ICON CLASS-NAME 0 ( МЕНЮ ДЛЯ НАС ЗДЕСЬ НЕДОСТУПНО)
BACKGROUND CURSOR ICON APPINST EXT-CLASS WIN-PROCEDURE @
CLASS-STYLE 48 ( РАЗМЕР СТРУКТУРЫ) SP@ ;
: REGISTER-CLASS ( -- f)
SP@ >R CLASS REGISTERCLASS CALL R> SWAP >R SP! R> ;
: CREATE-WINDOW ( -- wh)
SP@ >R WIN-LPR APPINST MENU WIN-DAD FRAME
WIN-STYLE HEADER CLASS-NAME WIN-STYLE+
CREATEWINDOW CALL R> SWAP >R SP! R> ;

CLASS-NAME - пример А4-В4, CLASS - В2, HEADER - В4, остальные - В1. Возвращаемое значение CREATE-WINDOW - Б2.
Понятно,что связки "SP@ >R" и "R> SWAP >R SP! R>" надо бы заменить на что-то более читабельно-осмысленное.
***

Вид, конечно, у этих конструкций мерзейший, но ничего, кроме MAKE-ов, вложенных в другие МАКЕ-и (может быть, с определением для читабельности промежуточных слов) придумать не удается (пока?).
Остается открытой и проблема Б2 (выделение ресурса). Здесь конструкции распадаются на два подкласса

1. СЛОВА-ОБОЛОЧКИ (Б2.1):

: РАБОТА-С-РЕСУРСОМ
ВЫДЕЛЕНИЕ-РЕСУРСА IF DOER-ОБРАБОТЧИК ELSE САМ-ДУРАК THEN ОСВОБОЖДЕНИЕ-РЕСУРСА ;

например, для пар BeginPaint - EndPaint или FILE+ - FILE- ;

2. пары отдельных слов (Б2.2) ВЫДЕЛЕНИЕ-РЕСУРСА - ОСВОБОЖДЕНИЕ-РЕСУРСА, которые используются в разных местах дерева обработчика сообщения (в первую очередь - создание/удаление окон и controls, причем, если выделение ресурса требуется только один раз, то освобождение - по крайней мере, дважды - в конце работы с ресурсом и в конце работы охватывающего объекта).
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Пт Июл 28, 2017 8:58 am

ЛОКАЛЬНЫЕ И ПОДОБНЫЕ ИМ ПЕРЕМЕННЫЕ

На кошачьем форуме некто пишет:: BOX // X1, Y1, X2, Y2, COLOR
LOC[
QUAN X1 QUAN X2 QUAN Y1 QUAN Y2 QUAN COLOR
]LOC
TO COLOR TO Y2 TO X2 TO Y1 TO X1
X1 Y1 X2 X1 - COLOR HLINE
X1 Y1 Y2 Y1 - COLOR VLINE
X1 Y2 X2 X1 - COLOR HLINE
X2 Y1 Y2 Y1 - COLOR VLINE
;

Да... Зачем писать на FORTH, если нас напрягает работа со стеком и так не хватает "нормальных переменных"? И, все равно, программа как была набором повторяющихся почти один-в-один строк, так и осталась?
И как связана проблема перетасовки стека с применением локальных переменных? Стек можно тасовать и в глобальных. Видимо, локальность здесь добавлена только для того, чтобы это было больше похоже на фокус.

Нее... Так не интересно.
Во-первых, в чем проблема? В том, что переменные попадают на стек не в том порядке, что используются?

1. А не в том ли они порядке?
X1 Y1 X2 Y2 надо преобразовать в (применение столь дурацких процедур рисования линий оставляем на совести нашего клоуна):

X1 Y1 DX
X1 Y1 DY
X1 Y2 DX
X2 Y1 DY

(пардон, D здесь означает не double, а delta).

Думаю, если вы немножко умеете писать на FORTH, вы вполне можете написать (для наглядности без COLOR):

: 4DUP ( X1,Y1,DX,DY -- X1,Y1,DX,DY,X1,Y1,DX,DY) 2OVER 2OVER ;
: Y+X ( X1,Y1,DX,DY -- X1,Y2,DX) SWAP >R + R> ;
: X+Y ( X1,Y1,DX,DY -- X2,Y1,DY) >R 0 D+ R> ;
: BOX 2OVER D- 4DUP DROP HLINE 4DUP NIP VLINE 4DUP Y+X HLINE X+Y VLINE ;

И, даже, добавить >R и R@ для COLOR...

Проще прямо написать "то, что надо", а не вспоминать, через какую жо... тьфу, стек, были определены LOC.

2. Более интересен вариант, когда данные для наших процедур будут подаваться не просто в неудобном порядке, но в произвольном. Тогда забавнее всего будет оформить слова СТАРТ, ВПРАВО, ВНИЗ, ВЛЕВО, ВВЕРХ через DOES> (с полями под координаты и смещения), а при вводе конкретных цифр - их модифицировать через >BODY .

3. В случае же усложнения задачи будет иметь смысл создать специальное слово - итератор, при каждом обращении выдающее следующую точку для рисования.

Но, ладно, вам ведь интереснее слушать про то, что "локальные переменные опять доказали свою нужность"...
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Gudleifr в Сб Ноя 11, 2017 11:26 am

СТЕК И КОДОВЫЕ СЛОВА

На кошачьем форуме не-скажу-кто выложил такое вот универсальное слово для "инкапсуляции прерывания".

;; CALLINT ( DI SI ВР SP BX DX СХ АХ n --> DI SI ВР SP BX DX СХ АХ )
;; Загрузить ряд регистров, вызвать прерывание n и возвратить
;; полученный ряд регистров.
AWORD CALLINT,"CALLINT",0
swapx
pop ax
mov [.n],al
mov [.rp],bp
popa
db 0xCD ; int
.n rb 1
pusha
db 0xBD ; mov bp,
.rp rw 1
swapx
AEND

Конечно, такой стековый комментарий страшен сам по себе. А представьте себе, что это слово включено в контекст, где параметры будут активно участвовать в вычислениях. Там, ведь, запредельное количество SWAP-ов и ROT-ов просто превратит код в "игру 15"...
Можно ли как-то с этим бороться, если, формат слова, вроде, диктуется железом и потребностями?

1. Ну, во-первых, если Вы посмотрите на любое INT-API, вы увидите, что используются не все возможные комбинации регистров, но только некоторые, причем, осмысленные. В AX обычно втюхивают код операции, в DX - данные, в BX - номер устройства... Кроме того, сложность обращений обычно возрастает путем добавления к уже устоявшемуся набору регистров одного - следующего. Т.е. чаще всего имеем набор int(AX), int(AX,DX), int(AX,DX,BX).., а не случайную комбинацию регистров. Да и возвращается результат обычно только в регистре AX...
А раз есть система, значит можно упростить.

2. Для примера, посмотрим, как это делается в языке C. Там можно пользоваться двумя свойствами компилятора - стек чистит программа, вызвавшая функцию, а значение ф-ии всегда возвращается в регистре AX. Таким образом, один и тот же код может выполнять вызовы и int(AX) и int(AX,DX,BX)... Ему плевать, кто и что напихал в стек, ведь чистить-то не ему. Главное, чтобы порядок соблюдался.

Неужели, FORTH хуже? Даже не создавая специальных C-подобных слов, можно тупо раскидать точки входа для разных типов вызовов INTi. В псевдокодах:

INT3: MOV CX,BX; POP BX;
INT2: MOV DX,BX; POP BX;
INT1: MOV AX,BX;
MOV BX,CX; INT-XXX; MOV BX,AX;

Выпендреж с BX-CX у меня вклинился, т.к. в BX я храню вершину стека. Дальше будет хуже, свободных регистров (у меня) больше нет, и придется куролесить.

3. Конечно, такими простейшими средствами можно ограничиться, если INT используется очень ограниченно (а так оно и бывает в 99% случаев). Но, если нам нужны все возможные варианты, то пора вспомнить, про то, что операция INT - это всего два байта. И проще втюхивать их куда надо, чем городить вокруг них универсальный огород. И мы изначально пошли не тем путем. Надо искать не возможность "вызвать прерывание", а возможность "сохранить-восстановить регистры". И здесь надо вспомнить об API-оболочках из Win-примера выше. Разница только в том, что здесь это будут не слова-заполнители, а макросы, работающие на этапе компиляции.
И не нужно никаких "полных ассемблеров". Нужно, по сути, только два слова: CODE и END-CODE . Остальное сделает "запятая". Создать набор кубиков-макросов, из которых можно собрать любые переконфигураторы регистров в любом частном случае - не проблема. И наплодить столько простых INT-слов, сколько надо...

4. Является ли избыточность и неуклюжесть слова CALLINT ошибками? Если мы увидим это слово внутри работающего кода, это не страшно. Ну писал человек на коленке, ну было ему так проще... Все равно, если эта хрень и породит критические ошибки, они, скорее всего, не успеют выявиться за то короткое время, что отведено для жизни обычной FORTH-программе.
Но, если, подобное нам преподносится как универсальное решение в рамках полностью готовой FORTH-системы, за это надо бить.
avatar
Gudleifr
Admin

Сообщения : 932
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: О самой концепции стека

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу

- Похожие темы

 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения