¿Por qué no almacenamos el árbol de sintaxis en lugar del código fuente?

Tenemos muchos lenguajes de programación. Todos los idiomas se analizan y se verifica la sintaxis antes de traducirlos al código, por lo que se crea un árbol de sintaxis abstracta (AST).

Tenemos este árbol de sintaxis abstracta, ¿por qué no almacenamos este árbol de sintaxis en lugar del código fuente (o al lado del código fuente)?

Mediante el uso de un AST en lugar del código fuente. Cada programador de un equipo puede serializar este árbol a cualquier idioma que deseen (con la gramática libre de contexto apropiada) y analizar de nuevo a AST cuando hayan terminado. Esto eliminaría el debate sobre las preguntas de estilo de codificación (dónde colocar {y}, dónde poner espacios en blanco, sangría, etc.)

¿Cuáles son los pros y los contras de este enfoque?

Espacio en blanco y comentarios

En general, un AST no incluye espacios en blanco, terminadores de línea y comentarios.

Formato significativo

Tiene razón en que en la mayoría de los casos esto es positivo (elimina el formato de las guerras santas), hay muchos casos en los que el formato del código original transmite algún significado, como en los literales de cadena de varias líneas y los "párrafos de código" (separando bloques de declaraciones con una línea vacía).

Código que no se puede compilar

Si bien muchos analizadores son muy resistentes a la sintaxis faltante, el código con errores a menudo da como resultado un árbol de sintaxis muy extraño, que está bien hasta que el usuario vuelve a cargar el archivo. ¿Alguna vez cometió un error en su IDE y luego, de repente, todo el archivo tiene "garabatos"? Imagínese cómo se volvería a cargar en otro idioma.

Tal vez los usuarios no confirman código no analizable, pero ciertamente necesitan guardar localmente.

No hay dos idiomas que sean parejas perfectas

Como otros han señalado, casi no hay dos idiomas que tengan una paridad de características perfecta. Lo más parecido que puedo pensar es VB y C #, o JavaScript y CoffeeScript, pero incluso entonces VB tiene características como XML Literals que no tienen equivalentes en C #, y la conversión de JavaScript a CoffeeScript podría generar muchos literales de JavaScript.

En una aplicación de software que escribo, en realidad necesitamos hacer esto, ya que se espera que los usuarios ingresen expresiones de "inglés simple" que se convierten a JS en segundo plano. Consideramos solo almacenar la versión JS, pero no encontramos una forma aceptable de hacerlo que se cargara y descargara de manera confiable, por lo que terminamos siempre almacenando tanto el texto del usuario como la versión JS, así como un indicador que indicaba si el "inglés simple "versión analizada perfectamente o no.

¿Por qué no almacenamos este árbol de sintaxis en lugar del código fuente? Todos los programadores de un equipo pueden serializar este árbol a cualquier idioma, lo deseen y analizar de nuevo a AST cuando hayan terminado.

De hecho, esa es una idea razonable. Microsoft tenía un proyecto de investigación en la década de 1990 para hacer casi exactamente eso .

Se me ocurren varios escenarios.

El primero es bastante trivial; como usted dice, puede hacer que el AST se muestre en diferentes vistas dependiendo de las preferencias de los diferentes programadores para cosas como el espaciado, etc. Pero almacenar un AST es excesivo para ese escenario; solo escríbete una bonita impresora. Cuando cargue un archivo en su editor, ejecute la bonita impresora para ponerlo en su formato preferido y vuelva al formato original cuando lo guarde.

El segundo es más interesante. Si puede almacenar el árbol de sintaxis abstracta, el cambio de código no será textual sino sintáctico. Las refactorizaciones donde se mueve el código se vuelven mucho más fáciles de entender. El inconveniente es, por supuesto, que escribir los algoritmos de diferencias de árbol no es exactamente trivial y, a menudo, debe hacerse por idioma. Text diff funciona para casi cualquier idioma.

El tercero es más parecido a lo que Simonyi imaginó para la programación intencional: que los conceptos fundamentales comunes a los lenguajes de programación son los que se serializan, y luego tiene diferentes puntos de vista de esos conceptos representados en diferentes lenguajes. Aunque es una idea hermosa, el hecho feo es que los idiomas son lo suficientemente diferentes en sus detalles que un enfoque de mínimo común denominador realmente no funciona.

En resumen, es una idea encantadora, pero es una enorme cantidad de trabajo adicional para un beneficio comparativamente pequeño. Por eso casi nadie lo hace.

Se podría argumentar que esto es exactamente lo que el código de bytes está en .NET. De hecho, el programa reflector de redgate traduce el código de bytes a una variedad de lenguajes de programación .NET.

Sin embargo, hay problemas. La sintaxis es específica del idioma en la medida en que hay cosas que puede representar en un idioma que no tienen representación en otros idiomas. Esto ocurre en .NET con C ++ como el único lenguaje .NET que tiene acceso a los 7 niveles de acceso.

Fuera del entorno .NET se vuelve mucho más complicado. Cada idioma comienza a tener su propio conjunto de bibliotecas asociadas. No sería posible reflejar una sintaxis genérica en C y Java que reflejara la misma ejecución de instrucciones, ya que resuelven problemas simulares de maneras muy diferentes.

Me gusta algo de tu idea, pero estás sobreestimando significativamente lo fácil que es traducir un idioma a otro. Si fuera tan fácil, ni siquiera necesitaría almacenar el AST, ya que siempre podría analizar el lenguaje X en el AST y luego pasar del AST al lenguaje Y.

Sin embargo, deseo que las especificaciones del compilador hayan pensado un poco más en exponer parte de AST a través de algún tipo de API. Cosas como la programación orientada a aspectos, la refactorización y el análisis de programas estáticos podrían implementarse a través de dicha API, sin que el implementador de esas capacidades tenga que rehacer gran parte del trabajo ya implementado por los compiladores.

Es extraño con qué frecuencia la estructura de datos del programador para representar un programa es como un grupo de archivos que contienen cadenas.

Creo que los puntos más destacados son aquellos:

• No hay beneficio Dijiste que significaría que todos podrían usar su lenguaje favorito. Pero eso no es cierto : el uso de una representación de árbol de sintaxis eliminaría solo las diferencias sintácticas, pero no las semánticas. Funciona hasta cierto punto para lenguajes muy similares, como VB y C #, o Java y Scala. Pero ni siquiera allí por completo.

• Es problemático Has ganado libertad de lenguaje, pero has perdido la libertad de herramientas. Ya no puede leer y editar el código en un editor de texto, ni siquiera en ningún IDE; depende de una herramienta específica que dice su representación AST para leer y editar el código. No se gana nada aquí.

  Para ilustrar este último punto, eche un vistazo a RealBasic, que es una implementación patentada de un poderoso dialecto BASIC. Durante un tiempo, casi parecía que el lenguaje podía despegar, pero era completamente dependiente del proveedor, hasta el punto de que solo podía ver el código en su IDE, ya que estaba guardado en un formato patentado sin texto. Gran error

Creo que si almacena tanto el texto como el AST, entonces realmente no ha agregado nada útil, ya que el texto ya está allí en un idioma, y ​​el AST puede reconstruirse rápidamente a partir del texto.

Por otro lado, si solo almacena el AST, pierde cosas como comentarios que no se pueden recuperar.

Creo que la idea es interesante en teoría pero no muy práctica ya que diferentes lenguajes de programación admiten diferentes construcciones, algunas de las cuales no tienen equivalentes en otros lenguajes.

Por ejemplo, X ++ tiene una instrucción 'while select' que no se podría escribir en C # sin mucho código adicional (clases adicionales, lógica adicional, etc.). http://msdn.microsoft.com/en-us/library/aa558063.aspx

Lo que digo aquí es que muchos idiomas tienen azúcares sintácticos que se traducen en grandes bloques de código del mismo idioma o incluso elementos que no existen en absoluto en otros. Aquí hay un ejemplo de por qué el enfoque AST no funcionará:

El lenguaje X tiene una palabra clave K que se traduce, en AST en 4 declaraciones: S1, S2, S3 y S4. El AST ahora se traduce en el lenguaje Y y un programador cambia S2. Ahora, ¿qué pasa con la traducción de regreso a X? El código se traduce como 4 declaraciones en lugar de una sola palabra clave ...

El último argumento en contra del enfoque AST son las funciones de la plataforma: ¿qué sucede cuando una función está integrada en la plataforma? Al igual que .NET's Environment.GetEnvironmentVariable. ¿Cómo lo traduces?

Hay un sistema construido alrededor de esta idea: JetBrains MPS . Un editor es un poco extraño, o simplemente diferente, pero en general no es un problema tan grande. El mayor problema es, así, que no es un texto más, así que no se puede utilizar cualquiera de las herramientas normales basados en texto - otros editores, grep, sed, fusionar y diff herramientas, etc.

En realidad, hay varios productos, generalmente conocidos como "bancos de trabajo de idiomas" que almacenan AST y presentan, en sus editores, una "proyección" del AST en un idioma en particular. Como dijo @ sk-logic, el MPS de JetBrains es uno de esos sistemas. Otro es el banco de trabajo intencional de Intentional Software.

El potencial para los bancos de trabajo de idiomas parece muy alto, particularmente en el área de lenguajes específicos de dominio, ya que puede crear una proyección específica de dominio. Por ejemplo, Intentional muestra un DSL relacionado con la electricidad que se proyecta como un diagrama de circuito, mucho más fácil y más preciso para que un experto en dominio lo discuta y critique que un circuito descrito en un lenguaje de programación basado en texto.

En la práctica, los bancos de trabajo de idiomas han tardado en ponerse al día porque, aparte del trabajo de DSL, los desarrolladores probablemente preferirían trabajar en un lenguaje de programación general y familiar. Cuando se comparan cara a cara con un editor de texto o IDE de programación, los bancos de trabajo de idiomas tienen toneladas de sobrecarga y sus ventajas no son tan claras. Ninguno de los bancos de trabajo de idiomas que he visto se ha abrochado hasta el punto en que pueden extender fácilmente sus propios IDE, es decir, si los bancos de trabajo de idiomas son excelentes para la productividad, ¿por qué las herramientas del banco de trabajo de idiomas no han mejorado? -y-mejor a tasas cada vez más rápidas?

Has estado leyendo mi mente.

Cuando tomé un curso de compiladores, hace unos años, descubrí que si tomas un AST y lo serializas, con notación de prefijo en lugar de la notación infija habitual, y usas paréntesis para delimitar declaraciones enteras, obtienes Lisp. Si bien había aprendido sobre Scheme (un dialecto de Lisp) en mis estudios de pregrado, nunca realmente lo había apreciado. Definitivamente gané un aprecio por Lisp y sus dialectos, como resultado de ese curso.

Problemas con lo que propones:

1. Es difícil / lento componer un AST en un entorno gráfico. Después de todo, la mayoría de nosotros podemos escribir más rápido de lo que podemos mover un mouse. Y, sin embargo, una pregunta emergente es "¿cómo se escribe el código del programa con una tableta?" Escribir en una tableta es lento / engorroso, en comparación con un teclado / computadora portátil con un teclado de hardware. Si pudiera crear un AST arrastrando y soltando componentes de una paleta en un lienzo en un dispositivo grande con pantalla táctil, la programación en una tableta podría convertirse en algo real.

2. pocas / ninguna de nuestras herramientas existentes soportan esto. Tenemos décadas de desarrollo envueltos en la creación de IDE cada vez más complejos y editores cada vez más inteligentes. Tenemos todas estas herramientas para reformatear texto, comparar texto, buscar texto. ¿Dónde están las herramientas que pueden hacer el equivalente de una búsqueda de expresión regular a través de un árbol? ¿O una diferencia de dos árboles? Todas estas cosas se hacen fácilmente con texto. Pero solo pueden comparar las palabras. Cambie el nombre de una variable, de modo que las palabras sean diferentes pero el significado semántico sea el mismo, y esas herramientas diff se encuentren en problemas. Dichas herramientas, desarrolladas para operar en AST en lugar de texto, le permitirán acercarse a la comparación del significado semántico. Eso sería algo bueno.

3. mientras que convertir el código fuente del programa en un AST es relativamente bien entendido (tenemos compiladores e intérpretes, ¿no?), convertir un AST en un código de programa no es tan bien entendido. Multiplicar dos números primos para obtener un número compuesto grande es relativamente sencillo, pero factorizar un número compuesto grande en primos es mucho más difícil; ahí es donde estamos analizando y descompilando AST. Ahí es donde las diferencias entre idiomas se convierten en un problema. Incluso dentro de un idioma en particular, hay múltiples formas de descompilar un AST. Iterando a través de una colección de objetos y obteniendo algún tipo de resultado, por ejemplo. ¿Usar un bucle for, iterando a través de una matriz? Eso sería compacto y rápido, pero hay limitaciones. Use un iterador de algún tipo, operando en una colección? Esa colección podría ser de tamaño variable, lo que agrega flexibilidad a expensas (posibles) de la velocidad. ¿Mapa reducido? Más complejo, pero implícitamente paralelo. Y eso es solo para Java, dependiendo de sus preferencias.

Con el tiempo, el esfuerzo de desarrollo se gastará y estaremos desarrollando utilizando pantallas táctiles y AST. Escribir será menos necesario. Veo eso como una progresión lógica desde donde estamos, mirando cómo usamos las computadoras, hoy, eso resolverá el # 1.

Ya estamos trabajando con árboles. Lisp es simplemente AST serializados. XML (y HTML, por extensión) es solo un árbol serializado. Para hacer búsquedas, ya tenemos un par de prototipos: XPath y CSS (para XML y HTML, respectivamente). Cuando se crean herramientas gráficas que nos permiten crear selectores y modificadores de estilo CSS, habremos resuelto parte de # 2. Cuando esos selectores se puedan extender para admitir expresiones regulares, estaremos más cerca. Todavía estoy buscando una buena herramienta gráfica de diferencias para comparar dos documentos XML o HTML. A medida que las personas desarrollen esas herramientas, se podrá resolver el n. ° 2. La gente ya está trabajando en esas cosas; simplemente no están allí, todavía.

La única forma en que puedo ver para poder descompilar esos AST en el texto del lenguaje de programación sería buscar objetivos. Si estoy modificando el código existente, el objetivo podría lograrse mediante un algoritmo que haga que mi código modificado sea lo más similar posible al código de inicio (diferencia textual mínima). Si escribo código desde cero, el objetivo podría ser el código más pequeño y ajustado (probablemente un bucle for). O podría ser un código que paraleliza de la manera más eficiente posible (probablemente un mapa / reducción o algo relacionado con CSP). Por lo tanto, el mismo AST podría resultar en un código significativamente diferente, incluso en el mismo idioma, en función de cómo se establecieron los objetivos. El desarrollo de tal sistema resolvería el # 3. Sería computacionalmente complejo, lo que significa que probablemente necesitaríamos algún tipo de disposición cliente-servidor,

Si su intención es eliminar el debate sobre los estilos de formato, entonces quizás lo que quiera es un editor que lea en un archivo fuente, lo formatee según sus preferencias personales para mostrarlo y editarlo, pero al guardarlo, reformatea el estilo elegido por el equipo usos.

Es bastante fácil si usa un editor como Emacs . Cambiar el estilo de formato de un archivo completo es un trabajo de tres comandos.

También debe poder construir los ganchos para transformar automáticamente un archivo a su propio estilo al cargar, y transformarlo al estilo del equipo al guardar.

Es difícil leer y modificar un AST, en lugar del código fuente.

Sin embargo, algunas herramientas relacionadas con el compilador permiten usar el AST. Java bytecode y .NET Intermediate code funcionan de manera similar a un AST.

Es una buena idea; pero el AST de cada idioma es diferente de todos los demás.

La única excepción que conozco es para VB.NET y C #, donde Microsoft argumenta que son "exactamente el mismo lenguaje con diferente sintaxis". Incluso otros lenguajes .NET (IronPython, F #, lo que sea) son diferentes en el nivel AST.

Lo mismo con los lenguajes JVM, todos apuntan al mismo código de bytes, pero las construcciones del lenguaje son diferentes, lo que hace que sean diferentes idiomas y diferentes AST.

Incluso los lenguajes de 'capa fina', como CoffeScript y Xtend, comparten gran parte de la teoría de los lenguajes subyacentes (JavaScript y Java, respectivamente); pero introduce conceptos de nivel superior que son (o deberían ser) retenidos en el nivel AST.

Si Xtend pudiera reconstruirse a partir de un AST de Java, creo que se habría definido como un 'descompilador' de Java a Xtend que crea mágicamente abstracciones de mayor nivel del código Java existente, ¿no crees?