Sabit nokta birleştirici - Fixed-point combinator

Matematik ve de bilgisayar biliminin , genel olarak, bir sabit nokta bir fonksiyonu fonksiyonu ile kendi eşlenen bir değerdir.

Gelen kombinatoriyel mantık için bilgisayar biliminin , bir sabit noktalı combinator (veya fixpoint combinator ) a nın daha yüksek dereceden fonksiyonu bu döner argümanı fonksiyonunun bir sabit nokta, eğer varsa. ${\displaystyle {\textsf {düzeltme}}}$

Biçimsel olarak, f fonksiyonunun bir veya daha fazla sabit noktası varsa, o zaman

${\displaystyle {\textsf {düzeltme}}\ f=f\ ({\textsf {düzeltme}}\ f)\ ,}$

ve bu nedenle, tekrarlanan uygulama ile,

${\displaystyle {\textsf {düzeltme}}\ f=f\ (f\ (\ldots f\ ({\textsf {düzeltme}}\ f)\ldots ))\ .}$

Y birleştirici

Klasik tiplendirilmemiş lambda hesabında her fonksiyonun sabit bir noktası vardır.

Özel bir uygulama düzeltme olduğunu Curry'nin paradoksal combinator Y ile temsil,

${\displaystyle {\textsf {Y}}=\lambda f.\ (\lambda xf\ (x\ x))\ (\lambda xf\ (x\ x))\ .}$

Gelen fonksiyonel programlama , Y combinator resmen tanımlamak için kullanılabilir özyinelemeli fonksiyonlar özyinelemeye desteklemeyen bir programlama dilinde.

Bu birleştirici Curry'nin paradoksunun uygulanmasında kullanılabilir . Curry'nin paradoksunun kalbi, türlenmemiş lambda hesabının tümdengelimli bir sistem olarak sağlam olmamasıdır ve Y birleştiricisi, anonim bir ifadenin sıfırı, hatta birçok değeri temsil etmesine izin vererek bunu gösterir. Bu matematiksel mantıkta tutarsızdır.

Tek değişkenli bir işleve uygulanan Y birleştiricisi genellikle sonlanmaz. Y birleştiricisini iki veya daha fazla değişkenli fonksiyonlara uygulayarak daha ilginç sonuçlar elde edilir . İkinci değişken bir sayaç veya indeks olarak kullanılabilir. Ortaya çıkan işlev , zorunlu bir dilde bir süre veya bir for döngüsü gibi davranır .

Bu şekilde kullanıldığında Y birleştiricisi basit özyineleme uygular. Lambda hesabında, bir fonksiyon gövdesindeki bir fonksiyonun tanımına atıfta bulunmak mümkün değildir. Özyineleme yalnızca bir işlevi parametre olarak ileterek elde edilebilir. Y combinator programlama bu tarzı gösterir.

Sabit nokta birleştirici

Y, combinator lambda Diferensiyel bir sabit noktalı combinator bir uygulamasıdır. Sabit nokta birleştiriciler, diğer işlevsel ve zorunlu dillerde de kolayca tanımlanabilir. Lambda hesabındaki sınırlamalar nedeniyle lambda hesabındaki uygulama daha zordur. Sabit nokta birleştirici birkaç farklı alanda kullanılabilir:

• Genel matematik
• Türlenmemiş lambda hesabı
• Yazılan lambda hesabı
• Fonksiyonel programlama
• Zorunlu programlama

Sabit nokta birleştiriciler bir dizi farklı işleve uygulanabilir, ancak normalde fazladan bir parametre olmadıkça sonlandırılmaz. Sabitlenecek işlev parametresine başvurduğunda, işleve başka bir çağrı çağrılır, bu nedenle hesaplama hiçbir zaman başlamaz. Bunun yerine, hesaplamanın başlamasını tetiklemek için ekstra parametre kullanılır.

Sabit noktanın tipi, sabitlenen fonksiyonun dönüş tipidir. Bu bir gerçek veya bir işlev veya başka bir tür olabilir.

Türlenmemiş lambda hesabında, sabit nokta birleştiriciyi uygulama işlevi, Church kodlaması gibi bir kodlama kullanılarak ifade edilebilir . Bu durumda (işlevleri tanımlayan) belirli lambda terimleri değer olarak kabul edilir. Kodlamadaki sabit nokta birleştiricinin "çalışması" (beta indirgemesi), sonuç için daha sonra sabit nokta değeri olarak yorumlanabilecek bir lambda terimi verir.

Alternatif olarak, bir fonksiyon, tamamen lambda hesabında tanımlanan bir lambda terimi olarak düşünülebilir.

Bu farklı yaklaşımlar, bir matematikçinin ve bir programcının sabit nokta birleştiricisini nasıl görebileceğini etkiler. Bir lambda hesabı matematikçisi, bir fonksiyona uygulanan Y birleştiricisini sabit nokta denklemini karşılayan bir ifade ve dolayısıyla bir çözüm olarak görebilir.

Buna karşılık, bazı genel programlama görevlerine yalnızca sabit nokta birleştirici uygulamak isteyen bir kişi, bunu yalnızca özyinelemeyi uygulamanın bir aracı olarak görebilir.

Değerler ve etki alanları

Her ifadenin bir değeri vardır. Bu genel matematikte doğrudur ve lambda hesabında da doğru olmalıdır. Bu, lambda hesabında, bir fonksiyona sabit nokta birleştirici uygulamanın size değeri fonksiyonun sabit noktası olan bir ifade verdiği anlamına gelir.

Bununla birlikte, bu lambda hesabı alanındaki bir değerdir, fonksiyonun alanındaki herhangi bir değere karşılık gelmeyebilir, bu nedenle pratik anlamda mutlaka fonksiyonun sabit bir noktası değildir ve yalnızca lambda hesabı alanında denklemin sabit bir noktasıdır.

Örneğin, düşünün

${\displaystyle x^{2}=-1\Rightarrow x={\frac {-1}{x}}\Rightarrow f\ x={\frac {-1}{x}}\land {\textsf {Y }}\ f=x}$

Küme bir imza numaraları , yani Church kodlama uygulanabilir f bir lambda terimi ile temsil edilebilir. Bu denklemin reel sayılarda çözümü yoktur. Ama karmaşık sayıların alanında i ve -i çözümlerdir. Bu, başka bir alanda bir denklemin çözümlerinin olabileceğini gösterir. Ancak, yukarıdaki denklemin çözümü için kullanılan lambda terimi bundan daha tuhaftır. Lambda terimi , x'in bir değer olarak i veya -i olabileceği durumu temsil eder . Alan değişikliğinde bu iki değeri birbirinden ayıran bilgiler kaybolmuştur. ${\görüntüleme stili Y\ f}$

Lambda hesabı matematikçisi için bu, lambda hesabı tanımının bir sonucudur. Programcı için bu, lambda teriminin beta indirgemesinin sonsuza kadar döngüye gireceği ve asla normal bir forma ulaşmayacağı anlamına gelir.

İşleve karşı uygulama

Sabit nokta birleştirici matematikte tanımlanabilir ve daha sonra diğer dillerde uygulanabilir. Genel matematik, genişleme özelliklerine dayalı bir işlevi tanımlar . Yani, aynı eşlemeyi yapıyorlarsa iki işlev eşittir. Lambda hesabı ve programlama dilleri, işlev kimliğini kasıtlı bir özellik olarak görür . Bir işlevin kimliği, uygulanmasına dayanır.

Bir lambda hesabı işlevi (veya terimi), bir matematiksel işlevin bir uygulamasıdır. Lambda hesabında, sabit nokta birleştiricinin matematiksel tanımını karşılayan bir dizi birleştirici (uygulama) vardır.

"Birleştirici" nedir?

Kombinasyon mantığı , daha yüksek mertebeden bir fonksiyon teorisidir. Bir birleştirici , kapalı bir lambda ifadesidir, yani serbest değişkeni yoktur. Birleştiriciler, değerleri değişken olarak adlandırmadan ifadedeki doğru yerlerine yönlendirmek için birleştirilebilir.

Programlamada kullanım

Sabit nokta birleştiriciler , işlevlerin özyinelemeli tanımını uygulamak için kullanılabilir . Ancak, pratik programlamada nadiren kullanılırlar. Basit bir şekilde yazılan lambda hesabı gibi güçlü bir şekilde normalleştirici tip sistemler , sonlandırmaya izin vermez ve bu nedenle sabit nokta birleştiricilere genellikle bir tip atanamaz veya karmaşık tip sistem özellikleri gerektirir. Ayrıca, sabit nokta birleştiriciler, daha fazla işlev azaltma gerektirdiğinden ve her bir karşılıklı özyinelemeli tanım grubu için bir demet oluşturup ayırdıklarından, özyinelemeyi uygulamak için diğer stratejilere kıyasla genellikle verimsizdir.

faktör fonksiyonu

Faktör işlevi, sabit nokta birleştiricinin nasıl uygulanabileceğine iyi bir örnek sağlar. Sonuç, zorunlu bir dilde tek bir döngüde uygulanacağı gibi basit özyinelemeyi gösterir. Kullanılan sayıların tanımı Kilise kodlamasında açıklanmıştır .

Kendini parametre olarak alan fonksiyon

${\displaystyle F\ f\ n=(\operatöradı {IsZero} \ n)\ 1\ (\operatöradı {çarpma} \ n\ (f\ (\operatöradı {pred} \ n)))\ .}$

Bu YF n'yi şu şekilde verir:

${\displaystyle {\begin{aligned}{\textsf {düzeltme}}\ F\ n&=F\ ({\textsf {düzeltme}}\ F)\ n\\&=(\operatöradı {IsZero} \ n)\ 1\ (\operatöradı {çarpma} \ n\ (({\textsf {düzeltme}}\ F)\ (\operatöradı {pred} \ n)))\ .\son{hizalanmış}}}$

Ayar verir ${\displaystyle {\textsf {düzeltme}}\ F=\operatör adı {gerçek}}$

${\displaystyle \operatöradı {gerçek} \ n=(\operatöradı {IsZero} \ n)\ 1\ (\operatöradı {çoğal} \ n\ (\operatöradı {gerçek} \ (\operatöradı {pred} \ n))) \ .}$

Bu tanım, F'yi yinelenecek bir döngünün gövdesi rolüne sokar ve faktöriyelin matematiksel tanımına eşdeğerdir:

${\displaystyle \operatorname {fact} \ n={\begin{cases}1&{\text{if}}~n=0\\n\times \operatorname {fact} \ (n-1)&{\text{ aksi halde.}}\end{durumlar}}}$

Lambda hesabında sabit nokta birleştiriciler

Y tarafından keşfedilen combinator Haskell B. Curry olarak tanımlanır

${\displaystyle Y=\lambda f.(\lambda xf\ (x\ x))\ (\lambda xf\ (x\ x))\ .}$

Bunun beta indirgemesi şunları sağlar:

${\görüntüleme stili Y\ g}$	${\displaystyle =(\lambda f.(\lambda xf\ (x\ x))\ (\lambda xf\ (x\ x)))\ g}$	( Y tanımı gereği )
	${\displaystyle =(\lambda xg\ (x\ x))\ (\lambda xg\ (x\ x))}$	( λf'nin β-indirgenmesiyle : Y'nin g'ye uygulanması)
	${\displaystyle =g\ ((\lambda xg\ (x\ x))\ (\lambda xg\ (x\ x)))}$	(λx'in β-indirgenmesiyle: sol fonksiyondan sağ fonksiyona uygulanır)
	${\görüntüleme stili =g\ (Y\ g)}$	(ikinci eşitlikle)

Bu eşitliği tekrar tekrar uygulamak şunları verir:

${\displaystyle Y\ g=g\ (Y\ g)=g\ (g\ (Y\ g))=g\ (\ldots g\ (Y\ g)\ldots )}$

(Yukarıdaki eşitlik, soldan sağa çok adımlı β-indirgemelerinin bir dizisi olarak düşünülmelidir. Lambda terimi , genel olarak, terime β-indirgemeyebilir . Bunun yerine eşitlik işaretleri, β-eşdeğerlikleri olarak yorumlanabilir. her iki yönde de ilerlemeye izin vermek için çok adımlı β-indirgemeleri.) ${\görüntüleme stili g\ (Y\ g)}$${\görüntüleme stili Y\ g}$

Sabit nokta birleştiricinin eşdeğer tanımı

Bu sabit nokta birleştirici, aşağıdaki gibi y olarak tanımlanabilir .

${\displaystyle x=f\ x\kara y\ f=x}$

y için bir ifade , bir let ifadesinin tanımından kurallar kullanılarak türetilebilir . İlk olarak, kuralı kullanarak

${\displaystyle (\exists xE\land F)\iff \operatöradı {let} x:E\operatöradı {içinde} F}$

verir

${\displaystyle \operatöradı {let} x=f\ x\operatöradı {in} y\ f=x\ .}$

Ayrıca, kullanarak

${\displaystyle x\not \in \operatöradı {FV} (E)\land x\in \operatöradı {FV} (F)\to \operatöradı {let} x:G\operatöradı {in} E\ F=E\ (\operatöradı {let} x:G\operatöradı {içinde} F)}$

verir

${\displaystyle y\ f=\operatöradı {let} x=f\ x\operatöradı {in} x\ .}$

Ve sonra eta azaltma kuralını kullanarak ,

${\displaystyle f\ x=y\iff f=\lambda xy\ ,}$

verir

${\displaystyle y=\lambda f.\operatöradı {let} x=f\ x\operatöradı {in} x\ .}$

Y birleştiricisinin türetilmesi

Curry'nin Y birleştiricisi, y tanımından kolaylıkla elde edilebilir .

ile başlayan,

${\displaystyle \lambda f.\operatöradı {let} x=f\ x\operatöradı {in} x\ ,}$

Bir lambda soyutlaması, uygulanan ifadede değişken adına başvuruyu desteklemez, bu nedenle x parametresi olarak x'e geçirilmelidir . Biz değiştirmek gibi bu düşünebiliriz x tarafından xx , ancak resmi olarak bu doğru değil. Bunun yerine tanımlayarak y tarafından verir ${\görüntüleme stili \için tüm z,y\ z=x}$

${\displaystyle \lambda f.\operatöradı {let} y\ z=f\ (y\ z)\operatöradı {in} y\ z\ .}$

let ifadesi, z'nin parametre olduğu y fonksiyonunun tanımı olarak kabul edilebilir . Örnekleme z olarak y çağrısında verir

${\displaystyle \lambda f.\operatöradı {let} y\ z=f\ (y\ z)\operatöradı {in} y\ y\ .}$

Ve, z parametresi her zaman y işlevini geçtiği için ,

${\displaystyle \lambda f.\operatöradı {let} y\ z=f\ (z\ z)\operatöradı {in} y\ y\ .}$

Kullanılması eta azaltma kuralını,

${\displaystyle f\ x=y\eşdeğer f=\lambda xy\ ,}$

verir

${\displaystyle \lambda f.\operatöradı {let} y=\lambda zf\ (z\ z)\operatöradı {in} y\ y\ .}$

Bir let ekspresyonu lambda soyutlama olarak ifade edilebilir ; kullanarak

${\displaystyle n\not \in FV(E)\to (\operatorname {let} n=E\operatorname {in} L\equiv (\lambda nL)\ E)}$

verir

${\displaystyle \lambda f.(\lambda yy\ y)\ (\lambda zf\ (z\ z))\ .}$

Bu muhtemelen lambda hesabında sabit nokta birleştiricinin en basit uygulamasıdır. Bununla birlikte, bir beta indirgemesi, Curry'nin Y birleştiricisinin daha simetrik biçimini verir:

${\displaystyle \lambda f.(\lambda zf\ (z\ z))\ (\lambda zf\ (z\ z))\ .}$

Ayrıca bkz . let ve lambda ifadeleri arasında çeviri yapma .

Diğer sabit nokta birleştiriciler

Türlenmemiş lambda hesabında sabit nokta birleştiriciler özellikle nadir değildir. Aslında sonsuz sayıda var. 2005'te Mayer Goldberg, türlenmemiş lambda hesabının sabit nokta birleştiricileri kümesinin özyinelemeli olarak sayılabilir olduğunu gösterdi .

Y, combinator ifade edilebilir SKI-taşı olarak

${\görüntüleme stili Y=S(K(SII))(S(S(KS)K)(K(SII)))\ .}$

John Tromp tarafından bulunan SK hesabındaki en basit sabit nokta birleştiricisi ,

${\displaystyle Y'=SSK(S(K(SS(S(SSK))))K)\ .}$

normal formda olmadığına dikkat edin, ki bu daha uzundur. Bu birleştirici lambda ifadesine karşılık gelir

${\ Displaystyle Y'=(\lambda xy.xyx)(\lambda yx.y(xyx))\ .}$

Aşağıdaki sabit nokta birleştiricisi, Y birleştiricisinden daha basittir ve β, Y birleştiricisine indirgenir; bazen Y birleştiricisinin kendisi olarak anılır:

${\displaystyle X=\lambda f.(\lambda x.xx)(\lambda xf(xx))\ .}$

Diğer bir yaygın sabit nokta birleştiricisi, Turing sabit nokta birleştiricisidir (adını keşfedicisi Alan Turing'den almıştır ):

${\displaystyle \Theta =(\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ .}$

Bu avantaj, fazla olmasıdır beta-azaltır , oysa ve sadece ortak terim beta-azaltır. ${\displaystyle {\textsf {Y}}}$${\görüntüleme stili\Teta\f}$${\görüntüleme stili f\ (\Theta f)}$${\displaystyle {\textsf {Y}}\ f}$${\displaystyle f\ ({\textsf {Y}}f)}$

${\görüntüleme stili \Teta }$ ayrıca basit bir değere göre arama formuna sahiptir:

${\displaystyle \Theta _{v}=(\lambda xy.y(\lambda z.xxyz))\ (\lambda xy.y(\lambda z.xxyz))\ .}$

Karşılıklı özyineleme için analog , Y* olarak gösterilebilen çok değişkenli bir sabit nokta birleştiricidir .

Katı sabit nokta birleştirici

Bir de sıkı bir programlama dili Y combinator yığın taşması kadar genişleyecektir veya kuyruk optimizasyon görüşmemiz durumunda durdurmak asla. Z combinator (uygulamalı değerlendirme sırası uygulanır da adlandırılan istekli diller,) sıkı dilde çalışacaktır. Z, combinator genleşmesini önler, açık bir şekilde tanımlanmış aşağıdaki argüman , Z tanımı sağ tarafında g:

${\displaystyle Zgv=g(Zg)v\ .}$

ve lambda hesabında Y birleştiricisinin bir eta-genişlemesidir :

${\displaystyle Z=\lambda f.(\lambda xf(\lambda v.xxv))\ (\lambda xf(\lambda v.xxv))\ .}$

Standart olmayan sabit nokta birleştiriciler

Türlenmemiş lambda hesabında, sabit nokta birleştirici olarak aynı Böhm ağacına sahip olan , yani aynı sonsuz uzantıya sahip olan terimler vardır λx.x (x (x ... )). Bunlara standart olmayan sabit nokta birleştiricileri denir . Herhangi bir sabit nokta birleştirici de standart değildir, ancak standart olmayan tüm sabit nokta birleştiriciler, bazıları "standart" olanları tanımlayan denklemi karşılayamadığı için sabit nokta birleştirici değildir. Bu garip birleştiricilere kesinlikle standart olmayan sabit nokta birleştiriciler denir ; bir örnek aşağıdaki birleştiricidir:

${\görüntüleme stili N=BM(B(BM)B)}$

nerede

${\displaystyle B=\lambda xyz.x(yz)}$

${\displaystyle M=\lambda x.xx\ .}$

Standart olmayan sabit nokta birleştiriciler kümesi özyinelemeli olarak numaralandırılamaz.

Diğer dillerde uygulama

(Y birleştiricisi, lambda hesabında sabit nokta birleştiricinin özel bir uygulamasıdır. Yapısı lambda hesabının sınırlamaları tarafından belirlenir. Diğer dillerde sabit nokta birleştiricinin uygulanmasında bu yapının kullanılması gerekli veya yararlı değildir. )

Bazı programlama paradigmalarında uygulanan basit sabit nokta birleştirici örnekleri aşağıda verilmiştir.

Tembel işlevsel uygulama

Haskell'de olduğu gibi tembel değerlendirmeyi destekleyen bir dilde , geleneksel olarak adlandırılan sabit nokta birleştiricinin tanımlayıcı denklemini kullanarak bir sabit nokta birleştiricisi tanımlamak mümkündür . Haskell'in tembel veri türleri olduğundan, bu birleştirici aynı zamanda veri oluşturucularının sabit noktalarını tanımlamak için de kullanılabilir (yalnızca özyinelemeli işlevleri uygulamak için değil). Tanım burada ve ardından bazı kullanım örnekleri verilmiştir. Hackage'da orijinal örnek: fix

fix, fix' :: (a -> a) -> a
fix f = let x = f x in x         -- Lambda dropped. Sharing.
                                 -- Original definition in Data.Function.
-- alternative:
fix' f = f (fix' f)              -- Lambda lifted. Non-sharing.

fix (\x -> 9)                    -- this evaluates to 9

fix (\x -> 3:x)                  -- evaluates to the lazy infinite list [3,3,3,...]

fact = fix fac                   -- evaluates to the factorial function
  where fac f 0 = 1
        fac f x = x * f (x-1)

fact 5                           -- evaluates to 120

Katı işlevsel uygulama

Katı bir işlevsel dilde, f'nin argümanı önceden genişletilir ve sonsuz bir çağrı dizisi verir,

${\displaystyle f\ (f...(f\ (\operatöradı {düzelt} \ f))...)\ x}$.

Bu, düzeltmeyi fazladan bir parametre ile tanımlayarak çözülebilir.

let rec fix f x = f (fix f) x (* note the extra x; here fix f = \x-> f (fix f) x *)

let factabs fact = function   (* factabs has extra level of lambda abstraction *)
   0 -> 1
 | x -> x * fact (x-1)

let _ = (fix factabs) 5       (* evaluates to "120" *)

Zorunlu dil uygulaması

Bu örnek, sabit nokta birleştiricinin biraz yorumlayıcı bir uygulamasıdır. fixer adlı düzeltme işlevini içeren bir sınıf kullanılır . Sabitlenecek işlev, sabitleyiciden miras alan bir sınıfta bulunur. Düzeltme fonksiyonu sanal işlevi olarak tespit edilecek işlevini erişir. Katı işlevsel tanımlamaya gelince, fix'e açıkça fazladan bir x parametresi verilir , bu da tembel değerlendirmeye gerek olmadığı anlamına gelir.

template <typename R, typename D>
class fixer
{
public:
    R fix(D x)
    {
        return f(x);
    }
private:
    virtual R f(D) = 0;
};

class fact : public fixer<long, long>
{
    virtual long f(long x)
    {
        if (x == 0)
        {
            return 1;
        }
        return x * fix(x-1);
    }
};

long result = fact().fix(5);

Lisp , Scheme veya Racket gibi zorunlu işlevli bir dilde Landin (1963), sabit nokta birleştirici oluşturmak için değişken atamanın kullanılmasını önerir:

(define Y!
  (lambda (f-maker)
    ((lambda (f)
       (set! f (f-maker (lambda (x) (f x)))) ;; assignment statement
       f)
     'NONE)))

Atama ifadeleri için aksiyomlu bir lambda hesabı kullanarak, Y! değere göre çağrı Y birleştiricisiyle aynı sabit nokta yasasını karşılar:

${\displaystyle ({\textsf {Y}}_{!}\ \lambda xe)e'=(\lambda xe)\ ({\textsf {Y}}_{!}\ \lambda xe)e'}$

Yazıyor

Gelen Sistem F (polimorfik lambda taşı), bir polimorfik sabit nokta combinator türü vardır;

∀a.(a → a) → bir

burada a bir tür değişkenidir . Yani fix , a → a'yı eşleyen ve onu a türünde bir değer döndürmek için kullanan bir işlev alır.

Özyinelemeli veri türleri ile genişletilmiş, basit bir şekilde yazılan lambda hesabında , sabit nokta operatörleri yazılabilir, ancak "yararlı" bir sabit nokta operatörünün türü (uygulaması her zaman dönen) kısıtlanabilir.

Gelen basitçe daktilo Lambda calculus bir noktada kendi kendini uygulama alt vadede başa çünkü, sabit nokta combinator Y tipi atanamıyor uygulama kurala göre: ${\görüntüleme stili x~x}$

${\displaystyle {\Gamma \vdash x\!:\!t_{1}\to t_{2}\quad \Gamma \vdash x\!:\!t_{1}} \over {\Gamma \vdash x~ x\!:\!t_{2}}}$

sonsuz tip nerede . Aslında hiçbir sabit nokta birleştiricisi yazılamaz; bu sistemlerde, özyineleme için herhangi bir destek dile açıkça eklenmelidir. ${\görüntüleme stili x}$${\displaystyle t_{1}=t_{1}\to t_{2}}$

Y birleştiricisi için yazın

Özyinelemeli veri türlerini destekleyen programlama dillerinde , özyinelemeyi tür düzeyinde uygun şekilde hesaba katarak Y birleştiricisini yazmak mümkündür. x değişkenini kendi kendine uygulama ihtiyacı, (Rec a -> a) ile eşbiçimli olacak şekilde tanımlanan bir tür (Rec a) kullanılarak yönetilebilir.

Örneğin, aşağıdaki Haskell kodda, elimizdeki Inve outtürleri ile izomorfizim, iki yönden isimlerini olmak:

In :: (Rec a -> a) -> Rec a
out :: Rec a -> (Rec a -> a)

hangi yazmamıza izin verir:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Veya eşdeğer olarak OCaml'de:

type 'a recc = In of ('a recc -> 'a)
let out (In x) = x

let y f = (fun x a -> f (out x x) a) (In (fun x a -> f (out x x) a))

Alternatif olarak:

let y f = (fun x -> f (fun z -> out x x z)) (In (fun x -> f (fun z -> out x x z)))

Genel bilgi

Sabit noktalı combinators Özyinelemeyi uygulamak için kullanılabilir, çünkü, gibi olanlar gibi yinelemeli hesaplamalar, belirli türleri tanımlamak için kullanmak mümkündür sabit nokta yineleme , iteratif yöntemler , yinelemeli birleştirme içinde ilişkisel veri tabanları , veri akışı analizi , İLK ve bağlamdan bağımsız bir dilbilgisi , geçişli kapatma ve diğer kapatma işlemleri türlerinde terminal olmayan kümeleri TAKİP EDİN .

Bunun için bir fonksiyon , her giriş sabit bir nokta olan denir kimlik fonksiyonu . Resmi olarak:

${\görüntüleme stili\tüm x(f\ x=x)}$

Hepsi üzerinde evrensel nicelemenin aksine , sabit nokta birleştirici , sabit noktası olan bir değer oluşturur . Sabit nokta birleştiricinin dikkat çekici özelliği, rastgele verilen bir işlev için sabit bir nokta oluşturmasıdır . ${\görüntüleme stili x}$${\görüntüleme stili f}$${\görüntüleme stili f}$

Diğer işlevlerin, bir kez uygulandıktan sonra başka uygulamaların hiçbir etkisinin olmadığı özel özelliği vardır. Daha resmi:

${\displaystyle \forall x(f\ (f\ x)=f\ x)}$

Bu tür işlevlere idempotent denir (ayrıca bkz. İzdüşüm (matematik) ). Tüm çift tamsayılar için 0 ve tüm tek tamsayılar için 1 döndüren işlev böyle bir işlevin bir örneğidir .

Olarak lambda hesabı , bir kimlik işleve bir sabit noktalı bir bağdaştırıcının veya İdempotent fonksiyonu uygulanarak bir görüş hesaplama noktadan tipik olarak sona hesaplama ile sonuçlanır. Örneğin, elde ederiz

${\displaystyle (Y\ \lambda xx)=(\lambda x.(xx)\ \lambda x.(xx))}$

burada ortaya çıkan terim yalnızca kendisine indirgenebilir ve sonsuz bir döngüyü temsil eder.

Sabit nokta birleştiriciler, daha kısıtlayıcı hesaplama modellerinde mutlaka bulunmaz. Örneğin, basitçe yazılan lambda hesabında bulunmazlar .

Y, combinator sağlar yineleme bir dizi olarak tanımlanması yeniden yazma kuralları dilde doğal yineleme destek gerektirmeden.

Anonim işlevleri destekleyen programlama dillerinde , sabit nokta birleştiriciler anonim özyinelemeli işlevlerin tanımlanmasına ve kullanılmasına izin verir , yani bu tür işlevleri tanımlayıcılara bağlamak zorunda kalmadan . Bu ayarda, sabit nokta birleştiricilerinin kullanımına bazen anonim özyineleme denir .

Ayrıca bakınız

• anonim işlev
• Sabit nokta yineleme
• Lambda hesabı#Öyineleme ve sabit noktalar
• Lambda kaldırma
• ifade edelim

Notlar

Referanslar

• Werner Kluge, Soyut bilgi işlem makineleri: bir lambda hesabı perspektifi , Springer, 2005, ISBN  3-540-21146-2 , s. 73–77
• Mayer Goldberg, (2005) On the Recursive Enumerability of Fixed-Point Combinators , BRICS Report RS-05-1, University of Aarhus
• Matthias Felleisen , üzerine bir Ders Why ait Y .

Dış bağlantılar

• Özyineleme Teorisi ve Sevinç , Manfred von Thun, (2002 veya öncesi)
• Lambda Hesabı - Don Blaheta'nın notları, 12 Ekim 2000
• Y Birleştirici
• "Ruby'de Y Birleştiricisinin Kullanımı"
• "Ada'da fonksiyonel programlama"
• Rosetta kodu - Y birleştirici