Преобразование императивной программы в дерево

[bsivko]

Добрый день.

Интересуюсь у всезнающего All в двух базовых математических вопросах программирования.

I.

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

Можно ли любую программу такого рода преобразовать к виду, в котором одна инструкция не может повторяться дважды?

Например в такую программу А:


Первый шаг в логической цепочке. Любую императивную программу можно представить в виде структурированной согласно теореме Бёма — Якопини. Можно ли зная, что алгоритм гарантированно завершается, преобразовать программу к виду А (например разорвав циклы в фиксированное количество инструкций)?

II.

Как называется метод-способ, когда программа вида A преобразуется в программу вида B:



(т.е. когда граф выполнения представляет собой дерево, точнее, слабо-связный ацикличный ориентированный граф)

?

Точно знаю, что способ-подход есть, и он как-то называется, но не могу найти концов..

Ссылки всячески приветствуются, в т.ч. на буржуйском. Достаточно только направления куда копать (;

[arseniiv]

bsivko в сообщении #586164 писал(а):

например разорвав циклы в фиксированное количество инструкций

Такое никак не выйдет. Без циклов остаться не суждено.

Зачем это?

[Alexu007]

bsivko в сообщении #586164 писал(а):

например разорвав циклы в фиксированное количество инструкций?

Рекурсия. Функция с адресом исходного узла ищет соседние узлы и вызывает сама себя с адресом соседнего узла и т.д. Циклы не нужны.

[bsivko]

arseniiv в сообщении #586194 писал(а):

Такое никак не выйдет. Без циклов остаться не суждено.

В общем случае представляется следующее.

Если программа имеет конечное число входных состояний, то для каждого из них можно прописать "if smth then return f(smth)", в результате получаем программу типа B с конечным числом узлов. Но от такой программы толку ноль, все равно что в ленту тьюринга преобразовывать.

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

Alexu007 в сообщении #586234 писал(а):

Рекурсия. Функция с адресом исходного узла ищет соседние узлы и вызывает сама себя с адресом соседнего узла и т.д. Циклы не нужны.

ищет соседние узлы - это цикл, перебирающий узлы? имеется ввиду виртуальная машина на одном цикле?

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

arseniiv в сообщении #586194 писал(а):

Зачем это?

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

Как А, так и B можно автоматически конвертнуть в серию аппаратных элементов (OR, AND, NOT), или например задать в ПЛИС. Также их удобно выполнять параллельно.

[arseniiv]

bsivko в сообщении #586314 писал(а):

Если программа имеет конечное число входных состояний, то для каждого из них можно прописать "if smth then return f(smth)", в результате получаем программу типа B с конечным числом узлов. Но от такой программы толку ноль, все равно что в ленту тьюринга преобразовывать.

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

А по-другому никак.

-- Пн июн 18, 2012 21:13:28 --

К тому же, обычно программы принимают на вход достаточно много информации. И если перебирать каждое возможное значение «входного слова», такая программа займёт так много места ($O(c^\text{длина входа})$), что такую программу будет использовать, написать (компилятору) и хранить нереально.

-- Пн июн 18, 2012 21:15:21 --

А если входных состояний сколь угодно большое число, то вообще ничего не выйдет.