www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Challenge: Automatic differentiation in D

reply Bill Baxter <wbaxter gmail.com> writes:
If I had the time I'd love to play around with automatic differentiation in D.
http://en.wikipedia.org/wiki/Automatic_differentiation

I played around with it a bit in C++ before, using the operator
overloading approach, but didn't go much beyond basic polynomials with
it.
The page above offers something of a challenge for a potential D implementation:
"""
Operator overloading for forward accumulation is easy to implement,
and also possible for reverse accumulation. However, current compilers
lag behind in optimizing the code when compared to forward
accumulation.
"""

I wonder if the fancy compile-time machinery offered by D could enable
a more efficient implementation?

Ultimately I'd be interested in using AD for implementing physics-y
things where complicated derivatives end up being necessary all the
time.
Here's a paper where they made use of a simple AD implementation for
doing thin shell simulations:
http://www.cs.columbia.edu/cg/pdfs/10_ds.pdf
You can also find their C++ AD code on the caltech site somewhere.

Just throwing this out there, because occasionally there are folks
looking for little self-contained projects to undertake.  And because
I think AD is nifty.

--bb
May 12 2009
next sibling parent reply Steve Teale <steve.teale britseyeview.com> writes:
Bill Baxter Wrote:


 If I had the time I'd love to play around with automatic differentiation in D.
 http://en.wikipedia.org/wiki/Automatic_differentiation
 
 I played around with it a bit in C++ before, using the operator
 overloading approach, but didn't go much beyond basic polynomials with
 it.
 The page above offers something of a challenge for a potential D
implementation:
 """
 Operator overloading for forward accumulation is easy to implement,
 and also possible for reverse accumulation. However, current compilers
 lag behind in optimizing the code when compared to forward
 accumulation.
 """
 
 I wonder if the fancy compile-time machinery offered by D could enable
 a more efficient implementation?
 
 Ultimately I'd be interested in using AD for implementing physics-y
 things where complicated derivatives end up being necessary all the
 time.
 Here's a paper where they made use of a simple AD implementation for
 doing thin shell simulations:
 http://www.cs.columbia.edu/cg/pdfs/10_ds.pdf
 You can also find their C++ AD code on the caltech site somewhere.
 
 Just throwing this out there, because occasionally there are folks
 looking for little self-contained projects to undertake.  And because
 I think AD is nifty.
 
 --bb


Bill,

D4 maybe. In the present mood I think you are spitting in the wind!

Steve
May 12 2009
parent reply Bill Baxter <wbaxter gmail.com> writes:
On Tue, May 12, 2009 at 10:48 AM, Steve Teale
<steve.teale britseyeview.com> wrote:

 Bill Baxter Wrote:


 If I had the time I'd love to play around with automatic differentiation=




 in D.

 http://en.wikipedia.org/wiki/Automatic_differentiation

 I played around with it a bit in C++ before, using the operator
 overloading approach, but didn't go much beyond basic polynomials with
 it.
 The page above offers something of a challenge for a potential D impleme=




ntation:

 """
 Operator overloading for forward accumulation is easy to implement,
 and also possible for reverse accumulation. However, current compilers
 lag behind in optimizing the code when compared to forward
 accumulation.
 """

[...]
 Just throwing this out there, because occasionally there are folks
 looking for little self-contained projects to undertake. =A0And because
 I think AD is nifty.

 --bb


 Bill,

 D4 maybe. In the present mood I think you are spitting in the wind!


I'm just proposing it as a fun project if anyone is interested.
Shouldn't require any compiler changes.  Unless roadblocks are found
that require some compiler changes, in which case it's better to know
about those now than later on.   I see AD as a category of interesting
numerical techniques that a sufficiently advanced compiler can make
much less painful to use.  Like expression templates.  I think D2 has
most of what would be needed already.  The basic idea of AD (forward
AD, anyway) is pretty simple and quite elegant IMO, and worth learning
about anyway, for anyone interested in numerical computing,
computational physics, etc.

--bb
May 12 2009
parent reply Steve Teale <steve.teale britseyeview.com> writes:
Bill Baxter Wrote:


 Bill,

 D4 maybe. In the present mood I think you are spitting in the wind!


 
 I'm just proposing it as a fun project if anyone is interested.
 Shouldn't require any compiler changes.  Unless roadblocks are found
 that require some compiler changes, in which case it's better to know
 about those now than later on.   I see AD as a category of interesting
 numerical techniques that a sufficiently advanced compiler can make
 much less painful to use.  Like expression templates.  I think D2 has
 most of what would be needed already.  The basic idea of AD (forward
 AD, anyway) is pretty simple and quite elegant IMO, and worth learning
 about anyway, for anyone interested in numerical computing,
 computational physics, etc.
 
 --bb


Bill,

Has there been a discussion about expression templates - I have never been able
to understand why they only apply to declarations. That sounds interesting.

Steve
May 12 2009
parent Bill Baxter <wbaxter gmail.com> writes:
I actually was reminded about AD by someone's recent post on a SciPy
discussion list.
Here's another interesting link that appeared there questioning why AD
doesn't get more use in the machine learning community:
http://justindomke.wordpress.com/2009/02/17/automatic-differentiation-the-m=
ost-criminally-underused-tool-in-the-potential-machine-learning-toolbox/

And a followup posted by the same guy explaining the basics of reverse-mode=
 AD:
http://justindomke.wordpress.com/2009/03/24/a-simple-explanation-of-reverse=
-mode-automatic-differentiation/

--bb

On Tue, May 12, 2009 at 11:31 AM, Steve Teale
<steve.teale britseyeview.com> wrote:

 Bill Baxter Wrote:


 Bill,

 D4 maybe. In the present mood I think you are spitting in the wind!


 I'm just proposing it as a fun project if anyone is interested.
 Shouldn't require any compiler changes. =A0Unless roadblocks are found
 that require some compiler changes, in which case it's better to know
 about those now than later on. =A0 I see AD as a category of interesting
 numerical techniques that a sufficiently advanced compiler can make
 much less painful to use. =A0Like expression templates. =A0I think D2 ha=




s

 most of what would be needed already. =A0The basic idea of AD (forward
 AD, anyway) is pretty simple and quite elegant IMO, and worth learning
 about anyway, for anyone interested in numerical computing,
 computational physics, etc.

 --bb


 Bill,

 Has there been a discussion about expression templates - I have never bee=


n able to understand why they only apply to declarations. That sounds inter=
esting.

 Steve
May 12 2009
prev sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
Bill Baxter wrote:

 If I had the time I'd love to play around with automatic differentiation in D.
 http://en.wikipedia.org/wiki/Automatic_differentiation
 
 I played around with it a bit in C++ before, using the operator
 overloading approach, but didn't go much beyond basic polynomials with
 it.
 The page above offers something of a challenge for a potential D
implementation:
 """
 Operator overloading for forward accumulation is easy to implement,
 and also possible for reverse accumulation. However, current compilers
 lag behind in optimizing the code when compared to forward
 accumulation.
 """
 
 I wonder if the fancy compile-time machinery offered by D could enable
 a more efficient implementation?
 
 Ultimately I'd be interested in using AD for implementing physics-y
 things where complicated derivatives end up being necessary all the
 time.
 Here's a paper where they made use of a simple AD implementation for
 doing thin shell simulations:
 http://www.cs.columbia.edu/cg/pdfs/10_ds.pdf
 You can also find their C++ AD code on the caltech site somewhere.
 
 Just throwing this out there, because occasionally there are folks
 looking for little self-contained projects to undertake.  And because
 I think AD is nifty.
 
 --bb


I can't forsee any compiler issues if you use an interface like:

mixin(ctfeFunc("expression"));

That said, you'd need to do all the parsing, etc. in CTFE if you went 
that route. Without macros, though, the only other way would be abuse of 
operator overloading, which might prove to be more difficult anyway.
May 12 2009