Definicja rachunku lambda

Aby zapoznać się z ogólnym wprowadzeniem, zobacz rachunek lambda .

Rachunek lambda to formalny system matematyczny oparty na abstrakcji lambda i zastosowaniu funkcji . Podano tutaj dwie definicje języka: definicję standardową i definicję wykorzystującą wzory matematyczne.

Standardowa definicja

Ta formalna definicja została podana przez Alonzo Churcha .

Definicja

Wyrażenia lambda składają się z

• zmienne ${\ Displaystyle v_ {1}}$ , ${\ Displaystyle v_ {2}}$ , ..., ${\ Displaystyle v_ {n}}$ , ...
• symbole abstrakcji lambda $kropka$ ”.
• nawiasy ( )

Zbiór wyrażeń lambda można zdefiniować indukcyjnie : ${\ displaystyle \ Lambda}$

1. Jeśli ${\ displaystyle x}$ jest zmienną, to ${\ displaystyle x \ in \ Lambda}$
2. ${\ Displaystyle x}$ jest zmienną i ${\ Displaystyle M \ in \ Lambda}$ , to ${\ Displaystyle (\ lambda xM) \ in \ Lambda}$
3. Jeśli ${\ Displaystyle M, N \ in \ Lambda}$ , to ${\ Displaystyle (M \ N) \ in \ Lambda}$

Przypadki reguły 2 są znane jako abstrakcje, a przypadki reguły 3 są znane jako aplikacje.

Notacja

Aby notacja wyrażeń lambda była czytelna, zwykle stosuje się następujące konwencje.

• Skrajne nawiasy są odrzucane: ${\ Displaystyle M \ N}$ zamiast ${\ Displaystyle (M \ N)}$
• Zakłada się, że aplikacje są lewostronnie skojarzone: ${\ Displaystyle M \ N \ P}$ można pisać zamiast ${\ Displaystyle ((M \ N) \ P)}$
• Ciało abstrakcji rozciąga się tak daleko w prawo, jak to możliwe : ${\ Displaystyle \ lambda xM \ N}$ oznacza ${\ Displaystyle \ lambda x. (M \ N)}$ i nie ${\ Displaystyle (\ lambda xM) \ N}$
• Sekwencja abstrakcji jest skrócona: ${\ Displaystyle \ lambda x. \ lambda y. \ lambda zN}$ jest skracane jako ${\ Displaystyle \ lambda xyz.N}$

Zmienne swobodne i związane

$, że$ operator abstrakcji wiąże swoją zmienną wszędzie tam, gdzie występuje w abstrakcji. Mówi się, że zmienne, które wchodzą w zakres abstrakcji, są powiązane . Wszystkie inne zmienne są nazywane free . Na $przykład$ w poniższym wyrażeniu $jest$ związaną i wolna: ${\ Displaystyle \ lambda yx \ x \ y}$ . Należy również zauważyć, że zmienna jest związana z jej „najbliższą” abstrakcją. W poniższym przykładzie pojedyncze wystąpienie wyrażenia w wyrażeniu jest ograniczone przez drugą lambdę: ${\ Displaystyle \ lambda xy (\ lambda xz \ x)}$$}$

Zbiór wolnych zmiennych wyrażenia lambda , jest oznaczony jako $}$$Displaystyle \ operatorname {FV} (M$ i jest zdefiniowany przez rekurencję w strukturze terminów, jak co następuje:

1. ${\ Displaystyle \ nazwa operatora {FV} (x) = \ {x \}}$ , gdzie ${\ Displaystyle x}$ jest zmienną
2. ${\ Displaystyle \ nazwa operatora {FV} (\ lambda xM) = \ nazwa operatora {FV} (M) \ ukośnik odwrotny \ {x \}}$
3. ${\ Displaystyle \ nazwa operatora {FV} (M \ N) = \ nazwa operatora {FV} (M) \ kubek \ nazwa operatora {FV} (N) }$

Mówimy, że wyrażenie, które nie zawiera wolnych zmiennych, jest zamknięte . Zamknięte wyrażenia lambda są również znane jako kombinatory i są równoważne terminom w logice kombinatorycznej .

Zmniejszenie

Znaczenie wyrażeń lambda jest definiowane przez sposób, w jaki można je zredukować.

Istnieją trzy rodzaje redukcji:

• α-konwersja : zmiana zmiennych powiązanych ( alfa );
• β-redukcja : zastosowanie funkcji do ich argumentów ( beta );
• η-redukcja : która oddaje pojęcie ekstensjonalności ( eta ).

Mówimy również o wynikowych równoważnościach: dwa wyrażenia są β-równoważne , jeśli można je β-przekonwertować na to samo wyrażenie, a równoważność α/η jest zdefiniowana podobnie.

Termin redex , skrót od wyrażenia redukowalnego , odnosi się do terminów podrzędnych, które można zredukować za pomocą jednej z reguł redukcji. Na przykład $(\ lambda xM) \ N}$${\ displaystyle x}$ jest β-redexem w wyrażaniu podstawienia za $w$ M $\ displaystyle M }$ ; jeśli nie jest wolny w ${\ displaystyle M}$ , $displaystyle x}$${\ Displaystyle \ lambda xM \ x}$ jest η-redex. Wyrażenie, do którego redukuje się redex, nazywa się jego redukcją; używając poprzedniego przykładu, redukty tych wyrażeń to odpowiednio ${\ Displaystyle M [x: = N]}$ i ${\ displaystyle M}$ .

konwersja α

Konwersja alfa, czasami nazywana zmianą nazwy alfa, umożliwia zmianę powiązanych nazw zmiennych. Na przykład konwersja alfa ${\ Displaystyle \ lambda xx}$ może dać ${\ Displaystyle \ lambda yy}$ . Terminy, które różnią się tylko konwersją alfa, nazywane są ekwiwalentami alfa . Często w zastosowaniach rachunku lambda terminy równoważne α są uważane za równoważne.

Dokładne zasady konwersji alfa nie są całkowicie trywialne. Po pierwsze, podczas konwersji alfa abstrakcji jedynymi wystąpieniami zmiennych, których nazwy są zmieniane, są te, które są powiązane z tą samą abstrakcją. Na przykład konwersja alfa ${\ Displaystyle \ lambda x. \ lambda xx}$ może skutkować ${\ Displaystyle \ lambda y. \ lambda xx}$ , ale nie mogło to skutkować ${\ Displaystyle \ lambda y. \ lambda xy}$ . Ten ostatni ma inne znaczenie niż oryginał.

Po drugie, konwersja alfa nie jest możliwa, jeśli spowodowałaby przechwycenie zmiennej przez inną abstrakcję. Na przykład, jeśli zastąpimy ${\ displaystyle x}$ przez ${\ displaystyle y}$ w ${\ Displaystyle \ lambda x. \ lambda yx}$ , otrzymujemy ${\ Displaystyle \ lambda y. \ lambda yy}$ , co wcale nie jest takie samo.

W językach programowania o zakresie statycznym konwersję alfa można wykorzystać do uproszczenia rozpoznawania nazw , zapewniając, że żadna nazwa zmiennej nie maskuje nazwy w zakresie zawierającym (patrz zmiana nazwy alfa w celu uproszczenia rozpoznawania nazw ).

Podstawienie

$mi [ V: = R ]$ , napisane $\ displaystyle E$ to proces zastępowania wszystkich wolnych wystąpień zmiennej w wyrażeniu $mi$ { ${\ Displaystyle R}$ . Substytucja na warunkach rachunku lambda jest definiowana przez rekurencję na strukturze terminów w następujący sposób (uwaga: x i y to tylko zmienne, podczas gdy M i N to dowolne wyrażenie λ).

${\ Displaystyle {\ rozpocząć {wyrównane} x [x: = N] i \ równoważnik N \\ y [x: = N]&\equiv y{\text{, if }}x\neq y\end{wyrównane}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} (M_ {1} \ M_ {2}) [x: = N] i \ równoważnik (M_ {1} [x: = N]) \ (M_ {2}[x:=N])\\(\lambda xM)[x:=N]&\równoważnik \lambda xM\\(\lambda yM)[x:=N]&\równoważnik \lambda y.( M[x:=N]){\text{, jeśli }}x\neq y{\text{, pod warunkiem }}y\notin FV(N)\end{wyrównane}}}$

Aby zastąpić abstrakcję lambda, czasami konieczna jest konwersja wyrażenia α. Na przykład nie jest poprawne, aby ${\ Displaystyle (\ lambda xy) [y: = x]}$ skutkowało ${\ Displaystyle (\ lambda xx)}$ , ponieważ podstawiony miał być wolny, ale ostatecznie został $związany$ Prawidłowe podstawienie w tym przypadku to ${\ Displaystyle (\ lambda zx)}$ aż do α-równoważności. Zauważ, że substytucja jest definiowana jednoznacznie aż do równoważności α.

β-redukcja

Redukcja β oddaje ideę zastosowania funkcji. β $} styl wyświetlania E[V:=E']}$$(\ lambda VE) \$ w kategoriach podstawienia: β-redukcja jest mi .

$(\lambda n.\ n\times 2)\ 7)\rightarrow 7\times 2}$$($ kodowanie , mamy następującą β-redukcję: $($ .

η-redukcja

Redukcja η wyraża ideę ekstensjonalności , która w tym kontekście polega na tym, że dwie funkcje są takie same wtedy i tylko wtedy, gdy dają ten sam wynik dla wszystkich argumentów. η-redukcja konwertuje między ${\ Displaystyle \ lambda x. (fx)}$ i ${\ displaystyle f}$$ilekroć$ nie pojawia się za darmo w ${\ displaystyle f}$ .

Normalizacja

Główny artykuł: normalna postać beta

Celem β-redukcji jest obliczenie wartości. Wartość w rachunku lambda jest funkcją. Tak więc β-redukcja trwa, dopóki wyrażenie nie wygląda jak abstrakcja funkcji.

Wyrażenie lambda, którego nie można dalej zredukować ani przez β-redex, ani η-redex, ma postać normalną. Zauważ, że konwersja alfa może konwertować funkcje. Wszystkie postacie normalne, które można przekształcić na siebie nawzajem przez konwersję α, są zdefiniowane jako równe. Zobacz główny artykuł na temat normalnej postaci Beta, aby uzyskać szczegółowe informacje.

Normalny typ formularza	Definicja.
Normalna forma	Żadne redukcje β lub η nie są możliwe.
Normalna postać głowy	W postaci abstrakcji lambda, której ciało nie jest redukowalne.
Słaba Głowa Normalna Forma	W postaci abstrakcji lambda.

Definicja składni w BNF

Rachunek Lambda ma prostą składnię. Program rachunku lambda ma składnię wyrażenia, w którym

Nazwa	BNF	Opis
Abstrakcja	< wyrażenie > ::= λ < lista-zmiennych > . < wyrażenie >	Definicja funkcji anonimowej.
Termin aplikacji	< wyrażenie > ::= < termin-aplikacji >
Aplikacja	< termin-aplikacji > ::= < termin-aplikacji > < element >	Wywołanie funkcji.
Przedmiot	< termin-aplikacji > ::= < pozycja >
Zmienny	< pozycja > ::= < zmienna >	Np. x, y, fakt, suma, ...
Grupowanie	< element > ::= ( < wyrażenie > )	Wyrażenie w nawiasach.

Lista zmiennych jest zdefiniowana jako,

  <  lista-zmiennych  >  :=  <  zmienna  >  |  <  zmienna  >  ,  <  lista-zmiennych  > 

Zmienna używana przez informatyków ma składnię,

    
   
     
    <  zmienna  >  ::=  <  alfa  >  <  rozszerzenie  >  <  rozszerzenie  >  ::=  <  rozszerzenie  >  ::=  <  znak rozszerzenia  >  <  rozszerzenie  >  <  znak rozszerzenia  >  ::=  <  alfa  >  |  <  cyfra  >  | _  

Matematycy czasami ograniczają zmienną do pojedynczego znaku alfabetu. Podczas korzystania z tej konwencji przecinek jest pomijany na liście zmiennych.

Abstrakcja lambda ma niższy priorytet niż aplikacja, więc;

${\ Displaystyle \ lambda xy \ z = \ lambda x. (y \ z)}$

Aplikacje pozostają asocjacyjne;

${\ Displaystyle x \ y \ z = (x \ y) \ z}$

Abstrakcja z wieloma parametrami jest równoważna z wieloma abstrakcjami jednego parametru.

${\ Displaystyle \ lambda xyz = \ lambda x. \ lambda yz}$

Gdzie,

• x jest zmienną
• y jest listą zmiennych
• z jest wyrażeniem

Definicja jako wzory matematyczne

Problem, w jaki sposób można zmieniać nazwy zmiennych, jest trudny. Ta definicja pozwala uniknąć problemu, zastępując wszystkie nazwy nazwami kanonicznymi, które są tworzone na podstawie pozycji definicji nazwy w wyrażeniu. Podejście jest analogiczne do tego, co robi kompilator, ale zostało przystosowane do pracy w ramach ograniczeń matematyki.

Semantyka

Wykonanie wyrażenia lambda przebiega przy użyciu następujących redukcji i przekształceń,

1. α-konwersja - $\ Displaystyle \ operatorname {alpha-conv} (a) \to \operatorname {kanonim} [A,P]=\operatorname {kanonim} [a[A],P]}$
2. β-redukcja - ${\ Displaystyle \ nazwa operatora {beta-redex} [\ lambda pb \ v] = b [p: = v]}$
3. η-redukcja - ${\ Displaystyle x \ nie \ w \ nazwa operatora {FV} (f) \ do \ nazwa operatora {eta-redex} [\ lambda x. (f \ x)] = f}$

Gdzie,

• canonym to zmiana nazwy wyrażenia lambda w celu nadania wyrażeniu standardowych nazw na podstawie pozycji nazwy w wyrażeniu.
• Operator podstawienia , ${\ Displaystyle b [p: = v]}$ jest podstawieniem nazwy $w$ wyrażenie lambda wyrażeniu lambda $displaystyle v}$$b}$$\$ .
• Swobodny zestaw zmiennych ${\ Displaystyle \ operatorname {FV} (f)}$ to zbiór zmiennych, które nie należą do abstrakcji lambda w ${\ displaystyle f}$ .

Wykonanie polega na wykonywaniu redukcji β i redukcji η na podwyrażeniach w kanonimie wyrażenia lambda, aż wynikiem będzie funkcja lambda (abstrakcja) w postaci normalnej .

Wszystkie konwersje α wyrażenia λ są uważane za równoważne.

Kanonim - Nazwy kanoniczne

Canonym to funkcja, która pobiera wyrażenie lambda i zmienia nazwy kanonicznie na podstawie ich pozycji w wyrażeniu. Może to zostać zaimplementowane jako

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {kanonim} [L, Q] & = \ nazwa operatora {kanonim} [L, O, Q] \\\ nazwa operatora {kanonim} [\ lambda pb, M, Q ]&=\lambda \nazwa_operatora {nazwa} (Q).\nazwa_operatora {kanonim} [b,M[p:=Q],Q+N]\\\nazwa_operatora {kanonim} [X\ Y,x,Q] &=\operatorname {kanonim} [X,x,Q+F]\\operatorname {kanonim} [Y,x,E+S]\\\operatorname {kanonim} [x,M,Q]&=\operatorname { nazwa} (M[x])\end{wyrównane}}}$

Gdzie N to ciąg „N”, F to ciąg „F”, S to ciąg „S”, + to konkatenacja, a „nazwa” konwertuje ciąg na nazwę

Operatorzy mapy

Odwzoruj jedną wartość na inną, jeśli wartość znajduje się na mapie. O to pusta mapa.

1. ${\ Displaystyle O [x] = x}$
2. ${\ Displaystyle M [x: = y][x] = y}$
3. ${\ Displaystyle x \ neq z \ do M [x: = y] [z] = M [z]}$

Operator podstawienia

Jeśli L jest wyrażeniem lambda, x jest nazwą, a y jest wyrażeniem lambda; ${\ Displaystyle L [x: = y]}$ oznacza zastąpienie x przez y w L. Zasady są następujące:

1. ${\ Displaystyle (\ lambda pb) [x: = y] = \ lambda pb [x: = y]}$
2. ${\ Displaystyle (X \, Y) [x: = y] = X [x: = y] \, Y[x:=y]}$
3. ${\ Displaystyle z = x \ do (z) [x: = y] = y}$
4. ${\ Displaystyle z \ neq x \ do (z) [x: = y] = z}$

Zauważ, że reguła 1 musi zostać zmodyfikowana, jeśli ma być używana w wyrażeniach lambda, których nazwy nie zostały zmienione kanonicznie. Zobacz Zmiany w operatorze podstawienia .

Wolne i związane zbiory zmiennych

Zbiór zmiennych wolnych wyrażenia lambda, M, jest oznaczony jako FV(M). Jest to zestaw nazw zmiennych, których instancje nie są powiązane (używane) w abstrakcji lambda, w wyrażeniu lambda. Są to nazwy zmiennych, które mogą być powiązane ze zmiennymi parametrów formalnych spoza wyrażenia lambda.

Zbiór powiązanych zmiennych wyrażenia lambda, M, jest oznaczony jako BV(M). Jest to zestaw nazw zmiennych, które mają instancje powiązane (używane) w abstrakcji lambda, w wyrażeniu lambda.

Poniżej podano zasady dla obu zestawów.

${\ Displaystyle \ operatorname {FV} (M)}$ - Swobodny zbiór zmiennych	Komentarz	${\ Displaystyle \ operatorname {BV} (M)}$ - Zbiór zmiennych związanych	Komentarz
${\ Displaystyle \ operatorname {FV} (x) = \ {x \}}$	gdzie x jest zmienną	${\ Displaystyle \ operatorname {BV} (x) = \ pusty zbiór}$	gdzie x jest zmienną
${\ Displaystyle \ operatorname {FV} (\ lambda xM) = \ operatorname {FV} (M) \ setminus \ {x \}}$	Wolne zmienne M z wyłączeniem x	${\ Displaystyle \ operatorname {BV} (\ lambda xM) = \ operatorname {BV} (M) \ puchar \ {x \}}$	Zmienne związane M plus x.
${\ Displaystyle \ operatorname {FV} (M \ N) = \ operatorname {FV} (M) \ kubek \ operatorname {FV} (N) }$	Połącz wolne zmienne z funkcji i parametru	${\ Displaystyle \ operatorname {BV} (M \ N) = \ operatorname {BV} (M) \ kubek \ operatorname {BV} (N) }$	Połącz powiązane zmienne z funkcji i parametru

Stosowanie;

• Zbiór zmiennych swobodnych FV jest używany powyżej w definicji redukcji η .
• Bound Variable Set, BV, jest używany w regule dla β-redexu niekanonicznego wyrażenia lambda.

Strategia oceny

Ta matematyczna definicja ma taką strukturę, że przedstawia wynik, a nie sposób jego obliczenia. Jednak wynik może być inny w przypadku leniwej i chętnej oceny. Ta różnica jest opisana we wzorach oceny.

Podane tutaj definicje zakładają, że zostanie użyta pierwsza definicja pasująca do wyrażenia lambda. Ta konwencja jest stosowana, aby definicja była bardziej czytelna. W przeciwnym razie wymagane byłyby pewne warunki, aby definicja była precyzyjna.

Uruchamianie lub ocenianie wyrażenia lambda L to,

${\ Displaystyle \ operatorname {eval} [\ operatorname {kanonim} [L], Q]}$

gdzie Q jest przedrostkiem nazwy, prawdopodobnie pustym ciągiem znaków, a eval jest zdefiniowany przez,

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {eval} [x \ y] & = \ nazwa operatora {eval} [\ nazwa operatora {zastosuj} [\ nazwa operatora {eval} [x] \ \ nazwa operatora {strategia} [y] ]]\\\operatorname {zastosuj} [(\lambda xy)\ z]&=\operatorname {kanonim} [\operatorname {beta-redex} [(\lambda xy)\ z],x]\\\operatorname { zastosuj} [x]&=x{\text{ jeśli x odpowiada powyższemu.}}\\\nazwa_operatora {eval} [\lambda x.(f\ x)]&=\nazwa_operatora {eval} [\nazwa_operatora { eta-redex} [\lambda x.(f\ x)]]\\\nazwa_operatora {eval} [L]&=L\\\nazwa_operatora {leniwy} [X]&=X\\\nazwa_operatora {chętny} [ X]&=\operatorname {eval} [X]\end{aligned}}}$

Następnie strategia ewaluacji może zostać wybrana jako:

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {strategia} & = \ nazwa operatora {leniwy} \\\ nazwa operatora {strategia} & = \ nazwa operatora {chętny} \ koniec {wyrównane}}}$

Wynik może być różny w zależności od zastosowanej strategii. Ocena chętna zastosuje wszystkie możliwe redukcje, pozostawiając wynik w normalnej postaci, podczas gdy ocena leniwa pominie niektóre redukcje parametrów, pozostawiając wynik w „normalnej postaci słabej głowy”.

Normalna forma

Wszystkie redukcje, które można było zastosować, zostały zastosowane. Jest to wynik uzyskany z zastosowania chętnej oceny.

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {normalna} [(\ lambda xy) \ z] & = \ nazwa operatora {fałsz} \\\ nazwa operatora {normalna} [\ lambda x. (f \ x)] & = \operatorname {false} \\\operatorname {normalny} [x\ y]&=\operatorname {normalny} [x]\land \operatorname {normalny} [y]\end{aligned}}}$

We wszystkich innych przypadkach

${\ Displaystyle \ nazwa operatora {normalna} [x] = \ nazwa operatora {prawda}}$

Słaba głowa w normalnej formie

Zastosowano redukcje funkcji (głowy), ale nie wszystkie redukcje parametru zostały zastosowane. Jest to wynik uzyskany z zastosowania oceny leniwej.

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {whnf} [(\ lambda xy) \ z] & = \operatorname {false} \\\operatorname {whnf} [x\ y]&=\operatorname {whnf} [x]\end{aligned}}}$

We wszystkich innych przypadkach

${\ Displaystyle \ nazwa operatora {whnf} [x] = \ nazwa operatora {prawda}}$

Wyprowadzenie normy z definicji matematycznej

Standardowa definicja rachunku lambda posługuje się pewnymi definicjami, które można uznać za twierdzenia, których można dowieść na podstawie definicji w postaci wzorów matematycznych .

Definicja nazewnictwa kanonicznego rozwiązuje problem tożsamości zmiennej poprzez konstruowanie unikalnej nazwy dla każdej zmiennej na podstawie pozycji abstrakcji lambda dla nazwy zmiennej w wyrażeniu.

Ta definicja wprowadza zasady stosowane w definicji standardowej i wyjaśnia je w kategoriach kanonicznej definicji zmiany nazwy.

Zmienne swobodne i związane

Operator abstrakcji lambda, λ, przyjmuje formalną zmienną parametru i wyrażenie ciała. Podczas oceny zmienna parametru formalnego jest identyfikowana z wartością parametru rzeczywistego.

Zmienne w wyrażeniu lambda mogą być „powiązane” lub „wolne”. Zmienne powiązane to nazwy zmiennych, które są już dołączone do formalnych zmiennych parametrów w wyrażeniu.

Mówi się, że zmienna parametru formalnego wiąże nazwę zmiennej, gdziekolwiek występuje ona w ciele. Zmienne (nazwy), które zostały już dopasowane do formalnej zmiennej parametru, nazywane są powiązanymi . Wszystkie inne zmienne w wyrażeniu są nazywane free .

Na przykład w poniższym wyrażeniu y jest zmienną związaną, a x jest wolną: ${\ Displaystyle \ lambda yx \ x \ y}$ . Należy również zauważyć, że zmienna jest powiązana z jej „najbliższą” abstrakcją lambda. W poniższym przykładzie pojedyncze wystąpienie x w wyrażeniu jest ograniczone przez drugą lambdę: ${\ Displaystyle \ lambda xy \ (\ lambda xz \ x)}$

Zmiany w operatorze podstawienia

W definicji Operatora Zastępczego reguła,

• ${\ Displaystyle (\ lambda pb) [x: = y] = \ lambda pb [x: = y]}$

należy wymienić na,

1. ${\ Displaystyle (\ lambda xb) [x: = y] = \ lambda xb}$
2. ${\ Displaystyle Z \ neq x \ \ do (\ lambda zb) [x: = y] = \ lambda zb [x: = y]}$

Ma to na celu zatrzymanie zastępowania powiązanych zmiennych o tej samej nazwie. To nie miałoby miejsca w kanonicznie przemianowanym wyrażeniu lambda.

Na przykład poprzednie zasady zostałyby błędnie przetłumaczone,

${\ Displaystyle (\ lambda xx \ z) [x: = y] = (\ lambda xy \ z)}$

Nowe zasady blokują to zastąpienie, tak że pozostaje takie,

${\ Displaystyle (\ lambda xx \ z) [x: = y] = (\ lambda xx \ z)}$

Transformacja

Znaczenie wyrażeń lambda jest definiowane przez sposób, w jaki wyrażenia mogą być przekształcane lub redukowane.

Istnieją trzy rodzaje transformacji:

• α-konwersja : zmiana zmiennych powiązanych ( alfa );
• β-redukcja : stosowanie funkcji do ich argumentów ( beta ), wywoływanie funkcji;
• η-redukcja : która oddaje pojęcie ekstensjonalności ( eta ).

Mówimy również o wynikowych równoważnościach: dwa wyrażenia są β-równoważne , jeśli można je β-przekonwertować na to samo wyrażenie, a równoważność α/η jest zdefiniowana podobnie.

Termin redex , skrót od wyrażenia redukowalnego , odnosi się do terminów podrzędnych, które można zredukować za pomocą jednej z reguł redukcji.

konwersja α

Konwersja alfa, czasami nazywana zmianą nazwy alfa, umożliwia zmianę powiązanych nazw zmiennych. Na przykład konwersja alfa ${\ Displaystyle \ lambda xx}$ może dać ${\ Displaystyle \ lambda yy}$ . Terminy, które różnią się tylko konwersją alfa, nazywane są ekwiwalentami alfa .

W konwersji α nazwy mogą być zastępowane nowymi nazwami, jeśli nowa nazwa nie jest wolna w treści, ponieważ prowadziłoby to do przechwycenia wolnych zmiennych .

${\ Displaystyle (y \ nie \ w FV(b)\land a(\lambda xb)=\lambda yb[x:=y])\to \operatorname {alpha-con} (a)}$

$,$ że podstawienie nie będzie rekurencyjne w treści wyrażeń lambda z parametrem formalnym powodu zmiany operatora podstawienia opisanej powyżej.

Zobacz przykład;

konwersja α	wyrażenie λ	Nazwany kanonicznie	Komentarz
	${\ Displaystyle \ lambda z. \ lambda y. (z \ y)}$	${\ Displaystyle \ lambda \ nazwa operatora {P}. \ lambda \ nazwa operatora {PN}. (\ nazwa operatora {P} \ nazwa operatora {PN})}$	Oryginalne wyrażenia.
poprawnie zmień nazwę y na k, (ponieważ k nie jest używane w treści)	${\ Displaystyle \ lambda z. \ lambda k. (z \ k)}$	${\ Displaystyle \ lambda \ nazwa operatora {P}. \ lambda \ nazwa operatora {PN}. (\ nazwa operatora {P} \ nazwa operatora {PN})}$	Brak zmian w kanonicznym wyrażeniu o zmienionej nazwie.
naiwnie zmień nazwę y na z (źle, ponieważ z jest wolne w ${\ Displaystyle \ lambda y. (z \ y)}$ )	${\ Displaystyle \ lambda z. \ lambda z. (z \ z)}$	${\ Displaystyle \ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {PN}. ({\ kolor {czerwony} \ nazwa operatora {PN}} \ nazwa operatora {PN})}$	zostaje przechwycony. ${\ displaystyle z}$

β-redukcja (unikanie przechwytywania)

β-redukcja oddaje ideę zastosowania funkcji (zwanej także wywołaniem funkcji) i implementuje podstawienie rzeczywistego wyrażenia parametru zamiast formalnej zmiennej parametru. β-redukcja jest zdefiniowana w kategoriach podstawienia.

Jeśli żadne nazwy zmiennych nie są wolne w rzeczywistym parametrze i związane w treści, β-redukcję można przeprowadzić na abstrakcji lambda bez zmiany nazwy kanonicznej.

${\ Displaystyle (\ forall z: z \ not \ in FV (y) \ lor z \ not \ in BV (b)) \ ​​to \ operatorname {beta-redex} [\ lambda xb \ y] = b [x: =y]}$

Zmiana nazwy alfa może być użyta do zmiany nazw, które są wolne w $ale$ związane w $displaystyle b} , aby$$spełnić$ warunek wstępny tej transformacji.

Zobacz przykład;

β-redukcja	wyrażenie λ	Nazwany kanonicznie	Komentarz
	${\ Displaystyle (\ lambda x. \ lambda y. (\ lambda z. (\ lambda xz\ x)(\lambda yz\ y))(x\ y))}$	${\ Displaystyle (\ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {PN} . (\ lambda \ nazwa operatora {PNF} . (\ lambda \ nazwa operatora {PNFNF} . \ nazwa operatora {PNF} \ nazwa operatora {PNFNF}) ( \lambda \nazwa_operatora {PNFNS} .\nazwa_operatora {PNF} \nazwa_operatora {PNFNS} ))(\nazwa_operatora {P} \nazwa_operatora {PN} ))}$	Oryginalne wyrażenia.
naiwna beta 1,	${\ Displaystyle (\ lambda x. \ lambda y. ((\ lambda x. (x \ y)x)(\lambda y.(x\ y)y)))}$	Kanoniczny ${\ Displaystyle (\ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {PN} . ((\ lambda \ nazwa operatora {PNF}. ({\ kolor {niebieski} \ nazwa operatora {P}} \ nazwa operatora {PN}) \ nazwa_operatora {PNF} )(\lambda \nazwa_operatora {PNS} .(\nazwa_operatora {P} {\kolor {niebieski}\nazwa_operatora {PN}}}\nazwa_operatora {PNS} ))}}$ Naturalny ${\ Displaystyle (\ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {PN} . ((\ lambda \ nazwa operatora {PNF}. ({\ kolor {czerwony} \ nazwa operatora {PNF}} \ nazwa operatora {PN}) \ operatorname {PNF} )(\lambda \operatorname {PNS} .(\operatorname {P} {\color {Red}\operatorname {PNS} )}\operatorname {PNS} )))}$	x (P) i y (PN) zostały uchwycone w podstawieniu.
Alfa zmień nazwę wewnętrzna, x → a, y → b	${\ Displaystyle (\ lambda x. \ lambda y. (\ lambda z. (\ lambda xz\ a)(\lambda bz\ b))(x\ y))}$	${\ Displaystyle (\ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {PN} . (\ lambda \ nazwa operatora {PNF} . (\ lambda \ nazwa operatora {PNFNF} . \ nazwa operatora {PNF} \ nazwa operatora {PNFNF}) ( \lambda \nazwa_operatora {PNFNS} .\nazwa_operatora {PNF} \nazwa_operatora {PNFNS} ))(\nazwa_operatora {P} \nazwa_operatora {PN} ))}$
Beta 2,	${\ Displaystyle (\ lambda x. \ lambda y. ((\ lambda a. (x \ y)a)(\lambda b.(x\ y)b)))}$	Kanoniczny ${\ Displaystyle (\ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {PN } .((\lambda \nazwa_operatora {PNF} .(\nazwa_operatora {P} \nazwa_operatora {PN} )\nazwa_operatora {PNF} )(\lambda \nazwa_operatora {PNS} .(\nazwa_operatora {P} \nazwa_operatora {PN} )\nazwa operatora {PNS} )))}$ Naturalny ${\ Displaystyle (\ lambda \ nazwa operatora {P} . \ lambda \ nazwa operatora {$	x i y nie zostały przechwycone.

${\ Displaystyle {\ rozpocząć {tablica} {r} ((\ lambda xz \ x) (\ lambda yz \ y)} [z: = (x \ y)] \\ ((\ lambda az \ a) (\ lambda bz\ b))[z:=(x\ y)]\end{tablica}}}$

w tym przykładzie

1. W β-redeksie,
   1. Wolne zmienne to ${\ Displaystyle \ operatorname {FV} (x \ y) = \ {x, y \}}$
   2. Zmienne związane to ${\ Displaystyle \ nazwa operatora {BV} ((\ lambda xz \ x) (\ lambda yz \ y))=\{x,y\}}$
2. Naiwny β-redex zmienił znaczenie wyrażenia, ponieważ x i y z rzeczywistego parametru zostały przechwycone, gdy wyrażenia zostały podstawione w wewnętrznych abstrakcjach.
3. Zmiana nazwy alfa usunęła problem, zmieniając nazwy x i y w wewnętrznej abstrakcji, tak aby różniły się od nazw x i y w rzeczywistym parametrze.
   1. Wolne zmienne to ${\ Displaystyle \ operatorname {FV} (x \ y) = \ {x, y \}}$
   2. Zmienne związane to ${\ Displaystyle \ operatorname {BV} ((\ lambda az \ a) (\ lambda bz \ b))=\{a,b\}}$
4. Następnie β-redex miał zamierzone znaczenie.

η-redukcja

Redukcja η wyraża ideę ekstensjonalności , która w tym kontekście polega na tym, że dwie funkcje są takie same wtedy i tylko wtedy, gdy dają ten sam wynik dla wszystkich argumentów.

Redukcji η można używać bez zmian w wyrażeniach lambda, których nazwy nie zostały zmienione kanonicznie.

${\ Displaystyle x \ nie \ w \ operatorname {FV} (f) \ do {\ tekst {η-redex}} [\ lambda x. (fx)] = f}$

W tym przykładzie pokazano problem z użyciem η-redex, gdy f ma wolne zmienne,

Zmniejszenie	Wyrażenie lambda	β-redukcja
	${\ Displaystyle (\ lambda x. (\ lambda yy \, x) \, x) \, a}$	${\ Displaystyle \ lambda aa \, a}$
Naiwna redukcja η	${\ Displaystyle (\ lambda yy \, x) \, a}$	${\ Displaystyle \ lambda aa \, x}$

To niewłaściwe użycie redukcji η zmienia znaczenie, pozostawiając x w ${\ Displaystyle \ lambda yy \, x}$ niepodstawiony.