www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Purity in D =?UTF-8?B?4oCT?= new article

reply "David Nadlinger" <see klickverbot.at> writes:
Some of you might remember that I have been meaning to write a 
comprehensive introduction to design and use of purity for quite 
some while now – I finally got around to do so:

http://klickverbot.at/blog/2012/05/purity-in-d/

Feedback and criticism of all kinds very welcome!

David
May 27 2012
next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 27 May 2012 at 20:56:22 UTC, David Nadlinger wrote:

 Some of you might remember that I have been meaning to write a 
 comprehensive introduction to design and use of purity for 
 quite some while now – I finally got around to do so:

 http://klickverbot.at/blog/2012/05/purity-in-d/

 Feedback and criticism of all kinds very welcome!

 David


Thank you for your hard work on this, this will be extremely 
useful next time someone asks about D's take on functional purity.

I also feel this could fill a big void in the list of articles on 
dlang.org.
May 27 2012
parent "David Nadlinger" <see klickverbot.at> writes:
On Sunday, 27 May 2012 at 21:43:44 UTC, Jakob Ovrum wrote:

 I also feel this could fill a big void in the list of articles 
 on dlang.org.


If it is deemed suitable, I'll gladly submit a pull request.

David
May 28 2012
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/27/2012 1:56 PM, David Nadlinger wrote:

 Some of you might remember that I have been meaning to write a comprehensive
 introduction to design and use of purity for quite some while now – I finally
 got around to do so:

 http://klickverbot.at/blog/2012/05/purity-in-d/

 Feedback and criticism of all kinds very welcome!

 David


Reddit:

http://www.reddit.com/r/programming/comments/u84fc/purity_in_d/
May 27 2012
prev sibling next sibling parent reply "David Nadlinger" <see klickverbot.at> writes:
On Sunday, 27 May 2012 at 20:56:22 UTC, David Nadlinger wrote:

 http://klickverbot.at/blog/2012/05/purity-in-d/


The article is now on Reddit and Hacker News as well:

http://www.reddit.com/r/programming/comments/u84fc/purity_in_d/
http://news.ycombinator.com/item?id=4032248

David
May 28 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
David Nadlinger:


 http://www.reddit.com/r/programming/comments/u84fc/purity_in_d/


On Reddit "yogthos" has said:
http://www.reddit.com/r/programming/comments/u84fc/purity_in_d/c4t8czg


they're called persistent data structures, and wikipedia has a 
nice article showing how they work. These are implemented in 
languages like Haskell and Clojure, and offer performance that's 
within that of using mutable data.<


Those data structures are interesting, they are persistent so 
they remove certain classes of bugs and allow for certain 
high-level algorithms, they play well with multiple CPUs cores, 
so probably they will be handy in D too. But on a single CPU 
their performance is not so good compared to mutable flat 
array-based data structures. Idiomatic Clojure code is often 
slow, and it uses tons of RAM, several times the memory used by 
equivalent Python code. So the situation isn't as good as they 
keep saying.

Bye,
bearophile
May 28 2012
parent reply Gour <gour atmarama.net> writes:
On Mon, 28 May 2012 19:03:48 +0200
"bearophile" <bearophileHUGS lycos.com> wrote:


 But on a single CPU their performance is not so good compared to
 mutable flat array-based data structures.


How many are on a single CPU today and in the nearby tomorrow?


Sincerely,
Gour


--=20
In this endeavor there is no loss or diminution,=20
and a little advancement on this path can protect=20
one from the most dangerous type of fear.

http://atmarama.net | Hlapicina (Croatia) | GPG: 52B5C810
May 28 2012
parent "bearophile" <bearophileHUGS lycos.com> writes:
Gour:


 How many are on a single CPU today and in the nearby tomorrow?


This question turns this discussion into something vast and 
complex. The short answer is that if your purpose is to go fast, 
those immutable data structures don't seem the solution. Please 
take a look at what data structures and algorithms are used where 
people have to perform large amounts of processing (Google data 
centers, modern video games, sensory processing, and so on).

If your computational hardware looks like a GPU, with thousands 
(or more) very small cores able to run all similar code, code 
that contains few jumps and conditions, the best data structures 
aren't those. Take a look at how they implement Support Vector 
Machines on GPUs or other advanced data structures fit for that 
computational iron. There was a very active research on this.

Today I have seen cases where low-indirection-ratio data 
structures used by plain looking C programs running on a single 
core are faster (and use 1/15 of the RAM) than Clojure programs 
running on 8 cores (and I don't think having 16 cores will change 
those specific cases). This happens because (among other things) 
communication between cores has a cost, and there are parts of 
the programs that don't parallelize. Single cores that are 
programmed to work smartly on their L1 and L2 caches are fast.

In future we'll have many cores, but physics tells us that 
communication and synchronization can't be for free. So for 
several not so easily parallelized algorithms you will keep 
wanting to use not tiny cores/memory organized in a tree of 
progressively more costly communication and synchronization. For 
such iron structure, I think languages like X10 and Chapel have 
far better chance to produce efficient code than Clojure and it 
current standard data structures.

You are able to build data structures more fit for heavy 
computation for Haskell too, but Chapel and X10 languages are 
built around them from the start (example: in Chapel it's easy to 
design _complex hierarchical tiling_ strategies for data 
structures, that to me seem the key to work efficiently on the 
modern pyramid-shaped design of memories and their related 
communication costs. D design seems to have ignored all the nice 
ideas present in Chapel and X10 languages).

Bye,
bearophile
May 28 2012
prev sibling next sibling parent reply Don Clugston <dac nospam.com> writes:
On 27/05/12 22:56, David Nadlinger wrote:

 Some of you might remember that I have been meaning to write a
 comprehensive introduction to design and use of purity for quite some
 while now – I finally got around to do so:

 http://klickverbot.at/blog/2012/05/purity-in-d/

 Feedback and criticism of all kinds very welcome!

 David


For the part about floating-point calculations:

As this would be an impractical restriction, in D pure functions are 
allowed to read and write floating point flags
+ (ie, the floating point state is regarded as a variable implicitly 
passed to every pure function).


And to set the record straight -- the relaxed purity ideas were not my idea.
I forget who first said them, but it wasn't me. I just championed them.
May 29 2012
parent reply "David Nadlinger" <see klickverbot.at> writes:
On Tuesday, 29 May 2012 at 12:08:08 UTC, Don Clugston wrote:

 And to set the record straight -- the relaxed purity ideas were 
 not my idea.
 I forget who first said them, but it wasn't me. I just 
 championed them.


Unfortunately, I don't quite remember either – was it Bruno 
Medeiros? In any case, if somebody can help my memory here, I'd 
be glad to give credit to the one who came up with the original 
proposal in the article as well.

David
May 29 2012
parent Don Clugston <dac nospam.com> writes:
On 29/05/12 19:35, David Nadlinger wrote:

 On Tuesday, 29 May 2012 at 12:08:08 UTC, Don Clugston wrote:

 And to set the record straight -- the relaxed purity ideas were not my
 idea.
 I forget who first said them, but it wasn't me. I just championed them.


 Unfortunately, I don't quite remember either – was it Bruno Medeiros? In
 any case, if somebody can help my memory here, I'd be glad to give
 credit to the one who came up with the original proposal in the article
 as well.

 David


The successful proposal, using "weakly pure/strongly pure" (Sep 21 2010):

http://www.digitalmars.com/d/archives/digitalmars/D/Proposal_Relax_rules_for_pure_117735.html

It"s basically the same as this one by Bruno (Apr 29 2008), which uses 
"partially pure" and mentions an earlier post by me:

http://www.digitalmars.com/d/archives/digitalmars/D/Idea_partially_pure_functions_70762.html#N70762

And the earliest reference I could find is by me (Apr 5 2008) where I 
called it an "amoral" function.

http://www.digitalmars.com/d/archives/digitalmars/D/Grafting_Functional_Support_on_Top_of_an_Imperative_Language_69253.html

The first compiler release with pure function attributes (though not 
implemented) was released in Apr 22, 2008 and the first with pure as a 
keyword was Jan 20 2008.
So surely this is close to the original.

So now I'm confused, maybe it *was* me after all!????
Then formalized by Bruno, and later championed by me?
May 30 2012
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/27/2012 01:56 PM, David Nadlinger wrote:

 Some of you might remember that I have been meaning to write a
 comprehensive introduction to design and use of purity for quite some
 while now – I finally got around to do so:

 http://klickverbot.at/blog/2012/05/purity-in-d/

 Feedback and criticism of all kinds very welcome!

 David


Thank you very much for the article, which should already be translated 
to other languages. ;)

In addition to having a much clearer idea on the topic after reading 
your article, I have also been pleasantly surprised that one of my 
problems with the type system has also been solved by 'pure'.

I had posted about this topic on the d.D.learn forum before, that the 
return value of the following function should implicitly be convertible 
to immutable:

import std.stdio;

char[] repeat(dchar d, size_t n)
{
     char[] result;

     foreach (i; 0 .. n) {
         result ~= d;
     }

     return result;
}

void main()
{
     char[] c = repeat('-', 2);
     string s = repeat('=', 3);  // <- compilation error
}

Now I see that my problem has been not marking repeat() as 'pure'. The 
following works. Awesome! :)

char[] repeat(dchar d, size_t n) pure
{
     // ...
}

However, I would like to make a suggestion about that section in the 
article. Under the "pure and immutable – again?" section, you say

     "The effects of const and immutable on referential
      transparency have already been discussed at length"

and then continue with

     "the return value of pure functions can in some cases be
      safely cast to immutable".

That gave me the impression that the implicit conversion to immutable of 
the return value would still work even with the following definition of 
primes():

ulong[] primes(uint n, immutable char[] i, const char[] c)
{
     // ...
}

Unfortunately, that does not compile with dmd 2.059 and I think that I 
understand why. Would that be possible for you to make it clear under 
what conditions the return value can be converted to immutable.

Once again, thank you very much for a great article,
Ali

-- 
D Programming Language Tutorial: http://ddili.org/ders/d.en/index.html
May 29 2012
parent "David Nadlinger" <see klickverbot.at> writes:
On Tuesday, 29 May 2012 at 18:46:21 UTC, Ali Çehreli wrote:

 Unfortunately, that does not compile with dmd 2.059 and I think 
 that I understand why. Would that be possible for you to make 
 it clear under what conditions the return value can be 
 converted to immutable.


Okay, thanks for the feedback – will see about clarifying the 
section.

David
May 29 2012
prev sibling parent Iain Buclaw <ibuclaw ubuntu.com> writes:
On 27 May 2012 21:56, David Nadlinger <see klickverbot.at> wrote:

 Some of you might remember that I have been meaning to write a comprehens=


ive

 introduction to design and use of purity for quite some while now =96 I
 finally got around to do so:

 http://klickverbot.at/blog/2012/05/purity-in-d/

 Feedback and criticism of all kinds very welcome!

 David


Enjoyable read. :)

Makes me think about getting round to writing something someday...


--=20
Iain Buclaw

*(p < e ? p++ : p) =3D (c & 0x0f) + '0';
May 30 2012