ted@computing-maths.cardiff.ac.uk (Ted Lawson) (05/28/89)
Can anyone provide or (preferably) point-to a definition of, or discussion about, the oft-heard term "Expressive Power" ? All I can find is John Backus's '77 Turing Award Lecture where he says: "...language A would be more expressive than language B under the following roughly stated conditions. First, form all possible functions of all types in A by applying all existing functions to objects and to each other in all possible ways until no new function of any type can be formed. ... Do the same for language B. Next, compare each type in A to the corresponding type in B. If, for every type, A's type includes B's corresponding type, then A is more expressive than B (or equally expressive)." [Comm. ACM 21(8) 623-624, 1978]. Is this the last word ? Ted Lawson
ken@aiai.ed.ac.uk (Ken Johnson) (05/30/89)
In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes: > > Can anyone provide or (preferably) point-to a definition of, > or discussion about, the oft-heard term "Expressive Power" ? > ... If, for every > type, A's type includes B's corresponding type, then A > is more expressive than B (or equally expressive)." No, this doesn't seem to hold water as a complete definition. Suppose that in language A I can form statements of the type S1, S2 and S3. In language B I can form statements of the type S2, S3, S4,S5, ... S100000. Then language B can be said to be more expressive than language A, but language A is handy if I want to execute statements of the form S1. The definition you suggest does not allow for this sort of case. -- Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212 `I have read your article, Mr. Johnson, and I am no wiser than when I started.' -- `Possibly not, sir, but far better informed.'
chrisp@regenmeister.uucp (Chris Prael) (06/01/89)
From article <494@skye.ed.ac.uk>, by ken@aiai.ed.ac.uk (Ken Johnson): > In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes: >> ... If, for every >> type, A's type includes B's corresponding type, then A >> is more expressive than B (or equally expressive)." > > No, this doesn't seem to hold water as a complete definition. Suppose > that in language A I can form statements of the type S1, S2 and S3. In You might want to reread the statement. Your example falls outside Backus's statement. A simplified restatement would be: If the set of all possible functions written in the language B is a subset of the set of all possible functions written in language A, then language A is more expressive than B. Unfortunately, it is not a practically useful definition. Chris Prael
pjs269@tijc02.UUCP (Paul Schmidt ) (06/01/89)
> In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes: > > > > Can anyone provide or (preferably) point-to a definition of, > > or discussion about, the oft-heard term "Expressive Power" ? > > No, this doesn't seem to hold water as a complete definition. Suppose > that in language A I can form statements of the type S1, S2 and S3. In > language B I can form statements of the type S2, S3, S4,S5, ... > S100000. > > Then language B can be said to be more expressive than language A, > but language A is handy if I want to execute statements of the > form S1. > > The definition you suggest does not allow for this sort of case. > -- > Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN There have been NO languages such as A and B that have ever been discovered. If I remember correctly there are only three or four classes of expressive power that have been discovered. None of these classes intersect, they either contain a class or are contained in another task. A digram of this as best as I can remember is: +-------------------------+ | Recursive | | +---------------------+ | | | Partially Recursive | | | | +-----------------+ | | | | | ??? | | | | | | +-------------+ | | | | | | | ??? | | | | | | | +-------------| | | | | | +-----------------+ | | | +---------------------+ | +-------------------------+ If you know of any languages such as A and B, please post. ---------------------------------------------------------------------- Paul Schmidt USENET: rti!tijc02!pjs269 Texas Instruments PHONE: (615) 461-2461 PO Drawer 1255 M/S 3517 Johnson City, TN 37605-1255
gudeman@arizona.edu (David Gudeman) (06/03/89)
In article <483@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt ) writes: ]> In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes: ]> > ]> > Can anyone provide or (preferably) point-to a definition of, ]> > or discussion about, the oft-heard term "Expressive Power" ? ]> ]> No, this doesn't seem to hold water as a complete definition. Suppose ]> that in language A I can form statements of the type S1, S2 and S3. In ]> language B I can form statements of the type S2, S3, S4,S5, ... ]> S100000. ] ]There have been NO languages such as A and B that have ever been discovered. ]If I remember correctly there are only three or four classes of expressive power ]that have been discovered. None of these classes intersect, they either contain ]a class or are contained in another task. Actually, there is an unbounded number of classes of languages with different expressive powers, some of which intersect with each other with neither including the other. As an example, let X be the subset of regular expressions without closure, and let Y be the subset of regular expressions without alternation. Let A be the class of languages that can be described with X and let B be the class of languages that can be described with Y. I claim that the language classes A and B intersect, but that neither contains the other. -- David Gudeman Department of Computer Science The University of Arizona gudeman@arizona.edu Tucson, AZ 85721 {allegra,cmcl2,ihnp4,noao}!arizona!gudeman
gudeman@arizona.edu (David Gudeman) (06/03/89)
In article <769@cf-cm.UUCP> ted@computing-maths.cardiff.ac.uk (Ted Lawson) writes: > > Can anyone provide or (preferably) point-to a definition of, > or discussion about, the oft-heard term "Expressive Power" ? Funny you should ask, since the is one of the main topics of my dissertation.... First, it looks to me like Backus is really defining "complexity" in the segment you quoted (I'm not really sure though, since the quote didn't contain his definition of "type"). Complexity is usually not interesting to programming language designers since virtually all programming languages have the same complexity. My definition of expressiveness goes something like this: Given two languages A and B, A [= B (read B is at least as expressive as A) iff (1) the syntax of A is a subset of the syntax of B. (2) for all programs P in A, the denotation of P under the semantics of B subsumes the denotation of P under the semantics of A. The definition of "subsumes" is rather complicated, and really needs the motivation of the rest of the dissertation, so I won't include it here. Under this definition, there are very few (if any) real programming languages that are comparable under the expressiveness relation (it's a partial order). I'm trying to come up with a definition that isn't so dependent on syntax, but this is difficult since the syntax of a language effects the expressiveness so much. For example, I claim that there is no difference in the expressiveness of Lisp and C in the following expressions: Lisp: (setq a (+ 1 a)) C: a = 1 + a; the syntax is different, but both expressions say the same thing in pretty much the same way. However these next two show an expressiveness advantage in C: Lisp: (setq a (1+ a)) C: a += 1; C: ++a; In both languages you can express the concept of "add 1" as a seperate idea from "add two numbers". But in C, you can also express the notion of "increment location by one" as an atomic notion itself. However, you can _define_ an "increment location" macro in Lisp. On the other hand Lisp is more expressive than C in areas such as defining functions at run time. There is no way to simulate this in C. Well you _can_ simulate it in C by writting a Lisp interpreter in C... It all gets very confusing. It's much easier to just require that one language have a syntax that is a subset of the other. -- David Gudeman Department of Computer Science The University of Arizona gudeman@arizona.edu Tucson, AZ 85721 {allegra,cmcl2,ihnp4,noao}!arizona!gudeman
will@uoregon.uoregon.edu (William Clinger) (06/03/89)
In article <483@tijc02.UUCP> pjs269@tijc02.UUCP (Paul Schmidt ) writes: >If I remember correctly there are only three or four classes of expressive >power that have been discovered.... and cites the fact that partial recursion (i.e. bounded iteration) is strictly less powerful than recursion. A less familiar example is that flowchart schemes (i.e. unbounded iteration) are strictly less powerful than recursive schemes. Another example is that deterministic program schemes are strictly less powerful than certain classes of nondeterministic program schemes. The problem with discussing expressive power is that powerful data structures (e.g. integers of unbounded size) can in theory simulate powerful control structures, and vice versa, but this theoretical result is of no practical importance since nobody in their right mind is going to simulate (e.g.) recursion by encoding the program state as an (e.g.) integer. By abstracting away from the data types using schemes, you can make finer distinctions that have more to do with the expressive power of languages in practice. Would you believe that Fortran IV (assuming integers of bounded size, and a finite set of representable reals) would not have been Turing equivalent without the REWIND statement? Peace, William Clinger
will@uoregon.uoregon.edu (William Clinger) (06/03/89)
Excuse me. As I was walking home after posting a message to this newsgroup, I realized that I had said "partial recursive" when I meant "primitive recursive". My mind was, as they say, elsewhere. Here is a less incorrect version of the paragraph: ...and cites the fact that primitive recursion (without the minimization operator) is strictly less powerful than general recursion. A less familiar example is that flowchart schemes (i.e. unbounded iteration) are strictly less powerful than recursive schemes. Another example is that deterministic program schemes are strictly less powerful than certain classes of nondeterministic program schemes. I apologize for the confusion this must have caused. William Clinger
jwb@LINDENTHAL.CAE.RI.CMU.EDU (John Baugh) (06/04/89)
In article <11318@megaron.arizona.edu> gudeman@arizona.edu (David Gudeman) writes: > [stuff deleted] >pretty much the same way. However these next two show an >expressiveness advantage in C: > >Lisp: (setq a (1+ a)) >C: a += 1; >C: ++a; > >In both languages you can express the concept of "add 1" as a seperate >idea from "add two numbers". But in C, you can also express the >notion of "increment location by one" as an atomic notion itself. >However, you can _define_ an "increment location" macro in Lisp. On No. It's already there, at least in Common Lisp. The macro "incf" takes an optional argument "delta", which defaults to 1. So (from CLtL): (setq n 0) => 0 and now n => 0 (incf n) => 1 and now n => 1 (incf n 3) => 4 and now n => 4 The same macro can be used to destuctively increment a "place", e.g., (setq l '(1 2 3)) => (1 2 3) and now l => (1 2 3) (incf (cadr l) 3) => (1 5 3) and now l => (1 5 3) The decrement macro "decf" is also provided. >the other hand Lisp is more expressive than C in areas such as >defining functions at run time. There is no way to simulate this in What about treating functions as values? Doesn't this add to the expressive power of a language? Modern functional languages provide this plus many other "expressive" features: currying, so that the application of "add" to 1 returns a unary function that adds 1 to its argument, (e.g., add1 = add 1); pattern matching; defining types via recursion equations, ... If having an increment function makes a language more expressive, doesn't the above have to fit in somewhere? > [stuff deleted] > David Gudeman >Department of Computer Science >The University of Arizona gudeman@arizona.edu >Tucson, AZ 85721 {allegra,cmcl2,ihnp4,noao}!arizona!gudeman John Baugh --