W3C home > Mailing lists > Public > www-tag@w3.org > December 2005

Re: Initial Draft Finding on Principle of Least Power

From: Harry Halpin <hhalpin@ibiblio.org>
Date: Tue, 20 Dec 2005 11:15:03 -1000
Message-ID: <43A87457.5070303@ibiblio.org>
To: www-tag@w3.org

There are good examples of non-Turing complete languages that make sense
to your ordinary programmer on the street, such as regular expressions.
Also, Henry noted with his functionalXML thinking that plain-old linear
pipelines are not Turing complete. Original core SQL i.e. SQL 92/96 is
not Turing complete, but SQL99 (SQL3) is.

 I might add that the characterization of functional programming
languages as somehow  "less powerful" than procedural languages might
want to be - i.e. "through those that are functional and Turing complete
(Haskell), to those which are unashamedly procedural (Java, Javascript,
C)" - should be rephrased, since this will offend functional programmers
who would argue the *exact* opposite :)

If I remember correctly, you get Turing-completeness is you get
variables and unbounded loops combined with the rather subtle effect of
having having arbitary effects at arbitrary steps in the computation. I
think it's the last requirement that makes proofs of Turing completeness
rather subtle [1].

In general, I think it might be a good having Wenfei Fan take a look at
this (wenfei@inf.ed.ac.uk <mailto:wenfei@inf.ed.ac.uk>). Database
researchers like him care *a lot* about language power and
Turing-completeness, since the last thing they want is a database query
which can't be guaranteed to ever return a result (i.e. why SQL was
originally non-Turing complete). I remember him once proving to me that
XPath 2.0 was Turing complete while XPath 1.0 wasn't, but I cannot
remember the details right now.

If one wanted to talk about SemWeb stuff, one could point out that some
problems are undecideable if even a Turing-complete machine be proved
capable of solving them, and one of these problems is inference in FOL,
while weaker logics like description logics (ala OWL-DL/Lite/RDF Schema)
have decideable inference.

Excellent writing in general!

                              -harry

[1]http://www.mulberrytech.com/Extreme/Proceedings/html/2004/Kepser01/EML2004Kepser01.html
Tim Berners-Lee wrote:

>
> Noah,
>
> Looks good, in general -- Thank you for doing it.
>
> I had thought Roy had said a Principle was a reasonable epithet here 
> - but I may remember wrongly.
>
> The PLP bit was added to the Principles DesignIssues note at revision 
> 1.10, in January 2002.
> I'm not sure whether it was taken from a previous location.
>
> I'd like to change the wording of the bit about RDF to not talk about 
> RDF in the HTML file
> but compare and HTML file with an RDF file.  The business of mixing 
> them is a distraction.
>
> As regards SQL and truing completeness, I had assumed that it wasn't 
> but then I seem to remember
> being told it was.
>
> Tim
>
>
> Annotations for Principles.html
> ***************
> 1.10         (timbl    12-Jan-02): <!DOCTYPE html PUBLIC "-//W3C//DTD 
> HTML 4.01 Transitional//EN"
> 1.10         (timbl    12-Jan-02):     "http://www.w3.org/TR/html4/
> loose.dtd">
> 1.1          (timbl    09-Sep-99): <html>
> 1.1          (timbl    09-Sep-99): <head>
> 1.10         (timbl    12-Jan-02):   <meta http-equiv="Content-Type" 
> content="text/html">
> 1.1          (timbl    09-Sep-99):   <title>-- Axioms of Web 
> architecture</title>
> 1.9          (timbl    08-Jan-01):   <link rel="Stylesheet" 
> href="di.css">
> 1.1          (timbl    09-Sep-99): </head>
> 1.1          (timbl    09-Sep-99):
> 1.10         (timbl    12-Jan-02): <body bgcolor="#ddffdd" 
> text="#000000" lang="en">
> 1.1          (timbl    09-Sep-99): <address>
> 1.1          (timbl    09-Sep-99):   Tim Berners-Lee <br>
> 1.10         (timbl    12-Jan-02):   Date: 1998, last change: $Date: 
> 2001/01/08 19:23:50 $ <br>
> 1.10         (timbl    12-Jan-02):   Status: personal view only. 
> Editing status: first draft.
> 1.1          (timbl    09-Sep-99): </address>
> 1.1          (timbl    09-Sep-99):
> 1.1          (timbl    09-Sep-99): <p><a href="./">Up to Design 
> Issues</a></p>
> 1.1          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p></p>
> 1.2          (timbl    09-Sep-99): <hr>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <h1>Principles of Design</h1>
> 1.2          (timbl    09-Sep-99):
> 1.8          (timbl    09-Sep-99): <p>Again and again we fall back on 
> the folklore of the principles of good
> 1.2          (timbl    09-Sep-99): design. Sometimes I need a URI for 
> them so this is started as collection of
> 1.8          (timbl    09-Sep-99): them. I have written about some in 
> many places.  Principles such as
> 1.10         (timbl    12-Jan-02): <b>simplicity</b> and 
> <b>modularity</b> are the stuff of software
> 1.10         (timbl    12-Jan-02): engineering; <b>decentralization</
> b> and <b>tolerance</b> are the life and
> 1.10         (timbl    12-Jan-02): breath of Internet.  Brian 
> Carpenter has enumerated some principles of design
> 1.10         (timbl    12-Jan-02): of the Net [<a 
> href="Architecture.html#carpenter">carpenter</a>]. The third
> 1.10         (timbl    12-Jan-02): pair of ideas I have found 
> commonly useful for the Web. I mentioned them in a
> 1.10         (timbl    12-Jan-02): keynote at WWW7 and the note on <a 
> href="Evolution.html">Evolvability</a>.</p>
> 1.5          (timbl    09-Sep-99):
> 1.10         (timbl    12-Jan-02): <p>This is largely "motherhood and 
> apple pie" but it still needs a home.</p>
> 1.2          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <h2><a name="KISS">Simplicity</a></
> h2>
> 1.2          (timbl    09-Sep-99):
> 1.7          (timbl    09-Sep-99): <blockquote>
> 1.7          (timbl    09-Sep-99):   <p>"Keep it simple, stupid!"</p>
> 1.7          (timbl    09-Sep-99): </blockquote>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p>Simplicity is easily to quote 
> but often ignored in strange ways. Perhaps
> 1.2          (timbl    09-Sep-99): this is because it is the eye of 
> the beholder.</p>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p>A language which uses fewer 
> basic elements  to achieve the same power is
> 1.2          (timbl    09-Sep-99): simpler.</p>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p>Sometimes simplicity is 
> confused with 'easy to understand". For example, a
> 1.2          (timbl    09-Sep-99): two-line solution which uses 
> recursion is a pretty simple, even though some
> 1.2          (timbl    09-Sep-99): people might find it easier to 
> work though a 10-line solution which avoids
> 1.2          (timbl    09-Sep-99): recursion.</p>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p>In XML, "Processing 
> Instructions", those things which start with "&lt;?"
> 1.2          (timbl    09-Sep-99): are <strong>not</strong> simple.  
> They look simple, just an extra sort of
> 1.2          (timbl    09-Sep-99): thing in the language, but the 
> complicate what was a very clean design of
> 1.2          (timbl    09-Sep-99): elements and attributes, and a 
> complication in the underlying syntax is has
> 1.2          (timbl    09-Sep-99): great effect. All specifications 
> which refer to XML processing will have to
> 1.2          (timbl    09-Sep-99): figure out what to do about 
> processing instructions as well as elements.</p>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <h2><a name="Modular">Modular 
> Design</a></h2>
> 1.2          (timbl    09-Sep-99):
> 1.10         (timbl    12-Jan-02): <p>When you design a system, or a 
> language, then if the features can be
> 1.10         (timbl    12-Jan-02): broken into relatively loosely 
> bound groups of relatively closely bound
> 1.10         (timbl    12-Jan-02): features, then that division is a 
> good thing to be made a part of the design.
> 1.10         (timbl    12-Jan-02): This is just good engineering.  It 
> means that when you want to change the
> 1.10         (timbl    12-Jan-02): system, you can with luck in the 
> future change only one part, which will only
> 1.10         (timbl    12-Jan-02): require you to understand (and 
> test) that part. This will allow other people
> 1.10         (timbl    12-Jan-02): to independently change other 
> parts at the same time. This is just classic
> 1.10         (timbl    12-Jan-02): good software design and books 
> have been written about it.  The corollary,
> 1.10         (timbl    12-Jan-02): the TOII is less frequently met.</p>
> 1.3          (timbl    09-Sep-99):
> 1.3          (timbl    09-Sep-99): <p>Modular design hinges on the 
> simplicity and abstract nature of the
> 1.3          (timbl    09-Sep-99): interface definition between the 
> modules. A design in which the insides of
> 1.3          (timbl    09-Sep-99): each module need to know all about 
> each other is not a modular design but an
> 1.3          (timbl    09-Sep-99): arbitrary partitioning of the 
> bits.</p>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <h2 id="Tolerance">Tolerance</h2>
> 1.2          (timbl    09-Sep-99):
> 1.7          (timbl    09-Sep-99): <blockquote>
> 1.7          (timbl    09-Sep-99):   <p>"Be liberal in what you 
> require but conservative in what you do"</p>
> 1.7          (timbl    09-Sep-99): </blockquote>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p>This is the expression of a 
> principle which applies pretty well in life,
> 1.2          (timbl    09-Sep-99): (it is a typical UU tenet), and is 
> commonly employed in design across the
> 1.2          (timbl    09-Sep-99): Internet.</p>
> 1.2          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <p>Write HTML 4.0-strict.  Accept 
> HTML-4.0-Transitional (a superset of
> 1.4          (timbl    09-Sep-99): strict).</p>
> 1.3          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <p>This principle can be 
> contentious.  When browsers are lax about what they
> 1.4          (timbl    09-Sep-99): expect, the system works better 
> but also it encourages laxness on the part of
> 1.4          (timbl    09-Sep-99): web page writers.  The principle 
> of tolerance does not blunt the need for a
> 1.4          (timbl    09-Sep-99): perfectly clear protocol 
> specification which draws a precise distinction
> 1.4          (timbl    09-Sep-99): between a conformance and non-
> conformance. The principle of tolerance is no
> 1.5          (timbl    09-Sep-99): excuse for a product which 
> contravenes a standard.</p>
> 1.4          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <p></p>
> 1.2          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <h2 
> id="Decentrali">Decentralization</h2>
> 1.2          (timbl    09-Sep-99):
> 1.3          (timbl    09-Sep-99): <p>This is a principle of the 
> design of distributed systems, including
> 1.10         (timbl    12-Jan-02): societies. It points out that any 
> single common point which is involved in
> 1.10         (timbl    12-Jan-02): any operation trends to limit the 
> way the system scales, and produce a single
> 1.3          (timbl    09-Sep-99): point of complete failure.</p>
> 1.3          (timbl    09-Sep-99):
> 1.3          (timbl    09-Sep-99): <p>Centralization in social 
> systems can apply to concepts, too. For example,
> 1.3          (timbl    09-Sep-99): if we make a knowledge 
> representation system which requires anyone who uses
> 1.5          (timbl    09-Sep-99): the concept of "automobile" to use 
> the term
> 1.3          (timbl    09-Sep-99): "http://www.kr.org/stds/industry/
> automobile" then we restrict the set of uses
> 1.3          (timbl    09-Sep-99): of the system to those for whom 
> this particular formulation of what an
> 1.3          (timbl    09-Sep-99): automobile is works.  The Semantic 
> Web must avoid such conceptual bottlenecks
> 1.10         (timbl    12-Jan-02): just as the Internet avoids such 
> network bottlenecks.</p>
> 1.2          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <h2><a name="TOII">Test of 
> Independent Invention</a></h2>
> 1.8          (timbl    09-Sep-99):
> 1.8          (timbl    09-Sep-99): <blockquote>
> 1.8          (timbl    09-Sep-99):   <p>If someone else had already 
> invented your system, would theirs work with
> 1.8          (timbl    09-Sep-99):   yours?</p>
> 1.8          (timbl    09-Sep-99): </blockquote>
> 1.3          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <p>Does this system have to be the 
> only one of its kind?  This simple thought
> 1.4          (timbl    09-Sep-99): test is described in more detail 
> in "<a
> 1.4          (timbl    09-Sep-99): 
> href="Evolution.html#TOII">Evolution</a>" in these Design Issues.  It is
> 1.4          (timbl    09-Sep-99): modularity inside-out: designing a 
> system not to be modular in itself, but to
> 1.4          (timbl    09-Sep-99): be a part of an as-yet unspecified 
> larger system. A critical property here is
> 1.10         (timbl    12-Jan-02): that the system tries to do one 
> thing well, and leaves other things to other
> 1.4          (timbl    09-Sep-99): modules. It also has to avoid 
> conceptual or other centralization, as no two
> 1.5          (timbl    09-Sep-99): modules can claim the need to be 
> the unique center of a larger system.</p>
> 1.4          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <h2><a name="PLP">Principle of  
> Least Power</a></h2>
> 1.4          (timbl    09-Sep-99):
> 1.10         (timbl    12-Jan-02): <p>In choosing computer languages, 
> there are classes of program which range
> 1.10         (timbl    12-Jan-02): from the plainly descriptive (such 
> as Dublin Core metadata, or the content of
> 1.4          (timbl    09-Sep-99): most databases, or HTML) though 
> logical languages of limited power (such as
> 1.10         (timbl    12-Jan-02): access control lists, or 
> <em>conneg</em> content negotiation) which include
> 1.10         (timbl    12-Jan-02): limited propositional logic, 
> though declarative languages which verge on the
> 1.10         (timbl    12-Jan-02): Turing Complete (PDF) through 
> those which are in fact Turing Complete though
> 1.10         (timbl    12-Jan-02): one is led not to use them that 
> way (XSLT, SQL) to those which are
> 1.10         (timbl    12-Jan-02): unashamedly procedural (Java, C).</p>
> 1.10         (timbl    12-Jan-02):
> 1.10         (timbl    12-Jan-02): <p>The choice of language is a 
> common design choice.  The low power end of
> 1.10         (timbl    12-Jan-02): the scale is typically simpler to 
> design, implement and use, but the high
> 1.10         (timbl    12-Jan-02): power end of the scale has all the 
> attraction of being an open-ended hook
> 1.10         (timbl    12-Jan-02): into which anything can be placed: 
> a door to uses bounded only by the
> 1.10         (timbl    12-Jan-02): imagination of the programmer.</p>
> 1.10         (timbl    12-Jan-02):
> 1.10         (timbl    12-Jan-02): <p>Computer Science in the 1960s 
> to 80s spent a lot of effort making
> 1.10         (timbl    12-Jan-02): languages which were as powerful 
> as possible. Nowadays we have to appreciate
> 1.10         (timbl    12-Jan-02): the reasons for picking not the 
> most powerful solution but the least
> 1.10         (timbl    12-Jan-02): powerful.  The reason for this is 
> that the less powerful the language, the
> 1.10         (timbl    12-Jan-02): more you can do with the data 
> stored in that language. If you write it in a
> 1.10         (timbl    12-Jan-02): simple declarative from, anyone 
> can write a program to analyze it in many
> 1.10         (timbl    12-Jan-02): ways. The Semantic Web is an 
> attempt, largely, to map large quantities of
> 1.10         (timbl    12-Jan-02): existing data onto a common 
> language so that the data can be analyzed in ways
> 1.10         (timbl    12-Jan-02): never dreamed of by its creators. 
> If, for example, a web page with weather
> 1.10         (timbl    12-Jan-02): data has RDF describing that data, 
> a user can retrieve it as a table, perhaps
> 1.10         (timbl    12-Jan-02): average it, plot it, deduce things 
> from it in combination with other
> 1.10         (timbl    12-Jan-02): information.  At the other end of 
> the scale is the weather information
> 1.10         (timbl    12-Jan-02): portrayed by the cunning Java 
> applet. While this might allow a very cool user
> 1.10         (timbl    12-Jan-02): interface, it cannot be analyzed 
> at all. The  search engine finding the page
> 1.10         (timbl    12-Jan-02): will have no idea of what the data 
> is or what it is about. This the only way
> 1.10         (timbl    12-Jan-02): to find out what a Java applet 
> means is to set it running in front of a
> 1.10         (timbl    12-Jan-02): person.</p>
> 1.4          (timbl    09-Sep-99):
> 1.4          (timbl    09-Sep-99): <p>I hope that is a good enough 
> explanation of this principle.  There are
> 1.4          (timbl    09-Sep-99): millions of examples of the 
> choice.  I chose HTML not to be a programming
> 1.4          (timbl    09-Sep-99): language because I wanted 
> different programs to do different things with it:
> 1.4          (timbl    09-Sep-99): present it differently, extract 
> tables of contents, index it, and so on.</p>
> 1.1          (timbl    09-Sep-99):
> 1.1          (timbl    09-Sep-99): <p></p>
> 1.1          (timbl    09-Sep-99):
> 1.5          (timbl    09-Sep-99): <p></p>
> 1.5          (timbl    09-Sep-99): <hr>
> 1.5          (timbl    09-Sep-99):
> 1.5          (timbl    09-Sep-99): <h2><a 
> name="References">References</a></h2>
> 1.5          (timbl    09-Sep-99):
> 1.5          (timbl    09-Sep-99): <p><a href="ftp://ftp.isi.edu/in-
> notes/rfc1958.txt" name="carpenter">B.
> 1.5          (timbl    09-Sep-99): Carpenter, Editor: "Architectural 
> Principles of the Internet"</a> Internet
> 1.5          (timbl    09-Sep-99): Architecture Board, June 1996, 
> RFC1958</p>
> 1.5          (timbl    09-Sep-99):
> 1.5          (timbl    09-Sep-99): <p></p>
> 1.1          (timbl    09-Sep-99):
> 1.2          (timbl    09-Sep-99): <p></p>
> 1.1          (timbl    09-Sep-99):
> 1.1          (timbl    09-Sep-99): <p></p>
> 1.1          (timbl    09-Sep-99): <hr>
> 1.1          (timbl    09-Sep-99):
> 1.1          (timbl    09-Sep-99): <p><a href="Overview.html">Up to 
> Design Issues</a></p>
> 1.1          (timbl    09-Sep-99):
> 1.1          (timbl    09-Sep-99): <p><a href="../People/Berners-
> Lee">Tim BL</a></p>
> 1.1          (timbl    09-Sep-99): </body>
> 1.1          (timbl    09-Sep-99): </html>
>
Received on Tuesday, 20 December 2005 21:15:46 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Thursday, 26 April 2012 12:47:37 GMT