Defining `Declarative`

I’ve seen many definitions for `declarative programming`. The term `declarative` is often contested because it has connotations and market buzz surrounding it – i.e. there is some advantage to saying your product is `declarative` even if that means stretching the term. I freely admit that I might be guilty of this, too.

My understanding of `declarative` is that it describes a synergistic intersection of several useful properties. Consequently, I can place languages on a lattice for just how declarative they happen to be. This article explains how I reach the definition I favor.

I start with the informal notion of `declaration`:

declaration: an explicit (written or oral) statement or indication of fact, opinion, or belief.

I believe a declarative programming language should enable expressing a program in terms of declarations – not just one big declaration, but a bunch of smaller statements each indicating a fact, opinion, or belief about the program’s behavior. For programming, of course, I’m primarily interested in written declaration.

How am I to recognize that an expression is a declaration? Well, I compare to some ideal properties of declarations.

  1. Explicitly stating the same fact, opinion, or belief twice in a given context doesn’t affect its meaning or truth.
  2. Source, location, and origin of a fact, opinion, or belief doesn’t affect its meaning or truth. Though, it is sometimes useful to track origin as part of the fact (e.g. `David believes that declarative is …`).
  3. Facts, opinions, and beliefs have a `continuous` nature – they hold over time. We can express statements about past events (e.g. `the ball went through the hoop`) but even such statements are true `over time`.
  4. Facts, opinions, and beliefs will name, describe, and relate objects in an implicit environment or system (e.g. `the ball`, `the hoop`). Thus, the meaning of a declaration is actually a function of its environment.

Formalizing these concepts gives me the properties I now associate with `declarative` expression:

  • idempotent: declarative expressions can be duplicated, and duplicate expressions can be eliminated, without affecting behavior of the program.
  • commutative: declarative expressions can be reordered or reorganized without changing their meaning.
  • concurrent: declarative expressions naturally hold at overlapping times. Declarative systems are implicitly concurrent in the sense of separate expressions holding simultaneously.
  • reactive: declarative expressions hold over time and have meaning relative to their implicit environment. If the environment changes over time, so will the active meaning of the declarative expression. [upd. 1/13]

Some people say that declarative is about eliminating `control flow`, but I understand that as a natural consequence of commutativity and concurrency – and to only be skin deep: control flow isn’t implicit in the syntax. In my experience, declarative programming is excellent for modeling ad-hoc control flows and work flows in terms of observations and declared rules of action. I point to Berkeley’s Dedalus paper as offering several good examples.

Some people argue that declarative is about `referential transparency` or `purity`, but I reject this. Declarations don’t have a `value` so much as they have a meaning relative to their implicit environment. However, idempotence and commutativity together do allow most of the same abstraction and refactoring advantages achieved by referentially transparent code.

Some people claim that declarative is about `what not how`, but there isn’t any fundamental reason we cannot declare hows instead of whats. To be honest, I’ve never understood the `what not how` argument – what vs. how is a difference in perspective, whether you’re looking up or down the ladder of abstraction. A clever man might try `why not how`. But, again, this seems orthogonal to the notion of declaration – the decision to declare motivation, intention, or mechanism is just stages of abstraction.

There is simplicity and elegance in having `declarative all the way down` or `everything is declarative`, including IO. The input to such a declarative program is a set of declarations – essentially, another declarative program. And so is the output. That implies a declarative representation of implicit environment and computed demands, of observation and influence. Such a design would be useful for abstraction, staging, typing, metaprogramming, embedding and extending languages. Declarations of what, why, and how are mixed in a single program, together with declarations to combine and compile them.

Of course, the benefits of `everything is a` designs are hardly unique to declarative. Similar benefits have been argued for functional, OOP, procedural.

While I don’t list `everything is a` as a criterion for declarative, it would be a fair point in a comparison between languages if arguing which is `more declarative`. Though, I’m not sure the argument itself would have a point. While `more declarative` is better if all else is equal, all else is probably not equal.

There are many programming models that I count as highly declarative under my definition: constraint, logic, temporal constraint, temporal logic, generative grammars, relational, various forms of dataflow, synchronous reactive, event calculus, functional reactive, and reactive demand. These models vary considerably in other characteristics – composition, security, resource management, completeness, staging, etc.. But they are all very declarative.

On the other hand, there are many systems that are ostensively `declarative` – such as HTML or pure functional programming – that I consider to be relatively weak examples of declarative programming (e.g. due to having poor idempotence or commutativity of expressions). Sure, HTML is more declarative than PostScript. And pure functional is somewhat more declarative than procedural (and certainly more cleanly staged). But they aren’t very high on the declarative lattice.

I posit that functional programming is `declarative` primarily to the extent one is functionally constructing a declarative program.

Advertisements
This entry was posted in Glossary, Language Design. Bookmark the permalink.

7 Responses to Defining `Declarative`

  1. The ‘reactive’ property seems the wrong one here. Because it is essentially true of *all* languages. (All languages relate to something external, hence are dependent on it, otherwise they could not be used for anything.)

    What you are getting at seems like the ‘internal structure’ of the language — the relations between parts, not between them and the outside. The other properties (idempotent, commutative, concurrent) seem internal. And they seem to delineate a particular kind of language — so look interesting.

    This definition seems to reject hierarchy — as in the example about HTML. That is also interesting. It leads to questions about what hierarchy *does*, how ‘simple’ it is, and so on.

    (Maybe this definition of declarative is somewhat reminiscent of logical atomism, like (early) Wittgensteinian ‘facts’ . . .)

    • dmbarbour says:

      Interaction with an environment is not a sufficient condition for reactivity. A procedural statement, for example, might observe and manipulate the environment but will not remain active while the environment continues to change. Declarative expressions are `reactive` because they are `continuously active` over the course of the environmental changes. I should have been more explicit.

      Hierarchical expression is possible with declarative systems. Most use-cases I envision involve controlling or enhancing the relationships between internal expressions and the external environment – e.g. membranes, sandboxes, partitioning of external state spaces (e.g. different subdirectories to different subexpressions), abstraction and vocabulary extensions (`let foo = _ in _`), resource discovery and selection. Use of staged abstraction is inherently hierarchical. It seems to me that hierarchy is orthogonal to declarative.

      The declarative weakness of HTML is primarily that relative position of each toplevel expression has implicit meaning for the whole program. One might roughly summarize `declarative` as the elimination of implicit spatial-temporal meaning.

  2. shelby says:

    1. HTML is commutative when employing CSS ‘position:fixed’ or ‘position:absolute’ with distinct ‘z-Index’ properties.

    2. Declaring an environment-independent order (e.g. not time-dependent) is a valid declaration that doesn’t violate the concurrent and reactive properties, and thus should be allowed to selectively disable the commutative property. CSS ‘position:relative’ is declarative ordering with respect to the parent, analogous to a function call or an attribute argument list of the parent declaration.

    3. HTML is not idempotent, not even when employing duplicate ‘id’ attributes, because duplicate ‘id’ attributes are illegal and have undefined behavior.

    4. Conceptually analogous ditto #2 for #3, idempotence could be selectively disabled, for as long as there is no environment dependency and thus concurrent and reactive properties are not violated. For example, declaring an event handler that creates a new object. Otherwise how can declarative programming create new objects?

    5. How can declarative programming most generally interopt with environmental state, i.e. what is the general model of declarative interoption of modules?

    Assume a referentially transparent (RT) expression, that calls a pure function and that function inputs an immutable copy of the environment and returns a modified copy of the environment. Assume an non-RT expression which contains that RT expression and stores the value of the returned environment. This non-RT expression is equivalent (except for atomicity of multiple changes) to calling an impure function that inputs an immutable copy of the environment and within the function writes state changes to the environment. It is critical that this impure function does not read changes to the environment, i.e. it is pure other than written side-effects to the environment, thus the concurrent and reactive (and even parallelism) properties are not violated.

    I have written about how to implement this with type safety using Scala dependent method types.

    This impure function is analogous to an Erlang-style Actor. It sends messages (writes) to the environment, and responds to messages (reads) only from its arguments it is called. The key revelation of Actors is they interface with the environment declaratively, in that they can exchange state only via incoming messages and that the order messages are received is asynchronous (i.e. undefined, thus sends and receives are commutative).

    An Actor that reads mutable state (not from the input message arguments), even if it is persistant (between input messages) state, is not pure and thus not reactive and thus not declarative. The read expressions are not RT, and thus are not modular for composition. This Serializer type of Actor is necessary to do coordination or to have deterministic persistant state (there is dynamic, stochastic and potentially resilient state in the distributed actors). Note that message sends are RT within the scope of processing a single input message, and thus are modular for composition of the programming an Actor’s message processing function.

    6. Persistent immutable data structures with structural sharing are the most efficient for exchanging mutated state. Rich Hickey discusses this (see 23:50min). The atomicity of state changes in the Actor model are handled either by the fact that a message receive is atomic, or for multiple coordinated Actors using an intermediary Serializer. The Lost Update Problem should be handled in the messaging protocol, e.g. “add to list if not already in list” or “write this value, if current value is this old value, else…” (include an edit id in immutable structures for faster distributed equality comparison).

    7. Comments on Hickey’s criticisms (see bullets in the “Message Passing and Actors” section).

    * Deadlock should be impossible because there is no way for an Actor’s message processing function to lock a resource on another Actor and wait before replying to the input. A deadlock requires two process to lock the same two resources in opposite order and wait for the locks. It is true that timeouts (stored in a Serializer for persistence) will be necessary on expected callback replies, which makes more resilient and modular programs, even if the persistent (shared between Actors by persisting between input messages) state is all on the local machine (e.g. crashed modules). Non-persistent local data can be r/w directly with no messaging. A non-serializer Actor’s message handling function is pure (except for sending msgs to other Actors), thus it can be serialized to send it to a distributed instance, thus the bifurcation should not occur and should be handled in the Actor library.

    * Afaics, the Actor library can be just as efficient between local Actors. I showed that function calls are equivalent to message passing in #5 above.

    * Afaics, it is good modular, resilient design. The Serializer Actor enables coordination.

    * Afaics, the Serializer Actor can be a local persistent state store to give same non-distributed semantics.

    8. Comments on David Barbour’s criticisms (see bullets in the “Some ActorsModel Skepticism” section).

    * Why can’t a timeout be placed on expected callback reply to a message? This can be stored in the Serializer. As for the code for the non-serializer Actor, this is a caching not a garbage collection issue, since it can have only one value. Distributed values are copies and can be discarded immediately upon return of Actor message processing function.

    * What is wrong with a persistent serializer?

    * In my vision, there is a serializer that is coordinating which Actors are responding to which events. So the CPS could update the behavior for an event at the Serializer.

    9. I am adding the concept of a Future, which encapsulates a callback as an immutable value, so that multiple callbacks can be multiplexed as Future objects as arguments in pure functional composition within the Actor’s message processing function. When the value is needed, it will callback on function supplied to the Future.get and then return from the Actor’s message processing function.

  3. shelby says:

    My prior comment apparently went into WordPress’s spam queue, so here is a link to it.

    http://goldwetrust.up-with.com/t112p240-computers#4725

    [original version now un-spammed]

  4. shelby says:

    Where I wrote, “except for atomicity of multiple changes”, I forgot to note that the order messages are received is not guaranteed in the Actor model. The comparable pure function that returned a list of changes to the environment, would also not be able to guarantee that the order would remain the same as they were added to the list, otherwise the implementation of the function wouldn’t commutative (and thus not declarative). If the returned list was ordered logically (supplying an order number for each item in the list, irrespective of the order added to the list), the implementation of the comparable pure function could also be commutative and thus declarative.

    The point I am making is that declaring messages within the Actor’s message handling function, does not make the function impure (nor imperative), due to the context of message order being undefined (i.e. asynchronous). Since the message order is undefined, then atomicity and order is not the goal. As noted in prior paragraph, It is possible to enforce order purely and declaratively, but apparently that would be impractical in the distributed context.

    • dmbarbour says:

      Actors model systems are not declarative. The order in which messages are processed is clearly observable. Duplicate messages can easily have double effect. The contents of a message cannot change based on new observations. Commutative, idempotent, continuous, reactive – actors model has none of these properties.

      Even if messages were augmented with declared order or timing, challenges would remain to ensure actors observe the messages consistently with this order (for keeping local state and computing messages), and that duplicate messages do not double effect.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s