A programming language that can only create algorithms with polynomial runtime? Has someone constructed a programming language that can construct all the algorithms in P, and no others?
I'm interested in this restriction coming from the syntax naturally, as opposed to just being a normal Turing machine with a step-timer attached.
 A: If I understand the paper's abstract, Yes.
A: Perhaps the most natural examples come from various extensions to SQL (of course, if query languages count). For example Datalog on ordered relations equals P. Generally, such languages are somewhere around P, but for most of them it is really hard to give exact characterisations.
A: Yes, there is a whole research area devoted to this problem -- it's called "implicit complexity theory". The general idea is to use a lambda calculus based on linear logic. The linearity constraint on lambda-terms lets you control the complexity of cut-elimination (and hence of evaluation), giving natural programming languages that are complete for various complexity classes (such as PTIME, PSPACE, or LOGSPACE). 
A: Yet another perspective (and IMHO a more natural one) is descriptive complexity theory (check also this Wikipedia article). 
They study the question from a perspective different from the one mentioned by Neel. There are various languages that capture exactly the polynomial time computable functions. One of the most famous ones is FO+LFP.
