220 26286 article Path: news.gmane.org!not-for-mail From: "Arthur O'Dwyer" Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Re: statement folding on variadic templates parameters pack Date: Sat, 11 Jun 2016 13:46:13 -0700 Lines: 182 Approved: news@gmane.org Message-ID: References: <1e3daa7c-e10a-4589-8118-26f47bc1a0df@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=94eb2c059d500396a4053506bf55 X-Trace: ger.gmane.org 1465677977 1385 80.91.229.3 (11 Jun 2016 20:46:17 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 11 Jun 2016 20:46:17 +0000 (UTC) To: "ISO C++ Standard - Future Proposals" Original-X-From: std-proposals+bncBDLZJYWNDQIJN4PRXICRUBD2VEOFM@isocpp.org Sat Jun 11 22:46:16 2016 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f198.google.com ([209.85.161.198]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1bBpnM-0004qg-DS for gclcip-std-proposals@m.gmane.org; Sat, 11 Jun 2016 22:46:16 +0200 Original-Received: by mail-yw0-f198.google.com with SMTP id n63sf236296920ywf.3 for ; Sat, 11 Jun 2016 13:46:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post :list-help:list-archive:list-subscribe:list-unsubscribe; bh=TPlD9GeAQnsoOMcL1WnkdKuAAdI32A8uqptdOGa9lJM=; b=VsubX/iesTAU5pLvoPeuQepJHI8TmPzAt6LOBEFJ0eJ5j9D7t5Lsev31g6sVKNaNfe je+AVYtgPaYKyA5ul10gHy4tAGZYbkBx53i3fOKxoYjSAeRB4PUbr091yHs7KcnQDBer n6yyOgqOFGwwEETpD4k8cB1TEYnagLe2LbMGrW5SsAdEYQnJCl+8J0bGy3vrvkwcD03U 2LuTlJ1uS1pV8Cf6vJf7M2z2XmSFbSEHlWGm/PF9LWm8Tcqo/RmITggPwHTABTriSJDF 7/21aGzBJL+oRbjKhML3Hud9F5RiWubG2+wsyaojB1O/fw4T/S/I+i+YlMNHT83jxSMi GXRg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=TPlD9GeAQnsoOMcL1WnkdKuAAdI32A8uqptdOGa9lJM=; b=DRZWYi8wzr1JT8J/ovNo/xF6Ds56Hh3MPDgj6PHk1FFR/Uq6mLchpIgVvaPQi3ebVA /b3fyN/4Jt9iQF1wbuQDPgEc8XEoM8KIpNdrGywB8wpFr4/y2/wxlGq4dcevLP7Iks20 N4J9l1cqCwdyaCgUJfrZBgwDIgWsdjPZJm/oANzqrqpjMM/wb8XcKoaYdZkGOinH3/EF Ji69h9vlm3mTJ3goUJSni1H2nFrnWnJc+TDzeh0AdNOuGPpcTL32+WClUKzWV9iB4FJe EIoPBfNcobhCly4AbJBVil9t8ey9Vy1hEUjM912qBFqz5k+pc9+kVyOvIBmMmZNa8EOB JviA== X-Gm-Message-State: ALyK8tJ64LAlpJoXaCOJszPDfeH6P24+ZrPwQx5BqRg+jbW3CT2qCwnuW3tQSisXa6qBow== X-Received: by 10.13.248.4 with SMTP id i4mr6447969ywf.20.1465677975515; Sat, 11 Jun 2016 13:46:15 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.38.104 with SMTP id s95ls2700143qgs.61.gmail; Sat, 11 Jun 2016 13:46:14 -0700 (PDT) X-Received: by 10.140.162.67 with SMTP id i64mr7863542qhi.103.1465677974553; Sat, 11 Jun 2016 13:46:14 -0700 (PDT) Original-Received: from mail-qk0-x22a.google.com (mail-qk0-x22a.google.com. [2607:f8b0:400d:c09::22a]) by mx.google.com with ESMTPS id y70si10234077qkb.137.2016.06.11.13.46.14 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 11 Jun 2016 13:46:14 -0700 (PDT) Received-SPF: pass (google.com: domain of arthur.j.odwyer@gmail.com designates 2607:f8b0:400d:c09::22a as permitted sender) client-ip=2607:f8b0:400d:c09::22a; Original-Received: by mail-qk0-x22a.google.com with SMTP id s186so53184550qkc.1 for ; Sat, 11 Jun 2016 13:46:14 -0700 (PDT) X-Received: by 10.55.104.81 with SMTP id d78mr7728501qkc.189.1465677974310; Sat, 11 Jun 2016 13:46:14 -0700 (PDT) Original-Received: by 10.200.51.177 with HTTP; Sat, 11 Jun 2016 13:46:13 -0700 (PDT) In-Reply-To: X-Original-Sender: arthur.j.odwyer@gmail.com X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com; spf=pass (google.com: domain of arthur.j.odwyer@gmail.com designates 2607:f8b0:400d:c09::22a as permitted sender) smtp.mailfrom=arthur.j.odwyer@gmail.com; dmarc=pass (p=NONE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:26286 Archived-At: --94eb2c059d500396a4053506bf55 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Fri, Jun 10, 2016 at 4:25 AM, Sergey Vidyuk wrote: > >> for constexpr (size_t i=3D0; i < sizeof...(Ts); ++i) { // new synta= x >> ("for constexpr") >> using T =3D Ts...[i]; // new syntax (pack indexing) >> f(); >> } >> >> > I can see one more issue with such kind of for-loop extension: it's > impossible to prove that the loop will terminate in generic case so some > (probably implementation defined) limit on a number of body instantiation= s > required. Range based for over variadic parameters pack have no such > problem since number of items in pack known by compiler before loop > instantiation. > The non-range variant of "for constexpr" does seem more problematic than the range variant, but I don't think termination is a problem here. "Can't prove termination" is not a new problem (for computer science or for C++ in particular), and the existing solutions/workarounds apply. The compiler already has to do something reasonable with e.g. constexpr int f() { int i =3D 42; while (true) ++i; return i; } int main() { static int x[f()]; } Clang on my machine does this: *x.cc:1:15: **error: **constexpr function never produces a constant expression [-Winvalid-constexpr]* constexpr int f() { int i =3D 42; while (true) ++i; return i; } * ^* *x.cc:1:46: note: *constexpr evaluation hit maximum step limit; possible infinite loop? constexpr int f() { int i =3D 42; while (true) ++i; return i; } * ^* The (minor) advantage of the general-purpose for-loop syntax as opposed to the ranged-over-pack syntax is that for any given loop-of-N-iterations, the latter requires the compiler to construct an actual entity, a pack-of-N-elements; whereas the former doesn't. They both take O(N) time, but only the latter takes O(N) space as well. In practice, determining N for an arbitrary input program is equivalent to the Halting Problem, so compilers must implement resource limiting logic similar to the Clang error message above. The practical limits on N for "time" can be pretty high; whereas the practical limits on N for "space" will in practice tend to be lower. Clang seems to put a limit of 512 recursions within a constexpr function, but allows upwards of 1000 iterations of loop control flow within a single constexpr function. This matches with my intuition: Recursion requires space, and is therefore capped tightly. Iteration requires only time, and therefore is capped more loosely. Therefore, any time the user-programmer can make the tradeoff (more time <-> less space) in a constexpr context, he should do so =E2=80=94 and ideally the language should provide the tools fo= r doing so (examples: C++14's unrestricting constexpr functions, C++17's fold-expressions). =E2=80=93Arthur --=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp= ..org/d/msgid/std-proposals/CADvuK0KfyAvXiw%3D453SXvXKKV%3DehMT7Nw2M0oa5JQAa= 9PcyXmA%40mail.gmail.com. --94eb2c059d500396a4053506bf55 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On Fri, Jun 10, 2016 at 4:25 AM, Sergey Vidyuk <sir= ..vestnik@gmail.com> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;pa= dding-left:1ex">

=C2=A0 = =C2=A0 for constexpr (size_t i=3D0; i < sizeof...(Ts); ++i) { =C2=A0// n= ew syntax ("for constexpr")
=C2=A0 =C2=A0 =C2=A0 =C2=A0 using T =3D Ts...[i]; =C2=A0/= / new syntax (pack indexing)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 f<T>();
=C2=A0 =C2=A0 }
=C2=A0
I can see one more issue with such kind of = for-loop extension: it's impossible to prove that the loop will termina= te in generic case so some (probably implementation defined) limit on a num= ber of body instantiations required. Range based for over variadic paramete= rs pack have no such problem since number of items in pack known by compile= r before loop instantiation.

Th= e non-range variant of "for constexpr" does seem more problematic= than the range variant, but I don't think termination is a problem her= e. "Can't prove termination" is not a new problem (for comput= er science or for C++ in particular), and the existing solutions/workaround= s apply. The compiler already has to do something reasonable with e.g.

constexpr int f() = { int i =3D 42; while (true) ++i; return i; }
int main() {
=C2=A0 =C2=A0 static int x[f()];
}

Clang on my machine does this:

x.cc:1:15: error: constexpr function never produces a constant expression [-Winvalid-co= nstexpr]

constexpr int f() { int i =3D 42; while (true) ++i; retur= n i; }

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 ^

x.cc:1:46: note: constexpr evaluation hit maximum = step limit; possible infinite loop?

constexpr int f() { int i =3D 42; while (true) ++i; retur= n i; }

=C2=A0=C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ^

The (m= inor) advantage of the general-purpose for-loop syntax as opposed to the ra= nged-over-pack syntax is that for any given loop-of-N-iterations, the latte= r requires the compiler to construct an actual entity, a pack-of-N-elements= ; whereas the former doesn't. They both take O(N) time, but only the la= tter takes O(N) space as well.
In practice,= determining N for an arbitrary input program is equivalent to the Halting = Problem, so compilers must implement resource limiting logic similar to the= Clang error message above. The practical limits on N for "time" = can be pretty high; whereas the practical limits on N for "space"= will in practice tend to be lower.

Clang seems to put a limit of 512 recursions = within a constexpr function, but allows upwards of 1000 iterations of loop = control flow within a single constexpr function. This matches with my intui= tion: Recursion requires space, and is therefore capped tightly. Iteration = requires only time, and therefore is capped more loosely.=C2=A0 Therefore, = any time the user-programmer can make the tradeoff (more time <-> les= s space) in a constexpr context, he should do so =E2=80=94 and ideally the = language should provide the tools for doing so (examples: C++14's unres= tricting constexpr functions, C++17's fold-expressions).

=E2=80=93Arthur
<= /div>

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CADvuK0KfyAvX= iw%3D453SXvXKKV%3DehMT7Nw2M0oa5JQAa9PcyXmA%40mail.gmail.com.
--94eb2c059d500396a4053506bf55-- .