On Thursday, 15 May 2014 at 10:31:47 UTC, luka8088 wrote:
On 15.5.2014. 11:45, Don wrote:
On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
On Thu, 15 May 2014 05:51:14 +0000
via Digitalmars-d <[email protected]> wrote:
Yep, purity implies memoing.
No, it doesn't. _All_ that it means when a function is pure
is that
it cannot
access global or static variables unless they can't be
changed after
being
initialized (e.g. they're immutable, or they're const value
types),
and it
can't call any other functions which aren't pure. It means
_nothing_
else. And
it _definitely_ has nothing to do with functional purity.
Now, combined with other information, you _can_ get
functional purity
out it -
e.g. if all the parameters to a function are immutable, then
it _is_
functionally pure, and optimizations requiring functional
purity can
be done
with that function. But by itself, pure means nothing of the
sort.
So, no, purity does _not_ imply memoization.
- Jonathan M Davis
Um. Yes it does. http://dlang.org/function.html#pure-functions
"functional purity (i.e. the guarantee that the function will
always
return the same result for the same arguments)"
The fact that it should not be able to effect or be effected
by the
global state is not a basis for purity, but rather a
consequence.
Even other sources are consistent on this matter, and this is
what
purity by definition is.
Please note: D's 'pure' annotation does *not* mean that the
function is
pure. It means that it is statically verified to be OK to call
it from a
pure function.
The compiler determines if a function is pure, the programmer
never does.
There are two things going on here, and they are quite
distinct.
(1) Really the keyword should be something like '@noglobal',
rather than
'pure'. It's called pure for historical reasons. To reduce
confusion
I'll call D's pure '@noglobal' and the functional languages
pure
'@memoizable'.
But it turns out that @memoizable isn't actually an interesting
property, whereas '@noglobal' is.
"No global state" is a deep, transitive property of a function.
"Memoizable" is a superficial supersetextra property which the
compiler
can trivially determine from @noglobal.
Suppose you have function f(), which calls function g().
If f does not depend on global state, then g must not depend
on global
state.
BUT if f() can be memoizable even if g() is not memoizable.
This approach used by D enormously increases the number of
functions
which can be statically proven to be pure. The nomenclature
can create
confusion though.
(2) Allowing GC activity inside a @noglobal function does
indeed weaken
our ability to memoize.
The compiler can still perform memoizing operations on most
functions
that return GC-allocated memory, but it's more difficult. We
don't yet
have data on how much of a problem this is.
An interesting side-effect of the recent addition of @nogc to
the
language, is that we get this ability back.
Yeah, I read all about weak/string purity and I do understand
the
background. I was talking about strong purity, maybe I should
pointed
that out.
So, to correct myself: As I understood strong purity implies
memoization. Am I correct?
Yes. 'strong pure' means pure in the way that the functional
language crowd means 'pure'.
'weak pure' just means doesn't use globals.
But note that "strong purity" isn't an official concept, it was
just the terminology I used when explain to Walter what I meant.
I don't like the term because it's rather misleading
-- in reality you could define a whole range of purity strengths
(more than just two).
The stronger the purity, the more optimizations you can apply.
