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 reply "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
next sibling parent reply "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
parent reply "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
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 reply 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
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
prev 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
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 reply "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
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).


 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


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