November 9th, 2007

Book

HN0 теперь с оптимизатором

Дописал к моему компилятору маленький peephole-оптимизатор на два правила:
  • вызовы функций более эффективны - currying используется только там, где он нужен;
  • функция flip создает меньше замыканий.
Теперь на очереди стандартная библиотека HN0 для С++.
Book

Прогресс 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.

Collapse )
Book

Расставил теги

Расставил теги во всех записях за 2007 год. Наслаждайтесь тегами hn0 (все посты по моему языку) и более широким сompiler design (все посты, связанные с преимуществами, предоставляемыми продвинутыми языковыми возможностями - функциональностью, ссылочной прозрачностью и мощными системами типов).
Book

О комбинаторе W/join, инкапсулирующем всю нелинейность

Открытие о том, что комбинатор W - единственный нелинейный комбинатор, и этот факт можно использовать для оптимизации, получилось случайно - vag_vagoff  прислал пример, нереализуемый с помощью комбинаторов BCIK (все они - линейные!):
testfun a = a + x where x = sqrt a
До этого момента HN0 прекрасно обходился без W, I и K, голыми BC. В необходимости I и K я до сих пор не уверен, всё еще жду примера, когда они не могут быть устранены оптимизатором. Т.е., я считаю, что \a b -> a всегда может быть заменена на a и  \a -> a (комбинатор I, id) всегда может быть заменена на a.

В BCW на HN0 данный пример выглядит так:
testfun = join i where
	i = j sqrt where
		j = o +
Тут я полагаю, что реализовывать +, sqrt и числа искусственными конструкциями в духе нумералов Чёрча, для которых вполне могут понадобится искусственные же комбинаторы I и K, не нужно.

По причине искусственности комбинатора S я сразу же отверг базис SK. Вы же не оперируете при покупке картошки аксиомами Пеано, и не строите условных операторов исключительно с помощью штриха Шеффера.

Необходимость flip была мне очевидна - привязку второго аргумента member в оригинальном примере без него сделать нельзя было. В процессе разработки библиотеки выяснилось, что о нужен тоже, и o и flip не реализуются друг через друга.

У меня получалось писать довольно сложные программы, несмотря на убогость языка и отсутствие какой-либо поддержки для рекурсии, условных конструкций и разделения данных. В связи с этим Ваг и сконструировал серию примеров, требующих обязательного разделения. Общая рекурсия, судя по Epigram и Martin-Lof Type Theory, мне никогда и не понадобится. А вот с if действительно загвоздка, не хочется вычислять обе ветки. Буду думать, как это впишется в текущий компилятор.
Book

Практичность HN0 (бизнес-план)

Тратить 15 лет на создание такой чудовищно непрактичной хуйни, как Haskell, Clean, ML или Epigram у меня нет желания. Поэтому я пошел другим путем. Сначала докажу, что можно построить практичную (переплёвывающую С++ в области высокопроизводительных и системных приложений) систему на основе современных технологий, а затем привлеку людей и финансирование, чтобы догнать тот же GHC скажем, за год. Итак...

HN+inf - будущий архипрактичный язык, использующий языки ...HN+2, HN+1, HN0 в качестве бэкенда. Область применения - сегодняшняя область применения С++. Это:
  1. встраиваемые системы (плееры, мобильные телефоны),
  2. системы реального времени (управление технологическими процессами, работа с датчиками-сервоприводами)
  3. игры
  4. системное ПО (операционные системы, серверы баз данных, серверы приложений, веб-серверы, виртуальные машины других языков, компиляторы)
  5. небольшие утилиты (традиционно распространяемые как shareware и пишущиеся на С++, в духе winzip, Mozilla или winMd5Sum)
  6. мультимедиа (кодеки, все продукты Adobe, фотореалистичный 3D-рендеринг)
  7. научные вычисления (HPC)
Каким требованиям должен удовлетворять новый язык для того, чтобы кто-то согласился отдать деньги или время на разработку? Язык должен быть перспективным, high-tech, чтобы можно было посулить поднятие эффективности в разы и поднять маркетинговый hype. Должна быть возможность делать на этом деньги (крупным инвесторам может хватить и возможности делать репутацию!). Никто не согласится платить деньги за те же яйца, только в профиль.
  1. Язык действительно должен обеспечивать более высокую продуктивность программиста по сравнению с С++.
  2. Язык не должен уступать существующим решениям по производительности приложений (базок данных и других нетребовательных корпоративных приложений, традиционно пишущихся на С#/Java нет в списке областей применения, не говоря уже о Perl/Ruby/Python/PHP!)
  3. Приложения должны иметь небольшой footprint (требуется в областях 1, 5)
  4. Должна быть поддержка (инструменты, документация, семинары, учебники, on-site consulting, развитое тематическое сообщество - you name it)
  5. Должна быть бесшовная интеграция со старым кодом (читайте: написанным на С++)
3 требованию удовлетворяют только С++ и Fortran (последний - из-за того что был разработан исключительно для 7 области, где используется в слегка подсахаренном виде и поныне). 3 требование в сочетании с 4 - только С++. Всем остальным требованиям удовлетворяет любой мейнстримовый язык, но скажем Haskell запросто переплевывает мейнстрим по первому пункту.

Итого, рецепт такой:
  • Берем идеи продвинутых немейнстримовых языков
  • Доводим производительность и footprint до уровня С++
  • Обеспечиваем link compatibility с С++ для всех компиляторов и платформ (включая дешевый двухсторонний маршаллинг вызовов!)
  • Обеспечиваем поддержку
  • Обеспечиваем маркетинг
При неограниченном бюджете в этом рецепте провалиться может только второй и последний пункты. Соответственно, я взялся за первые два пункта (которые бессмысленны один без другого) и пытаюсь создать proof-of-concept систему без повторной реализации того, что и так уже сделано в Haskell или Epigram. Итого, HN0 пытается ответить на такой вопрос:
  • Можно ли обеспечить в высокоуровневом чисто функциональном языке производительность низкоуровневого императивного С++?
Отсюда и его неудобство для конечного пользователя - я откладываю реализацию тех фич, которые никак не повлияют на производительность. Для начала я реализую "голый" лямбда-калкулус максимально эффективно (у меня есть идеи). Если эффективности не хватит, то буду последовательно реализовывать линейные типы и типы с  зависимостями, так как более строгая типизация предоставит более сильные инварианты оптимизатору. Структуры, которые можно эффективно представить синтаксическим сахаром, и которые не повлияют на эффективность - мне на данном этапе не интересны, не хочется делать лишнюю работу если потом окажется что все мои идеи - хуйня...

Да, еще важный вопрос - откуда возьмутся деньги? Ответ - поддержка, продажа инструментария. Часть инструментария должна быть бесплатной, с особо расслабленными лицензиями для некоммерческой и академической разработки. Необходимость поддержки также исключает возможность базарной разработки. Возможно, будет гибридная модель, наподобие той, что пытается сделать QNX. Но сейчас слишком рано об этом говорить.
Book

О ленивости

Возьмем такой пример (за порядок аргументов не отвечаю, главное что смысл был ясен):
f n = fold1 (+) [1..n]
Функции семейства fold строги по своим списковым аргументам, так как их останавливаемость не зависит от нормального или аппликативного порядка редукции, и передача жопы вместо списка приведет к жопе _|_.

Но будете ли Вы рады, если f 123456789 выделит в ходе предвычисления списка 482 мегабайта памяти? Для эффективного вычисления данной функции нужно то, что я называю словом "ленивость". Нормальный порядок редукции - это никакая не ленивость.

Например, я могу передать в LISP с аппликативным порядком какую-нибудь функцию makeList 1 n которая вернет stream, и всё нормально будет работать и ничего не есть, несмотря на полное отсутствие нормального порядка редукции.

Есть ли литература именно по ленивости в таком, узком смысле этого слова?