[TYPES] [tag] Re: Declarative vs imperative

[Adam Smith]

(resending after actually signing up for types-list)

Vladimir's way distinguishing declarative vs imperative programs is indeed
clear-cut, but let me offer an explanation why it's not going to convince
every programmer or language designer. The key idea is that languages of
one type are usually rich enough enough to support an embedded language of
the other type (or possibly many layers like this), and the experience of
the programmer/designer may so strongly focus on the embedded languages
that the properties of the outer language become largely inconsequential.

Concretely, if you come across a large collection of declarative statements
that are semantically about imperative commands, you start to simply read
through the declarative aspects and see the imperative program as the real
one. Here are a bunch of declarative statements (that are simply true):

~ The first step of the algorithm is to set a variable called "maxlen" to
"0".
~ The second step of is to enact a for-loop over the variable "j" from "0"
to "2".
~ The body of this loop is the action of setting "maxlen" to the maximum of
the value of "maxlen" and the length of input value "j".

The following example is from an on-going project involving using answer
set programming to reason about the different possible execution paths
through imperative code. At the surface level, it's just one giant
declarative AnsProlog fact that states that "add(....) is a procedure". For
all other purposes (including capturing an idea in code and debugging its
representation on the basis of it's example executions), it's a pile of
quite imperative code.



procedure(
  add(

    set(maxlen, 0),
    for(j,0,2, do(
      set(maxlen, max(maxlen,input(len(j)))))),

    set(c, 0),

    for(i,0,maxlen, do(

      set(k,0),
      for(j,0,2,do(
        if(lt(i, input(len(j))), then(
          set(k, plus(k,input(n(j,i)))))))),

      if(lt(0, c), then(
        set(k, plus(k,c)))),

      set(c, 0),
      if(lt(9, k), then(
        set(c, hi(k)))),

      set(output, digit(i,lo(k))))),

    if(lt(0, c), then(
      set(output, digit(i,c)),
      die(special))),

    die(end_of_procedure)
)).

This specification of a concrete algorithm is interpreted by a compiler (or
is it just a specification for a compiler?) that transforms it into another
specification cast in terms of assembly-like primitives:
http://pastie.org/7698516 (following one particular compilation strategy
amongst many). Finally, it is executed (in a sense) by an abstract
processor with a program counter, registers, and application-specific ALU
pathways. The result, in terms of the answer sets of the overall answer set
program, describe the set of all branching pathways that could be explored
by the algorithm on the basis of unseen (nondeterminsitically chosen)
inputs.

At one level, I've only ever entered facts and rules that I trust the
solver will consider as a collection (but in no particular order). At
another level, I've built a procedural pipeline: compile, assemble,
generate processor, generate program inputs, execute program on processor,
summarize observed pathways. At yet another level, I've written a program
in a (made up) language that legitimately has its own operational semantics.

In traditional Prolog, every rule you write can be read as simply a
statement of a fact in the :-/2 predicate (clause/2). As a programmer,
however, you might your rules as imperative lists of execution steps for
backwards chaining -- because that's what the :-/2 rules most clearly seem
to be talking about. Meanwhile, once you get into making meta-interpreters
(quite common, I believe), you quickly go back to treating instances of
:-/2 as declarative statements of the structure of some data, a
specification of a case in some formal structure.

At every level, whether the language is imperative or declarative is quite
clear-cut, what's not at all clear is which level is the relevant one to
talk about.


>
>
> On Mon, Apr 22, 2013 at 10:26 AM, Vladimir Lifschitz <vl at cs.utexas.edu>wrote:
>
>> > > 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
>>
>>
>>
>>
>