Язык программирования Ficus для вычислений и не только

"Наш путь извилист, но перспективы светлые" Мао Цзедун

Здравствуйте, уважаемыее. Меня зовут Вадим Писаревский, я являлся лидером OpenCV (Open Source Computer Vision Library) на протяжении примерно 20 лет, и продолжаю участие в этом замечательном проекте. В этой статье я рад представить вашему вниманию результат другого своего проекта, над которым в фоне работаю уже много лет, а последние пару лет как минимум половину своего рабочего времени.

Краткая информация о языке

Ficus/Фикус это мульти-парадигменный язык программирования общего назначения, прежде всего функциональный, но также поддерживается императивная модель и некоторые объектно-ориентированные возможности. Главная "фишка" языка – это заточенность на обработку числовой и символьной информации. По сути, это язык для программирования разнообразных алгоритмов, от которых требуется высокая скорость работы и надежность при этом (например, алгоритмы компьютерного зрения и искусственного интеллекта по идее должны работать на самом разном железе, часто в условиях ограниченности вычислительных ресурсов. И не должны ломаться, желательно никогда). Компилятор Фикуса выдает на выходе код на языке Си неплохого качества, из которого можно получить готовое приложение, либо же скомпилировать в составе некоего более крупного проекта. Компилятор изначально был написан на OCaml, но уже почти как год переведен на сам Фикус. Все вместе, компилятор, стандартная библиотека, примеры, тесты и т.д. распространяются по лицензии Apache 2. В репозитории имеется небольшой учебник, распространяемый по лицензии Creative Common License.

Немного истории, или как меня угораздило взяться за новый язык

"Какой самый живучий паразит? Бактерия? Вирус? Кишечный глист? Идея. Она живуча и крайне заразна. Стоит идее завладеть мозгом, избавиться от неё уже практически невозможно." Кобб, фильм Inception

Считаю нужным с самого начала ответить на неминуемый вопрос "зачем?", ибо полностью согласен с Бобом Дэвисом, одним из создателей Intel VTune, а также автором самого первого инсталлятора OpenCV, который мне как-то сказал: "знаешь, если есть возможность обойтись без написания программы, лучше не писать – и ошибок не будет, и сопровождать не надо".

Началось проектирование языка примерно в 2011 году, когда мы готовили предложение в комитет Кронос по стандарту API компьютерного зрения OpenVX на базе OpenCV. Многие компании были заинтересованы в таком стандарте, чтобы потом предложить свои решения, прежде всего аппаратные, которые были бы дружественны пользователям OpenCV и более менее согласованы между собой по программным интерфейсам. С самого начала было понятно что OpenCV слишком большой и динамичный проект для стандартизации, поэтому искали некий базис операций минимального размера и при этом обладающий максимальными выразительными возможностями. Проблема была не только и не столько в выборе конкретного набора примитивных операций, но в определении способа составления из них более сложных алгоритмов обработки изображений и компьютерного зрения. Рассматривались следующие подходы:

• Библиотечный или последовательный — самый примитивный, т.е. тот, который предоставляет классический интерфейс OpenCV. Последовательно вызываем функции из предоставляемого набора. Если нужные функции отсутствуют, реализуем их самостоятельно и вставляем в середину. Этот подход сочетает необыкновенную простоту и большую гибкость с очень низкой эффективностью, поскольку каждая операция прокачивает все данные через кэши.

• Графовый — тот, который в итоге был выбран комитетом OpenVX, который в OpenCV реализуется в модуле G-API (graph API), и который сегодня также реализован в различных движках по запуску нейронных сеток. Подход заключается в том что реализуемый алгоритм представляется в виде направленного ациклического графа (DAG), вершины которого являются примитивными операциями. Такой граф может быть сформирован вручную или автоматически с помощью метода ленивых вычислений (который как раз и реализован в OpenVX и в OpenCV G-API). Коль скоро граф построен, его можно проанализировать, объединить некоторые операции вместе (т.е. осуществить слияние циклов), разбить массивы на блоки чтобы задействовать несколько ядер, возможно выполнить часть или все вычисления на GPU и прочих ускорителях. Эффективность качественных реализаций графового подхода в разы выше библиотечного варианта. Существенный недостаток такого подхода - невысокая гибкость. Как только алгоритм перестает выражаться с помощью доступного базиса операций, как только появляется динамическая логика, мы вместо одного графа получаем много мелких и эффективность подхода резко снижается. При этом очень много усилий тратится и ухищрений используется в попытках выразить нетривиальный алгоритм в виде такого графа.

• Наконец, языковой подход. Проектируется язык, либо domain-specific, либо общего назначения, который бы особенно эффективно работал с массивами. Пишется компилятор такого языка, как правило, JIT компилятор, который переводит алгоритмы в бинарный код, возможно с вызовом функций из runtime, выполняющих примитивные операции над блоками из обрабатываемых массивов, так что данные остаются в кеше. Эффективность максимальна, гибкость при правильном выборе операций и конструкций языка также достаточна. Недостатки - самая высокая сложность реализации среди представленных подходов, а также потенциально высокий накладные расходы, особенно в случае JIT-компилятора, ведь со своим приложением нужно поставлять и компилятор, и если он например базируется на LLVM - это десятки мегабайт. Тем не менее, популярные решения на базе этого подхода также имеются. Например это язык APL для вычислений вообще, до сих пор применяющийся в финансовой сфере, язык Halide для обработки изображений или фреймвок tvm для машинного обучения, созданный на основе кода Halide.

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

C++ и Python для OpenCV и что с ними не так

Возникает вопрос — зачем создавать новый язык, если есть быстрый C++ и удобный Python?

OpenCV изначально была написана на C, в 2009 году интерфейс был кардинально переделан на C++ по мотивам Matlab, прежде всего его всемогущих массивов. Прежде всего хотелось удобства обращения с массивами почти как в Matlab, чего в итоге и добились. В то же время, по мере роста размера и сложности библиотеки, по мере портирования алгоритмов на различные платформы, по мере повышения требований к производительности стали все больше проявляться следующие очевидные недостатки языка C++ как языка для реализации алгоритмов компьютерного зрения:

• отсутствие встроенного типа многомерных плотных массивов, из-за чего:

  • каждая библиотека реализует свой тип массивов (ну кроме std::vector<>, std::array<>), поэтому при совместном использовании нескольких библиотек нужно перегонять данные из одного формата в другой, желательно эффективно.

  • компилятор не в состоянии сделать глубокую оптимизацию циклов обработки массивов, включая слияние циклов, устранение промежуточных массивов, блочную обработку с параллельной обработкой разных блоков и т.д. Из-за этого, например, многие простые операции над массивами в OpenCV хороши только на этапе прототипирования, но совершенно не годятся для оптимизированных сложных алгоритмов.

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

• до появления стандарта C++ 20 отсутствие полноценной поддержки модулей. Даже сейчас поддержка модулей только-только появляется в компиляторах и есть различия от версии к версии.

• эффективный CPU код писать вручную кропотливо, хотя часто используются одни и те же приемы. Например, в одном из своих докладов я приводил пример, когда референсная реализация некоего фильтра на 70 строчек кода, работающая со скоростью 640x480@1FPS, была превращена в оптимизированную версию на 350 строчек кода работающую со скоростью 640x480@30FPS. То есть, не выходя за рамки C++ получилось разогнать код в 30 раз, но ценой усложнения реализации примерно в 5 раз. Особенно заметно бессилие 'оптимизирующих' и 'векторизующих' компиляторов C++ становится заметно в целочисленных вычислениях с пониженной точностью (int8, int16)

• отсутствие поддержки GPU на уровне языка. Экспериментальная поддержка есть в стандартах OpenMP и OpenACC, но о возможности реализовать надежные кросс-платформенные решения речи пока не идет. Есть OpenCL и CUDA, но их использование за рамками простых книжных примеров требует поистине экспертного уровня. При этом тренды в вычислениях очевидны, компьютерное зрение и машинное обучение скорее рано чем поздно полностью мигрируют на GPU и специализированные ускорители:

Таким образом, потребность в полноценном языке или хотя бы Domain-Specific Language (DSL) для компьютерного зрения и машинного обучения становится очевидной, хотя бы даже для упрощения запуска алгоритмов на GPU.

Часто выбирают вариант с DSL, который встраивают в один из распространенных языков, типа C++, C# или Python. Компилятор для DSL и сделать проще и "продать" проще, т.к. не надо пересаживать людей с основного языка который используется для продукта, но:

1. Гибридный код сложнее отлаживать.

2. В случае JIT компилятора появляется накладной расход при распространении конечных приложений, а возможно и лицензионные вопросы.

3. В случае использования Python как основного языка также нужно распространять Python, мириться со низкой скоростью и недостаточным контролем за типами на стадии компиляции (хотя опциональная типизация потихоньку пробивает себе дорогу).

Конкретизация идеи языка

Таким образом, после некоторых размышлений было решено сделать:

• полноценный язык, чтобы не было необходимости использовать два языка в программе. Вместо постепенного расширения синтаксиса и семантики DSL языка (а в подобных расширениях необходимость возникает примерно в 100% случаев) было решено сразу сделать универсальное решение, пусть и не самое быстрое, и по мере необходимости добавлять распознавание особых паттернов в компилятор (то есть, делать его умнее) и добавлять новые интринзики для увеличения скорости полученного кода.

• с автоматическим управлением памятью

• с полноценной поддержкой массивов

• с полноценной поддержкой модулей

• настолько же быстрый как C++, в потенциале быстрее, за счет автоматического портирования некоторых циклов на GPU

• настолько же удобный и выразительный как Python, хоть пока без интерактивного режима, к сожалению

• со строгой статической типизацией, чтобы одновременно устранить две главные проблемы Python

• с генерацией на выходе кода на C/C++, чтобы с одной стороны упростить себе жизнь и переиспользовать все существующие компиляторные технологии, а с другой стороны не зависеть полностью от такого монстра как LLVM. Дополнительное преимущество получилось в том что полученный код можно включить в состав более крупного проекта на C/C++.

• с легким runtime, в отличие от C#, Java и даже Python. В частности поэтому отказался от полноценного сборщика мусора в пользу механизма подсчета ссылок.

Это были общие, вполне логичные решения. Оставалось определиться, как это все должно выглядеть, какие будут языковые конструкции, какой синтаксис. Изначально идея была взять за основу любимый Python, а возможно и одну из его вариаций, типа Cython, встроить туда поддержку многомерных массивов, и дело сделано! Я придерживался этой идеи пока случайно не познакомился с языками OCaml и StandardML, а также вообще с функциональным программированием, про которое я конечно слышал, и даже в свое время немного изучал Lisp, но глубоко не копал. Теоретически эти языки обладали всеми нужными свойствами кроме первоклассной поддержки многомерных массивов (выходной язык компилятора и метод сборки мусора относится скорее к деталям реализации, так что они не считались фундаментальными недостатками), и кроме этого синтаксис был слишком непривычен для меня как для пользователя C++ и Python, хотя автоматический вывод типов позволяет писать строго-типизированные программы с минимумом явных аннотаций, тем самым немного приближая код к Python-стилю.

Синтаксис, как оказалось впоследствии, довольно несложно переделать на что-нибудь более современное, и даже по мере развития проекта менять один синтаксис на другой, даже особо не затрагивая т.н. Abstract Syntax Tree (абстрактное древовидное представление синтаксиса, генерируемое парсером).

Оставался вопрос с поддержкой массивов.

Array comprehensions (буду благодарен за перевод термина)

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

К сожалению, с массивами так не получается. В компьютерном зрении и в обработке изображений должна быть возможность быстро, очень быстро прочитать и поменять значения отдельных элементов массива, отдельных пикселей на изображении и т.д.

С инкрементальными небольшими изменениями массивов понятно. Но что насчет довольно типичных операций, когда мы вычисляем все элементы выходного массива. Можно ли это сделать с помощью какой-нибудь красивой функциональной нотации?

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

val A = load_gray_image(imagename)
val (h, w) = size(A)
val B: uint8 [,] =
    make_array_uninit((h-2, w-2)) // гипотетическая функция
                                // создания неинициализированного
                                // массива
// применяем фильтр [|0, 1, 0; 1, 4, 1; 0, 1, 0|]/8
for y <- 1:h-1
  for x <- 1:w-1 {
     B[y-1, x-1] = uint8((A[y-1,x]+A[y,x-1]+A[y,x]*4+
                          A[y,x+1]+A[y+1,x])>>3)
  }

Во-первых, B создается неинциализированным, что ненадежно. А если его инициализировать, то это впустую потраченное время. Во-вторых, нужно правильно посчитать размер выходного массива. Если ошибемся в большую сторону, получим ноль диагностики и неправильную работу. Во-третьих, компилятор должен понять что каждый элемент B вычисляется один и только один раз и независимо от других, поэтому цикл можно векторизовать, в-четвертых, запись немного многословна для такой простой операции.

Изучение вопроса привело к языкам SISAL и SAC (Single-Assignment C). В этих языках присутствует понятие array comprehensions, которые выглядят как циклы for, но тело цикла вычисляет отдельный элемент массива результирующего вектора. Прямо как list comprehensions в Python, но только многомерные. В результате, тот же самый код теперь можно записать как:

val A = load_gray_image(imagename)
val (h, w) = size(A)
// применяем фильтр [|0, 1, 0; 1, 4, 1; 0, 1, 0|]/8
val B = [| for y <- 1:h-1 for x <- 1:w-1 {
     uint8((A[y-1,x]+A[y,x-1]+A[y,x]*4+
            A[y,x+1]+A[y+1,x])>>3)
      }|]

Т.е. array comprehension выглядят как обыкновенные циклы for, но только они завернуты в скобки [| |], что позволяет их правильно классифицировать и обработать. С одной стороны, массивы по-прежнему остаются изменяемыми (мутабельными) структурами данных. С другой стороны, благодаря comprehensions некоторые операции работы над массивами можно выразить в функциональном стиле, используя принцип "single-assignment" - то что так обожают все оптимизирующие компиляторы. Также уменьшается простор для возможных ошибок и опечаток. В частности, тут B создается нужной размерности, размера и типа, элементы вычисляются гарантированно последовательно и независимо, сама конструкция синтаксически гарантирует инициализацию каждого элемента без пропусков и повторений. Для автоматического векторизатора такую нотацию гораздо проще обработать.

Заодно, упомянем про еще одно интересное свойство Фикуса. С одной стороны, Фикус гарантирует проверку на диапазон при доступе к элементам массива. С другой стороны, при анализе этого цикла компилятор увидит что доступ к массиву A обеспечивается с помощью т.н. "афинных" (т.е. линейных) операций над счетчиками циклов, поэтому он просто возьмет и для каждой из 5 операций доступа возьмет крайние значения индексов и до цикла проверит что они в пределах массива. Если нет, будет брошено исключение. При этом проверки на диапазон внутри цикла будут полностью удалены. Это уже реализованная оптимизация, которая стала реальной поскольку компилятор знает про многомерные массивы. В современном C++ такая оптимизация невозможна.

Оптимизирующий компилятор Фикуса. Пример со слиянием циклов

Вообще, несмотря на младенческий возраст, компилятор Фикуса гораздо более продвинут чем компилятор Python и даже местами умнее C++.

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

• устранение неиспользуемого кода

• замена хвостовой рекурсии на циклы

• вынос инвариантов цикла за его пределы

• замена некоторых операций над матрицами, например A'*B+С, на специальные интринзики (gemm в данном случае)

• подстановка тел небольших функций вместо их вызова

• раскрытие блоков кода, вложенных в другие линейные блоки кода (flatten). Часто полезно после подстановки функций.

• слияние циклов

• устранение избыточных проверок на диапазон при последовательном обращении к элементам массива внутри цикла (см. описание выше)

• замена константных выражений на их результаты, устранение недостижимых веток в условных операторах

отдельно после всех этих оптимизаций применяется вынос вложенных и lambda-функций наверх и остальная подготовка к генерации финального С кода.

Давайте рассмотрим на примере как работает такая многостадийная оптимизация:

/* обобщенная реализация операции поэлементного сложения
   для массивов произвольной размерности из стандартной библиотеки.
   здесь 't1 [+] означает
      "массив какой-то (но определенной)
       размерности из элементов типа 't1",
   't1 означает обобщенную переменную типа, по аналогии с
       "typename t1" в C++.
*/   
operator + (A: 't1 [+], B: 't2 [+]) =
  [| for a <- A, b <- B {a+b} |]

// обобщенная реализация операции поэлементного умножения
// элементов массива слева на скаляр из стандартной библиотеки
operator .* (a: 't, B: 't [+]) =
  [| for b <- B {a*b} |]

// инициализируем массивы явным перечислением их элементов
val A = [| 1., 2., 3. |]
val B = [| 5., 6., 7. |]
// используем операции над массивами
val C = A + 0.5.*B

Как мы видим, некоторые даже самые простые операции работы над массивами не спрятаны внутри компилятора, а реализованы на самом языке в стандартной библиотеке.

Компилятор преобразует код следующим образом (некоторые преобразования здесь сгруппированы вместе для краткости изложения):

• инстанциируем обобщенные реализации для нашего случая, вводим имена для промежуточных результатов

operator + (A: double [], B: double []) = ... // тела не изменяются
operator .* (a: double, B: double []) = ...

val A = ...
val B = ...
val temp1 = (.*)(0.5, B)
val C = (+)(A, temp1)

• поставляем функции inline. Поскольку функции после подстановки больше не используются, мы их удаляем

val A = ...
val B = ...
val temp1 = [| for b <- B {0.5*b} |]
val C = [| for a <- A, t <- temp1 {a+t} |]

• сливаем циклы. Компилятор замечает что:

  • temp1 это временное значение, которое является результатом array comprehension. Тело array comprehension при этом — 'чистое выражение' без побочных эффектов.

  • temp1 используется лишь один раз, причем внутри другого comprehension

  Тогда можно заменить итерацию по temp1 на итерацию по массивам из которых получается temp1, а в тело цикла подставить выражение для вычисления элементов temp1.

val A = ...
val B = ...
val C = [| for a <- A, b <- B {val t = 0.5*b; a+t} |]

Основные свойства языка

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

1. Синтаксис языка являет собой гремучую смесь C/C++, Python, Ocaml, Scala, Swift, Rust и возможно других языков, тем не менее, если рассматривать язык по слоям, то:

   • на уровне лексики, операций и выражений мы имеем С-подобный язык.

   • также есть препроцессор, напоминающий таковой в C/C++, но более простой и думается более безопасный. Задачу условной компиляции он вроде как решает.

   • на уровне управляющих конструкций, стиля описания типов, стиля определения функций, исключений и т.д. язык идеологически напоминает Ocaml и StandardML, с той большой разницей что вместо let-in цепочек мы используем блоки, внутри которых можно свободно чередовать декларации с выражениями. Но фундаментально Фикус - это функциональный язык, то есть, любая управляющая конструкция, включая 'if' и 'match', это выражение, которое может быть вложено в другие выражения.

   • блоки оформляются как в Swift, Rust и Go разве что нет ограничений где писать '{' - где хотите, можно переносить на новую строчку, можно не переносить.

   • система модулей построена по лекалам Python, т.е. она сильно отличается от Ocaml и StandardML.

2. Массивы, списки, вектора, строки, структуры, кортежи, типы-суммы - first-class citizens. Компилятор все про них знает и адекватным образом конструирует, копирует, разрушает, передает в функции и хранит в контейнерах. Копирование любой структуры данных (operator =), передача ее в функцию или возвращение из функции, независимо от количества элементов это O(1) операции. Для некоторых структур, например массивов, доступно также глубокое копирование с помощью функции copy(). Пользователь не может переопределять поведение '=' или деструкторов.

3. Почти нигде не используется boxing/unboxing типов. Есть пара небольших исключений, но они никак не влияют на объем занимаемой памяти или скорость обработки данных. Практически можно считать что boxing/unboxing не используется.

4. Реализована довольно большая часть семантики языков OCaml и StandardML, за исключением их системы модулей. Также OOP реализовано немного по-другому чем в OCaml.

5. Подобно C++ и Java, и в отличие от Python, OCaml и StandardML доступно полноценное переопределение функций, т.н. ad-hoc полиморфизм. Благодаря этому не нужно придумывать 100 вариантов названия функции print() и прочих базовых операций, как и не нужно устраивать в подобных функциях гирлянду из проверок if typeof(a) == t1 {...} else if ... (и не получится, ввиду отсутствия boxing/unboxing типов).

6. Кстати о print(), string() и прочих. Для практически всех определенных пользователем типов доступны из коробки функции печати, преобразования в строку и сравнения. Исключение составляют варианты (и то сравнивать на равенство/неравенство их можно). Если автоматически генерируемая реализация не устраивает, можно переопределить.

7. Для массивов доступны многие базовые операции из Матлаба и Python+numpy. При этом, в отличие от этих языков, циклы по массивам очень быстры. Так что, если чего-то не хватает, гораздо проще это эффективно реализовать.

8. Для строк, списков и векторов также доступны многие базовые операции из OCaml, Python и остальных подобных языков.

9. Строки используют Unicode, идентификаторы в программе могут включать Unicode-символы категорий 'буква' и 'цифра'.

10. На выходе генерируется C или опционально C++ код. Из программ на Фикусе можно вызывать функции на C/C++, и соответственно наоборот (например, можно писать на Фикусе callback'и для C библиотек).

11. Отдельная фишка - можно реализовывать тело Фикус-функции на C/C++. То есть, по аналогии с C/C++, где есть встроенный ассемблер, здесь есть встроенный C/C++. Это еще больше упрощает подключение сторонних библиотек и реализацию некоторых низкоуровневых функций стандартной библиотеки.

12. Реализованы многие, но не все фичи функциональных языков типа Ocaml: неизменяемые значения и структуры данных, вложенные и безымянные функции, автоматический вывод типов, pattern-matching. Не реализованы ленивые вычисления.

13. Реализованы многие, но не все фичи императивных языков. Есть циклы for, while, есть операторы break, continue, return. Есть изменяемые значения, они же переменные (var), можно отдельные поля структур объявлять изменяемыми (что снижает эффективность, но иногда оно того стоит).

14. Отдельной строкой: каждое значение или переменную в Фикусе нужно обязательно явно инициализировать.

15. Реализована обработка исключений, как в Ocaml/StandardML.

16. Реализованы некоторые фичи объектно-ориентированных языков. Есть классы и есть интерфейсы. Интерфейсы можно наследовать друг от друга, классы нельзя (то есть, каждый класс - это final класс в терминологии Java). Классы построены на базе структур. Классы могут реализовывать ноль или более интерфейсов. В последнем случае можно делать преобразование класса к интерфейсу и обратно, можно преобразовывать один интерфейс к другому (аналог dynamic_cast<>() в C++ или QueryInterface() в COM).

17. Доступны обобщенные функции и типы.

18. На уровне синтаксиса, компилятора и стандартной библиотеки есть поддержка многопоточности. Просто нужно поставить @parallel перед for, и @sync перед блоками, которые нужно исполнить атомарно и эксклюзивно. Более сложные концепции типа корутин, агентных моделей, асинхронного выполнения и прочего пока не реализованы.

Стандартная библиотека постепенно пополняется, в настоящий момент она включает:

1. базовые операции над числами, кортежами, структурами, строками, списками, векторами, массивами.

2. чуть менее базовые операции над строками, включая регулярные выражения.

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

4. базовые математические операции, генерация случайных чисел

5. функциональные и императивные ассоциативные контейнеры (на базе деревьев и хэш-таблиц, соответственно)

6. операции над файлами, системные вызовы

7. чтение/запись .json файлов

8. простой движок для реализации unit-тестов

9. частичные обертки для библиотеки OpenCV

Производительность

Вот небольшое сравнение текущей версии Фикуса c C/С++ и Python на нескольких бенчмарках из проекта https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html. Исходный код всех этих бенчмарок на Фикусе можно найти в репозитории по ссылке ниже.

В строке C/C++ для бенчмарок приведены две цифры. Первая цифра - для самой быстрой доступной реализации на данном языке, а в этом проекте разработчики заходят достаточно далеко в погоне за максимальной скоростью. Вторая цифра приведена для достаточно эффективной, но все еще читаемой реализации без использования встроенного ассемблера и специальных интринзиков (хотя и с распараллеливанием, когда это имеет эффект). Для Python приведено время самой быстрой реализации.

Статус и планы

"Мы строили-строили, и наконец построили!" Че

"После сборки обработать напильником." Из инструкции по сборке экспортного советского танка

1. Язык спроектирован, компилятор реализован и самораскручен. Есть компактный runtime, небольшая стандартная библиотека, написан учебник. На момент написания статьи версия языка - 1.0-alpha.

2. Одна из основных киллер-фич языка - продвинутые array comprehensions. Благодаря им нотация получается гораздо более компактной и удобной для анализа, а различные оптимизирующие преобразования над такими конструкциями можно осуществлять проще и безопаснее.

3. Реализовано около сотни unit-тестов, также при начальной сборке компилятор собирает сам себя. Таким образом, есть некий sanity-check и он успешно проходится.

4. Генерируемый код получается достаточно эффективным, хотя пока и отстает от вручную оптимизированного С кода, иногда заметно, что впрочем ожидаемо.

5. Обернута часть библиотеки OpenCV, таким образом язык можно понемногу начинать использовать для написания небольших программ, для экспериментов с компьютерным зрением.

6. Благодаря встраиваемым фрагментам на C/C++ подключать новые библиотеки, особенно после небольшой тренировки, достаточно несложно.

Вместе с тем, определенно есть куда расти:

1. Есть определенные шероховатости в реализации компилятора, например обработка частичных специализаций обобщенных/шаблонных функций, работа с вложенными модулями, компиляция некоторых проектов на Windows.

2. Обработка различных особых случаев (corner cases) в компиляторе и в стандартной библиотеке возможно недостаточна и определенно не тестируется должным образом.

3. Вообще, покрытие тестами достаточно слабое

4. Стандартная библиотека далека от завершенности. На этот счет имеется отдельный тикет в багтрекере.

5. Было бы неплохо реализовать более совершенный пакетный менеджер, например как в Python или как в Rust.

6. Скорость генерируемого кода пока далека от идеала. Можно улучшать скорость для CPU, можно пробовать реализовать экспериментальный запуск циклов на GPU. По крайней мере, бенчмарки mandelbrot.fx и spectralnorm.fx можно попробовать серьезно разогнать.

7. Было бы интересно попробовать сделать экспериментальную реализацию небольшого движка для запуска нейронных сеток на Фикус. Это будет еще одной хорошей проверкой для самого языка, качества компилятора и полноты стандартной библиотеки.

8. Инструментальная поддержка языка пока очень слабая.

   • Было бы неплохо реализовать Language Server Protocol для полноценной поддержки языка внутри Visual Studio Code, VIM и других совместимых с этой технологией редакторов.

   • Необходимо как-то решить вопрос с отладкой программ на Фикусе. Пока предлагается два решения: 1) использовать отладочную печать, 2) с помощью cmake сгенерировать проект из сгенерированных Фикусом .c файлов, открыть его в IDE и запустить отладчик. Пример скрипта для такого способа прилагается.

9. В настоящий момент реализована только сборка приложений (режим 'app'). Возможно следует переработать систему сборки и обеспечить полноценный режим компиляции отдельных модулей. Особенно это будет полезно и удобно если модули большие и зависят от сторонних C/C++ библиотек.

Благодарности

Благодарю:

• Shenzhen Institute of Artificial Intelligence and Robotics for Society (AIRS), где мне посчастливилось некоторое время поработать и где мне дали достаточно свободы для реализации данного проекта.

• Отдельная благодарность Yu Shiqi за приглашение меня в AIRS, в OpenCV China и всестороннюю поддержку

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

• Ребят с прежней работы (из компании Itseez, ныне ставшей частью Нижегородского центра Intel) за обсуждение деталей дизайна и помощь в некоторых моментах на ранних стадиях работы над проектом.

• Авторов различных open-source проектов, чьи результаты были с удовольствием использованы (некий частичный список помещен в конце головного README.md в корне проекта на github).

Также, заранее благодарю читателей этой статьи, и особенно тех кто попробует Фикус, за любые комментарии и предложения по поводу языка, а может и за помощь, кто знает.

Ссылки:

1. Репозиторий Ficus: https://github.com/vpisarev/ficus. В подкаталоге doc есть учебник в формате PDF. В подкаталоге examples можно найти примеры.

2. MinCaml: https://github.com/esumii/min-caml. Микро-компилятор для очень маленького подмножества Ocaml, который вдохновил на написание компилятора Фикуса

3. OpenCV: https://github.com/opencv/opencv/wiki

4. Halide: https://halide-lang.org

5. TVM: https://tvm.apache.org

6. "Image Algebra: An Overview". G. X. Ritter et al https://www.researchgate.net/publication/222760582_Image_algebra_An_overview.О том как можно выразить различные алгоритмы обработки изображений с помощью некоей формальной нотации. Есть дальнейшая работа этого же автора на тему алгоритмов компьютерного зрения.

7. Functional Approach To Programming. Guy Cousineau, Michel Mauny. https://www.cambridge.org/core/books/functional-approach-to-programming/27F7047FBF0962D02161E79B90BD7FD2. Выдающаяся книжка о том что такое функциональное программирование, и как начать думать и писать в таком стиле.