Привет, хабрачеловек. Сегодня я расскажу тебе про некоторые фундаментальные вещи в 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!
комментарии (76)
Я кстати обнаружил подвох только когда прочел английское написание этой фамилии в ссылке. Видимо потому, что я недостаточно знаю инлиш :)
П.С. тоже прочитал Футурама ^^
drbugy длео грвиоот.
Итак, тестирование… Кетсвачо мироалтаев наииккх ннеикраай не ввзеаыыт. Метал по виду крепкий и качественный.
перескоки букв на одну-две позиции очень легко читаются. а в вашем примере дальность «перескока» в основном 3-5 позиций, это сложный пример.
В этом смысле «Футамура» и «Футурама», имхо — идеальная пара, на глаз практически неразличимая.
Да и вообще теории териями, а практика без всяких глупостей доказывает этот тезис. У меня есть знакомый, он часто опечатывается в словах именно по типу неправильного порядка нажатия клавиш. Когда я читаю его письма ~90% слов читаются на ходу
Я не одинок…
P.S. Ну и фамилия… Что-то она мне напомнила…
Прощай спокойный сон )
Разве суперкомпиляция — это ненормально? =)
А вообще, очень похожа на кусок из книги Душкина про Хаскель.
Правда он это вероятно тоже откуда-то спёр (как и целые главы их YAHT) =)
Как раз сегодня писал о Прологе и вскользь касался Рефала.
Не совсем понял логику 4 пункта, а именно связь между суперкомпиляцией, инвертированием и pattern matching ). В прологе, многие предикаты и так уже инвертированы, например,
И коль уж зашла речь, функцию всех подстрок длины 2 можно реализовать так:
пример работы:
образец — это функция, вычисление
вот мы хотим сопоставить что-то с образцом; это «что-то» — результат вычисления, выход функции
также мы можем указать какие-то известные входы функции в образце
нам нужно вычислить недостающие (неизвестные) входы этой функции, чтобы выполнить «pattern match»
а для этого нужно прогнать вычисление от выхода к входам, наоборот, т.е. получить инвертированный алгоритм
пример:
sum a b = a + b
case 5 of
(sum x 3) → print x
выведет 2
а про связь между инвертированием и компиляцией можно у того же Турчина почитать:
portal.acm.org/citation.cfm?doid=96877.96953
We proved by construction an application considered theoretically by Turchin [7] that self-application of metacomputation will allow the automatic construction of inverse algorithms, in particular the algorithm of binary subtraction from the algorithm of binary addition.
1. константа
2. конструктор списка (head:tail), конструктор алгебраических типов (структуры, варианты)
3. некоторые умеют (x + 1) матчить (хз, зачем)
A Supercompiler For Core Haskell (pdf)
// в статье кстати красивый график есть, к которому заглавие «А Си быстрее и без суперкомпиляции» подходит =)
в статье есть ссылка на попытку сделать суперкомпилятор для Java, но что-то у них не пошло
а C не быстрее, C — более explicit, так же, как assembler vs. C
задача в том, чтобы сделать функциональный код как минимум не медленнее вручную написанного
Ну не надо противопоставлять теплое мягкому. explicit это одно свойство языка, а скорость — это совершенно другое.
Графики явно показывают, что С быстрее… Конечно, можно возразить, что у Haskell'а есть другие преимущества и его оптимизацией занимаются не столько времени, сколько занимаются оптимизациями императивных языков… Но тут мы ступаем на весьма зыбкую почву.
более-того ну возьмем мы автоматическое распараллеливание какой-нибудь десктопной программки на Haskell, в которой списки ([a]) автоматически превратились в параллельные массивы ([:a:]) и даже очень много функций принимающих списки автоматически распаралилились и стали принимать параллельные массивы… Где гарантия, что всё это станет действительно быстрее работать? А не начнётся пыхтение, сопение и переключение контекстов и постоянные проблемы с кэшем и синхронизацией?
Нет, я, конечно, не отрицаю, что на Haskell можно достаточно легко писать руками параллельные программы в стиле «share nothing». Только вот такие программы и на Си писать легко. Проблемы начинаются, когда возникает необходимость сделать «share something».
Я считаю на этом поле the next big thing это транзакционная память. Будет ли от неё счастье, мне пока не ясно до конца, но надежды есть…
ну в самом деле, не будете же вы делать оптимизацию ассемблерного кода, когда эти оптимизации проще делать на уровне, скажем, C++
не понял почему.
опять не понял, что значит на уровне C++? большинство известных мне оптимизаций* делаются на уровне весьма себе низкоуровневого императивного IR. на выскоуровневом структурном IR делается незначительное число оптимизаций.
* — я говорю об императивщине.
в статье как раз рассказывается про оптимизации на высоком уровне (частичные вычисления)
>> не понял почему.
потому что анализировать функциональный код проще
в статье функциональщина, я говорил про С++
не думаю что уж сильно проще, где-то проще, а где-то сложнее… вот над fusion в GHC сколько бьются, никак сделать нормально не могут =)
и вообще вас разве привлекают только простые задачи? меня наоборот =)
Очень интересно, реально ли воспользоваться идеей для написания компиляторов. Есть некая загвоздка — всё было бы прекрасно, если бы транслярор был написан на ассемблере, но сейчас трансляторы пишут на высокоуровневых языках. А это означает, что specialize(interpreter, code) вернёт код на том языке, на котором написан interpreter, а не на asm'е, к сожалению.
Очевидно, нельзя написать такую specialize, которая смогла бы специализировать код на любом языке. Нужно некое внутреннее представление, которая specialize могла бы обрабатывать и функция перевода кода в это представление — это раз.
Далее. Какой код, как вы думаете, получится после применения specialize к этому внутреннему представлению? Правильно! Получится снова промежуточный код. А значит, нам нужно преобразовать его к исходному формату. То есть нам нужна ещё и функция перевода промежуточного кода в старый код.
Так вот! По сути компилятором (вернее, генератором кода), оказывается вторая переданная функция, а вовсе не specialize.
Таким образом, мы ничего нового не изобрели, а эта «магическая функция» specialize остаётся не более чем тем, чем она являлась первоначально — вычислителем константных выражений.
разумеется
И ещё «минус первую» проекцию: процесс разработки есть специализация возможностей разработчика конкретной задачей.
Отыскал свои высказывания шестилетней давности на эти темы:
www.jroller.com/deep/entry/cyber_telepathy_of_generative_programming
На примере unix — некая программа может быть скомпилирована с поддержкой библиотек A, B, C. А может обойтись и без них. Например, с поддержкой JPG, PNG, X11 или без части из них. Это отразится на ее функциональности, но про это мы можем знать заранее. Далее — есть дистрибутивы ОС. Они поставляются с предкомпилированными программами. При инсталляции есть варианты выбора вида инсталляции — с X11 и без оного. Вопрос в том как отрубить у готовых бинарников лишние зависимости? Т.е как вести разработку программ и их оформление чтобы это отрубание происходило без их пере компиляции? Вроде эта задача может иметь решение в отличии от оптимизации любого кода? :)
Если обобщать — как оптимизировать программу зная не фиксированные параметры, а перечни или диапазоны параметров. Или же от обратного — зная те диапазоны параметров, которые заведомо не будут поданы на вход программе.
Или же еще по другому — отсекать диапазоны входных значений на уровне их ввода, а не на уровне использования. При этом оставляя ту же программу — без пере компиляции способную включить требуемую функциональность. Пример — как только появляется библитотека Mysql включить поддержку ее не пересобирая с соответствующей libmysqlclient, но при этом не валиться в core, если пользователь укажет на входе ключик -connect-mysql.
Сейчас по большей части в C это решается через условную компиляцию и #ifdef.
Может есть уже готовые решения?
ps. в давние времена был забавный глюк в некоей IDE — если в программе на C не встречалось ни одного дробного числа в явном виде, то в printf переставало обрабатываться %f — вывод чисел с плавающей запятой. :)