OT: Hygiene in C++ templates? (was Re: Separate compilation)

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

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

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 depe
nd
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

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

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

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

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

Bradd W. Szonye <bradd+news@szonye.com> wrote:
> Antoun Kanawati wrote: 

> 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 <find@my.address.elsewhere> wrote:
> Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
[...] 

> 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

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