Почему неправильно иметь многострочные функции constexpr?

Question

Согласно Обобщенным выражениям констант - Редакция 5, следующее является незаконным.

constexpr int g(int n) // error: body not just ‘‘return expr’’
{
    int r = n;
    while (--n > 1) r *= n;
    return r;
}

Это потому, что все функции "constexpr" должны иметь вид { return expression; }, Я не вижу причин, по которым это должно быть так.

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

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

Написать действительный constexpr для приведенного выше примера вы можете сделать:

constexpr int g(int n) // error: body not just ‘‘return expr’’
{
    return (n <= 1) ? n : (n * g(n-1));
}

Но это намного сложнее понять, и вы должны надеяться, что компилятор позаботится о хвостовой рекурсии, когда вы вызываете с параметрами, которые нарушают требования для const-expr,

Answer 1

Причина в том, что компилятору уже есть над чем поработать, и при этом он не является полноценным интерпретатором, способным оценивать произвольный код C++.

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

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

В двух словах, это:

7 * 2 + 4 * 3

это просто вычислить. Вы можете построить синтаксическое дерево, которое выглядит так:

   +
  /\
 /  \
 *   *
/\  /\
7 2 4 3

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

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

int i0 = 7;
int i1 = 2;
int i2 = 4;
int i3 = 3;

int i4 = i0 * i1;
int i5 = i2 * i3;
int i6 = i4 + i5;
return i6;

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

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

    ;    
    /\
   ST \
   /\  \
  i0 3  \
        ;
       /\
      ST \
      /\  \
     i1 4  \
           ;
          /\
         ST \
         / \ \
       i2  2  \
              ;
             /\
            ST \
            /\  \
           i3 7  \
                 ;
                /\
               ST \
               /\  \
              i4 *  \
                 /\  \
               LD LD  \
                |  |   \
                i0 i1   \
                        ;
                       /\
                      ST \
                      /\  \
                     i5 *  \
                        /\  \
                       LD LD \
                        |  |  \
                        i2 i3  \
                               ;
                              /\
                             ST \
                             /\  \
                            i6 +  \
                               /\  \
                              LD LD \
                               |  |  \
                               i4 i5  \
                                      LD
                                       |
                                       i6

Это не только выглядит намного сложнее, но и требует состояния. Раньше каждое поддерево можно было интерпретировать отдельно. Теперь все они зависят от остальной части программы. Одна из операций с листами LD не имеет смысла, если она не помещена в дерево, чтобы ST операция была выполнена в том же месте ранее.

Answer 2

На всякий случай, если есть какая-то путаница здесь, вы знаете, что constexpr функции / выражения оцениваются во время компиляции. При этом не возникает проблем с производительностью.

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

Я обеспокоен проблемами QoI с этим все же. Интересно, будут ли разработчики компилятора достаточно умны для выполнения запоминания?

constexpr fib(int n) { return < 2 ? 1 : fib(n-1) + fib(n-2); }

Без запоминания вышеупомянутая функция имеет сложность O (2ⁿ), что, конечно, не то, что я хотел бы почувствовать даже во время компиляции.

Answer 3

РЕДАКТИРОВАТЬ: игнорировать этот ответ. Ссылочная статья устарела. Стандарт допускает ограниченную рекурсию (см. Комментарии).

Обе формы являются незаконными. Рекурсия не допускается в функциях constexpr из-за ограничения на то, что функция constexpr не может быть вызвана, пока она не определена. Ссылка, предоставленная ОП, прямо говорит об этом:

constexpr int twice(int x);
enum { bufsz = twice(256) }; // error: twice() isn’t (yet) defined

constexpr int fac(int x)
{ return x > 2 ? x * fac(x - 1) : 1; } // error: fac() not defined
                                       // before use

Несколько строк ниже:

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

...

Мы (до сих пор) запрещаем рекурсию во всех ее формах в постоянных выражениях.

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

Answer 4

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

Answer 5

Это вероятно плохо сформировано, потому что это слишком трудно осуществить. Аналогичное решение было принято в первой версии стандарта в отношении замыканий функций-членов (т. Е. Возможности выдавать obj.func как вызываемая функция). Возможно, более поздний пересмотр стандарта предложит больше широты.