Beta normal formu - Beta normal form

İçinde lambda hesabı bir terim var beta normal form Eğer hayırsa beta indirgeme mümkün.^[1] Bir terim var beta-eta normal formu ne beta indirimi ne de eta indirgeme mümkün. Bir terim var baş normal formu eğer yoksa baş pozisyonunda beta-redex.

Beta indirgeme

Lambda hesabında, bir beta redex şu formdaki bir terimdir:

${ displaystyle ( mathbf { lambda} x.A) M}$.

Bir redex ${ displaystyle r}$ içinde baş pozisyonu bir dönem ${ displaystyle t}$, Eğer ${ displaystyle t}$ aşağıdaki şekle sahiptir (uygulamanın soyutlamadan daha yüksek önceliğe sahip olduğunu ve aşağıdaki formülün bir uygulama değil, bir lambda-soyutlaması olduğunu unutmayın):

${ displaystyle lambda x_ {1} ldots lambda x_ {n}. underbrace {( lambda xA) M_ {1}} _ {{ text {redex}} r} M_ {2} ldots M_ {m}}$, nerede ${ displaystyle n geq 0}$ ve ${ displaystyle m geq 1}$.

Bir beta indirgeme aşağıdaki yeniden yazma kuralının bir terimin içerdiği bir beta redex'e uygulanmasıdır:

${ displaystyle ( mathbf { lambda} x.A) M longrightarrow A [x: = M]}$

nerede ${ displaystyle A [x: = M]}$ terimi ikame etmenin sonucudur ${ displaystyle M}$ değişken için ${ displaystyle x}$ dönem içinde ${ displaystyle A}$.

Bir baş beta indirgeme, kafa konumunda, yani aşağıdaki biçimde uygulanan bir beta indirgemesidir:

${ displaystyle lambda x_ {1} ldots lambda x_ {n}. ( lambda xA) M_ {1} M_ {2} ldots M_ {m} longrightarrow lambda x_ {1} ldots lambda x_ {n} .A [x: = M_ {1}] M_ {2} ldots M_ {m}}$, nerede ${ displaystyle n geq 0}$ ve ${ displaystyle m geq 1}$.

Diğer herhangi bir indirim bir iç beta indirgeme.

Bir normal form beta redex içermeyen bir terimdir, yani bu daha fazla azaltılamaz. Bir baş normal formu baş pozisyonunda beta redex içermeyen bir terimdir, yani bir kafa küçültme ile daha fazla azaltılamaz. Basit lambda hesabı düşünüldüğünde (yani sabit veya fonksiyon sembolleri eklenmeden, ek delta kuralı ile indirgenmesi amaçlanmıştır), baş normal formları aşağıdaki şeklin terimleridir:

${ displaystyle lambda x_ {1} ldots lambda x_ {n} .xM_ {1} M_ {2} ldots M_ {m}}$, nerede ${ displaystyle x}$ bir değişkendir, ${ displaystyle n geq 0}$ ve ${ displaystyle m geq 0}$.

Bir baş normal formu her zaman normal bir form değildir, çünkü uygulanan argümanlar ${ displaystyle M_ {j}}$ normal olması gerekmez. Bununla birlikte, bunun tersi doğrudur: herhangi bir normal form aynı zamanda bir baş normal formdur. Aslında normal formlar, tam olarak alt terimlerin baş normal formlarıdır. ${ displaystyle M_ {j}}$ kendileri normal biçimlerdir. Bu, normal formların tümevarımlı sözdizimsel bir tanımını verir.

Ek bir kavram var zayıf kafa normal formu (whnf): bir terim var whnf bir uygulama değilse ve sabit veya işlev simgesiyle başlamıyorsa. ${ displaystyle mathbf { lambda} x.M}$ içinde whnf çünkü bu bir soyutlamadır. ${ displaystyle 1 + 2}$ içinde değil whnf çünkü bir fonksiyon sembolü ile başlar, yani ${ displaystyle +}$.

Azaltma stratejileri

Genel olarak, belirli bir terim birkaç yeniden ifade içerebilir, bu nedenle birkaç farklı beta indirimi uygulanabilir. Bir belirleyebiliriz strateji hangi redeksin azaltılacağını seçmek için.

• Normal sıra azaltma Bu tür bir azalma mümkün olmayana kadar baş pozisyonunda beta azaltma kuralının sürekli olarak uygulandığı stratejidir. Bu noktada, ortaya çıkan terim, baş normal formdadır. Daha sonra alt terimlerde kafa azaltma uygulamaya devam edilir ${ displaystyle M_ {j}}$, soldan sağa. Aksi belirtilirse, normal sıralı azaltma, her zaman önce en soldaki en dıştaki redex'i azaltan stratejidir.
• Aksine, uygulama emri indirimi, biri önce dahili azaltmaları uygular ve sonra yalnızca daha fazla dahili azaltma mümkün olmadığında kafa azaltma uygular.

Normal sıra indirgeme tamamlanmıştır, yani bir terim normal bir kafa biçimine sahipse, o zaman normal sıra indirgemesi sonunda ona ulaşacaktır. Yukarıdaki normal formların sözdizimsel açıklamasıyla, bu "tamamen" normal bir form için aynı ifadeyi gerektirir (bu, standardizasyon teoremi ). Buna karşılık, terim normal bir biçime sahip olsa bile, uygulamalı sipariş indirimi sona ermeyebilir. Örneğin, uygulamalı sipariş indirimi kullanılarak, aşağıdaki indirimler dizisi mümkündür:

${ displaystyle { başlar {hizalı} & ( mathbf { lambda} xz) (( lambda w.www) ( lambda w.www)) sağ & ( lambda xz) (( lambda w .www) ( lambda w.www) ( lambda w.www)) rightarrow & ( lambda xz) (( lambda w.www) ( lambda w.www) ( lambda w.www) ( lambda w.www)) rightarrow & ( lambda xz) (( lambda w.www) ( lambda w.www) ( lambda w.www) ( lambda w.www) ( lambda w.www)) & ldots end {hizalı}}}$

Ancak normal sıra indirgeme kullanıldığında, aynı başlangıç ​​noktası hızla normal forma indirgenir:

${ displaystyle ( mathbf { lambda} x.z) (( lambda w.www) ( lambda w.www))}$

${ displaystyle rightarrow z}$

Sinot yönetmen dizeleri beta azaltmanın hesaplama karmaşıklığının optimize edilebileceği bir yöntemdir.

Ayrıca bakınız

• Lambda hesabı
• Normal form (belirsizliği giderme)

Referanslar