¿Qué propiedades de un lenguaje de programación hacen imposible la compilación?

72

Pregunta:

"Ciertas propiedades de un lenguaje de programación pueden requerir que la única forma de ejecutar el código escrito en él sea mediante interpretación. En otras palabras, la compilación en un código de máquina nativo de una CPU tradicional no es posible. ¿Cuáles son estas propiedades?"

Compiladores: Principios y práctica por Parag H. Dave y Himanshu B. Dave (2 de mayo de 2012)

El libro no da pistas sobre la respuesta. Traté de encontrar la respuesta en Conceptos de lenguajes de programación (SEBESTA), pero fue en vano. Las búsquedas en la web también fueron de poca utilidad. ¿Tienes alguna pista?

Anderson Nascimento Nunes
fuente
31
Famosamente, Perl ni siquiera puede ser analizado . Aparte de eso, el reclamo parece ser trivialmente incorrecto sin más suposiciones: si hay un intérprete, siempre puedo agrupar el intérprete y el código en un ejecutable, voila.
Raphael
44
@Raphael: Buena idea, pero ... 1) Estás asumiendo que el código está disponible antes de ser ejecutado. Eso no es válido para uso interactivo. Claro, puede usar la compilación justo a tiempo para el código nativo en declaraciones bash o contenido de pila PostScript, pero es una idea bastante loca. 2) Su idea en realidad no compila el código: el paquete no es una versión compilada del código, sino un intérprete para el código.
reinierpost
77
En los viejos tiempos tenía auto edición de programas gwbasic (gwbasic almacena programas básicos en una especie de bytecode). Actualmente no puedo pensar en una forma sensata de compilarlos en el código de máquina nativo mientras conserva su capacidad de editarse.
PlasmaHH
15
@PlasmaHH: el código de modificación automática se remonta a 1948. El primer compilador se escribió en 1952. El concepto de código de modificación automática se inventó en el código de máquina nativo.
Mooing Duck
10
@reinierpost Raphael está adoptando una postura teórica sobre este tema. Tiene el mérito de mostrar las limitaciones conceptuales de la pregunta. La compilación es la traducción del lenguaje S al lenguaje T. El lenguaje T podría ser una extensión de S a la que se puede agregar el código de interpretación en algún otro idioma. Por lo tanto, agrupar a S y su intérprete es un programa en lenguaje T. Parece absurdo para un ingeniero, pero muestra que no es fácil formular la pregunta de manera significativa. ¿Cómo distingue un proceso de compilación aceptable de uno inaceptable (como el de Raphael) desde el punto de vista de la ingeniería?
babou

Respuestas:

61

La distinción entre código interpretado y compilado es probablemente una ficción, como lo subraya el comentario de Raphael :

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

El hecho es que el código siempre se interpreta, por software, por hardware o una combinación de ambos, y el proceso de compilación no puede determinar cuál será.

Lo que percibes como compilación es un proceso de traducción de un idioma (para el origen) a otro idioma (para el destino). Y, el intérprete de suele ser diferente de la intérprete para .T S TSTST

El programa compilado se traduce de una forma sintáctica a otra forma sintáctica , de modo que, dada la semántica prevista de los lenguajes y , y tienen el mismo comportamiento computacional, hasta algunas cosas que generalmente intenta cambiar, posiblemente para optimizar, como la complejidad o la eficiencia simple (tiempo, espacio, superficie, consumo de energía). Estoy tratando de no hablar de equivalencia funcional, ya que requeriría definiciones precisas.P T S T P S P TPSPTSTPSPT

Algunos compiladores se han utilizado simplemente para reducir el tamaño del código, no para "mejorar" la ejecución. Este fue el caso del lenguaje utilizado en el sistema Platón (aunque no lo llamaron compilación).

Usted puede considerar plenamente su código compilado si, después del proceso de compilación, ya no es necesario el intérprete de . Al menos, esa es la única forma en que puedo leer su pregunta, como una pregunta de ingeniería más que teórica (ya que, en teoría, siempre puedo reconstruir el intérprete).S

Una cosa que puede plantear problemas, afaik, es la meta-circularidad . Es entonces cuando un programa manipulará estructuras sintácticas en su propio lenguaje fuente , creando fragmentos de programa que luego se interpretarán como si hubieran sido parte del programa original. Como puede producir fragmentos de programa arbitrarios en el lenguaje como resultado de la computación arbitraria manipulando fragmentos sintácticos sin sentido, supongo que puede hacer que sea casi imposible (desde un punto de vista de ingeniería) compilar el programa en el lenguaje , de modo que ahora generar fragmentos de . Por lo tanto , se necesitará el intérprete para , o al menos el compilador de aS T T S S T SSSTTSST para compilar sobre la marcha los fragmentos generados en (ver también este documento ).S

Pero no estoy seguro de cómo se puede formalizar esto correctamente (y no tengo tiempo en este momento). E imposible es una gran palabra para un problema que no está formalizado.

Observaciones posteriores

Agregado después de 36 horas. Es posible que desee omitir esta larga secuela.

Los numerosos comentarios a esta pregunta muestran dos puntos de vista sobre el problema: un punto de vista teórico que lo considera sin sentido, y un punto de vista de la ingeniería que desafortunadamente no se formaliza tan fácilmente.

Hay muchas formas de ver la interpretación y la compilación, y trataré de esbozar algunas. Intentaré ser tan informal como pueda

El diagrama de lápida

Una de las primeras formalizaciones (principios de la década de 1960 hasta finales de 1990) son los diagramas T o Tombstone . Estos diagramas presentan en elementos gráficos componibles el lenguaje de implementación del intérprete o compilador, el idioma de origen que se interpreta o compila y el idioma de destino en el caso de los compiladores. Las versiones más elaboradas pueden agregar atributos. Estas representaciones gráficas pueden verse como axiomas, reglas de inferencia, utilizables para derivar mecánicamente la generación del procesador a partir de una prueba de su existencia a partir de los axiomas, a la Curry-Howard (aunque no estoy seguro de que se hiciera en los años sesenta :).

Evaluación parcial

Otra visión interesante es el paradigma de evaluación parcial . Estoy tomando una vista simple de los programas como un tipo de implementación de funciones que calcula una respuesta dados algunos datos de entrada. A continuación, un intérprete para el lenguaje es un programa que tome un programa escritos en y datos para ese programa, y calcula el resultado de acuerdo con la semántica de . La evaluación parcial es una técnica para especializar un programa de dos argumentos y , cuando solo se conoce un argumento, digamos . La intención es tener una evaluación más rápida cuando finalmente obtenga el segundo argumento S p S S d S a 1 a 2 a 1 a 2 a 2 a 1 a 1 a 2ISSpSSdSa1a2a1a2 . Es especialmente útil si cambia con más frecuencia que ya que el costo de la evaluación parcial con se puede amortizar en todos los cálculos donde solo está cambiando .a2a1a1a2

Esta es una situación frecuente en el diseño de algoritmos (a menudo el tema del primer comentario sobre SE-CS), cuando alguna parte más estática de los datos se procesa previamente, de modo que el costo del procesamiento previo se puede amortizar en todas las aplicaciones del algoritmo con partes más variables de los datos de entrada.

Esta es también la situación de los intérpretes, ya que el primer argumento es el programa que se ejecutará, y generalmente se ejecuta muchas veces con datos diferentes (o tiene subpartes ejecutadas muchas veces con datos diferentes). Por lo tanto, se convierte en una idea natural especializar a un intérprete para una evaluación más rápida de un programa dado al evaluarlo parcialmente en este programa como primer argumento. Esto puede verse como una forma de compilar el programa, y ​​ha habido un importante trabajo de investigación sobre la compilación mediante la evaluación parcial de un intérprete en su primer argumento (del programa).

El teorema de Smn

Lo bueno del enfoque de evaluación parcial es que tiene sus raíces en la teoría (aunque la teoría puede ser mentirosa), especialmente en el teorema de Smn de Kleene . Estoy tratando de dar una presentación intuitiva, esperando que no moleste a los teóricos puros.

Dada una numeración de Gödel de funciones recursivas, puede ver como su hardware, de modo que dado el número de Gödel (leer el código de objeto ) de un programa es la función definida por (es decir, calculada por el código de objeto en tu hardware)φφpφpp

En su forma más simple, el teorema se establece en wikipedia de la siguiente manera (hasta un pequeño cambio en la notación):

Dada una numeración de Gödel de funciones recursivas, hay una función recursiva primitiva de dos argumentos con la siguiente propiedad: por cada número de Gödel de una función computable parcial con dos argumentos, las expresiones y se definen para las mismas combinaciones de números naturales y , y sus valores son iguales para cualquier tal combinación. En otras palabras, la siguiente igualdad extensional de funciones es válida para cada : φσqfφσ(q,x)(y)f(x,y)xyxφσ(q,x)λy.φq(x,y).

Ahora, tomando como el intérprete , como el código fuente de un programa , e como los datos para ese programa, podemos escribir: qISxpSydφσ(IS,pS)λd.φIS(pS,d).

φIS puede ser visto como la ejecución del intérprete en el hardware, es decir, como un negro-caja lista para interpretar los programas escritos en un lenguaje .ISS

La función puede verse como una función que especializa al intérprete para el programa , como en la evaluación parcial. Por lo tanto, se puede ver que el número de Gödel tiene un código de objeto que es la versión compilada del programa .σISPSσ(IS,pS)pS

Entonces, la función puede verse como una función que toma como argumento el código fuente de un programa escrito en el lenguaje , y devuelve la versión del código objeto para ese programa Entonces, es lo que generalmente se llama un compilador.CS=λqS.σ((IS,qS)qSSCS

Algunas conclusiones

Sin embargo, como dije: "la teoría puede ser mentirosa", o en realidad parece serlo. El problema es que no sabemos nada de la función . En realidad, hay muchas funciones de este tipo, y supongo que la prueba del teorema puede usar una definición muy simple, que podría no ser mejor, desde un punto de vista de ingeniería, que la solución propuesta por Rafael: simplemente agrupar el código fuente con el intérprete . Esto siempre se puede hacer, por lo que podemos decir: la compilación siempre es posible.q S I SσqSIS

Formalizar una noción más restrictiva de lo que es un compilador requeriría un enfoque teórico más sutil. No sé qué se pudo haber hecho en esa dirección. El trabajo muy real realizado en la evaluación parcial es más realista desde el punto de vista de la ingeniería. Y, por supuesto, existen otras técnicas para escribir compiladores, incluida la extracción de programas a partir de la prueba de su especificación, desarrollada en el contexto de la teoría de tipos, basada en el isomorfismo de Curry-Howard (pero me estoy saliendo de mi dominio de competencia) .

Mi propósito aquí ha sido mostrar que el comentario de Raphael no es "loco", sino un recordatorio sensato de que las cosas no son obvias, ni siquiera simples. Decir que algo es imposible es una afirmación sólida que requiere definiciones precisas y una prueba, aunque solo sea para tener una comprensión precisa de cómo y por qué es imposible . Pero construir una formalización adecuada para expresar tal prueba puede ser bastante difícil.

Dicho esto, incluso si una característica específica no es compilable, en el sentido que entienden los ingenieros, las técnicas de compilación estándar siempre se pueden aplicar a partes de los programas que no usan dicha característica, como lo señala la respuesta de Gilles.

Para seguir las observaciones clave de Gilles de que, dependiendo del idioma, se puede hacer algo en tiempo de compilación, mientras que otro se debe hacer en tiempo de ejecución, lo que requiere un código específico, podemos ver que el concepto de compilación es realmente mal definido, y probablemente no sea definible de manera satisfactoria. La compilación es solo un proceso de optimización, como intenté mostrar en la sección de evaluación parcial , cuando lo comparé con el preprocesamiento de datos estáticos en algunos algoritmos.

Como un proceso de optimización complejo, el concepto de compilación en realidad pertenece a un continuo. Dependiendo de la característica del idioma o del programa, cierta información puede estar disponible estáticamente y permitir una mejor optimización. Otras cosas tienen que posponerse al tiempo de ejecución. Cuando las cosas se ponen realmente mal, todo debe hacerse en tiempo de ejecución, al menos para algunas partes del programa, y ​​agrupar el código fuente con el intérprete es todo lo que puede hacer. Por lo tanto, este paquete es solo el extremo inferior de este continuo de compilación. Gran parte de la investigación sobre compiladores trata de encontrar formas de hacer estáticamente lo que solía hacerse dinámicamente. La recolección de basura en tiempo de compilación parece un buen ejemplo.

Tenga en cuenta que decir que el proceso de compilación debería producir código de máquina no ayuda. Eso es precisamente lo que puede hacer la agrupación ya que el intérprete es código de máquina (bueno, la cosa puede volverse un poco más compleja con la compilación cruzada).

babou
fuente
3
" imposible es una gran palabra" Una palabra muy muy grande. =)
Brian S
3
Si uno define "compilación" para referirse a una secuencia de pasos que tienen lugar completamente antes de que un programa en ejecución reciba su primera entrada, y la interpretación es el proceso de hacer que el programa de control de datos fluya a través de medios que no son parte del modelo abstracto de máquina del programa , entonces, para que se compile un lenguaje, debe ser posible que el compilador identifique, antes de que comience la ejecución, cada significado posible que pueda tener una construcción de lenguaje. En los lenguajes donde una construcción de lenguaje podría tener un número ilimitado de significados, la compilación no funcionará.
supercat
@BrianS No, no lo es, y es imposible demostrar lo contrario;)
Michael Gazonda
@supercat Eso todavía no es una definición. ¿Cuál es el 'significado' de una construcción de lenguaje?
Rhymoid
¡Me encanta el concepto de ver un compilador / intérprete como una especie de ejecución parcial!
Bergi
17

La pregunta no es sobre si la compilación es imposible . Si se puede interpretar un idioma¹, se puede compilar de manera trivial al agrupar al intérprete con el código fuente. La pregunta es qué características del lenguaje hacen que esta sea esencialmente la única forma.

Un intérprete es un programa que toma el código fuente como entrada y se comporta según lo especificado por la semántica de ese código fuente. Si es necesario un intérprete, esto significa que el lenguaje incluye una forma de interpretar el código fuente. Esta característica se llama eval. Si se requiere un intérprete como parte del entorno de tiempo de ejecución del lenguaje, significa que el lenguaje incluye eval: evalexiste como primitivo o puede codificarse de alguna manera. Los idiomas conocidos como lenguajes de secuencias de comandos generalmente incluyen una evalcaracterística, como la mayoría de los dialectos de Lisp .

El hecho de que un idioma incluya evalno significa que la mayor parte no se pueda compilar en código nativo. Por ejemplo, hay compiladores Lisp optimizadores, que generan un buen código nativo y que, sin embargo, admiten eval; evalEl código ed puede interpretarse o compilarse sobre la marcha.

evales la última característica de necesidad de un intérprete, pero hay otras características que requieren algo menos que un intérprete. Considere algunas fases típicas de un compilador:

  1. Analizando
  2. Comprobación de tipo
  3. Codigo de GENERACION
  4. Enlace

evalsignifica que todas estas fases deben realizarse en tiempo de ejecución. Hay otras características que dificultan la compilación nativa. Tomándolo desde abajo, algunos lenguajes fomentan la vinculación tardía al proporcionar formas en que las funciones (métodos, procedimientos, etc.) y las variables (objetos, referencias, etc.) pueden depender de cambios de código no locales. Esto hace que sea difícil (pero no imposible) generar un código nativo eficiente: es más fácil mantener referencias de objetos como llamadas en una máquina virtual y dejar que el motor VM maneje los enlaces sobre la marcha.

En términos generales, la reflexión tiende a dificultar la compilación de idiomas en código nativo. Una evaluación primitiva es un caso extremo de reflexión; muchos idiomas no llegan tan lejos, pero tienen una semántica definida en términos de una máquina virtual, lo que permite, por ejemplo, que el código recupere una clase por su nombre, inspeccione su herencia, enumere sus métodos, llame a un método, etc. Java con JVM y C # con .NET son dos ejemplos famosos. La forma más sencilla de implementar estos lenguajes es compilándolos en bytecode , pero no obstante, existen compiladores nativos (muchos justo a tiempo ) que compilan al menos fragmentos de programas que no utilizan recursos de reflexión avanzados.

La verificación de tipos determina si un programa es válido. Diferentes idiomas tienen diferentes estándares para la cantidad de análisis que se realiza en tiempo de compilación frente al tiempo de ejecución: un idioma se conoce como "tipeado estáticamente" si realiza muchas comprobaciones antes de comenzar a ejecutar el código, y "tipeado dinámicamente" si no lo hace. Algunos idiomas incluyen una función de conversión dinámica o una función de comprobación de tipo y desorden; Estas características requieren incrustar un typechecker en el entorno de ejecución. Esto es ortogonal a los requisitos de incluir un generador de código o un intérprete en el entorno de tiempo de ejecución.

¹ Ejercicio: define un lenguaje que no se puede interpretar.

Gilles 'SO- deja de ser malvado'
fuente
(1) No estoy de acuerdo con incluir un intérprete con el código fuente contando como compilación, pero el resto de su publicación es excelente. (2) Totalmente de acuerdo sobre eval. (3) No veo por qué la reflexión haría que los lenguajes fueran difíciles de compilar en código nativo. Objective-C tiene reflexión, y (supongo) normalmente se compila. (4) Nota vagamente relacionada, la metamagia de la plantilla de C ++ generalmente se interpreta en lugar de compilarse y luego ejecutarse.
Mooing Duck
Se me ocurrió, Lua está compilada. El evalsimplemente compila el código de bytes, y luego como un paso separado el binario ejecuta el código de bytes. Y definitivamente tiene reflejo en el binario compilado.
Mooing Duck
En una máquina de Harvard Architecture, la compilación debería generar código al que nunca se debe acceder como "datos". Yo diría que la información del archivo fuente que termina siendo almacenada como datos en lugar de código no está realmente "compilada". No hay nada de malo en que un compilador tome una declaración como int arr[] = {1,2,5};y genere una sección de datos inicializados que contenga [1,2,5], pero no describiría su comportamiento como traducir [1,2,5] en código de máquina. Si casi todo un programa tiene que almacenarse como datos, ¿qué parte de él realmente se "compilaría"?
supercat
2
@supercat Eso es lo que los matemáticos y los informáticos entienden por trivial. Se ajusta a la definición matemática, pero no sucede nada interesante.
Gilles 'SO- deja de ser malvado'
@Gilles: si el término "compilar" está reservado para la traducción a las instrucciones de la máquina (sin retención de "datos" asociados) y acepta que en un lenguaje de compilación, el comportamiento de la declaración de la matriz no es "compilar" la matriz, entonces Hay algunos lenguajes en los que es imposible compilar una fracción significativa del código.
supercat
13

Creo que los autores suponen que compilar significa

  • el programa fuente no necesita estar presente en tiempo de ejecución, y
  • ningún compilador o intérprete necesita estar presente en tiempo de ejecución.

Aquí hay algunas características de muestra que lo harían problemático si no "imposible" para tal esquema:

  1. Si puede interrogar el valor de una variable en tiempo de ejecución, haciendo referencia a la variable por su nombre (que es una cadena), necesitará que los nombres de las variables estén disponibles en tiempo de ejecución.

  2. Si puede llamar a una función / procedimiento en tiempo de ejecución, refiriéndose a ella por su nombre (que es una cadena), necesitará los nombres de función / procedimiento en tiempo de ejecución.

  3. Si puede construir un programa en tiempo de ejecución (como una cadena), digamos ejecutando otro programa, o leyéndolo desde una conexión de red, etc., necesitará un intérprete o un compilador en tiempo de ejecución para Ejecute este programa.

Lisp tiene las tres características. Entonces, los sistemas Lisp siempre tienen un intérprete cargado en tiempo de ejecución. Los lenguajes Java y C # tienen nombres de funciones disponibles en tiempo de ejecución y tablas para buscar lo que significan. Probablemente, lenguajes como Basic y Python también tienen nombres de variables en tiempo de ejecución. (No estoy 100% seguro de eso).

Uday Reddy
fuente
¿Qué pasa si el "intérprete" se compila en el código? Por ejemplo, usando tablas de despacho para llamar a métodos virtuales, ¿son estos un ejemplo de interpretación o compilación?
Erwin Bolwidt
2
"ningún compilador o intérprete necesita estar presente en tiempo de ejecución", ¿eh? Bueno, si eso es cierto, entonces, en un sentido profundo, C tampoco se puede "compilar" en la mayoría de las plataformas. El tiempo de ejecución de C no tiene mucho que hacer: inicio, configurar pilas, etc., y apagado para el atexitprocesamiento. Pero todavía tiene que estar allí.
Seudónimo
1
"Los sistemas Lisp siempre tienen un intérprete cargado en tiempo de ejecución". - No necesariamente. Muchos sistemas Lisp tienen un compilador en tiempo de ejecución. Algunos ni siquiera tienen un intérprete en absoluto.
Jörg W Mittag
2
Buen intento, pero en.wikipedia.org/wiki/Lisp_machine#Technical_overview . Compilan Lisp y están diseñados para ejecutar el resultado de manera eficiente.
Peter - Restablece a Monica el
@ Seudónimo: El tiempo de ejecución de C es una biblioteca, no un compilador ni un intérprete.
Mooing Duck
8

Es posible que las respuestas actuales estén "pensando demasiado" en la declaración / respuestas. posiblemente a lo que se refieren los autores es al siguiente fenómeno. muchos idiomas tienen un comando "eval" como; Por ejemplo, consulte JavaScript Eval y su comportamiento se estudia comúnmente como una parte especial de la teoría CS (por ejemplo, Lisp). La función de este comando es evaluar la cadena en el contexto de la definición del lenguaje. por lo tanto, en efecto, tiene una similitud con un "compilador incorporado". el compilador no puede conocer el contenido de la cadena hasta el tiempo de ejecución. por lo tanto, no es posible compilar el resultado eval en el código de máquina en tiempo de compilación.

otras respuestas señalan que la distinción entre lenguajes interpretados y compilados puede difuminarse significativamente en muchos casos, especialmente con lenguajes más modernos como, por ejemplo, Java con un compilador "justo a tiempo", también conocido como "Hotspot" (los motores de JavaScript, por ejemplo, V8 utilizan cada vez más esta misma técnica). La funcionalidad "eval-like" es sin duda una de ellas.

vzn
fuente
2
V8 es un buen ejemplo. Es un compilador puro, nunca hay ninguna interpretación. Sin embargo, todavía admite la semántica completa de ECMAScript, incluso sin restricciones eval.
Jörg W Mittag
1
Lua hace lo mismo.
Mooing Duck
3

LISP es un ejemplo terrible, ya que fue concebido como una especie de lenguaje "máquina" de nivel superior como base para un lenguaje "real". Dicho lenguaje "real" nunca se materializó. Las máquinas LISP se construyeron con la idea de hacer (gran parte) de LISP en hardware. Como un intérprete de LISP es solo un programa, en principio es posible implementarlo en circuitos. No práctico, tal vez; pero lejos de ser imposible

Además, hay muchos intérpretes programados en silicio, normalmente llamados "CPU". Y a menudo es útil interpretar (aún no existe, no disponible, ...) códigos de máquina. Por ejemplo, Linux 'x86_64 se escribió y probó por primera vez en emuladores. Había distribuciones completas disponibles cuando los chips salieron al mercado, incluso solo para los primeros en adoptar / probar. Java a menudo se compila en código JVM, que es un intérprete que no sería demasiado difícil de escribir en silicio.

La mayoría de los idiomas "interpretados" se compilan en una forma interna, que se optimiza y luego se interpreta. Esto es, por ejemplo, lo que hacen Perl y Python. También hay compiladores para lenguajes interpretados destinados a ser, como el shell de Unix. Por otro lado, es posible interpretar idiomas compilados tradicionalmente. Un ejemplo un tanto extremo que vi fue un editor que usaba C interpretado como lenguaje de extensión. Es C podría ejecutar programas normales, pero simples, sin problemas.

Por otro lado, las CPU modernas incluso toman la entrada del "lenguaje de máquina" y la traducen en instrucciones de nivel inferior, que luego se reordenan y optimizan (es decir, "compilan") antes de entregarlas para su ejecución.

Toda esta distinción entre "compilador" y "intérprete" es realmente discutible, en algún lugar de la pila hay un intérprete definitivo que toma "código" y lo ejecuta "directamente". La entrada del programador sufre transformaciones a lo largo de la línea, cuál de ellos se llama "compilar" es simplemente dibujar una línea arbitraria en la arena.

vonbrand
fuente
1

La realidad es que hay una gran diferencia entre interpretar algún programa básico y ejecutar el ensamblador. Y hay áreas intermedias con el código P / código de bytes con o sin compiladores (justo a tiempo). Así que intentaré resumir algunos puntos en el contexto de esta realidad.

  • Si la forma en que se analiza el código fuente depende de las condiciones del tiempo de ejecución, puede ser imposible escribir un compilador, o tan difícil que nadie se molestará.

  • En general, el código que se modifica es imposible de compilar.

  • Un programa que utiliza una función similar a la evaluación generalmente no puede compilarse por completo por adelantado (si considera que la cadena que se le suministra como parte del programa), aunque si va a ejecutar el código evaluado repetidamente, aún puede ser útil para que su función eval-like invoque el compilador. Algunos idiomas proporcionan una API para el compilador para facilitar esto.

  • La capacidad de referirse a las cosas por su nombre no excluye la compilación, pero sí necesita tablas (como se mencionó). Llamar a las funciones por su nombre (como IDispatch) requiere mucho trabajo de fontanería, hasta el punto de que creo que la mayoría de la gente estaría de acuerdo en que estamos hablando efectivamente de un intérprete de llamadas de función.

  • La escritura débil (cualquiera que sea su definición) hace que la compilación sea más difícil y tal vez el resultado sea menos eficiente, pero a menudo no imposible, a menos que valores diferentes activen análisis diferentes. Aquí hay una escala móvil: si el compilador no puede deducir el tipo real, necesitará emitir ramas, llamadas a funciones y cosas que de otro modo no estarían allí, incrustando efectivamente bits de intérprete en el ejecutable.

Cobarde anónimo
fuente
1

Supongo que la característica principal de un lenguaje de programación que hace imposible un compilador para el lenguaje (en sentido estricto, ver también autohospedaje ) es la característica de auto modificación . Lo que significa que el lenguaje permite cambiar el código fuente durante el tiempo de ejecución (algo que un compilador que genera, fijo y estático, no puede hacer). Un ejemplo clásico es Lisp (ver también Homoiconicidad ). Se proporciona una funcionalidad similar utilizando una construcción de lenguaje como eval , incluida en muchos lenguajes (por ejemplo, javaScript). Eval realmente llama al intérprete (como una función) en tiempo de ejecución .

En otras palabras, el lenguaje puede representar su propio meta-sistema (ver también Metaprogramación )

Tenga en cuenta que la reflexión del lenguaje , en el sentido de consultar sobre metadatos de un cierto código fuente, y posiblemente modificar solo los metadatos, (algo así como el mecanismo de reflexión de Java o PHP) no es problemático para un compilador, ya que ya tiene esos metadatos en tiempo de compilación y puede ponerlos a disposición del programa compilado, según sea necesario, si es necesario.

Otra característica que hace que la compilación sea difícil o no la mejor opción (pero no imposible) es el esquema de escritura utilizado en el lenguaje (es decir, escritura dinámica frente a escritura estática y escritura fuerte frente a escritura suelta). Esto dificulta que el compilador tenga toda la semántica en tiempo de compilación, por lo que efectivamente una parte del compilador (en otras palabras, un intérprete) se convierte en parte del código generado que maneja la semántica en tiempo de ejecución . En otras palabras, esto no es compilación sino interpretación .

Nikos M.
fuente
LISP es un ejemplo terrible, ya que fue concebido como un sprt
vonbrand
@vonbrand, tal vez pero muestra tanto el concepto de homoiconicidad como la dualidad uniforme del código de datos
Nikos M.
-1

Siento que la pregunta original no está bien formada. Los autores de la pregunta pueden haber intentado hacer una pregunta algo diferente: ¿qué propiedades de un lenguaje de programación facilitan escribir un compilador para él?

Por ejemplo, es más fácil escribir un compilador para un lenguaje sin contexto que un lenguaje sensible al contexto. La gramática que define un idioma también puede tener problemas que dificultan la compilación, como las ambigüedades. Tales problemas pueden resolverse pero requieren un esfuerzo adicional. Del mismo modo, los lenguajes definidos por gramáticas sin restricciones son más difíciles de analizar que los lenguajes sensibles al contexto (ver Jerarquía de Chomsky ). Que yo sepa, los lenguajes de programación de procedimientos más utilizados están casi libres de contexto, pero tienen algunos elementos sensibles al contexto, lo que los hace relativamente fáciles de compilar.

Georgie
fuente
2
La pregunta es claramente la intención de oponerse / comparar compiladores e intérpretes. Si bien pueden funcionar de manera diferente, y generalmente lo hacen a excepción del caso límite de @Raphael anterior, tienen exactamente los mismos problemas con respecto al análisis de sintaxis y la ambigüedad. Entonces la sintaxis no puede ser el problema. También creo que el problema sintáctico no suele ser la principal preocupación en la redacción de compiladores hoy en día, aunque lo ha sido en el pasado. No soy el votante: prefiero comentar.
babou
-1

La pregunta tiene una respuesta correcta tan obvia que generalmente se pasa por alto como trivial. Pero sí importa en muchos contextos, y es la razón principal por la que existen los idiomas interpretados:

Compilar el código fuente en el código de la máquina es imposible si aún no tiene el código fuente.

Los intérpretes agregan flexibilidad y, en particular, agregan la flexibilidad de ejecutar código que no estaba disponible cuando se compiló el proyecto subyacente.

tylerl
fuente
2
"Perdí el código fuente" no es una propiedad de un lenguaje de programación sino de un programa en particular, por lo que eso no responde la pregunta. Y definitivamente necesita una cita para afirmar que evitar la pérdida del código fuente es "la razón principal por la que existen los idiomas interpretados", o incluso una razón por la que existen.
David Richerby
1
@DavidRicherby Supongo que el caso de uso que Tyleri tiene en mente es la interpretación interactiva, es decir, el código ingresado en tiempo de ejecución. Sin embargo, estoy de acuerdo en que eso está fuera del alcance de la pregunta, ya que no es una característica del lenguaje.
Rafael
@DavidRicherby y Raphael, digo que el autor de esta publicación implica (lo que describo en mi respuesta) como la característica de auto-modificación que, por supuesto, es una construcción del lenguaje por diseño y no un artefacto de algún programa específico
Nikos M.