¿Cómo son los lenguajes imperativos más diferentes entre sí que los lenguajes funcionales?

17

Estoy leyendo La implementación de los lenguajes de programación funcional de Simon Peyton Jones y hay una declaración que me sorprendió un poco (en la página 39):

En un grado mucho mayor que el caso de los lenguajes imperativos, los lenguajes funcionales son en gran medida variaciones sintácticas entre sí, con relativamente pocas diferencias semánticas.

Ahora, esto fue escrito en 1987 y mis pensamientos sobre este tema podrían estar influenciados por lenguajes de programación más modernos que no existían ni eran populares en ese momento. Sin embargo, me parece un poco difícil de creer. Por ejemplo, creo que el lenguaje de programación Miranda descrito (uno de los primeros predecesores de Haskell) tiene una semántica mucho más diferente en comparación con un lenguaje estricto como ML que decir que C tiene que con Pascal o tal vez incluso C tiene que hablar en pequeño (aunque cederé eso C ++ proporciona alguna validación de su punto :-).

Pero, de nuevo, estoy basando esto en mi comprensión intuitiva. ¿Simon Peyton Jones está en lo correcto al decir esto, o es un punto controvertido?

Jason
fuente

Respuestas:

19

Simon es básicamente correcto, desde un punto de vista extensional. Sabemos bastante bien cuál es la semántica de los lenguajes funcionales modernos, y realmente son variaciones relativamente pequeñas entre sí: cada uno representa traducciones ligeramente diferentes en un metalenguaje monádico. Incluso un lenguaje como Scheme (un lenguaje imperativo de orden superior de tipo dinámico con control de primera clase) tiene una semántica muy parecida a la de ML y Haskell.

V

Pero para llegar a una categoría adecuada para interpretar lenguajes funcionales mecanografiados modernos, las cosas se ponen bastante aterradoras. Básicamente, terminas construyendo una categoría enriquecida ultramétrica de relaciones de equivalencia parcial sobre este dominio. (Como ejemplo, vea Birkedal, Stovring y Thamsborg, "Semántica de realizabilidad del polimorfismo paramétrico, referencias generales y tipos recursivos"). Las personas que prefieren la semántica operativa conocen estas cosas como relaciones lógicas indexadas por pasos. (Por ejemplo, ver "Independencia de representación dependiente del estado" de Ahmed, Dreyer y Rossberg). De cualquier manera, las técnicas utilizadas son relativamente nuevas.

a -> bunTsiunsiT(UN)una

En lo que respecta a la teoría de la ecuación, dado que estos lenguajes pueden describirse mediante traducciones a subconjuntos ligeramente diferentes del mismo idioma, es completamente justo llamarlos variaciones sintácticas entre sí.

La diferencia de sensación entre ML y Haskell en realidad surge de las propiedades intensionales de los dos idiomas, es decir, el tiempo de ejecución y el consumo de memoria. ML tiene un modelo de rendimiento de composición (es decir, el costo de tiempo / espacio de un programa puede calcularse a partir de los costos de tiempo / espacio de sus subterms), como lo haría un verdadero lenguaje de llamada por nombre. Haskell real se implementa con una llamada por necesidad, una especie de memorización, y como resultado, su rendimiento no es compositivo: el tiempo que tarda una expresión vinculada a una variable en evaluar depende de si se ha utilizado antes o no. Esto no está modelado en la semántica a la que aludí anteriormente.

Si desea tomar las propiedades intensivas más en serio, ML y Haskell comienzan a mostrar diferencias más serias. Todavía es posible idear un metalenguaje común para ellos, pero la interpretación de los tipos diferirá de una manera mucho más sistemática, relacionada con la idea teórica de la prueba de enfoque . Un buen lugar para aprender sobre esto es la tesis doctoral de Noam Zeilberger.

Neel Krishnaswami
fuente
10

Mi sensación es que SPJ se refería a lenguajes puramente funcionales, es decir, lenguajes que son referencialmente transparentes. Esto incluye, por ejemplo, Haskell, Miranda, Clean, pero no ML. Una vez que tenga un lenguaje puramente funcional, en general, puede darle una semántica denotacional bastante limpia y bien definida. Esta semántica, en general, se verá como una para el cálculo lambda, con algunos ajustes aquí y allá. En general, tendrá un sistema de tipos que se desugará a algo parecido a una variante del Sistema F, quizás más poderoso en algunos aspectos, más restringido en otros. Esta es la razón por la cual la extracción / compilación de código para Haskell, O'Caml, etc. es relativamente sencilla de los asistentes de prueba sofisticados de tipo dependiente como Agda.

Dentro de ese marco, hay mucho espacio para jugar. Ciertamente, todavía hay una diferencia entre un lenguaje no estricto y uno estricto. Sin embargo, en ausencia de efectos secundarios, la única diferencia es que un lenguaje no estricto contiene más expresiones que no denotan fondo, en la medida en que las dos estrategias de evaluación no dan fondo, están de acuerdo.

La declaración de Simon también encaja en un contexto histórico muy importante. En el momento del nacimiento de Haskell (1987), había una panoplia de lenguajes funcionales no estrictos, no solo Miranda, sino Lazy ML, Orwell, Clean y muchos otros. Aparte de ciertas variaciones sintácticas, todas eran muy parecidas. Cuál fue precisamente la motivación para que se formara el Comité Haskell. Para obtener más información al respecto, consulte "Una historia de Haskell: ser flojo con la clase": http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/ .

sclv
fuente
5

Creo que SPJ tiene razón al decir esto para la semántica central.

Si bien hay muchas sutilezas avanzadas a las que uno puede apuntar, como el incumplimiento de una evaluación estricta o perezosa, como usted menciona, los detalles de los sistemas de tipos o cómo se organizan las unidades de código más grandes (módulos, estructuras), el modelo mental de un programa es muy similar en todos los lenguajes funcionales.

Elija alguna función específica en particular y escríbala en todos los idiomas que esté comparando, y probablemente encontrará que la estructura y la semántica de las diferentes implementaciones serán muy similares para todas ellas, incluido el nivel de abstracción, las estructuras de datos elegidas, ellas ' Todos asumiremos la recolección de basura, etc.

Por el contrario, supongamos que una implementación de C frente a una implementación de Smalltalk de la misma función probablemente tendrá una estructura diferente (funciones y estructuras de datos de bajo nivel frente a objetos), se centrará en diferentes niveles de detalle (por ejemplo, gestión manual de memoria frente a recolección de basura) ), y operar en diferentes niveles de abstracción.

La visión del mundo del espacio de diseño del lenguaje funcional es simplemente más específica y coherente que la del espacio de "programación imperativa" que agrupa el ensamblaje, C, Smalltalk, Forth y docenas de otros lenguajes radicalmente diferentes en una categoría general.

Marc Hamann
fuente
4

Creo que la cita de Simon PJ es en realidad un comentario poco convencional.

La similitud entre los idiomas está determinada por el consenso que se ha generado en la comunidad de investigadores y diseñadores de idiomas. No hay duda de que existe un mayor grado de consenso en la comunidad de programación funcional que en la comunidad de programación imperativa. Pero también es el caso de que los lenguajes de programación funcional están diseñados principalmente por investigadores en lugar de por profesionales. Por lo tanto, es natural que surja ese consenso.

Casi todos los lenguajes funcionales usan gestión de memoria recolectada de basura y estructuras de datos recursivas (originadas por Lisp), la mayoría de ellas usan tipos de datos "algebraicos" y coincidencia de patrones (originada por Hope), muchos de ellos usan funciones de orden superior y funciones polimórficas ( originado por ML). Más allá de eso, el consenso desaparece. Se diferencian en los sistemas de módulos utilizados, cómo se deben manejar las operaciones de cambio de estado y otros efectos computacionales, y el orden de evaluación (llamada por nombre vs llamada por valor), etc.

Los lenguajes de programación imperativos generalmente usan estructuras de control anidadas (originadas por Algol 60) y sistemas de tipos (originadas por Algol 60, pero consolidadas por Algol 68). En general, tienen una sintaxis de superficie engorrosa (de nuevo volviendo a Algol 60), hacen intentos poco entusiastas para manejar funciones de orden superior y tipos polimórficos, y difieren en su soporte para la estructura de bloques y los sistemas de módulos. Probablemente haya más uniformidad en el orden de evaluación porque, después de los años 60, la llamada por nombre ha desaparecido esencialmente de los idiomas imperativos.

Entonces, no está claro para mí que la diferencia entre las dos clases de idiomas en su uniformidad sea tan grande.

Realmente valdría la pena llevar las notaciones más limpias y uniformes de la programación funcional a los lenguajes de programación imperativos. Veo que Scala ha comenzado en esa dirección. Queda por ver si la tendencia continuará.

Uday Reddy
fuente
Me pregunto por qué usaste las comillas de miedo en los tipos de datos "algebraicos".
Steven Shaw el