"Joe Marshall" <[EMAIL PROTECTED]> writes:
> > On the Expressive Power of Programming Languages, by Matthias > > Felleisen, 1990. > > http://www.ccs.neu.edu/home/cobbe/pl-seminar-jr/notes/2003-sep-26/expressive-slides.pdf > > The gist of the paper is this: Some computer languages seem to be > `more expressive' than others. But anything that can be computed in > one Turing complete language can be computed in any other Turing > complete language. Clearly the notion of expressiveness isn't > concerned with ultimately computing the answer. > > Felleisen's paper puts forth a formal definition of expressiveness > in terms of semantic equivilances of small, local constructs. In > his definition, wholescale program transformation is disallowed so > you cannot appeal to Turing completeness to claim program > equivalence. I think expressiveness is more subtle than this. Basically, it boils down to: "How quickly can I write a program to solve my problem?". There are several aspects relevant to this issue, some of which are: - Compactness: How much do I have to type to do what I want? - Naturality: How much effort does it take to convert the concepts of my problem into the concepts of the language? - Feedback: Will the language provide sensible feedback when I write nonsensical things? - Reuse: How much effort does it take to reuse/change code to solve a similar problem? Compactness is hard to measure. It isn't really about the number of characters needed in a program, as I don't think one-character symbols instead of longer keywords make a language more expressive. It is better to count lexical units, but if there are too many different predefined keywords and operators, this isn't reasonable either. Also, the presence of opaque one-liners doesn't make a language expressible. Additionally, as mentioned above, Turing-completeness (TC) allows you to implement any TC language in any other, so above a certain size, the choice of language doesn't affect size. But something like (number of symbols in program)/log(number of different symbols) is not too bad. If programs are allowed to use standard libraries, the identifiers in the libraries should be counted in the number of different symbols. Naturality is very difficult to get a grip on, and it strongly depends on the type of problem you want to solve. So it only makes sense to talk about expressiveness relative to a set of problem domains. If this set is small, domain-specific languages win hands down, so if you want to compare expressiveness of general-purpose languages, you need a large set of very different problems. And even with a single problem, it is hard to get an objective measure of how difficult it is to map the problem's concepts to those of the language. But you can normally observe whether you need to overspecify the concept (i.e., you are required to make arbitrary decisions when mapping from concept to data), if the mapping is onto (i.e., can you construct data that isn't sensible in the problem domain) and how much redundancy your representation has. Feedback is a mixture of several things. Partly, it is related to naturality, as a close match between problem concepts and language concepts makes it less likely that you will express nonsense (relative to the problem domain) that makes sense in the language. For example, if you have to code everything as natural numbers, untyped pure lambda calculus or S-expressions, there is a good chance that you can get nonsense past the compiler. Additionally, it is about how difficult it is to tie an observation about a computed result to a point in the program. Measuring reuse depends partly on what is meant by problems being similar and also on whether you at the time you write the original code can predict what types of problems you might later want to solve, i.e., if you can prepare the code for reuse. Some languages provide strong mechanisms for reuse (templates, object hierarchies, etc.), but many of those require that you can predict how the code is going to be reused. So, maybe, you should measure how difficult it is to reuse a piece of code that is _not_ written with reuse in mind. This reminds me a bit of last years ICFP contest, where part of the problem was adapting to a change in specification after the code was written. > Expressiveness isn't necessarily a good thing. For instance, in C, > you can express the addresses of variables by using pointers. You > cannot express the same thing in Java, and most people consider this > to be a good idea. I think this is pretty much covered by the above points on naturality and feedback: Knowing the address of a value or object is an overspecification unless the address maps back into something in the problem domain. On a similar note, is a statically typed langauge more or less expressive than a dynamically typed language? Some would say less, as you can write programs in a dynamically typed language that you can't compile in a statically typed language (without a lot of encoding), whereas the converse isn't true. However, I think this is misleading, as it ignores the feedback issue: It takes longer for the average programmer to get the program working in the dynamically typed language. Torben -- http://mail.python.org/mailman/listinfo/python-list