Evaluador meta-circular
En informática , un evaluador meta-circular ( MCE ) o un intérprete meta-circular ( MCI ) es un intérprete que define cada característica del lenguaje interpretado utilizando una facilidad similar del idioma anfitrión del intérprete. Por ejemplo, la interpretación de una aplicación lambda se puede implementar usando la función aplicación. [1] La evaluación meta-circular es más prominente en el contexto de Lisp . [1] Un auto-intérprete es un intérprete meta-circular donde el idioma interpretado es casi idéntico al idioma anfitrión; los dos términos se utilizan a menudo como sinónimos. [2]
La disertación de Corrado Böhm [3] describe el diseño de un autoalojamiento compilador. [4] Debido a la dificultad de compilar funciones de orden superior , muchos lenguajes se definieron a través de intérpretes, principalmente Lisp. [1] [5] El término en sí fue acuñado por John C. Reynolds , [1] y popularizado a través de su uso en el libro Estructura e interpretación de programas de computadora . [2] [6]
Un auto-intérprete es un intérprete meta-circular donde el idioma anfitrión es también el idioma que se interpreta. [7] Un auto-intérprete tiene una función universal para el idioma en cuestión y puede ser útil para aprender ciertos aspectos del idioma. [8] Un auto-intérprete proporcionará una definición circular y vacía de la mayoría de las construcciones del lenguaje y, por lo tanto, proporcionará poca información sobre la semántica del lenguaje interpretado, por ejemplo , la estrategia de evaluación . Abordar estos problemas produce la noción más general de un "intérprete de definiciones". [1]
Los lenguajes de programación funcionales totales que se están normalizando fuertemente no pueden ser Turing completos , de lo contrario, se podría resolver el problema de la detención viendo si el tipo de programa se verifica. Eso significa que hay funciones computables que no se pueden definir en el lenguaje total. [9] En particular, es imposible definir un auto-intérprete en un lenguaje de programación total, por ejemplo, en cualquiera de los mecanografiada lambda cálculos tales como el cálculo lambda simplemente mecanografiado , Jean-Yves Girard 's System F , o Thierry Coquand ' s cálculo de construcciones . [10] [11]Aquí, por "auto-intérprete" nos referimos a un programa que toma una representación del 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 es válido para otras definiciones de "auto-intérprete". Por ejemplo, algunos autores se han referido a funciones de tipo como auto-intérpretes, donde es el tipo de representaciones de términos con tipo. Para evitar confusiones, nos referiremos a estas funciones como autorreconocimientos . Brown y Palsberg demostraron que los autorreconocimientos se pueden definir en varios lenguajes fuertemente normalizados, incluidos System F y System F ω . [12]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 autointerpretación es imposible (y se refieren a Wikipedia como un ejemplo de la sabiduría convencional), pero lo que en realidad 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 "autorreconocimiento" que se utiliza aquí, distinguiéndolos notablemente de los "autoevaluadores", del tipo . [13]También reconocen que implementar la autoevaluació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.
