What is Expressiveness in a Computer Language

[Xah Lee]

in March, i posted a essay “What is Expressiveness in a Computer
Language�, archived at:
http://xahlee.org/perl-python/what_i...esiveness.html

I was informed then that there is a academic paper written on this
subject.

On the Expressive Power of Programming Languages, by Matthias
Felleisen, 1990.
http://www.ccs.neu.edu/home/cobbe/pl...ive-slides.pdf

Has anyone read this paper? And, would anyone be interested in giving a
summary?

thanks.

Xah
xa*@xahlee.org
∑ http://xahlee.org/

[Rob Thorpe]

Torben Ægidius Mogensen wrote:

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. From the point of view purely of expressiveness I'd say it's rather

different.

If a language can express constraints of one kind that is an increase
in expressiveness.
If a language requires constraint to be in one particular way thats a
decrease in expressiveness.

So I would say languages that can be statically typed and can be
dynamically typed are the most expressive. Languages that require
static typing or are dynamic but cannot express static typing are less
expressive.

This meets my experience of what useful in practice too, static typing
for everything is painful for writing simple code. Pure dynamic typing
is painful when writing complex code because it makes impossible a
layer of error checking that could otherwise be useful.

[Joachim Durchholz]

Torben Ægidius Mogensen schrieb:

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.

Also past peer review and/or debugging runs. And, most importantly, past
your own mental review processes.

Regards,
Jo

[Joachim Durchholz]

Raffael Cavallaro schrieb:

On 2006-06-14 09:42:25 -0400, to*****@app-1.diku.dk (Torben Ægidius
Mogensen) said:

It takes longer for the average
programmer to get the program working in the dynamically typed
language.
Though I agree with much of your post I would say that many here find
the opposite to be true - it takes us longer to get a program working in
a statically typed language because we have to keep adding/changing
things to get the compiler to stop complaining and actually compile and
run

I think Torben was assuming a language with type inference. You write
only those type annotations that really carry meaning (and some people
let the compiler infer even these).
a program which would be perfectly permissible in a dynamically
typed language such as common lisp - for example - heterogeneous lists
and forward references to as yet non-existent functions.

Um... heterogenous lists are not necessarily a sign of expressiveness.
The vast majority of cases can be transformed to homogenous lists
(though these might then contain closures or OO objects).

As to references to nonexistent functions - heck, I never missed these,
not even in languages without type inference :-)

I don't hold that they are a sign of *in*expressiven ess either. They are
just typical of highly dynamic programming environments such as Lisp or
Smalltalk.

Regards,
Jo

[Joachim Durchholz]

Rob Thorpe schrieb:

If a language can express constraints of one kind that is an increase
in expressiveness.
Agreed.
If a language requires constraint to be in one particular way thats a
decrease in expressiveness.
Unless alternatives would be redundant.
Having redundant ways to express the same thing doesn't make a language
more or less expressive (but programs written in it become more
difficult to maintain).
So I would say languages that can be statically typed and can be
dynamically typed are the most expressive. Languages that require
static typing or are dynamic but cannot express static typing are less
expressive.

Note that this is a different definition of expressiveness.
(The term is very diffuse...)

I think Felleisen's paper defines something that should be termed
"concisenes s".
Whether there's a way to express constraints or other static properties
of the software is something different. I don't have a good word for it,
but "expressiveness " covers too much for my taste to really fit.

Regards,
Jo

[Pascal Costanza]

Torben Ægidius Mogensen wrote:

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.
It's important to get the levels right here: A programming language with
a rich static type system is more expressive at the type level, but less
expressive at the base level (for some useful notion of expressiveness ;).
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.

This doesn't seem to capture what I hear from Haskell programmers who
say that it typically takes quite a while to convince the Haskell
compiler to accept their programs. (They perceive this to be worthwhile
because of some benefits wrt correctness they claim to get in return.)
Pascal

--
3rd European Lisp Workshop
July 3 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/

[Pascal Bourguignon]

Joachim Durchholz <jo@durchholz.o rg> writes:

Raffael Cavallaro schrieb:

a program which would be perfectly permissible in a dynamically
typed language such as common lisp - for example - heterogeneous
lists and forward references to as yet non-existent functions.

Um... heterogenous lists are not necessarily a sign of
expressiveness. The vast majority of cases can be transformed to
homogenous lists (though these might then contain closures or OO
objects).

In lisp, all lists are homogenous: lists of T.
--
__Pascal Bourguignon__ http://www.informatimago.com/

ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling, " this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.

[Neelakantan Krishnaswami]

In article <4f************ *@individual.ne t>, Pascal Costanza wrote:

Torben Ægidius Mogensen wrote:

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.
It's important to get the levels right here: A programming language
with a rich static type system is more expressive at the type level,
but less expressive at the base level (for some useful notion of
expressiveness ;).

This doesn't seem obviously the case to me. If you have static
information about your program, the compiler can use this information
to automate a lot of grunt work away.

Haskell's system of typeclasses work this way. If you tell the
compiler how to print integers, and how to print lists, then when you
call a print function on a list of list of integers, then the compiler
will automatically figure out the right print function using your base
definitions. This yields an increase in Felleisen-expressiveness over
a dynamically typed language, because you would need to globally
restructure your program to achieve a similar effect.

More dramatic are the "polytypic" programming languages, which let you
automate even more by letting you write generic map, fold, and print
functions which work at every type.
This doesn't seem to capture what I hear from Haskell programmers
who say that it typically takes quite a while to convince the
Haskell compiler to accept their programs. (They perceive this to be
worthwhile because of some benefits wrt correctness they claim to
get in return.)

This is true, if you are a novice learning the language, or if you are
an expert programming with good style.

If you encode your invariants in the types, then type errors will
signal broken invariants. But: learning how to use the type system to
encode significantly complex invariants (eg, that an abstract syntax
tree representing an HTML document actually satisfies all of the
constraints on valid HTML) takes experience to do well.

--
Neel Krishnaswami
ne***@cs.cmu.ed u

[Raffael Cavallaro]

On 2006-06-14 15:04:34 -0400, Joachim Durchholz <jo@durchholz.o rg> said:

Um... heterogenous lists are not necessarily a sign of expressiveness.
The vast majority of cases can be transformed to homogenous lists
(though these might then contain closures or OO objects).

As to references to nonexistent functions - heck, I never missed these,
not even in languages without type inference :-)

I don't hold that they are a sign of *in*expressiven ess either. They
are just typical of highly dynamic programming environments such as
Lisp or Smalltalk.

This is a typical static type advocate's response when told that users
of dynamically typed languages don't want their hands tied by a type
checking compiler:

"*I* don't find those features expressive so *you* shouldn't want them."

You'll have to excuse us poor dynamically typed language rubes - we
find these features expressive and we don't want to give them up just
to silence a compiler whose static type checks are of dubious value in
a world where user inputs of an often unpredictable nature can come at
a program from across a potentially malicious internet making run-time
checks a practical necessity.

[Raffael Cavallaro]

On 2006-06-14 16:36:52 -0400, Pascal Bourguignon <pj*@informatim ago.com> said:

In lisp, all lists are homogenous: lists of T.

CL-USER 123 > (loop for elt in (list #\c 1 2.0d0 (/ 2 3)) collect
(type-of elt))
(CHARACTER FIXNUM DOUBLE-FLOAT RATIO)

i.e., "heterogeno us" in the common lisp sense: having different dynamic
types, not in the H-M sense in which all lisp values are of the single
union type T.

[Pascal Costanza]

Neelakantan Krishnaswami wrote:

In article <4f************ *@individual.ne t>, Pascal Costanza wrote:

Torben Ægidius Mogensen wrote:

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.

It's important to get the levels right here: A programming language
with a rich static type system is more expressive at the type level,
but less expressive at the base level (for some useful notion of
expressiveness ;).

This doesn't seem obviously the case to me. If you have static
information about your program, the compiler can use this information
to automate a lot of grunt work away.

Haskell's system of typeclasses work this way. If you tell the
compiler how to print integers, and how to print lists, then when you
call a print function on a list of list of integers, then the compiler
will automatically figure out the right print function using your base
definitions. This yields an increase in Felleisen-expressiveness over
a dynamically typed language, because you would need to globally
restructure your program to achieve a similar effect.

More dramatic are the "polytypic" programming languages, which let you
automate even more by letting you write generic map, fold, and print
functions which work at every type.

Yes, but these decisions are taken at compile time, without running the
program.
Pascal

--
3rd European Lisp Workshop
July 3 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/