473,721 Members | 4,008 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

What is Expressiveness in a Computer Language

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/

Jun 9 '06 #1
669 26027

Xah Lee wrote:
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?


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.

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.

Jun 9 '06 #2
<I've removed the massive cross-posting - I wouldn't presume this message is
all that interesting to folks in those other NG's, and I'm sure they'd be
saying, "who the heck is Paul McGuire, and who gives a @#*$! what he
thinks?">

"Joe Marshall" <ev********@gma il.com> wrote in message
news:11******** *************@h 76g2000cwa.goog legroups.com...

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.


For those who remember the bad old days of COBOL, its claim to fame was that
it was more like English prose, with the intent of making a programming
language that was as readable as English, assuming that this was more
"expressive ", and not requiring as much of a mental mapping exercise for
someone trying to "read" a program. Even the language terminology itself
strived for this: statements were "sentences" ; blocks were "paragraphs ".
The sentence model may have ended up being one of COBOL's Achilles Heel's -
the placement of terminating periods for an IF THEN ELSE block was crucial
for disambiguating which ELSE went with which IF. Unfortunately, periods
are one of the least visible printed characters, and an extra or missing
period could cause hours of extra debugging.

(Of course, at the time of COBOL's inception, the only primary languages to
compare with were assembly or FORTRAN-60, so this idea wasn't totally
unfounded.)

-- Paul
Jun 9 '06 #3
Joe Marshall wrote:
Xah Lee wrote:
On the Expressive Power of Programming Languages, by Matthias
Felleisen, 1990.
http://www.ccs.neu.edu/home/cobbe/pl...ive-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 suspect that the small, local transformations versus global
transformations is also to do with the practice of not saying the same
thing twice. Everything from subroutines to LISP macros also helps
here, increasing language expressiveness.
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.


Assuming the more-expressive feature does not preclude the
less-expressive one, good/bad depends on the programmer. I know *I*
can't be trusted with pointers ;-) , but I know many programmers benefit
greatly from them. Of course, knowing that the programmer cannot do
something does help the compiler stop you shooting yourself in the foot.

--
Simon Richard Clarkstone: s.************@ durham.ac.uk/s?m?n.cl?rkst?n ?@
hotmail.com ### "I have a spelling chequer / it came with my PC /
it plainly marks for my revue / Mistake's I cannot sea" ...
by: John Brophy (at: http://www.cfwf.ca/farmj/fjjun96/)
Jun 9 '06 #4
Xah Lee wrote:
[the usual toff-topic trolling stuff]

Shit, da troll is back. Abuse reports need to go to
abuse [] pacbell.net and abuse [] swbell.net this time.

Jun 9 '06 #5
Xah Lee wrote:
Has anyone read this paper? And, would anyone be interested in giving a
summary?


Not you, of course. Too busy preparing the next diatribe against UNIX,
Perl, etc. ;)

Jun 9 '06 #6


Joe Marshall wrote:
Xah Lee wrote:
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?

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.

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.


Thanks for the summary.

Me, I would like to see a definition of expressiveness that would
exclude a programming mechanism from "things to be expressed".

If the subject is programmer productivity, well, I write programs to get
some behavior out of them, such as operating an ATM cash dispenser. If I
need to keep a list of transactions, I need to express the abstraction
"list" in some data structure or other, but below that level of
abstraction I am just hacking code, not expressing myself -- well, that
is the distinction for which I am arguing.

heck, in this case I will even give you as "thing to express" getting
back multiple values from a function. That comes up all the time, and it
can be an aggravation or a breeze. But then I would score C down because
it does not really return multiple values. One still has some heavy
lifting to do to fake the expressed thing. But I would still give it an
edge over java because Java's fakery would have to be a composite object
-- one could not have a primary return value as the function result and
ancillary values "somewhere else".

kt

--
Cells: http://common-lisp.net/project/cells/

"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Jun 9 '06 #7
hi Joe,

Joe Marshall wrote:
« Expressiveness isn't necessarily a good thing. For instance, in C,
you can express the addresses ...»

we gotta be careful here, because soon we gonna say binaries are the
most expressive. For instance, in assembly, you can express the
registers and stuff.

Expressiveness, with respect to — for lack of refined terms —
semantics, is a good thing, period. When discussing a language's
semantical expressiveness, it goes without saying that a “domain”
are understood, or needs to be defined. This is almost never mentioned
because it is very difficult. Put it in driveler's chant for better
understanding: we can't “compare apples with oranges”.

Let me give a example. Let's say i invented a language, where, there's
no addition of numbers, but phaserfy and realify with respective
operators ph and re. So, in my language, to do 1+2, you write “ph 1
re ph 2”, which means, to phaserfy 1, and phaserfy 2, then realify
their results, which results in 3. Now, this language is the most
expressive, because it can deal with concepts of phaserfy and realify
that no other lang can.

This may seem ridiculous, but is in fact a lot imperative languages do.
I won't go long here, but for instance, the addresses or references of
C and Perl is such. And in Java and few other OOP langs, there's
“iterator” and “enumerator things, are likewise immaterial.

As to OOP's iterator and enumerator things, and the general perspective
of extraneous concepts in languages, i'll have to write a essay in
detail some other day.

----

Thanks for the summary.

Is there no one else who are able to read that paper?

Xah
xa*@xahlee.org
http://xahlee.org/
Xah Lee wrote:
in March, i posted a essay "What is Expressiveness in a Computer
Language", archived at:
http://xahlee.org/perl-python/what_i...esiveness.html
...
On the Expressive Power of Programming Languages, by Matthias
Felleisen, 1990. http://www.ccs.neu.edu/home/cobbe/pl...ive-slides.pdf

Joe Marshall wrote: 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.

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.


Jun 14 '06 #8
"Joe Marshall" <ev********@gma il.com> writes:

On the Expressive Power of Programming Languages, by Matthias
Felleisen, 1990.
http://www.ccs.neu.edu/home/cobbe/pl...ive-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
overspecificati on 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
Jun 14 '06 #9
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 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.

Jun 14 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

220
19085
by: Brandon J. Van Every | last post by:
What's better about Ruby than Python? I'm sure there's something. What is it? This is not a troll. I'm language shopping and I want people's answers. I don't know beans about Ruby or have any preconceived ideas about it. I have noticed, however, that every programmer I talk to who's aware of Python is also talking about Ruby. So it seems that Ruby has the potential to compete with and displace Python. I'm curious on what basis it...
24
2602
by: Xah Lee | last post by:
What is Expresiveness in a Computer Language 20050207, Xah Lee. In languages human or computer, there's a notion of expressiveness. English for example, is very expressive in manifestation, witness all the poetry and implications and allusions and connotations and dictions. There are a myriad ways to say one thing, fuzzy and warm and all. But when we look at what things it can say, its power of
23
3641
by: Xah Lee | last post by:
The Concepts and Confusions of Pre-fix, In-fix, Post-fix and Fully Functional Notations Xah Lee, 2006-03-15 Let me summarize: The LISP notation, is a functional notation, and is not a so-called pre-fix notation or algebraic notation. Algebraic notations have the concept of operators, meaning, symbols placed around arguments. In algebraic in-fix notation, different
0
8851
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, well explore What is ONU, What Is Router, ONU & Routers main usage, and What is the difference between ONU and Router. Lets take a closer look ! Part I. Meaning of...
0
8736
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9373
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
9143
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
5992
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4761
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3202
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2588
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2137
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.