[TYPES] Declarative vs imperative

[Chung-chieh Shan]

On 2013-04-19T22:34:00+0100, Uday S Reddy wrote:
> > I once defined "declarative programming" as "the division of _what_
> > to do and _how_ to do it into two modules that can be built and
> > reused separately."  
> 
> Sorry, I don't buy it.  The distinction of what vs how, i.e., external
> behaviour vs internal implementation, exists for *every* software system
> implemented in *every* conceivable programming language.  I don't see what
> this has to do with being "declarative".

I agree that the distinction exists all over the place, and indeed it's
probably always clear in your mind.  Being "declarative" means making
the distinction not only in your mind but also in code (more generally
in formal artifacts) so that you can easily change the "what" without
reimplementing the "how" or change the "how" without reimplementing
the "what".  That's what I meant by "two modules that can be built and
reused separately".  In particular, for a programming language to be
declarative (with respect to some "what"/"how" distinction) is for the
distinction between programs written in the language and implementations
of the language to follow the distinction you refer to.

> I was taught programming when I was a second year undergrad, using Dijkstra
> & Wirth-style top-down design and stepwise refinement.  So, I always thought
> of imperative programming in "denotative" terms.  What vs how were always
> clear in my mind.  I probably saw Landin's paper in the months and years
> that followed (as I looked through every CACM paper on programming languages
> from the 60's and 70's), and probably didn't understand the point of it.
> The distinction between denotative and procedural languages that Landin
> makes would have seemed to me to be a false dichotomy.  It is perfectly
> feasible for something to be "procedural" as well as "denotative".  So, what
> is he talking about?
> 
> After maturing, I have learnt that many people really have a big mental
> block about thinking of things as being procedural as well as denotative.
> Simon Peyton Jones seems to have finally conquered this brain space by
> explaining the things belonging to the IO types as "actions".  That seems to
> make sense to people.  Three cheers to him!

With respect to a given "what"/"how" distinction, a software system or a
programming language can be either declarative or not.  The same thing
can be declarative with respect to one "what"/"how" distinction yet not
with respect to another, just as a person can be tall with respect to
one height standard yet not with respect to another.  It doesn't require
any mental block to think of the same thing (such as me) as both "tall"
and "short" (with respect to different height standards), and it doesn't
require any mental block to think of the same thing (such as Haskell)
as both "declarative" and "not declarative" (with respect to different
"what"/"how" distinctions).

> And, let us not get carried away with "real world" ideas.  The "real world"
> has been using imperatives for millennia before we got into the game.  We
> didn't invent imperatives.  I believe Vijay was talking about a particular
> class of users and a particular class of applications where a declarative
> interface is the right layer of abstraction.  If he were to talk about a
> stock trading system or an on-board flight control system, the right layer
> of abstraction could very well be an imperative one.  There is nothing
> "unreal world" about imperatives (or "actions" as Simon calls them).

Indeed, your notion of "imperative" is entirely consistent with being
declarative.  If "what" we want to do is to perform IO, a language of IO
action combinators can be declarative (and imperative).  If "what" we
want to do is to parse sentences, the very same language would probably
not be declarative.

> PS You were probably confusing Strachey with Dana Scott.  Strachey worked on
> the semantics of imperative programs.  Scott worked on the semantics of
> recursion, using partial orders (and he also collaborated with Strachey on
> semantics of imperative programs).  A good place to read about Strachey's
> semantics is the book by Mike Gordon, a classic book that I also happened to
> read as an undergrad.  It is easy to find used copies of it these days
> because a lot of stupid libraries around the world are getting rid of their
> copies.
> 
> http://www.amazon.co.uk/The-Denotational-Description-Programming-Languages/dp/0387904336/ref=sr_1_1?ie=UTF8&qid=1366406702&sr=8-1&keywords=gordon+denotational+description

Indeed, the specific domain in which Strachey fixed Landin's problem is
not even the domain of all partial orders, but only some of them.