Progtwigción funcional, declarativa e imperativa

¿Qué significan los términos progtwigción funcional, declarativa e imperativa?

En el momento de escribir esto, las respuestas más votadas en esta página son imprecisas y confusas en la definición declarativa vs. imperativa, incluida la respuesta que cita a Wikipedia. Algunas respuestas están combinando los términos de diferentes maneras.

Consulte también mi explicación de por qué la progtwigción de hoja de cálculo es declarativa, independientemente de que las fórmulas muten las celdas.

Además, varias respuestas afirman que la progtwigción funcional debe ser un subconjunto de declarativo. En ese punto, depende si diferenciamos “función” de “procedimiento”. Permite manejar imperativo vs. declarativo primero.

Definición de expresión declarativa

El único atributo que puede diferenciar una expresión declarativa de una expresión imperativa es la transparencia referencial (RT) de sus subexpresiones. Todos los demás atributos se comparten entre ambos tipos de expresiones o se derivan de la RT.

Un lenguaje 100% declarativo (es decir, uno en el que cada expresión posible es RT) no permite (entre otros requisitos de RT) la mutación de los valores almacenados, por ejemplo, HTML y la mayor parte de Haskell.

Definición de expresión RT

RT a menudo se denomina “sin efectos secundarios”. El término efectos no tiene una definición precisa, por lo que algunas personas no están de acuerdo en que “no tener efectos secundarios” sea lo mismo que RT. RT tiene una definición precisa .

Dado que cada sub-expresión es conceptualmente una llamada a función, RT requiere que la implementación de una función (es decir, la expresión (s) dentro de la función llamada) no pueda acceder al estado mutable que es externo a la función (el acceso al estado local mutable es permitido). En pocas palabras, la función (implementación) debe ser pura .

Definición de función pura

A menudo se dice que una función pura no tiene “efectos secundarios”. El término efectos no tiene una definición precisa, por lo que algunas personas no están de acuerdo.

Las funciones puras tienen los siguientes atributos.

  • la única salida observable es el valor de retorno.
  • la única dependencia de salida son los argumentos.
  • los argumentos están completamente determinados antes de que se genere cualquier salida.

Recuerde que RT se aplica a las expresiones (que incluye llamadas a funciones) y la pureza se aplica a (implementaciones de) funciones.

Un oscuro ejemplo de funciones impuras que hacen expresiones RT es la concurrencia, pero esto se debe a que la pureza se rompe en la capa de abstracción de interrupción. Realmente no necesitas saber esto. Para hacer expresiones RT, llamas a funciones puras.

Atributos derivados de RT

Cualquier otro atributo citado para la progtwigción declarativa, por ejemplo, la cita de 1999 utilizada por Wikipedia, o bien se deriva de RT, o se comparte con la progtwigción imperativa. Demostrando así que mi definición precisa es correcta.

Tenga en cuenta que la inmutabilidad de los valores externos es un subconjunto de los requisitos para RT.

  • Los lenguajes declarativos no tienen estructuras de control de bucle, por ejemplo, for y while , porque debido a la inmutabilidad , la condición de bucle nunca cambiará.

  • Los lenguajes declarativos no expresan flujo de control además del orden de función nested (también conocido como dependencias lógicas), porque debido a la inmutabilidad , otras elecciones de orden de evaluación no cambian el resultado (ver a continuación).

  • Los lenguajes declarativos expresan “pasos” lógicos (es decir, el orden de llamada de función RT nested), pero no es requisito de progtwigción declarativa si cada llamada a función es un nivel semántico superior (es decir, “qué hacer”). La distinción de imperativo es que debido a la inmutabilidad (es decir, más generalmente RT), estos “pasos” no pueden depender del estado mutable, sino solo del orden relacional de la lógica expresada (es decir, el orden de anidación de las llamadas a función, también sub-expresiones )

    Por ejemplo, el párrafo HTML

    no se puede mostrar hasta que se hayan evaluado las expresiones secundarias (es decir, tags) en el párrafo. No hay un estado mutable, solo una dependencia de orden debido a la relación lógica de la jerarquía de tags (anidamiento de subexpresiones, que son llamadas de función análoga análogamente ).

  • Por lo tanto, existe el atributo derivado de inmutabilidad (más generalmente RT), que las expresiones declarativas expresan solo las relaciones lógicas de las partes constituyentes (es decir, de los argumentos de la función de subexpresión) y las relaciones de estado no mutables .

Orden de evaluación

La elección del orden de evaluación de las subexpresiones solo puede dar un resultado variable cuando cualquiera de las llamadas de función no es RT (es decir, la función no es pura), por ejemplo, se accede a un estado mutable externo a una función dentro de la función.

Por ejemplo, dadas algunas expresiones anidadas, por ejemplo, f( g(a, b), h(c, d) ) , la evaluación ansiosa y perezosa de los argumentos de la función dará los mismos resultados si las funciones f , g y h son puras .

Mientras que, si las funciones f , g y h no son puras, entonces la elección del orden de evaluación puede dar un resultado diferente.

Tenga en cuenta que las expresiones anidadas son funciones conceptualmente anidadas, ya que los operadores de expresiones son simplemente llamadas a funciones que se disfrazan como prefijo unario, postfijo unario o notación de infijo binario.

Tangencialmente, si todos los identificadores, por ejemplo, a , b , c , d , son inmutables en todas partes, no se puede acceder al estado externo al progtwig (es decir, E / S) y no hay ruptura de la capa de abstracción, las funciones siempre son puras.

Por cierto, Haskell tiene una syntax diferente, f (gab) (hcd) .

Detalles de la orden de evaluación

Una función es una transición de estado (no un valor almacenable mutable) desde la entrada hasta la salida. Para composiciones RT de llamadas a funciones puras , el orden de ejecución de estas transiciones de estado es independiente. La transición de estado de cada llamada de función es independiente de las otras, debido a la falta de efectos secundarios y al principio de que una función RT puede ser reemplazada por su valor almacenado en caché . Para corregir un error popular , la composición monádica pura es siempre declarativa y RT , a pesar del hecho de que la mónada IO de Haskell es discutiblemente impura y por lo tanto imperativa con respecto al estado World externo al progtwig (pero en el sentido de la advertencia siguiente, el lado -efectos son aislados).

La evaluación entusiasta significa que los argumentos de las funciones se evalúan antes de que se llame a la función, y la evaluación diferida significa que los argumentos no se evalúan hasta (y si) se accede a ellos dentro de la función.

Definición : los parámetros de función se declaran en el sitio de definición de función, y los argumentos de función se suministran en el sitio de llamada de función. Sepa la diferencia entre parámetro y argumento .

Conceptualmente, todas las expresiones son (una composición de) llamadas a funciones, por ejemplo, constantes son funciones sin entradas, operadores unarios son funciones con una entrada, operadores binarios son funciones con dos entradas, constructores son funciones e incluso instrucciones de control (por ejemplo, if , for , while ) se puede modelar con funciones. El orden en que se evalúan estas funciones de argumento (no confundir con orden de llamada de función anidada) no se declara mediante la syntax, por ejemplo, f( g() ) podría evaluar ansiosamente g luego f en el resultado de g o podría evaluar f solo evaluar perezadamente g cuando se necesita su resultado dentro de f .

Advertencia, no el lenguaje completo de Turing (es decir, que permite la recursión sin límites) es perfectamente declarativo, por ejemplo, la evaluación perezosa introduce la memoria y el indeterminismo del tiempo. Pero estos efectos secundarios debido a la elección del orden de evaluación están limitados al consumo de memoria, tiempo de ejecución, latencia, no terminación e histéresis externa, por lo tanto, sincronización externa.

Progtwigción funcional

Debido a que la progtwigción declarativa no puede tener bucles, entonces la única forma de iterar es la recursión funcional. Es en este sentido que la progtwigción funcional se relaciona con la progtwigción declarativa.

Pero la progtwigción funcional no se limita a la progtwigción declarativa . La composición funcional se puede contrastar con la subtipificación , especialmente con respecto al problema de expresión , donde la extensión puede lograrse agregando subtipos o descomposición funcional . La extensión puede ser una combinación de ambas metodologías.

La progtwigción funcional por lo general hace que la función sea un objeto de primera clase, lo que significa que el tipo de función puede aparecer en la gramática en cualquier otro lugar. El resultado es que las funciones pueden ingresar y operar funciones, lo que permite separar las preocupaciones al enfatizar la composición de funciones, es decir, separar las dependencias entre las subcomputaciones de una computación determinista.

Por ejemplo, en lugar de escribir una función separada (y emplear recurrencia en lugar de bucles si la función también debe ser declarativa) para cada una de un número infinito de posibles acciones especializadas que se podrían aplicar a cada elemento de una colección, la progtwigción funcional emplea iteración reutilizable funciones, por ejemplo, map , fold , filter . Estas funciones de iteración ingresan una función de acción especializada de primera clase. Estas funciones de iteración iteran la colección y llaman a la función de acción especializada de entrada para cada elemento. Estas funciones de acción son más concisas porque ya no necesitan contener las instrucciones de bucle para iterar la colección.

Sin embargo, tenga en cuenta que si una función no es pura, entonces es realmente un procedimiento. Quizás podamos argumentar que la progtwigción funcional que usa funciones impuras, es realmente progtwigción de procedimientos. Por lo tanto, si aceptamos que las expresiones declarativas son RT, entonces podemos decir que la progtwigción procedimental no es una progtwigción declarativa, y así podríamos argumentar que la progtwigción funcional siempre es RT y debe ser un subconjunto de la progtwigción declarativa.

Paralelismo

Esta composición funcional con funciones de primera clase puede express la profundidad en el paralelismo separando la función independiente.

Principio de Brent: el cálculo con el trabajo wy la profundidad d pueden implementarse en un procesador de fase PRAM en el tiempo O (max (w / p, d)).

Tanto la simultaneidad como el paralelismo también requieren progtwigción declarativa , es decir, inmutabilidad y RT.

Entonces, ¿de dónde viene esta peligrosa suposición de que viene el paralelismo == concurrencia? Es una consecuencia natural de los lenguajes con efectos secundarios: cuando su lenguaje tiene efectos secundarios en todas partes, cada vez que intenta hacer más de una cosa a la vez, esencialmente no tiene determinismo causado por el entrelazado de los efectos de cada operación . Entonces, en los lenguajes de efecto secundario, la única forma de obtener el paralelismo es la concurrencia; por lo tanto, no es sorprendente que a menudo veamos los dos fusionados.

Orden de evaluación FP

Tenga en cuenta que la orden de evaluación también afecta los efectos secundarios de terminación y rendimiento de la composición funcional.

Eager (CBV) y perezoso (CBN) son duelos categóricos [ 10 ], porque tienen un orden de evaluación invertido, es decir, si las funciones externas o internas, respectivamente, se evalúan primero. Imagine un árbol al revés, luego evalúa con entusiasmo desde la twig de árbol de funciones, sube la jerarquía de twigs al tronco de funciones de nivel superior; mientras que lazy evalúa desde el tronco hasta las puntas de las twigs. Eager no tiene productos conjuntivos (“y”, a / k / a “productos” categóricos) y perezosa no tiene coproductos disyuntivos (“o”, sums categóricas a / k / a “) [ 11 ].

Actuación

  • Ansioso

    Al igual que con la no terminación, ansioso está demasiado ansioso con la composición funcional conjuntiva, es decir, la estructura de control de la composición hace un trabajo innecesario que no se hace con pereza. Por ejemplo , ansioso e innecesariamente mapea la lista completa a booleanos, cuando está compuesta con un doblez que termina en el primer elemento verdadero.

    Este trabajo innecesario es la causa del supuesto “hasta” un factor de inicio de sesión extra en la complejidad de tiempo secuencial de ansioso frente a perezoso, ambos con funciones puras. Una solución es usar funtores (por ejemplo, listas) con constructores perezosos (es decir, ansiosos con productos perezosos opcionales), porque con entusiasmo la incorrección del afán se origina en la función interna. Esto se debe a que los productos son tipos constructivos, es decir, tipos inductivos con un álgebra inicial en un punto fijo inicial [ 11 ]

  • Perezoso

    Al igual que con la no terminación, perezoso es demasiado vago con la composición funcional disyuntiva, es decir, la finalidad coinductiva puede ocurrir más tarde de lo necesario, lo que resulta en trabajo innecesario y no determinismo de la tardanza que no es el caso con entusiasmo [ 10 ] [ 11 ] . Los ejemplos de finalidad son excepciones de estado, tiempo, no terminación y tiempo de ejecución. Estos son efectos secundarios imperativos, pero incluso en un lenguaje declarativo puro (por ejemplo, Haskell), hay estado en la mónada IO imperativa (nota: ¡no todas las mónadas son imperativas!) Implícitas en la asignación de espacio, y el tiempo es estado relativo al imperativo mundo real. Usar perezoso incluso con coproductos impares opcionales filtra “pereza” en coproductos internos, porque con pereza la incorrección de holgazanería se origina en la función externa (vea el ejemplo en la sección No terminación, donde == es una función de operador binario externo). Esto se debe a que los coproductos están limitados por la finalidad, es decir, los tipos coinductivos con un álgebra final en un objeto final [ 11 ].

    Lazy provoca indeterminismo en el diseño y la depuración de funciones para latencia y espacio, cuya depuración está probablemente más allá de las capacidades de la mayoría de los progtwigdores, debido a la disonancia entre la jerarquía de funciones declarada y el orden de evaluación en tiempo de ejecución. Las funciones lazy pure evaluadas con entusiasmo, podrían potencialmente introducir una no terminación previamente no vista en el tiempo de ejecución. Por el contrario, las funciones puras e impacientes evaluadas con holgazanería, podrían potencialmente introducir un indeterminismo de latencia y espacio previamente no visto en el tiempo de ejecución.

No terminación

En tiempo de comstackción, debido al problema de detención y recursión mutua en un lenguaje completo de Turing, no se puede garantizar que las funciones terminen en general.

  • Ansioso

    Con ganas pero no perezoso, para la conjunción de Head “y” Tail , si Head o Tail no termina, entonces, o bien List( Head(), Tail() ).tail == Tail() o List( Head(), Tail() ).head == Head() no es verdadero porque el lado izquierdo no, y el lado derecho, termina.

    Mientras que, con perezoso ambos lados terminan. Así, impaciente está demasiado ansioso con los productos conjuntivos y sin terminación (incluidas las excepciones de tiempo de ejecución) en los casos donde no es necesario.

  • Perezoso

    Con perezoso pero no ansioso, para la disyunción de 1 “o” 2 , si f no termina, entonces List( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tail no es verdadera porque el lado izquierdo termina, y el lado derecho no.

    Mientras que, con entusiasmo ninguno de los lados termina, entonces la prueba de igualdad nunca se alcanza. Por lo tanto, el perezoso es demasiado vago con los productos coproducidos disyuntivos, y en esos casos no termina (incluidas las excepciones de tiempo de ejecución) después de hacer más trabajo de lo que hubiera deseado.

[ 10 ] Contingencias declarativas y dualidad categórica, Filinski, secciones 2.5.4 Una comparación de CBV y CBN, y 3.6.1 CBV y CBN en el SCL.

[ 11 ] Contingencias declarativas y dualidad categórica, Filinski, secciones 2.2.1 Productos y coproductos, 2.2.2 objetos terminales y iniciales, 2.5.2 CBV con productos perezosos y 2.5.3 CBN con codiciados coproductos.

Realmente no hay ninguna definición objetiva no ambigua para estos. Así es como los definiría:

Imperativo : el enfoque es qué pasos debe tomar la computadora en lugar de qué hará la computadora (por ejemplo, C, C ++, Java).

Declarativo : el foco está en lo que debe hacer la computadora en lugar de cómo debería hacerlo (por ejemplo, SQL).

Funcional : un subconjunto de lenguajes declarativos que tiene un gran enfoque en la recursión.

imperativo y declarativo describen dos estilos opuestos de progtwigción. imperativo es el enfoque tradicional de “receta paso a paso”, mientras que el declarativo es más “esto es lo que quiero, ahora usted trabaja cómo hacerlo”.

estos dos enfoques ocurren durante la progtwigción, incluso con el mismo lenguaje y el mismo progtwig. en general, el enfoque declarativo se considera preferible, porque libera al progtwigdor de tener que especificar tantos detalles, al tiempo que tiene menos posibilidades de errores (si describe el resultado que desea, y un proceso automático bien probado puede funcionar al revés de eso a defina los pasos, entonces puede esperar que las cosas sean más confiables que tener que especificar cada paso a mano).

por otro lado, un enfoque imperativo te brinda un control de bajo nivel, es el “enfoque de microgestión” para la progtwigción. y eso puede permitir que el progtwigdor explote el conocimiento sobre el problema para dar una respuesta más eficiente. por lo que no es inusual que algunas partes de un progtwig se escriban en un estilo más declarativo, pero para que las partes críticas sean más imperativas.

como se puede imaginar, el lenguaje que usa para escribir un progtwig afecta lo declarativo que puede ser: un lenguaje que tiene “inteligencia” incorporada para determinar qué hacer, dado que una descripción del resultado permitirá una statement mucho más explícita. enfoque que no sea uno donde el progtwigdor necesita primero agregar ese tipo de inteligencia con un código imperativo antes de poder construir una capa más declarativa en la parte superior. así que, por ejemplo, un lenguaje como prólogo se considera muy declarativo porque tiene incorporado un proceso que busca respuestas.

hasta ahora, notarás que no he mencionado la progtwigción funcional . eso se debe a que es un término cuyo significado no está relacionado de manera inmediata con los otros dos. en su progtwigción más simple y funcional significa que usted usa funciones. en particular, que use un lenguaje que admita funciones como “valores de primera clase”, eso significa que no solo puede escribir funciones, sino que también puede escribir funciones que escriben funciones (que escriben funciones que …) y pasar funciones a funciones. en resumen, las funciones son tan flexibles y comunes como cosas como cadenas y números.

podría parecer extraño, entonces, que funcional, imperativo y declarativo se mencionen a menudo juntos. la razón de esto es una consecuencia de llevar la idea de la progtwigción funcional “al extremo”. una función, en su sentido más puro, es algo de las matemáticas, una especie de “caja negra” que requiere cierta aportación y siempre da el mismo resultado. y ese tipo de comportamiento no requiere almacenar variables cambiantes. entonces, si diseña un lenguaje de progtwigción cuyo objective es implementar una idea muy pura y matemáticamente influenciada de la progtwigción funcional, termina rechazando, en gran medida, la idea de valores que pueden cambiar (en un cierto sentido técnico limitado).

y si lo haces, si limitas cómo pueden cambiar las variables, casi por accidente terminas obligando al progtwigdor a escribir progtwigs que son más declarativos, porque una gran parte de la progtwigción imperativa describe cómo cambian las variables y ya no puedes ¡Haz eso! por lo que resulta que la progtwigción funcional, particularmente la progtwigción en un lenguaje funcional, tiende a dar más código declarativo.

para resumir, entonces:

  • imperativo y declarativo son dos estilos opuestos de progtwigción (los mismos nombres se usan para lenguajes de progtwigción que fomentan esos estilos)

  • la progtwigción funcional es un estilo de progtwigción donde las funciones se vuelven muy importantes y, como consecuencia, los valores cambiantes se vuelven menos importantes. la capacidad limitada de especificar cambios en los valores obliga a un estilo más declarativo.

así que la “progtwigción funcional” a menudo se describe como “declarativa”.

En una palabra:

Un lenguaje imperativo especifica una serie de instrucciones que la computadora ejecuta en secuencia (haga esto y luego haga eso).

Un lenguaje declarativo declara un conjunto de reglas sobre qué salidas deberían resultar de qué entradas (por ejemplo, si tiene A, entonces el resultado es B). Un motor aplicará estas reglas a las entradas y dará una salida.

Un lenguaje funcional declara un conjunto de funciones matemáticas / lógicas que definen cómo se traduce la entrada a la salida. p.ej. f (y) = y * y. es un tipo de lenguaje declarativo.

Imperativo: cómo alcanzar nuestra meta

  Take the next customer from a list. If the customer lives in Spain, show their details. If there are more customers in the list, go to the beginning 

Declarativo: lo que queremos lograr

  Show customer details of every customer living in Spain 

La Progtwigción Imperativa significa cualquier estilo de progtwigción en el que su progtwig esté estructurado con instrucciones que describan cómo ocurrirán las operaciones realizadas por una computadora .

La Progtwigción declarativa significa cualquier estilo de progtwigción en el que su progtwig sea una descripción del problema o la solución, pero no establece explícitamente cómo se realizará el trabajo .

La progtwigción funcional se progtwig evaluando funciones y funciones de funciones … Como progtwigción funcional (estrictamente definida) significa progtwigr definiendo funciones matemáticas libres de efectos secundarios, por lo que es una forma de progtwigción declarativa, pero no es el único tipo de progtwigción declarativa .

La Progtwigción Lógica (por ejemplo, en Prolog) es otra forma de progtwigción declarativa. Implica computación al decidir si una statement lógica es verdadera (o si puede cumplirse). El progtwig generalmente es una serie de hechos y reglas, es decir, una descripción en lugar de una serie de instrucciones.

La reescritura de términos (por ejemplo, CASL) es otra forma de progtwigción declarativa. Implica una transformación simbólica de los términos algebraicos. Es completamente distinto de la progtwigción lógica y la progtwigción funcional.

imperativo – las expresiones describen la secuencia de acciones a realizar (asociativas)

declarativo – expresiones son declaraciones que contribuyen al comportamiento del progtwig (asociativo, conmutativo, idempotente, monotónico)

funcional – las expresiones tienen valor como único efecto; la semántica apoya el razonamiento ecuacional

Desde que escribí mi respuesta anterior, formulé una nueva definición de la propiedad declarativa que se cita a continuación. También he definido la progtwigción imperativa como la propiedad dual.

Esta definición es superior a la que proporcioné en mi respuesta anterior, porque es sucinta y es más general. Pero puede ser más difícil de asimilar, porque la implicación de los teoremas de incompletitud aplicables a la progtwigción y la vida en general es difícil para los humanos para que puedan pensar.

La explicación citada de la definición discute el papel que juega la progtwigción funcional pura en la progtwigción declarativa.

Todos los tipos exóticos de progtwigción encajan en la siguiente taxonomía declarativa versus imperativa, ya que la siguiente definición afirma que son duales.

Declarativo vs. Imperativo

La propiedad declarativa es extraña, obtusa y difícil de capturar en una definición técnicamente precisa que sigue siendo general y no ambigua, porque es una noción ingenua que podemos declarar el significado (también conocido como semántica) del progtwig sin incurrir en efectos secundarios no deseados. Existe una tensión inherente entre la expresión del significado y la evitación de los efectos no deseados, y esta tensión en realidad se deriva de los teoremas de incompletitud de la progtwigción y nuestro universo.

Es una simplificación excesiva, técnicamente impreciso y, a menudo, ambiguo definir declarativo como qué hacer e imperativo como cómo hacerlo . Un caso ambiguo es el ” qué ” es el ” cómo ” en un progtwig que genera un progtwig, un comstackdor.

Evidentemente, la recursión ilimitada que completa un lenguaje de Turing también es análoga en la semántica, no solo en la estructura sintáctica de la evaluación (también conocida como semántica operacional). Este es lógicamente un ejemplo análogo al teorema de Gödel: ” cualquier sistema completo de axiomas también es inconsistente “. Medita sobre la rareza contradictoria de esa cita! También es un ejemplo que demuestra cómo la expresión de la semántica no tiene un límite comprobable, por lo que no podemos probar 2 que un progtwig (y análogamente su semántica) se detenga también conocido como el teorema de Detención.

Los teoremas de incompletitud derivan de la naturaleza fundamental de nuestro universo, que como se establece en la Segunda Ley de la Termodinámica es ” la entropía (también conocida como el número de posibilidades independientes) tiende al máximo para siempre “. La encoding y el diseño de un progtwig nunca se termina, ¡está vivo! Porque intenta responder a una necesidad del mundo real, y la semántica del mundo real siempre cambia y tiende a tener más posibilidades. Los humanos nunca dejan de descubrir cosas nuevas (incluidos los errores en los progtwigs ;-).

To precisely and technically capture this aforementioned desired notion within this weird universe that has no edge (ponder that! there is no “outside” of our universe), requires a terse but deceptively-not-simple definition which will sound incorrect until it is explained deeply.

Definición:


The declarative property is where there can exist only one possible set of statements that can express each specific modular semantic.

The imperative property 3 is the dual, where semantics are inconsistent under composition and/or can be expressed with variations of sets of statements.


This definition of declarative is distinctively local in semantic scope, meaning that it requires that a modular semantic maintain its consistent meaning regardless where and how it’s instantiated and employed in global scope. Thus each declarative modular semantic should be intrinsically orthogonal to all possible others— and not an impossible (due to incompleteness theorems) global algorithm or model for witnessing consistency, which is also the point of “ More Is Not Always Better ” by Robert Harper, Professor of Computer Science at Carnegie Mellon University, one of the designers of Standard ML.

Examples of these modular declarative semantics include category theory functors eg the Applicative , nominal typing, namespaces, named fields, and wrt to operational level of semantics then pure functional programming.

Thus well designed declarative languages can more clearly express meaning , albeit with some loss of generality in what can be expressed, yet a gain in what can be expressed with intrinsic consistency.

An example of the aforementioned definition is the set of formulas in the cells of a spreadsheet program— which are not expected to give the same meaning when moved to different column and row cells, ie cell identifiers changed. The cell identifiers are part of and not superfluous to the intended meaning. So each spreadsheet result is unique wrt to the cell identifiers in a set of formulas. The consistent modular semantic in this case is use of cell identifiers as the input and output of pure functions for cells formulas (see below).

Hyper Text Markup Language aka HTML— the language for static web pages— is an example of a highly (but not perfectly 3 ) declarative language that (at least before HTML 5) had no capability to express dynamic behavior. HTML is perhaps the easiest language to learn. For dynamic behavior, an imperative scripting language such as JavaScript was usually combined with HTML. HTML without JavaScript fits the declarative definition because each nominal type (ie the tags) maintains its consistent meaning under composition within the rules of the syntax.

A competing definition for declarative is the commutative and idempotent properties of the semantic statements, ie that statements can be reordered and duplicated without changing the meaning. For example, statements assigning values to named fields can be reordered and duplicated without changed the meaning of the program, if those names are modular wrt to any implied order. Names sometimes imply an order, eg cell identifiers include their column and row position— moving a total on spreadsheet changes its meaning. Otherwise, these properties implicitly require global consistency of semantics. It is generally impossible to design the semantics of statements so they remain consistent if randomly ordered or duplicated, because order and duplication are intrinsic to semantics. For example, the statements “Foo exists” (or construction) and “Foo does not exist” (and destruction). If one considers random inconsistency endemical of the intended semantics, then one accepts this definition as general enough for the declarative property. In essence this definition is vacuous as a generalized definition because it attempts to make consistency orthogonal to semantics, ie to defy the fact that the universe of semantics is dynamically unbounded and can’t be captured in a global coherence paradigm.

Requiring the commutative and idempotent properties for the (structural evaluation order of the) lower-level operational semantics converts operational semantics to a declarative localized modular semantic, eg pure functional programming (including recursion instead of imperative loops). Then the operational order of the implementation details do not impact (ie spread globally into) the consistency of the higher-level semantics. For example, the order of evaluation of (and theoretically also the duplication of) the spreadsheet formulas doesn’t matter because the outputs are not copied to the inputs until after all outputs have been computed, ie analogous to pure functions.

C, Java, C++, C#, PHP, and JavaScript aren’t particularly declarative. Copute’s syntax and Python’s syntax are more declaratively coupled to intended results , ie consistent syntactical semantics that eliminate the extraneous so one can readily comprehend code after they’ve forgotten it. Copute and Haskell enforce determinism of the operational semantics and encourage “ don’t repeat yourself ” (DRY), because they only allow the pure functional paradigm.


2 Even where we can prove the semantics of a program, eg with the language Coq, this is limited to the semantics that are expressed in the typing , and typing can never capture all of the semantics of a program— not even for languages that are not Turing complete, eg with HTML+CSS it is possible to express inconsistent combinations which thus have undefined semantics.

3 Many explanations incorrectly claim that only imperative programming has syntactically ordered statements. I clarified this confusion between imperative and functional programming . For example, the order of HTML statements does not reduce the consistency of their meaning.


Edit: I posted the following comment to Robert Harper’s blog:

in functional programming … the range of variation of a variable is a type

Depending on how one distinguishes functional from imperative programming, your ‘assignable’ in an imperative program also may have a type placing a bound on its variability.

The only non-muddled definition I currently appreciate for functional programming is a) functions as first-class objects and types, b) preference for recursion over loops, and/or c) pure functions— ie those functions which do not impact the desired semantics of the program when memoized ( thus perfectly pure functional programming doesn’t exist in a general purpose denotational semantics due to impacts of operational semantics, eg memory allocation ).

The idempotent property of a pure function means the function call on its variables can be substituted by its value, which is not generally the case for the arguments of an imperative procedure. Pure functions seem to be declarative wrt to the uncomposed state transitions between the input and result types.

But the composition of pure functions does not maintain any such consistency, because it is possible to model a side-effect (global state) imperative process in a pure functional programming language, eg Haskell’s IOMonad and moreover it is entirely impossible to prevent doing such in any Turing complete pure functional programming language.

As I wrote in 2012 which seems to the similar consensus of comments in your recent blog , that declarative programming is an attempt to capture the notion that the intended semantics are never opaque. Examples of opaque semantics are dependence on order, dependence on erasure of higher-level semantics at the operational semantics layer (eg casts are not conversions and reified generics limit higher-level semantics ), and dependence on variable values which can not be checked (proved correct) by the programming language.

Thus I have concluded that only non-Turing complete languages can be declarative.

Thus one unambiguous and distinct attribute of a declarative language could be that its output can be proven to obey some enumerable set of generative rules. For example, for any specific HTML program (ignoring differences in the ways interpreters diverge) that is not scripted (ie is not Turing complete) then its output variability can be enumerable. Or more succinctly an HTML program is a pure function of its variability. Ditto a spreadsheet program is a pure function of its input variables.

So it seems to me that declarative languages are the antithesis of unbounded recursion , ie per Gödel’s second incompleteness theorem self-referential theorems can’t be proven.

Lesie Lamport wrote a fairytale about how Euclid might have worked around Gödel’s incompleteness theorems applied to math proofs in the programming language context by to congruence between types and logic (Curry-Howard correspondence, etc).

Imperative programming: telling the “machine” how to do something, and as a result what you want to happen will happen.

Declarative programming: telling the “machine” what you would like to happen, and letting the computer figure out how to do it.

Example of imperative

 function makeWidget(options) { const element = document.createElement('div'); element.style.backgroundColor = options.bgColor; element.style.width = options.width; element.style.height = options.height; element.textContent = options.txt; return element; } 

Example of declarative

 function makeWidget(type, txt) { return new Element(type, txt); } 

Note: The difference is not one of brevity or complexity or abstraction. As stated, the difference is how vs what .

Nowadays, new focus: we need the old classifications?

The Imperative/Declarative/Functional aspects was good in the past to classify generic languages, but in nowadays all “big language” (as Java, Python, Javascript, etc.) have some option (typically frameworks ) to express with “other focus” than its main one (usual imperative), and to express parallel processes, declarative functions, lambdas, etc.

So a good variant of this question is “What aspect is good to classify frameworks today?” … An important aspect is something that we can labeling “programming style”

Focus on the fusion of data with algorithm

A good example to explain. As you can read about jQuery at Wikipedia ,

The set of jQuery core features — DOM element selections, traversal and manipulation —, enabled by its selector engine (…), created a new “programming style”, fusing algorithms and DOM-data-structures

So jQuery is the best (popular) example of focusing on a “new programming style” , that is not only object orientation, is ” Fusing algorithms and data-structures “. jQuery is somewhat reactive as spreadsheets, but not “cell-oriented”, is ” DOM-node oriented “… Comparing the main styles in this context:

  1. No fusion : in all “big languages”, in any Functional/Declarative/Imperative expression, the usual is “no fusion” of data and algorithm, except by some object-orientation, that is a fusion in strict algebric structure point of view.

  2. Some fusion : all classic strategies of fusion, in nowadays have some framework using it as paradigm… dataflow , Event-driven programming (or old domain specific languages as awk and XSLT )… Like programming with modern spreadsheets, they are also examples of reactive programming style.

  3. Big fusion : is “the jQuery style”… jQuery is a domain specific language focusing on ” fusing algorithms and DOM-data-structures “.
    PS: other “query languages”, as XQuery, SQL (with PL as imperative expression option) are also data-algorith-fusion examples, but they are islands , with no fusion with other system modules… Spring , when using find() -variants and Specification clauses, is another good fusion example.

Declarative programming is programming by expressing some timeless logic between the input and the output, for instance, in pseudocode, the following example would be declarative:

 def factorial(n): if n < 2: return 1 else: return factorial(n-1) output = factorial(argvec[0]) 

We just define a relationship called the 'factorial' here, and defined the relationship between the output and the input as the that relationship. As should be evident here, about any structured language allows declarative programming to some extend. A central idea of declarative programming is immutable data, if you assign to a variable, you only do so once, and then never again. Other, stricter definitions entail that there may be no side-effects at all, these languages are some times called 'purely declarative'.

The same result in an imperative style would be:

 a = 1 b = argvec[0] while(b < 2): a * b-- output = a 

In this example, we expressed no timeless static logical relationship between the input and the output, we changed memory addresses manually until one of them held the desired result. It should be evident that all languages allow declarative semantics to some extend, but not all allow imperative, some 'purely' declarative languages permit side effects and mutation altogether.

Declarative languages are often said to specify 'what must be done', as opposed to 'how to do it', I think that is a misnomer, declarative programs still specify how one must get from input to output, but in another way, the relationship you specify must be effectively computable (important term, look it up if you don't know it). Another approach is nondeterministic programming, that really just specifies what conditions a result much meet, before your implementation just goes to exhaust all paths on trial and error until it succeeds.

Purely declarative languages include Haskell and Pure Prolog. A sliding scale from one and to the other would be: Pure Prolog, Haskell, OCaml, Scheme/Lisp, Python, Javascript, C--, Perl, PHP, C++, Pascall, C, Fortran, Assembly

Some good answers here regarding the noted “types”.

I submit some additional, more “exotic” concepts often associated with the functional programming crowd:

  • Domain Specific Language or DSL Programming: creating a new language to deal with the problem at hand.
  • Meta-Programming : when your program writes other programs.
  • Evolutionary Programming : where you build a system that continually improves itself or generates successively better generations of sub-programs.

I think that your taxonomy is incorrect. There are two opposite types imperative and declarative. Functional is just a subtype of declarative. BTW, wikipedia states the same fact.

In a nutshell, the more a programming style emphasizes What (to do) abstracting away the details of How (to do it) the more that style is considered to be declarative. The opposite is true for imperative. Functional programming is associated with the declarative style.

    Intereting Posts