¿Qué hace que los lenguajes de programación funcional sean declarativos en lugar de imperativos?

En muchos artículos, que describen los beneficios de la programación funcional, he visto lenguajes de programación funcional, como Haskell, ML, Scala o Clojure, denominados "lenguajes declarativos" distintos de los lenguajes imperativos como C / C ++ / C # / Java. Mi pregunta es qué hace que los lenguajes de programación funcionales sean declarativos en lugar de imperativos.

Una explicación frecuente que describe las diferencias entre la programación declarativa y la imperativa es que en la programación imperativa usted le dice a la computadora "Cómo hacer algo" en lugar de "Qué hacer" en los lenguajes declarativos. El problema que tengo con esta explicación es que constantemente estás haciendo ambas cosas en todos los lenguajes de programación. Incluso si baja al ensamblaje del nivel más bajo, todavía le está diciendo a la computadora "Qué hacer", le dice a la CPU que agregue dos números, no le indica cómo realizar la suma. Si vamos al otro extremo del espectro, un lenguaje funcional puro de alto nivel como Haskell, de hecho le estás diciendo a la computadora cómo lograr una tarea específica, eso es lo que su programa es una secuencia de instrucciones para lograr una tarea específica que la computadora no sabe cómo lograr sola. Entiendo que lenguajes como Haskell, Clojure, etc. son obviamente de un nivel más alto que C / C ++ / C # / Java y ofrecen características tales como evaluación perezosa, estructuras de datos inmutables, funciones anónimas, currículum, estructuras de datos persistentes, etc. Programación funcional posible y eficiente, pero no los clasificaría como lenguajes declarativos.

Un lenguaje declarativo puro para mí sería uno que esté compuesto únicamente por declaraciones, un ejemplo de tales lenguajes sería CSS (Sí, sé que CSS técnicamente no sería un lenguaje de programación). CSS solo contiene declaraciones de estilo que son utilizadas por el HTML y Javascript de la página. CSS no puede hacer nada más que hacer declaraciones, no puede crear funciones de clase, es decir, funciones que determinan el estilo para mostrar en función de algún parámetro, no puede ejecutar scripts CSS, etc. Eso para mí describe un lenguaje declarativo (note que no dije declarativo lenguaje de programación ).

Actualizar:

He estado jugando con Prolog recientemente y para mí, Prolog es el lenguaje de programación más cercano a un lenguaje totalmente declarativo (al menos en mi opinión), si no es el único lenguaje de programación completamente declarativo. La elaboración de la programación en Prolog se realiza mediante declaraciones que establecen un hecho (una función de predicado que devuelve verdadero para una entrada específica) o una regla (una función de predicado que devuelve verdadero para una condición / patrón determinado en función de las entradas), reglas se definen utilizando una técnica de coincidencia de patrones. Para hacer cualquier cosa en el prólogo, consulta la base de conocimiento sustituyendo una o más de las entradas de un predicado con una variable y el prólogo intenta encontrar valores para las variables para las cuales el predicado tiene éxito.

Mi punto es en el prólogo que no hay instrucciones imperativas, básicamente le dice (declara) a la computadora lo que sabe y luego pregunta (consulta) sobre el conocimiento. En los lenguajes de programación funcionales, todavía está dando instrucciones, es decir, tome un valor, llame a la función X y agregue 1, etc., incluso si no está manipulando directamente las ubicaciones de memoria o escribiendo el cálculo paso a paso. No diría que la programación en Haskell, ML, Scala o Clojure es declarativa en este sentido, aunque puedo estar equivocado. Es propia, verdadera, pura programación funcional declarativa en el sentido que describí anteriormente.

Parece que estás trazando una línea entre declarar cosas e instruir a una máquina. No existe tal separación dura y rápida. Debido a que la máquina que está siendo instruida en programación imperativa no necesita ser hardware físico, hay mucha libertad para la interpretación. Casi todo se puede ver como un programa explícito para la máquina abstracta correcta. Por ejemplo, podría ver CSS como un lenguaje de alto nivel para programar una máquina que resuelve principalmente selectores y establece atributos de los objetos DOM seleccionados de esta manera.

La pregunta es si esa perspectiva es sensata y, por el contrario, hasta qué punto la secuencia de instrucciones se parece a una declaración del resultado que se calcula. Para CSS, la perspectiva declarativa es claramente más útil. Para C, la perspectiva imperativa es claramente predominante. En cuanto a idiomas como Haskell, bueno ...

El lenguaje ha especificado, semántica concreta. Es decir, por supuesto, uno puede interpretar el programa como una cadena de operaciones. Ni siquiera toma mucho esfuerzo elegir las operaciones primitivas para que se asignen bien en el hardware básico (esto es lo que hacen la máquina STG y otros modelos).

Sin embargo, por la forma en que se escriben los programas de Haskell, con frecuencia se pueden leer con sensatez como una descripción del resultado que se va a calcular. Tomemos, por ejemplo, el programa para calcular la suma de los primeros N factoriales:

sum_of_fac n = sum [product [1..i] | i <- ..n]

Puede desugar esto y leerlo como una secuencia de operaciones STG, pero es mucho más natural leerlo como una descripción del resultado (que, creo, es una definición más útil de programación declarativa que "qué calcular"): El resultado es la suma de los productos de [1..i]for all i= 0, ..., n. Y eso es mucho más declarativo que casi cualquier programa o función de C.

La unidad básica de un programa imperativo es la declaración . Las declaraciones se ejecutan por sus efectos secundarios. Modifican el estado que reciben. Una secuencia de declaraciones es una secuencia de comandos, denotando hacer esto y luego hacer eso. El programador especifica el orden exacto para realizar el cálculo. Esto es lo que la gente quiere decir al decirle a la computadora cómo hacerlo.

La unidad básica de un programa declarativo es la expresión . Las expresiones no tienen efectos secundarios. Especifican una relación entre una entrada y una salida, creando una salida nueva y separada de su entrada, en lugar de modificar su estado de entrada. Una secuencia de expresiones no tiene sentido sin que algunas contengan expresiones que especifiquen la relación entre ellas. El programador especifica las relaciones entre los datos y el programa infiere el orden para realizar el cálculo a partir de esas relaciones. Esto es lo que la gente quiere decir al decirle a la computadora qué hacer.

Los lenguajes imperativos tienen expresiones, pero su principal medio para hacer las cosas son las declaraciones. Del mismo modo, los lenguajes declarativos tienen algunas expresiones con semántica similar a las declaraciones, como secuencias de mónadas dentro de la donotación de Haskell , pero en esencia, son una gran expresión. Esto permite a los principiantes escribir código que tiene un aspecto muy imperativo, pero el verdadero poder del lenguaje se produce cuando escapas de ese paradigma.

La característica definitoria real que separa la programación declarativa de la imperativa es en estilo declarativo que no está dando instrucciones secuenciadas; en el nivel inferior sí, la CPU funciona de esta manera, pero eso es una preocupación del compilador.

Sugieres que CSS es un "lenguaje declarativo", no lo llamaría en absoluto lenguaje. Es un formato de estructura de datos, como JSON, XML, CSV o INI, solo un formato para definir datos que conoce un intérprete de alguna naturaleza.

Algunos efectos secundarios interesantes suceden cuando quitas el operador de asignación de un idioma, y ​​esta es la verdadera causa de perder todas esas instrucciones imperativas paso1-paso2-paso3 en lenguajes declarativos.

¿Qué haces con el operador de asignación en una función? Creas pasos intermedios. Ese es el quid de la cuestión, el operador de asignación se utiliza para alterar los datos paso a paso. Tan pronto como ya no pueda alterar los datos, pierde todos esos pasos y termina con:

Cada función tiene solo una declaración, esta declaración es la declaración única

Ahora hay muchas maneras de hacer que una sola declaración se parezca a muchas declaraciones, pero eso es solo un truco, por ejemplo: 1 + 3 + (2*4) + 8 - (7 / (8*3))esta es claramente una declaración única, pero si la escribe como ...

1 +
3 +
(
  2*4
) +
8 - 
(
  7 / (8*3)
)

Puede asumir la apariencia de una secuencia de operaciones que pueden ser más fáciles para que el cerebro reconozca la descomposición deseada que pretendía el autor. A menudo hago esto en C # con código como ...

people
  .Where(person => person.MiddleName != null)
  .Select(person => person.MiddleName)
  .Distinct();

Esta es una declaración única, pero muestra la apariencia de descomponerse en muchas, observe que no hay asignaciones.

También tenga en cuenta, en los dos métodos anteriores: la forma en que se ejecuta el código no está en el orden en que lo leyó de inmediato; porque este código dice qué hacer, pero no dicta cómo . Tenga en cuenta que la aritmética simple anterior obviamente no se ejecutará en la secuencia que se escribe de izquierda a derecha, y en el ejemplo de C # anterior, esos 3 métodos son realmente reentrantes y no se ejecutan hasta su finalización en secuencia, el compilador de hecho genera código eso hará lo que quiere esa declaración , pero no necesariamente cómo se supone.

Creo que acostumbrarse a este enfoque sin pasos intermedios de la codificación declarativa es realmente la parte más difícil de todo; y por qué Haskell es tan complicado porque pocos idiomas realmente lo rechazan como lo hace Haskell. Tienes que comenzar a hacer gimnasia interesante para lograr algunas cosas que normalmente harías con la ayuda de variables intermedias, como la sumatoria.

En un lenguaje declarativo, si desea que una variable intermedia haga algo, significa pasarla como un parámetro a una función que hace esa cosa. Es por eso que la recursividad se vuelve tan importante.

sum xs = (head xs) + sum (tail xs)

No puede crear una resultSumvariable y agregarla a medida que avanza xs, simplemente tiene que tomar el primer valor y agregarlo a la suma de todo lo demás, y para acceder a todo lo demás tiene que pasar xsa una función tailporque no puede simplemente crear una variable para xs y sacar la cabeza, lo que sería un enfoque imperativo. (Sí, sé que podría usar la desestructuración, pero este ejemplo es ilustrativo)

Sé que llego tarde a la fiesta, pero tuve una epifanía el otro día, así que aquí va ...

Creo que los comentarios acerca de efectos funcionales, inmutables y sin efectos secundarios se pierden cuando se explica la diferencia entre declarativo versus imperativo o cuando se explica lo que significa la programación declarativa. Además, como mencionas en tu pregunta, todo el "qué hacer" frente a "cómo hacerlo" es demasiado vago y realmente tampoco explica.

Tomemos el código simple a = b + ccomo base y veamos la declaración en algunos idiomas diferentes para obtener la idea:

Cuando escribimos a = b + cen un lenguaje imperativo, como C, estamos asignando el valor actual de b + cla variable ay nada más. No estamos haciendo ninguna declaración fundamental sobre lo que aes. Más bien, simplemente estamos ejecutando un paso en un proceso.

Cuando escribimos a = b + cen un lenguaje declarativo, como Microsoft Excel, (sí, Excel es un lenguaje de programación y probablemente el más declarativo de todos), estamos afirmando una relación entre ellos a, by ctal es siempre el caso que aes la suma de los otros dos. No es un paso en un proceso, es una invariante, una garantía, una declaración de verdad.

Los lenguajes funcionales también son declarativos, pero casi por accidente. En Haskel, por ejemplo, a = b + ctambién afirma una relación invariante, pero solo porque by cson inmutables.

Entonces, sí, cuando los objetos son inmutables y las funciones están libres de efectos secundarios, el código se vuelve declarativo (incluso si parece idéntico al código imperativo), pero no son el punto. Tampoco es evitar la asignación. El punto del código declarativo es hacer declaraciones fundamentales sobre las relaciones.

Tienes razón en que no hay una distinción clara entre decirle a la computadora qué hacer y cómo hacerlo.

Sin embargo, en un lado del espectro, casi exclusivamente piensa en cómo manipular la memoria. Es decir, para resolver un problema, lo presenta a la computadora en una forma como "establecer esta ubicación de memoria en x, luego establecer esa ubicación de memoria en y, saltar a la ubicación de memoria z ..." y luego de alguna manera terminar teniendo el resultado en alguna otra ubicación de memoria.

En lenguajes administrados como Java, C #, etc., ya no tiene acceso directo a la memoria del hardware. El programador imperativo ahora está preocupado por variables estáticas, referencias o campos de instancias de clase, todo lo cual son, en cierta medida, absracciones para ubicaciones de memoria.

En langugaes como Haskell, OTOH, la memoria se ha ido por completo. Simplemente no es el caso que en

f a b = let y = sum [a..b] in y*y

debe haber dos celdas de memoria que contengan los argumentos a y by otra que contenga el resultado intermedio y. Para estar seguros, un backend del compilador podría emitir un código final que funciona de esta manera (y en cierto sentido debe hacerlo siempre que la arquitectura de destino sea una máquina v. Neumann).

Pero el punto es que no necesitamos internalizar la arquitectura v. Neumann para comprender la función anterior. Tampoco necesitamos una computadora contemporánea para ejecutarlo. Sería fácil traducir programas en un lenguaje FP puro a una máquina hipotética que funciona sobre la base del cálculo SKI, por ejemplo. ¡Ahora intente lo mismo con un programa en C!

Un lenguaje declarativo puro para mí sería uno que esté compuesto únicamente por declaraciones

Esto no es lo suficientemente fuerte, en mi humilde opinión. Incluso un programa en C es solo una secuencia de declaraciones. Siento que debemos calificar aún más las declaraciones. Por ejemplo, ¿nos están diciendo qué es algo (declarativo) o qué hace (imperativo)?