Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

Прогресс HN0

Отказ от рекурсии и переменных существенно упрощает компилятор и дает возможность выполнять больше оптимизаций. Причем чем больше я читаю литературы, тем больше вижу преимуществ в таком подходе.

Например, вчера оказалось, что используемые мной комбинаторы B, C, K, W образуют базис, и вся нелинейность программы оказывается заключена в комбинаторе W, который нелинеен по второму параметру. В терминах Хаскеля B = (.), C = flip, K = const, а W = \x y _> x y y.

Таким образом, скорее всего, детектор линейности удастся реализовать, просто отслеживая все вхождения "разветвителя" W. Линейность - в смысле linear logic Жирара и Вадлера, это то же самое, что uniqueness types в языке Clean Плазмеера, но без привязки к Graph Rewriting. На переменные линейного типа может быть не более одной ссылки в программе.

Линейность хороша тем, что для переменных линейных типов можно организовать автоматическое управление памятью без сборки мусора и подсчета ссылок, а также in-place updates без потери referential transparency. Идея линейности используется в компиляторе Clean и приводит к существенному росту производительности (в 3 раза по сравнению с Хаскелем по синтетике). Соответственно, автоматический детектор линейности без необходимости явных аннотаций линейности той или иной переменной программистом был бы большим шагом вперед даже по сравнению с Clean.

По задумке, должен получиться эффективный компилятор в С++, который я буду использовать в своем текущем проекте вместо С++. Существующие языки я использовать не могу из-за их низкой производительности, отсутствия link compatibility с MSVC2005 или отсутствия компилятора под платформу Win/x64. Платформа Win/x64 требует от языка своего собственного генератора кода под эту платформу, т.к. GCC, традиционно используемый в качестве бэкенда, пока под Win64 не вышел. Соответственно, такой генератор не все могут себе позволить - он есть только в Clean.

Естественно, сначала скорость написания программ мной будет страдать. Комбинаторные программы славятся своей многословностью и тем, что при небольшом изменении функциональности приходится вносить гигантские изменения в код. Я планирую использовать эту кодебазу, написанную на кривом HN0, для оценки производительности в реальном HPC-приложении. Производительность не должна сильно пострадать, т.к. я устраню четыре источника замедления - косвенные вызовы, сборку мусора, выделение памяти под замыкания в куче и боксинг. И уж точно не будет такого маразма, который получает компилятор Хаскеля в результате компиляции своего STG-кода. Но так как товарищи SPJ (идеолог Хаскеля) и Plasmeijer (идеолог Клина) не полные дебилы, то абсолютной уверенности в собственной правоте у меня нет. Вдруг обнаружатся какие-то подводные грабли, которые всю производительность и съедят. Но я за последние несколько месяцев (с 5 августа - дня рождения HN0) перерыл горы литературы, и пока прочтенное мной только подкрепляет мою уверенность, что всё получится.

Если я увижу, что после переписывания на HN0 c C++ скорость пострадает не сильно, я начну расширять иерархию HN-языков вверх - HN+1, HN+2 и так далее, в духе архитектуры компилятора EHC. Введу сначала проверку и вывод обычных (simply typed lambda-calculus) типов по Хиндли-Милнеру-Дамасу в духе Haskell и Clean, затем добавлю линейные типы по Вадлеру-Плазмееру в духе Clean, затем зависимые типы по Мартин-Лёфу в духе Epigram и Agda. По пути появятся декларации типов, модули c FFI, algebraic data types и привычная некомбинаторная запись в виде сахара к комбинаторной.

Пока конечно, это мечты. Вот иллюстрация текущего прогресса по оптимизатору (бекенд для компиляции в Перл):
use hn;

__writeFile("firstOrLastHaskell.txt",
unlines(__filter(&{__flip2
(\&__member)}(fromList(readLines("config/namesFirst.txt"))),
readLines("config/namesLast.txt"))));
Сравните этот код с кодом из приведенного Вами поста:
use hn;

(&{(&{(__builtin2(\&__writeFile))}("firstOrLastHaskell.txt"))}(
(unlines((&{(&{(__builtin2(\&__filter))}((&{(flip(
(__builtin2(\&__member))))}((fromList((readLines("config/namesFirst.txt")))
)))))}((readLines("config/namesLast.txt"))))))));
Tags: compiler design, hn0
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 22 comments

Recent Posts from This Journal