Крупноблочная схема программ: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Крупноблочная схема программ''' (''Large-block program schemata'') - операторная ''схема п...)
 
Нет описания правки
 
(не показано 5 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Крупноблочная схема программ''' (''Large-block program schemata'') -
'''Крупноблочная схема программ''' (''[[Large-block program schemata]]'')
операторная ''схема программ'', которая рассматривает моделируемую программу в виде совокупности структурных операторов, обрабатывающих структурные значения совокупности переменных. Введена в литературу В.Н.Касьяновым в 1980 г.
операторная ''[[схема программ]]'', которая рассматривает моделируемую программу в виде совокупности структурных операторов, обрабатывающих структурные значения совокупности переменных. Введена в литературу В.Н.Касьяновым в 1980 г.


Базис <math>\Sigma</math>, над которым строятся схемы, содержит символы переменных, операций, доступов, предикатов выполнимости, выбора и операндов: обязательных и необязательных входов и выходов. Крупноблочная схема <math>\alpha</math> --- это тройка  
Базис <math>\,\Sigma</math>, над которым строятся схемы, содержит символы переменных, операций, доступов, предикатов выполнимости, выбора и операндов: обязательных и необязательных входов и выходов. Крупноблочная схема <math>\,\alpha</math> это тройка  


<math>(G_{\alpha}, R_{\alpha},\Omega_{\alpha}),</math>  
<math>\,(G_{\alpha}, R_{\alpha},\Omega_{\alpha}),</math>  


в которой <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|700px]]


См. также ''Неинтерпретированные схемы, Стандартные схемы, Схема программ, Схема с косвенной адресацией, Схема с распределенной памятью, Схемы Мартынюка.''
Крупноблочная модель программ вместе с концепцией крупноблочного моделирования одних схем другими дает единую позицию для комплексного исследования оптимизирующих преобразований программ со  структурами данных и действий и их применения в системах конструирования программ. Существенными свойствами, отличающими класс крупноблочных схем от других моделей программ, являются его универсальность в смысле широты описания класса последовательных программ и способов их оптимизации, а также его полнота — возможность построения по любой крупноблочной схеме (в частности, программе) и любому ее укрупнению операторов и переменных такой другой крупноблочной схемы, которая моделирует исходную при заданном ее укрупнении.
 
==См. также==
* ''[[Неинтерпретированные схемы]],''
* ''[[Стандартные схемы]],''
* ''[[Схема программ]],''
* ''[[Схема с косвенной адресацией]],''
* ''[[Схема с распределенной памятью]],''
* ''[[Схемы Мартынюка]].''
==Литература==
==Литература==
[Касьянов/88],
* Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
 
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
 


[Касьянов/86]
[[Категория:Теория схем программ]]

Текущая версия от 11:26, 18 апреля 2011

Крупноблочная схема программ (Large-block program schemata) — операторная схема программ, которая рассматривает моделируемую программу в виде совокупности структурных операторов, обрабатывающих структурные значения совокупности переменных. Введена в литературу В.Н.Касьяновым в 1980 г.

Базис [math]\displaystyle{ \,\Sigma }[/math], над которым строятся схемы, содержит символы переменных, операций, доступов, предикатов выполнимости, выбора и операндов: обязательных и необязательных входов и выходов. Крупноблочная схема [math]\displaystyle{ \,\alpha }[/math] — это тройка

[math]\displaystyle{ \,(G_{\alpha}, R_{\alpha},\Omega_{\alpha}), }[/math]

в которой [math]\displaystyle{ \,G_{\alpha} }[/math]управляющий граф (уграф), [math]\displaystyle{ \,R_{\alpha} }[/math]раскраска операндов операторов из [math]\displaystyle{ \,G_{\alpha}, }[/math] сопоставляющая с каждым операндом некоторую переменную, а [math]\displaystyle{ \,\Omega_{\alpha} }[/math] — множество интерпретаций.

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

Каждая интерпретация [math]\displaystyle{ \,I\in\Omega_{\alpha} }[/math] — это совокупность, состоящая из области интерпретации [math]\displaystyle{ \,D_I }[/math] и двух функций. Одна из них ставит в соответствие элементам базиса [math]\displaystyle{ \,\Sigma }[/math] элементы [math]\displaystyle{ \,D_I }[/math] и функции, заданные на [math]\displaystyle{ \,D^r_I }[/math], а вторая — выделяет используемые и неиспользуемые части аргументов интерпретирующих функций при вычислении указанных частей их результатов. Предполагается, что [math]\displaystyle{ \,D_I }[/math] может содержать как простые значения, так и составные. Каждое из составных значений — это множество упорядоченных пар элементов из [math]\displaystyle{ \,D_I }[/math], попарно различающихся по первым компонентам и называемых именами. Таким образом, одно значение может образовывать нетривиальную часть другого значения с некоторым адресом, представляющим собой последовательность имен.

Оператор (в общем случае) — это совокупность, состоящая из слова применимости — выражения, описывающего условия применимости оператора и построенного из обязательных входов и операций, слова выбора — выражения, построенного из входов и операций и описывающего правила выбора той из исходящих дуг, по которой будет осуществлен переход, а также из множества обязательных и необязательных присваиваний, описывающих правила перевычисления состояния памяти. Обязательное присваивание имеет вид [math]\displaystyle{ \,a:=F }[/math], где [math]\displaystyle{ \,a }[/math] — получатель (обязательный выход), а [math]\displaystyle{ \,F }[/math] — источник, представляющий собой выражение, построенное из входов и операций и описывающее правило вычисления значения, которое будет присвоено переменной [math]\displaystyle{ \,R(a) }[/math]. Необязательное присваивание имеет вид

[math]\displaystyle{ g(F_1,\ldots, F_r, F, a), }[/math]

где [math]\displaystyle{ \,g }[/math] — символ доступа, [math]\displaystyle{ \,a }[/math] — получатель (необязательный выход), [math]\displaystyle{ \,F }[/math] — источник, [math]\displaystyle{ F_1,\ldots,F_r }[/math] — ключи, представляющие собой выражения, построенные из входов и операций. В зависимости от интерпретации [math]\displaystyle{ \,g }[/math] и текущих значений ключей определены используемые и неиспользуемые части переменной [math]\displaystyle{ \,x=R(a) }[/math]. Необязательное присваивание сохраняет значения используемой части [math]\displaystyle{ \,x }[/math] и перевычисляет неиспользуемую часть [math]\displaystyle{ \,x }[/math], размещая в ней используемые части значения результата источника.

Large-block program schemata.png

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

См. также

Литература

  • Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.