|  | Functions without side-effects. Proposal | | |
| | | Zara |  |
|  Posted: Tue Sep 02, 2008 7:43 pm Post subject: Functions without side-effects. Proposal |  |
| |  | |
I would like to publish this proposal for enhancing C++ language. As
comp.std.c++ seems dead, I will post it in comp.lang.c++.moderated, as
I feel the intended audience reads this newsgroup usually.
Sorry for the length of the message, but I can't make it shorter.
Ruminations on a functional extension to C++
Juan Antonio Zaratiegui Vallecillo, a.k.a. Zara
zara@coit.es
Proposal for the adaptation of some ideas from functional programming
in order to improve C++ language.
** Rationale
Many problems of this language come from the existence of side-effects
in the 'functions', coming from the fact that the language is
'procedural' by definition. If we could guarantee that some functions
were such in a 'functional' way (that is, without side-effects) there
would be many cases in which:
testing the correctness of an algorithm would be easier. It would even
be possible.
the compiler would be able to optimize further, knowing when some
values/objects would be reusable as it could be sure they were not
affected by anything external.
there would be another compiler-time checking: the 'no-side-effects'
correctness, in the lines but stricter than 'const' correctness.
This is no syntactic sugar.
I hope that everything will become clearer in the following
paragraphs. Sorry for my english.
** Definition
A function or class-member function will be considered with no side
effects if:
- All parameters passed to it are passed as const value or by const
reference.
- It will return only an object of the type expressed by its
signature or an exception, and void return value is not valid. The
return value will never be a POD pointer, but it may be a smart
pointer.
- It will not modify any global object.
- It will not access any volatile value anywhere.
- Any object it creates, will also be destroyed unless it is the
return value.
- It will catch no exception, any exception generated within will
flow seamlessly to the caller.
- It will only create local objects or smart/scoped pointers, apart
form the return value. The objects will be created through
constructors with no side effects, and the destructors will have no
side effects. Allocating memory for the object data is not a
side-effect, and neither destroying it in the destructor. There should
be some kind of system to verify that the destructor rids these
allocated data, but I don´t know if it should be easy enough to force
the uses of smart/scoped pointers.
- It will only call another functions or member functions with no
side effects.
- Any time it is called with the same parameters it will return the
same value (apart form run time exceptions related with memory
exhaustion)
** Nomenclature
This is the hardest part. The best option seems to be to create a new
keyword to qualify this functions, for instance:
double sin ( double arc ) no_side_effects;
As this option may result too noisy for real programmers, an
abbreviation may be adopted:
double sin ( double arc ) nseff;
Thinking of the possibility of its availability being an option of the
compiler (but this may be unfeasible, as you may notice further on):
double sin ( double arc ) __nseff;
We may even try to reuse keywords, so as to maintain the keyword list
constant:
double sin ( double arc ) void;
This one would be a nice way to tell the compiler that the function is
void of side-effects! A draw-back: the quality of 'void' of a member
function would imply 'const', deviating from anythin seen otherwise on
the language.
I will use the qualifier no_side_effects from now on, but I am not
showing any special preference, it is just a matter of making it
easier for the reader to locate them on source samples.
Finally, there should be a special qualifier for templated functions
or templates or template member functions, which may have side effects
or not depending on the template parameters. Although I know it may
conflict with other propositions, I will use the keyword auto to
qualify these functions: the compiler will tag them as 'no side
effects' when functions accomplish all conditions listed above,
otherwise it will be tagged as normal (having side effects).
** Functions
Any function with no side effect should be tagged as that, letting the
compiler take advantage of it:
double sin ( double arc ) no_side_effects;
double sin_table[] = {
sin(0),
sin(M_PI/4),
sin(M_PI/2),
sin((3*M_PI)/4),
sin(M_PI),
sin((5*M_PI)/4),
sin((3*M_PI)/2),
sin((7*M_PI)/4)
};
In the usual C++ compiler (without no_side_effects), this structure
will be calculated at run time through eight calls to sin. The use of
the function tag may enable the compiler to use some compile time
library to evaluate sin, and fill the table without calling once the
function sin at run time.
This concept could be extended to no_side_effects functions defined
within the source code: the compiler may opt to evaluate them (if all
arguments are constant) and use the values calculated as constants
instead of living the calculations for run time.
** Classes
For an object to be used within a no side effect function, it should
constructed through an adequate constructor:
- All parameters passed to it are passed as const value or by const
reference.
- It will not modify any global, static object and/or mutable object.
- It will not access any volatile value anywhere.
- It will catch no exception, any exception generated within will
flow seamlessly to the caller.
- It will only create local objects or smart/scoped pointers. Any
data allocated by it, should be destroyed by the destructor. It should
be exception-safe, in the hardest way.
- It will only call another functions with no side effects.
- Any time it is called with the same parameters it will return the
same value (save for run time exceptions related with memory
exhaustion).
This constructors will be specifically qualified, i.e.:
class OneClass {
// this constructor has side-effects
OneClass( double& whatever );
// this constructor has no side-effects
OneClass( const int whatever ) no_side_effects;
};
** Member functions
A member function may be qualified as no_side_effects if it
accomplishes all conditions expressed for functions, plus:
the object passed to it (*this) is more than const: it behaves as a
const and no volatile or static members may be accessed.
** Function templates
A member function may be qualified as no_side_effects if it
accomplishes all conditions expressed for functions. When trying to
instantiate, the type of the parameters passed are critical. If the
instantiation renders valid, it will have more priority than all other
possibilities of the same characteristics.
template <class SOME_CLASS>
int calc_something() {
return SOME_CLASS::evaluate(22);
}
template <class SOME_CLASS>
static int calc_something() no_side_effects {
return SOME_CLASS::evaluate(42);
}
class SEclass {
private:
static int store_it;
public:
static int evaluate(int n) const {
return store_it=n;
}
};
class NSEclass {
public:
int evaluate(int n) no_side_effects {
return n;
}
};
It is evident that calc_something<SEclass> should return 22, while
calc_something<NSEclass> should return 42.
Function templates may inherit its quality of 'side-effect-ness' from
the template parameters, i.e.:
template <class SOME_CLASS>
int calc_other_thing() auto {
return SOME_CLASS::evaluate(6);
}
Thus, calc_other_thing<SEclass> is const, while
calc_other_thing<NSEclass> is no_side_effects.
** Template classes
All restrictions applicable to classes are of use, plus constructors
and member functions may be qualified as auto as in the case of
function templates.
** Template functions as members of classes and template classes
All restrictions applicable to member functions of classes and
template classes, they me qualified as auto.
** Future possiblities
Everything exposed above is only an skeleton, but I feel that the
existence of a functional paradigm aside with all the others already
living in C++, would made it a more expressive way of programming.
Maybe, someone at Boost may take advantage of it. What about
boost::has_no_side_effects?
On the other hand, codign guidelines suchs as MISRA-C++ may be
rewritten to rely on the existence of this model, as the necessity of
this functions withous side-effects is stated repeatedly in them.
** Final word
Everything expressed here is open to comments and criticism, of
course. I only beg for your forgiveness if it has already been
discussed (and maybe dismissed); if there are some inconsistencies
coming from a not deep enough knowledge of C++; or if anyone feels
hurt by anything said here; it is all my fault.
Juan Antonio Zaratiegui Vallecillo, a.k.a Zara
zara@coit.es
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Andrei Alexandrescu | |
| | Posted: Wed Sep 03, 2008 8:58 am Post subject: Re: Functions without side-effects. Proposal | |
| | | |
Alberto Ganesh Barbati wrote:
| Quote: | Zara ha scritto:
Proposal for the adaptation of some ideas from functional programming
in order to improve C++ language.
I'm sorry to sound dismissive, but it seems to me that most of this
proposal can either be achieved with constexpr or be automatically
detected by the compiler. In the rest of the cases, your "no side
effect" concept is just an optimization hint that doesn't change the
language semantic, so it would be better handled using an attribute
rather than a new syntax. Or am I missing something?
Ganesh
|
I think the proposal does have merit. It essentially introduces pure
functions, so it would allow writing entire parts of programs in pure
functional style.
There are some issues with proving that a function is pure. Worst thing
is object construction by a pure function. The compiler would have to
prove that the constructor creates an independent value that does not
alias anything else. That's hard to do modularly with existing
constructor semantics. But it can be done.
By the way, a pure function doesn't need to take constant objects. As
long as its output only depends on its input and it has no side effects,
the function is pure all right. Const doesn't help any in this case
because it's only skin deep (intransitive).
Andrei
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | David Abrahams | |
| | Posted: Wed Sep 03, 2008 6:55 pm Post subject: Re: Functions without side-effects. Proposal | |
| | | |
on Wed Sep 03 2008, Andrei Alexandrescu <SeeWebsiteForEmail-AT-erdani.org> wrote:
| Quote: | There are some issues with proving that a function is pure. Worst thing
is object construction by a pure function. The compiler would have to
prove that the constructor creates an independent value that does not
alias anything else.
|
IIUC that's true for some definition of "value," by the definition of
the language. I presume you mean to include data accessible through
pointers as part of the value?
| Quote: | That's hard to do modularly with existing constructor semantics. But
it can be done.
|
I don't see how you could possibly do it. We don't have anything in the
language that allows us to annotate a pointer as denoting a relationship
to a different object as opposed to a referencing a dynamically
allocated part of the object's value.
| Quote: | By the way, a pure function doesn't need to take constant objects. As
long as its output only depends on its input and it has no side effects,
the function is pure all right. Const doesn't help any in this case
because it's only skin deep (intransitive).
|
Doesn't help with what?
--
Dave Abrahams
BoostPro Computing
LINK
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Zara | |
| | Posted: Wed Sep 03, 2008 7:01 pm Post subject: Re: Functions without side-effects. Proposal | |
| | | |
On Tue, 2 Sep 2008 23:44:03 CST, Alberto Ganesh Barbati
<AlbertoBarbati@libero.it> wrote:
| Quote: | Zara ha scritto:
Proposal for the adaptation of some ideas from functional programming
in order to improve C++ language.
I'm sorry to sound dismissive, but it seems to me that most of this
proposal can either be achieved with constexpr or be automatically
detected by the compiler. In the rest of the cases, your "no side
effect" concept is just an optimization hint that doesn't change the
language semantic, so it would be better handled using an attribute
rather than a new syntax. Or am I missing something?
|
I didn´t know aboiut constexpr (I,ve just read n2235.pdf). As I see
it, constexpr are a subset of the no_side_effects functions I have
described.
I think that my proposal is more general, as it includes the
possibility of library functions to be tagged as no_side_effects,
complex functions to be tagged also.
In itself, it is as much an optimization hint as a set of restrictions
to be checked at compile-time. I don´t know (yet) if there is any
compiler with the possibility to check such a set of restrictions.
In fact, I am almost certain that these sets of restrictions (or at
least, part of them) do change language semantic.
Best regards,
Zara
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | restor | |
| | Posted: Wed Sep 03, 2008 8:58 pm Post subject: Re: Functions without side-effects. Proposal | |
| Quote: | ** Definition
- It will not access any volatile value anywhere.
|
what about this function? Is it pure (side effect free)?
const int FACTOR = 2;
const int increase( const int i ) {
return FACTOR * i;
}
Does it side-effect-free-ness change if it is linked with another
library that executes:
extern int FACTOR;
int mutable_factor = const_cast<int>(FACTOR);
increase(4);
mutable_factor = 3;
increase(4);
Regards,
&rzej
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | RobThaBlob | |
| | Posted: Wed Sep 03, 2008 8:58 pm Post subject: Re: Functions without side-effects. Proposal | |
| | | |
On Sep 3, 9:58 am, Andrei Alexandrescu <SeeWebsiteForEm...@erdani.org>
wrote:
| Quote: | Alberto Ganesh Barbati wrote:
Zara ha scritto:
Proposal for the adaptation of some ideas from functional programming
in order to improve C++ language.
I'm sorry to sound dismissive, but it seems to me that most of this
proposal can either be achieved with constexpr or be automatically
detected by the compiler. In the rest of the cases, your "no side
effect" concept is just an optimization hint that doesn't change the
language semantic, so it would be better handled using an attribute
rather than a new syntax. Or am I missing something?
Ganesh
I think the proposal does have merit. It essentially introduces pure
functions, so it would allow writing entire parts of programs in pure
functional style.
There are some issues with proving that a function is pure. Worst thing
is object construction by a pure function. The compiler would have to
prove that the constructor creates an independent value that does not
alias anything else. That's hard to do modularly with existing
constructor semantics. But it can be done.
By the way, a pure function doesn't need to take constant objects. As
long as its output only depends on its input and it has no side effects,
the function is pure all right. Const doesn't help any in this case
because it's only skin deep (intransitive).
|
{ Signature and banner removed; please don't quote unnecessary material.
-mod }
I'd have to agree, and would favour the use of the keyword 'pure' for
such purposes to indicate that it is a 'pure' functional-style
function.
The ability to have pure functions could, in turn, lead to many other
applications from FP style, such as currying (one or more parameter
being fixed, generating a new variant of the function at the
compiler's discretion).
However, it may be that such an approach may complicate the language
yet more, and be better pursued by using Foreign Function Interfaces
between a true FP language and procedural languages.
Rob Grainger
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Alberto Ganesh Barbati | |
| | Posted: Thu Sep 04, 2008 1:46 am Post subject: Re: Functions without side-effects. Proposal | |
restor ha scritto:
| Quote: | ** Definition
- It will not access any volatile value anywhere.
what about this function? Is it pure (side effect free)?
const int FACTOR = 2;
const int increase( const int i ) {
return FACTOR * i;
}
Does it side-effect-free-ness change if it is linked with another
library that executes:
extern int FACTOR;
int mutable_factor = const_cast<int>(FACTOR);
increase(4);
mutable_factor = 3;
increase(4);
|
This code does not try to modify FACTOR, so why should it affect the
side-effect-ness of function increase()? Maybe you intended to write:
int& mutable_factor = const_cast<int&>(FACTOR);
In this case the behaviour is undefined, according to 7.1.5.1/4: "[...]
any attempt to modify a const object during its lifetime (3. results
in undeï¬ned behavior", so the question is moot.
Ganesh
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Andrei Alexandrescu | |
| | Posted: Thu Sep 04, 2008 1:58 am Post subject: Re: Functions without side-effects. Proposal | |
| | | |
David Abrahams wrote:
| Quote: | on Wed Sep 03 2008, Andrei Alexandrescu <SeeWebsiteForEmail-AT-erdani.org> wrote:
There are some issues with proving that a function is pure. Worst thing
is object construction by a pure function. The compiler would have to
prove that the constructor creates an independent value that does not
alias anything else.
IIUC that's true for some definition of "value," by the definition of
the language. I presume you mean to include data accessible through
pointers as part of the value?
|
Entities worth working with for purity purposes are entire access
graphs, e.g. any data reachable starting from a given object.
It all depends on how ambitious a purity subsystem wants to be. If no
private mutable data is allowed inside a pure function and no
user-defined object construction is allowed inside a pure function, then
it's easy to typecheck a pure function:
a) No mutation is allowed inside a pure function.
b) A pure function can only call other pure functions.
Assuming constructors cannot be pure, ensuring a and b is all that's
needed for ensuring a pure modular subsystem in C++.
Things get about an order of magnitude more interesting when pure
functions are allowed to mutate private state. Arguably, this is a pure
function:
unsigned factorial(unsigned n)
{
unsigned result = 1;
for (unsigned i = 1; i < n; ++i) result *= i;
return result;
}
It is pure because it output only depends on its input. However, by a
rigid definition of purity it's not pure because it mutates result and
i. But that's an implementation detail so factorial should typecheck as
pure. This is where the notion of private state and comes into play. If
allowing private user-defined objects is needed, disjoint object graphs
come into play too.
| Quote: | That's hard to do modularly with existing constructor semantics. But
it can be done.
I don't see how you could possibly do it. We don't have anything in the
language that allows us to annotate a pointer as denoting a relationship
to a different object as opposed to a referencing a dynamically
allocated part of the object's value.
|
It can be done by annotating constructors and typechecking them in a
special way that makes those annotated constructor more restrictive. D
will do that. The story is not quite simple and I doubt there will be
extensive information on it until my book on D comes out.
| Quote: | By the way, a pure function doesn't need to take constant objects. As
long as its output only depends on its input and it has no side effects,
the function is pure all right. Const doesn't help any in this case
because it's only skin deep (intransitive).
Doesn't help with what?
|
Typechecking pure constructors.
Andrei
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Alberto Ganesh Barbati | |
| | Posted: Thu Sep 04, 2008 9:28 pm Post subject: Re: Functions without side-effects. Proposal | |
Zara ha scritto:
| Quote: | In fact, I am almost certain that these sets of restrictions (or at
least, part of them) do change language semantic.
|
There's a quick test to discern that. Write a well-formed program with
the proposed decoration. Then, remove *all* decorations. If the program
is still well-formed and produces the same observable behaviour, then
the decoration did no affect the language semantic.
Ganesh
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| | | Edward Rosten | |
| | Posted: Thu Sep 04, 2008 10:43 pm Post subject: Re: Functions without side-effects. Proposal | |
| | | |
On Sep 4, 3:28 pm, Alberto Ganesh Barbati <AlbertoBarb...@libero.it>
wrote:
| Quote: | Zara ha scritto:
In fact, I am almost certain that these sets of restrictions (or at
least, part of them) do change language semantic.
There's a quick test to discern that. Write a well-formed program with
the proposed decoration. Then, remove *all* decorations. If the program
is still well-formed and produces the same observable behaviour, then
the decoration did no affect the language semantic.
|
It depends if overloading based on pureness is allowed (muck like
const). For instance, functions like acos() affect the global errno
variable. There you could have two prorotpyes:
double acos(double);
double acos(double) pure;
If you can only call pure functions from within pure functions (like
const methods), then the two can potentially produce different
retults:
double foo(double d) pure {return acos(d);}
acos(0);
foo(-10);
if(errno == EDOM)
...
Another point is that pure functions of compile-time constants could
result in compile time constants, which would be useful.
Finally, if it really helps correctness and optimization, then is it
worth it? With many programs, you could remove all consts, and still
get the same results, bit I find them useful. Likewise, inline should
not be necessary either.
-Ed
--
[ See LINK for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
| |
| Page 1 of 3 .:. Goto page 1, 2, 3 Next | |
|
|
