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

88

He estado pensando en esta pregunta por mucho tiempo, pero realmente no pude encontrar la respuesta en Google y 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 fácil que escribirlos en lenguajes imperativos.

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

compiler-construction haskell ocaml functional-programming wvd
fuente
5
No diría que es más fácil. Pero la naturaleza funcional de las tareas de compilación, como el análisis, probablemente se preste con bastante naturalidad a la programación funcional. Los lenguajes funcionales como OCaml pueden ser extremadamente rápidos, rivalizando con la velocidad de C.
Robert Harvey
17
Amigos, ¿esto es realmente polémico? Seguramente alguien tiene alguna idea. Me gustaría conocerme a mí mismo.
Robert Harvey
Creo que debería haber al menos algunas buenas razones para usar un lenguaje funcional en lugar de uno imperativo. Encontré un artículo que básicamente se refería a que los lenguajes funcionales no tienen efectos secundarios y cosas así. Pero no estaba del todo claro. Sin embargo, si esto es discutible, entonces sería mejor cerrarlo o reformular la pregunta.
wvd
12
¿Es realmente discutible reconocer que algunos nichos se adaptan mejor a un estilo particular de lenguaje? "¿Por qué C es mejor que Javascript para escribir controladores de dispositivos" no sería controvertido, creo ...
CA McCann
1
Pensé que sería todo lo contrario. Estoy leyendo "compilador súper pequeño" y usa mutación variable por todas partes.
Rolf

Respuestas:

101

A menudo, 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 verificación de tipos. Ahora puede convertir ese árbol en un árbol que solo contenga elementos básicos del lenguaje (convirtiendo notaciones sintácticas similares a azúcar en una forma sin azúcar). Ahora puede realizar varias optimizaciones que son básicamente transformaciones en el árbol. Después de eso, probablemente crearía un árbol en alguna forma normal y luego iteraría sobre ese árbol para crear el código de destino (ensamblaje).

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 eso generalmente se consideran buenos lenguajes para escribir compiladores.

sepp2k
fuente
La respuesta más completa hasta ahora, la marcaré como la respuesta aceptada, sin embargo, creo que la respuesta de Pete Kirkham también es buena.
wvd
1
¿Qué hay de "probar la corrección", dado que la corrección de un compilador es un atributo importante, a menudo he escuchado 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 eso significa realmente en términos prácticos, pero como la confiabilidad del compilador es importante, parece que vale la pena.
Warren P
3
@WarrenP: El concepto de "código portador de pruebas" proviene de 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 el tipo si es correcto, por lo que el hecho de que el código se compile es la prueba de la corrección. Por supuesto, esto no es del todo posible si se mantiene el turing completo del lenguaje y la verificación de tipos decidibles. Pero cuanto más fuerte sea el sistema de tipos, más te acercarás a ese objetivo.
sepp2k
3
La razón por la que este concepto es principalmente popular en la comunidad funcional es que en los lenguajes con estado mutable, también tendría que codificar información sobre cuándo y dónde ocurre el cambio de estado en los tipos. En los lenguajes en los que sabe que el resultado de una función solo depende de sus argumentos, es mucho más fácil codificar una prueba en los tipos (también es mucho más fácil probar manualmente la corrección del código porque no tiene que considerar qué estado global es posible y cómo afectará al comportamiento de la función). Sin embargo, nada de esto está relacionado específicamente con los compiladores.
sepp2k
3
En mi opinión, la característica más importante es la coincidencia de patrones. Optimizar un árbol de sintaxis abstracto con coincidencia de patrones es estúpidamente fácil. Hacerlo sin la coincidencia de patrones a menudo es frustrantemente difícil.
Bob Aman
38

Muchas tareas del compilador coinciden con patrones en estructuras de árbol.

Tanto OCaml como Haskell tienen capacidades de coincidencia de patrones poderosas y concisas.

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

Pete Kirkham
fuente
Suena como una respuesta razonable, pero ¿es esto lo único? por ejemplo, ¿cosas como la recursividad de la cola también jugarían un papel?
wvd
Eso parecería indicar que se trata más de un problema del sistema de tipos que del modelo de ejecución real. Algo basado en programación imperativa con valores inmutables sobre tipos estructurales podría estar bien.
Donal Fellows
@wvd: La optimización de recursividad de cola es un detalle de implementación, no una característica del lenguaje como tal, que hace que las funciones recursivas lineales sean equivalentes a un ciclo iterativo. Una función recursiva para recorrer una lista enlazada en C se beneficiaría tanto como lo hace la recursión en una lista en Scheme.
CA McCann
@wvd gcc C tiene eliminación de llamadas de cola, al igual que otros lenguajes de estado mutables
Pete Kirkham
3
@camccann: Si el estándar del lenguaje garantiza tco (o al menos garantiza que las funciones recursivas de una determinada forma nunca causarán un desbordamiento de pila o un crecimiento lineal del consumo de memoria), lo consideraría una característica del lenguaje. Si el estándar no lo garantiza, pero el compilador lo hace de todos modos, es una característica del compilador.
sepp2k
15

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

En mi último trabajo de compilador, usamos OCaml exactamente por esta razón mientras manipulamos el código C, era la mejor herramienta para la tarea. Si la gente de INRIA hubiera construido OCaml con diferentes prioridades, podría no haber sido una 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: vuelve a mis tareas de Java con menos alegría ...

Ukko
fuente
4
-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. ;)
Andrei Krotkov
15
@Andrei Krotkov: La palabra del día de hoy es fa · ce · tious Pronunciación: \ fə-ˈsē-shəs \ Función: adjetivo Etimología: francés medio facetieux, de facetie jest, del latín facetia Fecha: 1599 1: bromear o bromear a menudo de manera inapropiada : waggish <solo ser gracioso> 2: destinado a ser humorístico o divertido: no serio <a comentario gracioso> sinónimos ver ingenioso Además de perderse el chiste, su lógica sigue siendo defectuosa. Está asumiendo que todas las personas son actores racionales y, me temo, no es una suposición justa.
Ukko
5
Supongo que me perdí la broma, ya que conozco personas en la vida real que dirían más o menos exactamente lo mismo, excepto que en serio. La ley de Poe, supongo. tvtropes.org/pmwiki/pmwiki.php/Main/PoesLaw
Andrei Krotkov
13
@Andrei: Usando su argumentum ad populum : "Si la razón es mejor que la ignorancia emocional, todos la usaríamos en todas partes".
Tim Schaeffer
9

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 ensamblador, 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 cualidad. Aunque puede escribir este tipo de código en un lenguaje imperativo, los lenguajes funcionales están especializados para ello.

Arrojar
fuente
6

Ver también

Patrón de diseño F #

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.

Brian
fuente
3
Esto se relaciona con lo que se llama, en algunos círculos de la teoría del lenguaje de programación, el "problema de expresión". Por ejemplo, vea esta pregunta , en la que demuestro un código Haskell verdaderamente horrible que hace las cosas a la manera de "tipos extensibles". Por el contrario, forzar un lenguaje de programación orientada a objetos en el estilo de "operaciones extensibles" tiende a motivar el patrón de visitantes.
CA McCann
6

Una posibilidad es que un compilador tiende a tener que tratar con mucho cuidado una gran cantidad de casos de esquina. Obtener el código correcto a menudo se facilita mediante el uso de patrones de diseño que estructuran la implementación de una manera que se asemeja 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, es más fácil de implementar en un lenguaje declarativo (y la mayoría de ellos son funcionales).

BCS
fuente
4

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

Básicamente, usted representa los analizadores sintácticos genéricos más simples como solo funciones y tiene operaciones especiales (típicamente funciones de orden superior) que le permiten componer estos analizadores sintácticos primitivos en analizadores sintácticos más complicados y específicos para su gramática.

Por supuesto, esta no es la única forma de hacer marcos parer.

snk_kid
fuente