天天看點
傳回

Y 組合子詳解 （The Y Combinator）

Y 組合子詳解 （The Y Combinator）

如何實作一個匿名遞歸函數？

Is there any way to make an anonymous function call itself?

不動點 

f(g)=g

這個 g 就是 f 的不動點(Fixed Point)。

A fixed point of a function g ， is a value that is mapped to itself by the function f.

什麼是 Y 組合子

Y 組合子詳解 （The Y Combinator）

Y 組合子（The Y combinator） , discovered by ​​Haskell B. Curry​​, is defined as:

λf. (λx. f (x x))(λx. f (x x))

用于計算（高階）函數的不動點，使得lambda演算可以定義匿名遞歸函數。

Let’s see that in action:

X = (λx. f (x x))(λx. f (x x))
X = f (x x) [x := λx. f (x x)]
X = f ((λx. f (x x)) (λx. f (x x)))
X = f X

In ​​functional programming​​​, the Y combinator can be used to formally define ​​recursive functions​​ in a programming language that does not support recursion.

It turns out that for any λ-expression f,

(λx. f (x x))(λx. f (x x))

is a fixed-point of f.

lambda 演算

所謂lambda演算是一種計算模型，在這種計算模型中，一切都是函數，連數值都可以沒有（用函數表示）。它具有和圖靈機等價的計算能力，但是和圖靈機偏硬體的描述方式不同，lambda演算（基本上）隻依賴兩條數學推理規則。

雖然lambda演算中一切都是函數，但都可以不需要函數名。沒有函數名的函數稱為「匿名函數」。

比如平方函數 sqr (x) = x * x ，在lambda演算中寫成：

lambda x . x * x

表明對參數 x 執行自己乘以自己的操作。任何用到 sqr (x) 的地方，直接用這個lambda式子替換就可以。

α-equivalent：identity function

λx. x is known as the identity function

That is, it takes in some input x, and outputs the same x.

You might ask, “Isn’t λy. y also the identity function?” Indeed it is! λx. x and λy. y are α-equivalent (alpha-equivalent). In fact, all of the following are α-equivalent:

λx. x
λy. y
λz. z
λ☃. ☃

constant function

And what about

λx. y

constant function! it ignores the input x and returns y no matter what.

Bound vs. free variables

For example：

x is a bound variable in λx.x

but x is a free variable in (λy. y) x.

β-reduction：function application 

(λx. x) y

上面的表達式：以 ​

​y​

​​ 為入參調用函數 ​

​λx. x​

​ , 得到的結果就是 y。

The rules of β-reduction say that a term

(λx. t) s

can be reduced to

t [x := s]

Line by line, it looks like this:

(λx. x) s
x [x := s]
s

For example, take a look at the following term:

λy.(λx. x) y

… and feed it two inputs, a and b:

(λy.(λx. x) y) a b
((λx. x) y) [y := a]) b
(λx. x) a b
(x [x := a]) b
a b

Now take a look at the following λ-term:

(λx. x x)(λx. x x)

What happens when you apply β-reduction to it?

(λx. x x)(λx. x x)
(x x) [x := (λx. x x)]
(λx. x x)(λx. x x)

從計算階乘說起

數學中的階乘計算如下：

factorial 0 = 1
  factorial 1 = 1 * 1
  factorial 2 = 2 * 1 = 2
  factorial 3 = 3 * 2 * 1 = 6
  factorial 4 = 4 * 3 * 2 * 1 = 24

公式化的定義就是：

factorial(0) = 1
factorial(n) = n*factorial(n-1) (n>0)

用 Lisp 實作代碼如下：

(defun factorial (n)
      (if (= 0 n) 1
       (* n (factorial (- n 1))))
   )

(factorial 4)
24

這個函數在内部遞歸調用了自身，調用自身需要函數本體的名字，這個函數叫 factorial 。

從上面的例子可以看出，遞歸函數的一個關鍵點就在于調用自身，而調用自身必須要知自身的函數名，這樣才能通過作用域鍊通路到函數對自己的聲明和定義。

BUT, λ-calculus does not allow this kind of self-reference, at least not directly.

匿名遞歸函數

函數在内部遞歸調用了自身，這就叫遞歸。

至今為止，我們提到的函數，都是有名字的。

回到一開始提出的問題：如何實作一個匿名遞歸函數？

但是當需要定義的函數含有遞歸時，比如階乘 factorial，我們習慣的方式是 (Kotlin 語言)：

package com.light.sword.ycombinator

fun factorial(n: Int): Int {
    return when (n) {
        0 -> 1
        else -> n * factorial(n - 1)
    }
}

fun main() {
    val a = factorial(4)
    println(a) // 24
}

上面的階乘函數 factorial 直接寫成lambda演算則是

factorial (x) = lambda x. (x == 0) ? 1 : 
                                     x * factorial (x - 1)

這時候函數的定義部分引用了函數自身，但是，沒有函數名意味着用無法直接引用函數自身。怎麼辦呢？

The Y combinator：終結

她又來了：

λf. (λx.f (x x))(λx.f(x x))

希望你現在看她覺得熟悉了。

現在讓我們回到階乘函數 factorial . 如果函數可以引用自身，那麼遞歸就很簡單：

f := λx.(if x == 0 then 1 else x * f (x–1))

但是，我們知道 λ 演算中不許這麼做。

那我們換個角度思考一下吧。

我們來定義一個高階函數 F ， 入參是函數 f :

F := λf. λx.(if x == 0 then 1 else x * f (x–1))

然後，我們想求解 F 的不動點：

F(f) = f

這樣我們就可以使用 F(f) 進行“間接自引用” 來實作遞歸。

我們已經知道，對任意 λ-expression f

(λx. f (x x))(λx. f (x x))

is a fixed-point of f.

Let’s see that in action again:

X = (λx.f (x x))(λx.f (x x))

X = f (x x) [x := λx. f (x x)]

X = f ((λx. f (x x)) (λx. f *(x x)))

X = f X

As you can see, for any arbitrary function f, the input X remains unchanged.

Given this, we can build a function that returns a fixed-point for any function f by taking the function in as an argument:

λf. (λx.f (x x))(λx.f (x x))

And that right there is the Y combinator.

各大程式設計語言實作 Y combinator 函數

程式設計語言的另一個重要分界線是靜态類型和動态類型。

靜态類型語言是在編譯時确定所有表達式類型的語言，任何類型錯誤都會導緻編譯失敗。

動态類型語言直到運作時才進行任何類型檢查，并且如果将函數應用于無效類型的參數（*例如，*通過嘗試将整數和字元串相加，然後報告錯誤。

在常用的程式設計語言中，C，C ++和Java是靜态類型的，Perl，Python和Ruby是動态類型的。Scheme（我們将用于示例的語言）也是動态類型的。（也有跨越靜态類型和動态類型之間邊界的語言）

人們經常聽到靜态類型，稱為強類型和動态類型，稱為弱類型，但這是濫用術語。強類型隻是意味着語言中的每個值都隻有一種類型，而弱類型意味着某些值可以有多種類型。是以，動态類型的Scheme也是強類型的，而靜态類型的C是弱類型的（因為您可以将指向一種對象的指針轉換為指向另一種類型的對象而不改變指針的值） 。

事實證明，在動态類型語言中定義Y組合器要簡單得多。可以用許多靜态類型語言定義Y組合子，但是這樣的定義通常需要一些hackery，因為Y組合子本身沒有簡單的靜态類型。

Common Lisp

實作 Y 組合子：

(defun Y (f)
  ((lambda (g) (funcall g g))
   (lambda (g)
     (funcall f (lambda (&rest a)
      (apply (funcall g g) a))))))

用 Y 組合子實作階乘與斐波那契數列：

(defun fac (n)
  (funcall
   (Y (lambda (f)
       (lambda (n)
         (if (zerop n)
     1
     (* n (funcall f (1- n)))))))
   n))
 
(defun fib (n)
  (funcall
   (Y (lambda (f)
       (lambda (n a b)
         (if (< n 1)
           a
           (funcall f (1- n) b (+ a b))))))
   n 0 1))
 
(mapcar #'fac '(1 2 3 4 5 6 7 8 9 10))
(1 2 6 24 120 720 5040 40320 362880 3628800))
 
(mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))
(1 1 2 3 5 8 13 21 34 55)

C

C doesn’t have first class functions, so we demote everything to second class to match.

#include <stdio.h>
#include <stdlib.h>

/* func: our one and only data type; it holds either a pointer to
   a function call, or an integer.  Also carry a func pointer to
   a potential parameter, to simulate closure                   */
typedef struct func_t func;
typedef struct func_t {
        func (fn) (func, func);
        func _;
        int num;
} func_t;

func new(func(f)(func, func), func ) {
        func x = malloc(sizeof(func_t));
        x->fn = f;
        x-> = _;       /* closure, sort of */
        x->num = 0;
        return x;
}

func call(func f, func n) {
        return f->fn(f, n);
}

func Y(func(*f)(func, func)) {
        func g = new(f, 0);
        g->_ = g;
        return g;
}

func num(int n) {
        func x = new(0, 0);
        x->num = n;
        return x;
}

func fac(func self, func n) {
        int nn = n->num;
        return nn > 1   ? num(nn * call(self->_, num(nn - 1))->num)
                        : num(1);
}

func fib(func self, func n) {
        int nn = n->num;
        return nn > 1
                ? num(  call(self->, num(nn - 1))->num +
                        call(self->, num(nn - 2))->num )
                : num(1);
}

void show(func n) { printf(" %d", n->num); }

int main() {
        int i;
        func f = Y(fac);
        printf("fac: ");
        for (i = 1; i < 10; i++)
                show( call(f, num(i)) );
        printf("\n");

        f = Y(fib);
        printf("fib: ");
        for (i = 1; i < 10; i++)
                show( call(f, num(i)) );
        printf("\n");
     
        return 0;

}

Output:

fac: 1 2 6 24 120 720 5040 40320 362880

fib: 1 2 3 5 8 13 21 34 55

JavaScript 

var Y = f => (x => x(x))(y => f(x => y(y)(x)));
var fac = Y(f => n => n > 1 ? n * f(n-1) : 1);

fac(10)
3628800

Kotlin 

package com.light.sword.ycombinator

/**
 * FP: Y Combinator
 *
 * lambda f. (lambda x. (f(x x)) lambda x. (f(x x)))
 * Created by jack on 2017/7/9.
 */

typealias G<T, R> = (T) -> R

interface F<T, R> : Function1<F<T, R>, G<T, R>>

fun <T, R> f(block: (F<T, R>) -> G<T, R>) = object : F<T, R> {
    // 調用函數自身
    override fun invoke(g: F<T, R>) = block(g)
}

typealias E<T, R> = Function1<G<T, R>, G<T, R>>

/**
 * Y 組合子函數
 * @param e :E 入參，是一個函數類型 Function1<G<T, R>, G<T, R>>
 */
fun <T, R> Y(e: E<T, R>) = ({ g: F<T, R> -> g(g) })(f { g ->
    e { x -> g(g)(x) }
})

/**
 * 用 Y 組合子實作 factorial 階乘函數
 */
val factorial: (Int) -> Int = Y { f ->
    { x ->
        if (x == 0) 1 else x * f(x - 1)
    }
}

/**
 * 用 Y 組合子實作 fibonacci 數列函數 fib: (T)->R
 * Y(fib) = fib
 * 可以推斷： Y(Y(fib)) = Y(fib) = fib
 */
val fib: (Int) -> Int = Y { f ->
    { x ->
        if (x == 1 || x == 2) 1 else f(x - 1) + f(x - 2)
    }
}

fun main() {
    println(fib(10)) // 55
    println(factorial(10)) // 3628800
}

參考資料

The Y Combinator (no, not that one) A crash-course on lambda calculus：

​​https://medium.com/@ayanonagon/the-y-combinator-no-not-that-one-7268d8d9c46​​

The Y Combinator (Slight Return)：

​​https://mvanier.livejournal.com/2897.html​​

Y combinator:

y combinator fp 靜态類 動态類型 遞歸函數
上一篇: Netty——ByteBuf
下一篇: java3d貼圖_java3d 貼圖隻有顔色，沒有紋理

繼續閱讀