stringtranslate.com

Evaluador meta-circular

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]

Historia

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]

Autointerpretes

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]

De autointérprete a máquina abstracta

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érmino

El 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.

Autointerpretación en lenguajes de programación total

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.

Usos

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 ]

Ejemplos

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:

Véase también

Referencias

  1. ^ abcde Reynolds, John C. (1972). "Intérpretes definicionales para lenguajes de programación de orden superior". Actas de la conferencia anual de la ACM sobre - ACM '72 (PDF) . Vol. 2. Actas de la 25.ª Conferencia Nacional de la ACM. págs. 717–740. doi :10.1145/800194.805852 . Consultado el 14 de abril de 2017 .
  2. ^ ab Reynolds, John C. (1998). "Revisitando los intérpretes definicionales" (PDF) . Higher-Order and Symbolic Computation . 11 (4): 355–361. doi :10.1023/A:1010075320153. S2CID  34126862. Consultado el 21 de marzo de 2023 .
  3. ^ ab "El evaluador metacircular". Estructura e interpretación de programas informáticos . MIT.
  4. ^ Böhm, Corrado (1954). "Calculatrices digitales. Du déchiffrage des formules logico-mathématiques par la machine même dans la conception du program". Ana. Estera. Pura Appl . 4 (37): 1–51.
  5. ^ Knuth, Donald E. ; Pardo, Luis Trabb (agosto de 1976). El desarrollo temprano de los lenguajes de programación. p. 36.
  6. ^ McCarthy, John (1961). "Una función universal de LISP" (PDF) . Manual del programador de Lisp 1.5 . pág. 10.
  7. ^ Harvey, Brian. "Por qué la estructura y la interpretación de los programas informáticos son importantes". people.eecs.berkeley.edu . Consultado el 14 de abril de 2017 .
  8. ^ Braithwaite, Reginald (22 de noviembre de 2006). «La importancia del intérprete metacircular» . Consultado el 22 de enero de 2011 .
  9. ^ Danvy, Olivier (2006). Un enfoque analítico de los programas como objetos de datos (Tesis). doi :10.7146/aul.214.152. ISBN 9788775073948.
  10. ^ Strachey , Christopher (1967). Conceptos fundamentales en lenguajes de programación (informe técnico). doi :10.1023/A:1010000313106.
  11. ^ Mosses, Peter D. (2000). "Un prólogo a 'Conceptos fundamentales en lenguajes de programación'"". Computación simbólica y de orden superior . 13 (1/2): 7–9. doi :10.1023/A:1010048229036. S2CID  39258759.
  12. ^ Plotkin, Gordon D. (1975). "Llamada por nombre, llamada por valor y el cálculo lambda". Ciencias Informáticas Teóricas . 1 (2): 125–159. doi : 10.1016/0304-3975(75)90017-1 .
  13. ^ Felleisen, Matthias ; Friedman, Daniel (1986). Operadores de control, la máquina SECD y el cálculo lambda (PDF) . Descripción formal de conceptos de programación III, Elsevier Science Publishers BV (Holanda del Norte). págs. 193–217.
  14. ^ Schmidt, David A. (1980). "Máquinas de transición de estado para expresiones de cálculo lambda". Máquinas de transición de estado para expresiones de cálculo lambda . Notas de clase en informática. 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.
  15. ^ Danvy , Olivier (2004). Una deconstrucción racional de la máquina SECD de Landin (PDF) . Implementación y aplicación de lenguajes funcionales, 16.º taller internacional, IFL 2004, Documentos seleccionados revisados, Lecture Notes in Computer Science 3474, Springer. pp. 52–71. ISSN  0909-0878.
  16. ^ Ager, Mads Sig; Biernacki, Dariusz; Danvy, Olivier ; Midtgaard, Jan (2003). "Una correspondencia funcional entre evaluadores y máquinas abstractas". Serie de informes Brics . 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 .
  17. ^ Riolo, Rick; Worzel, William P.; Kotanchek, Mark (4 de junio de 2015). Teoría y práctica de la programación genética XII. Springer. pág. 59. ISBN 978-3-319-16030-6. Recuperado el 8 de septiembre de 2021 .
  18. ^ Conor McBride (mayo de 2003), "sobre la terminación" (publicado en la lista de correo Haskell-Cafe).
  19. ^ Andrej Bauer (junio de 2014), Respuesta a: Un lenguaje total que sólo un lenguaje completo de Turing puede interpretar (publicado en el sitio Theoretical Computer Science StackExchange )
  20. ^ Brown, Matt; Palsberg, Jens (11 de enero de 2016). "Rompiendo la barrera de la normalización: un autointérprete para f-omega" (PDF) . Actas del 43.° Simposio anual ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . pp. 5–17. doi :10.1145/2837614.2837623. ISBN . 9781450335492. Número de identificación del sujeto  14781370.
  21. ^ Brown, Matt; Palsberg, Jens (enero de 2017). "Autoevaluación tipificada mediante funciones de tipo intensional". Actas del 44.º Simposio ACM SIGPLAN sobre principios de lenguajes de programación . págs. 415–428. doi : 10.1145/3009837.3009853 . ISBN . 9781450346603.
  22. ^ Oriol, Manuel; Meyer, Bertrand (29 de junio de 2009). Objects, Components, Models and Patterns: 47th International Conference, TOOLS EUROPE 2009, Zúrich, Suiza, 29 de junio-3 de julio de 2009, Actas. Springer Science & Business Media. pág. 330. ISBN 9783642025716. Recuperado el 14 de abril de 2017 .
  23. ^ Implementación metacircular del lenguaje de programación Pico

Enlaces externos