search

bmstu-iu9 / refal-5-lambda

Компилятор Рефала-5λ
https://bmstu-iu9.github.io/refal-5-lambda
Other
79 stars 35 forks source link

Останавливать специализацию по отношению Хигмана-Крускала #253

Closed Mazdaywik closed 4 years ago

Mazdaywik commented 5 years ago

Мотивация

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

Например:

$SPEC F t.x t.Y;

F {
  (t.X) t.Y = <F t.X (t.Y)>;
  Z t.Y = t.Y;
}

Здесь специализатор зависнет. С ограничением --opt-tree-cycles=5 получится такой результат:

содержимое лога ```Refal5 F { (t.X#1) t.Y#1 = ; Z t.Y#1 = t.Y#1; } F@1 { t.Y0#1 (t.X#1) = ; t.Y0#1 Z = (t.Y0#1); } F@2 { t.Y0#1 (t.X#1) = ; t.Y0#1 Z = ((t.Y0#1)); } F@3 { t.Y0#1 (t.X#1) = ; t.Y0#1 Z = (((t.Y0#1))); } F@4 { t.Y0#1 (t.X#1) = ; t.Y0#1 Z = ((((t.Y0#1)))); } F@5 { t.Y0#1 (t.X#1) = ; t.Y0#1 Z = (((((t.Y0#1))))); } ```

Конечно, это надуманный пример. Но есть реальные ситуации, когда с таким зависанием приходится бороться. В своём недавнем письме в рассылку я описал интерпретатор стекового языка, который растворяется при оптимизации. В исходном коде этого интерпретатора есть два случая, когда реально приходится бороться с зависанием:

$SPEC Loop e.stack (e.CODE) (e.DICT);

Loop {
  e.Stack (e.Code_) (e.Dict)
    , e.Code_
    : {
        ...

        if (e.True) else (e.False) e.Code
          , e.Stack
          : {
              e.Stack^ (0)
                = <Loop
                    <Loop e.Stack (e.False) (e.Dict)>
                    (e.Code) (e.Dict)
                  >;

              e.Stack^ (e.NotZero)
                = <Loop
                    <Loop e.Stack (e.True) (e.Dict)>
                    (e.Code) (e.Dict)
                  >;
            };

        define e.Code
          = <TransferBodyToDict e.Code (e.Dict)> : e.Code^ (e.Dict^)
            /* Функция TransferBodyToDict нужна, чтобы избежать зацикливания */
          = <Loop e.Stack (e.Code) (e.Dict)>;

        ...
      };
}

$INLINE TransferBodyToDict, Lookup;

TransferBodyToDict {
  s.FuncName (e.Body) e.Code (e.Dict) = e.Code ((s.FuncName e.Body) e.Dict);
}

Во-первых, рекурсивный вызов Loop при обработке оператора if-else:

                = <Loop
                    <Loop e.Stack (e.False) (e.Dict)>
                    (e.Code) (e.Dict)
                  >;

Более естественно было бы написать

                = <Loop e.Stack (e.False e.Code) (e.Dict)>;

Во-вторых, грязный хак с TransferBodyToDict (о чём даже говорит комментарий в коде):

        define e.Code
          = <TransferBodyToDict e.Code (e.Dict)> : e.Code^ (e.Dict^)
            /* Функция TransferBodyToDict нужна, чтобы избежать зацикливания */
          = <Loop e.Stack (e.Code) (e.Dict)>;

вместо логичного

        define s.FuncName (e.Body) e.Code
          = <Loop e.Stack (e.Code) ((s.FuncName e.Body) e.Dict)>;

Содержательная оптимизация происходит в функции Go, где на вход программы передаётся константный исходный текст. Но есть и побочная оптимизация: оптимизируется сама функция Loop. И если написать if/else и define так, как логично, то вызовы

<Loop e.Stack (e.False e.Code) (e.Dict)>

и

<Loop e.Stack (e.Code) ((s.FuncName e.Body) e.Dict)>

приведут к зацикливанию.

В первом e.CODE будет на каждом цикле возрастать по цепочке e.1, e.1 e.2, e.1 e.2 e.3…, во втором e.DICT — e.1, (s.1 e.2) e.3, (s.1 e.2) (s.3 e.4) e.5…

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

Что надо сделать

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

Истории сигнатур для примера с функцией F:

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

И как её прерывать?

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

Данное обобщение будет «перестройкой снизу» в терминах С. М. Абрамова (частная переписка). В суперкомпиляции перестройка сверху означает, что если верхняя и одна из дочерних конфигураций похожи, то вычисляется их обобщение, всё поддерево, растущее из верхней конфигурации отбрасывается и заменяется деревом, растущим из обобщения. В случае перестройки снизу дерево не отбрасывается, вместо этого нижняя конфигурация обобщается до обобщения себя и родительской.

В случае специализации при обнаружении похожих по Х.-К. сигнатур мы не отбрасываем функции, специализированные после первой сигнатуры, а обобщаем сигнатуру нижнюю.

Вывод

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

Заметим, что при пополнении словаря с известной программой отношение Хигмана-Крускала не сработает. e.DICT увеличивается, но при этом e.CODE уменьшается.

Mazdaywik commented 5 years ago

Это прекрасная задача для курсовой работы или даже ВКР. Для курсовой достаточно реализовать базовый вариант — когда компилятор отказывается от специализации, если сигнатура «свистит». Т.е. прерывание цепи специализаций без обобщения.

Mazdaywik commented 5 years ago

Задача не была выбрана в качестве курсовой.

Mazdaywik commented 4 years ago

Что надо будет сделать по коду.

  1. Нужно будет расширить e.SpecInfo, чтобы в нём хранить ещё и историю сигнатур.
  2. «Протаскивать» историю от определения функции (SpecUnit) до анализа вызова (SpecCall), где её уже можно будет использовать.
  3. Ну и в SpecCall уже учитывать сигнатуры, как описано выше.

Ну, по крайней мере, я так вижу.

Mazdaywik commented 4 years ago

Добрый день, @koshelevandrey!

@Kaelena разрабатывает инструмент для автоматической разметки оптимизируемых функций — её модуль будет автоматически добавлять метки $DRIVE и $SPEC в синтаксическое дерево (см. https://github.com/bmstu-iu9/refal-5-lambda/issues/252#issuecomment-621768213).

Метки в задаче #252 должны расставляться безопасно — пометка функций как прогоняемой или специализируемой не должна приводить к зацикливанию. Правильно добавлять метки $SPEC чертовски сложно, если специализация может зацикливаться, но довольно легко, если специализатор умеет прерываться (предмет настоящей задачи).

Поэтому предлагаю работу разбить на два этапа:

  1. Прерывание специализации без обобщения — когда на очередном вызове обнаружили зацикливание, этот вызов оставляем неизменным.
    • Вы создаёте pull request в master, я делаю ревью и сливаю.
    • @Kaelena вливает master в свою ветку и может вести разработку и тестирование разметки $SPEC’ов.
  2. Вы дальше продолжаете работу над обобщением — чтобы зацикленный вызов не оставлять как есть, а как-то оптимизировать.