Поддерживает ли С++ 11 рекурсию типов в шаблонах?

Нет, это невозможно. Запрещена даже непрямая рекурсия через шаблоны псевдонимов.

C++11, 4.5.7/3:

Идентификатор типа в объявлении шаблона псевдонима не должен ссылаться на объявляемый шаблон псевдонима. Тип, созданный специализацией шаблона псевдонима, не должен прямо или косвенно использовать эту специализацию. [ Пример:

template <class T> struct A;
template <class T> using B = typename A<T>::U;
template <class T> struct A {
typedef B<T> U;
};
B<short> b; // error: instantiation of B<short> uses own type via A<short>::U

— конец примера]

Если вы хотите этого, придерживайтесь своего Felix, Ocaml или Haskell. Вы легко поймете, что очень немногие (ни одного?) успешные языки имеют такие же богатые системы типов, как эти три. И на мой взгляд, если бы все языки были одинаковыми, учить новые не стоило бы.

template<typename T>
using list<T> = variant< unit, tuple<T, list<T>> >;

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

Этот шаблон псевдонима эквивалентен следующему фрагменту Haskell:

type List a = Either () (a, List a)

GHCi отклоняет это, потому что «[циклы] в объявлениях синонимов типов» не разрешены. Я не уверен, что это прямо запрещено в С++ или разрешено, но вызывает бесконечную рекурсию при замене. В любом случае, это не работает.

Способ определения новых типов в C++ — это ключевые слова struct, class, union и enum. Если вы хотите что-то вроде следующего Haskell (я настаиваю на примерах Haskell, потому что я не знаю двух других языков), вам нужно использовать эти ключевые слова.

newtype List a = List (Either () (a, List a))

Я думаю, вам, возможно, придется пересмотреть свою теорию типов, так как некоторые из ваших утверждений неверны.

Давайте ответим на ваш главный вопрос (и двусмысленный момент) - как указывали другие, рекурсия типа запрошенного вами типа не разрешена. Это не означает, что C++ не поддерживает рекурсию типов. Он отлично поддерживает его. Запрашиваемая вами рекурсия типа — это рекурсия типа name, представляющая собой синтаксическую особенность, которая на самом деле никак не влияет на реальную систему типов.

C++ допускает рекурсию членства в кортеже через прокси. Например, С++ позволяет

class A
{
    A * oneOfMe_;
};

Это рекурсия типов, которая имеет реальные последствия. (И, очевидно, ни один язык не может сделать это без внутреннего прокси-представления, потому что в противном случае размер бесконечно рекурсивен).

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

Чтобы доказать, что рекурсия имени типа не добавляет функциональности системе типов, нужно только указать, что система типов С++ позволяет полностью вычислять типы по Тьюрингу, используя метапрограммирование для констант времени компиляции (и их списков типов), посредством простого отображения имена констант. Это означает, что существует функция MakeItC++:YourIdeaOfPrettyName->TypeParametrisedByTypelistOfInts, которая создает любую вычислимую по Тьюрингу систему типов, которую вы хотите.

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

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

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

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

Большинство вариантов во время выполнения обычно лучше инкапсулируются в полиморфизме во время выполнения. Полиморфизм времени выполнения имеет статически проверенную семантику, которая может иметь связанную проверку инвариантов времени выполнения, и в отличие от вариантов (где тип суммы универсально объявлен в одном месте кода) фактически поддерживает принцип Open-Closed. Из-за необходимости объявлять вариант в одном месте, вы должны менять это место каждый раз, когда добавляете в сумму новый функциональный тип. Это означает, что код никогда не закрывается для внесения изменений и, следовательно, может содержать ошибки. Однако полиморфизм во время выполнения позволяет добавлять новые поведения в отдельные локусы кода, отличные от других поведений.

(Кроме того, большинство реальных языковых систем типов в любом случае не являются дистрибутивными. (a, b | c) =/= (a, b) | (a, c), так какой же здесь смысл?)

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

Но ничто из этого не дает причин атаковать систему типов С++. Почти для каждого языка существуют законные атаки — рекурсия имен типов и доступность вариантов не являются таковыми.

РЕДАКТИРОВАТЬ: Поскольку моя точка зрения о полноте Тьюринга, похоже, не понята, как и мой комментарий о способе С++ использования тегов типов и признаков для разгрузки вычислений типов, возможно, пример в порядке.

Теперь ОП утверждает, что хочет этого в случае использования списков, с которым легко справляется мой предыдущий пункт в макете. Лучше просто используйте std::list. Но из других комментариев и других источников я думаю, что они действительно хотят, чтобы это работало над переводом Felix-> C++.

Итак, я думаю, что ОП думает, что они хотят, что-то вроде

template <typename Type>
class SomeClass
{
    // ...
};

а затем иметь возможность построить тип

SomeClass< /*insert the SomeClass<...> type created here*/ >

Я упомянул, что это всего лишь соглашение об именах. Никому не нужны имена типов — они являются переходными процессами процесса перевода. Что на самом деле требуется, так это то, что вы сделаете с Type позже в структурной композиции типа. Он будет использоваться в вычислениях имени типа для создания данных членов и сигнатур методов.

Итак, что можно сделать в С++, это

struct SelfTag {};

Затем, когда вы захотите сослаться на себя, просто поместите туда этот тег типа.

Когда имеет смысл выполнить вычисление типа, у вас есть специализация шаблона на SelfTag, которая заменит SomeClass<SelfTag> вместо замены SelfTag в соответствующем месте вычисления типа.

Я хочу сказать, что система типов С++ является завершенной по Тьюрингу, и это означает гораздо больше, чем то, что я думаю, что ОП читает каждый раз, когда я это пишу. Вычисление любого типа может быть выполнено (учитывая ограничения рекурсии компилятора) и это действительно означает, что если у вас есть проблема в одной системе типов на совершенно другом языке, вы можете найти перевод здесь . Я надеюсь, что это сделает мою точку зрения еще более ясной. Вернуться назад и сказать: «Ну, вы все еще не можете использовать XYZ в системе типов», было бы явно упущено главное.

C++ действительно имеет «любопытно повторяющийся шаблон шаблона» или CRTP. Однако это не относится к С++ 11. Это означает, что вы можете сделать следующее (бессовестно скопированное из Википедии):

template <typename T>
struct base
{
    // ...
};
struct derived : base<derived>
{
    // ...
};

@jpalcek ответил на мой вопрос. Однако моя реальная проблема (как указано в примерах) может быть решена без рекурсивных псевдонимов, например:

// core combinators
struct unit;
struct point;
template<class T,class U> struct fix;
template<class T, class U> struct tup2;
template<class T, class U> struct var2;

template <> struct   
  fix<
    point,
    var2<unit, tup2<int,point> > 
  > 
{ 
  // definition goes here
};

используя типы fix и point для представления рекурсии. Мне не нужно определять какие-либо шаблоны, мне нужно только определить специализации. Мне нужно было имя, которое было бы одинаковым в двух разных единицах перевода для внешней связи: имя должно было быть функцией структуры типа.

@ Ex0du5 заставил задуматься об этом. Фактическое решение также связано с перепиской Габриэля де Руа много лет назад. Я хочу поблагодарить всех, кто внес свой вклад.