Derivative of a program

Let us assume you can represent a program as mathematical function, that's possible. How does the program representation of the first derivative of that function look like? Is there a way to transform a program to its "derivative" form, and does this make开发者_运维知识库 sense at all?

Yes it does make sense, it's known as Automatic Differentiation. There are one or two experimental compilers which can do this, for example NAGware's Differentiation Enabled Fortran Compiler Technology. And there are a lot of research papers on the topic. I suggest you get Googling.

First, it only makes sense to try to get the derivative of a pure function (one that does not affect external state and returns the exact same output for every input). Second, the type system of many programming languages involves a lot of step functions (e.g. integers), meaning you'd have to get your program to work in terms of continuous functions in order to get a valid first derivative. Third, getting the derivative of any function involves breaking it down and manipulating it symbolically. Thus, you can't get the derivative of a function without knowing how what operations it is made of. This could be achieved with reflection.

You could create a derivative approximation function if your programming language supports closures (that is, nested functions and the ability to put functions into variables and return them). Here is a JavaScript example taken from http://en.wikipedia.org/wiki/Closure_%28computer_science%29 :

function derivative(f, dx) {
    return function(x) {
        return (f(x + dx) - f(x)) / dx;
    };
}

Thus, you could say:

function f(x) { return x*x; }
f_prime = derivative(f, 0.0001);

Here, f_prime will approximate function(x) {return 2*x;}

If a programming language implemented higher-order functions and enough algebra, one could implement a real derivative function in it. That would be really cool.

See Lambda the Ultimate discussions on Derivatives and dissections of data types and Derivatives of Regular Expressions

How do you define the mathematical function of a program?

A derivative represent the rate of change of a function. If your function isn't continuous its derivative will be undefined over most of the domain.

I'm just gonna say that this doesn't make a lot of sense, as a program is much more abstract and "ruleless" than a mathematical function. As a derivative is a measure of the change in output as the input changes, there are certainly some programs where this could apply. However, you'd need to be able to quantify your input/output both in numerical terms.

Since input/output would both numerical, it's reasonable to assume that your program represents or operates similarly to a mathematical function, or series of functions. Hence, you can easily represent a derivative, but it would be no different than converting the mathematical derivative of a function to a computer program.

If the program is denoted as a distribution (Schwartz) then you have some notion of derivative assuming that tests functions models your postcondition (you can still take the limit to get a characteristic function). For instance, the assignment x:=x+1 is associated to the Dirac distribution \delta_{x_0+1} where x_0 is the initial value of the variable x. However, I have no idea what is the computational meaning of \delta_{x_0+1}'.

I am wondering, what if the program your're trying to "derive" uses some form of heursitics ? How can it be derived then ?

Half-jokingly, we all know that all real programs use at least a rand().