Частичное вычисление: как получить компилятор бесплатно

The Magic of Partial Evaluation

Джимми Миллер рассказывает о красоте частичного вычисления — идеи, которая позволяет выполнять часть программы на этапе сборки, оставляя только динамические фрагменты. На примере интерпретатора brainfuck он показывает первую проекцию Футамуры: если применить частичный вычислитель к интерпретатору и программе, на выходе получается скомпилированная программа. Это не только эстетически привлекательно, но и даёт практическую выгоду — например, ускорение валидации схем в 5 раз.

Когда вы берёте интерпретатор и частично вычисляете его с программой, вы получаете скомпилированную программу!
  1. TuringTest

    > Для меня самые красивые куски программного обеспечения — те, что раскрывают что-то о природе языков программирования.

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

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

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

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

    Эти озарения заставляют осознать, что все парадигмы программирования имеют общую природу обработки символов и что не существует «истинного описания» выполнения программы во время исполнения — императивный, функциональный и логический взгляды на работающую программу являются эквивалентными представлениями.

  2. artrax

    Мы строим это как библиотеку на C++, чтобы делать query-compilation для нашего движка потоковой обработки.

    https://github.com/nebulastream/nautilus

    Это позволяет нам реализовывать операторы или функции, не описывая их на DSL LLVM IR (или подобном). Вместо этого вы пишете свои функции над типом-обёрткой (и возвращаете его), для которого есть перегрузка всего, что можно перегрузить в C++.

    Вы можете создать экземпляр обёртки из некоторого значения C++, и в этом случае обёртка просто перенаправит всё этому значению, что было удобно для отладки в доагентную эру.

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

    Для управления потоком мы записываем каждый раз, когда тип-обёртка вычисляется как bool, сначала возвращаем true, а когда достигаем конца одной ветви, выбрасываем исключение, чтобы вернуться к началу и начать всё заново, но вычислить его как false.

    Полученную трассу мы можем превратить в LLVM IR и скомпилировать или запустить, например, в wasm.

  3. apignotti

    Несколько лет назад мы реализовали похожую концепцию в нашем компиляторе C++ -> JavaScript/WebAssembly (Cheerp). Это была интересная задача.

    https://labs.leaningtech.com/blog/reducing-webassembly-size-...

Ещё за этот день

2026-11-18