Стек и очередь - две плохих парадигмы и что можно с этим сделать

[escalibur]

Существуют две структуры данных, которые известны любому программисту и которые настолько считаются аксиомами, что никто не пытается даже проанализировать, а так ли они нужны, есть ли от них польза и не превышает ли вред от них эту самую пользу.
Очередь
В первую очередь обсудим очередь. В чём смысл очереди? Очередь - это буфер. А когда нам нужен буфер? Когда мы не успеваем обработать входящие события в темпе их поступления.
В связи с вышесказанным возникает один единственный вопрос: а зачем? Ответ в том, что мы надеемся, что что-то случится и вдруг система позволит нам обработать события.
Сначала разберемся с первым пунктом. Что должно случиться с системой, что она вдруг перестанет тормозить и начнет переваривать данные быстрее? Скорее всего, просто закончится какой-то ресурсоёмкий процесс и освободит ресурсы. А что, если этого не произойдет? Что делать с данными? Известно что: либо мы просто их сбрасываем, либо вся система просто виснет от нехватки ресурсов.

Дак вот, есть два вопроса:

1. А почему нельзя отбрасывать данные сразу, если мы знаем, что у нас на их обработку нет ресурсов? То есть почему нельзя сделать очередь из одного элемента?
2. Либо обратный вопрос. Почему мы питаем иллюзии и не снабжаем систему необходимым количеством ресурсов, чтобы обрабатывать данные в темпе поступления?

Ответы на эти вопросы, собственно, очевидны. Мы просто не умеем проектировать программно-аппаратные комплексы. Потому как если бы мы их умели проектировать, то мы бы знали сколько у нас входных данных, темп их поступления, сколько нам нужно на их обработку и, соответственно, могли бы высчитать реальную потребность в ресурсах. Но современное состояние средств и методологий разработки ИКТ, за исключением части технологических систем (и то далеко не всех), не позволяет нам сделать объективные расчеты потребности в ресурсах.

А закрываем мы эти недочёты всяческими буферами, в частности, в виде очередей. В результате, мы имеем бомбу, заложенную в основание здания ещё на уровне котлована, потому что эти костыли служат источником разнообразных презанятнейших и трудно уловимых проблем с надежностью, безопасностью и просто качеством работы.
Но, продолжим, впереди у нас моя самая "любимая" структура - стек!
Стек
Вот уж точно, как говорил в своё время Хоар про Null, что это ошибка на миллиард долларов, так то же самое можно сказать и про стек.

Это одна из проблемнейших структур, используемых в ИКТ и крайне желательно её максимальное избегание в практике создания аппаратного и программного обеспечения, вплоть до полного искоренения.
Итак, что, собственно, за проблема со стеком? Да ровно та же, что и с очередью. Стеки принципиально невозможно упорядочить. Как только появится человек, который точно предскажет сколько памяти нужно стеку любой произвольной программы, я лично извинюсь и напишу огромную статью о том, что я был неправ и попрошу прощения.

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

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

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

1. Рекурсия, реализуемая в виде раскрытия стекового алгоритма в цикл с блоком данных, изменяемых в процессе выполнения цикла.
2. Если же нужно передавать параметры, то вы организуете систему микропрограмм с обменом сообщениями. А про обмен сообщениями мы выходим на очереди, которые были описаны в первой части статьи. Если уж так хочется стек, то уж явно туда не стоит запихивать десятки и сотни килобайт объектов, а нужно для этого выделять память нормально, на куче.

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

Разумеется, часть возможностей будет, возможно, потеряна, но это, если рассмотреть детально - не факт.
BlockOut
В 1995-м году мною с моим одногруппником были сформулированы принципы построения операционной системы, которая исключала обе этих парадигмы.Принципы были следующими:

1. Программное обеспечение - сети взаимодействующих процессов.
2. Взаимодействие процессов осуществляется путём обмена сообщениями.
3. Сеть взаимодействующих процессов организована следующим образом: источниками первичных сообщений в такой сети являются только события от внешнего мира, поставляемые оборудованием, конечными потребителями сообщений являются только устройства, которые производят действия во внешнем мире. То есть сеть начинается в реальном мире и заканчивается в нем.
4. Процессы не могут обладать приоритетами. Приоритетами могут обладать только сети процессов.
5. Сеть никогда не буферизирует сообщения. Программно-аппаратный комплекс должен быть организован так, чтобы успевать обрабатывать сообщения в темпе их поступления из внешнего мира.
6. Аппаратный комплекс представляет собой сеть вычислительных узлов, связанных каналами связи.
7. Каждый узел имеет "стоимость", зависящую от его вычислительной мощности, объема памяти, загруженности и весового коэффициента, учитывающего затраты на его создание и поддержание.
8. Каждый канал связи имеет "стоимость", зависящую от его пропускной способности, загруженности и весового коэффициента, учитывающего затраты на его создание и поддержание.
9. Операционная система обеспечивает запуск процессов в ответ на поступающие сообщения и маршрутизацию сообщений.
10. Операционная система обеспечивает распределение процессов и сообщений по вычислительным узлам, оптимизируя функцию f(cpu,mem) на сетевой топологии с учётом стоимости передачи кода процесса и сообщений на узел.
11. С учётом построения системы, всегда можно точно вычислить необходимое количество памяти для процесса. Необходимое количество времени счёта можно точно вычислить на основе анализа алгоритма.

Процессор BIND
В рамках преподавательской деятельности, вместе со студентами в своё время принял участие в конкурсе IEEE эмуляторов CPU. Был разработан бесстековый процессор общего назначения гарвардской архитектуры по системе команд похожий на ранние ARMы. Так же в CPU была инкорпорирована забытая идея транспьютеров и процессор был оснащён 16 8-битными каналами приема-передачи.

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

Данный текст является, скорее, компиляцией мыслей, которые имели место быть на протяжении всей карьеры в ИТ, чтобы, так сказать, свести всё в одно место.