Notacja De Bruijna

W logice matematycznej notacja De Bruijna jest składnią terminów w rachunku λ wymyślonym przez holenderskiego matematyka Nicolaasa Goverta de Bruijna . Można to postrzegać jako odwrócenie zwykłej składni rachunku λ, w którym argument w aplikacji jest umieszczany obok odpowiadającego mu łącznika w funkcji zamiast po treści tego ostatniego.

Definicja formalna

Terminy ( $)$ ) w notacji De Bruijn są albo zmiennymi ( $albo$ mają jeden z dwóch przedrostków wagonów . Wagon abstrakcyjny , napisany , odpowiada zwykłemu segregatorowi λ rachunku λ , a wagon aplikatorowy , napisany ${\ Displaystyle (M)}$ , odpowiada argumentowi w [ v ] {\ Displaystyle $}$ zastosowanie w rachunku λ.

{\ Displaystyle M, N, ...:: = \ v \ |\ [v] \; M \ |\ (M) \; N}

Terminy w tradycyjnej składni można przekonwertować na notację De Bruijna, definiując funkcję indukcyjną, dla której: ${\ displaystyle {\ mathcal {I}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} {\ mathcal {I}} (v) & = v \\ {\ mathcal {I}} (\ lambda v. \ M) & = [v] \; {\ mathcal { I}}(M)\\{\mathcal {I}}(M\;N)&=({\mathcal {I}}(N)){\mathcal {I}}(M).\end{wyrównane }}}$

$tłumaczenia$ -warunkach dojeżdżają w odniesieniu do . Na przykład zwykła β-redukcja,

{\ Displaystyle (\ lambda v. \ M) \; N \ \ \ longrightarrow _ {\ beta} \ \ M [v: = N]}

w notacji De Bruijn jest, jak można było przewidzieć,

{\ Displaystyle (N) \; [v] \; M \ \ \ longrightarrow _ {\ beta} \ \ M [v: = N].}

Cechą tej notacji jest to, że wagony abstrakcji i aplikatora β-redeksów są sparowane jak nawiasy. Rozważmy na przykład etapy β-redukcji terminu ${\ Displaystyle (M) \; (N) \; [ u]\;(P)\;[v]\;[w]\;(Q)\;z}$ , gdzie powtórzenia są podkreślone:

${\ Displaystyle {\ rozpocząć {wyrównane} (M) \; {\ podkreślenie {(N) \; [u]}} \; (P) \; [v] \; [w] \; (Q) \; z&{\ \longrightarrow _{\beta }\ }(M)\;{\podkreślenie {(P[u:=N])\;[v]}}\;[w]\;(Q[u:= N])\;z\\&{\ \longrightarrow _{\beta }\ }{\underline {(M)\;[w]}}\;(Q[u:=N,v:=P[u :=N]])\;z\\&{\ \longrightarrow _{\beta }\ }(Q[u:=N,v:=P[u:=N],w:=M])\; z.\end{wyrównane}}}$

Tak więc, jeśli ktoś postrzega aplikator jako otwarty nawias (' ( '), a abstrakt jako nawias zamknięty (' ] '), to wzór w powyższym wyrażeniu to ' ((](]] '). De Bruijn nazwał aplikator i odpowiadający mu abstrakt w tej interpretacji partnerzy , a wagony bez partnerów kawalerzy . Ciąg wagonów, który nazwał segmentem , jest dobrze zrównoważony, jeśli wszystkie jego wagony są partnerami.

Zalety notacji De Bruijna

W dobrze zrównoważonym segmencie wagony współpracujące mogą być dowolnie przemieszczane i dopóki parytet nie zostanie zniszczony, znaczenie tego terminu pozostaje takie samo. $przykładzie$ aplikator można przenieść do jego $lub$ abstraktor W rzeczywistości wszystkie konwersje przemienne i permutacyjne na warunkach lambda można opisać po prostu w kategoriach zmiany kolejności wagonów partnerskich z zachowaniem parzystości. W ten sposób uzyskuje się uogólniony prymityw konwersji dla wyrazów λ w notacji De Bruijna.

Kilka właściwości terminów λ, które są trudne do określenia i udowodnienia przy użyciu tradycyjnej notacji, można łatwo wyrazić w notacji De Bruijna. Na przykład w opartych na teorii typów można łatwo obliczyć kanoniczną klasę typów dla terminu w kontekście pisania i przekształcić problem sprawdzania typów w problem sprawdzania, czy sprawdzany typ należy do tej klasy. Wykazano również, że notacja De Bruijna jest przydatna w rachunku różniczkowym do jawnego podstawienia w systemach typu czystego .

Zobacz też

Notacja matematyczna