Hispanopedia Wiki
Articulo de referencia

Máquina Krivine

Vista en imagen de una máquina Krivine. En informática teórica , la máquina de Krivine es una máquina abstracta . Como tal, comparte características con las máquinas de Turing y...

Hispanopedia WikiContenido en espanolLectura gratuita
Vista en imagen de una máquina Krivine.

En informática teórica , la máquina de Krivine es una máquina abstracta . Como tal, comparte características con las máquinas de Turing y la máquina SECD . La máquina de Krivine explica cómo calcular una función recursiva. Más específicamente, su objetivo es definir rigurosamente la reducción de la forma normal de cabeza de un término lambda mediante la reducción por nombre . Gracias a su formalismo, explica en detalle cómo funciona un tipo de reducción y establece la base teórica de la semántica operacional de los lenguajes de programación funcional . Por otro lado, la máquina de Krivine implementa la reducción por nombre porque evalúa el cuerpo de una β- redefinición antes de aplicarlo a su parámetro. En otras palabras, en una expresión ( λ x . t ) u , evalúa primero λ x . t antes de aplicarlo a u . En programación funcional , esto significaría que para evaluar una función aplicada a un parámetro, primero evalúa la función antes de aplicarla al parámetro.

La máquina de Krivine fue diseñada por el lógico francés Jean-Louis Krivine a principios de la década de 1980.

Llamar por nombre y cabeza reducción de forma normal

La máquina de Krivine se basa en dos conceptos relacionados con el cálculo lambda , a saber, la reducción de cabeza y la llamada por nombre.

Reducción de la forma normal de la cabeza

Un redex [ 1 ] (también se dice β-redex) es un término del cálculo lambda de la forma ( λ x . t ) u . Si un término tiene la forma ( λ x . t ) u 1 ... u n se dice que es un redex de cabeza . Una forma normal de cabeza es un término del cálculo lambda que no es un redex de cabeza. [ a ] ​​Una reducción de cabeza es una secuencia (no vacía) de contracciones de un término que contrae redex de cabeza. Una reducción de cabeza de un término t (que se supone que no está en forma normal de cabeza) es una reducción de cabeza que comienza en un término t y termina en una forma normal de cabeza. Desde un punto de vista abstracto, la reducción de cabeza es la forma en que un programa calcula cuando evalúa un subprograma recursivo. Es importante comprender cómo se puede implementar dicha reducción. Uno de los objetivos de la máquina de Krivine es proponer un proceso para reducir un término en forma normal de cabeza y describir formalmente este proceso. Así como Turing utilizó una máquina abstracta para describir formalmente la noción de algoritmo, Krivine utilizó una máquina abstracta para describir formalmente la noción de reducción de la forma normal de la cabeza.

Un ejemplo

El término (( λ 0) ( λ 0)) ( λ 0) (que corresponde, si se usan variables explícitas, al término ( λx . x ) ( λy . y ) ( λz . z )) no está en forma normal de cabeza porque ( λ 0) ( λ 0) se contrae en ( λ 0) dando como resultado el redex de cabeza ( λ 0) ( λ 0) que se contrae en ( λ 0) y que, por lo tanto, es la forma normal de cabeza de (( λ 0) ( λ 0)) ( λ 0). Dicho de otro modo, la contracción de la forma normal de cabeza es:

(( λ 0) ( λ 0 )) ( λ 0 ) ➝ ( λ 0) ( λ 0) ➝ λ 0,

que corresponde a  :

( λx . x ) ( λy . y ) ( λz . z ) ➝ ( λy . y ) ( λz . z ) ➝ λz . z .

Veremos más adelante cómo la máquina de Krivine reduce el término (( λ 0) ( λ 0)) ( λ 0).

Llamar por nombre

Para implementar la reducción de la cabeza de un término uv que es una aplicación, pero que no es un redex, se debe reducir el cuerpo u para exhibir una abstracción y, por lo tanto, crear un redex con v . Cuando aparece un redex, se reduce. Reducir siempre primero el cuerpo de una aplicación se llama llamada por nombre . La máquina de Krivine implementa la llamada por nombre .

Descripción

La presentación de la máquina de Krivine que se da aquí se basa en notaciones de términos lambda que utilizan índices de De Bruijn y asume que los términos de los que calcula las formas normales de cabeza son cerrados . [ 2 ] Modifica el estado actual hasta que ya no puede hacerlo, en cuyo caso obtiene una forma normal de cabeza. Esta forma normal de cabeza representa el resultado del cálculo o produce un error, lo que significa que el término del que partió no es correcto. Sin embargo, puede entrar en una secuencia infinita de transiciones, lo que significa que el término que intenta reducir no tiene forma normal de cabeza y corresponde a un cálculo que no termina.

Se ha demostrado que la máquina de Krivine implementa correctamente la reducción de la forma normal de la cabeza por nombre en el cálculo lambda. Además, la máquina de Krivine es determinista , ya que cada patrón del estado corresponde a, como máximo, una transición de la máquina.

El estado

El estado tiene tres componentes [ 2 ]

  1. un término ,
  2. una pila ,
  3. un entorno .

El término es un λ-término con índices de De Bruijn. La pila y el entorno pertenecen a la misma estructura de datos recursiva . Más precisamente, el entorno y la pila son listas de pares <término,  entorno> , que se denominan cierres . En lo que sigue, la inserción como cabeza de una lista ℓ (pila o entorno) de un elemento a se escribe a:ℓ , mientras que la lista vacía se escribe □. La pila es la ubicación donde la máquina almacena los cierres que deben evaluarse posteriormente, mientras que el entorno es la asociación entre los índices y los cierres en un momento dado durante la evaluación. El primer elemento del entorno es el cierre asociado con el índice 0 , el segundo elemento corresponde al cierre asociado con el índice 1, etc. Si la máquina tiene que evaluar un índice, recupera allí el par <término, entorno>, el cierre que produce el término a evaluar y el entorno en el que debe evaluarse este término. [ b ] Estas explicaciones intuitivas permiten comprender las reglas de funcionamiento de la máquina. Si se escribe t para término, p para pila, [ c ] y e para entorno, los estados asociados a estas tres entidades se escribirán t , p, e. Las reglas explican cómo la máquina transforma un estado en otro, tras identificar los patrones entre los estados.

El estado inicial tiene como objetivo evaluar un término t ; es el estado t ,□,□, en el que el término es t y la pila y el entorno están vacíos. El estado final (en ausencia de error) es de la forma λ  t ,  □,  e; en otras palabras, el término resultante es una abstracción junto con su entorno y una pila vacía.

Las transiciones

La máquina de Krivine [ 2 ] tiene cuatro transiciones  : App , Abs , Zero , Succ .

La transición App elimina el parámetro de una aplicación y lo coloca en la pila para su posterior evaluación. La transición Abs elimina el λ del término y extrae el cierre de la parte superior de la pila y lo coloca en la parte superior del entorno. Este cierre corresponde al índice de De Bruijn 0 en el nuevo entorno. La transición Zero toma el primer cierre del entorno. El término de este cierre se convierte en el término actual y el entorno de este cierre se convierte en el entorno actual. La transición Succ elimina el primer cierre de la lista de entornos y disminuye el valor del índice.

Dos ejemplos

Evalúemos el término ( λ 0 0) ( λ 0) que corresponde al término ( λ x . x x ) ( λ x . x ). Comencemos con el estado ( λ 0 0) ( λ 0), □, □.

La conclusión es que la forma normal de la cabeza del término ( λ 0 0) ( λ 0) es λ 0 Volviendo a poner las variables: la forma normal de la cabeza del término ( λ x . x x ) ( λ x . x ) es λ x . x

Evalúemos el término (( λ 0) ( λ 0)) ( λ 0) como se muestra a continuación:

Esto confirma el hecho anterior de que la forma normal del término (( λ 0) ( λ 0)) ( λ 0) es ( λ 0) O con variables: (( λ x . x ) ( λ x . x )) ( λ x . x ) es ( λ x . x )

Interderivaciones

La máquina de Krivine, al igual que la máquina CEK , no solo corresponde funcionalmente a un evaluador metacircular , [ 3 ] [ 4 ] [ 5 ] sino que también corresponde sintácticamente a laλρ^{\displaystyle \lambda {\widehat {\rho }}}Cálculo: una versión del cálculo de Pierre-Louis Curien.λρ^{\displaystyle \lambda {\widehat {\rho }}}cálculo de sustituciones explícitas que es cerrado bajo reducción, con una estrategia de reducción de orden normal. [ 6 ] [ 7 ] [ 8 ]

Si elλρ^{\displaystyle \lambda {\widehat {\rho }}}El cálculo incluye generalizadoβ{\displaystyle \beta }reducción (es decir, la anidada)β{\displaystyle \beta }redex(λincógnita1.λincógnita2.mi0)mi1mi2{\displaystyle (\lambda x_{1}.\lambda x_{2}.e_{0})\;e_{1}\;e_{2}}se contrae en un paso en lugar de dos), entonces la máquina sintácticamente correspondiente coincide con la máquina original de Jean-Louis Krivine. [ 9 ] [ 7 ] (Además, si la estrategia de reducción es de derecha a izquierda llamada por valor e incluye generalizadaβ{\displaystyle \beta }reducción, entonces la máquina sintácticamente correspondiente es la máquina abstracta ZINC de Xavier Leroy , que subyace a OCaml .) [ 10 ] [ 7 ]

Véase también

Notas

  1. ↑ Si solo se trabaja con términos cerrados, estos términos toman la forma λ x . t .
  2. ↑ Utilizando el concepto de cierre, se puede reemplazar la tripleta <término, pila, entorno> , que define el estado, por un par <cierre, pila> , pero este cambio es cosmético.
  3. ↑ p es de pile , la palabra francesa para pila, que no queremos confundir con s , de state.

Referencias

  1. ↑ Barendregt, Hendrik Pieter (1984), El cálculo lambda: su sintaxis y semántica , Estudios en lógica y fundamentos de las matemáticas, vol.  103 (edición revisada  ), North Holland, Ámsterdam, ISBN 0-444-87508-5Archivado del original el 23 de agosto de 2004.Correcciones .
  2. 1 2 3 Curien, Pierre-Louis (1993). Combinadores categóricos, algoritmos secuenciales y programación funcional (2.ª ed.). Boston/Basilea/Berlín: Birkhäuser. ISBN  0-8176-3654-4.
  3. ↑ Schmidt, David A. (1980). "Máquinas de transición de estados para expresiones de cálculo lambda". Máquinas de transición de estados para expresiones de cálculo lambda . Lecture Notes in Computer Science. Vol. 94. Generación de compiladores dirigida por semántica, LNCS 94. págs. 415–440 . doi : 10.1007/3-540-10250-7_32 . ISBN   978-3-540-10250-2.
  4. ↑ Schmidt, David A. (2007). "Máquinas de transición de estados, una revisión". Higher-Order and Symbolic Computation . 20 (3): 333– 335. doi : 10.1007/s10990-007-9017-x . S2CID 3012667 . 
  5. ↑ Ager, Mads Sig; Biernacki, Dariusz; Danvy, Olivier ; Midtgaard, Jan (2003). "Una correspondencia funcional entre evaluadores y máquinas abstractas" . BRICS Report Series . 10 (13). 5.ª Conferencia Internacional ACM SIGPLAN sobre Principios y Práctica de la Programación Declarativa (PPDP'03): 8–19 . doi : 10.7146/brics.v10i13.21783 .
  6. ↑ Curien, Pierre-Louis (1991). "Un marco abstracto para máquinas de entorno" . Theoretical Computer Science . 82 (2): 389– 402. doi : 10.1016/0304-3975(91)90230-Y .
  7. 1 2 3 Biernacka, Małgorzata; Danvy, Olivier (2007). "Un marco concreto para máquinas de entorno" . ACM Transactions on Computational Logic . 9 (1): 6. doi : 10.1145/1297658.1297664 .
  8. ↑ Swierstra, Wouter (2012). "De las matemáticas a la máquina abstracta: una derivación formal de una máquina Krivine ejecutable" . Electronic Proceedings in Theoretical Computer Science . 76. Actas del Cuarto Taller sobre Programación Funcional Estructurada Matemáticamente (MSFP 2012): 163–177 . arXiv : 1202.2924 . doi : 10.4204/EPTCS.76.10 . S2CID 14668530 . 
  9. ↑ Krivine, Jean-Louis (2007). "Una máquina de cálculo lambda por nombre". Higher-Order and Symbolic Computation . 20 (3): 199– 207. doi : 10.1007/s10990-007-9018-9 . S2CID 18158499 . 
  10. ↑ Leroy , Xavier (1990). El experimento ZINC: una implementación económica del lenguaje ML (Informe técnico). Inria. 117.

El contenido de esta edición se ha traducido del artículo existente en la Wikipedia en francés en fr:Machine de Krivine ; consulte su historial para obtener la atribución.

Bibliografía

  • Jean-Louis Krivine: Una máquina de cálculo lambda por nombre . Higher-Order and Symbolic Computation 20(3): 199-207 (2007) archivo .
  • Curien, Pierre-Louis (1993). Combinadores categóricos, algoritmos secuenciales y programación funcional (2.ª  ed.). Boston/Basilea/Berlín: Birkhäuser. ISBN 0-8176-3654-4.
  • Frédéric Lang: Explicación de la máquina de Krivine perezosa mediante sustitución explícita y direcciones . Higher-Order and Symbolic Computation 20(3): 257-270 (2007) archivo .
  • Olivier Danvy (Ed.): Editorial del número especial de Higher-Order and Symbolic Computation on the Krivine machine, vol. 20(3) (2007)
  • Logotipo de Wikimedia CommonsContenido multimedia relacionado con la máquina Krivine en Wikimedia Commons.