On Nov 29, 2007 4:31 AM, Luke Palmer wrote:

On Nov 29, 2007 4:02 AM, Chris Smith wrote:

...

I was talking to a few people about this on #haskell, and it was suggested I ask here. I should say that I'm playing around here; don't mistake this for an urgent request or a serious problem.

Suppose I wanted to implement automatic differentiation of simple functions on real numbers; then I'd take the operations from Num, Fractional, and Floating, and define how to perform them on pairs of values and their differentials, and then I'd write a differentiate function... but finding an appropriate type for that function seems to be a challenge.

Oh, I think I totally missed the point. I missed the word "simple". I think the problem is that a function of type Num a => a -> a can be any function whatsoever, it does not have to be a simple combination of operators (it could, for example, use show, do a string transformation, and then read the result). So while you can do your AD type, I think a function which differentiates (Num a => a -> a) is not possible using this approach. You must resort to numerical methods... Luke

...

We have:

1. Differentiating a function of the most general type (Num a => a -> a) should produce a result of type (Num a => a -> a).

I don't see why this should be true. Int -> Int is an instance of this type, but derivatives require limits, which integers don't have. Do you intend to output the difference sequence of the function in this case?

But then Double -> Double is also an instance of this type. Do you intend to approximate the real derivative when it's specialized to this?

Instead of worrying about the types, first tell us what semantics you want.

Luke

Luke Palmer wrote:

I don't see why this should be true. Int -> Int is an instance of this type, but derivatives require limits, which integers don't have. Do you intend to output the difference sequence of the function in this case?

But then Double -> Double is also an instance of this type. Do you intend to approximate the real derivative when it's specialized to this?

Instead of worrying about the types, first tell us what semantics you want.

I intend to naively treat each function as being from the reals to the reals, and then take advantage of the fact (which is proven by the type system in the code I posted) that when the derivative is evaluated at integer inputs for functions defined using only ring operations, the result is an integer (and similarly for rationals and field operations). Note that the functions here are defined over real numbers rather than *merely* intervals, because the type given for diffNum, for example, requires that the first parameter be no more specific than Num a => a -> a... so one may not actually pass in a function of type Int -> Int and expect the code to compile. -- Chris Smith

Dan Piponi wrote:

I must be missing the point of something. What's wrong with

...

diff f x = let AD y dy = f (AD x 1) in dy

?

In ghci we get

*Main> :t diff (\x -> 2*x) (2::Int) diff (\x -> 2*x) (2::Int) :: Int *Main> :t diff (\x -> 2*x) (2::Float) diff (\x -> 2*x) (2::Float) :: Float

I've used almost exactly that line of code myself a few times.

Yep, that does what I want. Thank you (and Stefan, and ghci's :t) for pointing it out. If this were a practical thing, I'd certainly decide that's the best option and move on. But since this is me trying to figure out the Right Answer (tm), that still doesn't look like it. (Though I suspect if there were a Right Answer, it would have been pointed out by now.)

From my perspective, what's wrong with it what Stefan mentioned when he suggested it: it breaks abstraction. Even if I don't expose the type AD (i.e., it's an implementation detail and the user of a library shouldn't care that it even exists), the inferred type signature for diff depends on it.

Prelude AD> :t diff diff :: forall a t. (Num a) => (AD.AD a -> AD.AD t) -> a -> t But what's AD? If it's exported, then at least it will show up in Haddock with a list of its instances, so the type is merely misleading. but if it's not exported, then the type is just plain not useful. So I want the parameter to be more restricted. No one is going to write a function that *only* works on AD types. Instead, the parameter to diff ought to be required to be polymorphic. The rank n type does that, but it loses the ability to get the most general possible result type. -- Chris Smith

Hi Dan, thanks for answering. Dan Piponi wrote:

When you specify that a function has type a -> b, you're entering into a bargain. You're saying that whatever object of type a you pass in, you'll get a type b object back. "a -> b" is a statement of that contract.

Sure, that much makes perfect sense, and we agree on it.

Now your automatic differentiation code can't differentiate any old function. It can only differentiate functions built out of the finite set of primitives you've implemented (and other "polymorphic enough" functions).

Sure. To be more specific, here's the contract I would really like. 1. You need to pass in a polymorphic function a -> a, where a is, at *most*, restricted to being an instance of Floating. This part I can already express via rank-N types. For example, the diffFloating function in my original post enforces this part of the contract. 2. I can give you back the derivative, of any type b -> b, so long as b is an instance of Num, and b can be generalized to the type a from condition 1. It's that last part that I can't seem to express, without introducing this meaningless type called AD. There need be no type called AD involved in this contract at all. Indeed, the only role that AD plays in this whole exercise is to be an artifact of the implementation I've chosen. I could change my implementation; I could use Jerzy's implementation with a lazy infinite list of nth-order derivatives... or perhaps I could implement all the operations of Floating and its superclasses as data constructors, get back an expression tree, and launch Mathematica via unsafePerformIO to calculate its derivative symbolically, and then return a function that interprets the result. And who knows what other implementations I can come up with? In other words, the type AD is not actually related to the task at hand. [...]

Luckily, there's a nice way to express this. We can just say diff :: (AD a -> AD a) -> a -> a. So AD needs to be exported. It's an essential part of the language for expressing your bargain, and I think it *is* the Right Answer, and an elegant and compact way to express a difficult contract.

Really? If you really mean you think it's the right answer, then I'll have to back up and try to understand how. It seems pretty clear to me that it breaks abstraction in a way that is really rather dangerous. If you mean you think it's good enough, then yes, I pretty much have conluded it's at least the best that's going to happen; I'm just not entirely comfortable with it. -- Chris Smith

I must be missing something, because to me the contract seems to be much simpler to express (than the Functor + Isomorphism route you seem to me to be heading towards): diff :: (Eq x, Dense x, Subtractible x, Subtractible y, Divisible y x yOverX) => (x -> y) -> x -> yOverX class Dense a where addEpsilon :: a -> a class Subtractible a where takeAway :: a -> a -> a class Divisible a b c | a b -> c where divide :: a -> b -> c Then diff is just: diff f a = if dx == dx' then error "Zero denom" else dydx where a' = addEpsilon a dx = a' `takeAway` a dx' = a `takeAway` a' dy = f a' `takeAway` f a dydx = dy `divide` dx With the instances: instance Dense Double where addEpsilon x = x * 1.0000001 + 1.0e-10 instance Dense Int where addEpsilon x = x + 1 instance Subtractible Double where takeAway x y = x - y instance Subtractible Int where takeAway x y = x - y instance Divisible Double Double Double where divide x y = x / y instance Divisible Int Int Int where divide x y = x `div` y and throwing in {-# OPTIONS_GHC -fglasgow-exts #-}, I get: *Diff> diff sin (0.0::Double) 1.0 *Diff> diff (\x -> x*7+5) (4::Int) 7 Dan Weston Chris Smith wrote:

Hi Dan, thanks for answering.

Dan Piponi wrote:

...

When you specify that a function has type a -> b, you're entering into a bargain. You're saying that whatever object of type a you pass in, you'll get a type b object back. "a -> b" is a statement of that contract.

Sure, that much makes perfect sense, and we agree on it.

...

Now your automatic differentiation code can't differentiate any old function. It can only differentiate functions built out of the finite set of primitives you've implemented (and other "polymorphic enough" functions).

Sure. To be more specific, here's the contract I would really like.

1. You need to pass in a polymorphic function a -> a, where a is, at *most*, restricted to being an instance of Floating. This part I can already express via rank-N types. For example, the diffFloating function in my original post enforces this part of the contract.

2. I can give you back the derivative, of any type b -> b, so long as b is an instance of Num, and b can be generalized to the type a from condition 1. It's that last part that I can't seem to express, without introducing this meaningless type called AD.

There need be no type called AD involved in this contract at all. Indeed, the only role that AD plays in this whole exercise is to be an artifact of the implementation I've chosen. I could change my implementation; I could use Jerzy's implementation with a lazy infinite list of nth-order derivatives... or perhaps I could implement all the operations of Floating and its superclasses as data constructors, get back an expression tree, and launch Mathematica via unsafePerformIO to calculate its derivative symbolically, and then return a function that interprets the result. And who knows what other implementations I can come up with? In other words, the type AD is not actually related to the task at hand.

[...]

...

Luckily, there's a nice way to express this. We can just say diff :: (AD a -> AD a) -> a -> a. So AD needs to be exported. It's an essential part of the language for expressing your bargain, and I think it *is* the Right Answer, and an elegant and compact way to express a difficult contract.

Really? If you really mean you think it's the right answer, then I'll have to back up and try to understand how. It seems pretty clear to me that it breaks abstraction in a way that is really rather dangerous.

If you mean you think it's good enough, then yes, I pretty much have conluded it's at least the best that's going to happen; I'm just not entirely comfortable with it.

On 30 Nov 2007, cdsmith@twu.net wrote:

Sure. To be more specific, here's the contract I would really like.

1. You need to pass in a polymorphic function a -> a, where a is, at *most*, restricted to being an instance of Floating. This part I can already express via rank-N types. For example, the diffFloating function in my original post enforces this part of the contract.

It seems to me that you need the type system to ensure that the function is differentiable. For this, you have to export the type (though not the constructor as long as you don't want users to be able to extend it). Am I missing something? Jed