With regards to programming language elegance, it should be worthwhile to
take a look at what has emerged from research in Algorithmic Information
Theory and Complexity.
I found this definition by G. J. Chaitin;
" Call a program ``elegant'' if no smaller program has the same output.
I.e., a LISP S-expression is defined to be elegant if no smaller
S-expression has the same value. For any computational task there is at
least one elegant program, perhaps more. Nevertheless, we present a Berry
paradox proof that it is impossible to prove that any particular large
program is elegant. The proof is carried out using a version of LISP
designed especially for this purpose. This establishes an extremely
concrete and fundamental limitation on the power of formal mathematical
reasoning. "
The full article is at:
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.html
and a lot more stuff at his page at The Centre for Discrete Mathematics and
Theoretical Computer Science;
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
On a side note, I found this guy's biography rather interesting. Take a
look...
Biographical Note
Gregory Chaitin is a member of the computer systems & software department
at the IBM Watson Research Center in New York. In the mid 1960s, when he
was a teenager, he created algorithmic information theory, which combines,
among other elements, Shannon's information theory and Turing's theory of
computability. In the three decades since then he has been the principal
architect of the theory. Among his contributions are the definition of a
random sequence via algorithmic incompressibility, and his
information-theoretic approach to G�del's incompleteness theorem. His work
on Hilbert's 10th problem has shown that in a sense there is randomness in
arithmetic, in other words, that God not only plays dice in quantum
mechanics and nonlinear dynamics, but even in elementary number theory. He
is the author of four books: Algorithmic Information Theory published by
Cambridge University Press; Information, Randomness & Incompleteness and
Information-Theoretic Incompleteness, both published by World Scientific;
and The Limits of Mathematics, published by Springer-Verlag. In 1995 he was
given the degree of doctor of science honoris causa by the University of
Maine, and he was elected to the IBM Academy of Technology.
------------
pcm (···@mira.net) wrote:
: With regards to programming language elegance, it should be worthwhile to
: take a look at what has emerged from research in Algorithmic Information
: Theory and Complexity.
: I found this definition by G. J. Chaitin;
: " Call a program ``elegant'' if no smaller program has the same output.
< snip >
Or maybe we should call a program "elegant" if no *faster* program
(when run on the same machine) has the same output.
-- Wetboy
From: Mark Wilden
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <3436D7CF.7A44@mWilden.com>
wetboy wrote:
>
> Or maybe we should call a program "elegant" if no *faster* program
> (when run on the same machine) has the same output.
But that's the whole point: elegance is not the same thing as speed.
Mark Wilden <····@mWilden.com> wrote:
> wetboy wrote:
> >
> > Or maybe we should call a program "elegant" if no *faster* program
> > (when run on the same machine) has the same output.
>
> But that's the whole point: elegance is not the same thing as speed.
But it's not the same as brevity, either. I must say, for a formal
defintion, the supplied one left much to be desired, e.g., what is the
measure of "length"? the number of: characters, or "lines"--when
"properly" formatted, or keywords, or...? Without knowing this there's
really no way to make sense of "shortest". After all, if characters are
what get counted, then 1 character identifiers will rule the day. I
don't see how that will ensure elegance (in the intuitive sense).
Also, using a "built-in" function alone is not always a particularly
elegant program (not that it need be *inelegant*).
I'm sure that there are given "direct brute force" algorithms which have
instantiations as programs which are shorter than a given "more elegant"
program (that's another problem; elegance is a matter of degree). If we
are going to talk about program elegance, then we must talk about
algorithm elegance. (I won't even get into *language* elegance.)
Cheers,
Bijan Parsia
·······@email.unc.edu (Bijan Parsia) writes:
>But it's not the same as brevity, either. I must say, for a formal
>defintion, the supplied one left much to be desired, e.g., what is the
>measure of "length"? the number of: characters, or "lines"--when
>"properly" formatted, or keywords, or...?
All of this is crisply and clearly spelled out in Chaitin's book,
which is freely available by FTP. Why flame before you read?
Chaitin was *not* proposing this definition as a perfect translation
of the English word 'elegant'. He was analysing a technical concept
for which `elegant' was an appropriate name, and what he cared about
was the proof that this reasonably intuitive concept cannot be tested
in general.
--
John �neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
Richard A. O'Keefe <··@goanna.cs.rmit.edu.au> wrote:
> ·······@email.unc.edu (Bijan Parsia) writes:
>
> >But it's not the same as brevity, either. I must say, for a formal
> >defintion, the supplied one left much to be desired, e.g., what is the
> >measure of "length"? the number of: characters, or "lines"--when
> >"properly" formatted, or keywords, or...?
>
> All of this is crisply and clearly spelled out in Chaitin's book,
> which is freely available by FTP. Why flame before you read?
Um, A) I didn't thinking I was flaming, but rather criticizing. B) I
wasn't criticizing Chatin's book or his *actual* defintition, but the
defintion *as provided* by the original poster. (Note the phrase "the
supplied one".) I think if one is going to provide a formal defintion,
all the parts should be properly specified. The poster did not do so.
Granted, I probably should of checked the reference and then criticized
the poster on the basis of not having supplied all of the definition....
but I don't think it unreasonable to take a supplied formal definition
as complete, and to work with it directly.
> Chaitin was *not* proposing this definition as a perfect translation
> of the English word 'elegant'. He was analysing a technical concept
> for which `elegant' was an appropriate name, and what he cared about
> was the proof that this reasonably intuitive concept cannot be tested
> in general.
Fine, but that doesn't eliminate my other criticisms, which were *not*
of what Chaitin was doing (he could have called the concept "butt ugly"
for all I care; formal definition is--or tends to be--stipulative, so
what counts is the definition not the term).
However, there is, of course, a difference between giving a formal
stipulative definition, and providing a reasonable formalization of an
in-use natural language term. While 'elegant' is, perhpas, a
*reasonable* name for the concept 'shortest program generating a certain
output', I don't think that 'the shortest program generating a certain
output' is a reasonable approximation of the concept we were trying to
capture. Furthermore, I don't see that we're getting any closer to
*language* elegance. Remember that the orginal posting was designed to
provide a starting place for a discussion of language elegance. If the
original poster merely wanted to construct a concept, call it "language
elegance" on the basis of Chaitin's "program elegance" that is one thing
(and, while of some interest, not of interest to me, and probably not
relevant to the original discussion). If the original poster was after a
decent account of a reasonably intutive notion of language elegance,
then starting with a formal definition of program elegance which, IMHO,
*doesn't* answer to a reasonably intuitive notion of progam elegance (as
is commonly used) is a non-starter.
To recap: The definition, as presented, was incomplete. *Regardless* of
how you filled in the definition, it was inadequate *for the purposes of
the current discussion.* Neither point has anything to do with Chaitin's
actual definition, or it's adequacy for his purposes, or the worthiness
of those purposes.
(From the original post:
>With regards to programming language elegance, it should be worthwhile
>to take a look at what has emerged from research in Algorithmic
>Information Theory and Complexity.
>
>I found this definition by G. J. Chaitin;
>
>" Call a program ``elegant'' if no smaller program has the same output.
>I.e., a LISP S-expression is defined to be elegant if no smaller
>S-expression has the same value. For any computational task there is at
>least one elegant program, perhaps more. Nevertheless, we present a
Berry
>paradox proof that it is impossible to prove that any particular large
>program is elegant. The proof is carried out using a version of LISP
>designed especially for this purpose. This establishes an extremely
>concrete and fundamental limitation on the power of formal mathematical
>reasoning. "
>
>The full article is at:
Clearly, the purposes for which the definition was put forth was to help
find a reasonable ground for the discussion of programming language
elegance. Not quite as clearly from this post, but made clear by you,
this was not the original purpose of the definition. I don't think the
defintion as presented by the poster *OR* by Chaitin--that is, with
"smaller" spelled out--will do the job.
That all being said, I guess I should go read the paper. Unless, of
course, it has nothing to do with capturing the logic of the more
problematic value predicates we use with regard to various computer
science entities. That's what *I'm* interested in.)
Cheers,
Bijan Parsia
(P.S. Richard: I don't think *you* flamed me, but I do think you got me
wrong. Please elucidate if I've missed the point.)
Bijan Parsia <·······@email.unc.edu> wrote:
+---------------
| >" Call a program ``elegant'' if no smaller program has the same output.
+---------------
Chaitin's seems to have used "elegant" in the same way as, say, physicists
chose the names "charm" and "beauty" -- because it was cute! His work would
read equally well (perhaps better, for *this* crowd!) if he had used the word
"minimal" (or some other rough equivalent) instead of "elegant".
+---------------
| That all being said, I guess I should go read the paper. Unless, of
| course, it has nothing to do with capturing the logic of the more
| problematic value predicates we use with regard to various computer
| science entities. That's what *I'm* interested in.
+---------------
Chaitin's work has nothing to do with "programming language advocacy", rather,
it's about an information-theoretic approach to computability, and some
implications that arise from that approach to issues such as completeness
(or rather, incompleteness).
In particular, he shows several alternate (and probably a lot easier to
understand) derivations of Godel's first incompleteness theorem, including
some based on the Berry Paradox ("the smallest <XYZ> not describable by a
sentence/program smaller than <this one>") rather than the Liar's Paradox
("this statement is false") used by Godel. (Well, he says Godel actually
used "this statement is not provable in formal system <this one>").
His larger result is a claim that incompleteness is not a niggling artifact
of the formal system Godel chose to work in, but a much more serious universal
property.
Personally, I found it quite fascinating! However, it has nothing at all
to do with "pretty" versus "ugly" languages.
-Rob
-----
Rob Warnock, 7L-551 ····@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd. FAX: 650-933-4392
Mountain View, CA 94043 PP-ASEL-IA
In article <············@fido.asd.sgi.com>,
····@rigden.engr.sgi.com (Rob Warnock) wrote:
>
>
>In particular, he shows several alternate (and probably a lot easier to
>understand) derivations of Godel's first incompleteness theorem, including
>some based on the Berry Paradox ("the smallest <XYZ> not describable by a
>sentence/program smaller than <this one>") rather than the Liar's Paradox
>("this statement is false") used by Godel. (Well, he says Godel actually
>used "this statement is not provable in formal system <this one>").
>
Godel did NOT use the Liar's Paradox, which would not have been any use to
him, since it is paradoxical. He used a statement which asserts it's own
unprovability (is that a word?) and then goes on to show it true. No paradox
here.
Peter
Rob Warnock <····@rigden.engr.sgi.com> wrote:
> Bijan Parsia <·······@email.unc.edu> wrote:
> +---------------
> | >" Call a program ``elegant'' if no smaller program has the same output.
> +---------------
>
> Chaitin's seems to have used "elegant" in the same way as, say, physicists
> chose the names "charm" and "beauty" -- because it was cute! His work would
> read equally well (perhaps better, for *this* crowd!) if he had used the word
> "minimal" (or some other rough equivalent) instead of "elegant".
I, by and large, argree. I think it's a *little* better than the
physicists as there is *some* connection between minimality and
elegance. What would be interesting is to see what qualifications could
be added to the definition that would extend it to cover more of the
intuitive cases. I suspect that we'll have trouble ending up with a
concept that is even extensionally equivalent to "elegant".
[snipped quote from me]
>
> Chaitin's work has nothing to do with "programming language advocacy", rather,
> it's about an information-theoretic approach to computability, and some
> implications that arise from that approach to issues such as completeness
> (or rather, incompleteness).
That sounds pretty cool (if, as I suspected, off topic).
[details of the paper snipped]
> His larger result is a claim that incompleteness is not a niggling artifact
> of the formal system Godel chose to work in, but a much more serious universal
> property.
Hmm. *Godel* showed *that*. Any system which is strong enough to include
the Peano axioms will suffer from incompleteness. (There are some
people, I think--talking off the top of my head late at night so I'm
probably getting this all wrong--who think that an intensional approach
of some kind might do the trick. And Carnap--again I'm just digging into
my confused memory--thought that a system with an infinite number of
axioms could be complete. That is, you just added *all* the Godel
sentences--as opposed to one at a time. I didn't think much of this
strategy.)
Cheers,
Bijan.
On Tue, 7 Oct 1997 22:49:55 -0500, Bijan Parsia <·······@email.unc.edu> posted:
>Rob Warnock <····@rigden.engr.sgi.com> wrote:
>
>> Bijan Parsia <·······@email.unc.edu> wrote:
>> +---------------
>> | >" Call a program ``elegant'' if no smaller program has the same output.
>> +---------------
>>
>> Chaitin's seems to have used "elegant" in the same way as, say, physicists
>> chose the names "charm" and "beauty" -- because it was cute! His work would
>> read equally well (perhaps better, for *this* crowd!) if he had used the word
>> "minimal" (or some other rough equivalent) instead of "elegant".
>
>I, by and large, argree. I think it's a *little* better than the
>physicists as there is *some* connection between minimality and
>elegance. What would be interesting is to see what qualifications could
>be added to the definition that would extend it to cover more of the
>intuitive cases. I suspect that we'll have trouble ending up with a
>concept that is even extensionally equivalent to "elegant".
Indeed.
What Chaitlin talks about certainly sounds like the notion of
Komolgorov complexity where you define the *complexity* of a function
by the size of the "simplest"/"shortest" formula that can be used to
compute the function.
In this fashion, Pi (that number that resembles 22/7 :-) ) can be
described by a variety of computations. The Komolgorov complexity
is the size of the shortest such computation.
Mapping "shortness" to "elegance" (as Chaitlin does) seems to me to
be a bit of a stretch.
The process of minimizing the size of a computation does not seem
likely to me to result necessarily in an "elegant" answer. One might
*hope* that this would be the case; it's just as likely that minimizing
the expression results in an impenetrably complex-looking result.
One can take Perl code that is as attractively-formatted as it gets,
and then shorten variable names to the minimum possible, then
remove comments and any excess spaces, and attain a rather wonderful
*MESS.* They have contests for this sort of thing; calling it
"elegant" isn't the first term I'd think of. "Perverse" would be
a better word.
>[snipped quote from me]
>> Chaitin's work has nothing to do with "programming language advocacy", rather,
>> it's about an information-theoretic approach to computability, and some
>> implications that arise from that approach to issues such as completeness
>> (or rather, incompleteness).
>That sounds pretty cool (if, as I suspected, off topic).
It's the topic that Chaitlin is talking about, so it's at least relevant
to discussing his article.
Was it Einstein who said that you should simplify things as much as
appropriate, and no further, or was it Feynman?
That would be the way I'd look at it; the most elegant representation
of something in a programming language is a representation that has been
simplified as much as possible, but not further than is possible...
--
Christopher B. Browne, ········@hex.net, ············@sdt.com
PGP Fingerprint: 10 5A 20 3C 39 5A D3 12 D9 54 26 22 FF 1F E9 16
URL: <http://www.hex.net/~cbbrowne/>
Bill Gates to his broker: "You idiot, I said $150 million on **SNAPPLE**!!!"
Christopher Brown wrote:
> Mapping "shortness" to "elegance" (as Chaitlin does) seems to me to
> be a bit of a stretch.
>
> The process of minimizing the size of a computation does not seem
> likely to me to result necessarily in an "elegant" answer. One might
> *hope* that this would be the case; it's just as likely that minimizing
> the expression results in an impenetrably complex-looking result.
>
> One can take Perl code that is as attractively-formatted as it gets,
> and then shorten variable names to the minimum possible, then
> remove comments and any excess spaces, and attain a rather wonderful
> *MESS.* They have contests for this sort of thing; calling it
> "elegant" isn't the first term I'd think of. "Perverse" would be
> a better word.
What's more, this is the *point* of Chaitin's paper that was cited.
The fact that `elegant' programs look random is intimately connected
to the fact that one can't reliably recognise them.
(If a program *does* have much noticeable structure, then you can
use that to compress it, so it isn't shortest-possible.)
Chaitin's work is interesting (though, I'm uncharitably inclined to think,
not quite as interesting as he thinks it is) but of course it doesn't
have anything to do with what's usually called `elegance' by programmers.
It's a bit closer to the mathematician's idea of elegance, which puts a
big premium on short proofs.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
From: John Clements
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <61tvv4$5s4$1@joe.rice.edu>
In article <·······················@knuth.brownes.org>,
Christopher B. Browne <········@hex.net> wrote:
>
>One can take Perl code that is as attractively-formatted as it gets,
>and then shorten variable names to the minimum possible, then
>remove comments and any excess spaces, and attain a rather wonderful
>*MESS.* They have contests for this sort of thing; calling it
>"elegant" isn't the first term I'd think of. "Perverse" would be
>a better word.
>
Okay, I'm trying to stay out of this, but people keep bringing up
this "short variable names" and "no whitespace" issue. Go back
to the original "short=elegant" post and substitute "shortest
token string" for "shortest program". I'm certain Chaitin wasn't
suggesting that using single-letter variable names was more elegant.
That's all.
john clements
--
"Sorry, I will stick with the old school here. You dope smoking Lisp and Scheme
hippies can try your Newspeak on some undergraduate freshmen."
--- "Kaz", posting to comp.lang.<your favorite language here>
> In article <·······················@knuth.brownes.org>,
> Christopher B. Browne <········@hex.net> wrote:
> >
> >One can take Perl code that is as attractively-formatted as it gets,
> >and then shorten variable names to the minimum possible, then
> >remove comments and any excess spaces, and attain a rather wonderful
> >*MESS.* They have contests for this sort of thing; calling it
> >"elegant" isn't the first term I'd think of. "Perverse" would be
> >a better word.
> >
>
> Okay, I'm trying to stay out of this, but people keep bringing up
> this "short variable names" and "no whitespace" issue. Go back
> to the original "short=elegant" post and substitute "shortest
> token string" for "shortest program". I'm certain Chaitin wasn't
> suggesting that using single-letter variable names was more elegant.
Chaitin is doing recursion theory. In that context _any_ mechanical
transformation is considered just another equivalent program.
The first few results in this field are:
There _is_ a unique shortest program for any given problem. It is _not_
possible in general to compute that program from an arbitrary program
for the same problem.
This contrasts with the situation for time complexity. There may be
_no_ fastest program for a given problem, because running time is not
a simple number, it is a function of input size. There may be an
infinite sequence of programs that solve the same problem, each faster
than the one before. Each program deals with longer and longer input
before it begins to get slow.
It is no more useful to get into an argument about whether this really
constitutes elegance than it is to interupt a mathematician in the
middle of proof about a number field, to object that this has nothing
to do with wide flat grassy areas.
--
--Keith
This mail message sent by GNU emacs and Linux.
Power to the people. Linux is here.
Food, Shelter, Source code.
········@news.brownes.org (Christopher B. Browne) writes:
>
> What Chaitlin talks about certainly sounds like the notion of
> Komolgorov complexity where you define the *complexity* of a function
> by the size of the "simplest"/"shortest" formula that can be used to
> compute the function.
Algorithmic complexity emerged in the mid sixties through independent
works of R. J. Solomonoff, A. N. Kolmogorov and G. J. Chaitin. See the
the Li and Vitanyi bible of K-complexity for further details.
-Bill Dubuque
Bijan Parsia (·······@email.unc.edu) wrote:
: Um, A) I didn't thinking I was flaming, but rather criticizing. B) I
: wasn't criticizing Chatin's book or his *actual* defintition, but the
: defintion *as provided* by the original poster. (Note the phrase "the
: supplied one".) I think if one is going to provide a formal defintion,
: all the parts should be properly specified. The poster did not do so.
Actually, the quote that was posted was the *full* text of the
abstract to the article referred to in the web link provided.
If the full text (1000s of lines) had been posted then the
amount of complaints would have been enourmous (and fully
justified). After apparantly flaming this posting twice
now I think you should *really* go and read the article
pointed to in the original posting!!
Cheers,
- PCM
On Tue, 7 Oct 1997, P Murray wrote:
> In article <······················@s013h009.dialup.unc.edu> you wrote:
>
> : Um, A) I didn't thinking I was flaming, but rather criticizing. B) I
> : wasn't criticizing Chatin's book or his *actual* defintition, but the
> : defintion *as provided* by the original poster. (Note the phrase "the
> : supplied one".) I think if one is going to provide a formal defintion,
> : all the parts should be properly specified. The poster did not do so.
>
> Actually, the quote that was posted was the *full* text of the
> abstract to the article referred to in the web link provided.
> If the full text (1000s of lines) had been posted then the
> amount of complaints would have been enourmous (and fully
> justified).
And an abstract isn't necessarily a formal definition. I didn't ask for
the full text, I asked for the full formal definition. To fully specify
it, all that was needed was to supply a formal account (or, indeed,
*any* account) of 'smaller'. I doubt that the entire text would be
needed.
Why would you think it was, or that that was what I required? Typically,
formal definitions are a very small part of a work, and a relatively
self-contained (typically taking up a mere paragraph on the order of the
one supplied). When I finally *do* look at the text, I rather suspect
that I'll find that very little has to do with the definition, and quite
a lot has to do with establishing the proof.
To reiterate: The original poster (was that you?) wasn't suggesting that
we read the paper together and discuss it (as I read the poster).
Rather, that person proposed that we take the formal definition (and the
"results") and use it as a starting point for a fresh discussion of
language elegance. I responded *first* by pointing out that the formal
definition, *even if fully specified*, was *prima facie* inadquate to
the task at hand (regardless of it's usefulness otherwise), and *second*
(as an elaboration of the first) by pointing out that the formal
definition was incomplete and (by implication) that the choices
available--any *one* of which would satisfy the demands of formality,
though not necessarily for Chatin's purposes--were all unsatisfactory
*for the current discussion*.
Is it really so hard to read my post contextually? Nothing Richard has
said has made the definition any *more* appealing; indeed, it has made
it
less so. Pointing out that the definition in the paper was complete, or
that it was designed for a specific purpose (which is *not* the purpose
for which is was proposed in the original post), or that the original
paper was too long to post are all irrelevant. Richard supplied the
completed definition, the purpose for which the definition was used is
off-topic, the filling in of the hole was but a single line (thus the
whole paper need not have been posted), and the paper isn't, as far as I
can tell until I read the damn thing, itself purporting to address the
issue at hand.
If it isn't even *purporting* to address the issue at hand (as the
abstract makes clear), and what I'm interested in is the issue at hand,
why *should* I read it. There's lots to read in the world.
(A followup in this thread makes it very clear what the article is
attempting--and I find that interesting *in itself*. So when I clear my
plate, I *will* read it. However, I don't need to read it before making
the comments I have, as that same post made clear.)
> After apparantly flaming this posting twice
> now I think you should *really* go and read the article
> pointed to in the original posting!!
Am I even apparently flaming? I really don't think so. My second
posting was a response to *Richard's* post, in which, as I said in *my*
response, I believe he misrepresented my words, and criticized (not very
kindly) those words.
(You too, I believe, have misrepresented my words (again, not very
kindly).)
Thus, my second post merely *mentioned* my earlier criticism; it didn't
*use* it. I don't see how my criticism of *Richard's* post, which made
*no* reference to the contents of the article (my criticism, that is) is
a flame of the *article* (which, I conclude is Richard's complaint).
You at least, acknowledge that I was discussing the *article*. But, I
have argued, your criticism is off target. The original poster did not
need to post the whole article to satisfy the "formal definition"
complaint, and, unless I hear or read otherwise, no one has addressed
the point that this formal definition is *prima facie* inadqueate to
handle questions about the elegance *generally speaking* of programs and
programming languages.
Given that there *could* be a brute force solution that was shorter (in
the specified sense) than some "more elegant" solution is the reason I
think that that definition is inadequate (for my purposes). Of course, a
knock down case would have to supply the two programs (the brute force
and the longer elegant one).
Another worry: the definition doesn't *seem* to allow for *comparative*
judgements.
Yes yes yes, of course he might *extend* the definition. But *as it
stood* it didn't handle it. (And if we do the straightforward mapping of
short*er* to *more* elegant, I bet we'll have an easier time finding
counterexamples.)
>
> Cheers,
> - PCM
So, did you flame me? Seems like. Maybe Richard did too. In which case,
*I've* been flamed twice in a row *without* having been charitibly read.
even with the text right in front of each of you!!
<sigh> I perfer not to believe that. I prefer to believe that we're just
miscommunicating. But I'm really at a loss on how to be *more* clear. In
my response to Richard, I very carefully limited my claims. I'm doing so
with you as well.
Cheers,
Bijan Parsia.
P.S. Further response is welcome. But I'd really rather you didn't claim
that I'm flaming (it is sad to me that perfectly rational and
polite--*even if* it were, contrary to fact, misinformed--criticism
counts as flaming), at least, without better evidence that I have been.
If reading the article changes my mind, you can bet I'll post something
to that effect. (It won't change my mind about the original post, since
all my criticism was directed to the actual content of that post.) I
also rather that you didn't include weakly supported imperatives. I
could have responded to both you and to Richard with, respectively "You
should *really* reread my posts." and "Why don't *you* read before you
flame." I didn't. I took you both seriously, and responded a carefully
and completely as I could to your *content*. I would *like* the same in
return.
If anyone else has complaints about what I read, let's take it to email.
I'm am cc-ing you a copy, as that's what you did for me. Please don't,
in the future.
I'm really glad that encoding a program needing the smallest number of bits
will make it elegant. I am going to run all of my programs through arithmetic
compression of order 9 and come up with some really elegant stuff. Or perhaps
it is lack of entropy, not just smallest size? Well, if that is the case,
then I will run the result of compression through several 128 bit encryption
algorithms. Talk about ELEGANCE!
--
C-FAQ ftp sites: ftp://ftp.eskimo.com ftp://rtfm.mit.edu
Hypertext C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
C-FAQ Book: ISBN 0-201-84519-9.
Want Software? Algorithms? Pubs? http://www.infoseek.com
In article <·············@mWilden.com>, Mark Wilden <····@mWilden.com> wrote:
>wetboy wrote:
>>
>> Or maybe we should call a program "elegant" if no *faster* program
>> (when run on the same machine) has the same output.
>
>But that's the whole point: elegance is not the same thing as speed.
But then we could also say that elegance is not the same thing as size. Why
should size be preferred to speed as a parameter of elegance?
Do we look at the size of executable code or source code?
Are the winners of the obfuscated C competition more elegant than neatly
written, maintainable programs?
Shouldn't correctness also count? A program more elegant than another should
not only produce the same output, but also be equally robust, and avoid
failures equally well.
Etc.
--
Kaz <···@latte.cafe.net> wrote in article <············@latte.cafe.net>...
> In article <·············@mWilden.com>, Mark Wilden <····@mWilden.com>
wrote:
> >wetboy wrote:
> >>
> >> Or maybe we should call a program "elegant" if no *faster* program
> >> (when run on the same machine) has the same output.
> >
> >But that's the whole point: elegance is not the same thing as speed.
> But then we could also say that elegance is not the same thing as size.
Why
> should size be preferred to speed as a parameter of elegance?
Good point. We can define a measure and give it any name we chose. I could
call the program whose combined source code files have the fewest carriage
returns to be the most "lengthy" and stand on the claim that I have merely
used a word as a name and have defined it's meaning very clearly. But
nearly everyone would take exception to my use of the word "lengthy"
because my definition is not consistent with the other common
interpretations of that word.
If you are going to use a word such as "elegant" that has certain
subjective connotations to define a very concrete technical concept, then
you really do have an obligation to justify that what you are defining is
not at odds with the subjective meanings of that word.
> Do we look at the size of executable code or source code?
>
> Are the winners of the obfuscated C competition more elegant than neatly
> written, maintainable programs?
>
> Shouldn't correctness also count? A program more elegant than another
should
> not only produce the same output, but also be equally robust, and avoid
> failures equally well.
I think the claim here would be that for two programs to produce the same
output they would, by definition, be equally robust and equally able to
avoid failures. If not, you have a case where, in at least some situations,
the output of one is different from the output of the other.
William L. Bahn wheezed these wise words:
> If you are going to use a word such as "elegant" that has certain
> subjective connotations to define a very concrete technical concept, then
> you really do have an obligation to justify that what you are defining is
> not at odds with the subjective meanings of that word.
The alternative is to play the "egg orientation" game. In other words,
fight over which way an egg should be oriented. (See Gulliver's
Travels, by Jonothan Swift.)
We _could_ save a lot of time. ;) I'll get my coat.
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
Please note: my email address is gubbish
assert(got(coat)).
From: Mark Wilden
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <3437E033.5A4B@mWilden.com>
Kaz wrote:
>
> In article <·············@mWilden.com>, Mark Wilden <····@mWilden.com> wrote:
> >wetboy wrote:
> >>
> >> Or maybe we should call a program "elegant" if no *faster* program
> >> (when run on the same machine) has the same output.
> >
> >But that's the whole point: elegance is not the same thing as speed.
>
> But then we could also say that elegance is not the same thing as size. Why
> should size be preferred to speed as a parameter of elegance?
I don't know why people are asking me this. I've never said elegance has
anything to do with size.
From: ? the platypus {aka David Formosa}
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <876032397.288944@cabal>
In <··········@fridge.shore.net> ······@shore.net (wetboy) writes:
>pcm (···@mira.net) wrote:
[...]
>: " Call a program ``elegant'' if no smaller program has the same output.
>< snip >
>Or maybe we should call a program "elegant" if no *faster* program
>(when run on the same machine) has the same output.
No that IMHO is a diffrent concet, that is speed optimisation, meany
in-elegant things have been done at the alter of speed.
--
Please excuse my spelling as I suffer from agraphia see the url in my header.
Never trust a country with more peaple then sheep. Buy easter bilbies.
Save the ABC Is $0.08 per day too much to pay? ex-net.scum and proud
I'm sorry but I just don't consider 'because its yucky' a convincing argument
In article <··········@fridge.shore.net> ······@shore.net "wetboy" writes:
>pcm (···@mira.net) wrote:
>: With regards to programming language elegance, it should be worthwhile to
>: take a look at what has emerged from research in Algorithmic Information
>: Theory and Complexity.
>
>: I found this definition by G. J. Chaitin;
>
>: " Call a program ``elegant'' if no smaller program has the same output.
>< snip >
>
>Or maybe we should call a program "elegant" if no *faster* program
>(when run on the same machine) has the same output.
Elegance is an aethetic property. It isn't simply down to size, it has
something to do with simplicity, clarity and beauty (which of course is
very subjective).
--
-----------------------------------------
Lawrence Kirby | ····@genesis.demon.co.uk
Wilts, England | ·········@compuserve.com
-----------------------------------------
Lawrence Kirby wrote:
> Elegance is an aethetic property. It isn't simply down to size,
> it has something to do with simplicity, clarity and beauty
> (which of course is very subjective).
Elegance is self-apparent, except for those for whom it isn't.
-thant
--
thant at acm dot org
I propose that "an elegant language provides the greatest semantic
verbosity for the minimal syntactic encapsulation".
Ie: the meaning is clear without twenty-character identifiers.
Take this (pseudo C) example:
void sort(void); {
long ptr, temp;
long pos = 1;
for (arr[0] = 1 << 31 ; pos < size ; pos++)
for (ptr = pos ; arr[ptr] < arr[ptr - 1] ;)
{ temp = arr[ptr];
arr[ptr] = arr[ptr - 1];
arr[--ptr] = temp; } }
and this equivalent BASIC/Pascal example:
Proc sort
Local ptr, pos
arr[0] := 1 << 31
For pos := 1 To size Do
ptr := pos
While arr[ptr] < arr[ptr - 1]
Swap arr[ptr], arr[ptr - 1]
EndWhile
Next
EndProc
Is it more elegant to produce less source code, object code or faster
execution? Why reason about such meaningless metrics at all?
Is it not more reasonable to say a grammar/language is elegant if you
can more easily understand some arbitrary string in that language than
an 'equivalent' string in some other language, while both are optimal
representations of some given computation (excluding white space and
identifier length).
Steve
--
Stephen Revill, Software Engineer Tel: +44 (0) 1223 725 296 #5296
Applied Technologies WWW: http://www.acorn.com/acorn/
Acorn Computers Ltd
Acorn House, 645 Newmarket Road, Cambridge, United Kingdom, CB5 8PB
From: Charles Fiterman
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <343A3C1E.5E7@geodesic.com>
Language elegance depends a lot on the problem
domain. If you are in a problem domain where
most of the work is spent understanding the
domain and its rules you are going to be stuck
with massive comments and long symbol names.
Suppose you are writing programs intimately
connected with the tax code. You will have
dozens of comment lines for every line of
code. Your bugs will largely be the result
of misreading the problem domain rather than
errors in algorithms.
Not only that but when you go to meetings
you will meet with people who took COBOL
courses at school and can read that language
and no other. This suggests that COBOL is
an elegant language in that domain.
Yes. I admit part of why I said that is I
like saying outrageous things.
I've suggested a tool for an OO language
which I call "Springtime for COBOL" which
would allow an object oriented program to
be written normally and printed out in
COBOL like syntax. The COBOL syntax would
be used to take to meetings not to write
code.
In article <················@srevill.acorn.co.uk>, Steve wrote:
>I propose that "an elegant language provides the greatest semantic
>verbosity for the minimal syntactic encapsulation".
What a completely inelegant sentence :-)
The first time elegance really dawned on me (you don't learn it, you
experience it), was in a comparative programming languages class, where
I first learned Lisp.
We were given a few tiny programs to do in Lisp, over the course of 2
assignments I think. They were the most rudimentary of programs,
designed for absolute novices at Lisp. But they ended up teaching a
lot more about programming than it seemed at first.
First, was a program to extract every other element from a list with
an odd index. Second, was a program to do the same, but only those
with an even index (get the cdr then call the first program). Third,
write a function that takes two sorted lists, and merges them into a
single sorted list. Then maybe some other similar functions, I
forget. Finally, take the bits, and make a full sort program from
them. It was simple at that point; split the list into two (evens and
odds), sort those, and merge the results. And it was all done in a
purely functional manner, no goto's, prog's, or anything like that.
It was very inefficient, but very understandable and very elegant.
I just said "wow".
Recursion has always seemed elegant to me; to many though, it's a
curse (I've been a TA several times, and students hate recursion).
But it distills algorithms down into their basics; draw trunk, draw
left subtree, draw right subtree, very straight forward (pity the
people that had to learn recursion with only text output). Or, find
pivot, partition, sort first half, sort second half. That's the whole
algorithm, all the rest is glue and efficiency and pragmatic concerns.
--
Darin Johnson
·····@usa.net.delete_me
In article <·············@signature.below>, Thant Tessman wrote:
>Elegance is self-apparent, except for those for whom it isn't.
Everyone says the programming is a mix of art and science. Well...
Elegance is the "art" in programming.
--
Darin Johnson
·····@usa.net.delete_me
In article <····················@connectnet1.connectnet.com>,
Darin Johnson <·····@usa.net.delete_me> wrote:
>In article <·············@signature.below>, Thant Tessman wrote:
>>Elegance is self-apparent, except for those for whom it isn't.
>
>Everyone says the programming is a mix of art and science. Well...
>
>Elegance is the "art" in programming.
>
>--
>Darin Johnson
>·····@usa.net.delete_me
Yes, I agree. 'Elegance' is a judgement of aesthetics, which is INHO
impossible to _completely_ formulate. People who have years of experience
in a certain field are the ones who are equipped to make such judgements
of about work in their domain. For example, I'd love to hear what Donald
Knuth thinks is an 'elegant' language, and why.
However, in the field of aesthetics, people have been able to make some
kinds of formal analyses of quality and beauty. This goes back to
the ancient Greeks' discussion of proportion, and beyond. There is a book
on my shelf called 'The Elements of Typographic Style' by Robert Bringhurst
which I refer to to get pleasing proportions to use on the financial
reports I program, because I don't have much visual design talent.
In that case, some formal rules of desin work well enough, but true artistry
can't be learned from a book in typography, programming or anything else.
So I believe that we may have some limited objective basis for
judging elegance in programming languages,
but we should be fully aware of the limitations of this, and as Darin
implied, recognize that which falls into the domain of art.
--
// Michael Davis, Programmer/Analyst I don't speak for Multipath. //
// ······@DELmultipath.com Nor do I speak against them. //
// Toronto The 'DEL' in my address is an anti-spam device. //
In comp.lang.c++ Michael Davis <······@DELmultipath.com> wrote:
[...]
: Yes, I agree. 'Elegance' is a judgement of aesthetics, which is INHO
: impossible to _completely_ formulate. People who have years of experience
: in a certain field are the ones who are equipped to make such judgements
: of about work in their domain. For example, I'd love to hear what Donald
: Knuth thinks is an 'elegant' language, and why.
: However, in the field of aesthetics, people have been able to make some
: kinds of formal analyses of quality and beauty. This goes back to
: the ancient Greeks' discussion of proportion, and beyond. There is a book
: on my shelf called 'The Elements of Typographic Style' by Robert Bringhurst
: which I refer to to get pleasing proportions to use on the financial
: reports I program, because I don't have much visual design talent.
: In that case, some formal rules of desin work well enough, but true artistry
: can't be learned from a book in typography, programming or anything else.
I agree.
Programming languages are tools, crafted by language designers, for
use by programmers. There are principles of good tool design that
transcend the particular tool domains and have been studied both from
the standpoint of aesthetics and from the standpoint of human
usability. (See, for example, Donald Norman's book, The Design of
Everyday Things.)
Certainly for programming languages such factors as naturalness,
readability, expressiveness, regularity, etc. must rank as much more
important than the compactness of minimal programs touted eariler in
this thread. Another important feature is the compactness of the
language's specification, though issues of elegance in language
specification simply push the same discussion up to the metalanguage
level. (I hate reading Van Wijngaarden grammars and don't find them
elegant.)
Tom Payne
You mean you don't think APL is best?
Tom Payne wrote:
> In comp.lang.c++ Michael Davis <······@DELmultipath.com> wrote:
> [...]
> : Yes, I agree. 'Elegance' is a judgement of aesthetics, which is INHO
> : impossible to _completely_ formulate. People who have years of experience
> : in a certain field are the ones who are equipped to make such judgements
> : of about work in their domain. For example, I'd love to hear what Donald
> : Knuth thinks is an 'elegant' language, and why.
>
> : However, in the field of aesthetics, people have been able to make some
> : kinds of formal analyses of quality and beauty. This goes back to
> : the ancient Greeks' discussion of proportion, and beyond. There is a book
> : on my shelf called 'The Elements of Typographic Style' by Robert Bringhurst
> : which I refer to to get pleasing proportions to use on the financial
> : reports I program, because I don't have much visual design talent.
>
> : In that case, some formal rules of desin work well enough, but true artistry
> : can't be learned from a book in typography, programming or anything else.
>
> I agree.
>
> Programming languages are tools, crafted by language designers, for
> use by programmers. There are principles of good tool design that
> transcend the particular tool domains and have been studied both from
> the standpoint of aesthetics and from the standpoint of human
> usability. (See, for example, Donald Norman's book, The Design of
> Everyday Things.)
>
> Certainly for programming languages such factors as naturalness,
> readability, expressiveness, regularity, etc. must rank as much more
> important than the compactness of minimal programs touted eariler in
> this thread. Another important feature is the compactness of the
> language's specification, though issues of elegance in language
> specification simply push the same discussion up to the metalanguage
> level. (I hate reading Van Wijngaarden grammars and don't find them
> elegant.)
>
> Tom Payne
In article <··········@fridge.shore.net>,
wetboy <······@shore.net> wrote:
>pcm (···@mira.net) wrote:
>: With regards to programming language elegance, it should be worthwhile to
>: take a look at what has emerged from research in Algorithmic Information
>: Theory and Complexity.
>
>: I found this definition by G. J. Chaitin;
>
>: " Call a program ``elegant'' if no smaller program has the same output.
>< snip >
>
>Or maybe we should call a program "elegant" if no *faster* program
>(when run on the same machine) has the same output.
It seems to me that speed normally has more to do with the algorithm
than the language it's implemented in. A good (elegant?) language will
be flexible enough to allow an efficient algorithm to be implemented
easily, and complete enough that coding details don't get in the way.
This may require such a language to be special purpose. For
example, Prolog may be 'elegant' for a scheduling problem, but if you
try to implement a text editor you'll be spending more time using cuts
and other techniques to combat the very side effects which make it
suitable for AI, just to prevent it from changing your efficient
text-editor algorithm into an inefficient and near-useless tree-search
algorithm.
--
John Bayko (Tau).
·····@cs.uregina.ca
http://www.cs.uregina.ca/~bayko
·····@borealis.cs.uregina.ca (John Bayko) writes:
> This may require such a language to be special purpose. For
>example, Prolog may be 'elegant' for a scheduling problem, but if you
>try to implement a text editor you'll be spending more time using cuts
>and other techniques to combat the very side effects which make it
>suitable for AI, just to prevent it from changing your efficient
>text-editor algorithm into an inefficient and near-useless tree-search
>algorithm.
This is a really weird paragraph.
Cuts not only _don't_ "combat side effects", they very nearly _are_
side effects.
Side effects do NOT make Prolog suitable for AI; it is the relative
ABSENCE of side effects which makes Prolog useful for that.
What's more, David Warren, the inventor of the DEC-10 Prolog compiler,
*DID* write a text editor in Prolog, and used it for years. Cuts were
not used to make it efficient, because they don't that. INDEXING is
what makes Prolog efficient (when it is).
--
John �neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
··@goanna.cs.rmit.edu.au (Richard A. O'Keefe) writes:
>What's more, David Warren, the inventor of the DEC-10 Prolog compiler,
>*DID* write a text editor in Prolog, and used it for years. Cuts were
>not used to make it efficient, because they don't that. INDEXING is
>what makes Prolog efficient (when it is).
Can you explain what you mean by indexing? Do you mean the compiler must
keep an index of predicates? Can this be influenced by the programmer at
all then?
To address your second point, here's my opinion: actually when I look at
many of the so-called "standard personal productivity products" I
find that there is a multitude of inept programs to choose from. That's
why I write my own as well, whenever time permits. And I'm happy to
exploit the extra flexibility Prolog gives me.
Ulrich
--
Ulrich Mayring
Please reply to: u @ 123 . org
==========================================================================
You can also use ulim @ addict . de or ulim @ freebsd . first . gmd . de
From: Vasili N. Galchin
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <343E9B0A.4AFD@bnr.ca>
Torkel Franzen wrote:
>
> ····@127.0.0.1 (Ulrich Mayring) writes:
>
> >Can you explain what you mean by indexing? Do you mean the compiler must
> >keep an index of predicates? Can this be influenced by the programmer at
> >all then?
>
> From the SICStus manual, at http://www.sics.se/isl/sicstus/sicstus_toc.html:
>
> Indexing
>
> The clauses of any predicate are indexed according to the principal
> functor of the first argument in the head of the clause. This means
> that the subset of clauses which match a given goal, as far as the
> first step of unification is concerned, is found very quickly, in
> practically constant time. This can be very important where there is a
> large number of clauses for a predicate. Indexing also improves the
> Prolog system's ability to detect determinacy--important for
> conserving working storage, and strongly related to last call
> optimization (see below).
>
> Indexing applies to interpreted clauses as well as to compiled clauses.
Sorry this is intended as a thread of original topic! Ptof Fielson(sp??)
at Rice Univ. wrote a paper that is an attempt to formalize the notion
of program expressiveness. This seems to go along with elegance. maybe
somebdoy else can give citation of paper?????
Regards,
Vasili N. Galchin
From: Shriram Krishnamurthi
Subject: Expressiveness (was Re: A Formal Definition of LANGUAGE ELEGANCE)
Date:
Message-ID: <j7vzpodf7tg.fsf_-_@africa.cs.rice.edu>
[Note followups.]
"Vasili N. Galchin" <········@bnr.ca> writes:
> Sorry this is intended as a thread of original topic! Ptof Fielson(sp??)
> at Rice Univ. wrote a paper that is an attempt to formalize the notion
> of program expressiveness. This seems to go along with elegance. maybe
> somebdoy else can give citation of paper?????
You mean Felleisen. The reference is
@inproceedings{scp91-felleisen,
author = "Matthias Felleisen",
year = "1991",
booktitle = "Science of Computer Programming",
volume = "17",
pages = "35-75",
note = "Preliminary version in: {\it Proc. European
Symposium on Programming}, Lecture Notes in Computer Science,
432. Springer-Verlag (1990), 134--151.",
title = "On the Expressive Power of Programming Languages"
}
Find it at
http://www.cs.rice.edu/CS/PLT/Publications/scp91-felleisen.{dvi,ps}.gz
'shriram
In article <············@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <··@goanna.cs.rmit.edu.au> wrote:
>·····@borealis.cs.uregina.ca (John Bayko) writes:
>> This may require such a language to be special purpose. For
>>example, Prolog may be 'elegant' for a scheduling problem, but if you
>>try to implement a text editor you'll be spending more time using cuts
>>and other techniques to combat the very side effects which make it
>>suitable for AI, just to prevent it from changing your efficient
>>text-editor algorithm into an inefficient and near-useless tree-search
>>algorithm.
>
>This is a really weird paragraph.
>Cuts not only _don't_ "combat side effects", they very nearly _are_
>side effects.
>Side effects do NOT make Prolog suitable for AI; it is the relative
>ABSENCE of side effects which makes Prolog useful for that.
I suppose I mis-used the term 'side effects' here - what I meant
is that you're going to be fighting Prolog's tendency to execute
programs as a tree search algorithm if you try to use it to implement
a procedural algorithm.
>What's more, David Warren, the inventor of the DEC-10 Prolog compiler,
>*DID* write a text editor in Prolog, and used it for years. Cuts were
>not used to make it efficient, because they don't that. INDEXING is
>what makes Prolog efficient (when it is).
In that case, chances are that the algorithm he used was suited
for Prolog (being the shaping force of modern Prolog systems, it's
probably more natural for him to think Prologishly anyway). But on
the other hand, I/O is entirely side-effectual as far as Prolog goes
anyway - it's not a 'natural' Prolog thing to do.
And my original point was not what it's possible to do with a
language (theoretically, anything if it's turing-equivalent), but what's
natural (or easy) to do with it.
['sci.math' dropped from Newsgroups: ]
--
John Bayko (Tau).
·····@cs.uregina.ca
http://www.cs.uregina.ca/~bayko
From: Norman Bullen
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <3436FE0D.6113@ix.netcom.com>
pcm wrote:
>
> With regards to programming language elegance, it should be worthwhile to
> take a look at what has emerged from research in Algorithmic Information
> Theory and Complexity.
>
> I found this definition by G. J. Chaitin;
>
> " Call a program ``elegant'' if no smaller program has the same output.
> I.e., a LISP S-expression is defined to be elegant if no smaller
> S-expression has the same value. For any computational task there is at
> least one elegant program, perhaps more. Nevertheless, we present a Berry
> paradox proof that it is impossible to prove that any particular large
> program is elegant. The proof is carried out using a version of LISP
> designed especially for this purpose. This establishes an extremely
> concrete and fundamental limitation on the power of formal mathematical
> reasoning. "
< snipped >
Does this mean that we can make programs more elegant by minimizing the
length of variable names and eliminating white space? ;>)
Norm
Norman Bullen <·······@ix.netcom.com> wrote in article
<·············@ix.netcom.com>...
> pcm wrote:
> >
> > With regards to programming language elegance, it should be worthwhile
to
> > take a look at what has emerged from research in Algorithmic
Information
> > Theory and Complexity.
> >
> > I found this definition by G. J. Chaitin;
> >
> > " Call a program ``elegant'' if no smaller program has the same output.
>
> < snipped >
>
> Does this mean that we can make programs more elegant by minimizing the
> length of variable names and eliminating white space? ;>)
>
Not to mention eliminating comments and cramming multiple lines of code
onto a single line.
When I was taking me first programming class in high school we had to write
a simple High-Low guessing game. I did a 2-D "video" game complete with
real chinzy text graphics. The print out was about 5 pages long, mostly due
to comments. It ran really slow on the interpreter we had and so I spent
time over the next couple of months to condense it down as much as I could.
I eventually had the code so that the print out was half a page long plus
another half a page for the instructions for the player that it printed out
at the beginning of the program. It ran a lot faster. A few months later I
was asked to modify the code by the instructor so that he could use it as a
demo for new students. I spent several days trying to figure out how the
damn code worked (remember, I was brand new to programming) and finally
gave up and went back to an older version that was about two pages long.
Within an hour I had it modified and running. Out of curiosity we ran some
tests to see how much faster the two page program was compared to the
half-page program. The two page program was noticeably faster because it
used single print statements to draw the screen boarders and labels while
the short program used for-next loops to do it one character at a time. I
came back a year later and further modified the code and was able to do it
with no trouble because the two-page program had enough comments and
meaningful enough variable names that I could figure out immediately what
was going on.
There may be value in defining a term that means the shortest possible
program that has the same output. And some would argue that it doesn't
matter what we call it since the meaning is established by the definition.
But I would argue that a word such as "elegant" is an inappropriate choice
because it has denotations and connotations in everyday usage that are not
consistent with this definition. I would recommend a word such as "terse"
being used to describe such a program.
Even still, what does "smallest program" mean? How do you decide which of
two similar programs is the smaller?
Norman Bullen <·······@ix.netcom.com> writes:
>Does this mean that we can make programs more elegant by minimizing the
>length of variable names and eliminating white space? ;>)
The papers are very easy to fetch by FTP. You could have found out.
The answer is NO. The question is about the number of bits it takes
to encode an algorithm. Layout, comments, and identifier spelling are not
relevant. Think "after compression", very roughly.
--
John �neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
From: Michael Tiomkin
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <34375D5B.7E9C@iil.intel.com>
pcm wrote:
>
> With regards to programming language elegance, it should be worthwhile to
> take a look at what has emerged from research in Algorithmic Information
> Theory and Complexity.
>
> I found this definition by G. J. Chaitin;
>
> " Call a program ``elegant'' if no smaller program has the same output.
> I.e., a LISP S-expression is defined to be elegant if no smaller
> S-expression has the same value. For any computational task there is at
> least one elegant program, perhaps more. Nevertheless, we present a Berry
> paradox proof that it is impossible to prove that any particular large
> program is elegant. The proof is carried out using a version of LISP
> designed especially for this purpose. This establishes an extremely
> concrete and fundamental limitation on the power of formal mathematical
> reasoning. "
>
> The full article is at:
> http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.html
>
> and a lot more stuff at his page at The Centre for Discrete Mathematics and
> Theoretical Computer Science;
> http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
>
> ........
> ------------
This seems to be the definition of Kolmogoroff complexity. It's a
well known fact that you cannot always find the minimal program: a
simple diagonal argument will do the work.
Good luck!
Michael
pcm (···@mira.net) wrote:
: With regards to programming language elegance, it should be worthwhile to
: take a look at what has emerged from research in Algorithmic Information
: Theory and Complexity.
: I found this definition by G. J. Chaitin;
: " Call a program ``elegant'' if no smaller program has the same output.
When I write a program, I try to make it reliable, understandable,
maintainable, documentable, extendable, debuggable, and efficient.
These things may take on different priorities in different programs.
If a program I write is also "elegant" - in whatever sense - then
perhaps that results from doing the other things well.
-- Wetboy
From: Jeffrey B. Siegal
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <3437F8C2.BDD80962@quiotix.com>
You've missed the point. When a mathematician says:
Call a program ``elegant'' if no smaller program has the same output
he doesn't mean that he think that small programs are elegant, he is just using
the term elegant to describe a particular property of programs prior to then
continuing on to prove interesting properties of 'elegant' programs.
pcm <···@mira.net> wrote in article <··························@pc1>...
> With regards to programming language elegance, it should be worthwhile to
> take a look at what has emerged from research in Algorithmic Information
> Theory and Complexity.
>
> I found this definition by G. J. Chaitin;
>
> " Call a program ``elegant'' if no smaller program has the same output.
> I.e., a LISP S-expression is defined to be elegant if no smaller
> S-expression has the same value. For any computational task there is at
> least one elegant program, perhaps more. Nevertheless, we present a Berry
> paradox proof that it is impossible to prove that any particular large
> program is elegant. The proof is carried out using a version of LISP
> designed especially for this purpose. This establishes an extremely
> concrete and fundamental limitation on the power of formal mathematical
> reasoning. "
But what is meant by a "smaller program"? The number of lines of code? The
number of distinct instructions in the executable? The size of the
executable file? Does execution speed not count at all? Is a brute force
sin() algorithm that's short more elegant than a slightly longer program
that utilizes symmetry in the definition to speed convergence?
"William L. Bahn" <····@pcisys.net> writes:
>pcm <···@mira.net> wrote in article <··························@pc1>...
>> I found this definition by G. J. Chaitin;
>But what is meant by a "smaller program"?
You should have followed up the reference.
Chaitin provides a precise definition of 'smaller':
the number of bits it takes to encode the thing.
>Does execution speed not count at all?
Not when you are talking about SIZE, no.
The same Lisp program whose source form is encoded in N bits
may have a huge number of different executable translations
differing hugely in speed.
(For what it's worth, Chaitin's documents include an interpreter
for his Lisp, written in Mathematica. Fast it's not.)
>Is a brute force
>sin() algorithm that's short more elegant than a slightly longer program
>that utilizes symmetry in the definition to speed convergence?
If it takes fewer bits to encode it, yes, by this definition.
Note that Chaitin set that definition up as _one_ possible spelling
out of the concept precisely in order to show that it is not in general
possible to determine whether a program is `elegant' in that sense.
--
John �neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
From: Chris Bitmead
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <m3yb44uyao.fsf@thepla.net>
"William L. Bahn" <····@pcisys.net> writes:
> But what is meant by a "smaller program"? The number of lines of code? The
> number of distinct instructions in the executable? The size of the
> executable file? Does execution speed not count at all? Is a brute force
> sin() algorithm that's short more elegant than a slightly longer program
> that utilizes symmetry in the definition to speed convergence?
I think we should say using the same basic algorithim.
It seems obvious to me that the definition of an elegant language is
one that has the most powerful abilities for expressing abstractions
and factoring out commonality. And that is why it will lead to smaller
programs and thus shorter algorthms - because you have factored out
more commonality. It is hard to see this looking at the code to one
algorithm. You have to look at a non-trivial program to see how
successful you can be in factoring out commonality.
By this definition COBOL would be one of the least elegant because it
is very difficult to factor commonality. Lisp would be getting pretty
close to perfection in elegance because it gives near perfect ability
to factor commonality. Languages like C would be in the middle to poor
area.
--
Chris Bitmead
http://www.thepla.net/~chrisb
From: Eric W. Nikitin
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <61g80q$6n3$1@nerd.apk.net>
Chris Bitmead (······@thepla.net) wrote:
: It seems obvious to me that the definition of an elegant language is
[snip]
Whenever I see discussions about definitions of terms used in computer
science, I usually like to examine the word in question as it relates
to common english usage. The following is one of the definitions from
the online WWWebster dictionary:
elegance: scientific precision, neatness, and simplicity <the
elegance of a mathematical proof>
where "neatness" means free from irregularity and disorder.
Is there any reason why the use of the word "elegance" should mean
something different when describing a programming language?
Even if you accept this definition, it doesn't make objectively
*measuring* the elegance of a programming language much easier :)
Eric
pcm <···@mira.net> wrote in article
<··························@pc1>...
> With regards to programming language elegance, it should be
worthwhile to
> take a look at what has emerged from research in Algorithmic
Information
> Theory and Complexity.
>
> I found this definition by G. J. Chaitin;
>
> " Call a program ``elegant'' if no smaller program has the
same output.
> I.e., a LISP S-expression is defined to be elegant if no
smaller
> S-expression has the same value. For any computational task
there is at
> least one elegant program, perhaps more. Nevertheless, we
present a Berry
> paradox proof that it is impossible to prove that any
particular large
> program is elegant. The proof is carried out using a version
of LISP
> designed especially for this purpose. This establishes an
extremely
> concrete and fundamental limitation on the power of formal
mathematical
> reasoning. "
Is this intended to be a definition of ``elegance'' for LISP
programs only? In that case, I neither agree or disagree (I
don't care).
If it implies that the true definition of elegance in any
programming situation at all, than in a good many cases (NOT
ALL) the most ``elegant'' possible program will be one written
in assembly language, although there might well be times
(especially on RISC or unusual architectures) when an algorithm
is optimized well enough by a particular compiler (perhaps
FORTRAN and C most likely) when it will beat an average or even
above average assembly language coder.
Frankly, I don't see how one can establish a mathematical
definition of ``elegance'' which is a purely subjective term. I
could tell the story of Romeo and Juliet in a few paragraphs.
Would my version be more elegant than Shakespeare's?
Jack
Jack Klein <·········@worldnet.att.net> wrote in article
<··········@bgtnsc03.worldnet.att.net>...
> pcm <···@mira.net> wrote in article
> <··························@pc1>...
<snip>
> > " Call a program ``elegant'' if no smaller program has the
> same output.
<snip>
> Is this intended to be a definition of ``elegance'' for LISP
> programs only? In that case, I neither agree or disagree (I
> don't care).
>
> If it implies that the true definition of elegance in any
> programming situation at all, than in a good many cases (NOT
> ALL) the most ``elegant'' possible program will be one written
> in assembly language, although there might well be times
> (especially on RISC or unusual architectures) when an algorithm
> is optimized well enough by a particular compiler (perhaps
> FORTRAN and C most likely) when it will beat an average or even
> above average assembly language coder.
>
> Frankly, I don't see how one can establish a mathematical
> definition of ``elegance'' which is a purely subjective term. I
> could tell the story of Romeo and Juliet in a few paragraphs.
> Would my version be more elegant than Shakespeare's?
And this gets right to my point that even though someone might define the
term "elegant" very narrowly in a computer programming sense, you cannot
escape the fact that people will interpret the meaning in terms of what
"elegant" means in everyday usage. The conversations taking place in this
thread would be very different if the author had used the word "terse" to
describe the shortest possible program.
In article <··························@pc1>, ···@mira.net wrote:
| I found this definition by G. J. Chaitin:
| " Call a program ``elegant'' if no smaller program has the same output.
So I see that even after all these years, TECO and APL are still the most
elegant languages.
Yay.
bc
Dammit, where's Visual Object Teco when you need it?
(remembers someone "proving mathematically" that the ultimate musical band
was RUSH)
In article <···················@17.127.19.93>,
··@wetware.com (Bill Coderre) wrote:
>In article <··························@pc1>, ···@mira.net wrote:
>| I found this definition by G. J. Chaitin:
>| " Call a program ``elegant'' if no smaller program has the same output.
>
>So I see that even after all these years, TECO and APL are still the most
>elegant languages.
>
>Yay.
>
>bc
Surely, any definition of elegance for a programming language would include
readability. I am not familiar with TECO but APL does NOT satisfy that
requirement!
>Dammit, where's Visual Object Teco when you need it?
>
>(remembers someone "proving mathematically" that the ultimate musical band
>was RUSH)
If somebody did this then it confirms why I gave up doing mathematics! This
is one Canadian who can't abide RUSH.
From: Colin Dooley
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <343EDAAE.794B@medit3d.com>
Peter Davies wrote:
>
> Surely, any definition of elegance for a programming language would include
> readability.
>
You mean like in COBOL?
--
<\___/> | For the spooks: plutonium semtex CIA MI5 FBI
/ O O \ | Clinton Khadaffi Hussein stealth fighter
\_____/ FTB. | soviet suitcase bomb warhead cryptography
I was grumpy, but now I see the light!
Yes. For its defined problem domain COBOL was for years the most
elegant language.
Jim Rogers
Colorado Springs, Colorado
Colin Dooley <·····@medit3d.com> wrote in article
<·············@medit3d.com>...
> Peter Davies wrote:
> >
> > Surely, any definition of elegance for a programming language would
include
> > readability.
> >
>
> You mean like in COBOL?
Hello!
Colin Dooley <·····@medit3d.com> writes:
> Peter Davies wrote:
> >
> > Surely, any definition of elegance for a programming language would include
> > readability.
>
> You mean like in COBOL?
How about: Unlike APL (or INTERCAL 8-)?
SCNR
Clemens
-----------------------------------------------------------------------------
When there is useful information which [your] ·······@lili.uni-bielefeld.de
program can send to the terminal but not get Clemens Meier
at itself, your customers start to say very GO C++ 3$ UL L+>+++ E++>+++ P-
unkindly things about you. R.A.O'Keefe N++ R+>+++ G'''' b++ TWERPS+++
pcm wrote:
>
> With regards to programming language elegance, it should be worthwhile to
> take a look at what has emerged from research in Algorithmic Information
> Theory and Complexity.
>
> I found this definition by G. J. Chaitin;
>
> " Call a program ``elegant'' if no smaller program has the same output.
[...]
Well, I wouldn't let this go as definition of elegance.
Look at the following programs:
Basic version:
int main()
{
int i;
for(i=0; i<100; i++)
printf("%i\n",i);
return 0;
Shorter (more elegant?) version:
int main()
{
int i;
for(i=0; i<100; printf("%i\n",i++));
return 0;
}
Even shorter (most elegant?):
int main()
{
int i=0;
while(printf("%i\n",i++), i<100);
return 0;
}
BTW, does the return value count as output?
Else it would be more elegant to omit return 0; completely...
From: Robert White
Subject: Re: A Formal Definition of LANGUAGE ELEGANCE
Date:
Message-ID: <34455661.31550E0D@pobox.com>
Christopher Eltschka wrote:
> int main()
> {
> int i=0;
> while(printf("%i\n",i++), i<100);
> return 0;
> }
>
> BTW, does the return value count as output?
> Else it would be more elegant to omit return 0; completely...
void main() {for(int i=0;printf("%i\n",i++);i<100);}
Smaller? Yes
Same Output? Yes, main with return type void returns 0 to invoking environment
More Ellegant? Matter of opinion, the symantics and readability suck.
"Here's mud in your watter",
Rob.
In article <·················@pobox.com>,
Robert White <·······················@pobox.com> wrote:
>void main() {for(int i=0;printf("%i\n",i++);i<100);}
>
>Smaller? Yes
>Same Output? Yes, main with return type void returns 0 to invoking environment
Certainly, that is one possible consequence of undefined behavior. My system,
on the other hand, gives off smoke when you write nonsense like that.
--