6 votos

En los sistemas de cableado ¿las definiciones crean nuevas leyes de reescritura o un alias? ¿Y esta es una pregunta significativa?

Cálculo Lambda es a menudo presentado como una reescritura o la sustitución del sistema. Donde $\beta$ de reducción se describe como la sustitución de las variables vinculadas con el valor que la variable que está enlazado. Por ejemplo, $(\lambda x. x) y \rightarrow y$ se describe como la sustitución de todas las instancias de "x" en la expresión con y.

Ahora las extensiones de cálculo lambda (tales como Martin-Lof tipo de teoría) a menudo permiten la creación de definiciones, por ejemplo: $$\text{id} := \lambda x .x$$

Mi pregunta es la siguiente. ¿Esta definición crear una nueva regla de reescritura que dice cuando nos encontramos con "id" reescribir/sustituto "$\lambda x.x$" o estado "de identificación" y "$\lambda x.x$" representan el mismo subyacente de referencia?

Es la distinción que estoy haciendo incluso significante?

2voto

Luca Bressan Puntos 1647

La distinción que están haciendo puede ser útil y se utiliza realmente en alguna prueba asistentes.

Hay muchas posibles reglas de reescritura en el lambda-cálculo, entre los que se destacan $\alpha$-conversión, $\beta$-reducción y $\eta$-conversión. La fundamental relación de equivalencia entre los términos es sintáctica igualdad de $\equiv$, que en general es definido de manera que contenga $\alpha$-conversión. Pero también hay otras las relaciones de equivalencia que identificar los términos que hasta la aplicación repetida de $\beta$-reducción y/o $\eta$-conversión.

Por ejemplo, intensional igualdad de $=_\beta$ entre los términos se define por las reglas: $$\frac {M \to_\beta N} {M =_\beta N} \qquad \frac {M \equiv N} {M =_\beta N} \qquad \frac {M =_\beta N} {N =_\beta M} \qquad \frac {L =_\beta M \quad M =_\beta N} {L =_\beta N}$$ que en conjunto expresan el hecho de que $=_\beta$ es reflexiva, simétrica y transitiva cierre de $\to_\beta$.

Extensional igualdad de $=_{\beta\eta}$ es otra relación entre los términos, definidos por las normas: $$\frac {M \to_\beta N} {M =_{\beta\eta} N} \qquad \frac {M \to_\eta N} {M =_{\beta\eta} N} \qquad \frac {M \equiv N} {M =_{\beta\eta} N} \qquad \frac {M =_{\beta\eta} N} {N =_{\beta\eta} M} \qquad \frac {L =_{\beta\eta} M \quad M =_{\beta\eta} N} {L =_{\beta\eta} N}$$

Así que, cuando decimos que dos términos son "el mismo" o "igual", es necesario especificar si estamos hablando de la igualdad sintáctica, intensional igualdad o extensional de la igualdad.

En su caso, lo que usted llama "la creación de definiciones" puede ser visto como una extensión de igualdad sintáctica de las reglas, tales como $$\mathsf {id} \equiv \lambda x. x$$ o como darle la introducción de reglas para otra regla de reescritura que se conoce a veces como $\delta$-conversión. Uno de tales normas podrían ser $$\mathsf {id}\, M \to_\delta M$$ que moralmente refleja el hecho de que $\mathsf {id}$ es la identidad. En este caso, podríamos definir de nuevo las relaciones de equivalencia $=_{\beta\delta}$$=_{\beta\delta\eta}$, al igual que antes, pero, respectivamente, de las reglas adicionales $$\frac {M \to_\delta N} {M =_{\beta\delta} N} \qquad \frac {M \to_\delta N} {M =_{\beta\delta\eta} N}$$

La elección depende de lo que queremos hacer. La mayoría de las veces no tratamos $\mathsf {id}$ como un acceso directo para $\lambda x. x$, de manera que podamos elegir a considerar sintácticamente equivalentes. Pero, en algunos contextos, tiene sentido considerar también la posibilidad de $\delta$conversión: por ejemplo, en Coq el llamado "desarrollo de transparente constantes", que esencialmente corresponde a $\to_\delta$, permite volver a escribir una nueva constante sólo cuando tiene sentido hacerlo.

Observación. Hay razones por las que es preferible tener un $\mathsf{id} \, M \to_\delta M$ en lugar de $\mathsf{id} \to_\delta \lambda x. x$, ver Taroccoesbrocco los comentarios de abajo.

1voto

Taroccoesbrocco Puntos 427

La vista estándar es que el "id" y "$\lambda x.x$" representan el mismo subyacente de referencia. Más precisamente, "id" es sólo una abreviatura (una macro, un alias) para el $\lambda$plazo "$\lambda x.x$". Y lo mismo para otras definiciones de este tipo.

La adición de nuevas reglas de reescritura para cualquier nueva definición no sólo iba a complicar inútilmente la reescritura sistema, sino que también alteran$-$y empeorar sin motivo aparente,$-$algunos tipos de investigaciones, tales como el análisis de la complejidad (que se basa en contar el número de reducción de pasos para llegar a la forma normal; es un tema interesante en la teoría de lenguajes de programación de una aplicación de punto de vista).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X