En informática , un evaluador metacircular ( MCE ) o intérprete metacircular ( MCI ) es un intérprete que define cada característica del lenguaje interpretado utilizando una función similar del lenguaje anfitrión del intérprete. Por ejemplo, la interpretación de una aplicación lambda se puede implementar utilizando la función application. [1] La evaluación metacircular es más destacada en el contexto de Lisp . [1] [2] Un autointérprete es un intérprete metacircular en el que el lenguaje interpretado es casi idéntico al lenguaje anfitrión; los dos términos se utilizan a menudo como sinónimos. [3]
La disertación de Corrado Böhm [4] describe el diseño de un compilador autoalojado . [5] Debido a la dificultad de compilar funciones de orden superior , muchos lenguajes se definieron a través de intérpretes, el más destacado de los cuales fue Lisp. [1] [6] El término en sí fue acuñado por John C. Reynolds , [1] y popularizado a través de su uso en el libro Structure and Interpretation of Computer Programs . [3] [7]
Un autointérprete es un intérprete metacircular en el que el idioma anfitrión es también el idioma que se interpreta. [8] Un autointérprete muestra una función universal para el idioma en cuestión y puede ser útil para aprender ciertos aspectos del idioma. [2] Un autointérprete proporcionará una definición circular y vacía de la mayoría de las construcciones del idioma y, por lo tanto, proporciona poca información sobre la semántica del idioma interpretado, por ejemplo, la estrategia de evaluación . Al abordar estas cuestiones se produce la noción más general de un "intérprete definicional". [1]
Esta parte se basa en la Sección 3.2.4 de la tesis de Danvy. [9]
Aquí se encuentra el núcleo de un autoevaluador para el cálculo. La sintaxis abstracta del cálculo se implementa de la siguiente manera en OCaml , representando las variables con su índice de Bruijn , es decir, con su desplazamiento léxico (empezando desde 0):
término de tipo = IND de int (* índice de Bruijn *) | ABS de plazo | APP de término * términoEl evaluador utiliza un entorno:
tipo valor = FUN de ( valor -> valor )deje que rec eval ( t : término ) ( e : valor lista ) : valor = coincida con t con IND n -> Lista . nth e n | ABS t' -> FUN ( fun v -> eval t' ( v :: e )) | APP ( t0 , t1 ) -> apply ( eval t0 e ) ( eval t1 e ) y apply ( FUN f : valor ) ( a : valor ) = f asea principal ( t : término ) : valor = eval t []Los valores (de tipo value) combinan valores expresables (el resultado de evaluar una expresión en un entorno) y valores denotables (los valores denotados por variables en el entorno), una terminología que se debe a Christopher Strachey . [10] [11]
Los entornos se representan como listas de valores denotables.
El evaluador central tiene tres cláusulas:
Este evaluador es compositivo en el sentido de que cada una de sus llamadas recursivas se realiza sobre una subparte propia del término dado. También es de orden superior , ya que el dominio de valores es un espacio de funciones.
En "Definitional Interpreters", Reynolds respondió a la pregunta de si un autointérprete de este tipo está bien definido. Respondió negativamente porque la estrategia de evaluación del lenguaje definido (el lenguaje fuente) está determinada por la estrategia de evaluación del lenguaje definitorio (el metalenguaje). Si el metalenguaje sigue la llamada por valor (como hace OCaml), el lenguaje fuente sigue la llamada por valor. Si el metalenguaje sigue la llamada por nombre (como hace Algol 60 ), el lenguaje fuente sigue la llamada por nombre. Y si el metalenguaje sigue la llamada por necesidad (como hace Haskell ), el lenguaje fuente sigue la llamada por necesidad.
En "Definitional Interpreters", Reynolds definió claramente un autointérprete haciéndolo independiente de la estrategia de evaluación de su lenguaje definitorio. Fijó la estrategia de evaluación transformando el autointérprete en un estilo de paso de continuación , que es independiente de la estrategia de evaluación, como se plasmó posteriormente en los teoremas de independencia de Gordon Plotkin . [12]
Además, como las relaciones lógicas aún no se habían descubierto, Reynolds hizo que el evaluador de paso de continuación resultante fuera de primer orden (1) convirtiéndolo en un evaluador de cierre y (2) desfuncionalizando la continuación. Señaló la "calidad de máquina" del intérprete resultante, que es el origen de la máquina CEK , ya que la transformación CPS de Reynolds era para la llamada por valor. [13] Para la llamada por nombre, estas transformaciones asignan el autointérprete a una instancia temprana de la máquina Krivine . [14] La máquina SECD y muchas otras máquinas abstractas se pueden interderivar de esta manera. [15] [16]
Es notable que las tres máquinas abstractas más famosas para el cálculo correspondan funcionalmente al mismo autointérprete.
Los lenguajes de programación funcional total que son fuertemente normalizadores no pueden ser Turing completos , de lo contrario se podría resolver el problema de detención viendo si el programa verifica el tipo. Eso significa que hay funciones computables que no se pueden definir en el lenguaje total. [17] En particular, es imposible definir un autointérprete en un lenguaje de programación total, por ejemplo en cualquiera de los cálculos lambda tipados como el cálculo lambda simplemente tipado , el Sistema F de Jean-Yves Girard o el cálculo de construcciones de Thierry Coquand . [18] [19] Aquí, por "autointérprete" nos referimos a un programa que toma una representación de término fuente en algún formato simple (como una cadena de caracteres) y devuelve una representación del término normalizado correspondiente. Este resultado de imposibilidad no se cumple para otras definiciones de "autointérprete". Por ejemplo, algunos autores se han referido a funciones de tipo como autointérpretes, donde es el tipo de representaciones de términos tipificados. Para evitar confusiones, nos referiremos a estas funciones como auto-reconocedores . Brown y Palsberg demostraron que los auto-reconocedores podrían definirse en varios lenguajes fuertemente normalizadores, incluyendo System F y System F ω . [20] Esto resultó ser posible porque los tipos de términos codificados que se reflejan en los tipos de sus representaciones impiden construir un argumento diagonal . En su artículo, Brown y Palsberg afirman refutar la "sabiduría convencional" de que la auto-interpretación es imposible (y se refieren a Wikipedia como un ejemplo de la sabiduría convencional), pero lo que realmente refutan es la imposibilidad de los auto-reconocedores, un concepto distinto. En su trabajo de seguimiento, cambian a la terminología más específica de "auto-reconocedor" utilizada aquí, distinguiéndolos notablemente de los "auto-evaluadores", de tipo . [21] También reconocen que implementar la auto-evaluación parece más difícil que el autorreconocimiento, y dejan la implementación de la primera en un lenguaje fuertemente normalizador como un problema abierto.
En combinación con una implementación de lenguaje existente, los intérpretes metacirculares proporcionan un sistema de base desde el cual extender un lenguaje, ya sea hacia arriba agregando más características o hacia abajo compilando características en lugar de interpretarlas. [22] También son útiles para escribir herramientas que están estrechamente integradas con el lenguaje de programación, como depuradores sofisticados. [ cita requerida ] Un lenguaje diseñado con una implementación metacircular en mente es a menudo más adecuado para construir lenguajes en general, incluso aquellos completamente diferentes del lenguaje anfitrión. [ cita requerida ]
Muchos lenguajes tienen una o más implementaciones metacirculares. A continuación se muestra una lista parcial.
Algunos lenguajes con una implementación metacircular diseñada de abajo hacia arriba, en orden cronológico agrupado:
Algunos lenguajes con una implementación metacircular a través de terceros:
