Re: Esoteric XSLT/FXSL question

Hi Justin,

> However "so on" rarely includes "foreach" as a signature function of the FP
> idiom.  Is this because "foreach" implies some kind of time ordered
> calculation, and therefore not optimizable?


Here is the definition from the XSLT 2.0 spec:

  http://www.w3.org/TR/xslt20/#element-for-each

There is no mentioning of the word "time".

Also, nowhere the spec says that the sequence specified in the
"select" attribute is processed in any order.

"For each item in the input sequence, evaluating the sequence
constructor produces a sequence of items (see 5.7 Sequence
Constructors). These output sequences are concatenated; if item Q
follows item P in the sorted sequence, then the result of evaluating
the sequence constructor with Q as the context item is concatenated
after the result of evaluating the sequence constructor with P as the
context item. The result of the xsl:for-each instruction is the
concatenated sequence of items"

There is ordering of the *results*, not of the application of the body
of <xsl:for-each> to the elements of the sequence.

The fact that the results are combined in the order of the original
sequence (after possible sorting if <xsl:sort> children are
specified), does not suppose any ordering in applying the body of
<xsl:for-each> to any item in the sequence -- these may be done in any
order.

Of course, an implementation of XSLT 2.0 may choose to apply
<xsl:for-each> to the items of the sequence in their sequence order:
while this is not mandatory, this is not forbidden. However, such
behavior will be just implementation-specific and there is no
guarantee that any compliant XSLT 2.0 processor will implement it.

This leeway in the spec is good, as it allows good optimization
techniques, related or non-related to lazy evaluation. One that
immediately comes to mind is parallel application of <xsl:for-each> on
many items of the sequence (likely dependent on the available free
CPUs in the system) with subsequent combination of the results, so
that they would be in the desired order.

In fact, I regard <xsl:for-each> as a synonym for the FXSL f:map() function.

The definition of the function is the following:

http://fxsl.cvs.sourceforge.net/fxsl/fxsl-xslt2/f/func-map.xsl?view=markup


   10     <xsl:function name="f:map" as="item()*">
   11       <xsl:param name="pFun" as="element()"/>
   12       <xsl:param name="pList1" as="item()*"/>
   13
   14       <xsl:sequence select=
   15        "for $this in $pList1 return
   16           f:apply($pFun, $this)"
   17       />
   18     </xsl:function>

which is essentially what <xsl:for-each> is supposed to do (ignoring
any <xsl:sort>).



-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play



On Wed, May 28, 2008 at 10:47 AM, Justin Johansson <procode@xxxxxxxxxxx> wrote:
> XSLT has been shown to be a member of the "Functional Programming (FP)
> Family of Languages".
>
> see:
> http://fxsl.sourceforge.net/articles/FuncProg/Functional%20Programming.html
>
> From the above, and other observations, it is fair conjecture that XSLT is
> more "functional" as opposed to "imperative".
>
> The FP idiom, sporting lazily and readily optimizable computation, suggests
> that functions can be forced to produce a result (i.e. actually calculate
> something) only when the result is needed for some ultimate calculation.
> This is achieved thru side-effect-free realization of functions.  Given
> this, then a side-effect-free aware functional optimizer can execute
> "stuff" in any order (so long as the computations have no side-effects).
> Somehow, the notion of calculation, in an FP sense, sublimes time and
> therefore ordering of output.
>
> Now, the FP alphabet of functions includes as its signature functions,
> "map", "fold" (aka "reduce") and so on.
>
> However "so on" rarely includes "foreach" as a signature function of the FP
> idiom.  Is this because "foreach" implies some kind of time ordered
> calculation, and therefore not optimizable?
>
> Noting that xsl:foreach always produces the same ordered output (in a
> result document), does this imply that XSLT breaches the pure FP idiom,
> recognizing, of course, that XSLT has never claimed to be an FP language?
>
> Perhaps I've been eating too much monadic fungi, but there seems to be a
> something about the essence of "foreach" as opposed to, say, map, in an FP
> context that needs explanation.
>
> Whatever the explanation, it still seems difficult to me to say what the
> heck of a kind of a language XSLT actually is :-)
>
> Cheers
>
> Justin Johansson
>
> P.S. Dimitre, thanks for your response on a prior thread :-
>
>> The woe for me however is having to counter the screams I'll no doubt get
>> from the library-developer (Javascript) users & also the hassle of
>> converting indexes on the external library side
>
> This is the least problem you might have. Be ready to explain why an
> xsl:variable cannot be modified...  :)