EditWYSIWYGAttachPrintable
r1 - 15 Jun 2005 - 14:42:38 - 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.

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

В.Ф. Турчин обращает внимание на отличие преобразования программ и суперкомпиляции. Первое заключается в том, что к программе последовательно применяются эквивалентные преобразования. При суперкомпиляции исходная программа не изменяется, 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