¿Por qué es más fácil escribir un compilador en un lenguaje funcional? [cerrado]
He estado pensando en esta pregunta mucho tiempo, pero realmente no pude encontrar la respuesta en Google, así como una pregunta similar en Stackoverflow. Si hay un duplicado, lo siento.
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 más fácil que escribirlos en lenguajes imperativos.
¿Es esto cierto? Y si es así why ¿por qué es tan eficiente y fácil de escribir en lenguajes 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 un lenguaje de bajo nivel como C?
7 answers
Muchas veces un compilador trabaja mucho con árboles. El código fuente se analiza en un árbol de sintaxis. Ese árbol puede ser transformado en otro árbol con anotaciones de tipo para realizar la comprobación de tipo. Ahora puede convertir ese árbol en un árbol que solo contenga elementos del lenguaje principal (convirtiendo notaciones sintácticas similares a azúcar en una forma no asignada). Ahora puede realizar varias optimizaciones que son básicamente transformaciones en el árbol. Después de eso, probablemente crearía un árbol en algunos forma normal y luego iterar sobre ese árbol para crear el código de destino (ensamblado).
El lenguaje funcional tiene características como la coincidencia de patrones y un buen soporte para la recursividad eficiente, lo que facilita el trabajo con árboles, por lo que generalmente se consideran buenos lenguajes para escribir compiladores.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-05-25 15:40:04
Muchas tareas del compilador son coincidencias de patrones en estructuras de árbol.
Tanto OCaml como Haskell tienen potentes y concisas capacidades de coincidencia de patrones.
Es más difícil agregar coincidencia de patrones a lenguajes imperativos, ya que cualquier valor que se esté evaluando o extrayendo para que coincida con el patrón debe estar libre de efectos secundarios.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-05-25 15:40:12
Un factor importante a considerar es que una gran parte de cualquier proyecto de compilador es cuando se puede auto-alojar el compilador y "comer su propia comida para perros."Por esta razón, cuando nos fijamos en lenguajes como OCaml, donde están diseñados para la investigación de lenguajes, tienden a tener grandes características para problemas de tipo compilador.
En mi último trabajo de compilador usamos OCaml exactamente por esta razón mientras manipulábamos código C, era la mejor herramienta para la tarea. Si la gente de INRIA tuviera construido OCaml con diferentes prioridades podría no haber sido un buen ajuste.
Dicho esto, los lenguajes funcionales son la mejor herramienta para resolver cualquier problema, por lo que lógicamente se sigue que son la mejor herramienta para resolver este problema en particular. QED.
/me: se arrastra de vuelta a mis tareas de Java con un poco menos de alegría...
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-08-09 09:53:18
Básicamente, un compilador es una transformación de un conjunto de código a otro: de fuente a IR, de IR a IR optimizado, de IR a ensamblado, etc. Este es precisamente el tipo de cosa para la 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 cualidad. Aunque puede escribir este tipo de código en un lenguaje imperativo, los lenguajes funcionales están especializados para ello.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-05-25 16:53:39
Véase también
FP agrupa cosas 'por operación', mientras que OO agrupa cosas 'por tipo', y 'por operación' es más natural para un compilador/intérprete.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:02:56
Una posibilidad es que un compilador tiende a tener que tratar con mucho cuidado con toda una serie de casos de esquina. Obtener el código correcto a menudo se hace más fácil mediante el uso de patrones de diseño que estructuran la implementación de una manera 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, "cuándo") y, por lo tanto, más fácil de implementar en un lenguaje declarativo (y la mayoría de ellos son funcionales).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-05-25 17:03:18
Parece que todos se perdieron otra razón importante. Es bastante fácil escribir un lenguaje específico de dominio incrustado (EDSL) para analizadores que se parecen mucho a (E)BNF en código normal. Los combinadores de Parser como Parsec son bastante fáciles de escribir en lenguajes funcionales usando funciones de orden superior y composición de funciones. No solo más fácil, sino muy elegante.
Básicamente representas los analizadores genéricos más simples como solo funciones y tienes operaciones especiales (típicamente funciones de orden superior) que le permitencomponer estos analizadores primitivos en analizadores más complicados y específicos para su gramática.
Esta no es la única manera de hacer frameworks parer, por supuesto.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-05-25 16:34:56