Эзотерический язык, транслирующийся в шаблоны C++

Шаблоны C++ — полный по Тьюрингу язык, на котором можно писать compile-time программы. Только вот синтаксис рассчитан на описание параметризованных типов и слабо приспособлен к ясному выражению чего-то более сложного. В этой статье рассмотрим, как типы и шаблоны становятся значениями и функциями, а также узнаем, к чему привела попытка автора создать свой функциональный язык, транслирующийся в шаблоны C++. Для прочтения текста знания в области функционального программирования почти не требуются.

Как это работает?

Здесь мы заложим основные кирпичики для построения из шаблонов программы этапа компиляции. Для тех, кто мало знаком с функциональным программированием — опишем простым языком некоторые необходимые понятия. Разобрав базовые вещи, мы будем готовы перейти к новому языку, его синтаксису, возможностях и проблемах. Желающие сразу перейти сразу к главному, могут проскроллить до зелёной картинки рядом с повторным появлением заголовка статьи.

Честно говоря, пару лет назад я порывался написать сюда пост про объяснение принципов работы compile-time программ на примере алгоритма смены приоритетов операторов в выражениях (т.е. реализовал варианты для compile-time и run-time алгоритма, с помощью которого можно было выражение «пересобрать» с альтернативными приоритетами и посчитать как , а не ).

Я уже почти дописал длинную статью с картинками и UML-диаграммами, но вдруг понял, что на хабре настолько часто рассказывали про метапрограммы, что это уже попросту никому не интересно. Тем более, что для практического использования добавили constexpr, а мне хотелось остаться в области извращённых развлечений и использовать минимум возможностей языка. Замечательные статьи Жизнь во время компиляции от HurrTheDurr и Интерпретация во время компиляции, или Альтернативное понимание лямбд в C++11 от ilammy (вторая — более хардкорная и без using template с constexpr) описывали практически всё, что извращённому уму нужно было знать. В итоге я оставил статью в черновиках, но не оставил желания метапрограммировать. И сегодня я возвращаюсь с заново написанным текстом и новыми идеями.

Если, несмотря на все мои старания, читателю всё ещё будет трудно воспринимать материал, рекомендую прочитать указанные статьи, а вдогонку — Мягкое введение в Haskell (часть 1, часть 2) от Пола Хьюдака и др. в переводе Дениса Москвина и Лямбда-исчисление на JavaScript от ibessonov. Всё это в какой-то степени повлияло на автора, может и на читателя повлияет?!

Метазначения и метафункции

Шаблоны классов — это, в некотором смысле, функции от типов, которые принимают и возвращают типы. Соответственно, шаблоны становятся метафункциями, а типы и целые числа — метазначениями. Например, метафункция std::vector принимает метазначение T и возвращает метазначение std::vector<T>. Важно, что у метазначения есть набор метаполей (с точки зрения C++ — вложенные классы, псевдонимы типов, статические константные поля), с помощью которых можно сделать самое интересное.

Можно выделить одно метаполе, например value, и понимать его как значение, которое возвращает метафункция. Метафункции над целыми числами запишутся довольно просто:

template <int x>
struct square {
  static const int value = x * x;
};

Вызывается применяется, как говорят в ФП, метафункция следующим образом: square<5>::value.

Но целые числа — это обычные значения, для работы с которыми достаточно и простого C++, а потому было бы несколько неспортивно использовать их в метавыражениях. Настоящее честное метазначение — это тип. Самый простой способ создать его — объявить структуру:

struct One;
struct Zero;

С точки зрения C++ one и zero только объявлены и практически бесполезны. Достаточно ли этого? Да. Чему же тогда они равны и как их использовать? Равны они, что важно, только самим себе. Это своего рода абстрактные символы, которые можно задействовать в символьных вычислениях (почти как в Mathematica и др.). Метапрограмма будет вычислять значения метавыражений различной сложности. Рассмотрим сначала эти выражения, а несколько позже займёмся интерпретацией символов и выводом результатов на экран.

Для нуля и единицы как булевых значений естественным будет написание функций NOT, AND и OR. Рассмотрим метафункцию отрицания:

template <typename T>
struct Not {
  typedef Zero value;
};

template <>
struct Not <Zero> {
  typedef One value;
};

Not принимает некоторое значение и возвращает единицу, если это значение — ноль. Во всех остальных случаях она возвратит ноль. Таким образом, за счёт специализации шаблонов, мы имеем паттерн-матчинг (сравнение с образцом) в зачаточной стадии: можем описывать отдельно поведение функции для одного или нескольких аргументов, имеющих конкретные значения, а компилятор C++, отметив соответствие параметров шаблона одному из образцов, подставит нужную специализацию. Пользуясь этим, мы могли бы уже написать что-то рекурсивное (например факториал, разделив описание на fac<0> и fac<всё остальное>).

Список

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

template <typename h, typename t>
struct Cons {
  typedef h head;
  typedef t tail;
};

struct Nil;

Cons в ФП — функция, конструирующая список из первого элемента (головы) и списка остальных элементов (хвост). Обычному списку будет соответствовать Cons<one, Cons<two, Cons<three, Nil>>>. Поскольку для работы со списком нужно уметь получать его составные части, мы сделаем Cons многозначной функцией, возвращающей голову (Cons<...,...>::head), и хвост (Cons<...,...>::tail). Любители ООП могут представить, что Cons — это конструктор, а head и tail — геттеры. В ФП все присваивания заменяются на вызов применение функции с изменёнными аргументами, поэтому сеттеров и их аналогов здесь не будет.

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

// отрицание непустого списка
template <typename list>
struct negate {
private: // инкапсулируем промежуточные вычисления
  typedef typename list::head h; // голова
  typedef typename Not<h>::value not_head; // отрицание головы
  typedef typename list::tail t; // хвост
  typedef typename negate<t>::value not_tail; // отрицание хвоста
public:
  // список из отрицаний элементов - это отрицание головы,
  // соединённое с хвостом отрицаний
  typedef Cons<not_head, not_tail> value;
};

// отрицание пустого списка
template <>
struct negate <Nil> {
  // пустой список - сам себе отрицание
  typedef Nil value;
};

Тут оказывается, что Haskell не так страшен, как его малюют. Всё то же самое выглядит настолько просто, что не грех добавить для наглядности примеры на этом языке. Для неподготовленного читателя отметим основное отличие от C++ и школьной математики: в Haskell аргументы разделяются пробелами и не группируются в скобках. Т.е. будет записано в Haskell как f (x+y) (g y) z.

-- список - либо слитые голова и хвост (причём хвост - сам список),
--          либо пустота
data List a = Cons a List | Nil

-- хелперы для получения головы и хвоста
head (Cons x _) = x -- возвращает голову
tail (Cons _ xs) = xs -- возвращает хвост

-- отрицание списка
negate (Cons x xs) = Cons (Not x) (negate xs)
negate Nil = Nil

В отличие от строго типизированных Haskell и C++, в языке шаблонов действует утиная типизация. negate<One>::value, конечно, не сработает, но если One будет иметь метаполя head и tail, он вполне подойдёт. Впрочем, пока negate<One> не «разыменовали» с помощью ::value, программа продолжает работать компилироваться.

Функции высшего порядка

В функциональных языках функции — такие же значения. Так, можно написать функцию высшего порядка — которая принимает функцию в качестве аргумента или возвращает функцию. Например, поэлементное преобразование списка осуществляется с помощью ФВП map:

-- Преобразованная голова соединяется с преобразованным хвостом
map f (Cons x xs) = Cons (f x) (map f xs)
-- Пустой список преобразовывать не нужно
map f Nil = Nil

STL содержит такое преобразование под именем std::transform. В нашем же языке метафункция map объявляется с помощью параметризации шаблона шаблоном:

// преобразование непустого списка
// f - шаблон с одним аргументом - унарная метафункция
template <template <typename> class f, typename list>
struct map {
private:
  typedef typename list::head h; // голова
  typedef typename f<h>::value new_head; // преобразованная голова
  
  typedef typename list::tail t; // хвост
  typedef typename map<f, t>::value new_tail; // преобразованный хвост
public:
  // Преобразованная голова соединяется с преобразованным хвостом
  typedef Cons<new_head, new_tail> value;
};

// преобразование пустого списка
template <template <typename> class f>
struct map<f, Nil> {
  // пустой список преобразовывать не нужно
  typedef Nil value;
};

В качестве f сюда можем подставить описанную ранее функцию Not и посчитать список отрицаний:

typedef map<Not, Cons<One, Cons<One, Cons<Zero, Nil>>>>::value list;
// list эквивалентно Cons<Zero, Cons<Zero, Cons<One, Nil>>>

Операции именования выражений

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

Начиная с C++11 можно использовать псевдонимы типов и шаблонов, чтобы задавать значения и функции через известные выражения:

using x = Not<One>::value;

template <typename xs>
using g = Cons<x, xs>;

Псевдонимы шаблонов позволяют избавиться от метаполя value, когда метафункция возвращает одно метазначение. Это может быть более удобным, если программисту лень явно указывать ::value, а также накладывать требование вычислимости.

// рассмотрим только одну из специализаций
template <typename expr1, typename expr2>
struct If <True, expr1, expr2> {
  // expr1, expr2 вычислены, а expr1::value и expr2::value - нет
  typedef typename expr1::value value;
}

// If<One, id<One>, destroy<the_world>>::value не разрушит мир

template <typename expr1, typename expr2>
struct If <True, expr1, expr2> {
  // expr1, expr2 вычислены
  typedef expr1 value;
};

// If<One, One, destroy<the_world>::value>::value разрушит мир

В основном же псевдонимы шаблонов — просто синтаксический сахар, эквивалентный шаблонам, без которого вполне можно обойтись.

Замыкания

Если в обычных C/C++ аргументы и локальные переменные умирают после завершения работы функции, то в функциональных языках функции могут возвращать функции, зависящие от аргументов и локальных переменных родительской функции. Соответственно, родительская функция уже завершилась, но её локальные переменные остаются в живых, «привязываясь» к дочерней функции. На практике это полезно, когда интерфейс требует, например, унарной функции, а в её реализации имеется некоторый контекст, от которого она тоже зависит.

Например, f x возвращает унарную функцию g, неявно использующую аргумент x функции f.

f x = g
  where g xs = Cons x xs

-- использование: (f x) xs или, что полезнее, map (f x) list

Можно было бы оставить и Cons, но g как унарную можно передать в уже написанную функцию map, а как бинарную — Cons нет!

// до C++11: функциональный объект, захвативший переменную
struct f {
  f(something& x) : x(x) {}
  something_else operator () (something_else& xs) { // xs - явный аргумент
    return Cons(x, xs);
  }
private:
  something x; // неявный аргумент
};

// C++11 и выше: лямбда-функция, захватившая переменную
something x;
auto f = [x](something_else& xs) { return Cons(x, xs); };

При замене функций (например, int(int)) на функциональные объекты (например, std::function<int(int)>) программист C++ получает полноценный аналог замыканий.

На уровне шаблонов потребности в подмене «функция → объект», как оказывается, нет. Замыкания поддерживаются самим языком:

template <typename x>
struct f {
  template <typename xs>
  struct g {
    typedef Cons<x, xs> value;
  };
};

// использование: f<x>::g<list>::value или map<f<x>::g, list>

В отличие от C++ и Haskell, здесь наружу f «вылезает» символ g, но в остальном — честное замыкание. Выражение f<x>::g может быть использовано вместо обычной унарной функции (например, Not).

Неограниченное число аргументов или синтаксический сахар для списков

Вариадические шаблоны позволяют записывать функции от списков. Опять же, в некоторых случаях это удобнее, но без них тоже можно спокойно жить с Cons и Nil. Кроме того, это может оказаться даже более простым ходом. Чтобы передать в метафункцию два списка, достаточно… передать два списка: f<xs, ys>, для вариадических же шаблонов требуется задавать обёртку, захватывающую все списки, кроме последнего: f<list_wrapper<x1,x2,x3>, y1, y2, y3>, так как список аргументов произвольной длины должен быть один, и несколько списков, записанные подряд, просто «слипнутся». По завершении вычислений приходится возвращать обёртку, т.к. в C++ нельзя затайпдефить список из нескольких типов. А чтобы «выковырить» список из обёртки и передать в метафункцию (скажем, f), придётся использовать метаколлбеки: реализовать у обёртки метаметод принимающий эту метафункцию f и передающий ей содержимое списка:

typename <typename... xs>
struct list_wrapper {
  // передаём в list_wrapper<...>::call функцию,
  // которой передадут наши аргументы xs
  struct call<template <typename...> class f> {
    typedef typename f<xs...>::value value;
  };
};

Итеративную/рекурсивную обработку списка даже с помощью этого так просто не реализуешь. Например, для реализации negate нужно сконструировать вспомогательную унарную метафункцию f, которая принимает результат рекурсивного применения negate к хвосту списка, вычисляет отрицание головы и возвращает обёртку для собранного вместе списка:

typename <typename x, typename... xs>
struct negate {
  template <typename... ys>
  struct f {
    typedef list_wrapper<Not<x>::value, ys> value;
  };
  
  typedef typename negate<xs>::template call<f>::value;
};

typename <>
struct negate<> {
  typedef list_wrapper<> value;
};

Вышло так, что за красивую запись вида при объявлении, пришлось пострадать, запаковывая, передавая и распаковывая эти последовательности. negate выглядит более громоздко даже по сравнению с версией для Cons/Nil. Здесь требуются и более серьёзные измышления, когда как для написания «обычной» версии достаточно основ ФП и механической замены Haskell → C++. Поэтому с помощью вариадических шаблонов лучше написать обёртку для преобразования последовательности параметров в список Cons/Nil, а затем при реализации программы пользоваться уже им. Так мы сможем и задавать списки приятным перечислением через запятую, и мыслить более простыми категориями.

Выход во внешний мир

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

По завершении вычислений в метапрограмме, результирующее выражение интерпретируется как сущность из реального мира и, либо сохраняется в переменную, либо выводится на экран. Для вывода можно использовать шаблонные классы. В конструкторе или других методах располагается императивный код. Он может быть как внутри самих метазначений (например, void One::print();), либо — внутри метафункции, если возможностей паттерн-матчинга хватает для рассмотрения всех вариантов. Вот, например, метафункция print, распечатывающая свой аргумент (единицу, ноль или список) на этапе конструирования экземпляра print<...>:

template <typename T>
struct print {
  print () {
    std::cout << "unknown number" << std::endl;
  }
};

template <>
struct print <One> {
  print () {
    std::cout << "1" << std::endl;
  }
};

template <>
struct print <Zero> {
  print () {
    std::cout << "0" << std::endl;
  }
};

// print<Not<Zero>::value>() выведет "1"

Аналогично, можно вывести список и всё, что угодно. Например, мы бы могли реализовать AND, NOT, XOR, двоичный сумматор, представить числа как списки из One и Zero и построить сложение, умножение,…

До C++11 и появления decltype никак нельзя было провести чисто функциональные вычисления над типами, создать переменные и объекты C++ соответствующих типов, провести вычисления над ними, а потом снова вернуться к вычислениям над типами.

sum<sum<One, two>, three> // тип - корректно
sum<sum<One, two>, three>() // значение - компилируется

do_something(sum<One, two>(), three()) // значения - компилируется
sum<sum<One, two>(), three()> // нельзя посчитать,
// т.к. нет перехода от значений к типам

sum<decltype(sum<One, two>()), decltype(three())> // C++11; компилируется

Конечно, эта возможность позволила писать на C++ идеологически более правильный код при меньших затратах, но она немного пошатнула идеологию метаязыка шаблонов. В Haskell, например, функция, испившая ядовитую чашу императивного мира, навсегда остаётся отравленной им и не имеет право возвращать обычные значения, принадлежащие к чистому миру. То есть переход от функциональной чистоты к императивности можно совершить только в одну сторону.

До decltype типы были аналогией чистоты, а значения — сущностями императивного мира: параметром шаблона мог быть только тип, а тип мог быть получен только преобразованиями типа; один раз создав значение, нельзя было вернуться обратно к типам.

В C++11 можно вычислить некий тип, создать значение этого типа, преобразовать его каким-либо образом и передать тип результата в выражение над типами с помощью decltype. Впрочем, decltype свой аргумент не исполняет, а лишь отвечает на вопрос «какой бы был тип выражения, если бы мы его начали считать», отчего не нарушает функциональной чистоты. Поэтому, пока выражение над переменными не покидает скобки decltype, чистота сохраняется. С точки зрения языка шаблонов, decltype выгодно использовать вместе с перегрузкой операторов. В следующем примере выражения эквивалентны, но нижнее выглядит менее громоздко:

typedef sum<sum<one, two>, three> x;
typedef decltype(one() + two() + three()) x;

Выход за скобки нарушает чистоту:

auto v = one() + two() + three(); // v выполнится как императивная конструкция
typedef decltype(v) x;

Эзотерический язык, транслирующийся в шаблоны C++

Основная проблема шаблонов C++ как ФЯ времени компиляции — излишняя многословность. Все эти ::value, скобочки и typename сильно выматывают программиста и растягивают код программы. Конечно, логика говорит, что решивший программировать в таком стиле должен страдать, но… это одно из тех извращённых развлечений, к которым зачастую склоняется мозг айтишника. Хочется попробовать сделать так, чтобы извращённость сохранилась, но в той степени, когда страдания ещё можно терпеть.

В общем, решил я создать свой язык, который будет транслироваться в шаблоны C++. Сделать это можно разными способами. Использовать можно даже наиболее хитроумные преобразования наподобие тех, что делает транслятор JSFuck. Но такой подход (а) породит ещё один ненужный язык, (б) оторванный от C++, (в) который ещё нужно придумать и (г) потратить силы на реализацию. А разработать и реализовать достаточно мощный и ненужный ФЯ — дело хлопотное и бесполезное. Особенно, когда в шаблонах C++ уже есть конструкции, эквивалентные функциям, замыканиям, паттерн-матчингу… Да и не спортивно это.

Я избрал путь наибольшего соответствия. Код на моём языке должен был выглядеть просто, но оставаться идейно похожим на C++. То есть преобразование должно было наиболее дословно переводить мой язык в C++. Он должен был стать килограммом синтаксического сахара над шаблонами.

Давайте перепишем приведённые выше куски кода на созданный язык, таким образом рассмотрев его особенности и их применение в деле. Будем двигаться в том же порядке от определения значений «ноль» и «один», функции отрицания числа, конструкторов списка к определению функции отрицания списка, ФВП map и т.д.

Значения и функции

Для объявления значения не требуется ключевое слово struct:

One;
Zero;

Объявление функции заключает аргументы и их типы в фигурные скобки, оставляя тело за знаком "=". Описания конкретных случаев приводится после описания общего случая и отличается тем, что у конкретных значений аргументов не указывается тип:

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

// использование: Not(One) или And(One, Zero)

В C++ параметром шаблона может быть тип (typename), другой шаблон (template <typename> class) и т.д., и это следует указывать. А значит, создавая метаФВП, одним typename не обойтись и требование указания типа переходит также в мой язык. По умолчанию задан тип val, соответствующий обычному метазначению (структура или обычный тип в C++). Для описания функций можно комбенировать типы с помощью стрелки (->). Например, val -> val — унарная функция (шаблон, принимающий один параметр), (val, val) -> val — бинарная функция (шаблон, принимающий два параметра) и так далее.

Здесь я немного отступил от дословности транслирования и ввёл псевдонимы типов, аналога которым (псевдонимов видов) в C++ нет. С помощью #type можно задавать синонимы, чтобы ещё чуть-чуть сократить запись и прояснить смысл за счёт уместного именования:

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;
// map_t раскроется в template <template <typename> class, typename> class

Можно рассматривать #type как аналог #define в C, задающий текстовые преобразования, которые нехитрым способом можно провести и вручную.

Список

Множественный возврат как полезную возможность я не отменял. Это пригождается уже при реализации списка:

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

Применение функции к аргументам, транслируясь в C++, автоматически раскрывает ::value. То есть f(x) эквивалентно f<x>::value. Но у Cons сгенерируется только два метаполя head и tail. Предотвращать раскрытие ::value требуется явно с помощью апострофа: Cons(x, xs)'.

Я долго думал над этой проблемой. С одной стороны, ::value как одна из частых конструкций должна была раскрываться автоматически, но должна была быть возможность (а) передать нераскрытое значение (см. проблему функции ветвления и бесконечной рекурсии выше под спойлером) и (б) использовать другие метаполя, кроме value. В итоге я остановился на «экранировании», записи метаполей через точку и ввёл обратный для экранирования оператор "!", раскрывающий ::value:

Cons(x, xs)'.head; // x
Cons(x, xs)'.tail; // xs
Not(Zero);         // One
Not(Zero)'!;       // One

Впрочем, метаполе ::value может вполне сосуществовать со множественным возвратом. Реализуя отрицание списка negate на C++, мы создавали локальные метапеременные, которые вполне можно было возвратить. Здесь — аналогично, только все значения публичны:

// отрицание непустого списка:
// список из отрицаний элементов - это отрицание головы,
// соединённое с хвостом отрицаний
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head; // голова
  not_head = Not(h); // отрицание головы
  t = list.tail; // хвост
  not_tail = negate(t); // отрицание хвоста
} // точку с запятой можно опустить!

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

Функции высшего порядка

Вспомним, что мы объявили типы унарной функции и списка и напишем map:

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head; // голова
  new_head = f(h); // преобразованная голова
  t = list.tail; // хвост
  new_tail = map(f, t); // преобразованный хвост
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

Разумеется, вместо unary и list можно было сразу указать val -> val и val соответственно, но запись оказалась бы более длинной и менее наглядной.

Замыкания

Поскольку замыкания поддерживаются самими шаблонами C++, здесь нет чего-то необычного:

f(val x) = {
  g(val xs) = Cons(x, xs)';
}

// использование: f(x)'.g(list) или map(f(x)'.g, list)

Но требуется давать имя (например, g) возвращаемой функции. Возвращаемая безымянная функция должна была бы иметь имя value и возвращать value. Одноимённый с классом член в C++ уже отдан конструктору, из-за чего задание ему нового смысла через typedef приводит к ошибке компиляции:

template <typename x>
struct f {
  template <typename xs>
  struct value {               // value!
    typedef Cons<x, xs> value; // value!
  };
};

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

C++ также не позволяет переиспользовать имена параметров шаблона внутри шаблона. Поскольку эти имена в моём языке относятся к локальным метапеременным и за пределы шаблона не выходят, я автоматизировал их переименование:

f (val x) = g(Not(x)) {
  g (val x) = x; // будет заменено на g (x1) = x1
  // т.к. x станет параметром template f и не допустит x как параметр template g
}

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

Выход во внешний мир

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

Оставалось только ввести тэги для вставки кода на C++ и удовлетворённо потирать руки. Но возникла логическая проблема: в исходниках нигде не упоминается, что для применения метафункций используется ::value, нигде не сказано, что f(x) — это f<x>::value, а не call<f, x>::result. Это знание хранилось внутри транслятора, и его использование в программе прорывало бы абстракцию:

f(val x) = One;
f(Zero) = Zero;

main {
  print<f<One>::value>(); // почему так?
}

Идей насчёт малоинтересной императивной части было немного, и после прикидывания нескольких вариантов я решил ввести (а) императивные блоки с возможностью использования в них обычного C++ и (б) экспорт в них значений из чистого функционального мира. Блок impure { код } может появляться вместо объявления значения/функции, а также справа после знака "=" при объявлении функции. В этих случаях код на C++ вставляется в соответствующее место программы. Для экспортирования выражения перед ним ставится ключевое слово impure. С точки зрения C++ это эквивалентно конструированию объекта типа, описываемого выражением.

В качестве демонстрации работы impure приготовим «распечатыватель» списка:

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    // после typedef-ов head, tail расположится следующий блок кода:
    print() {
      impure print(head); // преобразуется в "print<head>();"
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure { // аналогично print(Zero) { impure { ..., но короче
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

Пространства имён

Поскольку на моём языке в теории можно было бы создавать библиотеки, которые использовались бы в обычном C++, я «прокинул» в него namespace и using namespace:

namespace ns1 {
  namespace ns2 {
    f(val x) = x;
  }
}

namespace ns3 {
  using namespace ns1.ns2;
  g(val x) = f(x);
}

using namespace также является вынужденной мерой. В С++ в некоторых случаях недостаточно записи вида f<x>::y<z>. Если f, x или z — не конкретные типы/шаблоны, а параметры шаблона, то ::y становится выходом чёрного ящика. Нужно указывать, что мы получаем при вычислении ::y — тип или шаблон (например, typename f<x>::y или f<x>::template y<z>). Я не автоматизировал эти указания и не реализовал синтаксический сахар для более простого описания вручную, поэтому каждое использование точки вызывает появление «typename». Т.е. f<x>::y<z> оттранслируется во что-то некорректное вида typename typename f<x>::value::typename y<z>::value. В случае пространства имён это излишне, using namespace позволяет обойтись без вставки «typename».

Лямбды

Мне не хотелось оставлять функциональный язык без лямбда-функций. Полноценную поддержку реализовать не удалось, но вместо этого хотя бы можно перенести при объявлении функции её аргументы по ту сторону знака "="

f          (val x) =  y(x) { y(x) = g(x); } // было
f = lambda (val x) -> y(x) { y(x) = g(x); } // стало

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

template <typename x> struct f {}; // пусть была метафункция f

using g = f; // нельзя описать эквивалентность шаблона шаблону

// нужно описать эквивалентность выражений, соответствующих типам
template <typename x> using g = f<x>; // g<x> - тип, f<x> - тип

Для реализации записей вида map(lambda(val x) -> y, xs) придётся модифицировать язык и генерировать шаблоны с временными именами.

Как рассматривалось выше, value::value — это конструктор, поэтому не получается напрямую реализовать лямбду, которая возвращает лямбду. Для возврата функций из лямбд и разрешения записей вида g = f нужно использовать другие концепции и почти полностью переписать транслятор.

Недостатки и возможные пути решения

1. Нет сокрытия локальных переменных.
   Наивно решается вставкой impure { private: } в код или элементарной модификацией языка.
2. При использовании метаполя автоматически подставляется «typename».
   Не знаю, можно ли избавиться от этого автоматически. В качестве варианта решения можно использовать обязательную венгерскую нотацию (скажем, fMap(fCurry(fCons).fApply(vXs), vObj.vYs) — при доступе к метаполю подставится template, typename или ничего, если первым символом имени будет «f», «v» или «n» соответственно).

   Второй путь — «динамическая типизация». То есть представление всех сущностей в виде структуры-обёртки с хранящимся типом и значением:

   // объявляем значение x
   struct x {
     typedef internal::value type; // тип значения x
   };
   
   // объявляем функцию f(x) = x
   struct f {
     typedef internal::function type; // тип функции f
     template <typename x>
     struct value {
       typedef typename x::type type; // тип результата функции f
       struct result { // обёртка для того, чтобы избежать value::value
         typedef x value;
       };
     };
   };
   

   Транслятор автоматически сгенерирует пространство имён internal со списком типов и метафункциями для работы с ними; за счёт дополнительной обёртки struct result можно будет избавиться от value::value и возвращать безымянные функции из функций. Также из-за того, что любое значение или функция будет выражаться в виде структуры (то есть просто типа, а не типа или шаблона), можно будет задавать синонимы функций (с помощью typedef), отменить обязательное описание типов аргументов функции, устранить ограничения на лямбды и возврат функций из ФВП.

3. Есть ограничения на лямбды: они не могут возвращать функции и быть анонимными.
   Может помочь описанный выше подход.

   Также можно вместо value использовать два значения так, чтобы при увеличении глубины вложенности использовалось другое значение. Получится, что вместо value::value будет value1::value2 и никаких попыток переопределения конструктора не будет:

   template <typename x>
   struct f {
     typedef internal::True uses_value1; // использует value1
     template <typename y>
     struct value1 {
       typedef internal::False uses_value1; // использует value2
       typedef Cons<x, y> value2;
     };
   };
   

   Вызвать такие метафункции можно будет с помощью отдельной метафункции, которая в зависимости от обязательного метаполя uses_value1 будет выбирать, доступаться до value1 или до value2.

4. Не учитываются вариадические шаблоны и целые числа как параметры шаблонов.
   Для реализации требуется поддержка кроме val дополнительных типов для чисел (int, uint, ...) и массивов ([val], [int], [uint], ...). При использовании метаполей придётся решить описанную выше проблему с указанием template и typename, т.к. для чисел ничего не требуется указывать, а для типов и шаблонов — требуется.

Пример программы

В качестве примера построим список , возьмём его отрицание двумя способами и распечатаем все эти значения в main:

// строим списки:
my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    // печатаем списки:
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

Программа выведет следующее:

my list is 1, 1, 0,
negated list is 0, 0, 1,
negated list is also 0, 0, 1,

impure {
  #include <iostream>
}

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

// отрицание непустого списка:
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head;
  not_head = Not(h);
  t = list.tail;
  not_tail = negate(t);
}

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head;
  new_head = f(h);
  t = list.tail;
  new_tail = map(f, t);
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    print() {
      impure print(head);
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure {
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

#include <iostream>
struct One;
struct Zero;
template <typename x>
struct Not {
  typedef Zero _value;
};
template <>
struct Not<Zero> {
  typedef One _value;
};
template <typename x, typename y>
struct And;
template <typename x>
struct And<x, One> {
  typedef x _value;
};
template <typename x>
struct And<x, Zero> {
  typedef Zero _value;
};
struct Nil;
template <typename x, typename y>
struct Cons {
  typedef x head;
  typedef y tail;
};
template <typename list>
struct negate {
  typedef typename list::head h;
  typedef typename Not <h> ::_value not_head;
  typedef typename list::tail t;
  typedef typename negate <t> ::_value not_tail;
  typedef Cons <not_head, not_tail>  _value;
};
template <>
struct negate<Nil> {
  typedef Nil _value;
};
template <template <typename> class f, typename list>
struct map {
  typedef typename list::head h;
  typedef typename f <h> ::_value new_head;
  typedef typename list::tail t;
  typedef typename map <f, t> ::_value new_tail;
  typedef Cons <new_head, new_tail>  _value;
};
template <template <typename> class f>
struct map<f, Nil> {
  typedef Nil _value;
};
template <typename list>
struct print {
  typedef typename list::head head;
  typedef typename list::tail tail;
  print() {
    print <head> ();
    std::cout << ", ";
    print <tail> ();
  }
};
template <>
struct print<Zero> {
  print() {
    std::cout << "0";
  }
};
template <>
struct print<One> {
  print() {
    std::cout << "1";
  }
};
template <>
struct print<Nil> {
  print() {
    std::cout << std::endl;
  }
};
typedef Cons <One, Cons <One, Cons <Zero, Nil> > >  my_list;
typedef typename negate <my_list> ::_value negated_list;
typedef typename map <Not, my_list> ::_value negated_list2;
int main() {
  std::cout << "my list is ";
  print <my_list> ();
  
  std::cout << "negated list is ";
  print <negated_list> ();
  
  std::cout << "negated list is also ";
  print <negated_list2> ();
}

Транслятор

Свой транслятор я написал на JavaScript (люблю этот язык, на нём мне легче думается). В качестве генератора парсеров использовал PEG.js.

При запуске транслятор (см. страничку языка на GitHub) считывает файл, имя которого указано как параметр командной строки, и выдаёт в stdout результирующий текст программы на C++.

node src/compile <исходник> # запуск

Как только транслятор более-менее заработал и были написаны работающие программы, я разместил всё это добро на GitHub и, словно математик из анекдота, воскликнувший «Решение есть!», почти утратил интерес к развитию проекта. Порывался решить указанные выше проблемы чередованием/указанием типа/венгерской нотацией, но это требовало серьёзных изменений и повторного умственного напряжения. Думать, имея что-то готовое и работающее, было лень. Более того, мог нарушиться принцип наибольшего соответствия. Лишние обёртки и код по работе с ними убили бы красоту прямолинейности трансляции и приблизили бы программу к превышению лимита на вложенность шаблонов.

Поэтому я остановился на достигнутом и буду рад, если кто-нибудь заинтересуется и, быть может, сделает свой вклад в развитие языка.

Автор: sekrasoft

Источник