¿Cómo definir y-combinador sin “dejar que rec”?

Question

En casi todos los ejemplos, un Y-Combinator en lenguajes de tipo ML se escribe así:

let rec y f x = f (y f) x
let factorial = y (fun f -> function 0 -> 1 | n -> n * f(n - 1))

Este funciona como se espera, pero se siente como hacer trampa para definir la ordenada en el combinador usando let rec ....

Quiero definir este combinador sin utilizar la recursividad, usando la definición estándar:

Y = λf·(λx·f (x x)) (λx·f (x x))

Una traducción directa es la siguiente:

let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;

Sin embargo, F # se queja de que no puede averiguar los tipos:

  let y = fun f -> (fun x -> f (x x)) (fun x -> f (x x));;
  --------------------------------^

C:\Users\Juliet\AppData\Local\Temp\stdin(6,33): error FS0001: Type mismatch. Expecting a
    'a    
but given a
    'a -> 'b    
The resulting type would be infinite when unifying ''a' and ''a -> 'b'

¿Cómo se escribe la ordenada en el combinador en Fa # sin utilizar let rec ...?

Answer 1

A medida que los puntos fuera del compilador, no hay un tipo que se puede asignar a x de modo que la expresión (x x) está bien escrito-(esto no es estrictamente cierto, se puede escribir de forma explícita como x obj->_ - ver mi último párrafo). Puede solucionar este problema al declarar un tipo recursivo para que una expresión muy similar funcionará:

type 'a Rec = Rec of ('a Rec -> 'a)

Ahora el Y-combinador puede ser escrito como:

let y f =
  let f' (Rec x as rx) = f (x rx)
  f' (Rec f')

Desafortunadamente, usted encontrará que esto no es muy útil porque F # es un lenguaje estricto, por lo que cualquier función que se intenta definir el uso de este combinador provocará un desbordamiento de pila. En su lugar, es necesario utilizar la versión de orden aplicativo de la Y-Combinator (\f.(\x.f(\y.(x x)y))(\x.f(\y.(x x)y))):

let y f =
  let f' (Rec x as rx) = f (fun y -> x rx y)
  f' (Rec f')

Otra opción sería utilizar pereza explícito para definir el orden normal de Y-combinador:

type 'a Rec = Rec of ('a Rec -> 'a Lazy)
let y f =
  let f' (Rec x as rx) = lazy f (x rx)
  (f' (Rec f')).Value

Esto tiene la desventaja de que las definiciones de funciones recursivas ahora necesitan una fuerza explícita del valor perezoso (utilizando la propiedad Value):

let factorial = y (fun f -> function | 0 -> 1 | n -> n * (f.Value (n - 1)))

Sin embargo, tiene la ventaja de que se pueden definir los valores no recursivas de función, como ya se podía en un lenguaje vago:

let ones = y (fun ones -> LazyList.consf 1 (fun () -> ones.Value))

Como última alternativa, se puede tratar de una mejor aproximación al cálculo lambda sin tipo mediante el uso de boxeo y downcasting. Esto le daría (de nuevo utilizando la versión de orden aplicativo de la Y-Combinator):

let y f =
  let f' (x:obj -> _) = f (fun y -> x x y)
  f' (fun x -> f' (x :?> _))

Esto tiene el inconveniente obvio que hará que el boxeo no sean necesarios y unboxing, pero al menos esto es totalmente interna a la aplicación y en realidad nunca conducir a un fallo en tiempo de ejecución.

Answer 2

Yo diría que es imposible, y le preguntó por qué, me HandWave e invocar el hecho de que simplemente mecanografiado cálculo lambda tiene la normalización propiedad . En resumen, todos los términos del simplemente con tipo lambda cálculo terminar (por consiguiente, Y no puede ser definido en el cálculo lambda simplemente mecanografiado).

sistema de tipo F # 's no es exactamente el tipo de sistema de cálculo lambda simplemente mecanografiado, pero es lo suficientemente cerca. F # sin let rec viene realmente cerca del cálculo lambda simplemente mecanografiado - y, para reiterar, en la que el lenguaje no se puede definir un término que no pongan fin, y que excluye que definen Y también.

En otras palabras, en Fa #, "permiten rec" tiene que ser un lenguaje primitivo, por lo menos, porque incluso si fueron capaces de definirlo de las otras primitivas, que no sería capaz de escribir esta definición. Tenerlo como una primitiva que permite, entre otras cosas, para dar un tipo especial a la primitiva.

Editar: muestra KVB en su respuesta que las definiciones de tipo (una de las características ausentes de la lambda-cálculo simplemente mecanografiado, pero presente en let-rec-F # menor) permiten obtener algún tipo de recursividad. Muy inteligente.

Answer 3

Caso y dejar que las declaraciones en derivados de ML son lo que hace que sea Turing completo, creo que están basadas en System F y no se escriben de forma sencilla pero el punto es el mismo.

Sistema F no puede encontrar un tipo para el combinador cualquier punto fijo, si se pudiera, no era fuertemente normalizando.

¿Qué significa fuerte de la normalización es que cualquier expresión tiene exactamente un forma normal, en una forma normal es una expresión que no se puede reducir más lejos, esto difiere de sin tipo en el que cada expresión tiene a max una forma normal, sino que también puede no tener forma normal en absoluto.

Si mecanografiada lambda cálculos podrían construir un operador de punto fijo en lo que sea la forma, era muy posible que una expresión que no tienen forma normal.

Otro teorema famoso, el problema de la parada, implica que los lenguajes fuertemente de la normalización no se Turing completo, se dice que es imposible deciden (diferente a probar) de un lenguaje Turing completo lo subconjunto de sus programas se detener en lo que de entrada. Si es un lenguaje fuertemente normalización, es decidible si se detiene, es decir, que siempre se detiene. Nuestro algoritmo para decidir este es el programa:. true;

Para resolver esto, ML-derivados se extienden Sistema-F con el caso y dejar que (REC) para superar esto. Las funciones de este modo pueden referirse a sí mismos en sus definiciones de nuevo, por lo que, en efecto, no hay cálculos lambda en absoluto nada más, ya no es posible confiar en funciones anónimas sola para todas las funciones computables. Pueden por lo tanto una vez más entrar en bucles infinitos y recuperar su Turing-completo.

Answer 4

Respuesta corta:. No se puede

Respuesta larga: El cálculo lambda simplemente mecanografiado es fuertemente normalizando. Esto significa que no de Turing equivalente. La razón de esto se reduce básicamente al hecho de que un combinador Y debe ser bien definido de forma recursiva primitiva o (como has encontrado). Simplemente no se puede expresar en System F (o más simple cálculos escrita a máquina). No hay forma de evitar esto (se ha demostrado, después de todo). El combinador Y que puede en práctica funciona exactamente de la forma que desee, sin embargo.

Yo sugeriría intenta esquema si quieres un verdadero combinador Iglesia en forma de Y. Utilice la versión aplicativo dado anteriormente, como otras versiones no funcionará, a menos que agregue de forma explícita la pereza, o utilizar un intérprete de Scheme perezoso. (Esquema técnicamente no es completamente sin tipo, pero ha de tipos dinámicos, que es lo suficientemente bueno para esto.)

Ver esto por la prueba de la fuerte normalización: http://citeseerx.ist.psu.edu/viewdoc/summary ? doi = 10.1.1.127.1794

Después de pensar un poco más, estoy bastante seguro de que la adición de una primitiva combinador Y que se comporta exactamente de la forma en que el letrec define uno hace hace System F Turing completo. Todo lo que necesita hacer para simular una máquina de Turing es, pues, aplicar la cinta como un entero (interpretado en binario) y un cambio (en la posición de la cabeza).