Home > Archive > Scheme > February 2005 > OT: Hygiene in C++ templates? (was Re: Separate compilation)
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
OT: Hygiene in C++ templates? (was Re: Separate compilation)
|
|
| Lynn Winebarger 2004-10-30, 3:56 am |
|
Antoun Kanawati wrote:
> Joe Marshall wrote:
>
>
>
>
> That was precisely my point. While C++ templates may be quite
> expressive, or as some seem to feel, Turing-equivalent to a
> real programming language, they do not express the same concept
> as Scheme macros.
>
From what I've read (and I'm not a C++ programmer), C++ templates
are recursively callable macros and you can implement a substitution
based lambda calculus in them. They may not be able to call "executable
code" in the form of compiled C++ functions, but that's not the same
as being a "static construct".
As the subject indicates, though, I'd like to know whether C++
templates are hygeinic or not. Alexandrescou's intro to C++
metaprogramming doesn't seem to mention the issue (maybe I missed
it). I suspect they aren't, but that's just prejudice on my
part.
Lynn
| |
| Antoun Kanawati 2004-10-30, 8:56 pm |
| Lynn Winebarger wrote:
> From what I've read (and I'm not a C++ programmer), C++ templates
> are recursively callable macros and you can implement a substitution
> based lambda calculus in them. They may not be able to call "executable
> code" in the form of compiled C++ functions, but that's not the same
> as being a "static construct".
I program in C++ for pay. In earlier times, nearly all my programming
was in Scheme. So, while my Scheme may be somewhat rusty, I am still
up to date on C++.
The C++ template constructs are fundamentally compile-time constructs
(commonly known as 'static'). Given the same source code, you get the
same results every time, and not a single executable construct of that
source will be executed during compilation.
There is no question of executing arbitrary C++ programs in the middle
of compilation; there is a clear distinction between the code that
"implements" a template and the code that executes at runtime.
While processing C++ code, with templates, the compiler will never
instantiate a class, invoke a function, or even dereference a variable.
So, it doesn't matter if the computational potency of the C++ template
language is equivalent to the Lambda Calculus, it remains distinct from
the runtime language. In addition to that critical distinction, the C++
template language is operationally very limited: no access to any
runtime construct or state.
In Scheme, expanding a macro means running user defined Scheme code that
implements the syntactic transformation, not a subset with a tightly
restricted scope.
> As the subject indicates, though, I'd like to know whether C++
> templates are hygeinic or not. Alexandrescou's intro to C++
> metaprogramming doesn't seem to mention the issue (maybe I missed
> it). I suspect they aren't, but that's just prejudice on my
> part.
C++ templates are lexically scoped, etc... It would take a reading of
the standard, which includes a lot of minutiae, to answer your question.
--
A. Kanawati
NO.antounk.SPAM@comcast.net
| |
| Lynn Winebarger 2004-10-31, 3:57 am |
| Antoun Kanawati wrote:
> Lynn Winebarger wrote:
>
>
>
> I program in C++ for pay. In earlier times, nearly all my programming
> was in Scheme. So, while my Scheme may be somewhat rusty, I am still
> up to date on C++.
>
> The C++ template constructs are fundamentally compile-time constructs
> (commonly known as 'static'). Given the same source code, you get the
> same results every time, and not a single executable construct of that
> source will be executed during compilation.
>
Sorry, I had lost the thread. I was just responding the characterization
of templates as "static", whereas the argument is about how separate
compilation in scheme is hard because the compilation unit's code could depend
on variables in the scheme session compiling that unit. Is that a fair
summary?
If you want to say template code is interpreted only at compile time,
that seems fair enough. The sense I've seen static used in is in reference
to properties implicit in code, whereas templates are explicitly evaluated
(by substitution, if no more efficient means has been implemented). Also
the deduction process for the these properties is almost inevitably
guaranteed to terminate. I think some people have abandoned that as a
requirement, though. Templates, on the other hand, have nothing to
do with deduction of properties of the code and everything to do with
calculating what code to generate.
I assume there's been some work in compiling the templates after
the fiasco of early template metaprogramming (in terms of efficiency).
Just for clarity, I mean regarding templates as their own functional
language and compiling that language.
> There is no question of executing arbitrary C++ programs in the middle
> of compilation; there is a clear distinction between the code that
> "implements" a template and the code that executes at runtime.
>
> While processing C++ code, with templates, the compiler will never
> instantiate a class, invoke a function, or even dereference a variable.
From what I've read, a C++ compiler needs at least 3 components:
a template interpreter, a C++ expression interpreter (for reduction
of compile-time constants), and then the actual compiler for core C++
(no templates).
Isn't it the case that if you have a template T, the code T<2+3>
gets changed to T<5> _before_ T is invoked? If that's true, C++ code
is getting executed at compile-time, even it's by an interpreter and
not in the form of machine code.
>
>
> C++ templates are lexically scoped, etc... It would take a reading of
> the standard, which includes a lot of minutiae, to answer your question.
Yeah, I know. That's why I was casting about to see if someone else
had invested that time.
Of course, I could just construct a template that would
show hygiene problems and see what the compiler does with it.
Lynn
| |
| Vesa Karvonen 2004-10-31, 3:57 am |
| Lynn Winebarger <owinebar@indiana.edu> wrote:
[...]
> From what I've read (and I'm not a C++ programmer), C++ templates
> are recursively callable macros
No. C++ templates are very different from macros (both C preprocessor
and Scheme macros). I think that some people describe them as macros due
to the code bloat generating compilation model of C++ templates, which
differs from the separate compilation model established by ML.
> and you can implement a substitution based lambda calculus in them.
Yes, that is possible, though it isn't necessary to use a literally
substitution based implementation of lambda calculus.
> They may not be able to call "executable
> code" in the form of compiled C++ functions, but that's not the same
> as being a "static construct".
Basically, C++ template metaprograms only perform computations on types.
> As the subject indicates, though, I'd like to know whether C++
> templates are hygeinic or not. Alexandrescou's intro to C++
> metaprogramming doesn't seem to mention the issue (maybe I missed
> it). I suspect they aren't, but that's just prejudice on my
> part.
They are essentially hygienic. In particular, see section C.13.8
Name Binding on page 859 (or so) of the book The C++ Programming
Language, 3rd. ed. (or Special ed.).
-Vesa Karvonen
| |
| Antoun Kanawati 2004-10-31, 3:57 am |
| Lynn Winebarger wrote:
> Sorry, I had lost the thread. I was just responding the
> characterization of templates as "static", whereas the argument is
> about how separate compilation in scheme is hard because the compilation
> unit's code could depend on variables in the scheme session compiling
> that unit. Is that a fair summary?
Yup.
> Templates, on the other hand, have nothing to
> do with deduction of properties of the code and everything to do with
> calculating what code to generate.
I guess you meant macros.
> I assume there's been some work in compiling the templates after
> the fiasco of early template metaprogramming (in terms of efficiency).
> Just for clarity, I mean regarding templates as their own functional
> language and compiling that language.
I don't recall a fiasco, just general clunkiness and discomfort.
> From what I've read, a C++ compiler needs at least 3 components:
> a template interpreter, a C++ expression interpreter (for reduction
> of compile-time constants), and then the actual compiler for core C++
> (no templates).
That sounds right. The expression interpreter is fairly simple though.
> Isn't it the case that if you have a template T, the code T<2+3>
> gets changed to T<5> _before_ T is invoked? If that's true, C++ code
> is getting executed at compile-time, even it's by an interpreter and
> not in the form of machine code.
Only if you consider constant folding in the same class as the
execution of C++ code that accesses memory, causes sides effects,
interacts with the network, etc...
The template language explicitely excludes anything that looks
like a non-constant; for example:
// this is OK.
template<int n> struct intvalue { static const int value = n+n; };
const int four = intvalue<2>::value;
const int eight = intvalue<intvalue<2>::value>::value;
inline int add3(int n) { return n + 3; } // function call.
int xis = 6; // intial value is 6, but xis is not constant.
// these will be rejected.
const int twelve = intvalue<xis>::value;
const int ten = intvalue<add3(2)>::value;
Note that this does not prevent you from transcribing a good number
of recursive algorithms into template notation.
Anyway, the current state of templates can be very interesting to
a Schemer: define a cons-cell construct, a special null-type, and
now you can do all your introductory Scheme homeworks in C++ templates.
> Yeah, I know. That's why I was casting about to see if someone else
> had invested that time.
> Of course, I could just construct a template that would
> show hygiene problems and see what the compiler does with it.
This has been answered elsewhere in the thread.
--
A. Kanawati
NO.antounk.SPAM@comcast.net
| |
| Bradd W. Szonye 2004-11-01, 3:58 pm |
| Antoun Kanawati wrote:
> The C++ template constructs are fundamentally compile-time constructs
> (commonly known as 'static').
That's not what static means.
> Given the same source code, you get the same results every time, and
> not a single executable construct of that source will be executed
> during compilation.
That's not true. Template deduction and instantiation is itself an
executable code.
> There is no question of executing arbitrary C++ programs in the middle
> of compilation --
True, but you /can/ execute arbitrary template code. While the template
language is less expressive than the full language, it's still Turing
complete and therefore carries the same risks as executing any other
program.
> While processing C++ code, with templates, the compiler will never
> instantiate a class, invoke a function, or even dereference a variable.
That's irrelevant.
> So, it doesn't matter if the computational potency of the C++ template
> language is equivalent to the Lambda Calculus, it remains distinct
> from the runtime language --
Yes, it does matter. It means that the template language has the same
issues as any other Turing-complete language. For one thing, it won't
always be amenable to static analysis (despite your misuse of "static"
above).
--
Bradd W. Szonye
http://www.szonye.com/bradd
| |
| Antoun Kanawati 2004-11-02, 3:57 am |
| To reply in your very concise style, you're wrong, and irritating.
It would help, for example, to define the meaning of a word when
you assert "that's not what it means". Or elaborate a little
bit beyond 'irrelevant'.
So, yeah, I know that C++ templates are quite the potent thing.
But, I still cannot print dignostic messages during the expansion
of a recursive template, I cannot call any of the standard
library's functions, or even access a variable.
Of course, I can write a templates that can implement nearly
any reasonable compuation. But that's like deducing that
I can walk from Boston to New York because I can walk around
the block, and then going on to conclude that motorized transportation
is irrelevant.
Conventionally, the words 'static' refers to compile time entities,
and 'dynamic' refers to runtime entities. The C++ template, regardless
of its expressive power, remains confined to compile time. Furthermore,
a C++ template does not vary with time, quite unlike a 'dynamic' object
which can retain its identity while varying its state. The C++ template
language does not include a single imperative construct, or any
notion of state.
The template language may be equivalent to a pure functional language,
but it is not equivalent to an imperative language, except in some
very theoretical sense (the one where everything is written in
continuation passing style, with the store as an argument).
Bradd W. Szonye wrote:
> Antoun Kanawati wrote:
>
>
>
> That's not what static means.
>
>
>
>
> That's not true. Template deduction and instantiation is itself an
> executable code.
>
>
>
>
> True, but you /can/ execute arbitrary template code. While the template
> language is less expressive than the full language, it's still Turing
> complete and therefore carries the same risks as executing any other
> program.
>
>
>
>
> That's irrelevant.
>
>
>
>
> Yes, it does matter. It means that the template language has the same
> issues as any other Turing-complete language. For one thing, it won't
> always be amenable to static analysis (despite your misuse of "static"
> above).
--
A. Kanawati
NO.antounk.SPAM@comcast.net
| |
| Vesa Karvonen 2004-11-02, 3:57 am |
| Bradd W. Szonye <bradd+news@szonye.com> wrote:
> Antoun Kanawati wrote:
[color=darkred]
> That's not what static means.
Considering the context of C++, I think that the word "static" is quite
appropriate. No, there is no universal definition of every technical
term. A term may have different meanings in different technical
contexts.
> [...] While the template
> language is less expressive than the full language, it's still Turing
> complete and therefore carries the same risks as executing any other
> program.
[You haven't defined the term "risks", so I will interpret it as a
generic term.]
No it does not. A C++ template metaprogram can't delete my working
directory, for instance. Furthermore, the C++ template mechanism
isn't as Turing complete as one might naively think. Here is a snippet
from the C++ standard (well, draft actually):
"""
12There is an implementation-defined quantity that specifies the limit
on the depth of recursive instantiations. The result of an infinite
recursion in instantiation is undefined.
"""
The above snippet means that all template programs must finish in a
finite number of template instantiations (although the number of
instantiations may be large).
> Yes, it does matter. It means that the template language has the same
> issues as any other Turing-complete language. [...]
[You haven't defined the term "issues", so I will interpret it as
a generic term.]
C++ templates don't, for instance, have the concept of "cons-cell
identity" or "assignment" like Scheme does and C++ templates don't have
"issues" that relate to "cons-cell identity" or "assignment". Actually,
as the above standard quote shows, the C++ template language isn't even
strictly Turing complete. Even so, the sets of "issues" that different
Turing complete languages have are not all equal.
-Vesa Karvonen
| |
| Matthias Blume 2004-11-02, 3:58 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> ... Furthermore, the C++ template mechanism
> isn't as Turing complete as one might naively think. Here is a snippet
> from the C++ standard (well, draft actually):
>
> """
> 12There is an implementation-defined quantity that specifies the limit
> on the depth of recursive instantiations. The result of an infinite
> recursion in instantiation is undefined.
> """
>
> The above snippet means that all template programs must finish in a
> finite number of template instantiations (although the number of
> instantiations may be large).
The same is true for any program, including Turing machines. And for
every practical implementation on a physical computer, there is also
an upper limit on resources (space, time, ...).
> ... Actually,
> as the above standard quote shows, the C++ template language isn't even
> strictly Turing complete.
No language implementation on a physical computer is.
| |
| Vesa Karvonen 2004-11-02, 3:58 pm |
| Matthias Blume <find@my.address.elsewhere> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
[color=darkred]
> The same is true for any program,
So, by implication, you are claiming that the following Scheme program,
that one could call (after domain theory) "bottom", terminates in a
finite number of function applications:
((lambda (x) (x x))
(lambda (x) (x x)))
My advice: Don't hold your breath while you wait for the above program
to terminate.
> including Turing machines.
That is plain wrong. A Turing machine can be specified that will not
halt in any finite number of state transitions.
> And for
> every practical implementation on a physical computer, there is also
> an upper limit on resources
Yes, I know. What differentiates C++ templates from most other "Turing
complete" languages is that *every* computational step consumes some
finite resource. It is *strictly* impossible to write a C++ template
metaprogram whose evaluation on a standards conforming (whether resource
bound or not) C++ implementation would take an infinite number of
computational steps.
> (space, time, ...).
Space is usually a finite resource, time is less of a resource.
Under a reasonably stable environment, an electronic computer
could run virtually forever. At any rate, it is possible to
design a machine that saves its state every now and then and
can be restarted if it fails. Such a machine could be maintained
indefinitely.
-Vesa Karvonen
| |
| Matthias Blume 2004-11-02, 3:58 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> Matthias Blume <find@my.address.elsewhere> wrote:
> [...]
>
>
> So, by implication, you are claiming that the following Scheme program,
> that one could call (after domain theory) "bottom", terminates in a
> finite number of function applications:
>
> ((lambda (x) (x x))
> (lambda (x) (x x)))
No. That is not what I am claiming. But (AFAIK), there is no
guarantee that template instantiation terminates either. It has just
been postulated that if it doesn't, it does not count as valid C++.
In practice, the compiler will cut template instantiation off at some
point. But the same happens to every other program in the world (on a
real, practical computer).
> My advice: Don't hold your breath while you wait for the above program
> to terminate.
Thanks for the advice.
>
> That is plain wrong. A Turing machine can be specified that will not
> halt in any finite number of state transitions.
No, it is not wrong. A Turing machine which is supposed to produce a
result must terminate. Sure, there are TMs that do not terminate, but
they simply don't produce a result in that case. (Well, I know, they
could keep scribbling on the tape, and one could view that as a
process which produces an inifinte sequence of symbols, etc. This can
be accounted-for in ways which don't involve non-termination, though.
In the orginal sense a TM is supposed to capture the notion of an
algorithm, and an algorithm is always a finite recipe which, followed
step-by-step, produces a result in finite time. It just so happens
that if one doesn't want to exclude certain terminating programs, one
also has to make it possible for non-terminating programs to be
written.)
> ... At any rate, it is possible to
> design a machine that saves its state every now and then and
> can be restarted if it fails. Such a machine could be maintained
> indefinitely.
I doubt that very much. Rememer, I said "practical".
Matthias
| |
| Antoun Kanawati 2004-11-02, 3:58 pm |
| Vesa Karvonen wrote:
> No it does not. A C++ template metaprogram can't delete my working
> directory, for instance. Furthermore, the C++ template mechanism
> isn't as Turing complete as one might naively think. Here is a snippet
> from the C++ standard (well, draft actually):
>
> """
> 12There is an implementation-defined quantity that specifies the limit
> on the depth of recursive instantiations. The result of an infinite
> recursion in instantiation is undefined.
> """
>
> The above snippet means that all template programs must finish in a
> finite number of template instantiations (although the number of
> instantiations may be large).
Any real programming language has these limitations: space in real
computers is finite.
There is a basic difference between C++ templates and the usual
runtime system. In any good old programming language, I can write
things like:
loop: goto loop; // C, C++
(letrec ((loop (lambda () (loop)))) (loop)) ; scheme
which suck time while consuming a finite amount of space. I can't
do it in C++ templates.
C++ templates don't have looping constructs, so they must recurse;
the recursive steps fall in these classes:
1. instantiations of templates that have already been fully
instantiated. A completely instantatied T<2> is, for all
practical purposes, a constant. No work needed.
2. instantiation of templates whose expansion is not yet complete;
e.g.: while processing T<4>, you try to expand P<4>, which
tries to do T<4>. This is a detectable cycle, and an error.
3. brand new instantiation of a template: has the "side effect" of
increasing the size of the environment, and launching a
template expansion computation.
4. constant folding: limited to basic arithmetic, so not an
issue.
Or, in short words: when a C++ template stops consuming space, it
also stops consuming time (halts). Try saying that about ANY program
in your favourite programming language.
>
> C++ templates don't, for instance, have the concept of "cons-cell
> identity" or "assignment" like Scheme does and C++ templates don't have
> "issues" that relate to "cons-cell identity" or "assignment". Actually,
> as the above standard quote shows, the C++ template language isn't even
> strictly Turing complete. Even so, the sets of "issues" that different
> Turing complete languages have are not all equal.
Identity (and state) are relevant for imperative languages. In purely
functional programming, identity is not an issue, and nothing has
mutable state.
What you're saying is that C++ templates do not have any of the common
imperative constructs.
So, if we accept that finite resources are a common limitation to all
programming languages in a finite universe, this ceases to be a
distinctive limitation of the C++ template language.
Having used C++ templates to implement compile-time recursive
computations, I feel that there is a good chance that someone,
with time on their hands and sufficient interest and skills, can
prove they are equally computationally equivalent to turing machines.
But, it is quite obvious that, for any reasonable definition
of "practical", they are not equivalent to primitive C++; in
fact, they are purposefully distinct from it.
Back in the Scheme world, a Scheme macro implementation is not
limited to a strict subset of the language, even if it is to
be used only at compile time. Of course, a well-behaved macro
implementation will operate within some reasonably limited
confines. But, "well-behaved" and "reasonable" are ultimately
just informal concepts which demand no precise definition until
someone has a problem with your macro.
--
A. Kanawati
NO.antounk.SPAM@comcast.net
| |
| Matthias Blume 2004-11-02, 3:58 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> Space is usually a finite resource, time is less of a resource.
> Under a reasonably stable environment, an electronic computer
> could run virtually forever.
Oh, I forgot to mention: Even if time were really limitless, this
would not help if there is a limit on space.
| |
| Vesa Karvonen 2004-11-02, 3:58 pm |
| Matthias Blume <find@my.address.elsewhere> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[color=darkred]
> No. That is not what I am claiming. But (AFAIK), there is no
> guarantee that template instantiation terminates either.
Well, I've already said it only about 3 times in this thread, but
here goes nothing...
By logical implication, the C++ standard specifies that
template instantiation must terminate.
> It has just
> been postulated that if it doesn't, it does not count as valid C++.
According to the C++ standard, a C++ compiler must have an
implementation defined (finite) maximum template instantiation
depth.
On the other hand, if a C++ template instantiation would not terminate
in finite time, the result is undefined. In other words, the C++
standard does not specify how to compute arbitrary fixed points.
> In practice, the compiler will cut template instantiation off at some
> point.
And declare an error.
> But the same happens to every other program in the world (on a
> real, practical computer).
Well, try running the "bottom" program. I'm not aware of any
valid Scheme implementation that would cut off the evaluation
of the "bottom" program.
[color=darkred]
> Thanks for the advice.
Maybe I shouldn't have given the advice... :)
[color=darkred]
> No, it is not wrong. A Turing machine which is supposed to produce a
> result must terminate.
I don't particularly like to waste time arguing with people who first
come up with strong claims and then when they are proven incorrect,
quickly change the definitions. You should just admit that
nonterminating Turing machines exist. I wont waste more time correcting
you.
-Vesa Karvonen
| |
| Bradd W. Szonye 2004-11-02, 3:58 pm |
| Vesa Karvonen wrote:
> Well, I've already said it only about 3 times in this thread, but
> here goes nothing...
>
> By logical implication, the C++ standard specifies that
> template instantiation must terminate.
But that isn't true. The C++ standard requires vendors to document the
limit of template recursion, but it does not require a finite limit.
--
Bradd W. Szonye
http://www.szonye.com/bradd
| |
| Vesa Karvonen 2004-11-02, 3:58 pm |
| Bradd W. Szonye <bradd+news@szonye.com> wrote:
> Vesa Karvonen wrote:
[color=darkred]
> But that isn't true. The C++ standard requires vendors to document the
> limit of template recursion, but it does not require a finite limit.
The finiteness is implicit. Infinite is basically the opposite of
having a limit. That is why mathematicians use terms such "improper
limit" when they define the limit of an unbounded function to be
infinite. See:
http://planetmath.org/encyclopedia/ImproperLimits.html
-Vesa Karvonen
| |
| Matthias Blume 2004-11-02, 8:57 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> On the other hand, if a C++ template instantiation would not terminate
> in finite time, the result is undefined. In other words, the C++
> standard does not specify how to compute arbitrary fixed points.
I know that. But _no_ practical computer can compute arbitrary
fixpoints.
>
> Well, try running the "bottom" program. I'm not aware of any
> valid Scheme implementation that would cut off the evaluation
> of the "bottom" program.
Then I am not aware of any valid Scheme implementation. Every Scheme
implementation will cut off the evaluation of programs that outlive
the computer (or, eventually the world) they run on.
>
> I don't particularly like to waste time arguing with people who first
> come up with strong claims and then when they are proven incorrect,
> quickly change the definitions.
I don't particularly like to waste time arguing with people who don't
bother trying to understand what I actually meant to say.
C++ template instantiation is Turing complete in the absence of a time
limit. In the presence of a time limit, no machine is Turing
complete. The C++ standard postulates the presence of a time limit.
Since in practice every machine has a time limit, such a postulate is
redundant if it does not go beyond the mere existence of the limit
(which is already given), e.g., by giving a _particular_ limit.
My point was not that C++ template instantiation is not
Turing-complete as stated, but only that it is no less Turing-complete
than any other practical mechanism for carrying out computation.
> You should just admit that nonterminating Turing machines exist.
I do. (But only in the abstract -- and that was my point.)
> I wont waste more time correcting you.
It would be a waste of time only because correcting someone who isn't
even wrong is pretty pointless. However, I am going to admit that I
spoke sloppily in my first response to this thread. To witness, you said:
> The above snippet means that all template programs must finish in a
> finite number of template instantiations (although the number of
> instantiations may be large).
.... to which I sloppily (and therefore incorrectly under a strict
reading) replied:
The same is true for any program, including Turing machines.
What I meant to say was that for a TM /to produce a result/, it must
terminate in finite time. Non-terminating TMs are just an unfortunate
consequence of the Halting problem. They are not useful in their own
right. But ruling them out invariably rules out other, terminating
programs as well -- which is why we live with them (on paper).
To come back to template instantiation: For every C++ program where
template instantiation (in the absence of a time limit) does not
diverge, there is (at least in principle) a conforming C++ compiler
that successfully performs that instantiation. Thus, the only
template programs ruled out by the restriction are the uninteresting
ones that would never terminate given unbounded space and time. Thus,
the C++ standard comes as close as one can come to restricting
template instantiation to total computable functions. (Of course,
there is -- as usual -- no decision procedure that could reliably say
for every C++ template program whether it is legal or not in some
conforming implementation.)
Matthias
| |
| Vesa Karvonen 2004-11-02, 8:57 pm |
| Matthias Blume <find@my.address.elsewhere> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> Then I am not aware of any valid Scheme implementation. Every Scheme
> implementation will cut off the evaluation of programs that outlive
> the computer (or, eventually the world) they run on.
Can you point to a semantic definition (preferably formal) of Scheme
that specifies (or requires) the behavior you are informally describing
above?
> I don't particularly like to waste time arguing with people who don't
> bother trying to understand what I actually meant to say.
I can't read minds---particular when the mind is thousands of miles
away. In newsgroups your words must stand on their own. Being sloppy
and assuming the reader is similarly sloppy is asking for trouble.
> I do. (But only in the abstract -- and that was my point.)
Thanks. However, you should note that we have not named any
particular C++ (or Scheme) implementation in this discussion. In
general, when I discuss language standards or formal definitions I treat
them *always* "in the abstract" unless I explicitly indicate otherwise.
If you want to discuss a particular C++ implementation, the situation
would be completely different.
To me, seeing the use of imprecise words like "practical" appears as an
attempt to avoid proper formalization of the issue in such a way that
any counter argument can be refuted arbitrarily by saying that it
would not be "practical".
To me, computer science is a branch of mathematics rather than a branch
of physics. Referring to physical entities in order to refute arguments
in computer science is, IMO, mostly pointless.
> It would be a waste of time only because correcting someone who isn't
> even wrong is pretty pointless.
Don't consider this post as a correction. :)
> However, I am going to admit that I spoke sloppily in my first
> response to this thread.
Writing sloppily is the same as being wrong. The reader is always
right. Your words must stand on their own. I can't read your
unmanifested thoughts or intentions.
> What I meant to say was that for a TM /to produce a result/, it must
> terminate in finite time.
Well, that isn't what you said. If you *had* originally written the
above sentence, I would have agreed to the letter of the sentence, but
pointed out that there are Turing machines that do not terminate.
> Non-terminating TMs are just an unfortunate consequence of the Halting
> problem.
I wouldn't say that nontermination is a consequence of the Halting
problem. After all, the Halting problem is defined with respect to
the concept of nontermination. (See any book on the theory of
computability.) The purpose/meaning of the Halting problem is to show
that recursive and recursively enumerable languages aren't the same.
> To come back to template instantiation: For every C++ program where
> template instantiation (in the absence of a time limit) does not
> diverge, there is (at least in principle) a conforming C++ compiler
> that successfully performs that instantiation. [...]
That sounds more like a reasonable counter argument. However, I
disagree. The writer of a template metaprogram can not safely
assume that the limit can be made arbitrary high. The C++ standard
specifies that the minimal recursion depth that must be supported by
a conforming C++ implementation is 17. See:
http://www.csci.csusb.edu/dick/c++std/cd2/limits.html
If a program is written that requires a substantially higher template
recursion depth, a conforming C++ compiler may simply reject the
program. Similar *artificial* limits do not exist in most Turing
complete languages (and now I'm not referring to "practical"
implementations, but to the actual abstract language specifications).
Do note that the C++ standard is a "contract" that works both ways. The
standard specifies what is required from a conforming C++ implementation
and what assumptions can and can not be made while constructing a
conforming C++ program. Making wild assumptions about implementation
defined limits is unsafe: a conforming C++ implementation may reject the
program.
In other words, if you construct a C++ template metaprogram that
require a particular recursion depth higher than 17, I can construct a
conforming C++ implementation that conformingly rejects your program.
> Thus, the C++ standard comes as close as one can come to restricting
> template instantiation to total computable functions.
I basically disagree. The C++ standard effectively imposes an artificial
limit on recursion depth, which allows a conforming C++ implementation
to reject practically all non-trivial C++ template metaprograms.
-Vesa Karvonen
| |
| Jens Axel Søgaard 2004-11-02, 8:57 pm |
| Vesa Karvonen wrote:
> Matthias Blume <find@my.address.elsewhere> wrote:
[color=darkred]
[color=darkred]
> Can you point to a semantic definition (preferably formal) of Scheme
> that specifies (or requires) the behavior you are informally describing=
> above?
If Matthias is talking about Proper Tail Recursion you can see a
formal definition in Will Clinger's: "Proper tail recursion and space
efficiency."
<ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz>
--=20
Jens Axel S=F8gaard
| |
| Matthias Blume 2004-11-02, 8:57 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> ... Every Scheme
>
> Can you point to a semantic definition (preferably formal) of Scheme
> that specifies (or requires) the behavior you are informally describing
> above?
No. And why should I have to? I didn't say that Scheme
implementations are required to behave the way I said they behave (but
they do so anyway).
> To me, seeing the use of imprecise words like "practical" appears as an
> attempt to avoid proper formalization of the issue in such a way that
> any counter argument can be refuted arbitrarily by saying that it
> would not be "practical".
No. "Practical" is quite precise here. It means "something you can
physically build and operate".
>
> I wouldn't say that nontermination is a consequence of the Halting
> problem. After all, the Halting problem is defined with respect to
> the concept of nontermination.
True, but not what I was refering to. Yes, there are TMs that don't
halt, and that's just a consequence of how TMs are defined. However,
the fact that we continue to _use_ a model of computation that has the
potential of diverging is a consequence of the Halting problem. If it
were possible to come up with a machine that /precisely/ captures the
set of (total) recursive functions, then we would certainly use that.
Nobody needs diverging programs, but we tolerate them because getting
rid of them also gets rid of some total computable functions. And
*that* is a consequence of the Halting problem.
> The writer of a template metaprogram can not safely assume that the
> limit can be made arbitrary high.
I didn't say she could.
> The C++ standard specifies that the minimal recursion depth that
> must be supported by a conforming C++ implementation is 17. [ ... ]
> If a program is written that requires a substantially higher template
> recursion depth, a conforming C++ compiler may simply reject the
> program.
Why didn't the C++ standard just say "17 is the number, everything
that needs more is illegal"? After all, to be on the safe side I have
to assume 17, right?
I didn't realize that the standard actually mentions such a concrete
minimum. The fact that it does changes everything: Now suddenly the
imposed limit means something. (I did say before that the limit is
meaningless as long as only its existence is postulated without giving
it a concrete value.)
> In other words, if you construct a C++ template metaprogram that
> require a particular recursion depth higher than 17, I can construct a
> conforming C++ implementation that conformingly rejects your program.
Exactly!
>
> I basically disagree. The C++ standard effectively imposes an artificial
> limit on recursion depth, which allows a conforming C++ implementation
> to reject practically all non-trivial C++ template metaprograms.
Yes, reading it from that direction your interpretation is certainly
valid. However, it does not stand in opposition to what I said. In
fact, since I said (although not in these words) that every conforming
C++ compiler must reject non-terminating template programs, these
compilers effectively have no choice but to also reject infinitely
many terminating ones. (That, again, is simply a consequence of the
Halting problem and the fact that C++ template programs without time
limit are Turing complete.) Imposing a time limit is one way of
achieving this.
By the way, in an ideal world C++ compilers would simply rejected
*all* programs. :-)
<*duck*>
Matthias
| |
| Matthias Blume 2004-11-02, 8:57 pm |
| Jens Axel Søgaard <usenet@soegaard.net> writes:
> Vesa Karvonen wrote:
>
>
>
>
> If Matthias is talking about Proper Tail Recursion
For the record: I am not. (At least not right now. Right now I am
making a meta-comment about someone (me) not talking about Proper Tail
Recursion. Or is that a meta-meta-comment? Or a
meta-meta-meta-... Never mind. :-)
> you can see a
> formal definition in Will Clinger's: "Proper tail recursion and space
> efficiency."
>
> <ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz>
Sure. But what does this have to do with anything?
Matthias
| |
| Jens Axel Søgaard 2004-11-02, 8:57 pm |
| Matthias Blume wrote:
> Sure. But what does this have to do with anything?
Explaining why a tail recursive process doesn't eat up space.
(The comment were only relevant "If Matthias is talking about
Proper Tail Recursion" - and you weren't.)
--=20
Jens Axel S=F8gaard
| |
| Bradd W. Szonye 2004-11-04, 3:58 pm |
| Vesa Karvonen wrote:
Bradd wrote:[color=darkred]
[color=darkred]
> The finiteness is implicit. Infinite is basically the opposite of
> having a limit ....
Let me rephrase, then: The C++ standard permits implementations with no
specific limit, where available memory and processing time are the only
limits. That's practically the same as having no limit at all.
--
Bradd W. Szonye
http://www.szonye.com/bradd
| |
| Gabriel Dos Reis 2005-01-23, 3:58 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Matthias Blume <find@my.address.elsewhere> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
|
| > > Matthias Blume <find@my.address.elsewhere> wrote:
| > > > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| > > [...]
| > > > > The above snippet means that all template programs must finish in a
| > > > > finite number of template instantiations (although the number of
| > > > > instantiations may be large).
| > >
| > > > The same is true for any program,
| > >
| > > So, by implication, you are claiming that the following Scheme program,
| > > that one could call (after domain theory) "bottom", terminates in a
| > > finite number of function applications:
| > >
| > > ((lambda (x) (x x))
| > > (lambda (x) (x x)))
|
| > No. That is not what I am claiming. But (AFAIK), there is no
| > guarantee that template instantiation terminates either.
|
| Well, I've already said it only about 3 times in this thread, but
| here goes nothing...
|
| By logical implication, the C++ standard specifies that
| template instantiation must terminate.
That statement is false. The C++ standard does not mandate finite
resource, in particular, it does not require that template
instantiation terminates.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-23, 3:58 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
| That sounds more like a reasonable counter argument. However, I
| disagree. The writer of a template metaprogram can not safely
| assume that the limit can be made arbitrary high. The C++ standard
| specifies that the minimal recursion depth that must be supported by
| a conforming C++ implementation is 17.
Again, that statement is false. The part of the C++ standard that
suggests that number is purely *informative* and constitutes in no way
a requirement on C++ implementation.
[...]
| > Thus, the C++ standard comes as close as one can come to restricting
| > template instantiation to total computable functions.
|
| I basically disagree. The C++ standard effectively imposes an artificial
That is false.
| limit on recursion depth, which allows a conforming C++ implementation
| to reject practically all non-trivial C++ template metaprograms.
|
| -Vesa Karvonen
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-23, 3:58 am |
| Matthias Blume <find@my.address.elsewhere> writes:
[...]
| > The C++ standard specifies that the minimal recursion depth that
| > must be supported by a conforming C++ implementation is 17. [ ... ]
| > If a program is written that requires a substantially higher template
| > recursion depth, a conforming C++ compiler may simply reject the
| > program.
|
| Why didn't the C++ standard just say "17 is the number, everything
| that needs more is illegal"? After all, to be on the safe side I have
| to assume 17, right?
Simply because the C++ standard does not think that it is a reasonable
thing to do. Vesa Karvonen is clearly misinterpreting what the C++
standard says, taking purely informative notes as normative.
|
| I didn't realize that the standard actually mentions such a concrete
| minimum.
It never meant. Vesa Karvonen made that up.
| The fact that it does changes everything: Now suddenly the
| imposed limit means something. (I did say before that the limit is
| meaningless as long as only its existence is postulated without giving
| it a concrete value.)
And the C++ committee did know that know that the limit is meaning
less. The informative note picked 17 arbitrarily, especially not a
power of 2, in the hope of conveying the committee intent that it is
meaningless.
[...]
| By the way, in an ideal world C++ compilers would simply rejected
| *all* programs. :-)
:-)
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-23, 3:58 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| > They may not be able to call "executable
| > code" in the form of compiled C++ functions, but that's not the same
| > as being a "static construct".
|
| Basically, C++ template metaprograms only perform computations on types.
and constant expressions, and expression shapes.
Consider:
template<int> struct X { };
template<int I, int J>
X<I + J> f(X<I>, X<J> ); // #1
template<int I, int J>
X<I - J> f(X<I>, X<J> ); // #2
template<int K, int L>
X<K + L> f(X<K>, X<L> ); // #3
#1 anf #2 are different. #3 is a redeclaration of #1.
In type theory terminology, C++ templates involve dependent types
(notice that the C++ community uses "dependent type" with a slightly
different meaning).
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Vesa Karvonen 2005-01-23, 8:59 pm |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | Well, I've already said it only about 3 times in this thread, but
> | here goes nothing...
> |
> | By logical implication, the C++ standard specifies that
> | template instantiation must terminate.
> That statement is false. The C++ standard does not mandate finite
> resource, in particular, it does not require that template
> instantiation terminates.
"There is an implementation-defined quantity that specifies the
limit on the depth of recursive instantiations."
("limit" is equivalent to "finite".)
Regards,
Vesa Karvonen
| |
| Vesa Karvonen 2005-01-23, 8:59 pm |
| NNTP-Posting-Host: sbz-31.cs.helsinki.fi
X-Trace: oravannahka.helsinki.fi 1106489849 10527 128.214.9.99 (23 Jan 2005 14:17:29 GMT)
X-Complaints-To: abuse@helsinki.fi
NNTP-Posting-Date: 23 Jan 2005 14:17:29 GMT
User-Agent: tin/1.6.2-20030910 ("Pabbay") (UNIX) (Linux/2.6.10-1.737_FC3smp (i686))
Xref: number1.nntp.dca.giganews.com comp.lang.scheme:55637
Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> [...]
> | That sounds more like a reasonable counter argument. However, I
> | disagree. The writer of a template metaprogram can not safely
> | assume that the limit can be made arbitrary high. The C++ standard
> | specifies that the minimal recursion depth that must be supported by
> | a conforming C++ implementation is 17.
> Again, that statement is false. [...]
My interpretation of the C++ standard is that one can
build a standards conforming C++ implementation that has 17
as the limit of template recursion depth. If that is the case,
then the designer of a C++ template metaprogram really has no
provision (within the standard) to design complex template
metaprograms (requiring high recursion depth limits) and
expect to be able to port those programs. A conforming C++
implementation might just arbitrarily choose 17 as the limit
and conformingly reject all template metaprograms that would
require a higher limit. (Whether or not the number 17 is
only an ``informative'' figure or not is not important.)
Regards,
Vesa Karvonen
| |
| Gabriel Dos Reis 2005-01-23, 8:59 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | Well, I've already said it only about 3 times in this thread, but
| > | here goes nothing...
| > |
| > | By logical implication, the C++ standard specifies that
| > | template instantiation must terminate.
|
| > That statement is false. The C++ standard does not mandate finite
| > resource, in particular, it does not require that template
| > instantiation terminates.
|
| "There is an implementation-defined quantity that specifies the
| limit on the depth of recursive instantiations."
|
| ("limit" is equivalent to "finite".)
This is where you made it up. First, it is an
"implementation-defined" quantity; so it is up to the implementation
to document what it believes to be that limit (which could just be
infinite). Second, no, "limit" is not equivalent to "finite".
("limit" is equivalent to "finite"
is yours, not something inferred from the standard. Said
differently, nothing in C++ standard requires a compiler to accept and
execute
int main() { return 0; }
and nothing prevents it to take an infinite amount of time for
compiling and executing it.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-23, 8:59 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
|
| > [...]
|
| > | That sounds more like a reasonable counter argument. However, I
| > | disagree. The writer of a template metaprogram can not safely
| > | assume that the limit can be made arbitrary high. The C++ standard
| > | specifies that the minimal recursion depth that must be supported by
| > | a conforming C++ implementation is 17.
|
| > Again, that statement is false. [...]
|
| My interpretation of the C++ standard is that one can
| build a standards conforming C++ implementation that has 17
| as the limit of template recursion depth.
Yes, one can. You can even have 1 as limit. The magic sentence is
[...] If a program contains no violations of the rules in this
International Standard, a conforming implementation shall, within
its resource limits, accept and correctly execute that program.
You can even build a conforming that rejects all C++ programs on the
ground that its resources are excedeed. That does not mean the C++
standard requires a limit. That implementation just happens to be
useless or silly.
| If that is the case,
| then the designer of a C++ template metaprogram really has no
| provision (within the standard) to design complex template
| metaprograms (requiring high recursion depth limits) and
| expect to be able to port those programs.
The same way an ordinary Scheme or C or C++ programmer has no provision
that all her programs will be accepted and executed by all
compilers/interpreters. The input does not need to be a metaprogram
for realizing that hard fact of life.
| A conforming C++
| implementation might just arbitrarily choose 17 as the limit
| and conformingly reject all template metaprograms that would
| require a higher limit. (Whether or not the number 17 is
| only an ``informative'' figure or not is not important.)
Yes, where is the problem? That does not mean the C++ standard
requires a limit. It is just that it acknowledges the fact that C++
implementations may be run on actual machines where resources may be
finite. In practice, when C++ compilers realizes that people are
routinely uing the C++ template system in unanticipated contexts, most
of them just went and increased the default limits they have choosen,
providing a switch where the defaults are not appropriate.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Anton van Straaten 2005-01-23, 8:59 pm |
| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote:
> First, it is an
> "implementation-defined" quantity; so it is up to the implementation
> to document what it believes to be that limit (which could just be
> infinite).
Coming soon: Intel C++/WT (Wormhole Technology) - because one universe just
isn't enough to compile your C++ programs!
Anton
| |
| Vesa Karvonen 2005-01-24, 3:59 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | "There is an implementation-defined quantity that specifies the
> | limit on the depth of recursive instantiations."
> | ("limit" is equivalent to "finite".)
To be more precise, what I really intended to say is that
"having a limit" is equivalent to "being bounded".
> This is where you made it up. [...]
No. It is basic mathematical terminology. (Hint: look for the term
"improper limit".)
It seems that many compiler vendors agree with my interpretation of the
sentence. Namely, when you compile a program under default compiler
options, many C++ compilers do impose an artificial, finite bound on
template recursion depth. You explicitly have to pass an option (if one
is available) to eliminate (or worse, increase) the artifical limit on
those compilers.
....
I think that the discussion of implementation defined limits in the C++
standard is a historical accident whose net effect to C++ is strongly
negative. Instead of explicitly allowing an implementation to have
limits, a language standard should essentially just specify that an
implementation either translates a program (correctly) or fails and
gives a diagnostic indicating the reason for failure. Instead, the C++
standard bends over backwards to the compiler vendors. In C++, anything
that requires the slightest hint of sophistication from an
implementation is just not required.
Regards,
Vesa Karvonen
| |
| Vesa Karvonen 2005-01-24, 3:59 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> | > They may not be able to call "executable
> | > code" in the form of compiled C++ functions, but that's not the same
> | > as being a "static construct".
> |
> | Basically, C++ template metaprograms only perform computations on types.
> and constant expressions, [...]
Not exactly. Constant *expressions* essentially form a syntactic domain.
A C++ template metaprogram can not really perform computations on
*expressions*.
Regards,
Vesa Karvonen
| |
| Vesa Karvonen 2005-01-24, 3:59 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | My interpretation of the C++ standard is that one can
> | build a standards conforming C++ implementation that has 17
> | as the limit of template recursion depth.
[...]
> Yes, where is the problem? [...]
The C++ standard explicitly mentions that there is an implementation
defined limit on recursive template instantiations. On the other hand,
the C++ standard does not seem to talk about an implementation defined
limit on the length of identifiers.
"An identifier is an arbitrarily long sequence of letters and digits.
[...] All characters are significant."
However, as anyone can easily verify, there are limits (due to finite
resources) to the lengths of identifiers that particular C++
implementations can handle.
From the point of view of formal mathematical logic, the C++ standard is
likely to be an inconsistent theory and one can prove any theorem
reqarding it. What is left is really just the various interpretations of
the C++ standard. Many compilers (*all compilers I've used*) impose (by
default) an artificial limit on recursive template instantions. However,
some of the compilers I've used do not place such an artificial limit on
the length of identifiers (instead, an identifier really can be as long
as resources allow, but not longer). It seems that there are compiler
vendors that agree with my interpretation of the C++ standard: The C++
standard does not only allow, but goes long way into actually requirng,
a(n artificial) limit on template instantion depth.
....
Unless something really new surfaces, I will probably not waste more time
discussing this topic. It would be nice to have an unambiquous
definition (proven formally) of C++, but we really do not have such
luxury.
Regards,
Vesa Karvonen
| |
| Gabriel Dos Reis 2005-01-24, 3:59 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | My interpretation of the C++ standard is that one can
| > | build a standards conforming C++ implementation that has 17
| > | as the limit of template recursion depth.
| [...]
| > Yes, where is the problem? [...]
|
| The C++ standard explicitly mentions that there is an implementation
| defined limit on recursive template instantiations.
Yes, but it does not require that the limit is finite -- which is the
main point I wanted to get straight.
| On the other hand,
| the C++ standard does not seem to talk about an implementation defined
| limit on the length of identifiers.
|
| "An identifier is an arbitrarily long sequence of letters and digits.
| [...] All characters are significant."
That is no contradiction.
| However, as anyone can easily verify, there are limits (due to finite
| resources) to the lengths of identifiers that particular C++
| implementations can handle.
Yes, but as has been pointed out in this thread at different
occasions, that simple fact (finite resources in actual life) is true
for any implementation of Turing machine.
| From the point of view of formal mathematical logic, the C++ standard is
| likely to be an inconsistent theory and one can prove any theorem
| reqarding it. What is left is really just the various interpretations of
| the C++ standard. Many compilers (*all compilers I've used*) impose (by
| default) an artificial limit on recursive template instantions. However,
| some of the compilers I've used do not place such an artificial limit on
| the length of identifiers (instead, an identifier really can be as long
| as resources allow, but not longer). It seems that there are compiler
| vendors that agree with my interpretation of the C++ standard: The C++
| standard does not only allow, but goes long way into actually requirng,
| a(n artificial) limit on template instantion depth.
Again, I think you're making this up. And of course, you'll find
hard time figuring the exact sentences of a chain of logical
inferences that lead to your statement.
Now, since you're talking about C++ implementers' intents or
interpretations of the C++ standard, I'm going to put my C++
implementor hat on.
C++, unlike C, has chosen the path of *not* imposing minimum
limits. On the other hand, the C++ committee finds it obviously
unrealistic to require every C++ implementation to pretend infinite
resources. Consequently, it was decided to let implementations decide
what they think are their limits.
For example, not too long time ago, there used to be a very low limits
(in GCC port to solaris) whereby id-expressions resulting in more than
1024 characters mangled names pushed sun's linker to its limits (with
obscure error messages). Such things could easily came from things
like map<string, list<vector<string> > > or variants, with a "poor"
name mangling scheme (as was the case in GCC-2.95 and previous). Then
Sun corrected its linker by raising the limit. And as you said
yourself, the C++ standard did not require Sun to put a limit.
As of the template instantiation depth, there is the obvious fact a
template instantiation can diverge in the sense that an instantiation
can require another instantiation and so on. The issue, from an
implementor's point of view, is whether one should let a diverging
instantiation eats of all resources or set a hard limit that users can
raise. C++ compilers, I know of, in production use (including the one
I'm working on) go with the assumption that most instantiations
do not require an excessive instantiation depth (thus setting a
default depth to hundreds or thousands). As an implementer I see a
divergent template as a potential bug in user's code, so I believe it
is a service to have him/her use "bounded instantiations". I know of
no C++ implementers who interprets the C++ standard as requiring
hard limit on instantiation depth.
| ...
|
| Unless something really new surfaces, I will probably not waste more time
| discussing this topic.
That is your choice. You've made a false statement about what the C++
standard says. When pressed hard, you've deviated the topic of
length of identifiers, and now choose to leave. I respect your
decision, but that would not prevent me from trying to get facts
straight.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-24, 3:59 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | "There is an implementation-defined quantity that specifies the
| > | limit on the depth of recursive instantiations."
|
| > | ("limit" is equivalent to "finite".)
|
| To be more precise, what I really intended to say is that
|
| "having a limit" is equivalent to "being bounded".
No. That limit could be infinite.
|
| > This is where you made it up. [...]
|
| No. It is basic mathematical terminology. (Hint: look for the term
| "improper limit".)
If you want to talk maths, that is OK too -- that is my job.
A limit in Analysis came be infinite.
| It seems that many compiler vendors agree with my interpretation of the
| sentence.
See my other message. None of my co-implementers nor those I happen
to meet at C++ meeting happen to share your interpretation with me.
[...]
| I think that the discussion of implementation defined limits in the C++
| standard is a historical accident whose net effect to C++ is strongly
| negative.
I don't believe it is a historical accident. It is a conscious
decision of not imposing any limit and at the same time not requiring
every C++ implementation to pretend finite resource. It is up to each
C++ implementation to document what its limits are.
And, as you may have noticed production use compiler construction
seems not to be a matter of being the most sophisticated, but just
doing whatever other people are doing. With the result that,
compilers copy each including bugs and ill-designs. But, I guess that
is beside the instantiation depth limit you so much desire to read from
the C++ standard.
| Instead of explicitly allowing an implementation to have
| limits, a language standard should essentially just specify that an
| implementation either translates a program (correctly) or fails and
| gives a diagnostic indicating the reason for failure.
How is that better?
| Instead, the C++
| standard bends over backwards to the compiler vendors. In C++, anything
| that requires the slightest hint of sophistication from an
| implementation is just not required.
I'm tempted to say that obvisouly you have never implemented a
C++ compiler. Have you?
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-24, 3:59 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
|
| > | > They may not be able to call "executable
| > | > code" in the form of compiled C++ functions, but that's not the same
| > | > as being a "static construct".
| > |
| > | Basically, C++ template metaprograms only perform computations on types.
|
| > and constant expressions, [...]
|
| Not exactly. Constant *expressions* essentially form a syntactic domain.
I disagree. T<2+2> is required to designate the same type as T<4> or
T<sizeof(X)> where X is a typedef for char[4]. That is not just syntax.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Vesa Karvonen 2005-01-24, 3:59 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | Unless something really new surfaces, I will probably not waste more time
> | discussing this topic.
> That is your choice. You've made a false statement about what the C++
> standard says. [...]
As far as I know, I've quoted snippets from the C++ standard accurately.
At least I haven't intentionally misquoted. However, we disagree on
how to interpet the snippets. My interpretation happens to be supported
by many compilers.
Anyone who is reading this can write a deeply recursive (say 1000
recursive instantions) template metaprogram and try it on several
compilers. The result is that many of those compiler will reject the
program, not because they run out of some actual resource (memory),
but because the compiler has an artificial template instantion depth
limit (by default).
> When pressed hard, you've deviated the topic of
> length of identifiers [...]
You misunderstood. The point was to argue (by analogy) that there is no
reason to make explicit allowances for implementation defined limits.
The C++ standard could simply say that arbitrary bounded recursive
template instantion is allowed---there is no limit. However, the C++
standard says the opposite: there is a limit.
> and now choose to leave. [...]
That has nothing to do with anything you've said in this thread. I only
replied to your messages, because I think that they deserved a reply.
The reason I'm not going to spend a lot of time on this thread is that I
have no desire to spend time dicussing C++ (in general).
The way I see it, your interpretation of the C++ standard is not
supported by (m)any existing C++ compiler vendors. The fact is that
many, if not most, compiler vendors have interpreted the C++ standard in
such a way that an artifical limit is required on template instantion
depth. I'm sure you would like the reality to be different---I would,
artificial limits are very annoying---but it isn't.
Regards,
Vesa Karvonen
| |
| Gabriel Dos Reis 2005-01-24, 3:59 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | Unless something really new surfaces, I will probably not waste more time
| > | discussing this topic.
|
| > That is your choice. You've made a false statement about what the C++
| > standard says. [...]
|
| As far as I know, I've quoted snippets from the C++ standard accurately.
You provided quotes -- somoe of them were purely informative, some
normative. But then you went on asserting that the C++ standard did
impose impose limits, which in fact could be derived from the
normative notes.
| At least I haven't intentionally misquoted. However, we disagree on
| how to interpet the snippets. My interpretation happens to be supported
| by many compilers.
And since you were appealing to implementers, I have also explained
you how the license of having limits is used. The fact that you're
observing a hard limit in your implementation is no indication that
implementrs actually believe that the C++ standard does require limits
(as opposed to *allow* limits).
| Anyone who is reading this can write a deeply recursive (say 1000
| recursive instantions) template metaprogram and try it on several
| compilers. The result is that many of those compiler will reject the
| program, not because they run out of some actual resource (memory),
| but because the compiler has an artificial template instantion depth
| limit (by default).
Yes, that is not because the C++ standard does require that limit.
It is because implementors use the allowance to control potential
divergence.
| > When pressed hard, you've deviated the topic of
| > length of identifiers [...]
|
| You misunderstood.
I don't think so.
| The point was to argue (by analogy) that there is no
| reason to make explicit allowances for implementation defined limits.
I'm tempted to say that proof by analogy is fraud. But the point is
that you failed to show why that analogy is any relevant or adequate
to prove that the C++ standard does require finite bound on
instantiation depth. To date, any quote of the C++ standard does
not support your claim.
| The C++ standard could simply say that arbitrary bounded recursive
| template instantion is allowed---there is no limit.
since you're keen on mathematic precision, let me recall a basic fact.
There is a difference between having a limit and not having a limit.
x +-> x^2 * sin(x) has no limit at infinity. x +-> x^2 has a limit at
infinity (which is infinity).
Now, here I suppose you meant "there is no finite limite". But then,
your formulation is in contradiction with the simple fact that
implementations are not bound to the impossible: implementations
accept and translate C++ programs within their limits. By saying that
there is no "finite limit on template instantiation depth", you're
requiring implementations to go beyond resource.
| However, the C++ standard says the opposite: there is a limit.
you're  about what "implementation-defined limit" is.
--
Gabriel Dos Reis
gdr@integrable-solutions.net
| |
| Vesa Karvonen 2005-01-24, 3:59 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> [...] But, I guess that
> is beside the instantiation depth limit you so much desire to read from
> the C++ standard.
I don't have to desire. The C++ standard does use the word "limit". I'm
not making a unique "creative" reading of phrases of the form "there is
a [...] limit" in the C++ standard. I'm interpreting them in the same
natural way that many C++ compiler vendors have done.
I have to admit that if the intention of the committee was to say that
there is no limit on the depth of recursive template instantions, then
they definitely figured out the best way to say it. I mean, the current
wording simply doesn't admit any other interpretation. They really nailed
it!
> | Instead of explicitly allowing an implementation to have
> | limits, a language standard should essentially just specify that an
> | implementation either translates a program (correctly) or fails and
> | gives a diagnostic indicating the reason for failure.
> How is that better?
It would be a huge improvement over the C++ standard, which just adheres
to the GIGO-principle.
> | Instead, the C++
> | standard bends over backwards to the compiler vendors. In C++, anything
> | that requires the slightest hint of sophistication from an
> | implementation is just not required.
> I'm tempted to say that obvisouly you have never implemented a
> C++ compiler. Have you?
You got me!
Regards,
Vesa Karvonen
| |
| Gabriel Dos Reis 2005-01-24, 3:59 am |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
|
| > [...] But, I guess that
| > is beside the instantiation depth limit you so much desire to read from
| > the C++ standard.
|
| I don't have to desire. The C++ standard does use the word "limit". I'm
Sure you have: The C++ standard says "implementation-defined limit",
but you go and take "limit" out of context and tell people that the C++
standard does say there is a finite limit.
| not making a unique "creative" reading of phrases of the form "there is
| a [...] limit" in the C++ standard. I'm interpreting them in the same
| natural way that many C++ compiler vendors have done.
Sure, you're making a "creative" reading, since you've chosen to clip
the phrase "implementation-defined limit" to "[...] limit".
(That reminds me of something I've heard to the effect that COBOL
is of the C-family because it has "C" as its first letter.)
| I have to admit that if the intention of the committee was to say that
| there is no limit on the depth of recursive template instantions, then
| they definitely figured out the best way to say it. I mean, the current
| wording simply doesn't admit any other interpretation. They really nailed
| it!
The C++ standard can hardly prevent determined misreading. It
is very careful in saying "implementation-defined limit"; but it can
hardly prevent someone from taking out words out of context.
|
| > | Instead of explicitly allowing an implementation to have
| > | limits, a language standard should essentially just specify that an
| > | implementation either translates a program (correctly) or fails and
| > | gives a diagnostic indicating the reason for failure.
|
| > How is that better?
|
| It would be a huge improvement over the C++ standard, which just adheres
| to the GIGO-principle.
It is no improvement over existing requirement: it does not force an
implementation to translate a template instantiation with arbitrary depth.
|
| > | Instead, the C++
| > | standard bends over backwards to the compiler vendors. In C++, anything
| > | that requires the slightest hint of sophistication from an
| > | implementation is just not required.
|
| > I'm tempted to say that obvisouly you have never implemented a
| > C++ compiler. Have you?
|
| You got me!
Ah, that might be the crucial difference in our backgrounds: I'm
talking about part of daily activity, and you're lecturing about
how un-sophisticated is something you haven't done. ;-)
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Vesa Karvonen 2005-01-24, 8:58 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | I don't have to desire. The C++ standard does use the word "limit". I'm
> Sure you have: The C++ standard says "implementation-defined limit",
> but you go and take "limit" out of context and tell people that the C++
> standard does say there is a finite limit.
IIRC, the term "implementation-defined" was mentioned in the original
thread.
> Sure, you're making a "creative" reading, since you've chosen to clip
> the phrase "implementation-defined limit" to "[...] limit".
No. When I've used the term "limit" to describe C++, I have
been talking about implementation-defined limits.
> [...] The C++ standard can hardly prevent determined misreading. [...]
Sigh. Wake me up when you have two fully standards conforming C++
implementations that accept the same language.
> | > I'm tempted to say that obvisouly you have never implemented a
> | > C++ compiler. Have you?
> |
> | You got me!
> Ah, that might be the crucial difference in our backgrounds: I'm
> talking about part of daily activity, and you're lecturing about
> how un-sophisticated is something you haven't done. ;-)
Depends on what you mean. I have designed simple languages
and written interpreters and compilers for them. I have
also studied formal semantics of programming languages.
Indeed, that is why I find the C++ standard rather wanting.
I wish you "interesting times" while implementing C++ compilers.
Regards,
Vesa Karvonen
| |
| Vesa Karvonen 2005-01-24, 8:58 am |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | Not exactly. Constant *expressions* essentially form a syntactic domain.
> I disagree. [...]
Are you saying that the domain of "expressions" is not a "syntactic
domain"?
> [...] T<2+2> is required to designate the same type as T<4> or
> T<sizeof(X)> where X is a typedef for char[4]. That is not just syntax.
Are you saying that in order to determine whether
2+2 ,
4 , and
sizeof(X)
are a constant expression require a C++ compiler to perform more than
just syntax analysis?
A more convincing case would be to say that given
enum { x = 10 };
it is not just a simple syntactic property that
x
is a constant expression.
Regards,
Vesa Karvonen
| |
| Gabriel Dos Reis 2005-01-24, 4:01 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | I don't have to desire. The C++ standard does use the word "limit". I'm
|
| > Sure you have: The C++ standard says "implementation-defined limit",
| > but you go and take "limit" out of context and tell people that the C++
| > standard does say there is a finite limit.
|
| IIRC, the term "implementation-defined" was mentioned in the original
| thread.
As was "limit" but you keep mentionning "limit" without what
qualifies it. They are not separable. They form a unit.
It is not "limit", it is "implementation-defined limit".
| > Sure, you're making a "creative" reading, since you've chosen to clip
| > the phrase "implementation-defined limit" to "[...] limit".
|
| No. When I've used the term "limit" to describe C++, I have
| been talking about implementation-defined limits.
And do you know what that means? It means a choice an implementation
makes and documents. It does not mean a finite limit the C++ standard
imposes.
| > [...] The C++ standard can hardly prevent determined misreading. [...]
|
| Sigh. Wake me up when you have two fully standards conforming C++
| implementations that accept the same language.
|
| > | > I'm tempted to say that obvisouly you have never implemented a
| > | > C++ compiler. Have you?
| > |
| > | You got me!
|
| > Ah, that might be the crucial difference in our backgrounds: I'm
| > talking about part of daily activity, and you're lecturing about
| > how un-sophisticated is something you haven't done. ;-)
|
| Depends on what you mean. I have designed simple languages
| and written interpreters and compilers for them. I have
I had no doubt you have designed simple languages or written
interpreters and compilers for them. It can be an entrtaining
exercise. But it is one thing to design, implement a compiler for a
simple language. It is another one to implement a compiler for C++.
| also studied formal semantics of programming languages.
| Indeed, that is why I find the C++ standard rather wanting.
|
| I wish you "interesting times" while implementing C++ compilers.
Thanks!
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Gabriel Dos Reis 2005-01-24, 4:01 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | Not exactly. Constant *expressions* essentially form a syntactic domain.
|
| > I disagree. [...]
|
| Are you saying that the domain of "expressions" is not a "syntactic
| domain"?
I'm disgareeing with what you wrote and I quoted. Wasn't that obvious?
| > [...] T<2+2> is required to designate the same type as T<4> or
| > T<sizeof(X)> where X is a typedef for char[4]. That is not just syntax.
|
| Are you saying that in order to determine whether
|
| 2+2 ,
| 4 , and
| sizeof(X)
|
| are a constant expression require a C++ compiler to perform more than
| just syntax analysis?
You forgot the key sentence:
T<2+2>, T<4> and T<sizeof(X)> designates the same type.
The only fact that 2+2, 4, sizeof(X) are constant expressions does not
suffice to derive that.
| A more convincing case would be to say that given
It is not a convincing case (let alone "more"), as you have left out
the part of the assertion. But, hey, this is not the first time in
this thread you'll mutate what is said.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Vesa Karvonen 2005-01-24, 4:01 pm |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...]
> | > Sure, you're making a "creative" reading, since you've chosen to clip
> | > the phrase "implementation-defined limit" to "[...] limit".
> |
> | No. When I've used the term "limit" to describe C++, I have
> | been talking about implementation-defined limits.
> And do you know what that means? It means a choice an implementation
> makes and documents.
Yes.
> It does not mean a finite limit the C++ standard imposes.
But it does *allow* such an interpretation (that a finite artifical
limit is OK). Judging from the existing C++ implementations, it is
actually a rather common interpretation. C++ explicitly makes an
allowance for an implementation to choose an artificial limit (and
document it). This, in turn, implies that portable code should not
expect to be able to rely on deeply recursive template metaprograms.
How many times do I have to say this?
The situation is very different from, say, the use of recursion in
Scheme. All Scheme implementations try to support recursion to
maximum reasonable limits. When I write Scheme programs, I don't
generally have to worry about blowing recursion depth limits. Yes, it is
possible, but there is a(n unwritten) rule that implementations
make a good effort to allow deep recursion.
Actually, I don't ever recall getting a stack overflow in Scheme except
when I've had a bug in my code. While writing C++ template metaprograms,
the consideration of template recursion depth is something that one
has no hope of avoiding. I don't think I've ever written a non-trivial
template metaprogram that didn't blow the default artificial recursion
depth limit of the C++ compilers I have used. The situation is really so
bad that template metaprogramming libraries are even partially justified
due to recursion depth optimizations in the library code.
Regards,
Vesa Karvonen
| |
| Gabriel Dos Reis 2005-01-24, 4:01 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| [...]
| > | > Sure, you're making a "creative" reading, since you've chosen to clip
| > | > the phrase "implementation-defined limit" to "[...] limit".
| > |
| > | No. When I've used the term "limit" to describe C++, I have
| > | been talking about implementation-defined limits.
|
| > And do you know what that means? It means a choice an implementation
| > makes and documents.
|
| Yes.
|
| > It does not mean a finite limit the C++ standard imposes.
|
| But it does *allow* such an interpretation (that a finite artifical
| limit is OK).
Allowing is very different from requiring. Watch your previous claims.
| Judging from the existing C++ implementations, it is
| actually a rather common interpretation. C++ explicitly makes an
| allowance for an implementation to choose an artificial limit (and
| document it). This, in turn, implies that portable code should not
| expect to be able to rely on deeply recursive template metaprograms.
no more than a portable scheme program would expect to be able to rely
on deeply recursion.
--
Gabriel Dos Reis
gdr@cs.tamu.edu
Texas A&M University -- Department of Computer Science
301, Bright Building -- College Station, TX 77843-3112
| |
| Anton van Straaten 2005-01-24, 4:01 pm |
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> | Judging from the existing C++ implementations, it is
> | actually a rather common interpretation. C++ explicitly makes an
> | allowance for an implementation to choose an artificial limit (and
> | document it). This, in turn, implies that portable code should not
> | expect to be able to rely on deeply recursive template metaprograms.
>
> no more than a portable scheme program would expect to be able
> to rely on deeply recursion.
That's incorrect. A portable Scheme program can indeed rely on deep
recursion as long as it is designed to exploit the "proper tail recursion"
specified in Section 3.5 of R5RS.
The Scheme example is a good one, not to mention being on-topic for this
group. R5RS says "A Scheme implementation is properly tail-recursive if it
supports an unbounded number of active tail calls." It doesn't say that
there is an "implementation-defined limit" on the number of active tail
calls. If it did say that, one would not be able expect to be able to
portably rely on deep recursion in the same way. In that sense at least,
Vesa has a point.
Anton
| |
| Gabriel Dos Reis 2005-01-24, 4:01 pm |
| "Anton van Straaten" <anton@appsolutions.com> writes:
| Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| > | Judging from the existing C++ implementations, it is
| > | actually a rather common interpretation. C++ explicitly makes an
| > | allowance for an implementation to choose an artificial limit (and
| > | document it). This, in turn, implies that portable code should not
| > | expect to be able to rely on deeply recursive template metaprograms.
| >
| > no more than a portable scheme program would expect to be able
| > to rely on deeply recursion.
|
| That's incorrect. A portable Scheme program can indeed rely on deep
| recursion as long as it is designed to exploit the "proper tail recursion"
| specified in Section 3.5 of R5RS.
Notice how you quickly rectrict yourself to a particular form of recursion.
--
Gabriel Dos Reis
gdr@integrable-solutions.net
| |
| Anton van Straaten 2005-01-24, 8:58 pm |
| "Gabriel Dos Reis" <gdr@integrable-solutions.net> wrote:
> "Anton van Straaten" <anton@appsolutions.com> writes:
>
> | Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> | > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> | > | Judging from the existing C++ implementations, it is
> | > | actually a rather common interpretation. C++ explicitly makes an
> | > | allowance for an implementation to choose an artificial limit (and
> | > | document it). This, in turn, implies that portable code should not
> | > | expect to be able to rely on deeply recursive template metaprograms.
> | >
> | > no more than a portable scheme program would expect to be able
> | > to rely on deeply recursion.
> |
> | That's incorrect. A portable Scheme program can indeed rely on deep
> | recursion as long as it is designed to exploit the "proper tail
recursion"
> | specified in Section 3.5 of R5RS.
>
> Notice how you quickly rectrict yourself to a particular form of
recursion.
"Quickly"? Notice how you sneakily inject an irrelevant characterization
into what ought to be a factual discussion. ;)
My statement focused on the specific way in which your statement about
portable Scheme programs was incorrect.
But since your response is being driven by the C++ argument, let's look at
that. I probably shouldn't get involved, but since this argument has all
but devolved to the "is not!" ... "is so!" stage, I can only improve
matters.
Of course, there's necessarily a limit on recursion in general - even if an
implementation doesn't impose some predefined limit, available resources
will limit it. The phrase "implementation-defined limit" arguably covers
any such scenario.
However, that phrase says nothing about whether implementations are expected
or required to make a best possible effort at supporting deep recursion.
Quite the opposite, it explicitly gives them permission to impose a
restriction which falls well short of what would otherwise be possible.
This leads to the point which Vesa has been making. This is entirely
compatible with the interpretation in the previous paragraph.
Put another way, the phrase "implementation-defined limit" in no way imposes
a burden on implementations - it's not something that they have to live up
to. It can be seen as a statement of inevitable reality, but also as
explicit permission to take a shortcut.
Arguably, omitting such a statement -- as the Scheme standard seems to do
regarding general recursion -- imposes a greater burden on implementors. It
certainly doesn't impose a lesser burden, and it means that implementors
can't point to language in the standard to justify an unnecessarily
restrictive recursion limitation.
Omitting a sentence, thereby not offering an easy excuse for limiting
recursion, is a lot easier than trying to come up with a formal way to say
"thou shalt try thine hardest not to limit recursion".
(Any similarities between this and the question of unspecified evaluation
order are entirely uncoincidental. Sometimes the things we don't explicitly
say are the most interesting.)
I'm curious, does the C++ standard mention an "implementation-defined limit"
on available heap memory? If not, why or how is that different from the
case of template recursion?
Anton
| |
| Gabriel Dos Reis 2005-01-24, 8:58 pm |
| "Anton van Straaten" <anton@appsolutions.com> writes:
| "Gabriel Dos Reis" <gdr@integrable-solutions.net> wrote:
| > "Anton van Straaten" <anton@appsolutions.com> writes:
| >
| > | Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > | > Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
| > | > | Judging from the existing C++ implementations, it is
| > | > | actually a rather common interpretation. C++ explicitly makes an
| > | > | allowance for an implementation to choose an artificial limit (and
| > | > | document it). This, in turn, implies that portable code should not
| > | > | expect to be able to rely on deeply recursive template metaprograms.
| > | >
| > | > no more than a portable scheme program would expect to be able
| > | > to rely on deeply recursion.
| > |
| > | That's incorrect. A portable Scheme program can indeed rely on deep
| > | recursion as long as it is designed to exploit the "proper tail
| recursion"
| > | specified in Section 3.5 of R5RS.
| >
| > Notice how you quickly rectrict yourself to a particular form of
| recursion.
|
| "Quickly"? Notice how you sneakily inject an irrelevant characterization
| into what ought to be a factual discussion. ;)
The characterization is no less irrelevant than your quick restriction.
Your restriction would have been relevant if you showed that template
instantiation actually admitted a tail recursive implementation
model. But you didn', nor did anybody. So, the comparison should have
focused on "comparable" things, namely assuming general recursion for
a scheme program.
[...]
| However, that phrase says nothing about whether implementations are expected
| or required to make a best possible effort at supporting deep recursion.
| Quite the opposite, it explicitly gives them permission to impose a
| restriction which falls well short of what would otherwise be possible.
| This leads to the point which Vesa has been making. This is entirely
| compatibl | | |