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

Question

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

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

template<typename T, int SIZE> class FixedArray 
{ 
    T m_values[SIZE]; 

public: 
    int getElementCount() const { return SIZE; }

    T operator[] (int i) const { 
        if (i<0 || i>=SIZE) 
            throw;
        else 
            return m_values[i]; 
    }  
};

void f()
{
    FixedArray<float, 5> float_array; // Declares a fixed array of 5 floats. 
    //The size is known at compile time, and values are allocated on the stack.
}

В C ++ допускаются только постоянные целые и указатели, но я думаю, что было бы интересно использовать любое значение для параметризации (float, экземпляры классов, так далее.).Это может позволить выразить предварительные условия во время компиляции (обычно это неформально указано в документации) и автоматически проверять их во время выполнения.Например, вот шаблон «Interval» на гипотетическом диалекте C ++:

// Interval of type T between TMin and TMax. 
template<typename T, T TMin, T TMax> class Interval
{
    T m_value;

public:
    Interval(int val) { *this = val; }

    Interval& operator = (T val) { 
        //check that 'val is in [TMin, TMax] and set the value if so, throw error if not
        if (val < TMin || val > TMax) 
            throw;
        else
            m_value = val; 

        return *this;
    };  

    operator T() const { return m_value; }
}   

// Now define a f function which is only allowing a float between O and 1
// Usually, that kind of function is taking a float parameter with the doc saying "the float is in 0-1 range". But with our Interval template we have
// that constraint expressed in the type directly.
float f(Interval<float, 0, 1> bounded_value)
{
    // No need to check for boundaries here, since the template asserts at compile-time that the interval is valid
    return ...;
}

// Example usage
void main();
{
    float val = 0.5;

    Interval<float, 0, 1> sample_interval = val;    // OK. The boundary check is done once at runtime.

    f(sample_interval);             // OK. No check, because it is asserted by the type constraint at compile-time.
                                // This can prevent endless precondition testing within an algorithm always using the same interval

    sample_interval = 3*val;            // Exception at runtime because the constraint is no longer satisfied

    f(sample_interval);             // If I am here, I am sure that the interval is valid. But it is not the case in that example.
}   

Интересно было бы выразить отношения между этими типами.Например, выражение правила назначения интервала A другому интервалу B с другими границами или просто правило назначения значения интервалу, когда все проверяется во время компиляции.

Есть ли язык сэтот тип параметризации (или похожий подход) или еще нужно придумать?Какие-нибудь полезные исследовательские работы?

Answer 1

Типы, которые параметризованы значениями, называются зависимыми типами .¹ Было проведено много исследований по теме зависимых типов, но мало что достигло «основного языка».

Большая проблема с зависимыми типами состоит в том, что если ваши типы содержат выражения, то есть биты кода, то средство проверки типов должно иметь возможность выполнять код.Это не может быть сделано в полной общности: что, если код имеет побочные эффекты?Что делать, если код содержит бесконечный цикл?Например, рассмотрим следующую программу в C-подобном синтаксисе (проверка ошибок опущена):

int a, b;
scanf("%d %d", &a, &b);
int u[a], v[b];

Как компилятор может узнать, имеют ли массивы u и v одинаковый размер?Это зависит от номеров, которые вводит пользователь!Одним из решений является запрет побочных эффектов в выражениях, которые появляются в типах.Но это не заботится обо всем:

int f(int x) { while (1); }
int u[f(a)], v[f(b)];

компилятор войдет в бесконечный цикл, пытаясь определить, имеют ли u и v одинаковый размер.

Итак, давайте запретим побочные эффекты внутри типов и ограничим рекурсию и зацикливание делами, которые можно окончательно завершить.Делает ли это проверку типов разрешимой?С теоретической точки зрения да, может.То, что у вас есть, может быть чем-то вроде Coq доказательства Проблема в том, что проверка типов тогда легко разрешима , если у вас достаточно аннотаций типов (аннотации типов - это информация о типах, предоставляемая программистом).И здесь достаточно много значит много.Очень многоКак, например, аннотации типов в каждой отдельной языковой конструкции, не только объявления переменных, но также вызовы функций, операторы и все остальное.И типы будут представлять 99,9999% от размера программы.Часто было бы быстрее написать все это на C ++ и отладить его , чем писать всю программу со всеми необходимыми аннотациями типов.

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

Зависимые типы иногда появляются в ограниченной форме в основных языках.Например, C99 допускает массивы, размер которых не является константным выражением;тип такого массива является зависимым типом.Неудивительно, что для C компилятору не требуется проверять границы для такого массива, даже когда требуется проверять границы для массива постоянного размера.

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

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

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

¹ _{В более общем смысле теоретики типов классифицируют системы типов в соответствии с тем, имеют ли они типы высшего порядка (типы, параметризованные типами), полиморфизм (выражения, параметризованные типами) и зависимые типы (типы, параметризованные выражениями). Эта классификация называется куб Барендрегта или лямбда-куб . Фактически это гиперкуб, но обычно четвертое измерение (выражения, параметризованные выражениями, то есть функциями) само собой разумеется.}

Answer 2

Я думаю, вы в основном описываете Зависимые типы . Существует несколько (в основном исследовательских) языков, которые реализуют их, ссылки на которые приведены в статье. Как правило, становится трудным автоматически доказывать наличие типа в общем случае (т. Е. Проверка типов становится очень сложной или в общем случае не поддается разрешению), но были некоторые практические примеры их использования.

Answer 3

Ada95 поддерживает общие формальные параметры, которые являются значениями.В примере на этой странице , Size - это общий формальный параметр, значение которого должно быть положительным целым числом.