¿Derivación clara e intuitiva del combinador de punto fijo (combinador Y)?

cs.stackexchange https://cs.stackexchange.com/questions/9604

Pregunta

La solución del combinador de punto fijo (también conocido como el combinador y) en el cálculo lambda (sin typed) ($ lambda $) se define como:

FIJO $ triangleq lambda f. ( Lambda x. F ~ ( lambda y. X ~ x ~ y)) ~ ( lambda x. F ~ ( lambda y. X ~ x ~ y) $

Entiendo su propósito y puedo rastrear la ejecución de su aplicación perfectamente bien; Me gustaría entender cómo obtener la solución de los primeros principios.

Aquí hay lo que yo llego cuando trato de derivarlo yo mismo:

  1. Fix es una función: corrige $ triangleq lambda_ ldots $
  2. Fix Toma otra función, $ f $, para que sea recursivo: arreglar $ triangleq lambda f ._ ldots $
  3. El primer argumento de la función $ F $ es el "nombre" de la función, utilizado donde se pretende una aplicación recursiva. Por lo tanto, todas las apariencias del primer argumento a $ f $ deben reemplazarse por una función, y esta función debe esperar el resto de los argumentos de $ f $ (supongamos que $ f $ toma un argumento): arreglar $ triangleq lambda f ._ ldots f ~ ( lambda y. _ ldots y) $

Aquí es donde no sé cómo "dar un paso" en mi razonamiento. Las elipses pequeñas indican dónde me falta algo (aunque solo puedo saber eso al compararlo con la solución "real").

Ya he leído Tipos y lenguajes de programación, que no intenta derivarlo directamente, y en su lugar se refiere al lector a El pequeño esquema para una derivación. También he leído eso, y su "derivación" no fue tan útil. Además, es menos una derivación directa y más uso de un ejemplo muy específico y un intento ad-hoc de escribir una función recursiva adecuada en $ lambda $.

¿Fue útil?

Solución

No he leído esto en ningún lado, pero así es como creo que $ y $ podría haberse derivado:

Tengamos una función recursiva $ f $, tal vez un factorial o cualquier otra cosa así. Informalmente, definimos $ f $ como término pseudo-lambda donde $ f $ ocurre en su propia definición:

$$ f = ldots f ldots f ldots $$

Primero, nos damos cuenta de que la llamada recursiva se puede tener en cuenta como un parámetro:

$$ f = subbacial {( lambda r. ( ldots r ldots r ldots))} _ {m} f $$

Ahora podríamos definir $ F $ si solo tuviéramos una manera de aprobarlo como argumento para sí mismo. Esto no es posible, por supuesto, porque no tenemos $ F $ a mano. Lo que tenemos a mano es $ M $. Dado que $ M $ contiene todo lo que necesitamos para definir $ F $, podemos intentar pasar $ M $ como argumento en lugar de $ F $ e intentar reconstruir $ F $ más adelante. Nuestro primer intento se ve así:

$$ f = subbacace {( lambda r. ( ldots r ldots r ldots))} _ {m} subbacace {( lambda r. ( ldots r ldots r ldots))} _ { M} $$

Sin embargo, esto no es completamente correcto. Antes, $ F $ se sustituyó por $ R $ dentro de $ M $. Pero ahora pasamos $ M $ en su lugar. Tenemos que arreglar de alguna manera todos los lugares donde usamos $ R $ para que reconstruyan $ F $ de $ M $. En realidad, esto no es difícil en absoluto: ahora que sabemos que $ F = mm $, en todas partes usamos $ R $, simplemente lo reemplazamos por $ (RR) $.

$$ f = subbacace {( lambda r. ( ldots (rr) ldots (rr) ldots))} _ {m '} subbacace {( lambda r. ( ldots (rr) ldots ( rr) ldots))} _ {m '} $$

Esta solución es buena, pero tuvimos que alterar $ M $ adentro. Esto no es muy conveniente. Podemos hacer esto más elegantemente sin tener que modificar $ M $ presentando otro $ lambda $ que envía a $ M $ su argumento se aplica a sí mismo: expresando $ M '$ como $ lambda xm (xx) $ obtenemos

$$ f = ( lambda x. subbrase {( lambda r. ( ldots r ldots r ldots))} _ {m} (xx)) ( lambda x. Undbace {( lambda r. ( ldots r ldots r ldots))} _ {m} (xx)) $$

De esta manera, cuando $ m $ se sustituye por $ x $, $ mm $ se sustituye por $ r $, que es por definición igual a $ f $. ¡Esto nos da una definición no recursiva de $ F $, expresada como un término lambda válido!

La transición a $ y $ ahora es fácil. Podemos tomar un término lambda arbitrario en lugar de $ m $ y realizar este procedimiento en él. Para que podamos factorizar $ m $ out y definir

$$ y = lambda m. ( lambda x. m (xx)) ( lambda xm (xx)) $$

De hecho, $ ym $ se reduce a $ f $ a medida que lo definimos.

Nota: He derivado $ y $ como se define en la literatura. El combinador que ha descrito es una variante de $ y $ para llamado por valor Los idiomas, a veces también llamados $ Z $. Ver Este artículo de Wikipedia.

Otros consejos

Como Yuval ha señalado, no hay solo un operador de punto fijo. Hay muchos de ellos. En otras palabras, la ecuación para el teorema de punto fijo no tiene una sola respuesta. Entonces no puedes derivar el operador de ellos.

Es como preguntar cómo las personas derivan $ (x, y) = (0,0) $ como solución por $ x = y $. ¡No lo hacen! La ecuación no tiene una solución única.

En caso de que lo que quiere saber es cómo se descubrió el primer teorema de punto fijo. Permítanme decir que también me preguntaba cómo se les ocurrió los teoremas de punto fijo/recursión cuando los vi por primera vez. Parece tan ingenioso. Particularmente en la forma de la teoría de la computabilidad. A diferencia de lo que Yuval dice que no es el caso que las personas jugaran hasta que encontraron algo. Esto es lo que he encontrado:

Hasta donde recuerdo, el teorema se debe originalmente a SC Kleene. A Kleene se le ocurrió el teorema original de punto fijo al salvar la prueba de inconsistencia del cálculo Lambda original de la Iglesia. El cálculo de lambda original de la iglesia sufría una paradoja tipo Russel. El cálculo de lambda modificado evitó el problema. Kleene estudió la prueba de inconsistencia probablemente para ver cómo si el cálculo de lambda modificado sufriera un problema similar y convirtió la prueba de inconsistencia en un teorema útil en el cálculo de lambda modificado. A través de su trabajo con respecto a la equivalencia del cálculo de Lambada con otros modelos de cálculo (máquinas de Turing, funciones recursivas, etc.) lo transfirió a otros modelos de cálculo.

¿Cómo derivar el operador que podría preguntar? Así es como lo tengo en cuenta. El teorema de punto fijo se trata de eliminar la autorreferencia.

Todos conocen la paradoja de mentiroso:

Soy una guarida.

O en la forma más lingüística:

Esta oración es falsa.

Ahora la mayoría de la gente piensa que el problema con esta oración es con la autorreferencia. ¡No lo es! La autorreferencia se puede eliminar (el problema es con la verdad, un idioma no puede hablar de la verdad de sus propias oraciones en general, ver Indefinabilidad de Tarski del teorema de la verdad). La forma donde se elimina la autorreferencia es la siguiente:

Si escribe la siguiente cotización dos veces, la segunda vez dentro de las citas, la oración resultante es falsa: "Si escribe la siguiente cotización dos veces, la segunda vez dentro de las citas, la oración resultante es falsa:"

Sin autorreferencia, tenemos instrucciones sobre cómo construir una oración y luego hacer algo con ella. Y la oración que se construye es igual a las instrucciones. Tenga en cuenta que en $ lambda $ -calculus no necesitamos citas porque no hay distinción entre datos e instrucciones.

Ahora, si analizamos esto, tenemos $ mm $ donde $ mx $ es las instrucciones para construir $ xx $ y hacerle algo.

$ Mx = f (xx) $

Entonces $ M $ es $ lambda x. f (xx) $ y tenemos

$ Mm = ( lambda x. F (xx)) ( lambda x. F (xx)) $

Esto es por un $ F $ fijo. Si desea convertirlo en un operador, solo agregamos $ lambda f $ y obtenemos $ y $:

$ Y = lambda f. (Mm) = lambda f. (( Lambda x. F (xx)) ( lambda x. F (xx))) $

Así que tengo en cuenta la paradoja sin autorreferencia y eso me ayuda a entender de qué se trata $ Y $.

Por lo tanto, debe definir un combinador de punto fijo

fix f = f (fix f)
      = f (f (fix f))
      = f (f (f ... ))

pero sin recursión explícita. Comencemos con el combinador irreducible más simple

omega = (\x. x x) (\x. x x)
      = (\x. x x) (\x. x x)
      = ...

los x En el primer lambda se sustituye repetidamente por la segunda lambda. La conversión alfa simple deja este proceso más claro:

omega =  (\x. x x) (\x. x x)
      =α (\x. x x) (\y. y y)
      =β (\y. y y) (\y. y y)
      =α (\y. y y) (\z. z z)
      =β (\z. z z) (\z. z z)

Es decir, la variable en la primera lambda siempre desaparece. Entonces, si agregamos un f al primer lambda

(\x. f (x x)) (\y. y y)

la f Bobirá

f ((\y. y y) (\y. y y))

Tenemos nuestro omega espalda. Debería estar claro ahora, que si agregamos un f al segundo lambda, luego el f aparecerá en el primer lambda y luego se moverá:

Y f = (\x. x x)     (\x. f (x x))
      (\x. f (x x)) (\x. f (x x)) -- the classical definition of Y

Ya que 

(\x. s t) z = s ((\x. t) z), if `x' doesn't occur free in `s'

Podemos reescribir la expresión como

f ((\x. x x) (\x. f (x x))

Que es solo

f (Y f)

y tenemos nuestra ecuación Y f = f (Y f). Entonces el Y El combinador es esencialmente

  1. duplicar el f
  2. hacer el primero f se balanceó
  3. repetir

Es posible que haya visto el ejemplo clásico de una ecuación sin una forma normal:

$$ ( lambda x.xx) ( lambda x.xx) triangleright ( lambda x.xx) ( lambda x.xx) $$

Una ecuación similar es sugerida por la de la recursión general:

$$ begin {array} {rr} & ( lambda xr (xx))) ( lambda xr (xx)) ~ triangleright & r (~ ( lambda xr (xx)) ( lambda xr (xx ) ~) triangleright & r (r (~ ( lambda xr (xx)) ( lambda xr (xx)) ~)) triangleright & dots end {array} tag {a} $$

(A) es una forma de escribir ecuaciones recursivas generales en el cálculo de lambda (más allá de la primitiva recursiva). Entonces, ¿cómo resuelve la ecuación $ yf = f (yf) $? Enchufe $ F $ en $ R $ en la ecuación anterior para obtener:

$$ yf = ( lambda xf (xx)) ( lambda xf (xx)) $$ $$ y = lambda f. ( Lambda xf (xx)) ( lambda xf (xx)) $$

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top