www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Paper acknowledges positively D's approach to purity

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
David Wagner was kind enough to let me know about a paper that he and 
his students wrote recently:

http://www.cs.berkeley.edu/~daw/papers/pure-ccs08.pdf

It's a great honor and validation to be acknowledged in a paper of such 
quality and to see D's approach to purity not only mentioned, but in 
praise terms nonetheless (section 9).


Andrei
Sep 14 2008
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 David Wagner was kind enough to let me know about a paper that he and 
 his students wrote recently:
 
 http://www.cs.berkeley.edu/~daw/papers/pure-ccs08.pdf
 
 It's a great honor and validation to be acknowledged in a paper of such 
 quality and to see D's approach to purity not only mentioned, but in 
 praise terms nonetheless (section 9).

Reddit: http://www.reddit.com/r/programming/comments/71h8z/verifiable_functional_purity_in_java/
Sep 14 2008
prev sibling next sibling parent reply "Bill Baxter" <wbaxter gmail.com> writes:
On Mon, Sep 15, 2008 at 7:42 AM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:
 David Wagner was kind enough to let me know about a paper that he and his
 students wrote recently:

 http://www.cs.berkeley.edu/~daw/papers/pure-ccs08.pdf

 It's a great honor and validation to be acknowledged in a paper of such
 quality and to see D's approach to purity not only mentioned, but in praise
 terms nonetheless (section 9).

Congrats to all involved in the design! Is this the first mention of D in such a peer-reviewed research publication? --bb
Sep 15 2008
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:
 On Mon, Sep 15, 2008 at 7:42 AM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 David Wagner was kind enough to let me know about a paper that he and his
 students wrote recently:

 http://www.cs.berkeley.edu/~daw/papers/pure-ccs08.pdf

 It's a great honor and validation to be acknowledged in a paper of such
 quality and to see D's approach to purity not only mentioned, but in praise
 terms nonetheless (section 9).

Congrats to all involved in the design! Is this the first mention of D in such a peer-reviewed research publication?

Yes, in fact. We've been very slow in getting stuff published about D, but that will change once I finish my PhD. Andrei
Sep 15 2008
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Robert Jacques:
 this year I had a MICCAI workshop paper  
 (http://www.cse.buffalo.edu/hpmiccai/program.html, see Towards Real-Time  
 Radiation Therapy: GPU Accelerated Superposition/Convolution)

Nice, it says:
We have adapted the superposition/convolution algorithm to the GPU using a
combination of NVIDA's Compute Unified Device Architecture (CUDA) software
development environment and the Digital Marsí D programming language for our
implementation.<

How have you used D with CUDA? I'd like to know a bit more technical details. And do you know about BSGP (that I think is a step toward the future of such things)? http://www.kunzhou.net/ Bye, bearophile
Sep 15 2008
prev sibling next sibling parent reply bearophile <bearophile lycos.com> writes:
Andrei Alexandrescu:
 It's a great honor and validation to be acknowledged in a paper of such 
 quality and to see D's approach to purity not only mentioned, but in 
 praise terms nonetheless (section 9).

It seems to contain some comments that are not a praise too:
While this approach avoids the need to eliminate mutable state and determinism
from the global scope, there is a substantial cost in expressivity as it
prevents pure functions from making any use of impure functions and methods.
The result is essentially of a partition of the program into imperative and
purely functional portions, whereas our approach allows pure functions to make
full use of the rest of the program, limited only by the references they hold.<

Anyway, in Java, Python, and few articles I have read about such topics they all talk about immutable objects and variables, I too use this term generally. Commonly used (correct) terms are important to help people quickly create clear connections between concepts and their names, so I think D2 may chose to use a more correct term "immutable" to denote that concept. There's time to change terms still, not many people are using D2 yet. Bye, bearophile
Sep 15 2008
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
bearophile wrote:
 Andrei Alexandrescu:
 It's a great honor and validation to be acknowledged in a paper of
 such quality and to see D's approach to purity not only mentioned,
 but in praise terms nonetheless (section 9).

It seems to contain some comments that are not a praise too:
 While this approach avoids the need to eliminate mutable state and
 determinism from the global scope, there is a substantial cost in
 expressivity as it prevents pure functions from making any use of
 impure functions and methods. The result is essentially of a
 partition of the program into imperative and purely functional
 portions, whereas our approach allows pure functions to make full
 use of the rest of the program, limited only by the references they
 hold.<


Any paper will mention the disadvantages of related work in the pertinent section. I'm not worried about that at all. Their system is more expressive but also considerably more complex. That's not necessarily bad, it's a different point in tradeoff space.
 Anyway, in Java, Python, and few articles I have read about such
 topics they all talk about immutable objects and variables, I too use
 this term generally. Commonly used (correct) terms are important to
 help people quickly create clear connections between concepts and
 their names, so I think D2 may chose to use a more correct term
 "immutable" to denote that concept. There's time to change terms
 still, not many people are using D2 yet.

I think that's a good point. Andrei
Sep 15 2008
next sibling parent "Dave" <Dave_member pathlink.com> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:galdu2$pou$1 digitalmars.com...
 bearophile wrote:
 Andrei Alexandrescu:
 It's a great honor and validation to be acknowledged in a paper of
 such quality and to see D's approach to purity not only mentioned,
 but in praise terms nonetheless (section 9).

It seems to contain some comments that are not a praise too:
 While this approach avoids the need to eliminate mutable state and
 determinism from the global scope, there is a substantial cost in
 expressivity as it prevents pure functions from making any use of
 impure functions and methods. The result is essentially of a
 partition of the program into imperative and purely functional
 portions, whereas our approach allows pure functions to make full
 use of the rest of the program, limited only by the references they
 hold.<



"The result is essentially of a partition of the program into imperative and purely functional portions..." Isn't that a bit strong, even in the context of that paper, since pure functions and their return values can be used anywhere in the imperative 'portion' of a program? Also, couldn't D2's ability to initialize invariants at runtime (for example in a class or struct ctor) for use in pure functions bridge most of that gap fairly reasonably in many cases? For example, in the article's Voting Machine, a class with invariant data members representing a de/serialized Ballot could be instantiated and the results kept invariant until after the data was verified with pure function(s)?
 Any paper will mention the disadvantages of related work in the pertinent 
 section. I'm not worried about that at all. Their system is more 
 expressive but also considerably more complex. That's not necessarily bad, 
 it's a different point in tradeoff space.

Given that invariants are vital to 'pure' programming in D, could the tradeoff be made less onerous for the programmer with a few relatively minor changes to the invariant initialization spec? One thing off-hand that makes it tougher to use invariant reference types is the requirement to cast during initialization (which is also inconsistent with value types): class C { invariant int sz; invariant int[] arr; this(size_t sz) { this.sz = sz; // Value types don't require a cast to invariant (same with UDT's). //arr = new int[sz]; arr = cast(invariant int[])new int[sz]; // Reference types do. //foreach(i, ref val; arr) foreach(i, ref val; cast(int[])arr) { val = i; } // Or for(size_t i = 0; i < sz; i++) { //arr[i] = i; cast(int)arr[i] = i; } } ~this() { delete arr; // OK in dtor. } } - Dave
Sep 15 2008
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Andrei Alexandrescu wrote:
 bearophile wrote:
 Andrei Alexandrescu:
 It's a great honor and validation to be acknowledged in a paper of
 such quality and to see D's approach to purity not only mentioned,
 but in praise terms nonetheless (section 9).

It seems to contain some comments that are not a praise too:
 While this approach avoids the need to eliminate mutable state and
 determinism from the global scope, there is a substantial cost in
 expressivity as it prevents pure functions from making any use of
 impure functions and methods. The result is essentially of a
 partition of the program into imperative and purely functional
 portions, whereas our approach allows pure functions to make full
 use of the rest of the program, limited only by the references they
 hold.<


Any paper will mention the disadvantages of related work in the pertinent section. I'm not worried about that at all. Their system is more expressive but also considerably more complex. That's not necessarily bad, it's a different point in tradeoff space.

I haven't yet read the whole paper, haven't had the time yet, but, are we really restricted to the "Functions marked with the pure keyword must have only invariant arguments, can only read invariant global state, and can only call other pure methods." ? Don and I discussed an idea some time ago, called partially pure functions (aka locally pure, aka contextually pure): http://www.digitalmars.com/d/archives/digitalmars/D/Idea_partially_pure_functions_70762.html which would lift some of those restrictions, in a way that is safe and sound, thus allowing more expressiveness (significantly, IMO). As a side note, kudos to that paper for the best description of Monads I've seen so far: "Monads can be defined to allow writing in a more imperative style, in which each operation takes an input state and returns a monad instance that wraps the result along with auxiliary information such as side effects." I've read whole pages of text about Monads that didn't explain as well as this paragraph what a monad is, in the general sense. -- Bruno Medeiros - Software Developer, MSc. in CS/E graduate http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Sep 19 2008
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Bill Baxter wrote:
 On Fri, Sep 19, 2008 at 8:31 PM, Bruno Medeiros
 <brunodomedeiros+spam com.gmail> wrote:
 Andrei Alexandrescu wrote:
 bearophile wrote:
 Andrei Alexandrescu:
 It's a great honor and validation to be acknowledged in a paper of
 such quality and to see D's approach to purity not only mentioned,
 but in praise terms nonetheless (section 9).

 While this approach avoids the need to eliminate mutable state and
 determinism from the global scope, there is a substantial cost in
 expressivity as it prevents pure functions from making any use of
 impure functions and methods. The result is essentially of a
 partition of the program into imperative and purely functional
 portions, whereas our approach allows pure functions to make full
 use of the rest of the program, limited only by the references they
 hold.<


section. I'm not worried about that at all. Their system is more expressive but also considerably more complex. That's not necessarily bad, it's a different point in tradeoff space.

really restricted to the "Functions marked with the pure keyword must have only invariant arguments, can only read invariant global state, and can only call other pure methods." ? Don and I discussed an idea some time ago, called partially pure functions (aka locally pure, aka contextually pure): http://www.digitalmars.com/d/archives/digitalmars/D/Idea_partially_pure_functions_70762.html which would lift some of those restrictions, in a way that is safe and sound, thus allowing more expressiveness (significantly, IMO).

The funny thing is that D's pure hasn't been implemented yet. Walter added the keyword to the compiler, but I'm pretty sure it still doesn't do much of anything useful. I guess the fine paper was referring to the spec? --bb

Yeah, it probably refers to the accu-functional.pdf presented by Andrei, although I guess the author could have accessed some less-public discussions/talks/documents of Walter's "Inner Circle". :7 -- Bruno Medeiros - Software Developer, MSc. in CS/E graduate http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Sep 19 2008
prev sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Fri, Sep 19, 2008 at 8:31 PM, Bruno Medeiros
<brunodomedeiros+spam com.gmail> wrote:
 Andrei Alexandrescu wrote:
 bearophile wrote:
 Andrei Alexandrescu:
 It's a great honor and validation to be acknowledged in a paper of
 such quality and to see D's approach to purity not only mentioned,
 but in praise terms nonetheless (section 9).

It seems to contain some comments that are not a praise too:
 While this approach avoids the need to eliminate mutable state and
 determinism from the global scope, there is a substantial cost in
 expressivity as it prevents pure functions from making any use of
 impure functions and methods. The result is essentially of a
 partition of the program into imperative and purely functional
 portions, whereas our approach allows pure functions to make full
 use of the rest of the program, limited only by the references they
 hold.<


Any paper will mention the disadvantages of related work in the pertinent section. I'm not worried about that at all. Their system is more expressive but also considerably more complex. That's not necessarily bad, it's a different point in tradeoff space.

I haven't yet read the whole paper, haven't had the time yet, but, are we really restricted to the "Functions marked with the pure keyword must have only invariant arguments, can only read invariant global state, and can only call other pure methods." ? Don and I discussed an idea some time ago, called partially pure functions (aka locally pure, aka contextually pure): http://www.digitalmars.com/d/archives/digitalmars/D/Idea_partially_pure_functions_70762.html which would lift some of those restrictions, in a way that is safe and sound, thus allowing more expressiveness (significantly, IMO).

The funny thing is that D's pure hasn't been implemented yet. Walter added the keyword to the compiler, but I'm pretty sure it still doesn't do much of anything useful. I guess the fine paper was referring to the spec? --bb
Sep 19 2008
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 15 Sep 2008 04:52:20 -0400, Bill Baxter <wbaxter gmail.com> wrote:
 Congrats to all involved in the design!  Is this the first mention of
 D in such a peer-reviewed research publication?

Yes and no. It's the first time the language has been commented on (that I know of), but a year ago I had a conference poster (At AAPM) which mentioned D and this year I had a MICCAI workshop paper (http://www.cse.buffalo.edu/hpmiccai/program.html, see Towards Real-Time Radiation Therapy: GPU Accelerated Superposition/Convolution) in addition to some posters (at AAPM and ASTRO). I wouldn't be surprised if there are others that have used D in their research and have cited it.
Sep 15 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Mon, Sep 15, 2008 at 10:54 PM, Robert Jacques <sandford jhu.edu> wrote:
 On Mon, 15 Sep 2008 04:52:20 -0400, Bill Baxter <wbaxter gmail.com> wrote:
 Congrats to all involved in the design!  Is this the first mention of
 D in such a peer-reviewed research publication?

Yes and no. It's the first time the language has been commented on (that I know of),

Yeh, that's more what I meant. Being commented on as a language by people who study such things.
 but a year ago I had a conference poster (At AAPM) which mentioned
 D and this year I had a MICCAI workshop paper
 (http://www.cse.buffalo.edu/hpmiccai/program.html, see Towards Real-Time
 Radiation Therapy: GPU Accelerated Superposition/Convolution) in addition to
 some posters (at AAPM and ASTRO).

Hey! You gotta announce these things!
 I wouldn't be surprised if there are
 others that have used D in their research and have cited it.

Oh yeh. Good point -- like me for instance. :-) I guess I should follow my own advice. My D-using research paper: http://doi.acm.org/10.1145/1377980.1377993 I was kinda waiting to say anything until the paper describing the main project was published. The NPAR paper above one was just a little offshoot of that. I'll be presenting the main thing as a poster at Pacific Graphics '08 next month, but posters don't count as "Publications" in the world of computer graphics. --bb
Sep 15 2008
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 15 Sep 2008 17:08:58 -0400, Bill Baxter <wbaxter gmail.com> wrote:

 Hey!  You gotta announce these things!

Here's the post from a year ago: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=9466.
Sep 15 2008
prev sibling next sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Tue, Sep 16, 2008 at 10:06 AM, Robert Jacques <sandford jhu.edu> wrote:
 On Mon, 15 Sep 2008 17:08:58 -0400, Bill Baxter <wbaxter gmail.com> wrote:

 Hey!  You gotta announce these things!

Here's the post from a year ago: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D.announce&article_id=9466.

Oh, I see. I was on the road then. Must be why I missed it. Sorry for the undue harassment. --bb
Sep 15 2008
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 15 Sep 2008 20:33:58 -0400, bearophile <bearophileHUGS lycos.com>  
wrote:
 How have you used D with CUDA? I'd like to know a bit more technical  
 details.

Let's see. There's a couple of parts. 1) Created stub omf files to load the DLL correctly (CUDA doesn't support dynamic linking yet). The main issue here was there was a mangling change between what D expected and what NVIDIA provided. 2) Converted the CUDA device header over to D (done with htod with some manual clean up) 3) Made use of a template and mixin combo to simplify declaring all the methods of the CUDA types: i.e. float3, etc. I should refactor this to a template and aliases. 4) Made a high level api to simplify using CUDA. (Heavy use of templates again to type check, etc. everything). Here's an example: Device gpu = Device(); // Find the first CUDA compatible device writefln(gpu); // Print out its slot and type auto kernel = new Module("kernel.cubin"); // Load a compiled CUDA module from a file float[] data = ...; // Load some data auto image = new Texture!(float)(kernel,"image",640,480,data); // Place it into a texture auto ouput = new cu1D!(float)(640*480); // Allocate an output array auto func = new Kernel!(float*)(kernel,"func",image); // Get the function you want func[[40,30],[16,16]](output); // Launch the function gpu.wait; // Wait for the GPU to finish write_output(output.dup); // Get the results I still write all the kernels in C and compile with nvcc though. Recently, PTX (aka CUDA assembly) support came to the driver, so writing D code that generates CUDA directly is theoretically possible.
 And do you know about BSGP (that I think is a step toward the future of  
 such things)?
 http://www.kunzhou.net/

I hadn't heard about BSGP, so thanks. The general concept of BSGP has been around for a few years now, Microsoft's Accelerator (research.microsoft.com/act/) comes to mind (And apparently Microsoft is the licensor for BSGP too), though the implementation looks more modern (at first glance).
Sep 15 2008