4625
правок
Крупноблочная схема программ: различия между версиями
Материал из WikiGrapp
Крупноблочная схема программ (посмотреть исходный код)
Версия от 12:11, 17 ноября 2009
, 17 ноября 2009нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Крупноблочная схема программ''' (''[[Large-block program schemata]]'') - | '''Крупноблочная схема программ''' (''[[Large-block program schemata]]'') - | ||
операторная ''схема программ'', которая рассматривает моделируемую программу в виде совокупности структурных операторов, обрабатывающих структурные значения совокупности переменных. Введена в литературу В.Н.Касьяновым в 1980 г. | операторная ''[[схема программ]]'', которая рассматривает моделируемую программу в виде совокупности структурных операторов, обрабатывающих структурные значения совокупности переменных. Введена в литературу В.Н.Касьяновым в 1980 г. | ||
Базис <math>\Sigma</math>, над которым строятся схемы, содержит символы переменных, операций, доступов, предикатов выполнимости, выбора и операндов: обязательных и необязательных входов и выходов. Крупноблочная схема <math>\alpha</math> --- это тройка | Базис <math>\Sigma</math>, над которым строятся схемы, содержит символы переменных, операций, доступов, предикатов выполнимости, выбора и операндов: обязательных и необязательных входов и выходов. Крупноблочная схема <math>\alpha</math> --- это тройка | ||
| Строка 7: | Строка 7: | ||
в которой <math>G_{\alpha}</math> --- | в которой <math>G_{\alpha}</math> --- | ||
''[[управляющий граф]]'' (''уграф''), <math>R_{\alpha}</math> --- раскраска операндов операторов из <math>G_{\alpha},</math> сопоставляющая с каждым операндом некоторую переменную, а <math>\Omega_{\alpha}</math> --- множество интерпретаций. | ''[[управляющий граф]]'' (''[[уграф]]''), <math>R_{\alpha}</math> --- [[раскраска]] операндов операторов из <math>G_{\alpha},</math> сопоставляющая с каждым операндом некоторую переменную, а <math>\Omega_{\alpha}</math> --- множество интерпретаций. | ||
Переменные, поставленные в соответствие входам операторов, называются их ''аргументами'', а выходам --- ''результатами''. Аргументы и результаты разделяются на ''обязательные'' и ''необязательные'' в зависимости от того, являются ли таковыми операнды, с которыми они сопоставлены. | Переменные, поставленные в соответствие входам операторов, называются их ''[[аргумент оператора|аргументами]]'', а выходам --- ''[[результат оператора|результатами]]''. Аргументы и результаты разделяются на ''[[обязательный аргумент|обязательные]]'' и ''[[необязательный аргумент|необязательные]]'' в зависимости от того, являются ли таковыми операнды, с которыми они сопоставлены. | ||
Каждая интерпретация <math>I\in\Omega_{\alpha}</math> --- это совокупность, состоящая из ''области интерпретации'' <math>D_I</math> и двух функций. Одна из них ставит в соответствие элементам базиса | Каждая интерпретация <math>I\in\Omega_{\alpha}</math> --- это совокупность, состоящая из ''области интерпретации'' <math>D_I</math> и двух функций. Одна из них ставит в соответствие элементам базиса | ||
<math>\Sigma</math> элементы <math>D_I</math> и функции, заданные на <math>D^r_I</math>, а вторая --- выделяет используемые и неиспользуемые части аргументов интерпретирующих функций при вычислении указанных частей их результатов. Предполагается, что <math>D_I</math> может содержать как простые значения, так и составные. Каждое из составных значений --- это множество упорядоченных пар элементов из <math>D_I</math>, попарно различающихся по первым компонентам и называемых именами. Таким образом, одно значение может образовывать нетривиальную часть другого значения с некоторым адресом, представляющим собой последовательность имен. | <math>\Sigma</math> элементы <math>D_I</math> и функции, заданные на <math>D^r_I</math>, а вторая --- выделяет используемые и неиспользуемые части аргументов интерпретирующих функций при вычислении указанных частей их результатов. Предполагается, что <math>D_I</math> может содержать как простые значения, так и составные. Каждое из составных значений --- это множество упорядоченных пар элементов из <math>D_I</math>, попарно различающихся по первым компонентам и называемых именами. Таким образом, одно значение может образовывать нетривиальную часть другого значения с некоторым адресом, представляющим собой последовательность имен. | ||
Оператор (в общем случае) --- это совокупность, состоящая из ''слова применимости'' --- выражения, описывающего условия применимости оператора и построенного из обязательных входов и операций, ''слова выбора'' --- выражения, построенного из входов и операций и описывающего правила выбора той из исходящих дуг, по которой будет осуществлен переход, а также из множества обязательных и необязательных присваиваний, описывающих правила перевычисления состояния памяти. ''Обязательное присваивание'' имеет вид <math>a:=F</math>, где <math>a</math> --- получатель (обязательный выход), а <math>F</math> --- источник, представляющий собой выражение, построенное из входов и операций и описывающее правило вычисления значения, которое будет присвоено переменной <math>R(a)</math>. ''Необязательное присваивание'' имеет вид | Оператор (в общем случае) --- это совокупность, состоящая из ''[[слово применимости|слова применимости]]'' --- выражения, описывающего условия применимости оператора и построенного из обязательных входов и операций, ''[[слово выбора|слова выбора]]'' --- выражения, построенного из входов и операций и описывающего правила выбора той из исходящих дуг, по которой будет осуществлен переход, а также из множества обязательных и необязательных присваиваний, описывающих правила перевычисления состояния памяти. ''Обязательное присваивание'' имеет вид <math>a:=F</math>, где <math>a</math> --- получатель (обязательный выход), а <math>F</math> --- источник, представляющий собой выражение, построенное из входов и операций и описывающее правило вычисления значения, которое будет присвоено переменной <math>R(a)</math>. ''Необязательное присваивание'' имеет вид | ||
<math>g(F_1,\ldots, F_r, F, a),</math> | <math>g(F_1,\ldots, F_r, F, a),</math> | ||
где <math>g</math> --- символ доступа, <math>a</math> --- получатель (необязательный выход), <math>F</math> --- источник, <math>F_1,\ldots,F_r</math> --- ключи, представляющие собой выражения, построенные из входов и операций. В зависимости от интерпретации <math>g</math> и текущих значений ключей определены используемые и неиспользуемые части переменной <math>x=R(a)</math>. Необязательное присваивание сохраняет значения используемой части <math>x</math> и перевычисляет неиспользуемую часть <math>x</math>, размещая в ней используемые части значения результата источника. | где <math>g</math> --- символ доступа, <math>a</math> --- получатель (необязательный выход), <math>F</math> --- источник, <math>F_1,\ldots,F_r</math> --- ключи, представляющие собой выражения, построенные из входов и операций. В зависимости от интерпретации <math>g</math> и текущих значений ключей определены используемые и неиспользуемые части переменной <math>x=R(a)</math>. Необязательное присваивание сохраняет значения используемой части <math>x</math> и перевычисляет неиспользуемую часть <math>x</math>, размещая в ней используемые части значения результата источника. | ||
[[Файл:Large-block program schemata.png|500px]] | |||
Крупноблочная модель программ вместе с концепцией крупноблочного моделирования одних схем другими дает единую позицию для комплексного исследования оптимизирующих преобразований программ со структурами данных и действий и их применения в системах конструирования программ. Существенными свойствами, отличающими класс крупноблочных схем от других моделей программ, являются его универсальность в смысле широты описания класса последовательных программ и способов их оптимизации, а также его полнота --- возможность построения по любой крупноблочной схеме (в частности, программе) и любому ее укрупнению операторов и переменных такой другой крупноблочной схемы, которая моделирует исходную при заданном ее укрупнении. | Крупноблочная модель программ вместе с концепцией крупноблочного моделирования одних схем другими дает единую позицию для комплексного исследования оптимизирующих преобразований программ со структурами данных и действий и их применения в системах конструирования программ. Существенными свойствами, отличающими класс крупноблочных схем от других моделей программ, являются его универсальность в смысле широты описания класса последовательных программ и способов их оптимизации, а также его полнота --- возможность построения по любой крупноблочной схеме (в частности, программе) и любому ее укрупнению операторов и переменных такой другой крупноблочной схемы, которая моделирует исходную при заданном ее укрупнении. | ||
