Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!bloom-beacon!tut.cis.ohio-state.edu!ucbvax!agate!bionet!ig!arizona!gudeman
From: gudeman@arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: Re: Expressive Power - What is it ?
Message-ID: <11318@megaron.arizona.edu>
Date: 2 Jun 89 20:07:46 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 59

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