Cálculo de construcciones: comprime la expresión a su forma más pequeña

11

Soy consciente de que el cálculo de construcciones se está normalizando fuertemente, lo que significa que cada expresión tiene una normalidad que no puede ser beta, eta-reducida aún más. De hecho, esta es la expresión más eficiente que calcula el mismo valor que la expresión original.

Pero en ciertos casos, la normalización puede reducir una pequeña expresión a una gran expresión (en términos de tamaño).

¿Hay una forma más pequeña de expresiones? Un formulario que calcula el mismo valor con el tamaño más pequeño.

En otras palabras, en lugar de una forma normal eficiente en el tiempo, una eficiente en el espacio.

lambda-calculus reductions typed-lambda-calculus normalization calculus-of-constructions usuario47376
fuente

8

$\lambda$

$n$ $\overline{n}$ $n$ $\mathtt{succ}$ $0$ $M$ $\lceil M \rceil$ $M$

$t, u : \mathtt{nat} \to \mathtt{nat}$ $t \simeq u$ $n \in \mathbb{N}$ $t \, \overline{n}$ $s \, \overline{n}$

$\mathtt{nat} \to \mathtt{nat}$

$S : \mathtt{nat} \times \mathtt{nat} \to \mathtt{nat}$ $n \in \mathbb{N}$ $M$ $S (\lceil M \rceil, \overline{n})$ $\overline{1}$ $T$ $n$ $\overline{0}$ $n$

$Z_1, \ldots, Z_k$ $\lambda x : \mathtt{nat} .\, 0$ $\lambda x : \mathtt{nat} .\, 0$ $\lambda x : \mathtt{nat} .\, 0$ $\lambda x : \mathtt{nat} .\, 0$

$M$

u : = λ x : n a t . S (⌈ M ⌉, x)

$u \mathbin{{:}{=}} \lambda x : \mathtt{nat} .\, S (\lceil M \rceil, x)$

M

$M$

u \bar{n}

$u \overline{n}$

\bar{0}

$\overline{0}$

n

$n$

λ x : n a t . 0

$\lambda x : \mathtt{nat} .\, 0$

M

$M$

u

$u$

Z_{1}, \dots, Z_{k}

$Z_1, \ldots, Z_k$

M

$M$

Z_{1}, \dots, Z_{k}

$Z_1, \ldots, Z_k$

$\beta$

Andrej Bauer
fuente

¿Cómo se calcula Z1, .. Zk?

user47376

No tienes que hacerlo Es decir, el algoritmo que estoy describiendo está disponible, y no sabemos con precisión qué es, pero eso es irrelevante. En realidad no estoy tratando de ejecutar el algoritmo, solo necesito su existencia para mostrar que su algoritmo no existe.

Andrej Bauer

Sí, pero su argumento dice que si mi algoritmo existe, podemos resolver el problema de detención. Para determinar si una máquina Turing M detiene su algoritmo, normaliza uy comprueba si es uno de Z1, .. Zk. Por lo tanto, debe poder enumerarlos; de lo contrario, es posible que no se detenga.

user47376

Z_{1}, \dots, Z_{k}

$Z_1,\ldots,Z_k$

k

$k$

Z

$Z$

k

$k$

Z [i]

$Z[i]$

7

(λ x : T . C x x) u \to_{β} C u u

$(\lambda x:T.C\ x\ x)\ u\rightarrow_\beta C\ u\ u$

u

$u$

En este sentido, se sabe cómo reducir los términos sin tipo de una manera óptima, reduciendo el intercambio lo más posible. Esto se explica aquí: /programming//a/41737550/2059388 y la cita relevante es el algoritmo de J. Lamping para la reducción óptima del cálculo lambda . Hay pocas dudas de que el teorema del cálculo sin tipo puede extenderse al CIC.

Otra pregunta relevante es la cantidad de información de tipo que se puede borrar al realizar la conversión de tipo, o incluso cómo realizar una conversión eficiente, que es un campo activo de investigación, ver, por ejemplo , la tesis de Mishra-Linger .

cody
fuente

6

Permítanme insistir en el punto de vista tocado por la respuesta de Cody.

$\lambda$ $\lambda$ $\lambda$ $\lambda$

$M$ $f$

M \bar{x} \to^{l (| x |)} \bar{f (x)}

$M\,\overline{x}\to^{l(|x|)}\overline{f(x)}$

l (| x |)

$l(|x|)$

l (n) = O (n^{k})

$l(n)=O(n^k)$

k

$k$

f

$f$

$\lambda$ $\Theta(n)$ $\Theta(2^n)$ $\lambda$ $\lambda$

$\lambda$ $\lambda$

$\lambda$

Esta misma sintaxis se puede utilizar para demostrar que, contrariamente a la intuición ingenua, la respuesta a la pregunta anterior es sí, de hecho: el número de pasos más a la izquierda de la forma normal es una medida de costo razonable, incluso si el tamaño explota, porque de hecho, hay otra forma de representar el mismo cálculo (usando sustituciones lineales explícitas) en el que:

el tamaño no explota;
$\lambda$

Todo esto se explica en el artículo de Accattoli y Dal Lago "La reducción beta es invariable, de hecho" (LICS 2014 y luego creo que hay una versión más reciente de la revista).

$\lambda$

Damiano Mazza
fuente

Lo que tenía en mente es, por ejemplo, un término que despliega un millón de pasos para generar una lista de un millón de elementos. Esto se normaliza a la lista real, que es la representación más eficiente de ese valor (es el resultado final real, no se necesitan más pasos). Pero el término desplegado en sí mismo puede ser muy pequeño.

user47376

β

$\beta$

Sí, es imposible como dijo Andrej. Eso respondió mi pregunta.

user47376

Cálculo de construcciones: comprime la expresión a su forma más pequeña

Respuestas: