Привет, хабрачеловек. Сегодня я расскажу тебе про некоторые фундаментальные вещи в computer science: частичные вычисления, три проекции Футамуры и суперкомпиляцию.
 
 

1. Сразу к коду


-- функция, которая возводит x в степень y (неотрицательную)
power x y =
    case y of
        0 → 1
        1 → x
        _ → x * (power x (y - 1))



Предположим, мы используем эту функцию так:

  -- функция, вычисляющая площадь квадрата
  rectangleArea side = power side 2


Этот малюсенький пример наглядно показывает самый главный паттерн в программировании: абстракция.

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

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

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

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

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

  var someMagicNumber = 2^32


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

  var someMagicNumber = 4294967296


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

Попробуем частично-вычислить наш первый пример с площадью квадрата. Представим себя на месте компилятора. Компилятору известно, что функция power всегда в этом месте вычисляется с параметром y=2. Следовательно, её можно частично-вычислить, иначе говоря, специализировать по этому параметру.

Специализация, шаг 1. Подставляем константу 2 вместо свободного параметра y.

-- функция, которая возводит x в степень y (неотрицательную)
power2 x =
    case 2 of
        0 → 1
        1 → x
        _ → x * (power x (2 - 1))


Шаг 2. Вычисляем case-of, отбрасывая абсурдные ветки 0==2 и 1==2:

  -- функция, которая возводит x в степень 2
  power2 x = x * (power x (2 - 1))


Шаг 3. Вычисляем выражение (2 — 1):

  -- функция, которая возводит x в степень 2
  power2 x = x * (power x 1)


Шаг 4. Подставив y=1 в функцию power, получим:

  -- функция, которая возводит x в степень 2
  power2 x = x * x


Наверняка вы уже провели аналогию с техникой inlining — подстановки функций, знакомой по C/C++. Это тоже частичные вычисления.
 
 

2. Проекции Футамуры



Профессор Yoshihiko Futamura однажды пофантазировал на тему интерпретации программ в контексте частичных вычислений. Надо сказать, получилось довольно занятно, если не сказать, что полный крышеснос:

Пусть у нас есть некая волшебная функция, делающая частичные вычисления (специализирующая программы):

  specialize (program, data) : specialized_program


К примеру, если в specialize засунуть функцию функцию power из примера выше и данные «y=2» мы получим функцию power2. Довольно просто.

И есть интерпретатор некого языка, к примеру, интерпретатор PHP, написанный на ассемблере (хо-хо).

  php_eval (php_code) : data


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

Внимание, вопрос. Подумайте, что будет, если мы сделаем так:

  specialize (php_eval, php_code) ?


Мы смешиваем интерпретатор пхп на ассемблере и строку с пхп-кодом. В итоге, получается asm-программа, делающая то же самое, что пхп-программа. А это значит, что мы скомпилировали наш пхп-код в asm!

Итак, первая проекция Футамуры: компиляция — это специализация интерпретатора кодом интерпретируемой программы.

  compiled_php_code = specialize (php_eval, php_code)


Забавно, не правда ли?

Дальше — больше. Что будет, если мы сделаем:

  specialize (specialize, php_eval) ?


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

Выходит, что имея лишь интерпретатор PHP и магический специализатор, мы смогли родить компилятор PHP!

Это и есть вторая проекция Футамуры: компилятор — это специализация специализатора кодом интерпретатора.

  php_compiler (php_code) = (specialize (specialize, php_eval)) (php_code)


Уже немного начинает болеть голова, но ведь какой результат — из интерпретатора сделали компилятор! И это ведь ещё не всё… Сделаем так:

  specialize (specialize, specialize)


OMFG, что же это? Это генератор компиляторов. На вход подаем любой интерпретатор, на выходе получаем компилятор.

  make_compiler (interpreter) = (specialize (specialize, specialize)) (interpreter)


Это третья проекция Футамуры.
 
 

3. Суперкомпиляция, метавычисления



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

Компилятор, который математически моделирует выполнение программы, а затем использует эту модель для производства более эффективной программы называется суперкомпилятором (англ. supervising compiler).

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

Суперкомпиляцию еще называют «абстрактной интерпретацией» программ. У Турчина это обозначается термином «прогонка» — или «driving» в англоязычных публикациях.

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

Компилятор как бы пытается осмыслить процесс работы программы. Попробую проиллюстрировать на простом примере:

  frobnicate X =
  
    case X of
  
      true → case X of
        true → garply
        false → xyzzy
  
      false → case X of
        true → plugh
        false → garply


Не находите ничего странного в этом коде? При любом значении X алгоритм никогда не достигнет ни xyzzy, ни plugh. Мысленно прокрутите алгоритм и вы убедитесь в этом. Подумайте о том, как вы пришли к такому заключению — ведь суперкомпилятор работает точно так же.

Строим дерево процессов:

  X
    → true -- если X == true
  
      case true of
        true → garply
        false → xyzzy
  
    → false -- если X == false
  
      case false of
        true → plugh
        false → garply


Частично-вычисляем ветки case-of:

  X
    → true → garply
    → false → garply


Следовательно:

  frobnicate X = garply


Были попытки реализовать эту технику для Java:
www.supercompilers.com/white_paper.shtml

И, недавно, для Haskell (Supero):
www-users.cs.york.ac.uk/~ndm/supero/

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

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

Существуют разные техники обхода этой проблемы: генерализация — обобщение бесконечных деревьев, свертка (folding, code sharing) — обобщение одинаковых ветвей вычисления.

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

4. Programming by inversion



Суперкомпиляция программ дает интересные побочные эффекты — с её помощью можно решать задачи логического программирования (помните Prolog?), доказывать теоремы и инвертировать вычисления.

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

Допустим, у нас есть такая задача: найти в строке «abcd» все подстроки длиной 2 символа.

У нас есть функция (strstr a b), возвращающая true если b содержит a. Тогда записать решение, применив инверсию можно было бы так:

  >> [x | where (strstr x "abcd"), (length x) == 2]
    ["ab", "bc", "cd"]


Сразу же возникают ассоциации с техникой pattern matching в функциональных языках программирования. Собственно, так и есть — инверсия алгоритмов это ключ к абстрактному pattern matching.
 
 

Вместо заключения



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

P.S. Learn You a Haskell for Great Good!