Beta normalna postać - Beta normal form

W rachunku lambda termin ma postać normalnej beta, jeśli nie jest możliwa redukcja beta . Termin jest w normalnej postaci beta-eta, jeśli ani redukcja beta, ani redukcja eta nie są możliwe. Termin jest w normalnej formie głowy, jeśli nie ma beta-redex w pozycji głowy .

Redukcja beta

W rachunku lambda redex beta jest terminem o postaci:

${\ Displaystyle (\ mathbf {\ lambda} xA) M}$ .

Redex znajduje się na pozycji nagłówka w terminie , jeśli ma następujący kształt (zwróć uwagę, że aplikacja ma wyższy priorytet niż abstrakcja, a poniższy wzór ma być abstrakcją lambda, a nie aplikacją): ${\ displaystyle r}$${\ displaystyle t}$${\ displaystyle t}$

${\ Displaystyle \ lambda x_ {1} \ ldots \ lambda x_ {n}. \ underbrace {(\ lambda xA) M_ {1}} _ {{\ tekst {redex}} r} M_ {2} \ ldots M_ {m}}$ , gdzie i . ${\ displaystyle n \ geq 0}$${\ displaystyle m \ geq 1}$

Redukcji beta jest zastosowanie następującej reguły przepisywania do Redex beta zawartym w cyklu:

${\ Displaystyle (\ mathbf {\ lambda} xA) M \ longrightarrow A [x: = M]}$

gdzie jest wynikiem zastąpienia terminu zmienną w terminie . ${\ Displaystyle A [x: = M]}$${\ displaystyle M}$${\ displaystyle x}$${\ displaystyle A}$

Głowica redukcji beta redukcji beta stosowane w pozycji głowicy, to znaczy w postaci:

${\ 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}}$ , gdzie i . ${\ displaystyle n \ geq 0}$${\ displaystyle m \ geq 1}$

Każda inna redukcja jest wewnętrzną redukcją beta.

Postaci normalnej to określenie, które nie zawierają żadnych Redex beta, to znaczy , że nie może być dalej zmniejszony. Głowica normalnie tworzą to określenie, które nie zawierają Redex beta głowicami, czyli że nie może być dalej obniżona poprzez zmniejszenie głowicy. Rozważając prosty rachunek lambda (tj. Bez dodawania symboli stałych lub funkcji, które mają być zredukowane przez dodatkową regułę delta), formami normalnymi głowy są wyrazy o następującym kształcie:

${\ Displaystyle \ lambda x_ {1} \ ldots \ lambda x_ {n} .xM_ {1} M_ {2} \ ldots M_ {m.}}$ , gdzie jest zmienną i . ${\ displaystyle x}$${\ displaystyle n \ geq 0}$${\ Displaystyle m \ geq 0}$

Forma normalna głowy nie zawsze jest formą normalną, ponieważ zastosowane argumenty nie muszą być normalne. Jednak odwrotna sytuacja jest prawdą: każda normalna forma jest również formą normalną głowy. W rzeczywistości formy normalne są dokładnie formami normalnymi głowy, w których podteksty same są formami normalnymi. Daje to indukcyjny syntaktyczny opis form normalnych. ${\ displaystyle M_ {j}}$${\ displaystyle M_ {j}}$

Istnieje również pojęcie postaci normalnej o słabej głowie : termin w postaci normalnej o słabej głowie jest albo terminem w postaci normalnej głowy, albo abstrakcją lambda. Oznacza to, że w ciele lambda może pojawić się redex.

Strategie redukcyjne

Ogólnie rzecz biorąc, dany termin może zawierać kilka zmian redex, dlatego można zastosować kilka różnych redukcji współczynnika beta. Możemy określić strategię, aby wybrać redex do redukcji.

• Normalna redukcja to strategia, w której stale stosuje się zasadę redukcji beta pozycji głowy, dopóki takie redukcje nie są już możliwe. W tym momencie wynikowy termin jest w formie głowy normalnej. Następnie kontynuuje się redukcję głowy w podrzędach , od lewej do prawej. Inaczej mówiąc, redukcja w normalnym porządku jest strategią, która zawsze redukuje najpierw najbardziej wysunięty z lewej strony redex. ${\ displaystyle M_ {j}}$
• Z drugiej strony, w przypadku redukcji kolejności aplikacyjnej , najpierw stosuje się redukcje wewnętrzne, a następnie stosuje się zmniejszenie wysokości podnoszenia tylko wtedy, gdy nie są możliwe dalsze redukcje wewnętrzne.

Redukcja porządku normalnego jest zakończona, w tym sensie, że jeśli termin ma normalną postać głowy, to redukcja porządku normalnego ostatecznie ją osiągnie. Dzięki opisowi składniowemu form normalnych powyżej, pociąga to za sobą to samo stwierdzenie dla „w pełni” normalnej postaci (jest to twierdzenie o normalizacji ). Z kolei redukcja kolejności stosowania może nie zakończyć się, nawet jeśli termin ma normalną postać. Na przykład przy zastosowaniu redukcji zamówień aplikacyjnych możliwa jest następująca sekwencja obniżek:

${\ Displaystyle {\ rozpocząć {wyrównane} & (\ mathbf {\ lambda} xz) ((\ lambda w.www) (\ lambda w.www)) \\\ rightarrow & (\ 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) (\ lambda w.www) (\ lambda w.www) (\ lambda w.www)) \\ & \ ldots \ end {aligned}}}$

Ale stosując redukcję normalnej kolejności, ten sam punkt początkowy szybko przechodzi do normalnej postaci:

${\ Displaystyle (\ mathbf {\ lambda} xz) ((\ lambda w.www) (\ lambda w.www))}$

${\ displaystyle \ rightarrow z}$

Ciągi reżyserskie Sinota to jedna z metod optymalizacji złożoności obliczeniowej redukcji beta.

Zobacz też

• Rachunek lambda
• Forma normalna (ujednoznacznienie)

Bibliografia