Rachunek Lambda: różnica między kontekstami a kontekstami oceny

Po pierwsze, chciałbym powiedzieć, że mój tekst poniżej może zawierać błędy, więc możesz wskazać wszelkie błędy w moim sformułowaniu pytania.

Rozważ niepoprawny rachunek lambda z wartościami logicznymi i instrukcjami if, których warunki są podane przez tę składnię:

 t ::= v | t t | if t t t | x
 v ::= \x.t | #t | #f

Konteksty C w tym przypadku byłyby podane zgodnie z następującą składnią:

C ::= [-] | \x. C | C t | t C | if C t t | if t C t | if t t C 

Dodatkowo można zdefiniować konteksty oceny E zgodnie z inną składnią:

E ::= [-] | \x. E | v E | E t | if E t t 

Podzieliłem moje pytanie na trzy podpunkty, którymi chciałbym się zająć.

1. Kiedy stosuje się te dwa pojęcia? Wiem na przykład, że konteksty oceny są używane do definiowania semantyki rachunku różniczkowego, ale użycie kontekstów wciąż mi umyka. Chciałbym też trochę potwierdzić moją wiedzę tutaj.
2. Kiedy należy preferować jedno i dlaczego?
3. Czy możesz wskazać odpowiednie artykuły, które mogą pomóc mi w rozwiązaniu tej kwestii?

Kontekst jest wykorzystywany do wielu celów, ale zwykle do definiowania zgodności programów. Konteksty oceny są podzbiorem kontekstów. Są zwykle używane do definiowania relacji redukcji. Podam przykład każdego z nich.

Jednym z formalnych sposobów definiowania równości programu jest stwierdzenie, że dwa programy i N są kontekstowo równe i mogą się wzajemnie zastępować w każdym kontekście bez zmiany zachowania. Można to określić w następujący sposób: M i N są kontekstowo równe dostępne dla wszystkich sytuacjach końcowych C [ ⋅ ] o M i N : C, [ M ] ⇓ T tylko wtedy, gdy C [ N ] ⇓ T . Mówimy, że dla M , N kontekst się kończy$M$$N$$M$$N$$C[\cdot]$$M$$N$$C[M] \Downarrow t$$C[N] \Downarrow t$$M, N$jeśli ani ani C [ N ] nie mają wolnych zmiennych. EXPRESSION M ⇓ t oznacza, że program M zmniejsza się skończoną liczbę kroków do wartości ti . (Nawiasem mówiąc, należy zauważyć, że definicja równoważności kontekstowej jest bardziej zaangażowana w przypadku bogatych pojęć obliczeniowych, np. Równoległych procesów).$C[M]$$C[N]$$M \Downarrow t$$M$$t$

$$\frac{M \rightarrow N}{E[M] \rightarrow E[N]}$$ $\lambda$$\lambda$$M \rightarrow N$$\lambda x.M \rightarrow \lambda x.N$$\lambda$Zrewidowany raport na temat syntaktycznych teorii kontroli sekwencyjnej i stanu autorstwa Felleisen i Hieb.

$[]$

$$C ::= [] \mid x \mid t \, C \mid C \, t \mid \lambda x.C$$

$C[]$$t$$C[t]$$t$$[]$$C[t]$$[]$$t$

$$(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}$$ $M \{x\leftarrow N\}$$x \mapsto N$$M$

$t$$M$$N$$x$$t = (\lambda x. M) \, N$$t$$t'$$t' = (\lambda x. M) \, N$$t$$C$$M$$N$$x$$t = C[(\lambda x. M) \, N]$$C[M \{x\leftarrow N\}]$

$$\dfrac{}{(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}} (\beta) \qquad \dfrac{M \to_\beta N}{C[M] \to_\beta C[N]} (\gamma)$$ $$\dfrac{}{(\lambda x. M) \, N \to_\beta M \{x\leftarrow N\}} (\beta) \\ \dfrac{M \to_\beta N}{\lambda x. M \to_\beta \lambda x. N} (C_\lambda) \qquad \dfrac{M \to_\beta N}{M \, P \to_\beta N \, P} (C_{@\lt}) \qquad \dfrac{M \to_\beta N}{P \, M \to_\beta P \, N} (C_{@\gt})$$

Ta definicja daje redukcję beta, tzn. Pojęcie oceny, które pozwala na ograniczenie dowolnego okresu. Obliczenia wykonywane w językach programowania często nie pozwalają na ograniczenie subtermów w funkcjach: reguła redukcji może być zastosowana tylko na najwyższym poziomie, lub po lewej lub prawej stronie aplikacji. Możemy to wyrazić, definiując nowy rodzaj kontekstu, który nie zezwala na wszystkie formy składniowe: Możemy użyć tej składni do zdefiniowania pojęcia semantycznego bez oceny częściowej: Możemy również przedstawić tę definicję, rozszerzając ją, tak jak to zrobiliśmy powyżej dla pełnej redukcji wersji beta:

$$D ::= [] \mid x \mid t \, D \mid D \, t$$ $$\dfrac{}{(\lambda x. M) \, N \to_{np} M \{x\leftarrow N\}} \qquad \dfrac{M \to_{np} N}{D[M] \to_{np} D[N]}$$ $$\dfrac{}{(\lambda x. M) \, N \to_{np} M \{x\leftarrow N\}} (\beta) \\ \dfrac{M \to_{np} N}{M \, P \to_{np} N \, P} (C_{@\lt}) \qquad \dfrac{M \to_{np} N}{P \, M \to_{np} P \, N} (C_{@\gt})$$ $D$ byłby nazywany kontekstem oceny, ponieważ służy do zdefiniowania pojęcia oceny. Kontekst oceny nie jest szczególnym rodzajem kontekstu; raczej, nazywając ją kontekst oceny jest to kwestia tego, co służy do kontekstu .

Podam jeszcze jeden przykład kontekstu. Zdefiniujmy wartości zgodnie z następującą składnią: Teraz zdefiniujmy inny rodzaj kontekstów: W porównaniu z powyżej, dziura może znajdować się po stronie funkcji aplikacji, jeśli argumentem aplikacji jest wartość. Zdefiniuj zatem następujące pojęcie redukcji: $V$

$$V ::= x V_1 \ldots V_n \mid \lambda x. M$$ $$E ::= [] \mid M \, E \mid E \, V$$ $D$ $$\dfrac{}{(\lambda x. M) \, V \to_{cbva} M \{x\leftarrow V\}} (\beta_{cbva}) \qquad \dfrac{M \to_\beta N}{E[M] \to_{cbva} E[N]} (\gamma_{cbva})$$ Z zastrzeżeniem, że argument funkcji musi być wartością w pierwszej regule i że abstrakcje lambda nie są kontekstami, definiujemy strategię oceny call-by-value. Przy dalszym ograniczeniu, że argument jest oceniany przed funkcją, jest to wywołanie kolejności aplikacji według wartości.