Привет, хабрачеловек. Сегодня я расскажу тебе про некоторые фундаментальные вещи в computer science: частичные вычисления, три проекции Футамуры и суперкомпиляцию.
Предположим, мы используем эту функцию так:
Этот малюсенький пример наглядно показывает самый главный паттерн в программировании: абстракция.
Как и в этом примере, большую часть времени мы используем абстракции в частных, специальных случаях, при этом неиспользуемая часть неизбежно вызывает накладные расходы при вычислении.
Вспомните про свой любимый веб-фреймворк, к примеру. А вот какая часть его кода делает действительно полезную работу в вашем приложении?
Многих неопытных программистов этот вопрос буквально сводит с ума и они начинают заниматься преждевременной оптимизацией, отрицанием абстракций и прочими глупыми вещами.
Но использование абстракций не обязательно должно влечь за собой накладные расходы. Код, использующий тяжеловесные всемогущие фреймворки не обязательно должен работать медленнее, чем написанный вручную, ad hoc код.
Частичные вычисления — это мощная техника, полностью нивелирующая накладные расходы от абстракций. Подавляющее число оптимизаций, существенно увеличивающих скорость программы являются частными случаями частичного вычисления программы. Простой пример:
Почти каждый современный компилятор сможет упростить (и упростит) это выражение, переписав его при компиляции так, что не понадобится вычислять это снова и снова при запуске кода:
Это самый простой пример частичных вычислений. Называется этот термин так потому, что при этой оптимизации какая-то часть программы выполняется и результат сохраняется, а другая часть остается неизменной.
Попробуем частично-вычислить наш первый пример с площадью квадрата. Представим себя на месте компилятора. Компилятору известно, что функция power всегда в этом месте вычисляется с параметром y=2. Следовательно, её можно частично-вычислить, иначе говоря, специализировать по этому параметру.
Специализация, шаг 1. Подставляем константу 2 вместо свободного параметра y.
Шаг 2. Вычисляем case-of, отбрасывая абсурдные ветки 0==2 и 1==2:
Шаг 3. Вычисляем выражение (2 — 1):
Шаг 4. Подставив y=1 в функцию power, получим:
Наверняка вы уже провели аналогию с техникой inlining — подстановки функций, знакомой по C/C++. Это тоже частичные вычисления.
Профессор Yoshihiko Futamura однажды пофантазировал на тему интерпретации программ в контексте частичных вычислений. Надо сказать, получилось довольно занятно, если не сказать, что полный крышеснос:
Пусть у нас есть некая волшебная функция, делающая частичные вычисления (специализирующая программы):
К примеру, если в specialize засунуть функцию функцию power из примера выше и данные «y=2» мы получим функцию power2. Довольно просто.
И есть интерпретатор некого языка, к примеру, интерпретатор PHP, написанный на ассемблере (хо-хо).
На входе — строка с пхп-кодом, на выходе — результат вычисления. Тоже ничего необычного.
Внимание, вопрос. Подумайте, что будет, если мы сделаем так:
Мы смешиваем интерпретатор пхп на ассемблере и строку с пхп-кодом. В итоге, получается asm-программа, делающая то же самое, что пхп-программа. А это значит, что мы скомпилировали наш пхп-код в asm!
Итак, первая проекция Футамуры: компиляция — это специализация интерпретатора кодом интерпретируемой программы.
Забавно, не правда ли?
Дальше — больше. Что будет, если мы сделаем:
Мы смешиваем специализатор и интерпретатор пхп на ассемблере. Получается — программа, которой на вход можно подать любой пхп-код и она превратит его в ассемблерный код.
Выходит, что имея лишь интерпретатор PHP и магический специализатор, мы смогли родить компилятор PHP!
Это и есть вторая проекция Футамуры: компилятор — это специализация специализатора кодом интерпретатора.
Уже немного начинает болеть голова, но ведь какой результат — из интерпретатора сделали компилятор! И это ведь ещё не всё… Сделаем так:
OMFG, что же это? Это генератор компиляторов. На вход подаем любой интерпретатор, на выходе получаем компилятор.
Это третья проекция Футамуры.
Частичные вычисления позволяют сократить код путем подстановки заранее известных данных в программу. Но существует ещё более продвинутая техника, которая может оптимизировать код намного сильнее, и частичные вычисления являются её подмножеством — суперкомпиляция.
Компилятор, который математически моделирует выполнение программы, а затем использует эту модель для производства более эффективной программы называется суперкомпилятором (англ. supervising compiler).
Интересно, что авторство этого термина (и сопутствующих исследований) принадлежит нашему соотечественнику — Валентину Турчину. Он также разработал язык Рефал, демонстрирующий концепт суперкомпиляции (язык очень стар и основан на переписывании термов).
Суперкомпиляцию еще называют «абстрактной интерпретацией» программ. У Турчина это обозначается термином «прогонка» — или «driving» в англоязычных публикациях.
При прогонке компилятор строит дерево процессов программы — граф всех возможных состояний программы с ребрами-переходами между ними.
Компилятор как бы пытается осмыслить процесс работы программы. Попробую проиллюстрировать на простом примере:
Не находите ничего странного в этом коде? При любом значении X алгоритм никогда не достигнет ни xyzzy, ни plugh. Мысленно прокрутите алгоритм и вы убедитесь в этом. Подумайте о том, как вы пришли к такому заключению — ведь суперкомпилятор работает точно так же.
Строим дерево процессов:
Частично-вычисляем ветки case-of:
Следовательно:
Были попытки реализовать эту технику для Java:
www.supercompilers.com/white_paper.shtml
И, недавно, для Haskell (Supero):
www-users.cs.york.ac.uk/~ndm/supero/
Наверное, некоторые читатели уже представили себе некий компилятор, который, используя частичные вычисления и суперкомпиляцию, полностью оптимизирует любую программу. Но решить эту задачу невозможно — она относится к классу неразрешимых задач.
В реальности дерево процессов программы становится бесконечным или слишком большим для разумной обработки. Это происходит при попытке анализа даже небольших программ, что уж говорить про большие коммерческие приложения в десятки миллионов строк кода.
Существуют разные техники обхода этой проблемы: генерализация — обобщение бесконечных деревьев, свертка (folding, code sharing) — обобщение одинаковых ветвей вычисления.
В реализации этих техник также много проблемых мест — к примеру, не всегда легко определить, когда стоит обобщать, а когда нет. Как говорится, дьявол в деталях.
Суперкомпиляция программ дает интересные побочные эффекты — с её помощью можно решать задачи логического программирования (помните Prolog?), доказывать теоремы и инвертировать вычисления.
Обладая множеством входов и выходов функции и абстрактным графом вычисления (деревом процессов) — можно в некоторых частных случаях инвертировать вычисление.
Допустим, у нас есть такая задача: найти в строке «abcd» все подстроки длиной 2 символа.
У нас есть функция (strstr a b), возвращающая true если b содержит a. Тогда записать решение, применив инверсию можно было бы так:
Сразу же возникают ассоциации с техникой pattern matching в функциональных языках программирования. Собственно, так и есть — инверсия алгоритмов это ключ к абстрактному pattern matching.
Вот такая статья получилась, хабрачеловек. Надеюсь, она помогла тебе взглянуть под другим углом на интерпретацию, оптимизацию и компиляцию программ.
P.S. Learn You a Haskell for Great Good!
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!
