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 "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
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 "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
prev sibling next sibling 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 "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
prev sibling next sibling parent Gour <gour atmarama.net> writes:
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: quoted-printable

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
prev sibling next sibling 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 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 "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
prev sibling next sibling parent =?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
prev sibling next sibling 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=

 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