Staged multi-result supercompilation: filtering before producing

В случае применения суперкомпиляции в области решения задач, многорезультатная суперкомпиляция позволяет обнаруживать наилучшие решения благодаря тому, что порождается некоторое множество возможных остаточных графов конфигураций, которое затем фильтруется в соответствии с некоторыми критериями. К сожалению, пространство поиска при этом может получаться весьма обширным. Однако, мы показываем, что можно значительно уменьшить объем поиска разложив процесс многорезультатной суперкомпиляции в композицию из двух стадий. На первой стадии порождается компактное представление множества остаточных графов, которое получается в результате задержки некоторых операций по построению графов. Эти операции выполняются на второй стадии, когда компактное представление интерпретируется, в результате чего и генерируется множество графов. Основная идея предлагаемого подхода состоит в том, что вместо фильтрации множества графов можно выполнять анализ и чистку его компактного представления. Во многих случаях, представляющих практический интерес (таких, как отбор графов минимального размера или отбрасывание графов, содержащих ненадежные конфигурации) чистка может быть выполнена за линейное время.