Cálculo de Lambda: ¿Cómo funcionan los contextos de evaluación?

En el cálculo lambda puro, tenemos el conjunto de términos inductivamente definidos (la gramática):

$$e::= x \mid \lambda x . e \mid e_1 e_2$$

Bajo la estrategia de evaluación llamada por valor, tenemos las reglas de inferencia para la reducción beta y las reglas sobre cómo evaluar las aplicaciones (reglas de congruencia). Estoy tratando de entender cómo los contextos de evaluación pueden reemplazar las reglas de congruencia sin cambiar realmente la sintaxis del lenguaje. Sin contextos de evaluación, tenemos lo siguiente:

$$\frac{e_1 \rightarrow e_1'}{e_1e_2 \rightarrow e_1'e_2}$$ y $$\frac{e_2 \rightarrow e_2'}{ve_2 \rightarrow ve_2'}.$$

Esto tiene sentido, ya que si tenemos una instancia de una expresión , está claro que es de la forma y por lo tanto$t = (\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w$$e_1e_2 \rightarrow e_1'e_2$

$$(\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w \rightarrow (\lambda f . \lambda x. f x)(\lambda z .z)\lambda w.w$$

Si reemplazamos las reglas de congruencia con contextos de evaluación: entonces solo necesitamos una sola regla para expresar las reglas de congruencia del lenguaje:

$$E::= [\cdot] \mid Ee \mid vE$$ $$\frac{e \rightarrow e'}{E[e] \rightarrow E[e']}.$$

Estoy confundido acerca de cómo los contextos de evaluación pueden decirnos cómo evaluar la expresión desde arriba sin cambiar la sintaxis del lenguaje. No entiendo cómo "funciona" el contexto de evaluación sin reescribir como$t$$t$

$$E_t = (\lambda f . \lambda x. f x)[\cdot]\lambda w.w$$

donde . No hay una razón obvia a priori para evaluar bajo llamada por valor sin conocimiento de . Realmente no tengo idea de dónde me estoy equivocando. ¿Alguien puede ayudar a corregir mi pensamiento?$t = E_t[((\lambda y .y)\lambda z .z)]$$t$$E_t$

La sutileza reside en dónde se hace la distinción entre lenguaje y metalenguaje. Como lo expresó René Magritte :

$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$ es un término lambda, escrito en la sintaxis para términos lambda. Llamemos a este término lambda . Sea el término lambda . Puedo escribir (y esto es una verdadera igualdad): todo lo que hice fue darle un nombre a un subterráneo. Si considera el lado derecho de esta igualdad " ", no está escrito en la sintaxis de los términos lambda; Está escrito en una notación matemática donde permitimos que una letra represente un término lambda.$t$$M$$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z))$$t = M \, (\lambda w.w)$$M \, (\lambda w.w)$

Cuando escribimos una regla como establece el siguiente axioma: para cualquier término lambda y y cualquier valor , si se reduce a luego reduce a . Aquí nuevamente estamos usando meta-notaciones (es decir, notaciones matemáticas para razonar sobre un lenguaje): la flecha para expresar la relación de reducción; metavariables donde una letra indica el tipo ( para términos lambda,

$$\frac{e_2 \to e_2'}{v \, e_2 \to v \, e_2'}$$ $e_2$$e_2'$$v$$e_2$$e_2'$$v \, e_2$$v \, e_2'$$\to$$e$$v$para valores) y subíndices y primos distinguen entre metavariables del mismo tipo; La notación de fracción para escribir un axioma inductivo.

Cuando escribimos la regla , nuevamente es una meta-notación, parte del metalenguaje y no del lambda sintaxis a largo plazo. La regla significa: para cualquier término lambda y y cualquier contexto de evaluación , si reduce a entonces reduce a .

$$\frac{e \to e'}{E[e] \to v E[e']}$$ $E[\cdot]$$e$$e'$$E[\cdot]$$e$$e'$$E[e]$$E[e']$

Si llamamos al contexto por el (meta-) nombre , entonces . De nuevo, esta es una igualdad entre dos términos lambda, es decir, el mismo término lambda está a ambos lados del signo igual. Lo que tenemos a la izquierda y a la derecha son dos meta-notaciones diferentes para el mismo término lambda : uno que usa un nombre que le dimos, otro que es un poco más complicado e involucra un contexto al que le dimos un nombre.$(\lambda f. \lambda x. f x)[\cdot] (\lambda w.w)$$E_t$$t = E_t[(\lambda y.y)(\lambda z.z)]$$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda z.z)) (\lambda w.w)$

Dado el término , ¿cómo encuentra cómo puede reducirse?$t$

• Con la notación utilizando múltiples reglas, debe encontrar un árbol de deducción (en general, aquí la derivación es lineal, por lo que simplemente tiene que encontrar una cadena que conduzca a un axioma).
• Con la notación que utiliza contextos de evaluación, debe encontrar un contexto de evaluación adecuado.

La gramática del contexto de evaluación sigue la estructura de las reglas de evaluación, por lo que estos no son realmente dos métodos, sino dos formas diferentes de expresar la misma definición.

Para comprender esto, recomiendo encarecidamente el siguiente ejercicio: en su idioma favorito, implemente la evaluación de llamada por valor de término lambda de una manera directa, con un tipo que represente términos lambda y una función que realice un paso de reducción.