From HaskellWiki
Jump to: navigation, search

On page 8 of his paper 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.

Practical considerations

Of the three conditions, (c) is the most interesting from the viewpoint of an implementation: the absolute requirement for an expression to depend solely on the values of its subexpressions - not its ordering relative to other expressions, or any observable use of effects (e.g outside interactions) - requires an implementation to accomodate all the imperative mechanisms needed to make the use of denotative programs commonplace, in contrast to the current trend of moving the subsequent complexity out of the implementation into the language:

For example, we want to have lazy file reading. If it cannot be implemented in Haskell then it will have to be implemented "underground" as a primitive operation written in C or machine code. The same goes for unique-supply trees and lazy arrays.
Implementing such operations in C does not make them more hygienic or easy to reason about. On the contrary, it is much easier to understand, modify and construct variants of them if they are implemented in a Haskell library module than if they are embedded in the runtime system.

State in Haskell, John Launchbury and Simon Peyton Jones (page 45).

It remains to be seen whether the two seemingly-opposite approaches can be reconciled.