Концепция хранимого алгоритма

(контекстно-зависимой программы)

 

Модель вычислений в императивных языках высокого уровня – это выполнение упорядоченной последовательности операторов. Каждый оператор представляет собой неделимую и целостную языковую конструкцию, описывающую процесс преобразования данных. Порядок выполнения операций внутри оператора задается путем их ранжирования и расстановки скобок, т.е указанием информационных связей между операциями. Промежуточные результаты вычислений внутри оператора не отчуждаются. Отчуждается только результат выполнения оператора. Следовательно, для абстрактной машины, непосредственно реализующий некоторый язык высокого уровня, оператор языка является командой.Действительно, рассмотрим промежуточное представление программы в виде триад, получаемое после первой фазы компиляции (синтаксического анализа). Это представление является машинно-адаптированной формой исходного кода написанного на языке высокого уровня.Программа в этом виде записывается как пронумерованная последовательность триад. Данная последовательность делится на участки. Каждый участок соответствует одному оператору программы и содержит подмножество триад, реализующее этот оператор. Очередность записи участков соответствует очередности записи операторов в программе. Каждая триада описывает выполнение некоторой операции над операндами, заданными идентификаторами или ссылками. Ссылка является номером триады, результат выполнения которой используется в качестве операнда, т.е ссылка явно задает информационную связь между операциями. При этом, результаты триад передаваемые по ссылке не отчуждаются.Так как информационный обмен между операторами опосредован и осуществляется через отчуждение результатов, то подмножество триад реализующих оператор замкнуто. Оно не имеет ссылок на триады других операторов и триады других операторов не ссылаются на триады данного подмножества. Следует отметить, что вне своего подмножества триады смысла не имеют и не могут считаться системой команд. Они безусловно обладают неделимостью, но не обладают целостностью и, следовательно, не являются командами.Любая триада имеет смысл и может быть выполнена только в определенном контексте. А именно, только после выполнения триад, результаты которых она использует и до тех триад которые используют ее результаты, т.е только в составе своего подмножества. Таким образом, целостностью и неделимостью обладает все подмножество триад в целом, а не отдельные триады.Для сравнения, выполнение любой команды в фон-неймановском или потоковом процессоре не зависит от контекста. Все команды этих процессоров обладают неделимостью и целостностью. Группа команд, реализующая оператор обладает целостностью, но не обладает неделимостью.Как известно, исходное множество операций любого алгоритмического языка изначально зафиксировано и конечно. Множество операторов, которые теоретически могут быть сконструированы с использованием данных операций — потенциально бесконечно. Так как каждая программа имеет свой набор операторов и, соответственно, свою систему команд, то можно сказать, что машина, непосредственно реализующая язык высокого уровня, не имеет фиксированной системы команд.

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

Зависимость потока команд от самого себя не единственное отличие класса архитектур с хранимым алгоритмом (контекстно-зависимой программой) от класса архитектур с хранимой программой (контекстно-свободной программой). Можно также указать еще на два фундаментальных различия данных классов.

Первое – множество программ любой архитектуры с контекстно-свободной программой счетно. Множество программ любой архитектуры с контекстно-зависимой программой имеет мощность континуума.

Второе – архитектуры с контекстно-зависимой программой в общем случае не могут быть представлены машиной Тьюринга.