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

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

25 голосов
/ 12 июля 2010

Согласно Обобщенным выражениям констант - редакция 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.

Ответы [ 5 ]

18 голосов
/ 12 июля 2010

Причина в том, что компилятору уже есть над чем поработать, и при этом он не является полноценным интерпретатором, способным вычислять произвольный код 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 была выполнена ранее в том же месте .

5 голосов
/ 12 июля 2010

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

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

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

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

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

2 голосов
/ 13 июля 2010

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

Обе формы являются незаконными. Рекурсия не разрешена в функциях 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 за то, что потрясли мою память с вашим комментарием к моему другому ответу). Вместо того чтобы устанавливать произвольные пределы рекурсии, дизайнеры посчитали более простым просто сказать «Нет».

2 голосов
/ 12 июля 2010

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

0 голосов
/ 12 июля 2010

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

...