Привет, хабрачеловек. Сегодня я расскажу тебе про некоторые фундаментальные вещи в 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!
