Denotative

On page 8 of The Next 700 Programming Languages, Peter Landin introduces the word denotative as the direct opposite of the term imperative. To be considered denotative, Landin stipulates the following conditions for the expressions of a programming language:

(a) each expression has a nesting subexpression structure,
(b) each subexpression denotes something (usually a number, truth value or numerical function),
(c) the thing an expression denotes, i.e., its "value", depends only on the values of its subexpressions, not on other properties of them.

A programming language is trivially denotative if it only permits programs to be defined in terms of denotative expressions.

Being privately imperative

In 1994 researchers discovered a way to denotatively accommodate the imperative style by excluding the use of externally visible side-effects. For example:

type Graph = Array Vertex [Vertex]
data Tree a = Node a [Tree a]

dfs :: Graph -> [Vertex] -> [Tree Vertex]
dfs g vs = runST (
              newSTArray (bounds g) False >>= \ marks ->
              search marks vs
           )
  where search :: STArray s Vertex Bool -> [Vertex]
                  -> ST s [Tree Vertex]
        search marks   []   = return []
        search marks (v:vs) = readSTArray marks v >>= \ visited ->
                              if visited then
                                 search marks vs
                              else
                                writeSTArray marks v True >>
                                search marks (g!v)    >>= \ ts ->
                                search marks vs       >>= \ us ->
                                return ((Node v ts): us)

from Figure 2 (page 17 of 51) of State in Haskell

Even though dfs's local definition:

        search :: STArray s Vertex Bool -> [Vertex] -> ST s [Tree Vertex]

uses mutability and sequencing, the use of runST keeps those imperative details confined to dfs, hence its denotative type:

dfs :: Graph -> [Vertex] -> [Tree Vertex]

Therefore to be denotative, a programming language only needs to avoid using side effects which are externally visible: namely those of I/O.

Practical considerations

But most users want to interact with their programs, including those written in denotative languages! That requires I/O to be managed by the denotative language's implementation, with parts of it written in a non-denotative (I/O-capable) programming language.

This need for a non-denotative language though presents a dilemma:

• if it's too different from the denotative language, it's likely that users will request or attempt to add an I/O mechanism to the denotative language (to avoid having to extend the implementation);

• if it's quite similar to the denotative language, users could do all their programming in it and simply ignore the denotative language (as writing a program in multiple languages is often tedious).

It remains to be seen whether these two opposing requirements can be reconciled.