Re: Limited complexity requirement?

On Thu, 2004-07-15 at 13:14, Jim Hendler wrote:
> At 7:54 -0700 7/15/04, Dan Connolly wrote:
> >While thinking about xquery-based designs, I realized I have been 
> >assuming the following requirement. What do other folks think?
> >
> >3.X Limited complexity
> >
> >Less expressive languages are easier to implement, deploy, secure, 
> >and optimize (cf the Principle of Least Poser in an essay on design 
> >principles for the Web[1]). Since a large and interesting class of 
> >applications can be addressed with query languages that are less 
> >expressive than programming languages, this design should not 
> >involve a turning-complete query evaluator. The halting problem must 
> >not be expressible in this query language design.
> >
> >[1] http://www.w3.org/DesignIssues/Principles
> 
> Dan - while I agree with the goal of this, I'm not sure the wording 
> is correct - that is, I don't think what you're after has to do w/the 
> ability to express the halting problem, and I suspect that given that 
> RDF graphs, being actually "pseudo graphs" (since they can have 
> multiple links between same nodes) and allowing cycles, it is 
> possible to express queries even in simple languages that could have 
> halting issues - remember that decidability is in the problem, not in 
> the language used to express it

hmm... I meant to say "without using optional extensions" or something,
but maybe that doesn't cut it either...

>  (I can give you trivial problems that 
> are undecidable, for example stacking one block on another when each 
> block has a separate controller) -- I think if we simply drop the 
> last sentence it is closer to what you actually want to say (Turing 
> completeness is in the language, decidability/halting is in the 
> problem) so "yes" to:
> 
> 3.X Limited complexity
> 
> Less expressive languages are easier to implement, deploy, secure, 
> and optimize (cf the Principle of Least Poser in an essay on design 
> principles for the Web[1]). Since a large and interesting class of 
> applications can be addressed with query languages that are less 
> expressive than programming languages, this design should not involve 
> a turning-complete query evaluator.

Well, that's only should-strong. A design like javascript or
XSLT would pass it, if there's some justification for going
turing-complete.

hmm..

"... must not involved a turing-complete query evaluator"?


>   -JH
> p.s. Sorry, going on 20 years as a Professor of Computer Science has 
> made me overly literal on these things.
-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/

Received on Thursday, 15 July 2004 16:00:20 UTC