Eta expansión en el patrón cálculo lambda

12

Klop, van Oostrom y de Vrijer tienen un documento sobre el cálculo lambda con patrones.

http://www.sciencedirect.com/science/article/pii/S0304397508000571

En cierto sentido, un patrón es un árbol de variables, aunque solo lo estoy considerando como una tupla anidada de variables, por ejemplo, ((x, y), z), (t, s)).

En el documento mostraron que si los patrones son lineales, en el sentido de que no se repite ninguna variable en un patrón, entonces la regla

(\p . m) n = m [n/p]

donde p es un patrón variable yn es una tupla de términos con exactamente la misma forma que p, es confluente.

Tengo curiosidad por saber si hay desarrollos similares en la literatura para el cálculo lambda con patrones y la regla eta adicional (expansión, reducción o simplemente igualdad).

En particular, por eta, quiero decir 

m = \lambda p . m p

Más directamente, tengo curiosidad por saber qué propiedades tendría un cálculo lambda. Por ejemplo, ¿es confluente?

Obliga a cerrar la categoría de clasificación porque obliga a la propiedad que

m p = n p implies m = n

Al usar la regla \ xi en el medio. ¿Pero tal vez algo podría salir mal?

type-theory lambda-calculus typed-lambda-calculus extensionality Jonathan Gallagher
fuente
¿Puedes escribir poner qué regla eta quieres decir? A menos que sea muy extraño, deberías poder codificarlo usando sumas y hacer un argumento de simulación.
Max New
2
@MaxNew: parece que está preguntando sobre el cálculo sin tipo. Todo lo relacionado con los patrones funciona perfectamente con los tipos (sugiero modestamente mi propio Focusing on Pattern Matching ), pero el cálculo lambda sin tipo es lo suficientemente diferente del LC escrito (especialmente wrt eta) que no me atrevo a responder sin hacer las pruebas .
Neel Krishnaswami
@MaxNew: ¿Qué implicaría la codificación por sumas?
Jonathan Gallagher
@NeelKrishnaswami: Estoy realmente interesado en ambos. Creo que estoy nervioso por tener variables de un tipo de producto junto con la regla eta. Creo que esto se hace, por ejemplo, dicosmo.org/Articles/JFP96.pdf . Pero si me equivoco, corrígeme. Entonces tienes igualdades como \ lambda x .mx = m = \ lambda (p, q). m (p, q), por ejemplo. ¡Gracias por el enlace a tu artículo!
Jonathan Gallagher

Respuestas:

7

Esta no es una respuesta completa; Es un comentario que se hizo demasiado grande.

Si extiende el cálculo lambda mecanografiado con productos con eliminadores proyectivos (es decir, eliminadores de productos fst(e)y snd(e)), básicamente no hay problemas de ningún tipo. La razón por la que tardó tanto en darse cuenta es porque resulta más natural hacer expansiones eta que reducciones eta . Vea Las virtudes de la expansión Eta de Barry Jay .

Si desea que los productos tengan un eliminador de estilo de patrón 

let (a,b) = e in t

Entonces las cosas son más complejas. La principal dificultad con la coincidencia de patrones son las conversiones de conmutación . Es decir, estos cálculos tienen la ecuación

C[let (a,b) = e in t] === let (a,b) = e in C[t]

y averiguar (a) qué contexto C[-]usar y (b) cómo orientar esta ecuación se vuelve complicado. En mi opinión, el estado del arte para los enfoques de estilo de reescritura son la reescritura extensiva con sumas de Sam Lindley y la equivalencia decisiva con sumas y el tipo vacío de Gabriel Scherer , que consideran el cálculo lambda mecanografiado con productos y sumas.

Neel Krishnaswami
fuente