Оптимизация образцовых выражений путём ортогонализации образцов

[Mazdaywik]

Мотивация

Мотивация та же, что и в #15 — образцы сопоставляются независимо, из-за чего при переходе к следующему образцу теряется информация об успешности/неуспешности сопоставления на предыдущих этапах и приходится совершать дополнительные операции.

Это понятно, очевидно, но как всегда, дьявол прячется в нюансах.

Сначала была реализована независимая компиляция предложений без какого-либо взаимодействия между ними.

Затем был найден алгоритм, позволяющий найти префикс максимальной длины для всех образцов функции — алгоритм вычисления ГСО. Часть избыточности устранить удалось — одинаковые для всех предложений операции выполняются только один раз. Недостаток: если только часть предложений имеют несколько общих элементарных операций отождествления, они всё равно могут выполняться несколько раз.

В прошлом (2018) году была предложена группировка предложений. Но, чтобы её описать, понятие ГСО нужно обобщить от образца до подстановки.

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

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

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

Во-первых, не переставляются явно ортогональные предложения вида:

A 1 e.X = 1;
B 2 e.X = 2;
A 3 e.X = 3;

Будет построено такое дерево сужений:

e.0 → s.1 e.0
e.0 → s.2 e.0
Sentence {
  s.1 → A
  s.2 → 1
  return 1
}
Sentence {
  s.1 → B
  s.2 → 2
  return 2
}
Sentence {
  s.1 → A
  s.2 → 3
  return 3
}

Допустим, аргумент имеет вид A 3 'abcde'. Тогда произойдёт успешное сужение s.1 → A для первого образца, следующее сужение s.2 → 1 окажется неудачным. Управление будет передано второму образцу, где первое же сужение s.1 → B окажется тоже неудачным. Наконец в третьем образце оба элементарных сужения выполнятся успешно.

Заметим, что дерево будет построено именно так, поскольку для первых трёх и для первых двух предложений ГСО будет тривиальным, поэтому в группу будет выделено только первое предложение. Аналогично из двух оставшихся предложений тоже будут сформированы две группы.

Если переставить ортогональные предложения, то результат будет лучше:

A 1 e.X = 1;
A 3 e.X = 3;
B 2 e.X = 2;

Первые два предложения имеют нетривиальное ГСО s.1 → A, s.2 → s.2 (вторая подстановка тривиальна, зато первая нетривиальна), поэтому они будут выделены в отдельную группу.

e.0 → s.1 e.0
e.0 → s.2 e.0
Sentence {
  s.1 → A
  Sentence {
    s.2 → 1
    return 1
  }
  Sentence {
    s.2 → 3
    return 3
  }
}
Sentence {
  s.1 → B
  s.2 → 2
  return 2
}

Но алгоритм такой перестановки не был реализован.

Во-вторых, перестановка (даже если её реализовать) будет возможна только для ортогональных образцов, а значит, группу предложений

A 1 e.X = 1 e.X;
e.Y B = 2 e.Y;
A 3 e.X = 3 e.X;
/* пусто */ = 4;

оптимизировать никак не удастся. Для образца A 3 'abcde' придётся дважды сопоставлять A.

Так что же делать?

Предлагается реализовать алгоритм, который ничего не забывает из ранее выполненного. Для последнего примера он запомнит, что первым символом аргумента является A, и его повторно сопоставлять не нужно. Как? После выполнения каждого элементарного сужения раздваивать набор предложений для случаев, когда сопоставление успешно и когда оно неуспешно. Если предложение одного из наборов противоречит последнему сужению, оно исключается. Остальные остаются.

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

Рассмотрим его на последнем примере. Для трёх предложений имеем четыре подстановки:

e.0 → A 1 e.X = 1 e.X;
e.0 → e.Y B = 2 e.Y;
e.0 → A 3 e.X = 3 e.X;
e.0 → ε = 4;

Простейшее сужение, применимое к первому предложению, имеет вид e.0 → t.1 e.0. Применим его и его отрицание (e.0 → ε) ко всем:

if (e.0 → t.1 e.0) {
  t.1 → A, e.0 → 1 e.X = 1 e.X;
  t.1 → B = 2;
  e.0 → e.0 B = 2 t.1 e.0;
  t.1 → A, e.0 → 3 e.X = 3 e.X;
} else (e.0 → ε) {
  = 4;
}

В первую группу сразу упали первые три предложения, во вторую — последнее четвёртое. Второе предложение пришлось расщепить — сужения e.0 → t.1 e.0 и e.0 → e.Y B совместимы только в двух случаях: когда аргумент имеет вид B (при этом e.0 == e.Y == ε) или t.1 e.0 B (при этом e.Y == t.1 e.0) два новых предложения охватывают оба случая.

Последняя группа состоит из единственного предложения, делать с ней ничего не надо. Первая группа состоит из четырёх предложений, к первому из них применимо следующее элементарное сужение, t.1 → s.1. Его отрицанием будет t.1 → (e.1). Разобьём по нему первую ветку:

if (e.0 → t.1 e.0) {
  if (t.1 → s.1) {
    s.1 → A, e.0 → 1 e.X = 1 e.X;
    s.1 → B = 2;
    e.0 → e.0 B = 2 s.1 e.0;
    s.1 → A, e.0 → 3 e.X = 3 e.X;
  } else ( t.1 → (e.1)) {
    e.0 → e.0 B = 2 (e.1) e.0;
  }
} else (e.0 → ε) {
  = 4;
}

Следующее применимое сужение s.1 → A, его отрицание s.1 ≠ A:

if (e.0 → t.1 e.0) {
  if (t.1 → s.1) {
    if (s.1 → A) {
      e.0 → 1 e.X = 1 e.X;
      e.0 → e.0 B = 2 A e.0;
      e.0 → 3 e.X = 3 e.X;
    } else (s.1 ≠ A) {
      s.1 → B = 2;
      e.0 → e.0 B = 2 s.1 e.0;
    }
  } else ( t.1 → (e.1)) {
    e.0 → e.0 B = 2 (e.1) e.0;
  }
} else (e.0 → ε) {
  = 4;
}

Разбиваем первую внутреннюю группу по e.0 → t.2 e.0 / e.0 → ε:

if (e.0 → t.1 e.0) {
  if (t.1 → s.1) {
    if (s.1 → A) {
      if (e.0 → t.2 e.0) {
        t.2 → 1 = 1 e.0;
        t.2 → B = 2 A;
        e.0 → e.0 B = 2 A t.2 e.0;
        t.2 → 3 = 3 e.0;
      } else (e.0 → ε) {
        fail;
      }
    } else (s.1 ≠ A) {
      s.1 → B = 2;
      e.0 → e.0 B = 2 s.1 e.0;
    }
  } else ( t.1 → (e.1)) {
    e.0 → e.0 B = 2 (e.1) e.0;
  }
} else (e.0 → ε) {
  = 4;
}

Вторая ветка пустая, поскольку несовместима с сужениями e.0 → 1 e.X, e.0 → e.0 B и e.0 → 3 e.X. Поэтому, если передано на неё управление, функция должна аварийно завершиться. Продолжая ещё несколько раз в том же духе, получим окончательный результат:

if (e.0 → t.1 e.0) {
  if (t.1 → s.1) {
    if (s.1 → A) {
      if (e.0 → t.2 e.0) {
        if (t.2 → s.2) {
          if (s.2 → 1) {
            = 1 e.0;
          } else if (s.2 → B) {
            = 2 A;
          } else (s.2 ≠ 1 && s.2 ≠ B) {
            if (e.0 → e.0 t.3) {
              if (t.3 → s.3) {
                if (s.3 → B) {
                  = 2 A s.2 e.0;
                } else (s.3 ≠ B) {
                  if (s.2 → 3) {
                    = 3 e.0 s.3;
                  } else (s.2 ≠ 3) {
                    fail;
                  }
                }
              } else (t.3 → (e.3)) {
                if (s.2 → 3) {
                  = 3 e.0 (e.3);
                } else (s.2 ≠ 3) {
                  fail;
                }
              }
            } else (e.0 → ε) {
              if (s.2 → 3) {
                = 3;
              } else (s.2 ≠ 3) {
                 fail;
              }
            }
          }
        } else (t.2 → (e.2)) {
          if (e.0 → e.0 t.3) {
            if (t.3 → s.3) {
              if (s.3 → B) {
                = 2 A (e.2) e.0;
              } else (s.3 ≠ B) {
                fail;
              }
            } else (t.3 → (e.3)) {
              fail;
            }
          } else (e.0 → ε) {
            fail;
          }
        }
      } else (e.0 → ε) {
        fail;
      }
    } else if (s.1 → B) {
      = 2;
    } else (s.1 ≠ A && s.1 ≠ B) {
      e.0 → e.0 B = 2 s.1 e.0;
    }
  } else ( t.1 → (e.1)) {
    if (e.0 → e.0 t.2) {
      if (t.2 → s.2) {
        if (s.2 → B) {
          = 2 (e.1) e.0;
        } else (s.2 ≠ B) {
          fail;
        }
      } else (t.2 → (e.2)) {
        fail;
      }
    } else (e.0 → ε) {
      fail;
    }
  }
} else (e.0 → ε) {
  = 4;
}

Очень многословно, но зато алгоритм никогда не делает откатов. Лесенки else/fail/else/fail можно упрощать, но в этом примере такой задачи не ставилось.

Возникает вопрос: если доступно несколько сужений, то какое выбирать? В примере выше рассматривалось рандомное доступное элементарное сужение из первого предложения.

На самом деле можно группу предложений разбивать по любому доступному сужению из любого предложения — на корректность алгоритма это не повлияет. Это ещё более расширяет свободу выбора.

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

Очевидно, что если сужение взято из одного предложения, а всего предложений N, то получится не более 2N−1 предложений, поскольку отрицание сужения с выбранным предложением не совместимо. Но не менее и N предложений, поскольку каждое предложение или совместимо с сужением, или совместимо с отрицанием, или с ними обоими. При этом для сужений вида e.0 → t.1 e.0 и e.0 → e.X t.Y будут строиться не более чем два предложения для t.1 → t.Y и e.0 = e.X = ε и e.0 → e.0 t.Y и t.1 e.0 ← e.X.

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

Если выбрано такое сужение, что с каждым из предложений совместимо либо оно, либо его отрицание, то тоже мы получим N предложений.

Из таких соображений эвристика кажется работающей.

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

Поэтому интересно, во-первых, реализовать чистую оптимизацию по эвристике, во-вторых, её объединение с ГСО и сравнить их производительности.

Литература

Термин «ограниченный Рефал» и способ пересечения произвольного выражения (включая образцовое) с элементарным сужением можно найти в классических работах Турчина:

• В. Ф. Турчин. Эквивалентные преобразования рекурсивных функций, описанных на языке РЕФАЛ. В cб.: Труды симпозиума «Теория языков и методы построения систем программирования», Киев-Алушта: 1972. Стр. 31-42. PDF
• В. Ф. Турчин. Эквивалентные преобразования программ на РЕФАЛе. В cб.: Труды ЦНИПИАСС «Автоматизированная система управления строительством», выпуск 6, М: 1974. Стр. 36-68. PDF

[Mazdaywik]

Задача снимается, поскольку студент-дипломник ушёл из университета.