Re: [xml-dev] RE: Declarative programming requires a different mindset

[David <dlee@calldei.com>]

Good question.  I actually have an XQuery Language class  I have to teach at work next week (Blind leading the blind !)
And I need to describe the same thing.

Here's my novice insight.   Correction appreciated.

Here's a key, someone on this list (and I apologize for forgetting whom) said that a way to think of declarative languages is that the dont have a time component.
I really like that idea.  That is *NOT* the same as saying everything can be done in parallel !! Its saying that time is not part of the equation.
So you cant make ANY statements about time (parallel or sequential are both time statements).
So I prefer to use "expression" rather then "statement" because "statement" drags with it a sequential interpretation.

But here's the other thing.  Declarative expressions can have dependencies.  The evaluation of a declarative expression must act as if the dependencies are resolved before they are used ... but thats adding Time back into the equation ??!!?? .  Not exactly.

 Lets try to think without time.

Your example is really just something like this:
  
    let $a := 1, $b := $a;

Or
    foo(bar())

In both cases there are explicit dependencies.   If you add time to the equation you'd say "A must be set before B" or "bar must be called before foo".
But in a declarative language thats not quite true.   Whats true (IMHO) is that the end result must take into account those dependencies.
And it could do so any way it wants, including parallelism ... as long as the results come out right.
But time does not come into the *definition* of the language, only the implementation (until we have quantum xquery processors ) the order of evaluation.

For example, in the first case, a processor could simply assign 1 to both $a and $b in parallel.  Or notice that $a is never used and just assign $b := 1.
For the second example, it could inline the evaluation of bar() symbolically, then see where in foo the expression is used, and may not actually *evaluate* bar until later, if ever, although I think in XQuery's case dynamic error analysis may be difficult postponing the evaluation of bar() (inlined or not) past the entry point of foo().   I think its *possible* though as long as the error was detected before the end of the program.

So the end result.  Even if you have an infinitely parallel computer, dependancies do affect the actual run time of a declarative language.
Although the the language is careful to not impose exactly what those effects are, noone's invented a way to solve expressions with dependencies
without doing them in some order ... atleast on a Van Norman machine - even with infinite number of processors.
So the language isnt saying "everything can be done in parallel" ... (thats adding time).  Its saying "Were not going to tell you how you have to do it, but you do have to obey the rules of dependency somehow"    Maybe a quantum computer will solve everything ... (although I dont quite buy that yet ...)

-David

-------------------------
David A. Lee
dlee@calldei.com
http://www.calldei.com
http://www.xmlsh.org

On 3/24/2010 7:49 AM, Costello, Roger L. wrote:

5161E497-3B5C-4084-AE01-D19032EDFBC7@mimectl" type="cite">

Hi Folks,

 

It is my understanding that a key characteristic of declarative programming is that statements can be executed in any order, even in parallel. Do you agree?

 

If yes, then anything which forces sequential processing is, by definition, not declarative. Do you agree?

 

At the bottom of this message is a variable, namespace-map, which is then used by the second variable. The first variable must be created _before_ the second variable. Thus, a sequential processing is required and therefore it is not declarative.

 

Wait. That can’t be right.

 

Then I can’t create building blocks which can be used to create larger building blocks. The first variable is a building block that the second variable builds upon. Surely, assembling building blocks is important in declarative programming?

 

What is the right way to think about variables that use other variables? Is it bad, from a declarative programming perspective?

 

<xsl:variable name="namespace-map"

     select="document('')/*//f:namespace-map

         [f:input-document/f:namespace=$ns]" />

 

<xsl:variable name="use-this-namespace"

      select="$namespace-map/f:output-document/f:namespace" />

 

/Roger