¿Por qué es más fácil escribir un compilador en un lenguaje funcional?

He estado pensando en esta pregunta por mucho tiempo, pero realmente no he podido encontrar la respuesta en Google y una pregunta similar en Stackoverflow. Si hay un duplicado, lo siento por eso.¿Por qué es más fácil escribir un compilador en un lenguaje funcional?

Mucha gente parece decir que escribir compiladores y otras herramientas de lenguaje en lenguajes funcionales como OCaml y Haskell es mucho más eficiente y fácil que escribirlas en idiomas imperativos.

¿Es esto cierto? Y si es así, ¿por qué es tan eficiente y fácil escribirlos en idiomas funcionales en lugar de en un lenguaje imperativo, como C? Además, ¿no es una herramienta de lenguaje en un lenguaje funcional más lenta que en algún lenguaje de bajo nivel como C?

Fuente

2010-05-25 wvd

No diría que es más fácil. Pero la naturaleza funcional de las tareas de compilación, como el análisis sintáctico, probablemente se presten naturalmente a la programación funcional. Los lenguajes funcionales como OCaml pueden ser extremadamente rápidos, rivalizando con la velocidad de C. –

+15

Gente, ¿esto es realmente discutidor? Seguramente alguien tiene alguna idea. Me gustaría conocerme a mí mismo. –

Creo que al menos debería haber algunas buenas razones para usar un lenguaje funcional por encima de uno imperativo. He encontrado un artículo que básicamente se basa en que los lenguajes funcionales no tienen efectos secundarios y tal. Pero no estaba realmente claro en absoluto. Sin embargo, si esto es argumentativo, entonces sería mejor cerrarlo o reformular la pregunta. – wvd

Muchas veces un compilador trabaja mucho con árboles. El código fuente se analiza en un árbol de sintaxis. Ese árbol podría transformarse en otro árbol con anotaciones de tipo para realizar la comprobación de tipos. Ahora puede convertir ese árbol en un árbol que solo contenga elementos del lenguaje central (convirtiendo las notaciones sintácticas tipo azúcar en una forma no apareada). Ahora puede realizar varias optimizaciones que son básicamente transformaciones en el árbol. Después de eso, probablemente crees un árbol en una forma normal y luego iteras sobre ese árbol para crear el código de objetivo (ensamblaje).

El lenguaje funcional tiene funciones como la coincidencia de patrones y un buen soporte para la recursión eficiente, lo que facilita el trabajo con árboles, por lo que generalmente se los considera buenos lenguajes para escribir compiladores.

Fuente

2010-05-25 15:40:04 sepp2k

La respuesta más completa hasta el momento, marcaré esto como la respuesta aceptada, sin embargo, creo que la respuesta de Pete Kirkham también es buena. – wvd

¿Qué pasa con "probar la corrección", ya que la corrección de un compilador es un atributo importante, a menudo he oído que los fanáticos de los lenguajes funcionales incorporan una "prueba" de corrección en su flujo de trabajo de alguna manera. No tengo idea de lo que realmente significa en términos prácticos, pero como la fiabilidad del compilador es importante, parece que vale la pena. –

@WarrenP: El concepto de "código de prueba" proviene de los lenguajes funcionales de tipo estático. La idea es que use el sistema de tipos de tal manera que una función solo pueda verificar si es correcta, de modo que el hecho de que el código se compile es la prueba de la corrección. Por supuesto, esto no es totalmente posible mientras se mantiene el lenguaje turing-complete y typechecking decidable. Pero cuanto más fuerte es el sistema de tipos, más cerca se puede llegar a ese objetivo. – sepp2k

Muchas de las tareas del compilador son coincidencia de patrones en estructuras de árbol.

Tanto OCaml como Haskell tienen potentes y concisas funciones de coincidencia de patrones.

Es más difícil agregar patrones que coincidan con los lenguajes imperativos, ya que cualquier valor que se evalúe o extraiga para que coincida con el patrón debe ser libre de efectos secundarios.

Fuente

2010-05-25 15:37:04

Suena como una respuesta razonable, pero ¿es esto lo único? p.ej. ¿Cosas como la recursividad de la cola también juegan un papel? – wvd

Eso parecería indicar que es más un problema del sistema de tipo que del modelo de ejecución real. Algo basado en la programación imperativa con valores inmutables sobre tipos estructurales podría estar bien. –

@wvd: optimización de recursividad de cola es un detalle de implementación, no una función de lenguaje como tal, que hace funciones recursivas lineales equivalentes a un bucle iterativo. Una función recursiva para recorrer una lista enlazada en C se beneficiaría tanto como recursivamente en una lista en Scheme. –

Un factor importante a tener en cuenta es que una gran parte de cualquier proyecto de compilación es cuando puede autoevaluar el compilador y "comer su propia comida para perros". Por esta razón, cuando observa idiomas como OCaml, donde están diseñados para la investigación de idiomas, tienden a tener excelentes características para problemas de compilación.

En mi último trabajo al estilo del compilador utilizamos OCaml exactamente por este motivo mientras manipulamos el código C, era simplemente la mejor herramienta para la tarea. Si la gente de INRIA hubiera construido OCaml con diferentes prioridades, podría no haber sido tan buena opción.

Dicho esto, los lenguajes funcionales son la mejor herramienta para resolver cualquier problema, por lo que lógicamente se deduce que son la mejor herramienta para resolver este problema en particular. QED.

/Me: se arrastra de nuevo a mis tareas Java un poco menos con alegría ...

Fuente

2010-05-25 15:51:25 Ukko

-1 para "los lenguajes funcionales son la mejor herramienta para resolver cualquier problema". Si esto fuera cierto, todos los estaríamos usando en todas partes. ;) –

+15

@Andrei Krotkov: Palabra de hoy del día es fa · ce · cioso Pronunciación: \ fə-SE-shəs \ Función: adjetivo Etimología: facetieux francesa Medio, desde broma facetie, del latín facetia Fecha: 1599 1: broma o bromear a menudo inapropiada: waggish 2: destinado a ser humorístico o divertido: no graves sinónimos ver ingenioso Además de la falta broma, su lógica es todavía imperfecto . Estás asumiendo que todas las personas son actores racionales, y que me temo que no es una suposición justa. – Ukko

Supongo que me perdí la broma, ya que conozco personas en la vida real que dirían casi lo mismo, excepto completamente en serio. La ley de Poe, supongo. http://tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw –

Ver también

F# design pattern

FP grupos de cosas 'por la operación', mientras que los grupos OO cosas 'por tipo ', y' por operación 'es más natural para un compilador/intérprete.

Fuente

2010-05-25 16:26:47 Brian

Esto se relaciona con lo que se llama, en algunos círculos de Teoría del Lenguaje de Programación, el "problema de expresión". Por ejemplo, vea [esta pregunta] (http: // stackoverflow.com/questions/2807629 /), donde demuestro un código Haskell verdaderamente horrible que hace las cosas de la forma de los "tipos extensibles". Por el contrario, forzar un lenguaje OOP en el estilo de "operaciones extensibles" tiende a motivar el patrón de visitante. –

Parece que todos olvidaron otra razón importante. Es bastante fácil escribir un lenguaje específico de dominio incrustado (EDSL) para analizadores que se parecen mucho (E) a BNF en código normal.Los combinadores de analizador como Parsec son bastante fáciles de escribir en idiomas funcionales utilizando funciones de orden superior y composición de funciones. No solo es más fácil pero muy elegante.

Básicamente se representan los más simples analizadores genéricos que sólo las funciones y tiene operaciones especiales (por lo general funciones de orden superior), que le permiten componer estos analizadores primitivas en programas de análisis más complicados, más específicos para su gramática.

Esta no es la única forma de hacer frameworks parer de curso.

Fuente

2010-05-25 16:29:47

Básicamente, un compilador es una transformación de un conjunto de códigos a otro: de origen a IR, de IR a IR optimizado, de IR a ensamblaje, etc. Este es precisamente el tipo de cosas para las que están diseñados los lenguajes funcionales: una función pura es solo una transformación de una cosa a otra. Las funciones imperativas no tienen esta calidad. Aunque puede escribir este tipo de código en un lenguaje imperativo, los lenguajes funcionales están especializados para ello.

Fuente

2010-05-25 16:53:39 Chuck

Una posibilidad es que un compilador tenga que tratar con mucho cuidado una gran cantidad de casos de esquina. Obtener el código correcto a menudo es más fácil mediante el uso de patrones de diseño que estructuran la implementación de una manera que es paralela a las reglas que implementa. A menudo eso termina siendo un diseño declarativo (coincidencia de patrones, "dónde") en lugar de imperativo (secuenciación, "cuando") y, por lo tanto, más fácil de implementar en un lenguaje declarativo (y la mayoría de ellos son funcionales).

Fuente

2010-05-25 17:03:18 BCS

¿Por qué es más fácil escribir un compilador en un lenguaje funcional?

Respuesta

Cuestiones relacionadas