RE: Principle of Least Power (was Re: Agenda of 7 February 2006 T AG teleconference)

On Tue, 2006-02-07 at 16:25 -0600, Bullard, Claude L (Len) wrote:
> Thanks Dan.  Certainly there are some examples as you point out.
> I cut the cc list in deference to those who don't want to 
> read your tutoring of my lack of understanding this.
> 
> So the range is from simple declaration to Turing complete. Is 
> that the only razor?

The razors that we learn in school and that show up
in programming libraries are between:

 -- regular expressions
 -- context-free grammars, a class with a number of
      shades that tend to matter in practice:

   -- LL(1) grammars, which can be handled by recursive-descent parsing
   -- LALR(1) grammars, which can be handled by yacc
 -- turing machines, i.e. programming languages

A wikipdeia article on formal languages
http://en.wikipedia.org/wiki/Formal_language
shows that I forgot to distinguish recursive from recursively enumerable
languages and between context-sensitive and turing-complete. Those
distinctions don't show up in practical programming as much,
in my experience. I've used attribute grammars a few times in practice;
I'm not sure where they fit just now.

There's also algorithm complexity: O(1) vs O(N) vs polynomial etc.
  http://en.wikipedia.org/wiki/Complexity_class
  http://en.wikipedia.org/wiki/Computational_complexity_theory

And decideable logics (of various sorts) vs undecideable
 http://en.wikipedia.org/wiki/Decision_problem
and 1st order vs higher order.
  http://en.wikipedia.org/wiki/Second-order_logic


I'm not sure if any of this is worth adding to the finding.
The finding already makes the most important distinctions
that have occurred in Web technologies to date, I think.



> "you typically cannot determine what a program in a Turing-complete 
> language will do without actually running it."  
> 
> That is pretty good but you can't determine what you can't determine
> without 
> running it either.

Sure you can. If the spec says the language is regular, you
don't have to evaluate an expression to know that it
can't distinguish balanced ()s from unbalanced ()s.


>   As you point out, in the simple cases you know but 
> there is no demarcation that says 'beyond this thar be monsters'.
> 
> Given the broad range, it might be useful to have a list of features 
> of not-quite Turing complete languages beyond regexps.  Is that what 
> Henry is asking for? 
> 
> Wouldn't it be just as useful to isolate out the declarative features?  
> For example, the oft quoted comparison of C structs with XML element
> declarations 
> vs declaring a C++ object.  IOW, separation of powers is useful 
> in meeting this goal as in the RDF vs Java applet example for 
> weather (presentation vs calculation vs getData).
> 
> I dunno.  I am a little suspicious of the application of the principle 
> even if it appears reasonable on the surface because it's equivalent
> with 
> 'do the simplest thing that can possibly work' and 'separate
> presentation 
> from formatting" which leads to 'keep the business objects out of the 
> client' which leads to 'loose coupling' and the 'don't pass a type 
> if you can pass a string' idea which some think a step too far.

Yes, in a sense, this is all motherhood and apple pie. That's
a big part of the TAG's job, though, right?

> How does one know when to step up to more power?  When it isn't 
> the simplest thing that could possibly work?  If you can't know 
> without running it, the principle is equivalent to 'start simple 
> and run it until it quits working' but that isn't the same as 
> 'stay simple so others can use it in ways you don't know about 
> because they haven't run it yet'.  Feels weird.
> 
> I suppose that it being a 'best practice principle' it can be 
> mushy at the edges.

Principles are mushy by nature. "Keep it simple" is hardly
testable.


> If you had to write RDF for the languages that start from 
> declarative to Turing complete, could that be more than 
> "is one, isn't one"?  In other words, if a machine had 
> to apply the principle, could it?

No. See http://en.wikipedia.org/wiki/Halting_problem


-- 
Dan Connolly, W3C http://www.w3.org/People/Connolly/
D3C2 887B 0F92 6005 C541  0875 0F91 96DE 6E52 C29E

Received on Wednesday, 8 February 2006 14:56:08 UTC