r2 - 16 Jun 2005 - 14:27:24 - Luba ParmyonovaYou are here: TWiki >  Refaldevel Web > FuturePlans > SuperComp

Суперкомпиляция

Используются материалы, опубликованные на http://www.refal.org/doc/turchin/dag/dag.html#CONTENTS
и статья
Valentin F. Turchin. The Algorithm of Generalization in the Supercompiler. Partial Evaluation and Mixed Computation, IFIP 1988

При прогонке предполагается существование некоторой метамашины, главная задача которой - уметь имитировать поведение рефал-машины. Метамашина "управляет" рефал-машиной, "заставляя" ее делать то, для чего она не предназначалась, а имено, выполнять вычисления над выражениями со свободными переменными. Такое вычисление может быть названо метавычислением, его результат - не значение функции, а граф состояний и переходов рефал-машины, который описывает шаг вычисления для получения этого значения.

Суперкомпиляция, в отличие от прогонки, описывающей один шаг рефал-машины, может включать в себя несколько шагов.

Если при прогонке рассматривается активная вершина C (вершина, описывающая вызов функции), суперкомпилятор анализирует ее предшественников, и в зависимости от предшественника C' принимает одно из трех решений:

  1. сводит вершину C к вершине C' с помощью подстановки, что возможно только в случае, когда C вкладывается в C';
  2. строит обобщенную вершину Cg вершин C и C', такую, что C кладывается в Cg и C' вкладывается в Cg, стирает поддерево, которое начинается в C', сводит C' в Cg и выполняет прогонку для Cg;
  3. ничего не делает с C' (вершины C и C' "непохожи друг на друга") и проверяет следующую вершнину-предшественника; если больше предшественников, к которым можно свести C, нет, продолжает прогонку C.

Суперкомпиляция заканчивается, когда граф содержит для каждой активной вершины переход к следующей вершине, что соответсвует одному шагу рефал-машины. Этот граф - программа для вычисления вызова функции, находящегося в корневой вершине.

Обобщение - центральная проблема суперкомпиляции. Объекты, которые обобщаются при суперкомпиляции - вызовы функций. Принцип обобщения. Обобщение объектов имеет смысл только в контексте процесса вычисления, в котором участвуют эти объекты. Тогда язык обобщения должен иметь средства для описания истории вычислений, и обобщение должно представлять собой множество объектов, которые имеют общую историю вычислений до этого момента.

Обобщение делится на две части:

  1. принятие решения обобщить текущую конфигурацию C с одним из ее предшественников C' сведением C к C'; здесь необходим "свисток", чтобы предупредить возможно бесконечную прогонку (если не свести C к C').
  2. обобщение - построение конфигурации Cgen, такой что C и C' включаются в нее.

Хороший алгоритм обобщения должен находить баланс между двумя крайними случаями:
(1) "слишком общее" обобщение, которое оставляет результирующую программу неоптимизированной и
(2) надолго отложенное обобщение, так что процесс суперкомпиляции никогда не закончится.

В.Ф. Турчин обращает внимание на отличие преобразования программ и суперкомпиляции. Первое заключается в том, что к программе последовательно применяются эквивалентные преобразования. При суперкомпиляции исходная программа не изменяется, a создается модель вычислительного процесса, которая работает по определенным законам. Когда модель становится самодостаточной, исходная неизмененная программа отбрасывается.

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

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

-- Luba Parmyonova - 15 Jun 2005

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback