Cellular automata benchmarks: Java vs C++ vs Java vs C++

19 views
Skip to first unread message

Shinji Ikari

unread,
Jul 23, 2003, 1:33:27 AM7/23/03
to
Learn Scheme next.

Learning Java is equivalent to studying for a job in McDonalds. Its
targetted towards the great mass of average developers with limited
discipline and minimal programming abilities.

Learning C++ is equivalent to studying to be a NASA test pilot. Its
incredibly fast and effective, but takes years to master the arcania
and things tend to blowup in your face if you're not very careful.

Learning Fortran is like studying Cobol with some math electives.

Learning Scheme is like studying theoretical physics. Its the path
that may lead you to discover the true nature of things.


otis...@aol.com (Otismo47) wrote in message news:<20030721215430...@mb-m02.aol.com>...
> >Java vs C++ vs Java vs C++
>
> Here am I trying to learn Basic & Visual Basic 5 (a beginner).
>
> I have always known that I shud either learn C++ or JAVA next, but
>
> After reading thru this message thread,
> I am as confused as ever !!!
>
> (or maybe I shud learn FORTRAN next??)
>
> Thanks a lot, guys !!!
>
> Peace !!!
>
> Otis

Derk Gwen

unread,
Jul 23, 2003, 2:40:54 AM7/23/03
to
shi...@swirve.com (Shinji Ikari) wrote:

# Learning C++ is equivalent to studying to be a NASA test pilot. Its

Or to pilot an Evangelion?

--
Derk Gwen http://derkgwen.250free.com/html/index.html
Where do you get those wonderful toys?

Matthias Blume

unread,
Jul 23, 2003, 10:43:38 AM7/23/03
to
shi...@swirve.com (Shinji Ikari) writes:

> Learning C++ is equivalent to studying to be a NASA test pilot. Its
> incredibly fast and effective, but takes years to master the arcania
> and things tend to blowup in your face if you're not very careful.

I would rather compare it to learning how to drive a racecar: yes, it
can be fast. Most people tend to drive it off track right away. Some
people die in it. The skills you acquire by learning it are only
marginally related to what you need in the real world. (In the case
of cars, you learn nothing about traffic rules, defensive driving,
etc.) The activity is (or, in the case of C++, should be) illegal
except in specially marked areas that are protected from the rest of
the world, and of which the rest of the world is protected from. The
activity is also not very useful in practice: the vehicle goes really
fast for only short periods of time. Even very skilled drivers cannot
stop the vehicle from blowing up or falling apart after a few hundred
miles unless extremely expensive maintenance is applied constantly.

<duck>
Matthias

George Maydwell

unread,
Jul 23, 2003, 12:32:50 PM7/23/03
to
On 23 Jul 2003 09:43:38 -0500, Matthias Blume
<matt...@shimizu-blume.com> wrote:

>shi...@swirve.com (Shinji Ikari) writes:
>
>> Learning C++ is equivalent to studying to be a NASA test pilot. Its
>> incredibly fast and effective, but takes years to master the arcania
>> and things tend to blowup in your face if you're not very careful.
>
>I would rather compare it to learning how to drive a racecar: yes, it
>can be fast. Most people tend to drive it off track right away. Some
>people die in it. The skills you acquire by learning it are only
>marginally related to what you need in the real world.

The skills you acquire by learning C++ are only marginally related to
what you need in the real world only if you are bound and determined
to become a COBOL programmer. Writing modular efficient software will
be a real world need so long as there is competition and a software
industry. I've earned a living for almost twenty years by using C and
C++ on large projects for commercial product development. It works.

> (In the case
>of cars, you learn nothing about traffic rules, defensive driving,
>etc.) The activity is (or, in the case of C++, should be) illegal
>except in specially marked areas that are protected from the rest of
>the world, and of which the rest of the world is protected from. The
>activity is also not very useful in practice: the vehicle goes really
>fast for only short periods of time.

In practice, some care about raw speed, whereas others are perfectly
willing to tolerate and inflict slow software upon others, even
painfully slow software. Areas where speed is still important include
spreadsheets, simulations, image manipulation, page layout, non-SQL
database searching (as used in Proteomics), and cellular automata.

In reality the C++ vehicle never ever goes slower than the competion
when driven by a competent driver. It cannot, as the C++ language
started out as a preprocessor which generated C code, and C has little
overhead, being very close to machine language. There is very little
performance overhead in C++, despite it being a high-level language.

> Even very skilled drivers cannot
>stop the vehicle from blowing up or falling apart after a few hundred
>miles unless extremely expensive maintenance is applied constantly.

No. Even the most advanced technologies cannot make poorly architected
software maintenance-free or protect it from programmers who don't
know what they are doing. C++ just happens to be about the only
language successful enough in real life that a book has actually been
written about it: "Large Scale C++ Software Design". The following
Google query doesn't return many non C++ references:

http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software+design

>
><duck>
>Matthias


George Maydwell
--
Modern Cellular Automata: www.collidoscope.com/modernca
Collidoscope Hexagonal Screensaver: www.collidoscope.com

Frank Buss

unread,
Jul 23, 2003, 12:57:20 PM7/23/03
to
geo...@collidoscope.com (George Maydwell) wrote:

> The following
> Google query doesn't return many non C++ references:
>
> http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software
> +design

8th link:

http://lambda.weblogs.com/discuss/msgReader$4764

Erlang is a nice functional language and you can build large scale software
with this programming paradigmen very well. Take a look at the Quicksort
implementation in Haskell at http://www.haskell.org/aboutHaskell.html and
compare this to a C++ implementation.

--
Frank Buß, f...@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

Matthias Blume

unread,
Jul 23, 2003, 3:12:02 PM7/23/03
to
r...@zedat.fu-berlin.de (Stefan Ram) writes:

> Matthias Blume <matt...@shimizu-blume.com> writes:
> >shi...@swirve.com (Shinji Ikari) writes:
> >> Learning C++ is equivalent to studying to be a NASA test pilot. Its
> >> incredibly fast and effective, but takes years to master the arcania
> >> and things tend to blowup in your face if you're not very careful.
> >I would rather compare it to learning how to drive a racecar: yes, it
> >can be fast. Most people tend to drive it off track right away. Some
> >people die in it.
>

> Your words fit well on my web page about the quality
> of C++ as a language for learning. So I have appended
> it to the end with proper attributions, but will remove
> it on your request. The URI of this German language page is
>
> http://purl.net/stefan_ram/pub/c++_lernsprache_de

You are welcome to quote it. (I posted it to netnews, so it is public
already. I meant it as sort of a (long) aphorism. Of course, it is
offensive and extreme, and intentionally so. To be taken with a grain
of salt. But we all know that, don't we? :)

By the way, I cannot access the above URL. I get an "access denied"
error.

Cheers,
Matthias

Matthias Blume

unread,
Jul 23, 2003, 3:34:27 PM7/23/03
to

Someone bit. (I thought someone would.... still ducking for cover... :)

geo...@collidoscope.com (George Maydwell) writes:

> On 23 Jul 2003 09:43:38 -0500, Matthias Blume
> <matt...@shimizu-blume.com> wrote:
>
> >shi...@swirve.com (Shinji Ikari) writes:
> >
> >> Learning C++ is equivalent to studying to be a NASA test pilot. Its
> >> incredibly fast and effective, but takes years to master the arcania
> >> and things tend to blowup in your face if you're not very careful.
> >
> >I would rather compare it to learning how to drive a racecar: yes, it
> >can be fast. Most people tend to drive it off track right away. Some
> >people die in it. The skills you acquire by learning it are only
> >marginally related to what you need in the real world.
>
> The skills you acquire by learning C++ are only marginally related to
> what you need in the real world only if you are bound and determined
> to become a COBOL programmer. Writing modular efficient software will
> be a real world need so long as there is competition and a software
> industry. I've earned a living for almost twenty years by using C and
> C++ on large projects for commercial product development. It works.

You are right of course. The "real world" of today is like the early
days of automobiles where everybody had to be an expert in
double-clutching, half a car mechanic, etc. Nowadays those "bare
metal" machines of the past would have no chance in comparison to
modern, easy-to-drive, and safe vehicles. I expect the same to be
true for programming languages -- 20 years down the road, give or take
10.

>
> > (In the case
> >of cars, you learn nothing about traffic rules, defensive driving,
> >etc.) The activity is (or, in the case of C++, should be) illegal
> >except in specially marked areas that are protected from the rest of
> >the world, and of which the rest of the world is protected from. The
> >activity is also not very useful in practice: the vehicle goes really
> >fast for only short periods of time.
>
> In practice, some care about raw speed, whereas others are perfectly
> willing to tolerate and inflict slow software upon others, even
> painfully slow software. Areas where speed is still important include
> spreadsheets, simulations, image manipulation, page layout, non-SQL
> database searching (as used in Proteomics), and cellular automata.

For none of these is it necessary to use C or C++ to get the speed you
need. In some cases I will argue that C or C++ are going to hold you
back speed-wise. This is going to be more and more true as processor
architectures advance, resulting in a growing gap between the facts
and the assumptions that are inherent in the design of said languages.
Another reason for a speed differential I expect to emerge in the area of
memory management.


> In reality the C++ vehicle never ever goes slower than the competion
> when driven by a competent driver. It cannot, as the C++ language
> started out as a preprocessor which generated C code, and C has little
> overhead, being very close to machine language. There is very little
> performance overhead in C++, despite it being a high-level language.

This is a bogus reason. By the same argument we would still be
programming in assembler today. (Of course, we sometimes are, and
there is a place for C and C++ today, too. It is just not every place
-- and it also should not be "nearly every place".) If a project
gets complex enough, the task of actually hand-optimizing your C or
C++ code so that it matches the high-level languages with today's
sophisticated compilers is simply too hard, too error-prone, and does
not give enough return for the investment.

See, e.g., Doug Bagley's often cited "language shootout" to see for
yourself that C and C++ are by no means heads-and-shoulders above the
competition efficiency-wise.

In reality we will see more and more situations where C or C++ code
does not go slower than the competition simply because it never
manages to go at all, no matter how competent the programmers are. (I
have already seen this happen in real-world industrial projects with
programmers at the helm that by most standards are already considered
super-human when it comes to crafting good code.)

>
> > Even very skilled drivers cannot
> >stop the vehicle from blowing up or falling apart after a few hundred
> >miles unless extremely expensive maintenance is applied constantly.
>
> No. Even the most advanced technologies cannot make poorly architected
> software maintenance-free or protect it from programmers who don't
> know what they are doing.

Nobody said such a thing.

> C++ just happens to be about the only
> language successful enough in real life that a book has actually been
> written about it: "Large Scale C++ Software Design". The following
> Google query doesn't return many non C++ references:
>
> http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software+design

Having a book on some attempt at solving a problem does not mean that
the solution it talks about actually is one, and if it is, that it is
the only one, and certainly not that it is the best. (Being cynical
one could even argue that it might mean the opposite. Hehe, I'm still
ducking... :-)

Cheers,
Matthias

Jeffrey Mark Siskind

unread,
Jul 24, 2003, 1:38:05 AM7/24/03
to
> No. Even the most advanced technologies cannot make poorly architected
> software maintenance-free or protect it from programmers who don't
> know what they are doing. C++ just happens to be about the only
> language successful enough in real life that a book has actually been
> written about it: "Large Scale C++ Software Design". The following
> Google query doesn't return many non C++ references:
>
> http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software+design

The comments that I am about to make pertain to research. Though I
conjecture
that they may also pertain to development.

The programming-language advantages of functional programming as far
as issues
like safety and referential transparency go are well known. I am not
going
to repeat those here. I believe, however, that there is an additional
advantage to functional programming that is extremely important and
often
overlooked.

Researchers often write both papers and programs. Often, writing a
paper helps
foster clean thought that leads to better programs. And often, insight
gained
by writing and running programs helps one formulate and evaluate the
theory in
the paper. This works best---and maybe even only at all---when the
algorithm
in the paper corresponds *exactly* to the algorithm in the program.
Verifying
such correspondence, whether by machine or by inspection, is much
easier when
the surface formulation of the two are similar. By this I mean the
abstract
syntax and the semantics of the two languages, not their concrete
syntax.

A programming language must have at least two characteristics to
support such
surface correspondence to most mathematical notation. First, it must
allow
compositional formulation of expressions that take structured entities
as
arguments and return structured entities as results. In standard
mathematical
notation (both classical and modern), functions of and relations
between
vectors, matrices, tensors, sets, posets, graphs, trees, models,
formulas,
expressions, ... is pervasive. Further, new structures and new
functions and
relations between those structures are regularly defined. Second, it
must have
lambda expressions with lexical scoping of free variables. In standard
mathematical notation, quantification is pervasive:

\forall_{x\in X} \ldots
\exists_{x\in X} \ldots
\sum_{x\in X} \ldots
\prod_{x\in X} \ldots
\int_{x\in X} \ldots
\bigvee_{x\in X} \ldots
\bigwedge_{x\in X} \ldots
\bigcup_{x\in X} \ldots
\bigcap_{x\in X} \ldots
\max_{x\in X} \ldots
\min_{x\in X} \ldots
\argmax_{x\in X} \ldots
\argmin_{x\in X} \ldots
\{f(x)|x\in X\wedge p(x)}

Further, new quantifiers (aka higher-order functions) are regularly
defined.
And use of complex compound quantified expressions with free lexical
variables
is pervasive:

\forall_{x\in X}\exists_{y\in Y} \ldots
\int_0^1\int_0^1 \ldots dy dx

Determining that your code matches your paper is significantly easier
when you
write your code like:

(every (lambda (x) (some (lambda (y) ...) big-y)) big-x)
(integral (lambda (x) (integral (lambda (y) ...) 0.0 1.0)) 0.0 1.0)

Note that I wrote the above in Scheme because that it my personal
preference.
This post is not about Scheme, it is about functional programming. Any
language that supports first-class aggregate data, user-defined
higher-order
procedures, and lambda expressions with lexical scope will do. But
note that
C, C++, and Java will not do.

Also note that using a language that supports functional programming
with
first-class aggregate data, user-defined higher-order procedures, and
lambda
expressions with lexical scope is necessary but not sufficient. You
must further use the correct style when writing programs. If I had
written:

(let outer ((big-x-prime big-x))
(if (null? big-x-prime)
#t
(and (let ((x (first big-x-prime)))
(let inner ((big-y-prime big-y))
(if (null? big-y-prime)
#f
(or (let ((y (first big-y-prime)))
...)
(outer (rest big-y-prime))))))
(outer (rest big-x-prime)))))

instead of:

(every (lambda (x) (some (lambda (y) ...) big-y)) big-x)

it would be much more difficult to ascertain that my code implemented:

\forall_{x\in X}\exists_{y\in Y} \ldots

I have come to believe that, in research, it is really beneficial, and
even
imperative, that corresponding code and documentation have isomorphic
abstract
syntax. I conjecture that, if people really thought about it and
understood
the issues, the same would hold true in industrial software
development.

Marco van de Voort

unread,
Jul 24, 2003, 5:31:27 AM7/24/03
to
In article <bfmgjf$gm4va$1...@uni-berlin.de>, Stefan Ram wrote:

> Matthias Blume <matt...@shimizu-blume.com> writes:
>>shi...@swirve.com (Shinji Ikari) writes:
>>> Learning C++ is equivalent to studying to be a NASA test pilot. Its
>>> incredibly fast and effective, but takes years to master the arcania
>>> and things tend to blowup in your face if you're not very careful.
>>I would rather compare it to learning how to drive a racecar: yes, it
>>can be fast. Most people tend to drive it off track right away. Some
>>people die in it.

Note that more people die in ordinary cars each year, then in race cars.

Moral of the story: ( :-) )
- the professionals are not the ones to worry about
- the non-professionals are the ones that are responsable for the bulk of
the accidents and casualties, regardless of the car type.



> Your words fit well on my web page about the quality
> of C++ as a language for learning. So I have appended
> it to the end with proper attributions, but will remove
> it on your request. The URI of this German language page is

I read it (I'm interested in the subject of language choice from an
educational perspective) Some comments:

- the article reads as an advocacy type meant to put C++ down, maybe it isn't
meant as such, but it feels like it to me.
Some balancing here and there would help. Specifically:

- Try to detail for each paragraph (argument against C++) for which kind of
student (education type and level), Requirements for CS students are
totally different then for managers that want to do some
calculations. This is particularly the case for the memory
management paragraph. I wouldn't want to employ a CS student that
can't handle manual storage allocation, or somebody doing a
electronics course (or CS in the direction of embedded) who
doesn't know anything about internals.

- Try to detail if the argument is mainly a problem for an introductionary
course or in general. (here and there are some references to
beginners) The choices for an introductionary course is totally
different from an advanced course.

- I specially don't like the memory-management paragraph. While manual
management might be undesirable from a productivity and safety
perspective, that is a different discussion. I wouldn't say it is
unsuitable for teaching. (Pascal is quoted in the comments as ideal, and
that is also manually allocated).
In general if you teach a language that has fully automatic allocation,
you often get lazy and ad-hoc programming behaviour of students. If your
group is very small, this is not a problem, but with larger (20-30+)
groups, the effort students put into it decreases, simply because the
manual allocation encourages some self discipline and thinking before
doing.
This is not always the case; As said small groups or also a very precise
specification and proofing system can remedy this. However that kind of
exact thinking is often harder for most categories of students than
manual allocation for simple programs.

---
Something else if you are interested in education and selecting
introductionary languages and courses:

I happen to have had two introductionary courses in my (too) long carriere
as student, and was struck by the differences. One during my chemical
engineering (Master) study (pascal courses in the first year, some numerical
programming in the second year 1992-1994), and one during my CS bachelor (as
a quite experienced programmer meanwhile) this year (2002-2003)

The first was in Turbo Pascal, on the dos commandline. The second Java
(JBuilder and Visual Cafe). Paralel to this we also got a basic (plain) C
course for embedded use, using Visual C++ 6.0, but targeted towards
commandline usage.

While to me, the theoretic level of the C course was harder (creating and
managing double linked lists vs stuffing things in and out of a vector),
the other students' (and me too) perception was that the Java course was
much more difficult and time consuming.

I hadn't expected that, so I talked with the other students about this, and
the difference was caused by several factors:

- The primary factor was GUI<-> text. While most had to be learned to use
the console (and redirecting etc), it was considered easier than even
the very small GUI proportion of the Java demoes (nr of controls
per assignment 2-5, usually even pre-prepared by the teacher)
- The larger amount of basic concepts to be learned (particularly OOP
inheritance was a great hinderance)
- the compactness of the C source made it easier, also the
straightforwardness (the easy to follow sequence of things. Event
driven is more complicated)
- The IDE/RAD. VC++ was used as a GUI editor+ a knob to build. One needed to
know the Java RAD much better to adequately make and debug the
assignments

So in general, it was the larger amount of concepts and knowledge required
to make initial, simple programs.

The Pascal case (Turbo Pascal) at the time went even better, but at that
time all computer users still had a decent dos and cmdline knowledge. That's
much harder nowadays. For teaching, the string handling of TP is a really
big plus over C though IMHO, and Pasca is also much cleaner than C in a lot
of ways.

Using Dev-pascal instead could remedy this (by switching to a GUI editor,
minimizing the cmdline work). I think this is easier than Delphi even, since
the IDE is much simpler, and not geared towards making RAD generated GUI apps.

Hmm, enough ranting for a day :_)

George Maydwell

unread,
Jul 24, 2003, 8:57:58 AM7/24/03
to
On 23 Jul 2003 14:34:27 -0500, Matthias Blume
<matt...@shimizu-blume.com> wrote:

There's no such thing as a safe vehicle. There's no 100% protection
against the stupidity of bad drivers and the accidents they cause.

>
>>
>> > (In the case
>> >of cars, you learn nothing about traffic rules, defensive driving,
>> >etc.) The activity is (or, in the case of C++, should be) illegal
>> >except in specially marked areas that are protected from the rest of
>> >the world, and of which the rest of the world is protected from. The
>> >activity is also not very useful in practice: the vehicle goes really
>> >fast for only short periods of time.
>>
>> In practice, some care about raw speed, whereas others are perfectly
>> willing to tolerate and inflict slow software upon others, even
>> painfully slow software. Areas where speed is still important include
>> spreadsheets, simulations, image manipulation, page layout, non-SQL
>> database searching (as used in Proteomics), and cellular automata.
>
>For none of these is it necessary to use C or C++ to get the speed you
>need.

Then provide even a single example of non-C++ cellular automata
software which provides the speed I need. Your statement is
definitive, where is your proof?

> In some cases I will argue that C or C++ are going to hold you

What C++ knowledge have you displayed and why should others believe
you?

>back speed-wise. This is going to be more and more true as processor
>architectures advance, resulting in a growing gap between the facts
>and the assumptions

You've been following presidential politics.

> that are inherent in the design of said languages.
>Another reason for a speed differential I expect to emerge in the area of
>memory management.

And the basis for your expectations is what? I've seen bottlenecks in
code. I've also seen bottlenecks caused by memory management. Guess
what? It was the result of stupidity! Good programmers avoid memory
management in time critical code.


>
>
>> In reality the C++ vehicle never ever goes slower than the competion
>> when driven by a competent driver. It cannot, as the C++ language
>> started out as a preprocessor which generated C code, and C has little
>> overhead, being very close to machine language. There is very little
>> performance overhead in C++, despite it being a high-level language.
>
>This is a bogus reason.

Lack of performance overhead is a bogus reason for choosing C++? You
are bogus.

>programming in assembler today. (Of course, we sometimes are, and
>there is a place for C and C++ today, too. It is just not every place
>-- and it also should not be "nearly every place".) If a project
>gets complex enough, the task of actually hand-optimizing your C or
>C++ code so that it matches the high-level languages with today's
>sophisticated compilers is simply too hard, too error-prone, and does
>not give enough return for the investment.

What on earth are you talking about here? C++ code written by a
competent programmer doesn't need "hand optimization".

>
>See, e.g., Doug Bagley's often cited "language shootout" to see for
>yourself that C and C++ are by no means heads-and-shoulders above the
>competition efficiency-wise.

What does Doug Bagley know about the efficiency of C/C++ when
implementing fast cellular automata? What does he know about the
efficiency of C++ for simulation purposes? I've seen C++ function
inlining alone easily result in doublings of speed for numerical
calculations. What do other widely used languages do to remain
"head-and-shoulders" with inlined C++ "efficiency-wise"? Can even a
single example be produced?

>
>In reality we will see more and more situations where C or C++ code
>does not go slower than the competition simply because it never
>manages to go at all, no matter how competent the programmers are. (I
>have already seen this happen in real-world industrial projects with
>programmers at the helm that by most standards are already considered
>super-human when it comes to crafting good code.)

And if the "super-human" programmers blamed the project failure on C++
then they are not super-human and in my opinion they are not even
competent. If you've "seen this happen" then you are blind and naive.


>
>>
>> > Even very skilled drivers cannot
>> >stop the vehicle from blowing up or falling apart after a few hundred
>> >miles unless extremely expensive maintenance is applied constantly.
>>
>> No. Even the most advanced technologies cannot make poorly architected
>> software maintenance-free or protect it from programmers who don't
>> know what they are doing.
>
>Nobody said such a thing.
>
>> C++ just happens to be about the only
>> language successful enough in real life that a book has actually been
>> written about it: "Large Scale C++ Software Design". The following
>> Google query doesn't return many non C++ references:
>>
>> http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software+design
>
>Having a book on some attempt at solving a problem does not mean that
>the solution it talks about actually is one,

You are full of it. I wouldn't hire you.

> and if it is, that it is
>the only one, and certainly not that it is the best. (Being cynical
>one could even argue that it might mean the opposite. Hehe, I'm still
>ducking... :-)
>
>Cheers,
>Matthias

Joe Marshall

unread,
Jul 24, 2003, 11:05:11 AM7/24/03
to
geo...@collidoscope.com (George Maydwell) writes:

> There's no such thing as a safe vehicle. There's no 100% protection
> against the stupidity of bad drivers and the accidents they cause.

So therefore we should abandon any and all attempts to make them
safer?

> >> In practice, some care about raw speed, whereas others are perfectly
> >> willing to tolerate and inflict slow software upon others, even
> >> painfully slow software. Areas where speed is still important include
> >> spreadsheets, simulations, image manipulation, page layout, non-SQL
> >> database searching (as used in Proteomics), and cellular automata.
> >
> >For none of these is it necessary to use C or C++ to get the speed you
> >need.
>
> Then provide even a single example of non-C++ cellular automata
> software which provides the speed I need.

What sort of cellular automata software do you need?

> >> In reality the C++ vehicle never ever goes slower than the competion
> >> when driven by a competent driver. It cannot, as the C++ language
> >> started out as a preprocessor which generated C code, and C has little
> >> overhead, being very close to machine language. There is very little
> >> performance overhead in C++, despite it being a high-level language.
> >
> >This is a bogus reason.
>
> Lack of performance overhead is a bogus reason for choosing C++? You
> are bogus.

Hand written assembly code is almost always faster than compiler
written C++. On today's modern processors, you can often gain a
large speedup by taking advantage of the details of the hardware.

C++ introduces performance overhead. One big overhead is the lack of
global register allocation. Another is the cdecl calling conventions.

Since performance is your primary consideration, why aren't you
writing things in assembly code?

> >programming in assembler today. (Of course, we sometimes are, and
> >there is a place for C and C++ today, too. It is just not every place
> >-- and it also should not be "nearly every place".) If a project
> >gets complex enough, the task of actually hand-optimizing your C or
> >C++ code so that it matches the high-level languages with today's
> >sophisticated compilers is simply too hard, too error-prone, and does
> >not give enough return for the investment.
>
> What on earth are you talking about here? C++ code written by a
> competent programmer doesn't need "hand optimization".

Compilers *rarely* produce the highest performing code, even with high
optimization settings.

> >See, e.g., Doug Bagley's often cited "language shootout" to see for
> >yourself that C and C++ are by no means heads-and-shoulders above the
> >competition efficiency-wise.
>
> What does Doug Bagley know about the efficiency of C/C++ when
> implementing fast cellular automata? What does he know about the
> efficiency of C++ for simulation purposes? I've seen C++ function
> inlining alone easily result in doublings of speed for numerical
> calculations. What do other widely used languages do to remain
> "head-and-shoulders" with inlined C++ "efficiency-wise"? Can even a
> single example be produced?

What exactly are you questioning here? It is a fact that C++ code is
not the highest performing language for many problems. It is a fact
that there are simulation problems for which C++ produces inferior
code. I won't deny that C++ can produce code of reasonable
performance for a cellular automaton simulation on stock hardware, but
many languages produce `decent' code that is competitive with C++.

> >In reality we will see more and more situations where C or C++ code
> >does not go slower than the competition simply because it never
> >manages to go at all, no matter how competent the programmers are. (I
> >have already seen this happen in real-world industrial projects with
> >programmers at the helm that by most standards are already considered
> >super-human when it comes to crafting good code.)
>
> And if the "super-human" programmers blamed the project failure on C++
> then they are not super-human and in my opinion they are not even
> competent. If you've "seen this happen" then you are blind and naive.

Obviously you've never `seen this happen'. I have to wonder about
your definition of `blind' then.

Joe Marshall

unread,
Jul 24, 2003, 11:06:28 AM7/24/03
to
Matthias Blume <matt...@shimizu-blume.com> writes:


> You are welcome to quote it. (I posted it to netnews, so it is public
> already. I meant it as sort of a (long) aphorism. Of course, it is
> offensive and extreme, and intentionally so. To be taken with a grain
> of salt. But we all know that, don't we? :)

I found it neither offensive nor extreme. (I did assume it was
intentionally posted.)

George Maydwell

unread,
Jul 24, 2003, 12:43:37 PM7/24/03
to
On 24 Jul 2003 11:05:11 -0400, Joe Marshall <j...@ccs.neu.edu> wrote:

<snip>

>What sort of cellular automata software do you need?

Fast cellular automata. Video (75 - 85 Hz) refresh rates at 1600 by
1200 resolution with support for multiple colors. Eye candy!

>
>> >> In reality the C++ vehicle never ever goes slower than the competion
>> >> when driven by a competent driver. It cannot, as the C++ language
>> >> started out as a preprocessor which generated C code, and C has little
>> >> overhead, being very close to machine language. There is very little
>> >> performance overhead in C++, despite it being a high-level language.
>> >
>> >This is a bogus reason.
>>
>> Lack of performance overhead is a bogus reason for choosing C++? You
>> are bogus.
>
>Hand written assembly code is almost always faster than compiler
>written C++. On today's modern processors, you can often gain a
>large speedup by taking advantage of the details of the hardware.

Hand written assembler for my cellular automata was only about 8%
faster than C++ for my cellular automata. This is not a large speedup.

>
>C++ introduces performance overhead. One big overhead is the lack of
>global register allocation. Another is the cdecl calling conventions.

Global register allocation won't make my cellular automata go any
faster. Calling overhead is negligible in well written cellular
automata software. The overhead of C++ is not what you appear to be
trying to lead others to believe.

>
>Since performance is your primary consideration, why aren't you
>writing things in assembly code?

Because as mentioned above I've actually measured assembler to be only
8% faster for my application. You can look at my sixteen lines of C++
code here:
http://www.collidoscope.com/ca/arca.html#Code_For_ARCAL
and perhaps get an idea as to why assembler is not much faster than
C++ for my task. You can perhaps also get an idea of why Java with its
very expensive (for cellular automata) subscript checking is hopeless
performance-wise for the algorithm used in the C++ code.

>
>> >programming in assembler today. (Of course, we sometimes are, and
>> >there is a place for C and C++ today, too. It is just not every place
>> >-- and it also should not be "nearly every place".) If a project
>> >gets complex enough, the task of actually hand-optimizing your C or
>> >C++ code so that it matches the high-level languages with today's
>> >sophisticated compilers is simply too hard, too error-prone, and does
>> >not give enough return for the investment.
>>
>> What on earth are you talking about here? C++ code written by a
>> competent programmer doesn't need "hand optimization".
>
>Compilers *rarely* produce the highest performing code, even with high
>optimization settings.

Wrong. For any given application there will be one high-level language
compiler which produces the highest performing code for a specific
machine. I'm comparing high level languages to each other, not to
assembly language. C++ wins hands down for my applications.

>
>> >See, e.g., Doug Bagley's often cited "language shootout" to see for
>> >yourself that C and C++ are by no means heads-and-shoulders above the
>> >competition efficiency-wise.
>>
>> What does Doug Bagley know about the efficiency of C/C++ when
>> implementing fast cellular automata? What does he know about the
>> efficiency of C++ for simulation purposes? I've seen C++ function
>> inlining alone easily result in doublings of speed for numerical
>> calculations. What do other widely used languages do to remain
>> "head-and-shoulders" with inlined C++ "efficiency-wise"? Can even a
>> single example be produced?
>
>What exactly are you questioning here?

I'm questioning the validity of any performance comparison between
high level languages which ignores C++ function inlining and the very
real performance increases which this one feature alone can be
responsible for in time-critical code.

> It is a fact that C++ code is
>not the highest performing language for many problems. It is a fact
>that there are simulation problems for which C++ produces inferior
>code. I won't deny that C++ can produce code of reasonable
>performance for a cellular automaton simulation on stock hardware, but
>many languages produce `decent' code that is competitive with C++.

Where are these languages? I'd like to see someone rewrite my sixteen
lines of C++ code in another language! Go for it and prove your point.

>
>> >In reality we will see more and more situations where C or C++ code
>> >does not go slower than the competition simply because it never
>> >manages to go at all, no matter how competent the programmers are. (I
>> >have already seen this happen in real-world industrial projects with
>> >programmers at the helm that by most standards are already considered
>> >super-human when it comes to crafting good code.)
>>
>> And if the "super-human" programmers blamed the project failure on C++
>> then they are not super-human and in my opinion they are not even
>> competent. If you've "seen this happen" then you are blind and naive.
>
>Obviously you've never `seen this happen'. I have to wonder about
>your definition of `blind' then.

C++ projects don't fail because of programming language issues. A
blind person is perhaps less able to discern cause and effect than a
sighted person.

I can't help it if most projects I've worked on have succeeded and
shipped! I've seen exactly one case where language performance
problems doomed a project and in that case C++ was not the language
used for the project.

I'd be far more inclined to believe your side if you could provide an
example of a large-scale project which failed so miserably when C++
was used that another language was switched to which "saved the day".
Otherwise failed C++ projects prove nothing.

Matthias Blume

unread,
Jul 24, 2003, 2:07:14 PM7/24/03
to
Marco van de Voort <mar...@toad.stack.nl> writes:

> In article <bfmgjf$gm4va$1...@uni-berlin.de>, Stefan Ram wrote:
> > Matthias Blume <matt...@shimizu-blume.com> writes:
> >>shi...@swirve.com (Shinji Ikari) writes:
> >>> Learning C++ is equivalent to studying to be a NASA test pilot. Its
> >>> incredibly fast and effective, but takes years to master the arcania
> >>> and things tend to blowup in your face if you're not very careful.
> >>I would rather compare it to learning how to drive a racecar: yes, it
> >>can be fast. Most people tend to drive it off track right away. Some
> >>people die in it.
>
> Note that more people die in ordinary cars each year, then in race cars.
>
> Moral of the story: ( :-) )

The moral of the story, obviously, is that you have to look at the
ratio. Just ask your favorite insurance agent, i.e., try to get life
insurance for yourself and say that you do car racing. See what
happens...

> - the professionals are not the ones to worry about

Right, if people want to race cars or write C++ code, fine -- as long
as they do so in confined areas that do not affect my own lifelihood.

> - the non-professionals are the ones that are responsable for the bulk of
> the accidents and casualties, regardless of the car type.

That's not "regardless of car type". Hardly any non-professionals
drive race cars (by definition), so the comparison just does not hold.
It is testimony to the safety of ordinary cars that so many
non-professionals can drive them *without* getting killed. (Mind you,
I do think that still too many get killed, and that, in fact, way too
many people drive. I wish people would use public transportation
more, especially in this country. Although this gets way off topic
now, there might be a PL analogy in it, too.)

Matthias

Matthias Blume

unread,
Jul 24, 2003, 2:11:01 PM7/24/03
to
geo...@collidoscope.com (George Maydwell) writes:

[ lots of ad-hominems snipped ]

> You are full of it. I wouldn't hire you.

Who said I would want to work for you?

Matthias

Matthias Blume

unread,
Jul 24, 2003, 2:13:06 PM7/24/03
to
Joe Marshall <j...@ccs.neu.edu> writes:

Thanks. (I did post things more offensive and more extreme in the
past. I guess I'm mellowing...:-)

Matthias

Matthias Blume

unread,
Jul 24, 2003, 2:33:46 PM7/24/03
to
geo...@collidoscope.com (George Maydwell) writes:

> Wrong. For any given application there will be one high-level language
> compiler which produces the highest performing code for a specific
> machine. I'm comparing high level languages to each other, not to
> assembly language. C++ wins hands down for my applications.

How many (and, more importantly, which) "high-level languages" did you
try?

> >What exactly are you questioning here?
>
> I'm questioning the validity of any performance comparison between
> high level languages which ignores C++ function inlining and the very
> real performance increases which this one feature alone can be
> responsible for in time-critical code.

How did you get the idea that I am ignoring some particular feature of
C++? I have not even said which high-level language I compare C++ to.
(Hint: if I had to be specific, I would *not* choose Java.)

> C++ projects don't fail because of programming language issues. A
> blind person is perhaps less able to discern cause and effect than a
> sighted person.
>
> I can't help it if most projects I've worked on have succeeded and
> shipped! I've seen exactly one case where language performance
> problems doomed a project and in that case C++ was not the language
> used for the project.

I can easily believe that 16-liners can be written, debugged, and
shipped successfully in C++. They will even be fast, and it would be
hard to outright beat them using any other language. I am not talking
about projects failing because of not meeting some speed goals. I am
talking about (large!) projects failing because of their complexity
exceeding the managerial capabilities of the people involved. C++ is
not the best tool for managing complexity in software. In fact, I
think it compounds the problem by being overly complex in itself, and
by failing to adequately address some of the most common issues that
lead to complexity in large programs. (Again, memory management comes
to mind.)

> I'd be far more inclined to believe your side if you could provide an
> example of a large-scale project which failed so miserably when C++
> was used that another language was switched to which "saved the day".
> Otherwise failed C++ projects prove nothing.

This is obviously hard to do these days, given programmer education
and mentality, management structure of today's companies that engage
in such projects, and the fact that once the original project has
failed it is often to late to steer the ship out of the mess, so no
other toolset could possibly save the day. And, needless to say, the
toolset alone is rarely, if ever, the sole reason for failure or
success. To me, however, it seems that projects that succeed with C++
don't do this because of the language but rather in spite of it.

OTOH, there are definitely projects (and companies) that have failed
after switching *to* C++, *away* from their original language.
Whether or not this is due to the choice of C++ is, of course, not
provable, so I won't try.

Matthias

Anton van Straaten

unread,
Jul 25, 2003, 12:39:08 AM7/25/03
to
George Maydwell wrote:
> C++ just happens to be about the only
> language successful enough in real life that a book has actually been
> written about it: "Large Scale C++ Software Design". The following
> Google query doesn't return many non C++ references:
>
>
http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software+desi
gn

This is an example of that common logical error, "argument by book title"
(known formally as "modus titulus liber libri", iirc). These Google results
are dominated by the title of a single book, which "happen" to be the exact
words used in this query. This proves that... well, Google's output is
dependent on its input. A startling result indeed.

Here's a better query:
http://www.google.com/search?q=large+scale+software+design+-%22Large-Scale+C
%2B%2B+Software+Design%22

Along these lines, to demonstrate beyond all doubt which language is best,
try the following searches:

http://www.google.com/search?q=java - 32,700,000 results for Java
http://www.google.com/search?q=scheme - 10,300,000 results for Scheme
http://www.google.com/search?q=C%2B%2B - 7,820,000 results for C++
http://www.google.com/search?q=C%23 - 2,080,000 results for C#

This "argumentum googlum" demonstrates beyond any doubt that Java is the
most popular language, followed by Scheme. C++ is struggling along behind,
and C# is only being used, judging by the numbers, at subsidiaries of
Microsoft.

Anton

gr...@cs.uwa.edu.au

unread,
Jul 25, 2003, 12:52:08 AM7/25/03
to
In comp.lang.misc George Maydwell <geo...@collidoscope.com> wrote:
: C++ just happens to be about the only language successful enough

: in real life that a book has actually been written about it:
: "Large Scale C++ Software Design".

But surely C++ can't be responsible for _all_ the problems in
large scale software design, can it?

-Greg

felix

unread,
Jul 25, 2003, 1:42:05 AM7/25/03
to
geo...@collidoscope.com (George Maydwell) wrote in message news:<3f2501a7...@news.prodigy.net>...

>
> I'd be far more inclined to believe your side if you could provide an
> example of a large-scale project which failed so miserably when C++
> was used that another language was switched to which "saved the day".
> Otherwise failed C++ projects prove nothing.
>

This one is interesting:

http://www.research.avayalabs.com/user/wadler/armstrong.ps


cheers,
felix

Marco Gidde

unread,
Jul 25, 2003, 2:49:20 AM7/25/03
to
geo...@collidoscope.com (George Maydwell) writes:

> On 24 Jul 2003 11:05:11 -0400, Joe Marshall <j...@ccs.neu.edu> wrote:
>
> >Since performance is your primary consideration, why aren't you
> >writing things in assembly code?
>
> Because as mentioned above I've actually measured assembler to be only
> 8% faster for my application. You can look at my sixteen lines of C++
> code here:
> http://www.collidoscope.com/ca/arca.html#Code_For_ARCAL
> and perhaps get an idea as to why assembler is not much faster than
> C++ for my task. You can perhaps also get an idea of why Java with its
> very expensive (for cellular automata) subscript checking is hopeless
> performance-wise for the algorithm used in the C++ code.

You are writing about C++ and high level languages and give this
snippet as an example? You shouldn't call something C++ that is in
fact lowest level C.

David Rush

unread,
Jul 25, 2003, 5:07:50 AM7/25/03
to
geo...@collidoscope.com (George Maydwell) writes:

> On 23 Jul 2003 14:34:27 -0500, Matthias Blume wrote:
> >Someone bit. (I thought someone would.... still ducking for cover... :)

Yup. Dunno why I'm sticking my head up, either :)

> >geo...@collidoscope.com (George Maydwell) writes:
> >> On 23 Jul 2003 09:43:38 -0500, Matthias Blume
> >> <matt...@shimizu-blume.com> wrote:
> >> >shi...@swirve.com (Shinji Ikari) writes:
> >> >
> >> >> Learning C++ is equivalent to studying to be a NASA test pilot.

> >> >I would rather compare it to learning how to drive a racecar:

> Then provide even a single example of non-C++ cellular automata


> software which provides the speed I need. Your statement is
> definitive, where is your proof?

Sorry, your argument has only recently been cross-posted into
comp.lang.scheme. What are your requirements? I would be surprised to
find that Stalin couldn't beat your performance (at least on *nix
systems)

david rush
--
He who would make his own liberty secure, must guard even his enemy
from repression
-- Thomas Paine

David Rush

unread,
Jul 25, 2003, 5:22:05 AM7/25/03
to
geo...@collidoscope.com (George Maydwell) writes:

> On 23 Jul 2003 14:34:27 -0500, Matthias Blume wrote:
> >geo...@collidoscope.com (George Maydwell) writes:
> >> On 23 Jul 2003 09:43:38 -0500, Matthias Blume wrote:
> >> >shi...@swirve.com (Shinji Ikari) writes:

> What on earth are you talking about here? C++ code written by a
> competent programmer doesn't need "hand optimization".

Sorry, but programming in C/C++ involves *tons* of what amounts to
hand-optimization. Most C/C++ programmers either don't notice it
(because they don't know any better) or simply write inefficient
code. Since you profess to care about performance I'll assume that you
are in the former camp.

As a simple example, every time you invoke a memory allocation
operator, you are hand optimizing the run-time system.

> What does Doug Bagley know about the efficiency of C/C++ when
> implementing fast cellular automata?

Why don't you propose a CA problem for the shootout page then that
will show the difference?

> >In reality we will see more and more situations where C or C++ code
> >does not go slower than the competition simply because it never
> >manages to go at all, no matter how competent the programmers are. (I
> >have already seen this happen in real-world industrial projects with
> >programmers at the helm that by most standards are already considered
> >super-human when it comes to crafting good code.)
>
> And if the "super-human" programmers blamed the project failure on C++
> then they are not super-human and in my opinion they are not even
> competent. If you've "seen this happen" then you are blind and naive.

Sorry to be citing myself, but I made my comments to this sort of
argument in the following article:

http://groups.google.com/groups?selm=okf4rax3s52.fsf%40bellsouth.net

> You are full of it. I wouldn't hire you.

Your loss then. Matthias is a very clever person. You would do well to
do some background research on people before you start in with
personal attacks. Especially when they were obviously just trolling...

George Maydwell

unread,
Jul 25, 2003, 8:33:10 AM7/25/03
to
On 25 Jul 2003 08:49:20 +0200, Marco Gidde <mgid...@tiscali.de>
wrote:

I was specifically asked why I wasn't writing in assembly language.

> You shouldn't call something C++ that is in
>fact lowest level C.

Why not? The C++ compiler didn't complain about it. The C++ language
didn't stop me from writing code which also happens to be legal C. Nor
did it stop me from writing code which approaches the speed of
assembler.

With the exception of inlining it is perhaps unreasonable to expect to
see C++ specific language features utilized in the inner loop of fast
cellular automata software which is essentially nothing but table
lookups.

George Maydwell

unread,
Jul 25, 2003, 9:43:24 AM7/25/03
to
On Fri, 25 Jul 2003 09:07:50 +0000 (UTC), David Rush <dr...@aol.net>
wrote:

>geo...@collidoscope.com (George Maydwell) writes:
>> On 23 Jul 2003 14:34:27 -0500, Matthias Blume wrote:
>> >Someone bit. (I thought someone would.... still ducking for cover... :)
>
>Yup. Dunno why I'm sticking my head up, either :)
>
>> >geo...@collidoscope.com (George Maydwell) writes:
>> >> On 23 Jul 2003 09:43:38 -0500, Matthias Blume
>> >> <matt...@shimizu-blume.com> wrote:
>> >> >shi...@swirve.com (Shinji Ikari) writes:
>> >> >
>> >> >> Learning C++ is equivalent to studying to be a NASA test pilot.
>> >> >I would rather compare it to learning how to drive a racecar:
>
>> Then provide even a single example of non-C++ cellular automata
>> software which provides the speed I need. Your statement is
>> definitive, where is your proof?
>
>Sorry, your argument has only recently been cross-posted into
>comp.lang.scheme. What are your requirements? I would be surprised to
>find that Stalin couldn't beat your performance (at least on *nix
>systems)

Fast cellular automata. Video (75 - 85 Hz) refresh rates at 1600 by
1200 resolution with support for multiple colors. Eye candy! I can't
think of a better real world application for cellular automata.

I trimmed the newsgroups. I must have missed whatever justification
there was for adding comp.lang.scheme to a discussion of cellular
automata benchmarks. But in case you are interested here is a url of a
page with benchmark results which indicate to me that these speeds are
attainable with Java software, needing only a quality JIT compiler:
http://www.collidoscope.com/modernca/briansbench.html

>
>david rush

Joe Marshall

unread,
Jul 25, 2003, 10:27:59 AM7/25/03
to
geo...@collidoscope.com (George Maydwell) writes:

> Because as mentioned above I've actually measured assembler to be only
> 8% faster for my application. You can look at my sixteen lines of C++
> code here:
> http://www.collidoscope.com/ca/arca.html#Code_For_ARCAL
> and perhaps get an idea as to why assembler is not much faster than
> C++ for my task.

> Global register allocation won't make my cellular automata go any
> faster. Calling overhead is negligible in well written cellular
> automata software. The overhead of C++ is not what you appear to be
> trying to lead others to believe.

I've looked at the code and the inner loop is quite tight.
Nonetheless you can do better. You have encountered both the global
register allocation problem and the calling overhead in C, but you
have created a workaround by squishing everything into a single
function.

Your inner loop runs a little interpreter. You step through each cell
in turn and examine its state. Depending on the state of the cell,
you update the state of the neighboring cells.

Now let's consider what the processor is doing. It, like the cells,
is a finite state machine. It, like the cells, is changing state
based on a table of instructions in memory. However, its state
transitions are handled efficiently by hardware where your state
transitions are computed. If you could create an isomorphism between
the processor state and the cell state, you could co-opt the hardware
into directly emulating each cell.

The `liveMap' and the `deadMap' are essentially subroutines that
transmit the current state of the cell to the neighboring cells. Why
aren't they implemented in that manner? Rather than stepping through
a little table, you could have an inline routine. The routine would,
of course, be unrolled, thus avoiding the loop overhead in
interpretation. The loads and stores in the routine could be
re-ordered to take advantage of the deep pipeline. Finally, the
instruction fetch cycle and the `liveMap' or `deadMap' lookup cycle
would not be two separate memory cycles, but a single one that was
optimized for linear interpretation.

The inner loop of your routine would no longer be
do {
unsigned char* neighborAddr = curr + *inst++;
unsigned char* transition = (unsigned char*) *inst++;
*neighborAddr = transition[*neighborAddr];
}
while (inst[0]);

but rather
(*curr)();

The reason you don't do it this way is obvious: it would kill the
performance. For each cell you would have to save the current
function state, build a new stack frame, indirect call, return, and
restore the state.

This is the overhead involved with cdecl function calls and lack of
global register allocation. If the call were simply an indirect call,
with no change of registers and no stack frame, the callee (the cell
transition routine) could make use of the cell's own index (the
pointer to CURR) which would be kept in a register. You could even
avoid the overhead of pushing and popping return addresses by
introducing an `end of frame' state. Now each cell could tail-call
(i.e., jump to) the state transition function of the next.

This is not the sort of thing that is trivial to do in C, but possible
in assembly code.

> >> What does Doug Bagley know about the efficiency of C/C++ when
> >> implementing fast cellular automata? What does he know about the
> >> efficiency of C++ for simulation purposes? I've seen C++ function
> >> inlining alone easily result in doublings of speed for numerical
> >> calculations. What do other widely used languages do to remain
> >> "head-and-shoulders" with inlined C++ "efficiency-wise"? Can even a
> >> single example be produced?
> >
> >What exactly are you questioning here?
>
> I'm questioning the validity of any performance comparison between
> high level languages which ignores C++ function inlining and the very
> real performance increases which this one feature alone can be
> responsible for in time-critical code.

C++ is not the only language with function inlining.

Note that if function inlining gives `very real performance
increases', then how could it be that `calling overhead is
negligable'?

> > It is a fact that C++ code is
> >not the highest performing language for many problems. It is a fact
> >that there are simulation problems for which C++ produces inferior
> >code. I won't deny that C++ can produce code of reasonable
> >performance for a cellular automaton simulation on stock hardware, but
> >many languages produce `decent' code that is competitive with C++.
>
> Where are these languages? I'd like to see someone rewrite my sixteen
> lines of C++ code in another language! Go for it and prove your point.

I've outlined my approach above. I'd go further and design a compiler
that would generate the appropriate subroutines. But that's not where
my interests lie.

> I'd be far more inclined to believe your side if you could provide an
> example of a large-scale project which failed so miserably when C++
> was used that another language was switched to which "saved the day".
> Otherwise failed C++ projects prove nothing.

TRUE Software's `TrueChange 4.0' never got anywhere because the C++
got far too hairy. When implemented in CLOS, however, we were up and
running in a year.

George Maydwell

unread,
Jul 25, 2003, 11:11:54 AM7/25/03
to
On 25 Jul 2003 10:27:59 -0400, Joe Marshall <j...@ccs.neu.edu> wrote:

>geo...@collidoscope.com (George Maydwell) writes:
>
>> Because as mentioned above I've actually measured assembler to be only
>> 8% faster for my application. You can look at my sixteen lines of C++
>> code here:
>> http://www.collidoscope.com/ca/arca.html#Code_For_ARCAL
>> and perhaps get an idea as to why assembler is not much faster than
>> C++ for my task.
>> Global register allocation won't make my cellular automata go any
>> faster. Calling overhead is negligible in well written cellular
>> automata software. The overhead of C++ is not what you appear to be
>> trying to lead others to believe.

<snip>

>> >What exactly are you questioning here?
>>
>> I'm questioning the validity of any performance comparison between
>> high level languages which ignores C++ function inlining and the very
>> real performance increases which this one feature alone can be
>> responsible for in time-critical code.
>
>C++ is not the only language with function inlining.

I'm not aware of any other widely-used commercially-accepted language
with this feature, unless you are referring to C or the macro
capabilities in LISP.

>
>Note that if function inlining gives `very real performance
>increases', then how could it be that `calling overhead is
>negligable'?

You have mixed and matched unrelated quotes taken out of context.
Here is what I wrote: "Calling overhead is negligible in well written
cellular automata software".

Calling overhead for C++ inlined functions will always be negligible
because it is non-existent. This applies both to cellular automata
software and to non-cellular automata software.

<snip>

John D.

unread,
Jul 25, 2003, 3:41:31 PM7/25/03
to
"Anton van Straaten" <an...@appsolutions.com> wrote in message news:<Mv2Ua.118854$Io.10...@newsread2.prod.itd.earthlink.net>...

>
> Along these lines, to demonstrate beyond all doubt which language is best,
> try the following searches:
>
> http://www.google.com/search?q=java - 32,700,000 results for Java
> http://www.google.com/search?q=scheme - 10,300,000 results for Scheme
> http://www.google.com/search?q=C%2B%2B - 7,820,000 results for C++
> http://www.google.com/search?q=C%23 - 2,080,000 results for C#
>
> This "argumentum googlum" demonstrates beyond any doubt that Java is the
> most popular language, followed by Scheme. C++ is struggling along behind,
> and C# is only being used, judging by the numbers, at subsidiaries of
> Microsoft.

http://www.google.com/search?q=C - 316,000,000 results for C

How do like them apples?

Frank Buss

unread,
Jul 25, 2003, 6:03:16 PM7/25/03
to
"Anton van Straaten" <an...@appsolutions.com> wrote:

> Along these lines, to demonstrate beyond all doubt which language is
> best, try the following searches:
>
> http://www.google.com/search?q=java - 32,700,000 results for Java
> http://www.google.com/search?q=scheme - 10,300,000 results for Scheme
> http://www.google.com/search?q=C%2B%2B - 7,820,000 results for C++
> http://www.google.com/search?q=C%23 - 2,080,000 results for C#

This doesn't demonstrate anything, because it shows all the marketing,
newspaper etc. pages, and of course articles about the country Java and
the like. A better source would be the Sourceforge statistics. I've
checked it last year and this year and the growing rates are interesting,
too:

http://groups.google.de/groups?selm=bbj6pk%24qn2%241%40newsreader2.netcologne.de

Thant Tessman

unread,
Jul 25, 2003, 6:10:17 PM7/25/03
to
Frank Buss wrote:
> "Anton van Straaten" <an...@appsolutions.com> wrote:
>
>
>>Along these lines, to demonstrate beyond all doubt which language is
>>best, try the following searches:
>>
>>http://www.google.com/search?q=java - 32,700,000 results for Java
>>http://www.google.com/search?q=scheme - 10,300,000 results for Scheme
>>http://www.google.com/search?q=C%2B%2B - 7,820,000 results for C++
>>http://www.google.com/search?q=C%23 - 2,080,000 results for C#
>
>
> This doesn't demonstrate anything, because it shows all the marketing,
> newspaper etc. pages, and of course articles about the country Java and
> the like. [...]

It's much worse than that. Sometimes the words "Scheme" and "Java" have
nothing to do with computers. This probably is even more so for "C".

I think Anton van Straaten was making a joke. I laughed anyway...

-thant

George Maydwell

unread,
Jul 25, 2003, 7:45:36 PM7/25/03
to
On Fri, 25 Jul 2003 09:22:05 +0000 (UTC), David Rush <dr...@aol.net>
wrote:

>geo...@collidoscope.com (George Maydwell) writes:
>> On 23 Jul 2003 14:34:27 -0500, Matthias Blume wrote:
>> >geo...@collidoscope.com (George Maydwell) writes:
>> >> On 23 Jul 2003 09:43:38 -0500, Matthias Blume wrote:
>> >> >shi...@swirve.com (Shinji Ikari) writes:
>
>> What on earth are you talking about here? C++ code written by a
>> competent programmer doesn't need "hand optimization".
>
>Sorry, but programming in C/C++ involves *tons* of what amounts to
>hand-optimization.

No. Most programming in C/C++ that I've done involves getting things
like algorithms or object oriented user interfaces to work. Very
little involves hand optimization for performance purposes. If I had
to give a quantitative assessment of the percentage of the number of
lines of C/C++ code which I've seen which need any kind of
optimization I would put the figure at far less than 0.1%. I have
never seen a need for "tons" of hand optimization in a C/C++ project.
Good algorithm design almost always trumps hand optimization.

> Most C/C++ programmers either don't notice it
>(because they don't know any better) or simply write inefficient
>code. Since you profess to care about performance I'll assume that you
>are in the former camp.

I care enough about performance that I've actually gone out and
measured it in most of the various kinds of software I've worked on. I
also feel good programmers always understand the run-time performance
implications of every line of code they write. I'm not in your camp of
programmers who "don't know any better".

>
>As a simple example, every time you invoke a memory allocation
>operator, you are hand optimizing the run-time system.

Are you sure it is not the corresponding memory deallocation which
represents the "hand optimization" of the run-time system?

Next we'll hear that hand optimization is using one's fingers to type
code into the computer :-)

<snip>

Anton van Straaten

unread,
Jul 26, 2003, 8:57:14 AM7/26/03
to
> > This doesn't demonstrate anything, because it shows all the marketing,
> > newspaper etc. pages, and of course articles about the country Java
> > and the like. [...]
>
> It's much worse than that. Sometimes the words "Scheme" and "Java" have
> nothing to do with computers. This probably is even more so for "C".
>
> I think Anton van Straaten was making a joke. I laughed anyway...

Yes, thanks for noticing. :)

Re pages that have nothing to do with computers, if you make the query more
specific and google for "C++ language" and "Scheme language", the two come
out much closer - although Scheme still wins. Apparently Scheme is much
more popular than previously realized! I just can't understand why I'm not
seeing any Scheme jobs listed in the New York Times...

Anton

Frank Buss

unread,
Jul 26, 2003, 10:43:54 AM7/26/03
to
"Anton van Straaten" <an...@appsolutions.com> wrote:

>> I think Anton van Straaten was making a joke. I laughed anyway...
>
> Yes, thanks for noticing. :)

Your joke is getting old.

> Re pages that have nothing to do with computers, if you make the query
> more specific and google for "C++ language" and "Scheme language", the
> two come out much closer - although Scheme still wins.

With this query you'll find results like "a new language scheme for.." or
"a scheme for testing a program in ... language" etc.

According to http://sourceforge.net/softwaremap/trove_list.php?form_cat=160
there are 11091 C++ projects and 156 Scheme projects registered at
Sourceforge, which is a better measurement than a Google search.

David Rush

unread,
Jul 26, 2003, 12:47:06 PM7/26/03
to
geo...@collidoscope.com (George Maydwell) writes:

> On Fri, 25 Jul 2003 David Rush <dr...@aol.net> wrote:
> >Sorry, but programming in C/C++ involves *tons* of what amounts to
> >hand-optimization.
>
> No. Most programming in C/C++ that I've done involves getting things
> like algorithms or object oriented user interfaces to work. Very
> little involves hand optimization for performance purposes.

You are coming from a camp that does not have heavily optimizing
compilers. It is clear from your comments below that we do not share
similiar views of what kinds of coding are 'hand-optimization'. Which
was my point in saying:

> > Most C/C++ programmers either don't notice it
> >(because they don't know any better)

I apologize for the ambiguous reference. I am referring to
understanding what optimizations clever compilers *can* perform at
least as well as humans (and sometimes better). And, AFAIK, there are
*no* clever C compilers by my definition; the language semantics do
not really allow compilers to be clever.

> I'm not in your camp of
> programmers who "don't know any better".

Sorry, you haven't shown that you would recognize when you are
hand-optimizing code. You have shown that you *do* care about
performance.

> >As a simple example, every time you invoke a memory allocation
> >operator, you are hand optimizing the run-time system.
>
> Are you sure it is not the corresponding memory deallocation which
> represents the "hand optimization" of the run-time system?

Both malloc() and free() are memory allocation operators, are they
not? There are other allocation operators. I don't really want to
descend into the mire of comparing specific language features because
that is not my point. The point is that memory allocation is a solved
problem and since compilers/run-time systems can handle the gross
detail far better than humans, direct use of memory allocation
primitives amounts to hand-optimization. There are other common
hand-optimizations which are not solved problems for the run-time
environment. Tail-call optimization is another well-solved run-time
problem, which people hand-code around in C all the time.

Anton van Straaten

unread,
Jul 26, 2003, 11:43:43 PM7/26/03
to
Frank Buß wrote:
> "Anton van Straaten" <an...@appsolutions.com> wrote:
>
> >> I think Anton van Straaten was making a joke. I laughed anyway...
> >
> > Yes, thanks for noticing. :)
>
> Your joke is getting old.

Perhaps so, but it was relevant to the post I replied to, which claimed,
based on a Google search which exactly matched a book title, that C++ was


"about the only language successful enough in real life that a book has

actually been written about it" (where "it" meant large-scale design, or
something). I thought that such a silly claim deserved a silly response.

> > Re pages that have nothing to do with computers, if you make the query
> > more specific and google for "C++ language" and "Scheme language", the
> > two come out much closer - although Scheme still wins.
>
> With this query you'll find results like "a new language scheme for.." or
> "a scheme for testing a program in ... language" etc.

Thanks for pointing that out. I can see I'm going to have to completely
rethink my understanding of the artificially intelligent intent-inferencing
processes which underlie Google searches. What on earth has Peter Norvig
been doing there all this time, then?

Anton

Marco Gidde

unread,
Jul 27, 2003, 5:02:58 PM7/27/03
to
geo...@collidoscope.com (George Maydwell) writes:

> On 25 Jul 2003 08:49:20 +0200, Marco Gidde <mgid...@tiscali.de>
> wrote:
>
> > You shouldn't call something C++ that is in
> >fact lowest level C.
>
> Why not? The C++ compiler didn't complain about it. The C++ language
> didn't stop me from writing code which also happens to be legal C. Nor
> did it stop me from writing code which approaches the speed of
> assembler.
>
> With the exception of inlining it is perhaps unreasonable to expect to
> see C++ specific language features utilized in the inner loop of fast
> cellular automata software which is essentially nothing but table
> lookups.

You probably know that the C++ 'inline' statement is only a hint for
the compiler - a hint that can be ignored. On the other hand i do not
know an optimizing C compiler that does not inline code where it is
appropriate. Using a 'feature' that isn't a feature means that you are
writing C code.

Btw. rewriting your code using classes or the STL would definitely lose
speed, but that would be 'high level' and it would be C++.

HyperHacker

unread,
Jul 27, 2003, 11:35:42 PM7/27/03
to
"George Maydwell" <geo...@collidoscope.com> wrote in message
news:3f20c8d9...@news.prodigy.net...

> On 23 Jul 2003 14:34:27 -0500, Matthias Blume
> <matt...@shimizu-blume.com> wrote:
>
> >
> >Someone bit. (I thought someone would.... still ducking for cover... :)
> >
> >geo...@collidoscope.com (George Maydwell) writes:
> >
> >> On 23 Jul 2003 09:43:38 -0500, Matthias Blume
> >> <matt...@shimizu-blume.com> wrote:
> >>
> >> >shi...@swirve.com (Shinji Ikari) writes:
> >> >
> >> >> Learning C++ is equivalent to studying to be a NASA test pilot. Its
> >> >> incredibly fast and effective, but takes years to master the arcania
> >> >> and things tend to blowup in your face if you're not very careful.
> >> >
> >> >I would rather compare it to learning how to drive a racecar: yes, it
> >> >can be fast. Most people tend to drive it off track right away. Some
> >> >people die in it. The skills you acquire by learning it are only
> >> >marginally related to what you need in the real world.

The race car metaphor is the same metaphor as used by Neal Stephanson
in his book "In the Beginning...was the Command Line." I recommend all
to read this book.

> >> The skills you acquire by learning C++ are only marginally related to
> >> what you need in the real world only if you are bound and determined
> >> to become a COBOL programmer. Writing modular efficient software will
> >> be a real world need so long as there is competition and a software
> >> industry. I've earned a living for almost twenty years by using C and
> >> C++ on large projects for commercial product development. It works.

Too much industry specific argumentation, and far too prejudicial. Not all
languages are as bad as COBOL, and many are far worse.

> >You are right of course. The "real world" of today is like the early
> >days of automobiles where everybody had to be an expert in
> >double-clutching, half a car mechanic, etc. Nowadays those "bare
> >metal" machines of the past would have no chance in comparison to
> >modern, easy-to-drive, and safe vehicles. I expect the same to be
> >true for programming languages -- 20 years down the road, give or take
> >10.

Too optimistic that a *knowledge product* can be used without concomitant
*knowledge personal*. While many people use the car without getting under
the hood, there are many employed to do this job for others. Further, it is
not
always possible to use the car without some minimal knowledge. If the
driver
is not able to fill the tank, there is no driving.

I would argue that as the level of complexity of our *toys* increases, the
level
of personal responsibility for those *toys* grows.

> There's no such thing as a safe vehicle. There's no 100% protection
> against the stupidity of bad drivers and the accidents they cause.

Amen.

> >> > (In the case
> >> >of cars, you learn nothing about traffic rules, defensive driving,
> >> >etc.) The activity is (or, in the case of C++, should be) illegal
> >> >except in specially marked areas that are protected from the rest of
> >> >the world, and of which the rest of the world is protected from. The
> >> >activity is also not very useful in practice: the vehicle goes really
> >> >fast for only short periods of time.
> >>
> >> In practice, some care about raw speed, whereas others are perfectly
> >> willing to tolerate and inflict slow software upon others, even
> >> painfully slow software. Areas where speed is still important include
> >> spreadsheets, simulations, image manipulation, page layout, non-SQL
> >> database searching (as used in Proteomics), and cellular automata.
> >
> >For none of these is it necessary to use C or C++ to get the speed you
> >need.


>
> Then provide even a single example of non-C++ cellular automata
> software which provides the speed I need. Your statement is
> definitive, where is your proof?

Happy here to oblige. I have software which I have maintained for about
twenty years, which is constructed as it is because of the nature of the
hardware then available. I am very interested in von Neumann cellular
automata systems, the automatons thereon supportable, and the completion
of a design for a self-replicating cellular automaton which is strictly in
keeping
with von Neumann's architecture.

In order to be able to service the estimated 700 by 700 cell space necessary
to implementation and simulation of such a von Neumann self-replicating
cellular automaton, I needed special software in order to execute it on my
then minimal IBM-PC type processor (you know, 1MB RAM, 4 to 10 MHz
processor; the usual underpowered home computer). Given the minimal size
of RAM, and my expectation of many concurrent data streams within the
operating cellular automaton, it seemed reasonable that the best way to
obtain
speed was to compute the state transitions of all 490,000 cells. For the
8088 based PC running at (was it then) 5MHz, the computation yielded a
new state for the entire 700 by 700 space in one second.

I have long used this software, and my Core War Colosseum product, as a
means to judge the speed improvements of hardware releases.

The software for the von Neumann 29-state cellular automata system is mostly
written in C, though the state transition and graphic display functions are
entirely
in hand optimised 8088 assembly language. The functions originally were
written
in C, which itself was optimally written to begin with, and compiled using
the then
standard compiler. I typically used Microsoft, though the Borland language
tools
were often interchanged.

I can tell you that the code operates under Windows 2000 and other forms of
NT. It is highly self-modifying.

For additional information on my work, see:

http://users3.ev1.net/~hhacker

> > In some cases I will argue that C or C++ are going to hold you
>
> What C++ knowledge have you displayed and why should others believe
> you?
>
> >back speed-wise. This is going to be more and more true as processor
> >architectures advance, resulting in a growing gap between the facts
> >and the assumptions
>
> You've been following presidential politics.
>
> > that are inherent in the design of said languages.
> >Another reason for a speed differential I expect to emerge in the area of
> >memory management.
>
> And the basis for your expectations is what? I've seen bottlenecks in
> code. I've also seen bottlenecks caused by memory management. Guess
> what? It was the result of stupidity! Good programmers avoid memory
> management in time critical code.

Makes sense to me. Run-time memory management always is more
expensive than compile-time memory management (pre-allocation). It
would seem similarly valid that memory management at the leaf nodes of
the code tree would cost the most.

> >> In reality the C++ vehicle never ever goes slower than the competion
> >> when driven by a competent driver. It cannot, as the C++ language
> >> started out as a preprocessor which generated C code, and C has little
> >> overhead, being very close to machine language. There is very little
> >> performance overhead in C++, despite it being a high-level language.
> >
> >This is a bogus reason.

It is begging the question. Show me why C++ is always as fast as C.
The C++ language has extensions to the generated code which allow the
language to be object oriented. The V-table: two dereferences instead of
one.

> Lack of performance overhead is a bogus reason for choosing C++? You
> are bogus.
>

> >programming in assembler today. (Of course, we sometimes are, and
> >there is a place for C and C++ today, too. It is just not every place
> >-- and it also should not be "nearly every place".) If a project
> >gets complex enough, the task of actually hand-optimizing your C or
> >C++ code so that it matches the high-level languages with today's
> >sophisticated compilers is simply too hard, too error-prone, and does
> >not give enough return for the investment.
>

> What on earth are you talking about here? C++ code written by a
> competent programmer doesn't need "hand optimization".

Please, do not just assert. Prove your point.

I would generally agree, however, with the assertion. Indeed, I might
argue that hand optimisation is not possible in C++. Good design and
coding practices do the job for you. This is the case we have seen with
the change from spaghetti code to modular design, to structured coding,
and now to object oriented coding. It is clear that the mindset of those
programming according to these standards is different, and so the mindset
frees the programmer from needing to address certain kinds of problems.
Simply, follow the standard and the problems are abaited. The issue is
programmer efficiency.

However, this does not address the issues of code efficiency.

> >See, e.g., Doug Bagley's often cited "language shootout" to see for
> >yourself that C and C++ are by no means heads-and-shoulders above the
> >competition efficiency-wise.
>

> What does Doug Bagley know about the efficiency of C/C++ when
> implementing fast cellular automata? What does he know about the
> efficiency of C++ for simulation purposes? I've seen C++ function
> inlining alone easily result in doublings of speed for numerical
> calculations. What do other widely used languages do to remain
> "head-and-shoulders" with inlined C++ "efficiency-wise"? Can even a
> single example be produced?

Many C++ programmers would agree that the use of inline code is a means
to achieve efficient implementation. I see no sin in using the features of
a
programming language to your advantage.

> >In reality we will see more and more situations where C or C++ code
> >does not go slower than the competition simply because it never
> >manages to go at all, no matter how competent the programmers are. (I
> >have already seen this happen in real-world industrial projects with
> >programmers at the helm that by most standards are already considered
> >super-human when it comes to crafting good code.)
>
> And if the "super-human" programmers blamed the project failure on C++
> then they are not super-human and in my opinion they are not even
> competent. If you've "seen this happen" then you are blind and naive.

I would agree on this point: bad programmers.

> >> > Even very skilled drivers cannot
> >> >stop the vehicle from blowing up or falling apart after a few hundred
> >> >miles unless extremely expensive maintenance is applied constantly.
> >>
> >> No. Even the most advanced technologies cannot make poorly architected
> >> software maintenance-free or protect it from programmers who don't
> >> know what they are doing.
> >
> >Nobody said such a thing.
> >
> >> C++ just happens to be about the only


> >> language successful enough in real life that a book has actually been

> >> written about it: "Large Scale C++ Software Design". The following
> >> Google query doesn't return many non C++ references:
> >>
> >>
http://www.google.com/search?hl=en&ie=ISO-8859-1&q=large+scale+software+desi
gn
> >

> >Having a book on some attempt at solving a problem does not mean that
> >the solution it talks about actually is one,


>
> You are full of it. I wouldn't hire you.
>

> > and if it is, that it is
> >the only one, and certainly not that it is the best. (Being cynical
> >one could even argue that it might mean the opposite. Hehe, I'm still
> >ducking... :-)
> >
> >Cheers,
> >Matthias


>
>
> George Maydwell
> --
> Modern Cellular Automata: www.collidoscope.com/modernca
> Collidoscope Hexagonal Screensaver: www.collidoscope.com

--
William R. Buckley
Director Emeritus,
International Core Wars Society


David Rush

unread,
Jul 28, 2003, 5:53:54 AM7/28/03
to
geo...@collidoscope.com (George Maydwell) writes:
> Eye candy! I can't
> think of a better real world application for cellular automata.

Well, I can. Among other things there have been applications of CAs to
fluid-dynamics. ISTM that, in general, CAs are awfully close to
FEMs. I've personally used them as part of game AIs. I'm pretty sure
that there are other uses.

Siegfried Gonzi

unread,
Jul 28, 2003, 4:41:38 AM7/28/03
to
George Maydwell wrote:

> I'm questioning the validity of any performance comparison between
> high level languages which ignores C++ function inlining and the very
> real performance increases which this one feature alone can be
> responsible for in time-critical code.

I am not quite sure what you call inlining, but Bigloo (Scheme) has an
inlining mechanism. But I do not know whether this will increase
performance.

The functional programming language Clean has inlining too. There, I am
quite sure this is for performance reasons.

Okay, Clean is not for outside of its own world. But there exists
functional languages which have got the possibility to inline functions.

Btw: I am in academia too, and have never written programs which scratch
the 1000 lines of code threshold, but you shouldn't speak of large scale
programming and calling C++ and then pointing to your tiny programs.
Sorry, but this is ridiculous.

S. Gonzi

George Maydwell

unread,
Jul 28, 2003, 10:10:38 AM7/28/03
to

I didn't.

>Sorry, but this is ridiculous.

Indeed.

>
>S. Gonzi

David Rush

unread,
Jul 28, 2003, 11:59:33 AM7/28/03
to
Matthias Blume <matt...@shimizu-blume.com> writes:

> Joe Marshall <j...@ccs.neu.edu> writes:
> > I found it neither offensive nor extreme. (I did assume it was
> > intentionally posted.)
>
> Thanks. (I did post things more offensive and more extreme in the
> past. I guess I'm mellowing...:-)

Type safety of call-with-values in a winding continuation...

<g>

David Rush

unread,
Jul 28, 2003, 12:05:07 PM7/28/03
to
Frank Buss <f...@frank-buss.de> writes:
> According to http://sourceforge.net/softwaremap/trove_list.php?form_cat=160
> there are 11091 C++ projects and 156 Scheme projects registered at
> Sourceforge, which is a better measurement than a Google search.

Which is pretty bloody amazing if you consider that far less than 1%
of all programmers are Schemers.

david rush
--
(also a perpetrator of a noticeable percentage of the Scheme SF
projects)

Kent Paul Dolan

unread,
Jul 29, 2003, 12:20:44 AM7/29/03
to
"Siegfried Gonzi" <siegfri...@kfunigraz.ac.at> wrote:

> pointing to your tiny programs.

Someone who doesn't program in the large probably cannot recognize
what size George's programs have to be. What he put online for us
was the tiny inner loop of a very large program.

> Sorry, but this is ridiculous.

Indeed, to have people inveighing in ignorance "that isn't C++" (oh,
yes it is; C++ almost entirely includes C, and something that compiles
under the C++ compiler is C++, however un-fancy; probably, most inner
loops of most C++ programs will compile as C), or "that is a tiny
program", confusing subroutines with programs, is way ridiculous. We
can gin up enough malicious ignorance on our own without having to
import any.

xanthian.


--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

Bill Richter

unread,
Jul 29, 2003, 10:33:58 PM7/29/03
to
qo...@purdue.edu (Jeffrey Mark Siskind) writes:

> Further, new quantifiers (aka higher-order functions) are regularly
> defined. And use of complex compound quantified expressions with
> free lexical variables is pervasive:
>
> \forall_{x\in X}\exists_{y\in Y} \ldots
> \int_0^1\int_0^1 \ldots dy dx

Jeff, thanks for the response. Taking it online, That's a statement:

something about your double integral is supposed to be true for all x
in X and for some y in Y (depending on x).

I don't see how Math statements arise in Scheme. Church originally
wanted to foundationalize Math in the Lambda Calculus, but ran into
paradoxes, so restricted LC to functions. And yes, the `lexical
scoping of free variables' in Scheme/LC is the same as in Math.

> Determining that your code matches your paper is significantly
> easier when you write your code like:
>
> (every (lambda (x) (some (lambda (y) ...) big-y)) big-x)
> (integral (lambda (x) (integral (lambda (y) ...) 0.0 1.0)) 0.0 1.0)

OK, I went to CLTL to find out what every & some meant. Given a
predicate F of n arguments, and n lists, then considered as a
predicate

(some F (a_{1,0} ... ) (a_{2,0} ... ) ... (a_{n,0} ... ))

is true if ( F a_{1,i} a_{2,i} ... a_{n,i} ) is true for some i >= 0 ,

And considered as a predicate, (every ... ) is true if every such
invocation is true.

But since you write (lambda (x) ... ) & (lambda (y) ...), you're just
doing functions of 1 argument. So

(some (lambda (y) ...) big-y)

returns true if your function returns true on some member of the list
big-y. Got it. Now I guess big-x and big-y are lists that are like
your sets X and Y. But you're trying to conform to

> \forall_{x\in X}\exists_{y\in Y} \ldots
> \int_0^1\int_0^1 \ldots dy dx

Let's say there's some predicate F you can apply to this integral,
like maybe you want to know if the integral is positive or not. Then
wouldn't you mean

(every
(lambda (x)
(some
(lambda (y)
(F (integral (lambda (x) (integral (lambda (y) ...) 0.0 1.0)) 0.0 1.0)))
big-y))
big-x)

I think you write this way below in fact.

> If I had written:
>
> (let outer ((big-x-prime big-x))
> (if (null? big-x-prime)
> #t
> (and (let ((x (first big-x-prime)))
> (let inner ((big-y-prime big-y))
> (if (null? big-y-prime)
> #f
> (or (let ((y (first big-y-prime)))
> ...)
> (outer (rest big-y-prime))))))
> (outer (rest big-x-prime)))))

OK a named let to pull off a double "do" construction which ands
through all the elements x of big-x and then ors through the elements
y of big-y and tests if some function (foo x y) is true.

> instead of:
>
> (every (lambda (x) (some (lambda (y) ...) big-y)) big-x)
>
> it would be much more difficult to ascertain that my code implemented:
>
> \forall_{x\in X}\exists_{y\in Y} \ldots

Sure! But until I understand the Math connection better, I'm just
thinking that it's advantageous to have functions that short-circuit
the double "do" constructions. PLT Scheme has a number of such
functions, like filter.

> I have come to believe that, in research, it is really beneficial,
> and even imperative, that corresponding code and documentation have
> isomorphic abstract syntax. I conjecture that, if people really
> thought about it and understood the issues, the same would hold true
> in industrial software development.

I looked at your papers quickly and didn't find anything. Can you
give an example of this Math connection of yours, or speculate how it
would arise often in `industrial software development'?

Anton van Straaten

unread,
Jul 30, 2003, 2:01:34 AM7/30/03
to
Bill Richter wrote:
> Sure! But until I understand the Math connection better, I'm just
> thinking that it's advantageous to have functions that short-circuit
> the double "do" constructions. PLT Scheme has a number of such
> functions, like filter.

Stated prosaically, that *is* the "Math connection". It's just a question
of abstraction level. I notice you don't seem to be
worrying about how the electrons are flowing inside the CPU, or what machine
instructions are executing as a result of the high-level code you're
running. Why not? Because we rely on higher-level tools to correctly
perform the high-level instructions we give them.

In exactly the same way, when you invoke functions like 'every', 'some',
'map', 'filter', or 'fold' - standard functional programming operations -
there's other stuff going on beneath the abstraction which doesn't matter,
like double, triple, ntuple "do"s. All you should care about, though, is
that the language at the level of abstraction at which you're working has
been reliably implemented.

So the "Math connection" is simply that to do math in code, you want code
that's fairly isomorphic to your math. If it's not, you have to spend more
time making sure that your code and math say the same thing, and your code
is less likely to give you insights into your math, because the translation
back and forth tends to obscure things, not to mention waste time and mental
effort which could be better spent on something more productive and relevant
to your math.

To write code that's similar to your math, you need well-designed,
well-implemented, and high-level abstractions in the language you're using.
For this purpose, constructs like "do" are generally about as irrelevant as
an assembler instruction or the bit pattern that represents it. Instead,
you want a language with a decent formal basis that has math-like properties
and in which you can easily abstract away mechanics like iteration, for
example. Functional languages, including Scheme, fit this bill.

You wrote:
> I don't see how Math statements arise in Scheme.

But Siskind demonstrated a virtual transliteration from math to Scheme, and
it's easy to produces others like that. What's the problem? It seems
you're focusing on how the abstractions are implemented, but that's like
focusing on how you work out a concrete math problem with a paper and pen
(and I'm getting deja vu now).

If you're "just thinking that it's advantageous to have functions that
short-circuit the double "do" constructions", are you also "just thinking
it's advantageous to have greek symbols that short-circuit the excessive use
of a #2 pencil and some pressed sheets of pulped wood"? Well, sure it is.

> I looked at your papers quickly and didn't find anything. Can you
> give an example of this Math connection of yours, or speculate how it
> would arise often in `industrial software development'?

Identical issues apply in industrial software development. It's why
object-oriented designers spend a lot of time developing and refining object
models which match their application's domains, for example; and one of the
reasons why XML has become so popular - as a low-cost way of creating
domain-specific languages, however rudimentary. Unfortunately, for
historical reasons, many of the languages popular in industry have limited
abilities to abstract over some important domains, including one of the most
basic ones, functions.

Anton

Bill Richter

unread,
Jul 30, 2003, 1:22:45 PM7/30/03
to
Anton, I agreed I think with everything you wrote, but you
misunderstood me:

> I don't see how Math statements arise in Scheme.

But Siskind demonstrated a virtual transliteration from math to
Scheme, and it's easy to produces others like that. What's the
problem?

In Math, you prove theorems. Here's Fermat's last theorem, recently
proved by Wiles, they say:

\forall x \in N
\forall y in N
\forall z in N
\forall n in N
(n>= 3) and (x^n + y^n = z^n) implies xyz = 0

That's a statement, not a function. I don't know what the Scheme
analogue of Fermat's last theorem is, or why anyone would care.
Scheme is about functions. For instance like the function every,
which takes a predicate and a list as an argument, and

(every predicate list) => true
iff
(predicate x) => true
for all x in the list.

Now JMS does high-level AI, and has written a smart compiler (with an
awful name unfortunately), and he may very well have theorems in
mind, and not just statements.

So the "Math connection" is simply that to do math in code, you
want code that's fairly isomorphic to your math. If it's not, you
have to spend more time making sure that your code and math say the
same thing, and your code is less likely to give you insights into
your math, because the translation back and forth tends to obscure
things, not to mention waste time and mental effort which could be
better spent on something more productive and relevant to your
math.

Yeah, sure, if
Math = mathematical functions.
I thought JMS meant
Math = mathematical statements,
like Fermat's last theorem.

Jeffrey Mark Siskind

unread,
Jul 30, 2003, 5:49:48 PM7/30/03
to
I was refering to mathematical statements.If you read my posts
carefully, you
will see that all of the quantification is bounded. I intended the
quantification
to be over finite sets. Not all mathematical statements are about
infinite sets.
Often we quantify over an infinite class of finite structures. For
example, proving the
correctness of a compiler requires quantifying over all programs. But
for any given program you perform bounded quantification over finite
sets of identifiers,
expressions, accesses, assignments, and the like.

Bill Richter

unread,
Jul 30, 2003, 7:38:45 PM7/30/03
to
I was refering to mathematical statements.

Thanks, Jeff! I realized one thing I said was dumb: even mathematical
functions often are defined in terms of quantifiers \forall & \exists.

If you read my posts carefully, you will see that all of the
quantification is bounded. I intended the quantification to be over
finite sets.

OK, cool, good point.

Not all mathematical statements are about infinite sets. Often we
quantify over an infinite class of finite structures. For example,
proving the correctness of a compiler requires quantifying over all
programs. But for any given program you perform bounded
quantification over finite sets of identifiers, expressions,
accesses, assignments, and the like.

OK. would this be an example? You posted earlier that your compiler
analyzed a Scheme program for how `+' was used

(if (every plus-bound-to-arithmetic+?
plus-occurrences-in-program)
(strong-plus-optimize ...)
(if (every plus-something-more-arcane?
plus-occurrences-in-program)
(sorta-arcane-plus-optimize ...)
(if (every plus-something-really-arcane?
plus-occurrences-in-program)
(really-arcane-plus-optimize ...))))


Maybe that's not really a statement, but it looks clear.

Dumb question: isn't `every' in the simple case more or less just
syntactic sugar:

(every predicate list)
==
(apply and (map predicate list))

Maybe a macro, so `predicate' isn't applied past the first false.
Looks like pretty useful sugar to me! Even though it's only a savings
of 2 words. I'd still like to know more about statements, though.

Bill Richter

unread,
Aug 1, 2003, 1:32:20 AM8/1/03
to
I was refering to mathematical statements.If you read my posts
carefully, you will see that all of the quantification is
bounded. I intended the quantification to be over finite sets. Not
all mathematical statements are about infinite sets.

I think I got it, Jeff. Mathematical statements show up in programs
as predicates! So with a statement X, you code

(if X ...)

and the statement X will likely involve quantifiers, but as you say,
only bounded quantification arise; otherwise you couldn't code it up.

I think that's a good idea, using every & some to mimic the
quantifiers \forall & \exists, I'll try to look out for it.

Anton van Straaten

unread,
Aug 1, 2003, 1:20:15 PM8/1/03
to
Bill Richter wrote:
> In Math, you prove theorems. Here's Fermat's last theorem, recently
> proved by Wiles, they say:
>
> \forall x \in N
> \forall y in N
> \forall z in N
> \forall n in N
> (n>= 3) and (x^n + y^n = z^n) implies xyz = 0
>
> That's a statement, not a function. I don't know what the Scheme
> analogue of Fermat's last theorem is, or why anyone would care.

FWIW, here's Scheme which expresses the above statement (relies on srfi-40):

(define N (stream-from 0))

(define fermat-test-results
(stream-of (= (* x y z) 0)
(x in N)
(y in N)
(z in N)
(n in N)
(and (>= n 3) (= (+ (expt x n) (expt y n)) (expt z n)))))

That defines an infinite stream of booleans resulting from testing the
implication xyz=0, which should all be #t, assuming Wiles didn't mess up.
If you like, you can replace (= (* x y z) 0) with (list x y z), to get a
stream of triples that satisfy the basic constraints, without testing the
implication.

The stream can be examined with e.g. (stream-for-each display
fermat-test-results). Of course, that'll take a while to finish printing,
so you might want to use e.g. (stream-for-each display (stream-take 100
fermat-test-results)), specifying the number of results you want to see.

Perhaps more usefully, you can ask the program to check the first n results:

(define (test-fermat n)
(stream-fold-left (lambda (a b) (and a b)) #t (stream-take n
fermat-results)))

Invoking (test-fermat 1000) returns a boolean which tells you whether the
theorem is true for the first 1000 results.

You're probably wondering "why anyone might care", as you said. The above
doesn't directly prove the theorem, and can't usefully be used as a
predicate in a program unless you limit the size of the test's domain. But
Fermat's last theorem isn't easily proved, so it's no surprise that
expressing it in Scheme doesn't get us very far. Why don't you pick a
simpler proof and look at how to express it in Scheme so that executing it
proves the theorem?

Also, there might be things that can be done with mathematical statements
whose computational analogues are non-terminating. Gregory Chaitin does
some interesting stuff like that, e.g.:
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.html
He uses his LISP dialect (actually a kind of Scheme subset) to prove results
relating to things like Goedel's incompleteness, algorithmic information
theory, and the halting probability. See his description of how he uses his
'try' evaluation mechanism to deal with non-terminating computations.

He says of LISP is "So why do I love LISP?! Well, the answer is, because
it's really set theory, and all mathematicians love set theory! LISP is just
a set theory for computable mathematics rather than for abstract
mathematics."

And of course, there's the Curry-Howard correspondence. Proofs are
programs, QED. :)

Anton

Joe Marshall

unread,
Aug 1, 2003, 2:42:52 PM8/1/03
to
"Anton van Straaten" <an...@appsolutions.com> writes:

> You're probably wondering "why anyone might care", as you said. The above
> doesn't directly prove the theorem, and can't usefully be used as a
> predicate in a program unless you limit the size of the test's domain. But
> Fermat's last theorem isn't easily proved, so it's no surprise that
> expressing it in Scheme doesn't get us very far. Why don't you pick a
> simpler proof and look at how to express it in Scheme so that executing it
> proves the theorem?

Out of curiosity, how about proving that the square root of 2 is irrational?

Bill Richter

unread,
Aug 1, 2003, 10:28:59 PM8/1/03
to
Invoking (test-fermat 1000) returns a boolean which tells you
whether the theorem is true for the first 1000 results.

You're probably wondering "why anyone might care", as you said.

Thanks, Anton and Joe. But I think I figured it out:

I think JMS wasn't talking about Math statements like FLT or \sqrt 2
is irrational, which are either true of false. I think he was talking
about predicates. So given a predicate F and an expression X, then
(F X)
is a like a Math statement, in that it returns either #t or #f.

(F X) isn't gonna be a mathematical statement like FLT, but if F is
mathematically defined using quantifiers, it might easily profit from
JMS's every/some ideas. Why not code up test-fermat that way?

For instance, try (F m n) => #t iff m and n are relatively prime.
Mathematically, that's

F(n) = #t iff for every i with 1 < i < min(m,n),

i does not divide both m and n.

So I coded up this rather boring example, and compared it to the
non-generative HtDP code:


;; every: (x -> boolean) (listof X) -> boolean
;; return a true value if (F x) => true for every x in X
(define (every F X)
(if (null? X)
true
(and (F (first X))
(every F (rest X)))))


;; integers-2->n : N[>= 2] -> (listof N)
;; to return the list (2 .... n)
(define (integers-2->n n)
(build-list (sub1 n)
(lambda (i)
(+ 2 i))))

(define (relatively-prime? n m)
(let
([possible-divisors
(integers-2->n (sub1 (min n m)))]
[not-divide-n&m (lambda (i)
(or
(> (remainder n i) 0)
(> (remainder m i) 0)))])
(every not-divide-n&m possible-divisors)))

(relatively-prime? 33 15)
(relatively-prime? 33 25)
(relatively-prime? 81 33)
(relatively-prime? 42 55)


Welcome to DrScheme, version 204.
Language: Pretty Big (includes MrEd and Advanced).
#f
#t
#f
#t

OK, I'm thinking JMS had a nice mathematical coding trick! Here's the
way I would've done it before, and it's perfectly fine too, and you
can see I borrowed my code from HtDP's function gcd-structural:

;; gcd-structural : N[>= 1] N[>= 1] -> N
;; to find the greatest common divisior of n and m
;; structural recursion using data definition of N[>= 1]
(define (gcd-structural n m)
(local ((define (first-divisior-<= i)
(cond
[(= i 1) 1]
[else (cond
[(and (= (remainder n i) 0)
(= (remainder m i) 0))
i]
[else (first-divisior-<= (- i 1))])])))
(first-divisior-<= (min m n))))

(define (relatively-prime? n m)
(= (gcd-structural n m) 1))


BTW I was surprised I couldn't define every like this:

(define (every F X)
(apply and (map F X)))

Guess I don't understand apply or and.

Jens Axel Søgaard

unread,
Aug 2, 2003, 3:50:40 AM8/2/03
to
Bill Richter wrote:

> BTW I was surprised I couldn't define every like this:
>
> (define (every F X)
> (apply and (map F X)))
>
> Guess I don't understand apply or and.

You forget that and is special form and not a function.
If you need and as a function, just make one your self:

(define (fand . l)
(if (null? l)
#t
(and (car l) (fand (cdr l))))

(BTW: Note that the call to fand is tail-recursive.)

--
Jens Axel Søgaard

Bill Richter

unread,
Aug 2, 2003, 11:48:55 PM8/2/03