Частичное вычисление: как получить компилятор бесплатно
The Magic of Partial Evaluation
Джимми Миллер рассказывает о красоте частичного вычисления — идеи, которая позволяет выполнять часть программы на этапе сборки, оставляя только динамические фрагменты. На примере интерпретатора brainfuck он показывает первую проекцию Футамуры: если применить частичный вычислитель к интерпретатору и программе, на выходе получается скомпилированная программа. Это не только эстетически привлекательно, но и даёт практическую выгоду — например, ускорение валидации схем в 5 раз.
Когда вы берёте интерпретатор и частично вычисляете его с программой, вы получаете скомпилированную программу!
- TuringTest
> Для меня самые красивые куски программного обеспечения — те, что раскрывают что-то о природе языков программирования.
Есть три момента, которые заставляют функционального программиста развить своё понимание того, как на самом деле работает язык программирования как символьное представление человеческой мысли, за пределами метафоры, преподаваемой в школе, о компьютерной программе как о мясорубке, которая перемалывает входные данные и выдаёт результаты.
Первый — когда ты действительно понимаешь рекурсию и то, как функция может быть определена через саму себя (с разными параметрами для каждого вызова).
Второй — когда ты открываешь для себя унификацию переменных в Prolog или ленивые вычисления в Haskell и то, как можно представлять бесконечные структуры данных, не заставляя программу зависать в бесконечном цикле.
Третий — когда ты узнаёшь, что поведение любого императивного языка (вплоть до работы трактов данных микропроцессора) может быть полностью представлено на чистом функциональном языке перезаписи (без деструктивного присваивания / изменения состояния ячеек).
Эти озарения заставляют осознать, что все парадигмы программирования имеют общую природу обработки символов и что не существует «истинного описания» выполнения программы во время исполнения — императивный, функциональный и логический взгляды на работающую программу являются эквивалентными представлениями.
- artrax
Мы строим это как библиотеку на C++, чтобы делать query-compilation для нашего движка потоковой обработки.
https://github.com/nebulastream/nautilus
Это позволяет нам реализовывать операторы или функции, не описывая их на DSL LLVM IR (или подобном). Вместо этого вы пишете свои функции над типом-обёрткой (и возвращаете его), для которого есть перегрузка всего, что можно перегрузить в C++.
Вы можете создать экземпляр обёртки из некоторого значения C++, и в этом случае обёртка просто перенаправит всё этому значению, что было удобно для отладки в доагентную эру.
Но вы также можете создать такую обёртку как трассировщик, и результатом вычисления функции будет трасса.
Для управления потоком мы записываем каждый раз, когда тип-обёртка вычисляется как bool, сначала возвращаем true, а когда достигаем конца одной ветви, выбрасываем исключение, чтобы вернуться к началу и начать всё заново, но вычислить его как false.
Полученную трассу мы можем превратить в LLVM IR и скомпилировать или запустить, например, в wasm.
- apignotti
Несколько лет назад мы реализовали похожую концепцию в нашем компиляторе C++ -> JavaScript/WebAssembly (Cheerp). Это была интересная задача.
https://labs.leaningtech.com/blog/reducing-webassembly-size-...