Derivative Programs

Question

Suppose you can imagine a program as a mathematical function, which is possible. What is the representation of the first derivative of this function? Is there a way to convert a program to its "derivative" form, and does it make sense at all?

Answer 1

Firstly, it makes sense to try to get the derivative of a pure function (which does not affect the external state and returns an accurate result for each input). Secondly, the type system of many programming languages ​​includes many step functions (for example, integers), which means that you will need to make your program work in terms of continuous functions in order to get a real first derivative. Thirdly, the derivation of any function is associated with its destruction and its symbolic manipulation. Thus, you cannot get a derivative of a function without knowing what operations it was performed with. This can be achieved with reflection.

You can create a derived approximation function if your programming language supports closures (i.e. nested functions and the ability to put functions in variables and return them). Here is an example JavaScript 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; }; } 

So you can say:

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

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

If a programming language implemented functions of a higher order and sufficient algebra, one could implement a real derivative function in it. It would be great.

Answer 2

Yes, that makes sense, it is known as Automatic Differentiation . There are one or two experimental compilers that can do this, such as NAGware Dyniation Enabled Fortran Compiler Technology . And there are many scientific papers on this topic. I suggest you get googling.

Answer 3

See Lambda The Ultimate Discussion Derivatives and Showdowns of Data Types and Derivatives of Regular Expressions

Answer 4

How do you determine the mathematical function of a program?

The derivative is the rate of change of function. If your function is not continuous, its derivative will be undefined for most of the domain.

Answer 5

I will simply say that this does not make much sense, since the program is more abstract and "useless" than a mathematical function. Since a derivative is a measure of output changes as input changes, there are, of course, some programs in which this could be applied. However, you will need to quantify your input / output in numerical terms.

Since I / O would be numerical, it is reasonable to assume that your program represents or works in the same way as a mathematical function or series of functions. Therefore, you can easily imagine a derivative, but this is no different from converting a mathematical derivative of a function into a computer program.

Answer 6

If a program is referred to as a distribution (Schwartz), then you have a concept of derivative, which assumes that the test functions model your postcondition (you can still use the limit to get a characteristic function). For example, the assignment x:=x+1 is associated with the Dirac distribution \delta_{x_0+1} , where x_0 is the initial value of the variable x . However, I have no idea what the computational meaning of \delta_{x_0+1}' .

Answer 7

I am wondering what if the program you are trying to "output" uses some form of heursitics? How can it be obtained then?

As a joke, we all know that all real programs use at least rand ().