#include 
#include 

typedef int (*func_t)(int, int) ;

int add (int x, int y) { 
    return (x + y);
}

int foo (int x, int y) {
    return ((x + 1) * y);
}

int apply_2_3 (func_t func) {
    return (*func)(2, 3);
}

int main () {
    func_t func0 = add;
    func_t func1 = foo;

    printf("(%d %d)\n", apply_2_3(func0), apply_2_3(func1));
    return 0;
}

では、関数の値というからには、関数を簡単化していくのでしょうか？ でも、関数の等価な変換と言うのは難しいものです。 もともと、関数とは引数とその返り値の写像の事です。 つまり、ある関数と別の関数が等価であるかどうかは写像として同じもので あるかどうかであるはずです。 例えば、 f(x) = x + x, g(x) = 2 * x の f, g は関数として等価なはずです。 このように、関数の場合、等価な関数の表現は様々です。

関数の等価性を判断するために、写像としての同一性をみようとして 全ての引数とその結果を出して比較しようとしたとしましょう。 しかしながら、引数の範囲が有限であればそれぞれの値を求めて比較することで対応できますが、 無限であるならば機械的に処理することは出来ません。 加えて、関数がある引数に対して停止しない場合はどうなるでしょう。 つまり、ある引数に対して入力を与えては見たけれど、f, g もしばらく返って来ない。 でも、しばらく返って来ないからと言って、未来永劫返って来ないともいえません。 つまり、プログラムの停止性も考える必要があるわけです。

では、いくつかルールを準備して式変換を行う場合を考えましょう。 たとえば、前述のように f と g は等価であるという rule を準備することは可能でしょう。しかしながら事はそう単純ではありません。

    h(x) = (if (< x 0) (- x (abs x)) (* x 2))   

実は、このように一般の関数(すなわちアルゴリズム)について、 その等価性を求めるアルゴリズムは存在しません(決定不能:undecidable である)。 というわけで、 関数の等価性を返す関数もありません。 Scheme の eq?, eqv, equal を関数に対して適用した場合、 ある同じ場所で定義されたものについて #t を返すことはあっても、 等価な関数全てに対して #t を返してくれるわけではありません。