[TYPES] Declarative vs imperative

[Vladimir Lifschitz]

> > A program in an imperative language describes an algortithm.
> > A program in a declarative language describes a specification.
> 
> But one man's specification is another man's algorithm.  Even in Haskell,
> one writes a sorting program typically by choosing a particular
> algorithm (heap sort, quick sort, ...).  Sure, these can be considered
> specifications of sorting, but they are hardly the most abstract spec
> for sorting.

The way I see it, the difference between declarative and imperative
programs is as clear-cut as the difference between declarative and
imperative sentences in natural languages: "I like it" vs. "Sit down".
A declarative sentence can be true or false; an imperative sentence
can be executed or not executed.

Here is how sorting is done in answer set programming (I learned this
from Roland Kaminski):


order(X,Z)                    % X is the predecessor of Z
   :- p(X;Z),                 % if both X and Z belong to p,
      X<Z,                    % X is less than Z,
      #false : p(Y),X<Y,Y<Z.  % and no element of p is between X and Z.


A declarative program may look similar to a procedural program if they
use similar data structures.  Still, the difference is clear: a (truly)
declarative program describes what is counted as a solution; a procedural
program tells us which operations to perform.

Vladimir