Re: [Fwd: Re: Language is not markup and markup is not language.]

[David LeBlanc <whisper@xxxxxxxxxxxxx>]

Can you write an XSL processor in XSL? If so, I would agree it's Turing
complete; otherwise not.

At 10:28 PM 5/11/99 +0700, you wrote:
>Paul Prescod wrote:
>> 
>> David Carlisle wrote:
>> >
>> > Is it clear that it isn't complete anyway?
>> 
>> I'm not up to proving that XSL isn't Turing complete but I will give some
>> hints about why I think that it isn't:
>> 
>> > You have recursive calls, and can pass state via template parameters
>> > what else do you need?
>> 
>> You can pass state but can you work with the state? Remember that the
>> Turing machines has not only a concept of "current state" but also its
>> tape. What would we use in XSL to emulate the tape? The obvious choice is
>> a string, but how do you index to a particular location in the string? The
>> string manipulation functions don't seem up to the job.
>
>You can use a string that separates the representation of each location
>by some delimiter (say a /); then you can use basic arithmetic,
>recursion and substring-before/substring-after to index to a particular
>location.
>
>It seems fairly clear that the language is now Turing complete.
>
>> Compared to early drafts, however, it is incredibly flexible. Only time
>> will tell what optimizations are feasible but it is safe to say that some
>> optimization opportunities have probably been lost. With the early drafts
>> statically type checking and optimizing seemed almost doable but by now I
>> am very skeptical. Maybe we need a smaller, more optimizable XSL subset
>> for some applications....
>
>It's possible now to write XSLT stylesheets that will be very hard to
>optimize; but that's always been possible; for example XSL has always
>had recursive macros. I don't think the addition of new capabilities to
>XSLT need prevent optimization. If you had some stylesheet that could be
>expressed using an earlier WD, then it can still be expressed in a
>similar way in the current WD and it is equally susceptible to
>optimization. If an optimization would be possible except for some new
>feature in XSLT, you don't have to completely give up on that
>optimization, rather you can analyze the stylesheet to determine whether
>it makes use of that feature and then only apply the optimization if the
>stylesheet does not make use of the feature.  
>
>James
>
>
> XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
>
>


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list