El problema de representar las variables ligadas en la sintaxis, y en particular el de la sustitución para evitar la captura, es bien conocido y tiene una serie de soluciones: variables nombradas con equivalencia alfa, índices de Bruijn, anonimato local, conjuntos nominales, etc.
Pero parece haber otro enfoque bastante obvio, que sin embargo no he visto usado en ningún lado. Es decir, en la sintaxis básica tenemos solo un término "variable", escrito say , y luego le damos por separado una función que asigna cada variable a una carpeta en cuyo ámbito se encuentra. Entonces, a -term likeλ
se escribiría , y la función asignaría la primera a la primera y la segunda a la segunda . Por lo tanto, es como los índices de Bruijn, solo que en lugar de tener que "contar s" a medida que retrocede del término para encontrar la carpeta correspondiente, solo evalúa una función. (Si representa esto como una estructura de datos en una implementación, pensaría en equipar cada objeto de término variable con un puntero / referencia simple al objeto de término de carpeta correspondiente).∙ λ ∙ λ λ
Obviamente, esto no es sensato para escribir la sintaxis en una página para que los humanos la lean, pero tampoco lo son los índices de Bruijn. Me parece que tiene un sentido matemático perfecto y, en particular, hace que la sustitución para evitar la captura sea muy fácil: simplemente deje caer el término que está sustituyendo y tome la unión de las funciones de enlace. Es cierto que no tiene una noción de "variable libre", pero (de nuevo) tampoco los índices de Bruijn realmente; en cualquier caso, un término que contiene variables libres se representa como un término con una lista de carpetas de "contexto" al frente.
¿Me estoy perdiendo algo y hay alguna razón por la cual esta representación no funciona? ¿Hay problemas que lo hacen mucho peor que los demás que no vale la pena considerar? (El único problema que se me ocurre en este momento es que el conjunto de términos (junto con sus funciones vinculantes) no está definido inductivamente, pero eso no parece insuperable). ¿O hay realmente lugares donde se ha utilizado?
fuente
Respuestas:
Las respuestas de Andrej y Łukasz hacen buenos puntos, pero quería agregar comentarios adicionales.
Para hacer eco de lo que dijo Damiano, esta forma de representar la unión usando punteros es la sugerida por las redes de prueba, pero el primer lugar donde lo vi para los términos lambda fue en un viejo ensayo de Knuth:
En la página 234, dibujó el siguiente diagrama (que llamó una "estructura de información") que representa el término :(λy.λz.yz)x
Este tipo de representación gráfica de los términos lambda también se estudió de forma independiente (y más profundamente) en dos tesis a principios de la década de 1970, tanto por Christopher Wadsworth (1971, Semántica y pragmática del cálculo lambda ) como por Richard Statman (1974, Complejidad estructural). de pruebas ). Hoy en día, estos diagramas a menudo se denominan "gráficos λ" (ver, por ejemplo, este documento ).
Observe que el término en el diagrama de Knuth es lineal , en el sentido de que cada variable libre o ligada ocurre exactamente una vez; como han mencionado otros, hay problemas y elecciones no triviales que se deben hacer al tratar de extender este tipo de representación a -términos lineales.
Por otro lado, para términos lineales, ¡creo que es genial! La linealidad excluye la necesidad de copiar, por lo que obtienes -equivalencia y sustitución "gratis". Estas son las mismas ventajas que HOAS, y en realidad estoy de acuerdo con Rodolphe Lepigre en que hay una conexión (si no exactamente una equivalencia) entre las dos formas de representación: hay un sentido en el que estas estructuras gráficas pueden interpretarse naturalmente como diagramas de cuerdas , que representa endomorfismos de un objeto reflexivo en una bicategoría cerrada compacta (di una breve explicación de eso aquí ).α
fuente
No estoy seguro de cómo se representaría su función de variable a carpeta y para qué propósito le gustaría usarla. Si está utilizando indicadores de retroceso, entonces, como Andrej señaló, la complejidad computacional de la sustitución no es mejor que el cambio de nombre alfa clásico.
De su comentario sobre la respuesta de Andrej, infiero que, hasta cierto punto, está interesado en compartir. Puedo proporcionar alguna entrada aquí.
En un cálculo lambda tipificado típico, el debilitamiento y la contracción, al contrario de otras reglas, no tienen sintaxis.
Agreguemos una sintaxis:
a b , cCb,ca(⋅) está 'usando' la variable y vinculando las variables . Me enteré de esa idea de una de las " Implementaciones netas de interacción de reducción cerrada " de Ian Mackie .a b,c
Con esa sintaxis, cada variable se usa exactamente dos veces, una donde está vinculada y otra donde se usa. Esto nos permite distanciarnos de una sintaxis particular y ver el término como un gráfico donde las variables y los términos son aristas.
Desde la complejidad algorítmica, ahora podemos usar punteros no de una variable a un aglutinante, sino de un aglutinante a una variable y tener sustituciones en un tiempo constante.
Además, esta reformulación nos permite rastrear el borrado, la copia y el intercambio con más fidelidad. Uno puede escribir reglas que copien (o borren) de forma incremental un término mientras comparten subterms. Hay muchas formas de hacer eso. En algunos entornos restringidos, las victorias son bastante sorprendentes .
Esto se está acercando a los temas de redes de interacción, combinadores de interacción, sustitución explícita, lógica lineal, evaluación óptima de Lamping, gráficos compartidos, lógicas ligeras y otros.
Todos estos temas son muy emocionantes para mí y con mucho gusto daría referencias más específicas, pero no estoy seguro de si algo de esto es útil para usted y cuáles son sus intereses.
fuente
Su estructura de datos funciona, pero no será más eficiente que otros enfoques porque necesita copiar todos los argumentos en cada reducción beta, y debe hacer tantas copias como apariciones de la variable enlazada. De esta manera sigues destruyendo el intercambio de memoria entre subterms. Combinado con el hecho de que está proponiendo una solución no pura que implica manipulaciones de puntero y, por lo tanto, es muy propensa a errores, probablemente no valga la pena.
¡Pero estaría encantado de ver un experimento! Puede tomarlo
lambda
e implementarlo con su estructura de datos (OCaml tiene punteros, se llaman referencias ). Más o menos, solo tienes que reemplazarsyntax.ml
ynorm.ml
con tus versiones. Eso es menos de 150 líneas de código.fuente
Otras respuestas son principalmente sobre temas de implementación. Ya que mencionas tu principal motivación para hacer pruebas matemáticas sin demasiada contabilidad, aquí está el problema principal que veo con eso.
Cuando dice "una función que asigna cada variable a una carpeta en cuyo ámbito se encuentra": ¡el tipo de salida de esta función es seguramente un poco más sutil que eso! Específicamente, la función debe tomar valores en algo como "los ligantes del término en consideración", es decir, un conjunto que varía según el término (y obviamente no es un subconjunto de un conjunto ambiental más grande de ninguna manera útil). Por lo tanto, en la sustitución, no puede simplemente "tomar la unión de las funciones de enlace": también tiene que reindexar sus valores, de acuerdo con algún mapa de carpetas en los términos originales a carpetas en el resultado de la sustitución.
Estas reindexaciones seguramente deberían ser "rutinarias", en el sentido de que razonablemente podrían ser barridas debajo de la alfombra, o bien empaquetadas en términos de algún tipo de funcionalidad o naturalidad. Pero lo mismo es cierto de la contabilidad involucrada en el trabajo con variables con nombre. Entonces, en general, me parece probable que haya al menos tanta contabilidad involucrada con este enfoque como con enfoques más estándar.
Sin embargo, aparte de esto, es un enfoque conceptual muy atractivo, y me encantaría verlo cuidadosamente elaborado. Me imagino que podría arrojar una luz diferente sobre algunos aspectos de la sintaxis que los enfoques estándar.
fuente
Lazy.t
En general, creo que es una representación genial, pero implica cierta contabilidad con punteros, para evitar romper enlaces vinculantes. Supongo que sería posible cambiar el código para usar campos mutables, pero la codificación en Coq sería menos directa. Todavía estoy convencido de que esto es muy similar a HOAS, aunque la estructura del puntero se hace explícita. Sin embargo, la presencia de
Lazy.t
implica que es posible que algún código sea evaluado en el momento equivocado. Este no es el caso en mi código, ya que solo puede ocurrir una sustitución de una variable con una variable a laforce
vez (y no una evaluación, por ejemplo).fuente