Separating algorithms from implementations (long)
Toby Sharp
Apologies for double post if it subsequently appears. ]
For some time I have been reading books on computer graphics, studying
algorithms and idly contemplating how interesting it would be to have enough
time to write my own graphics engine / pipeline / applications.
Of course, if I had the time, it would have to be done properly. The design
stage is paramount in a robust and "future-proof" application. Naturally,
object-oriented design patterns come in handy, within a C++ architecture.
But in this setting, certain time-critical portions of code, while small,
may constitute 99% of the CPU time. For example, polygon drawing, vector
calculations, etc.
These time-critical sections need to be heavily optimised for speed. After
exploiting all a given algorithm's redundancy, critical code can be
hand-tuned in assembly language to squeeze out every drop of performance.
There's a very good reason for hand-crafting time-critical code in ASM: the
author knows far more about how the algorithm works than does a compiler,
and this extra knowledge allows the author to do far more optimisation than
just scheduling the instructions efficiently.
So, a few days later, what was a few lines of C code is now many lines of
ASM code, but it runs in half the time and everyone's happy. But then the
inevitable happens. A new CPU becomes available, and all the rules have
changed. Has anyone ever switched from floating-point to fixed-point and
back to floating-point again, depending on which is fastest at the time?
Instruction times and latencies are subject to change.
For example, multiplication is at least as computationally expensive as
addition, so (x + x) should be prefarable to (x * 2). But what about (x *
3)? Whether 'tis best to use one multiplication here or two additions
depends entirely on the target CPU, and therefore is subject to frequent
review, along with many, many other issues. Suddenly, your hand-crafted code
is no longer optimal, so you must re-write it if you still want it to be as
fast as possible. This isn't what life should be about.
At this point, most people would probably suggest leaving the code in C and
re-compiling when new compiler versions are released to reflect new target
CPUs. But this is not really satisfactory for critical performance. C will
use fixed-point or floating-point depending on what you told it to use. It
doesn't know about acceptable errors, nor does it know anything about the
nature or range of input data. For example, it will never use alpha instead
of sin(alpha) when alpha is small; and rightly so, for no-one said it
should. And as for exploiting parellism? Well, Intel's C/C++ compiler claims
automatic vectorisation for using their SIMD extenstions, but personally
(having tried their compiler) I certainly wouldn't trust my inner loops with
it.
We might be able to solve this problem if there were some way to describe
algorithms apart from their implementations. Such a description would need
to be sufficiently concrete to allow an implementation to be derived, but
needs to be sufficiently flexible to allow many different implementations.
These could then be tested for speed, or various trade-offs could be chosen
on the basis of knowledge of a target CPU. There would need to be a way to
state assumptions on the range and properties of input data. Knowledge of
these properties is what makes hand-tuned code able to be more efficient.
Acceptable errors could be defined where appropriate. Algorithms could be
described in ways which exploit parellelism, where appropriate, since this
is a strong direction for forthcoming CPUs.
Then a very, very clever compiler could spend a lot of time looking at the
algorithm description, assembling instructions into implementations, testing
sample data, and making changes as appropriate. If successful, the compiled
code should rival that of the hand-tuned implementation. However, the
algorithm doesn't change with the CPU, so neither does its description. It
can be recompiled later to generate a new implementation that benefits from
the features of a new CPU.
The crux of the idea is to have a new language which describes algorithms
separately from implementations. The language also provides a way to give
extra information about supplied input and required output, so that highly
optimised code can be created. A compiler goes into great detail to find the
best implementation for the supplied algorithm information.
So, has anyone done it? Suggested it? Any thoughts on whether theoretically
possible? Or practically feasible? All comments welcome at this stage.
--
--------------------------------------
Toby Sharp, B.Sc. (Hons), G.I.M.A.
Senior Software Developer
Serif (Europe) Ltd
--------------------------------------
Brett L. Moore
On Thu, 24 Aug 2000 13:00:16 GMT, "Toby Sharp" <TSh...@Serif.com>
wrote:
[snip]
>For example, multiplication is at least as computationally expensive as
>addition, so (x + x) should be prefarable to (x * 2). But what about (x *
>3)? Whether 'tis best to use one multiplication here or two additions
>depends entirely on the target CPU, and therefore is subject to frequent
>review, along with many, many other issues.
On definition of algorithm is:
"An algorithm is a set of rules that specify the order and kind of
arithmetic operations that are used on specified set of data".
Thus (x+x) and (x *2 ) represent two different algorithms to
accomplish the same objective: "make some quantity twice the value of
x"
[snip]
>At this point, most people would probably suggest leaving the code in C and
>re-compiling when new compiler versions are released to reflect new target
>CPUs. But this is not really satisfactory for critical performance. C will
>use fixed-point or floating-point depending on what you told it to use.
Under the above definition of alogrothm, using fixed-point or floating
point changes the algorithm.
[snip]
>algorithm doesn't change with the CPU, so neither does its description. It
>can be recompiled later to generate a new implementation that benefits from
>the features of a new CPU.
What you seem to be describing is a process that might modify the
algorithm or the implementation of an algorithm to achieve the "best"
executable image. What is best?
Such a system would have to be loaded with platform-dependent data
(i.e. how many registers - no big deal). However, it would have to
also include a large set of heuristics : ((i.e. when should it use x*2
or x+x?) Furthermore, the process must "understand" what the
objective is ("make some quantity twice the value of x"), then choose
the most appropriate method of accomplishing this task.
What you describe is challenging and of value to any optimization
problem: be it computer graphics, semiconductor manufacturing, or
public transportation.
James Van Buskirk
Toby Sharp wrote in message ...
[snip]
I could imagine doing what you want with assert(). Just as
assertions can be completely turned off with a compiler
switch, they could be turned off but the compiler allowed
to assume they are true with another switch.
Don't assume that multiplication is always at least as
computationally expensive as addition! This is most
definitely not true on a 21164 which has a dedicated and
often underutilized FP multiply pipeline. It's not
infrequently more efficient on that CPU to emulate floating
point or even integer additions with the FP multiplier
because that unit was not going to do anything in the
current clock cycle in any case, while the FP addition
pipeline or the integer pipelines are already saturated for
the current clock cycle. In such cases, FP multipication
is free whereas the more direct and obvious route costs
something.
Jeff Erickson
| We might be able to solve this problem if there were some way to
| describe algorithms apart from their implementations.
Wow. To my theoretician's eye, this statement is absolutely
preposterous. OF COURSE there are ways to describe algorithms apart
from their implementations. Look at ANY algorithms textbook, or for
that matter, almost any graphics textbook.
This is probably just a cultural difference in how we define the word
"algorithm". In my opinion, algorithms are abstract processes, not
limited to any particular hardware, operating system, or programming
language. Your mileage may vary.
I argue vehemently in the algorithms classes I teach that source code
is absolutely the wrong language to describe algorithms. Algorithms
are meant to be communicated to human beings. Source code includes
too much focus on (in the context of an algorithms class) irrelevant
details. Obviously those details have to be worked out in any actual
implementation, but they usually have little or no effect on the
design or analysis of the abstract algorithm and therefore should
usually be omitted from the high-level description.
| The crux of the idea is to have a new language which describes
| algorithms separately from implementations.
What's wrong with English?
--
Jeff Erickson je...@cs.uiuc.edu
Computer Science Department http://www.uiuc.edu/~jeffe
University of Illinois, Urbana-Champaign Non sum, ergo non cogito.
Christer Ericson
>I argue vehemently in the algorithms classes I teach that source code
>is absolutely the wrong language to describe algorithms. Algorithms
>are meant to be communicated to human beings. Source code includes
>too much focus on (in the context of an algorithms class) irrelevant
>details. Obviously those details have to be worked out in any actual
>implementation, but they usually have little or no effect on the
>design or analysis of the abstract algorithm and therefore should
>usually be omitted from the high-level description.
Generally I would agree with this: I'd much rather have a well-specified
algorithm description in plain English (with stress on the word _plain_)
than the source code implementing same.
However, there's also a danger in developing and presenting algorithms
without considering the implementation (as Jeff as a computational
geometrist would well know).
I've seen many algorithm descriptions given in plain text that leave out
those all-important details, making them, if not impossible, at least
very difficult to implement.
And on this topic, I must go on this side rant; please bear with me:
Singling out the field of computational geometry (as it is an important
field), it fails on both the above accounts, IMO. Despite that crisis
report of a few years ago, I still see lots of impractical unimplemented
(and, sometimes unimplementable) algorithms presented in that 'wonderfully'
unreadably obsfuscated style that academicians love. Always with half
of the important details omitted, and never objectively compared to all
those other papers with competing algorithms.
Of course, this problem isn't limited to just computational geometry.
Having been in the academic crystal castle myself, I think I have a good
understanding of where this all is coming from, but now being on the
outside looking in I have a newfound misappreciation of the practical
unusability of a large part of the academic research; mostly due to the
unnecessarily overcomplicated presentations.
Leaving the criticism behind and focusing on the constructive, does it
really have to be like this? Is there no way to get the academic world
to produce a) readable papers (for outside of the field), and b) with
more real-world usable results?
Christer Ericson
SCEA, Santa Monica
Jeff Erickson
| je...@cs.uiuc.edu (Jeff Erickson) wrote:
| >Source code includes too much focus on (in the context of an
| >algorithms class) irrelevant details. Obviously those details have
| >to be worked out in any actual implementation, but they usually
| >have little or no effect on the design or analysis of the abstract
| >algorithm and therefore should usually be omitted from the
| >high-level description.
| I've seen many algorithm descriptions given in plain text that leave
| out those all-important details, making them, if not impossible, at
| least very difficult to implement.
I think it's important to keep several issues separate here.
Most computer scientists (and I include myself here) do not know how
to write. We are trained in analytical thinking, not in clear
communication. We talk to ourselves in techno-babble, forgetting that
other people don't speak our language. I don't believe that anyone is
deliberately trying to confuse people. We just don't know how to say
things any other way.
On the other hand, some algorithms are inherently technical and
therefore difficult for ANYONE to understand. No matter how clearly
these algorithms are described, new readers will have to work hard to
understand them. This is less true for readers with some theoretical
training -- which is one reason that CS students should take
math and algorithms classes -- but even that may not be enough.
To quote Elvis Costello, answering a question about what his lyrics
mean: "If I could have said it any other way, I -would- have!"
I'm just as guilty as every other ivory tower computational geometer
of writing about algorithms that have no chance of ever being
implemented. I don't consider that a sin, as long as I'm honest about
it. Even unimplementable algorithms provide interesting mathematical
insights; those insights are the true goal of theoretical research,
NOT the algorithms themselves.
That may be the biggest hurdle. Theoreticians and practitioners have
different goals, different motivations, and different standards. That
makes it far too easy for each side to dismiss the other as being
clueless.
| Singling out the field of computational geometry (as it is an
| important field), it fails on both the above accounts, IMO. Despite
| that crisis report of a few years ago...
For those of you who don't know what Crister is talking about, you can
read all about it here:
http://www.uiuc.edu/~jeffe/cmopgeom/taskforce.html
| I still see lots of impractical unimplemented (and, sometimes
| unimplementable) algorithms presented in that 'wonderfully'
| unreadably obsfuscated style that academicians love.
Agreed, except for the part about academics loving obfuscation.
Slogging through a badly-written paper about a good result is deeply
frustrating.
Almost as frustrating as trying to write good papers myself!
| never objectively compared to all those other papers with competing
| algorithms.
What would you consider an 'objective' comparison? Most computational
geometry papers *do* compare their results with competitors. The
comparison is usually theoretical rather than experimental, but it's
certainly objective.
| Is there no way to get the academic world to produce a) readable
| papers (for outside of the field), and b) with more real-world
| usable results?
Good question.
The mirror-image of this question is just as reasonable, though. Can
the business world give produce problems concrete enough for academics
to solve, without bogging them down in technical (and advertising)
jargon?
ShemShuHor
An algorythm, how abstract it is, cannot escape from being
intrinsicaly made for a specific abstract machine.
there is no such thing as an "algorythm alone" ,
every single algorythm makes assumptions on the abstract machine
it operates on ( the machine could even be the brain itself, with its
arythmetical capabilities)
and there is always an abstract machine.
Now, from this, we see that what you are looking for is not a separation
between
algorythm and implementation, but more likely the separation between the
behaviour and
the abstract Machine+Algorythm.
Let me explain:
Let's say that an algorythm processes an input (from an input space)
to produce an output(from an output space), and this ON a particular
abstract machine.
So actually if you are given a map from inputs to outputs, you can
theoretically
consider the set of all pairs of (Abstract Machine, Algorythm) that will
produce the same
outputs from the same inputs.
If you choose a particular Abstract Machine, you will probably still get
many different algorythms
that do the job, ie: that show the same "behaviour" (map: inputs ----->
outputs )
Therefore, it is not a compiler that you look for but for a programmer, a
device that,
given an abstract machine and an algorythm, will be able to produce an
algorythm for any other
(sufficiently powerfull) abstract machine:
(AM1,Algo1) <----same behaviour---> (AM2,Algo2)
(the programming machine produces Algo2)
if you think about it you will realise that it is basically what we all do
when "programming"
something:
you first think about the problem resolving it with your brain as an
abstract machine,
the algorythm being your reasonning. Then you map this to your (Computer, X)
and you find X the algorythm that when run on the Abstract machine Computer
will exibit
the same behaviour : it will give the same outputs for the same inputs:
(Brain, Reasonning) <---same behaviour---> (Computer, X)
(the programming machine produces X)
It is definitely a challenging project to design such a device,
but not impossible, many devices actualy operate similarly.
The problem is to replace compilers with this technology.
You will then be able to code in any given "primary" abstract machine,
and the "programming machine" will write the best ever possible code for the
particular
target machine, doing optimizations that sometimes involve changing
COMPLETELY
the first principle of the original algorythm.
The important is that the result is the same.
(completely different theoretical fundations could be used,
imagine that you code in C a factorization program on a abstract PC
and that you target a Quantum Computer!! )
AI is definitely the field that will give such results, as it requires
"reasoning"
that up to know belongs solely to humans...
Loďc Royer
Toby Sharp <TSh...@Serif.com> wrote in message
news:A%8p5.1088$3Q6....@newsread2.prod.itd.earthlink.net...
Toby Sharp
> On definition of algorithm is:
> "An algorithm is a set of rules that specify the order and kind of
> arithmetic operations that are used on specified set of data".
>
> Thus (x+x) and (x *2 ) represent two different algorithms to
> accomplish the same objective: "make some quantity twice the value of
> x"
In the terms I was using, I would count that as two different
implementations known to be equivalent by the compiler. Both would be
candidates for use within the one algorithm.
> [snip]
> >At this point, most people would probably suggest leaving the code in C
and
> >re-compiling when new compiler versions are released to reflect new
target
> >CPUs. But this is not really satisfactory for critical performance. C
will
> >use fixed-point or floating-point depending on what you told it to use.
>
> Under the above definition of alogrothm, using fixed-point or floating
> point changes the algorithm.
Again, in my terms, this really is an implementation difference, not an
algorithmic one. The main differences will be accuracy and speed. Known
allowable error determines whether fixed-point is a candidate for an
implementation. If so, speed determines which is used in the actual
implementation. Both achieve results that match the algorithm description,
which is at a higher level.
> What you seem to be describing is a process that might modify the
> algorithm or the implementation of an algorithm to achieve the "best"
> executable image. What is best?
The fastest implementation that achieves the desired results.
Toby Sharp
Jeff Erickson <je...@cs.uiuc.edu> wrote in message
news:rBip5.243$I4.1...@newsread1.prod.itd.earthlink.net...
> "Toby Sharp" <TSh...@Serif.com> writes:
> | We might be able to solve this problem if there were some way to
> | describe algorithms apart from their implementations.
>
> preposterous. OF COURSE there are ways to describe algorithms apart
> from their implementations. Look at ANY algorithms textbook, or for
> that matter, almost any graphics textbook.
Hold on. Yes, algorithms are described very effectively by English, and
pseudo-code in many textbooks. That's great because it allows humans to
understand the workings and the flow of the algorithm so that, if they
choose, they can implement it in whatever programming language they like.
But I am proposing a way to describe algorithms which a computer can read,
in a language that can be parsed with well-defined meanings. But it should
still retain a difference from "source code", ie. not an implementation of
the algorithm. Very much like the algorithms in text books, but probably
with a lot more detail specified. These text books tend to have preceding
paragraphs saying (for example) "Here, x is always even, and notice that y <
x always", etc.
> This is probably just a cultural difference in how we define the word
> "algorithm". In my opinion, algorithms are abstract processes, not
> limited to any particular hardware, operating system, or programming
> language. Your mileage may vary.
[snip]
> I argue vehemently in the algorithms classes I teach that source code
> is absolutely the wrong language to describe algorithms.
Absolutely. Hence the heading "separating algorithms from implementations".
> Algorithms
> are meant to be communicated to human beings.
Why not have a way to communicate them to computers too? Why not give a
computer a chance to find an efficient implementation of an "abstract" but
well-defined algorithm?
shankar n. swamy
Toby Sharp <TSh...@Serif.com> wrote:
>
>
>For example, multiplication is at least as computationally expensive as
>addition, so (x + x) should be prefarable to (x * 2). But what about (x *
>3)? Whether 'tis best to use one multiplication here or two additions
>depends entirely on the target CPU, and therefore is subject to frequent
>review, along with many, many other issues. Suddenly, your hand-crafted code
>is no longer optimal, so you must re-write it if you still want it to be as
>fast as possible. This isn't what life should be about.
>
>At this point, most people would probably suggest leaving the code in C and
>re-compiling when new compiler versions are released to reflect new target
>CPUs. But this is not really satisfactory for critical performance. C will
>use fixed-point or floating-point depending on what you told it to use. It
>doesn't know about acceptable errors, nor does it know anything about the
>nature or range of input data. For example, it will never use alpha instead
>of sin(alpha) when alpha is small; and rightly so, for no-one said it
>should. And as for exploiting parellism? Well, Intel's C/C++ compiler claims
>automatic vectorisation for using their SIMD extenstions, but personally
>(having tried their compiler) I certainly wouldn't trust my inner loops with
>it.
>
>We might be able to solve this problem if there were some way to describe
>algorithms apart from their implementations. Such a description would need
>to be sufficiently concrete to allow an implementation to be derived, but
>needs to be sufficiently flexible to allow many different implementations.
>
To drive to this point, earlier you gave the example of computing '2x' in
two different ways, ans x+x and as 2*x. But there are you are really
talking about two different algorithms! Since these are really two different
algorithms, there is no way to capture both of them, simultaneously in a
single abstraction. You could generalize the problem that they solve in
a single abstraction - "to double a given number" - but not the two algorithms.
>
>These could then be tested for speed, or various trade-offs could be chosen
>on the basis of knowledge of a target CPU. There would need to be a way to
>state assumptions on the range and properties of input data. Knowledge of
>these properties is what makes hand-tuned code able to be more efficient.
>Acceptable errors could be defined where appropriate. Algorithms could be
>described in ways which exploit parellelism, where appropriate, since this
>is a strong direction for forthcoming CPUs.
>
>Then a very, very clever compiler could spend a lot of time looking at the
>algorithm description, assembling instructions into implementations, testing
>sample data, and making changes as appropriate. If successful, the compiled
>code should rival that of the hand-tuned implementation. However, the
>algorithm doesn't change with the CPU, so neither does its description. It
>can be recompiled later to generate a new implementation that benefits from
>the features of a new CPU.
>
>
>The crux of the idea is to have a new language which describes algorithms
>separately from implementations. The language also provides a way to give
>extra information about supplied input and required output, so that highly
>optimised code can be created. A compiler goes into great detail to find the
>best implementation for the supplied algorithm information.
>
Don't we already have a plethora of such languages from MIX to english?
Algorithms, by definition, ARE distinct from implementations. However,
at times people tend to use a fully functioning programming language like C
or Pascal or what have you, or a near functioning programming language like
MIX. At times, people ask me about how fast is that algorithm vs this
algorithm. What is meant (or, so I hope :-) is, given the best implementations
of both the algorithms, given the same data set, given same platform etc,
which implementation would be faster.
Most modern programming languages offer, to varying extents, the ability to
tune the generated code to the characteristics of the input, and to the known
properties of the output. In C/C++, for example, different datatypes to
represent numbers, further the capability to tag "volatile" types etc are
some examples.
>
>So, has anyone done it? Suggested it? Any thoughts on whether theoretically
>possible? Or practically feasible? All comments welcome at this stage.
>
Yes, people have done it; we have all been using them. I think you are
essentially asking to push the limits of the current day compilers
further, and, I don't see why we need to invent a new language
either a programming language for writing code, a language beyond english,
"pseudocode", MIX, diagrams, figures etc for describing algorithms.
But, I do not think we are yet at a point where, you describe an algorithm
in english, with constraints on inputs, and on expected outputs, then the
computer program will take it and generate an efficeint program for it.
We are nowhere near such program generator programs.
- shankar swamy
Christer Ericson
>christer...@playstation.sony.nospam.com (Christer Ericson) writes:
>| I've seen many algorithm descriptions given in plain text that leave
>| out those all-important details, making them, if not impossible, at
>| least very difficult to implement.
>
>Most computer scientists (and I include myself here) do not know how
>to write. We are trained in analytical thinking, not in clear
>communication. We talk to ourselves in techno-babble, forgetting that
>other people don't speak our language. I don't believe that anyone is
>deliberately trying to confuse people. We just don't know how to say
>things any other way.
My personal experience is that this obscurative style is implicitly
fostered in the academic world. For the reason you are stating, that
people are not trained writers, they turn to the writings of their
more experienced colleagues and to other papers in the field and
mimic their abstruse(*) style.
Basically, it's a vicious feedback loop that must be broken!
I fell trap to this system myself while at university, and only by
being outside looking in do I now realize how bad it is.
That's the major problem, IMO. However, there's also the problem of
language snobbishness. There really is no need for all the jargon,
the dictionary words and the latin. Unfortunately, I'm about as
guilty as charged here, so mea culpa.
(*) Abstruse is an abstruse word and should be avoided, unless
you're trying to make a point.
>On the other hand, some algorithms are inherently technical and
>therefore difficult for ANYONE to understand. No matter how clearly
>these algorithms are described, new readers will have to work hard to
>understand them. This is less true for readers with some theoretical
>training -- which is one reason that CS students should take
>math and algorithms classes -- but even that may not be enough.
Yes, this is a challenge to all the CS departments out there.
Unfortunately, it is my experience that CS students aren't very
interested in math and that e.g. calculus is seen as something
that they couldn't possibly ever have a use for. (And I was once
of this mindset myself as a CS student.)
CS departments really must try to motivate their students to learn
as much math as possible, or rather, math departments much do more
to sell their courses to the CS students. This is certainly possible.
Boy do I remember my linear algebra class as being boring, but had
it been presented as "this is the basis of all 3D graphics", everyone
would have sat straight up, eyes and ears wide open.
As for the inherently technical algorithms, this is simply a matter
of the author having enough self-insight to realize the difficulty
of the topic, and treating the writeup accordingly. If it's difficult,
pay more attention to the presentation. Give examples.
Basically, the recipe for writing a readable paper is to treat
the writeup as something you would hand out to your average 3rd
year students and expect them to (mostly) understand. Give the
paper the same attention as you would your lecture notes.
>Even unimplementable algorithms provide interesting mathematical
>insights; those insights are the true goal of theoretical research,
>NOT the algorithms themselves.
>
>That may be the biggest hurdle. Theoreticians and practitioners have
>different goals, different motivations, and different standards. That
>makes it far too easy for each side to dismiss the other as being
>clueless.
I don't think anyone is dismissing anyone as being clueless. While
the communication should ideally go both ways, I do think that
theoreticians have a greater responsibility in making their work
accessible to practitioners than the other way around. Certainly so
if they're government funded (as they are).
>| [The computational geometry crisis report]
>|
>For those of you who don't know what Crister is talking about, you can
>read all about it here:
> http://www.uiuc.edu/~jeffe/cmopgeom/taskforce.html
Jeff meant to write:
http://www.uiuc.edu/~jeffe/compgeom/taskforce.html
>| I still see lots of impractical unimplemented (and, sometimes
>| unimplementable) algorithms presented in that 'wonderfully'
>| unreadably obsfuscated style that academicians love.
>
>Agreed, except for the part about academics loving obfuscation.
>Slogging through a badly-written paper about a good result is deeply
>frustrating.
>
>Almost as frustrating as trying to write good papers myself!
I addressed this above. I do think that there is an implicit
love for obfuscation -- in the mimicing of style.
The frustrating part is that there aren't hardly any well-written
papers. Can you name one of the top of your head? Compare this
to how many bad papers you can pull out of your paper archive in
10 seconds flat.
While at Umeå University (in Sweden) I tried to address the problem
in part by suggesting that the Swedish Language Committee's (Svenska
språknämndens) book "Swedish writing rules" (Svenska skrivregler):
http://www.spraknamnden.se/SSN/skrivregler.htm
should be required reading for all of our CS students for
their report writing. Unfortunately, I believe nothing much
came out of this.
Sadly, it might be true that you have to infuse people with as much
passion for language (whether English or Swedish) as for their thesis
topic to make them care about the readability of their paper
presentations. However, as this CNN article reports, it's going
to be an uphill battle:
http://www.cnn.com/2000/US/08/24/education.report/index.html
>| never objectively compared to all those other papers with competing
>| algorithms.
>
>What would you consider an 'objective' comparison? Most computational
>geometry papers *do* compare their results with competitors. The
>comparison is usually theoretical rather than experimental, but it's
>certainly objective.
I was thinking primarily of the presentation of experimental results.
I'm not saying that results are deliberately doctored, but in many
cases it seems clear that either a) only results in favour of the
current method are presented, or b) those other comparative tests
that would have put the current method in bad light were never
performed. Both are equally bad.
I don't really see how else you can explain a group of similar
papers where every single presented algorithm overall beats all
of the other algorithms in a cyclic fashion.
I presume this is a problem with the refereeing of papers where
results of the type my-method-A-beats-his-method-B are deemed more
important than reporting I-tried-method-A-B-and-C-and-neither-worked.
I find this a very big flaw in *all* academic papers. Sometimes
it's not the result that is interesting, but the road which was
travelled in getting to the result. Unfortunately, no papers
(not even technical reports, that do not have the size limitations
that journal papers have) present the cast-away ideas that were
tried but that didn't work.
Mathematicians are exceptionally good at this. They present a
surprise look-at-this-wonderful-formula and then they present
the shortest possible proof of the result, without any hint
whatsoever as to how the solution originated.
>| Is there no way to get the academic world to produce a) readable
>| papers (for outside of the field), and b) with more real-world
>| usable results?
>
>Good question.
>
>The mirror-image of this question is just as reasonable, though. Can
>the business world give produce problems concrete enough for academics
>to solve, without bogging them down in technical (and advertising)
>jargon?
Yes, I'd say it can. But, until you just did now, did any
academician ever ask?
Jeff Erickson
| I am proposing a way to describe algorithms which a computer can
| read, in a language that can be parsed with well-defined meanings.
| But it should still retain a difference from "source code", ie. not
| an implementation of the algorithm.
I would argue that if you're communicating an algorithm to a computer
and getting actual executable code out the other end, then BY
DEFINITION you have an implementation of the algorithm.
What you are really asking for is a very high level programming/
specification language.
| > Algorithms are meant to be communicated to human beings.
| Why not have a way to communicate them to computers too? Why not
| give a computer a chance to find an efficient implementation of an
| "abstract" but well-defined algorithm?
The word you're looking for is "compiler".
Remember, the 'abstract machine' that you are writing your C (or
whatever) programs for has very little resemblance to the actual
device you compute with. Instructions are reordered both by the
compiler and the CPU. Loops and subroutine calls are optimized out of
existence. Modern CPUs speculatively take branches and backtrack if
they discover they're wrong. And so on. And you don't worry about
any of it.
Compared to raw machine code, C (or whatever) programs are already
abstract algorithm representations. Just not abstract enough.
Jeff Erickson
| To drive to this point, earlier you gave the example of computing
| '2x' in two different ways, ans x+x and as 2*x. But there are you
| are really talking about two different algorithms!
I disagree -- x*2 or x+x or x<<1 are three different implementations
of the algorithm "2x".
Dr John Stockton
JRS: In article <rBip5.243$I4.1...@newsread1.prod.itd.earthlink.net>
of Thu, 24 Aug 2000 23:55:03 seen in news:comp.lang.asm.x86, Jeff
Erickson <je...@cs.uiuc.edu> wrote:
>| The crux of the idea is to have a new language which describes
>| algorithms separately from implementations.
>
There is considerable potential for ambiguity in any local dialect of
English, unless extremely carefully written, in which case it tends
towards the bulky and unreadable (e.g. legalese).
Moreover, some Americans & some British seem to believe that they use
the same language as each other; and then there are the Indians,
Antipodeans, Canadians, Scandiwegians, etc ...
Algol 60 was an early attempt at describing a limited class of
algorithms in detail without being implementation-specific; AIUI, the
initial Algol planning was intended to produce something for a human,
rather than a compiler, to read.
***
If a language describes algorithms well enough for competent humans to
understand, then IMHO it will be possible nowadays to arrange a compiler
or interpreter such that a computer can execute the algorithms (if
provided with necessary hardware). A description in the language will
therefore describe implementations.
--
© John Stockton, Surrey, UK. j...@merlyn.demon.co.uk / JR.St...@physics.org ©
Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct 4-line sig. separator is as above, a line precisely "-- " (SoRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)
Chris Williams
> | algorithms separately from implementations.
>
English doesn't compile.
Daniel M. Pfeffer
news:rBip5.243$I4.1...@newsread1.prod.itd.earthlink.net...
> "Toby Sharp" <TSh...@Serif.com> writes:
[snip]
> I argue vehemently in the algorithms classes I teach that source code
> is absolutely the wrong language to describe algorithms. Algorithms
> are meant to be communicated to human beings. Source code includes
> too much focus on (in the context of an algorithms class) irrelevant
> details. Obviously those details have to be worked out in any actual
> implementation, but they usually have little or no effect on the
> design or analysis of the abstract algorithm and therefore should
> usually be omitted from the high-level description.
>
> | The crux of the idea is to have a new language which describes
> | algorithms separately from implementations.
>
> What's wrong with English?
What is required to describe algorithms is a language which allows no
ambiguities. An appropriate subset of English might be adequate, but that
subset should be rigorously defined. To date, I know of no standardisation
effort for an ADL (Algorithm Description Language).
Daniel Pfeffer
shankar n. swamy
Chris Williams <aa...@gol.com> wrote:
>> | The crux of the idea is to have a new language which describes
>> | algorithms separately from implementations.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
>> What's wrong with English?
>
>English doesn't compile.
>
Algorithm descriptions don't need to be compiled; just their implementations.
- shankar swamy
----------------------------------------------------------------------------
sha...@cs.indiana.edu
Jeff Erickson
| je...@cs.uiuc.edu (Jeff Erickson) wrote:
| >christer...@playstation.sony.nospam.com (Christer Ericson) writes:
| Unfortunately, it is my experience that CS students aren't very
| interested in math and that e.g. calculus is seen as something
| that they couldn't possibly ever have a use for.
Too true. As a result, many CS majors do quite badly in courses that
require any significant math -- numerical analysis, scientific
computing, algorithms, and yes, even computer graphics.
| CS departments really must try to motivate their students to learn
| as much math as possible, or rather, math departments much do more
| to sell their courses to the CS students. This is certainly possible.
That's not the math department's job! Yes, instructors should
motivate their students, but the math department should not be at the
service of computer scientists, or engineers, or anybody but
mathematicians. (Unless they teach linear algebra purely as a service
course to CS majors, in which case, they're de facto CS instructors.)
Here, again, we have a cultural difference between academia and the
real world. To academics, the primary purpose of a university
education is NOT to prepare students for jobs in the real world. The
purpose of a university education is to expose students to ideas, and
(hopefully) train them to learn and develop new ideas on their own.
Many people are amazingly successful in the real world, in highly
technical jobs, without a college degree. Bill Gates is a perfect
example.
| Basically, the recipe for writing a readable paper is to treat
| the writeup as something you would hand out to your average 3rd
| year students and expect them to (mostly) understand. Give the
| paper the same attention as you would your lecture notes.
I agree. I usually aim my papers at 2nd or 3rd year CS grad students,
because I need to assume a certain basic vocabulary that your average
3rd year CS major simply doesn't have. Most academics target their
peers, and so to their peers, their papers are perfectly readable.
| I don't think anyone is dismissing anyone as being clueless.
Trust me, it happens. I know a fairly famous computer graphics
researcher who is fond of the "lie on the beach" criticism of
theoreticians:
You theoreticians never have to do any real work. You can just
lie on the beach, soak up some rays, sip your margaritas. Every
so often, you have an idea, you spend ten minutes writing it
down, and then you go back to your tan. We can't get away with
that; we have to build a real functioning system.
My kneejerk response is "Yes, but at the end of the day, I have an
idea, and all you have is six minutes of videotape." but that's not
any fairer to him than his criticism is to me.
| While the communication should ideally go both ways, I do think that
| theoreticians have a greater responsibility in making their work
| accessible to practitioners than the other way around.
I disagree.
| The frustrating part is that there aren't hardly any well-written
| papers. Can you name one of the top of your head?
Sure, here are two of my favorites. One of them should be well-known
to graphics folks as the O(n log^* n)-time polygon triangulation
algorithm.
@article{c-garot-99
, author = "T. M. Chan"
, title = "Geometric Applications of a Randomized Optimization Technique"
, journal = "Discrete Comput. Geom."
, volume = 22
, number = 4
, year = 1999
, pages = "547--567"
}
@article{s-sfira-91
, author = "R. Seidel"
, title = "A simple and fast incremental randomized algorithm
for computing trapezoidal decompositions and for
triangulating polygons"
, journal = "Comput. Geom. Theory Appl."
, volume = 1
, number = 1
, year = 1991
, pages = "51--64"
}
Of course, there's a high correlation between which papers I consider
well-written and which papers I think have the most interesting
results. A clear paper with a boring subject is still boring.
| I'm not saying that results are deliberately doctored, but in many
| cases it seems clear that either a) only results in favour of the
| current method are presented, or b) those other comparative tests
| that would have put the current method in bad light were never
| performed. Both are equally bad.
I agree completely. The first question I ask whenever I read an
experimental paper about a new algorithm is "When is your algorithm
WORSE than its predecessors?" If the paper doesn't answer that
question, I assume the results are skewed.
But I don't think of those as theoretical papers.
| Unfortunately, no papers (not even technical reports, that do not
| have the size limitations that journal papers have) present the
| cast-away ideas that were tried but that didn't work.
Some do, but you're right, it's rare. Nobody's really interested in
negative results. (I vaguely remember a semi-serious suggestion to
found a new Journal of Negative Results a few years ago. It never
went anywhere.) I suppose part of the reason is that people don't
want to dwell on their mistakes. "Why should I spend all this time
writign about what doesn't work,
| Mathematicians are exceptionally good at this. They present a
| surprise look-at-this-wonderful-formula and then they present
| the shortest possible proof of the result, without any hint
| whatsoever as to how the solution originated.
Culture. Often the proof technique is the real result, not the
theorem. By and large mathematicians have much higher expectations of
their readers than computer scientists. A typical math paper could
take a senior grad student about one day per page to read, and this is
considered good. After all, why waste time writing stuff that the
reader can figure out on their own, given enough time?
| >Can the business world produce problems concrete enough for
| >academics to solve, without bogging them down in technical (and
| >advertising) jargon?
| Yes, I'd say it can. But, until you just did now, did any
| academician ever ask?
All the time. Whenever someone from the real world asks an academic
for something "useful".
George Neuner
>>English doesn't compile.
>>
>
>Algorithm descriptions don't need to be compiled; just their implementations.
>
The descriptions must be effectively communicated to be worthwhile.
There is an ongoing linguistic study of inner city dialect evolution
in three major US cities - public broadcasting did a piece on it last
year, I don't recall which university is sponsoring it.
The researchers found that over the course of 20 years, the vowel
sounds had been rotated and randomized in each of the inner city
neighborhoods in the study. The result was that people from one city
could not understand the dialects spoken in the other cities. So much
for spoken English.
Since US primary schools began to teach that the idea was more
important than the delivery, writing and reading skills have been in
precipitous decline. So much for written English.
Can't use mathematics as a common language, US schools don't teach it
anymore. I guess we're stuck with psuedo-code ;^)
George Neuner
Dynamic Resolutions, Inc.
===================================================
The opinions expressed herein are my own and do not
reflect the opinions or policies of my employer.
===================================================
Toby Sharp
> "Toby Sharp" <TSh...@Serif.com> writes:
> | I am proposing a way to describe algorithms which a computer can
> | read, in a language that can be parsed with well-defined meanings.
> | But it should still retain a difference from "source code", ie. not
> | an implementation of the algorithm.
>
> I would argue that if you're communicating an algorithm to a computer
> and getting actual executable code out the other end, then BY
> DEFINITION you have an implementation of the algorithm.
You contradict yourself.
Algorithms described in text books are entirely separate from their
implementations (as you say), yet one expects that an implementation can be
derived from those descriptions with the relevant perennial knowledge. When
one arrives at that implementation, that doesn't change the nature of the
original description. It was an algorithm still, not an implementation.
> What you are really asking for is a very high level programming/
> specification language.
Maybe. In a sense, it would be very high-level. But whereas a language like,
say, VB is a broad HLL, this language would be a very deep HLL. What I mean
by this is that it would be a highly efficient but time-consuming
compilation suitable only for well-described algorithms. It would benefit
time-critical code rather than the broad swep of applications. It's not
intended as a replacement for any other language, but as an addition.
> | > Algorithms are meant to be communicated to human beings.
> | Why not have a way to communicate them to computers too? Why not
> | give a computer a chance to find an efficient implementation of an
> | "abstract" but well-defined algorithm?
>
> The word you're looking for is "compiler".
Hey, no sarcasm required! If you take the trouble to read the original post
you will find the word "compiler" there very clearly.
> Remember, the 'abstract machine' that you are writing your C (or
> whatever) programs for has very little resemblance to the actual
> device you compute with. Instructions are reordered both by the
> compiler and the CPU. Loops and subroutine calls are optimized out of
> existence. Modern CPUs speculatively take branches and backtrack if
> they discover they're wrong. And so on. And you don't worry about
> any of it.
I absolutely DO worry about it!! Perhaps you have too much faith in your C
compiler, or perhaps you have never concerned yourself with time-critical
code.
These new processors don't work by magic. They still need careful
instruction scheduling so that their ROBs (re-order buffers) don't become
saturated. Cache pollution causes memory stalls, over which you have no
control in C. Most C compilers don't support new Intel SIMD instructions or
other parellel processing. And an incorrect branch prediction requires a
complete flush of the processor pipeline - that's a 20 stage pipeline for
the new Pentium 4!
If *you* don't worry about it, then it's not surprising that you can't see
the point of my original post. C code will do just fine for your
implementations.
Toby Sharp
I'm sure you're right about this, but maybe we need to take some
intermediary steps before replacing programmers copmletely. (Plus, I would
be out of a job!) For now, maybe it's possible to have a small well-defined
set of behaviours that can help with a small set of optimisation issues
given a certian level of abstraction.
All the same, very interesting stuff...
--
--------------------------------------
Toby Sharp, B.Sc. (Hons), G.I.M.A.
Senior Software Developer
Serif (Europe) Ltd
--------------------------------------
ShemShuHor <NOSPA...@NOSPAMrabvent.fr> wrote in message
news:sqdaln7...@corp.supernews.com...
Toby Sharp
Multiplication is defined as repeated addition.
2 * x is therefore identically x + x, by definition of 2 and the
multiplication operator.
Look it up in the 9 axioms of real numbers.
2x and x+x are therefore *identically equal* in any theoretical or abstract
setting.
The only difference between the two may come when you compute these
quantities on a machine by using different machine instructions.
Now, that *surely* must constitute an implementation difference ONLY.
George Neuner
>anymore. I guess we're stuck with psuedo-code ;^)
^^^^^^
Sorry, typo!
George
Ben Blish
Hi, Toby.
Step back from the problem for a minute. As other posts have gone into,
sometimes things are simply looked at in far too complicated a manner.
No matter what you CALL something, it "is what it is". Perhaps that's the worst
sin of academics, were there such a sin, that of delineating things by terms
and concepts others are unlikely to understand, even more than far too buried
in gibberish. (re presenting algorthims, again to quote another poster, what's
wrong with English?) I can't tell you the number of times I've slogged though
some incredibly terse academic-ese to wind up, sometimes PAGES later, saying "I
can't BELIEVE this took X pages to say!" because having (finally) figured out
what the writer was trying to say, I can now say it in about two sentences. Or
five lines of code. I completely, absolutely, utterly disagree with the person
who said that code is a poorer vehicle than the pin dancing that is so evident
in many texts that purport to deliver information about algorithms, or even
pseudo code (or blunders like using renderman's proprietary sublanguage...)
Write it in something you can be pretty sure everyone else who wants to
understand or test your ideas has access to, test it to death, make it work
preceisely according to your understanding, and you are *guaranteed* that it
embodies everything you meant to communicate. You are then free to go ahead and
describe the CODE in terms of your idea, and you'll probably find that your
idea has enjoyed considerable illumination in the process. And you'll probably
never again write something as buffonish as "Given a model F(P)=0 and a ray
R(t)=0+tD with origin O and direction D, the intersection point is simply
R(T[sub]hit)." Gah. Anyway...
I think C is ideal for explanations, as it's most widely known, and it doesn't
encourage you to hide things, unlike C++.
Back to the point. in the simple cases of 1+1, 1<<2, 2*1, these are all black
boxes that have the following property which (I think) is the main issue here:
Inputs: two integer 1's
Outputs: integer two.
The compiler needs to know the inputs precisely, as you say, and the outputs
precisely, as you say, and then it must know it's black boxes precisely, as
well as (considering modern processors) how they interact with other black
boxes that are or may be executing nearby in time/pipeline. And that's the
killer. If it knows those things, it can pick the best one to use. Can it know
those things? Probably not, not unless we get real AI.
Thinking this way, it can be considered that what you're looking for is a
compiler of black boxes; something with a great deal of deep knowledge about
those boxes, and how they, in all their infinite possibilities, interact. In
other words, an intelligent programmer, spec book for the CPU immediately
handy, profiler and untowardly nasty test cases hot and ready to shove down the
throat of the resulting code.
I *love* the idea, but the only solution I know of eats pizza. :-)
Regards,
Ben
Jeff Erickson
| > and getting actual executable code out the other end, then BY
| > DEFINITION you have an implementation of the algorithm.
| You contradict yourself.
What, again?
| Algorithms described in text books are entirely separate from their
| implementations (as you say), yet one expects that an implementation
| can be derived from those descriptions with the relevant perennial
| knowledge.
Yes, but by a human being. If a computer can understand it without
human intervention (which seems to be what you're proposing), it's an
implementation.
| > Remember, the 'abstract machine' that you are writing your C (or
| > whatever) programs for has very little resemblance to the actual
| > device you compute with. [...] And you don't worry about any of it.
| I absolutely DO worry about it!!
Oops.... I forgot about time-critical' code. But shoudn't that be
done in assembly code anyway?
Jeff Erickson
| Within the set of real numbers, 2 is defined as 1 + 1.
| Multiplication is defined as repeated addition.
Er... I think you mean integers, not real numbers. You'll have a hard
time multiplying pi and sqrt{2} using repeated addition.
Jeff Erickson
You could have said that more concisely.
I'm the person that you think you completely, absolutely, utterly
disagree with. You don't. I agree with you compeltely, absolutely,
utterly that C is better than a lot of academic pin-dancing. But good
pseudocode is better than C.
Here's one reason: C forces you to declare types. Sure, if the type
does matter, the algorithm's presentation should reflect that. But if
the type DOESN'T matter, the algorithm's presentation should reflect
that, too. For example, many algorithms that work on "lists" work
equally well if the list is actually a singly-linked list, a
doubly-linked list, an array, a binary tree, a strand of DNA, a
sequence of words written on a piece of paper, or a set of signposts
in the desert. If it doesn't matter which of these you use, then your
description of the algorithm shouldn't pick one arbitrarily. The
specific abstract data type should be left completely unspecified.
Again, this may be a cultural difference. I describe algorithms to
communicate the major ideas. Anything that distracts from those ideas
is, in that context, pointless.
| Write it in something you can be pretty sure everyone else who wants
| to understand or test your ideas has access to, test it to death,
| make it work preceisely according to your understanding, and you are
| *guaranteed* that it embodies everything you meant to communicate.
I'm pretty sure most of the people who want to understand my ideas
have access to English. I'm not quite so sure about C compilers.
| I think C is ideal for explanations, as it's most widely known, and
| it doesn't encourage you to hide things, unlike C++.
Perhaps another reason I insist on pseudo-code rather than C is that
in my experience, most programmers couldn't write readable C code if
it would prevent the sun from exploding.
Academics have no monopoly on obfuscation!
Toby Sharp
> done in assembly code anyway?
>
Gggaaaahhhhh!!!! (head in hands)
...
Having established this, we are now ready for you to read the original post!
Toby Sharp
If x is a real number:
2 * x
= (1 + 1) * x by defn of '2'
= (1 * x) + (1 * x) by right distributivity (ring axiom)
= x + x by defn of '1' as multiplicative identiy
(division algebra axiom)
Now will someone please agree that 2*x is identically x+x, and that
different methods of computing this quantity as part of a larger computation
constitute a difference in implementation and not in algorithm?
Jeff Erickson <je...@cs.uiuc.edu> wrote in message
news:%kmr5.3137$9N1....@vixen.cso.uiuc.edu...
Dave Eberly
> OK, I'll rephrase, using only the axiomatic properties of the real
numbers:
>
> If x is a real number:
>
> 2 * x
> = (1 + 1) * x by defn of '2'
> = (1 * x) + (1 * x) by right distributivity (ring axiom)
> = x + x by defn of '1' as multiplicative identiy
> (division algebra axiom)
>
> Now will someone please agree that 2*x is identically x+x, and that
> different methods of computing this quantity as part of a larger
computation
> constitute a difference in implementation and not in algorithm?
Your view:
Algorithm: compute twice a real number x
Implementation 1: Compute 2*x
Implementation 2: Compute x + x
My view:
Problem statement: Compute twice a real number x
Algorithm 1: Compute 2*x
Algorithm 2: Compute x + x
Implementation of Algorithm 1 in C:
float TwiceReal (float x) { return 2*x; }
Implementation of Algorithm 1 in Pascal:
function TwiceReal (x : real) : real; begin TwiceReal := x+x; end;
According to terminology I am familiar with, "algorithms"
are methods that you develop to solve problems. And
"implementations" are the realization of the algorithm.
I think the essence of the thread hinges on how you are
trying to define these terms differently than most folks
use them.
--
Dave Eberly
ebe...@magic-software.com
http://www.magic-software.com
Dave Eberly
function TwiceReal (x : real) : real; begin TwiceReal := 2*x; end;
Ben Blish
>| Gah.
>
>You could have said that more concisely.
Yes, I could have. :-)
>I'm the person that you think you completely, absolutely, utterly
>disagree with. You don't. I agree with you compeltely, absolutely,
>utterly that C is better than a lot of academic pin-dancing. But good
>pseudocode is better than C.
I don't agree. Because (a) you can't *test* pseudocode, and (b) pseudocode is
some random thing that the author feels like defining, today, whereas C is a
well defined language in which what one writes has a predefined behaviour. It's
more transportable from mind to mind, in other words, and (c) transistion from
pseudocode to working example for the reader (or victim, in the worst cases!)
is a process that depends on the reader understanding BOTH the pseudocode and
the target language, and (d) since as (a) points out, the pseudocode wasn't
tested - can't be, in fact - the transistion may be even less well defined, as
the pseudocode may well leave out very important details in getting the example
working, which does not happen with a working, tested program.
>Here's one reason: C forces you to declare types. Sure, if the type
>does matter, the algorithm's presentation should reflect that. But if
>the type DOESN'T matter, the algorithm's presentation should reflect
>that, too.
> For example, many algorithms that work on "lists" work
>equally well if the list is actually a singly-linked list, a
>doubly-linked list, an array, a binary tree, a strand of DNA, a
>sequence of words written on a piece of paper, or a set of signposts
>in the desert. If it doesn't matter which of these you use, then your
>description of the algorithm shouldn't pick one arbitrarily. The
>specific abstract data type should be left completely unspecified.
Jeff, on the one hand, you're counting on your reader to be good enough at
generalizing your pseudocode presentation (which they may not understand
completely, a likely motivation for reading it) into the reader's target
language. On the other hand, you apparently don't think they've got the
competance to generalize a working example into similar (or not so similar)
environments unless those environments are left unspecified (abstract). If
you're discussing a concept that's list based, and it'll work in any list,
using an example list of a particular type is no sin, as long as you mention
this is not a restriction, just a vehicle for the example.
Isn't this true for anything, anyway? If I talk about addition, and then throw
2 and 2 in there, have I ruined the definition or understanding of addition by
having introduced a non-abstract example? Have I forced the reader into a mode
that makes them think that addition only works with integers? Have I forced
them into thinking it only works with 2's? Hardly; and that's where your
abstraction argument leads. Furthermore, I can *say* that this process works
with real numbers, with vectors, with volumes, etc., without in any way
detracting from the usefulness of the concrete example.
Consequently, my position is that concrete C examples that *work* are better
than abstracted pseudocode examples that can't work at all.
>Again, this may be a cultural difference. I describe algorithms to
>communicate the major ideas. Anything that distracts from those ideas
>is, in that context, pointless.
>
>| Write it in something you can be pretty sure everyone else who wants
>| to understand or test your ideas has access to, test it to death,
>| make it work preceisely according to your understanding, and you are
>| *guaranteed* that it embodies everything you meant to communicate.
>
>I'm pretty sure most of the people who want to understand my ideas
>have access to English. I'm not quite so sure about C compilers.
English can't be tested. That means that both the writer may make errors, since
there is no mechanism to validate a description, and that the reader may make
errors, since they have to translate in order to implement a test bed. C
compilers are ubiquitous; and they're even free, if one wants to go that route.
And they're cross-language, come to that - a native polish speaker can
understand a C program as easily as an English speaker; but they *won't*
understand your description (and likely not your pseudocode, either!) I've even
got a C compiler for my "classic" 1970's era SWTPC microcomputer. :-)
>Perhaps another reason I insist on pseudo-code rather than C is that
>in my experience, most programmers couldn't write readable C code if
>it would prevent the sun from exploding.
True in many cases. Does that mean that somehow, readable pseudocode is likely
to come from anywhere? If it is your intent, as an author, to write something
in as readable a fashion as possible, then I would say you're as likely to be
able to write it in C as in pseudocode, however, in c, you're able to test your
work. The disadvantages of pseudocode are horrendous, and there is *no*
advantage over working code in some common language (and c is the *the* most
common language, hence my preference.)
By the way, I happen to be the author of a series of articles on c style and
clarity. :-)
>Academics have no monopoly on obfuscation!
Certainly not. But academics, at least as I see it, have the goal of
enlightening the rest of us, and so part of the job is to be as clear as
possible - it's basic to the idea. A programmer, on the other hand, is trying
to get a job done, often under time and funding constraints that are not
optimum or under the programmer's control. SO I tend to forgive programmers a
lack of clarity, and not academics. Besides... even when programmers write
without clarity, if the end product *works*, you at least know you're not
wasting your time trying to understand what they wrote! With pseudocode, you
may not know if it works OR if it's practical, until you've done the
programming yourself.
--Ben
Jeff Erickson
| (a) you can't *test* pseudocode
So what? Testing isn't good enough! The only way that I'll ever
really believe that an algorithm works is if I see (and understand) a
proof. And you *can* prove that pseudocode is correct.
| (b) pseudocode is some random thing that the author feels like
| defining, today, whereas C is a well defined language in which what
| one writes has a predefined behaviour.
Pseudocode is a fluid but rigorous method for describing algorithms
that will still be understandable when nobody programs in C. So
there. X-P
| (c) transistion from pseudocode to working example for the reader
| (or victim, in the worst cases!) is a process that depends on the
| reader understanding BOTH the pseudocode and the target language,
Absolutely right. I assume that the reader is a competent programmer,
which means that given a good description of any algorithm, they
should be able to implement it in the programming language of their
choice. This frees me (and the reader) to focus on the important
details of the abstract algorithm without worrying about language-
specific issues.
| (d) the pseudocode may well leave out very important details in
| getting the example working, which does not happen with a working,
| tested program.
Admittedly true. There are always unforseen details in translating
algorithms from one language to another (or from one system to
another, or even from one C compiler to another!)
| Jeff, on the one hand, you're counting on your reader to be good
| enough at generalizing your pseudocode presentation (which they may
| not understand completely, a likely motivation for reading it) into
| the reader's target language.
Absolutely right. I count on my ability to write clearly, and the
reader's ability to think abstractly and to code competently. If you
want code that you can plug into your program without understanding
how it works, talk to somebody else.
| On the other hand, you apparently don't think they've got the
| competance to generalize a working example into similar (or not so
| similar) environments unless those environments are left unspecified
| (abstract).
Not at all. I'm sure almost every decent programmer CAN translate one
specific instance into another. But remember, my goal is not just to
help programmers write code. My goal is to help the reader understand
the algorithm -- ideally, well enough that they can implement it
themselves from scratch without my help.
| If I talk about addition, and then throw 2 and 2 in there, have I
| ruined the definition or understanding of addition by having
| introduced a non-abstract example?
To take this to your logical extreme: If you define addition only in
terms of 2+2, then YES, you HAVE ruined the definition!! Examples are
absolutely essential, but they shouldn't be used as definitions.
| By the way, I happen to be the author of a series of articles on c
| style and clarity. :-)
:-) Good!
| Besides... even when programmers write without clarity, if the end
| product *works*, you at least know you're not wasting your time
| trying to understand what they wrote!
I suspect there's a fairly strong correlation between (a) how well a
program works, (b) how clearly the code is written, and (c) how well
the programmer understands the underlying abstract algorithms.
We're going around in circles; neither of us is convincing the other
of anything. I think we agree on one basic point: A well-written
algorithm description in any language (C, pseudocode, whatever) is far
better than a badly-written description in any language (pseudocode,
C, whatever). Maybe we should leave it at that.
Kenneth Sloan
*Algorithms* is what I do.
*Implementation* is what my assistant does.
This observation generalizes quite nicely across a wide range of
activities.
--
Kenneth Sloan sl...@uab.edu
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/info/faculty/sloan/
Toby Sharp
I'm sorry that this thread has digressed so far from the original point,
which may have been obscured by terminology differences.
In your teminology, what I was driving for is a compiler which can accept
input in terms of well-defined problem statement, e.g.
TWICE(x)
and try different algorithms
x+x, 2*x
to arrive at implementations (machine instructions) that can be tested for
speed and efficiency.
This example wasn't very challenging so here's another one:
Problem:
COS(x) : given(|x| < 0.01), allow_error(y)
-->
Algorithms:
cos(x), 1, 1 - x * x,
-->
Implementations in machine instructions.
Execute to test for greatest speed where result is within error.
Dave Eberly <ebe...@magic-software.com> wrote in message
news:8omhmh$tci$1...@slb1.atl.mindspring.net...
Jerzy Karczmarczuk
...
> Now will someone please agree that 2*x is identically x+x, and that
> different methods of computing this quantity as part of a
> larger computation constitute a difference in implementation
> and not in algorithm?
This is slowly becoming boring.
As all home-made philosophy...
The fact that the result of two *different* operations is the same
does not mean that the two *algorithms* are identical. A multiplication
is a multiplication, and an addition is an addition.
Shooting somebody, empoisoning him or hanging him give quite often
more or less the same results. The algorithms are still different,
and, please, don't call it a "difference in the implementation".
Unless you define in a serious, formal way the meaning of the word
"implementation". Dave Eberly - with my sincere respect - does not
do it well, since replacing the word "implementation" by
"realization" does not move us too far...
====
All this domain is fuzzy. Incremental, indexless, stream processing
methods applied to vectors are completely different from typical "C"
loops, yet they yield the same final results. But again, calling it
a "difference in implementation" is completely unjustified.
Jerzy Karczmarczuk
Caen, France.
Dave Eberly
news:39AF9176...@info.unicaen.fr...
> Unless you define in a serious, formal way the meaning of the word
> "implementation". Dave Eberly - with my sincere respect - does not
> do it well, since replacing the word "implementation" by
> "realization" does not move us too far...
Be prepared for the "circular dictionary problem".
Joseph O'Rourke
Jeff Erickson <je...@cs.uiuc.edu> wrote:
>I describe algorithms to
>communicate the major ideas. Anything that distracts from those ideas
>is, in that context, pointless.
This is the key point, I think, and why I agree with Jeff's position
(not surprising, coming from another academic). In my experience
describing algorithms in both pseudocode and in C, some algorithms
are resistant to being written in C code that is as transparent as the
ideas underlying it. Irrelevant data structure issues, or C language
limitations, tend to clutter the code and distract from the main points.
The ideal, perhaps, is to use both mechanisms: to first describe
the algorithm in pseudocode, and then redescribe it with heavily
annotated C code. This permits the latter discussion to focus on
the side issues and quirks and subtleties that often only emerge in real
code. I used this method in a textbook, but rarely does an author
have the time or space to describe an algorithm so lavishly.
ShemShuHor
since it started originaly with a very interesting interogation.
People don't understand each other, or fail to make the effort to
understand,
or even worst, they endlessly discuss in an "informal" way,
what turns out to be difficult problems that require a
strong formalism to be grasped.
let me repost this:
(you will see that the problem is more complex that the naive
implementation/algorythm duality.)
Loďc Royer
note:
Robert Posey
Toby Sharp wrote:
>
> Jeff Erickson <je...@cs.uiuc.edu> wrote in message
> news:rBip5.243$I4.1...@newsread1.prod.itd.earthlink.net...
> > "Toby Sharp" <TSh...@Serif.com> writes:
> > | We might be able to solve this problem if there were some way to
> > | describe algorithms apart from their implementations.
> >
> > Wow. To my theoretician's eye, this statement is absolutely
> > preposterous. OF COURSE there are ways to describe algorithms apart
> > from their implementations. Look at ANY algorithms textbook, or for
> > that matter, almost any graphics textbook.
>
> Hold on. Yes, algorithms are described very effectively by English, and
> pseudo-code in many textbooks. That's great because it allows humans to
> understand the workings and the flow of the algorithm so that, if they
> choose, they can implement it in whatever programming language they like.
>
Show me a single text book that does a good job at describing algorithms
in English. I believe it approaches the impossible to describe algorithms
in any detail in true normal English. What we need is well defined set
of formal rules for writing about algorithms that match reality. English
doesn't easily describe list of detailed steps. Its hard to add enough
modifiers without seemingly breaking the rules. What needs to be done
is to develop a new set of writing standards than are designed for
algorithms without creating a new language. This class should not
be taught by the English Department, or the Math Department. Ideally
there needs to be a new department, but Engineering could do the
job if truly motivated.
Muddy
> But I am proposing a way to describe algorithms which a computer can read,
> in a language that can be parsed with well-defined meanings. But it should
> still retain a difference from "source code", ie. not an implementation of
> the algorithm. Very much like the algorithms in text books, but probably
> with a lot more detail specified. These text books tend to have preceding
> paragraphs saying (for example) "Here, x is always even, and notice that y <
> x always", etc.
Good luck, if you avoid just creating another language, you are pushing
the limits of Natural Language Understanding to expect a computer to
correctly handle vague descriptions.
>
> > This is probably just a cultural difference in how we define the word
> > "algorithm". In my opinion, algorithms are abstract processes, not
> > limited to any particular hardware, operating system, or programming
> > language. Your mileage may vary.
Your definition agrees with mine, as long as you include data structures,
and mathematical precision.
>
> Why not have a way to communicate them to computers too? Why not give a
> computer a chance to find an efficient implementation of an "abstract" but
> well-defined algorithm?
What do you mean by abstract? Many types of Algorithms have to describe many
processes down to fine detail to be meaningful. There is also the problem of
handling the various access boundaries that can have much more effect than
O(N). Example would be a algorithm that did not group its file accesses into
reasonable blocks, vs. an ideally ordered access. The time difference could
be 1000x. This problem would exist for most reasonably sized data processing
problems, and thus there is currently a conflict between what is the base
algorithm, and what are implementation details. With enough understanding,
it can be handled, but the knowledge its there can not be ignored by a
worthwhile algorithm. An algorithm that requires totally random access to
a 1 Gigabyte data structure is not going to do well, yet many would argue that
the file access details are implementation details. Thus some way needs to
be provided to include the concept of data organization without becoming
system specific.
Muddy
>
Robert Posey
Jeff Erickson wrote:
>
> "Toby Sharp" <TSh...@Serif.com> writes:
> | Jeff Erickson <je...@cs.uiuc.edu> wrote in message
> | > I would argue that if you're communicating an algorithm to a computer
> | > and getting actual executable code out the other end, then BY
> | > DEFINITION you have an implementation of the algorithm.
>
> | You contradict yourself.
>
> What, again?
>
> | Algorithms described in text books are entirely separate from their
> | implementations (as you say), yet one expects that an implementation
> | can be derived from those descriptions with the relevant perennial
> | knowledge.
>
> Yes, but by a human being. If a computer can understand it without
> human intervention (which seems to be what you're proposing), it's an
> implementation.
>
> | > Remember, the 'abstract machine' that you are writing your C (or
> | > whatever) programs for has very little resemblance to the actual
> | > device you compute with. [...] And you don't worry about any of it.
>
> | I absolutely DO worry about it!!
>
> Oops.... I forgot about time-critical' code. But shoudn't that be
> done in assembly code anyway?
Every line of code that has or will be written is time critical code, the
timeline just varies. What I mean is that good code should always use
close to the "best" algorithmic solution in terms of time and space, and
then the amount of implementation optimization, which is hardly ever
reusable, will be kept to a minimum. I not implying that every
function(or method) has to be the best possible, but its time and space
implementations should never be ignored. Not paying attention to
time and space Order of functions is one of the best ways to write
software that works fine for small test cases, and fails to perform
in the real world.
Muddy
Jeff Erickson
| It's really quite simple:
| *Algorithms* is what I do.
| *Implementation* is what my assistant does.
No, my assistants don't implement, either. :-)
Ben Blish
>| (a) you can't *test* pseudocode
>
>So what? Testing isn't good enough! The only way that I'll ever
>really believe that an algorithm works is if I see (and understand) a
>proof.
I'm very sorry for you, then. Really. I don't mean to be condescending; there
is great beauty in careful coding and careful testing, as much as you seem to
find vision and clarity in a proof, such things lie in programming code as
well. Further, while you might *think* that something works by wrapping your
head around a mental proof, a program can show you, without the crippling
limitations of personal perception, that the idea does in *fact* work. Human
perception and opinion are far more fallable than a processor is. Given the
same set of information about the world, you can come up with an atheist, a
catholic or a muslim just as easily. Pseudocode, and associated proofs, present
an idea. These might work. They might not. There's no *actual* proof in the
sense of reality, from the existance of the idea and/or the pseudocode. Things
aren't so because we imagine that they are; they are so if they ARE so, and
there are no exceptions to that, much though many people would prefer it
otherwise. The program, however, will either do the task, or it won't; and if
it does, now you have reality-flavored proof rather than religious-flavored
proof. If it doesn't, you have more thinking to do!
>And you *can* prove that pseudocode is correct.
Nonsense. The only way you can prove any pseudocode in the practical sense is
to write working code that exactly mimics the pseudocode, concept by concept.
And if you've got to do that, you should have written a working example in the
first place (considering the goal of proof as desirable.) OTOH, If you're
talking about a "proof" in the ivory tower sense, that's of almost no use to
anyone but you and your immediate colleagues. Such things without working
examples are hugely deficient as carriers of ideas. Unless the academic's goals
do not include informing the rest of society about new knowledge, which is
something along the filthier lines of despicable, in my philosophical
outlook...
>| (d) the pseudocode may well leave out very important details in
>| getting the example working, which does not happen with a working,
>| tested program.
>
>Admittedly true. There are always unforseen details in translating
>algorithms from one language to another (or from one system to
>another, or even from one C compiler to another!)
Pseudocode isn't a "language" in the sense that C is. It's a language in the
sense that ghetto english is - it changes from day to day and speaker to
speaker, and it's just about as attractive in a professional venue, frankly. It
announces the laziness of the speaker, and a desire to isolate up in the
classic ivory tower (or down in the mud basement, in the case of ghetto
English.) The more jargon (especially jargon you just defined today!) you
immerse your ideas in, the less accessible they are to the rank and file who
might be capable of implementing those ideas, and the less useful your ideas
become - the correlation is direct and utterly inescapable. This is aside from
the testability issue, which I contend is far more valuable to society in
general than any abstract "proof" an academic might contemplate (and attempt to
pass off as sufficient in leiu of an actual working example.)
There is a huge problem with academic-speak. The idea is constantly promulgated
that a concise presentation is inherently better. But the problem is this, in
essence:
The tighter the representation by the teacher, the more required of the student
in terms of background. E=Mc squared means just about zilch to the average
person. That's because the concepts and math that underlie E, M and c are so
broad and so deep that they can't "get it". It can, however, be explained in
less formidible terms - Einstein wrote a book himself that does so (I own a
copy, a great book!) The implication, in which I have high confidence, is quite
valid: It is that as you broaden the explanation, and as you make the
explanation do donky work in practical terms, the audience that can understand
what you are presenting widens in direct proportion.
When you present ideas to an audience that is tasked with implementing those
ideas, in the case of complex concepts, the tighter you make the
representation, and the more abstract terms you couch your presentation in, the
more of your audience you lose, or at best, slow down.
The best teachers *directly* relate what they teach to the realities that those
teachings affect. The worst leave huge chunks of new ideas and/or new
implementations as "an exercise for the reader/student". That's appropriate if
you're trying to generate a new academic; it's NOT appropriate when you're
trying to create informed, intelligent worker bees. And guess what? That's what
the majority - the VAST majority - of students are either going to become, or
already are.
>| On the other hand, you apparently don't think they've got the
>| competance to generalize a working example into similar (or not so
>| similar) environments unless those environments are left unspecified
>| (abstract).
>
>Not at all. I'm sure almost every decent programmer CAN translate one
>specific instance into another. But remember, my goal is not just to
>help programmers write code. My goal is to help the reader understand
>the algorithm -- ideally, well enough that they can implement it
>themselves from scratch without my help.
Then you'd do well to show a working example. Far better than a fakey one that
may, or may not, work if converted to code. You avoided my point here; you
claimed that things must remain abstract, to the degree that this was
justification to avoid a concrete implementation, because that diluted the
abstration(s). I am saying that your contention is nonsensical. More:
>| If I talk about addition, and then throw 2 and 2 in there, have I
>| ruined the definition or understanding of addition by having
>| introduced a non-abstract example?
>
>To take this to your logical extreme: If you define addition only in
>terms of 2+2, then YES, you HAVE ruined the definition!! Examples are
>absolutely essential, but they shouldn't be used as definitions.
I didn't say "only" in terms of 2+2, nor did I imply this. I said that you can
show an EXAMPLE of 2+2 which serves to illustrate that the idea works in the
context of talking about addition (which was primary, if you read what I
wrote.) There is nothing stopping you from describing addition as completely as
you like, in every venue (or in as abstract a venue) as you prefer. You're
arguing against something I'm not advocating. I am saying ONLY that a concrete
example, that works (meaning, pseudocode is "right out", as Monty Python would
put it) is *the* most useful means to communicate an idea (and has the
beneficial side-effect of proving, in the real sense, that the idea actually
works, which pseudocode cannot do.) My *specific* statement began with:
"If I talk about addition, and then throw 2 and 2 in there"
Notice I said "talk about addition" FIRST, and then indicated the concrete
example. So what you call "my logical extreme" is something I eliminated from
consideration with my first five words. It's your illogical extreme, is what it
is. :-)
>I suspect there's a fairly strong correlation between (a) how well a
>program works, (b) how clearly the code is written, and (c) how well
>the programmer understands the underlying abstract algorithms.
No, I don't think so. And here, I am the expert. Programmers, as opposed to
academics, spend their careers using, and reusing, tools they are familiar
with. They often "bend" method A into a shape to do task B, though there may in
fact be a far more elegant way to get the job done - it's not as
cost-effective, because method A is already known, pitfalls, benefits and all,
while method B, which is more appropriate for task B, requires one to stop,
retrench, and turn a job from a set of knowns to a set of unknowns. "Method B"
may simply be completely unknown to the programmer, also. In the case where a
programmer has been "at it" for many years, their toolbox tends to become very
wide and very deep, and that's when coding tends to become more elegant -
because the solutions are more appropriate to the specific task and hence, more
concise, which to some degree correlates with elegance (though not always!)
coding style, coding clarity and algorithm elegance are unrelated,
unfortunately. Though when they're all present, it's a joy, no question.
>We're going around in circles; neither of us is convincing the other
>of anything. I think we agree on one basic point: A well-written
>algorithm description in any language (C, pseudocode, whatever) is far
>better than a badly-written description in any language (pseudocode,
>C, whatever). Maybe we should leave it at that.
We don't even agree on that. I contend that poorly written code that *works* is
better than fabulous pseudocode that claims to represent the same task. The
reason is simple: The code answers all the questions, AND it works. The
pseudocode may, or may not, answer all the questions, and it can NEVER work, so
you can never know if it's complete unless the base idea being demonstrated is
so simple that this argument is moot anyway.
--Ben
Joseph O'Rourke
Ben Blish <bbl...@TblackbeltsystemsDO.Tcom> wrote:
>Pseudocode isn't a "language" in the sense that C is. [...] It
>announces the laziness of the speaker, and a desire to isolate up in the
Let me take issue with your (forcefully stated) position via an
actual example. Two academic researches, Chen & Han (prof & grad student)
published an algorithm in 1990 for finding the shortest paths on the surface
of a polyhedron. Their paper was 10 pages long, and only presented
pseudocode. I read their paper, and thought it was an extraordinarily
clever algorithm, containing a substantial new idea. Point (a): Their
pseudocode communicated something useful to me. Point (b): It was
a full decade before their algorithm was implemented. The current
implementation (which might well be improved upon) is 2500 lines of
C++. It is nearly impossible to see their fundamental ideas in the
thicket this of code. There is a huge gap in this case between the
algorithmic ideas and a realization in code.
It would impede the progress of science if the original researchers did
*not* publish their results just because they had no implementation.
In this case, the skills required to conceive of the algorithm in the
first place are rather different from those needed to actually implement
it. There is no issue of "laziness" here.
Surely you would not recommend in this instance that the fruitful
algorithmic ideas should remain private awaiting an implementation?
For this would deny researchers access to these ideas not only for
a decade, but in this case for perhaps much longer (assuming no independent
rediscovery), because the implementation was ultimately undertaken by a
group unrelated to the original.
Kenneth Sloan
> In article <39b01c33...@news.montanavision.net>,
> Ben Blish <bbl...@TblackbeltsystemsDO.Tcom> wrote:
> >Pseudocode isn't a "language" in the sense that C is. [...] It
> >announces the laziness of the speaker, and a desire to isolate up in the
> >classic ivory tower [...].
>
> Let me take issue with your (forcefully stated) position via an
> actual example. Two academic researches, Chen & Han (prof & grad student)
> published an algorithm in 1990 for finding the shortest paths on the surface
> of a polyhedron. Their paper was 10 pages long, and only presented
> pseudocode. I read their paper, and thought it was an extraordinarily
> clever algorithm, containing a substantial new idea. Point (a): Their
> pseudocode communicated something useful to me. Point (b): It was
> a full decade before their algorithm was implemented. The current
> implementation (which might well be improved upon) is 2500 lines of
> C++. It is nearly impossible to see their fundamental ideas in the
> thicket this of code. There is a huge gap in this case between the
> algorithmic ideas and a realization in code.
{taking off the algorithms hat and putting on the implementation hat}
In that case, it's quite simply a bad implementation.
>
> It would impede the progress of science if the original researchers did
> *not* publish their results just because they had no implementation.
> In this case, the skills required to conceive of the algorithm in the
> first place are rather different from those needed to actually implement
> it. There is no issue of "laziness" here.
I respectfully disagree.
>
> Surely you would not recommend in this instance that the fruitful
> algorithmic ideas should remain private awaiting an implementation?
Not at all. But I would withhold recognition that the algorithm itself
was not yet completely understood or demonstrated. Notice how you shift
ground subtly by talking about "algorithmic ideas". By all means
publish the ideas. Ideas are useful. Just don't pretend that you have
an "algorithm" if you can't (or can't be bothered to) produce at least a
reference implementation which is actually amenable to testing some of
the claims made.
> For this would deny researchers access to these ideas not only for
> a decade, but in this case for perhaps much longer (assuming no independent
> rediscovery), because the implementation was ultimately undertaken by a
> group unrelated to the original.
And, taking your description at face value, I fault BOTH the
theoreticians AND the coders or doing a less-than-perfect job (note my
careful use of words - I'm talking about the ideal situation; I get the
feeling that you are describing the reality and then after-the-fact
rationalizing it as being actually desirable). The theoreticians
presented ideas, proofs, and a sketch. In my opinion, they didn't yet
have "an algorithm". The coders (according to you) produced opaque code
which does not reveal the design ideas. In my opinion, this may be
suitable for *use* - but is unsuitable for communication. Both could
have done better.
In my experience, both theoreticians AND coders continue to be too
impressed with truly low-level details. The theoreticians shun them
(rightly) and (incorrectly) take this as an excuse to do no
implementation at all. The coders think that they are the true essence
of implementation, and deprecate any implementation which is not aimed
at "production use". They do ugly and obfuscating things because they
think this makes things faster (and therefoe better).
Joe: surely you can dredge up a single isolated example of an
"algorithm" which was accepted by the theory community without
implementation and then later shown to be incomplete, to need further
work, or to be simply flat out wrong when someone actually tried to
implement it. Just one?
I tend to prefer a proof to measurement data - but I much prefer to have
BOTH. If you don't have both, then the job is not yet complete. That
doesn't mean that you have to delay publication of the theory - it
simply means that you can't in good conscious walk away and say "we
don't do implementations". Any more than the coders should be allowed
to present opaque code and call it an "algorithm".
Christer Ericson
Ben Blish
wrote:
>Let me take issue with your (forcefully stated) position via an
>actual example. Two academic researches, Chen & Han (prof & grad student)
>published an algorithm in 1990 for finding the shortest paths on the surface
>of a polyhedron. Their paper was 10 pages long, and only presented
>pseudocode. I read their paper, and thought it was an extraordinarily
>clever algorithm, containing a substantial new idea. Point (a): Their
>pseudocode communicated something useful to me. Point (b): It was
>a full decade before their algorithm was implemented. The current
>implementation (which might well be improved upon) is 2500 lines of
>C++. It is nearly impossible to see their fundamental ideas in the
>thicket this of code. There is a huge gap in this case between the
>algorithmic ideas and a realization in code.
>
>It would impede the progress of science if the original researchers did
>*not* publish their results just because they had no implementation.
>In this case, the skills required to conceive of the algorithm in the
>first place are rather different from those needed to actually implement
>it. There is no issue of "laziness" here.
In this case, you are presenting a situation where you're essentially saying
that the competance of the academic was not up to the task of writing a good
example. So in this case, it's not laziness, perhaps, as much as it is skill.
And no, I'm not saying they shouldn't publish, I'm just saying that they limit
their audience - and clearly, if this example was so severe as to engender a
*ten year* gap between pseudocode and a real, working version, then my position
that pseudocode is a terrible venue for presenting an idea is entirely
validated. If they had presented working code, there would have been no gap. I
would venture to say that, since they understood what it was they were
presenting, it would likely have taken them less than ten years to do it
themselves --- even if they had to learn to program as part of the task (which
clearly, if they can write pseudocode that is translatable, they are well along
the road to knowing anyway.)
>Surely you would not recommend in this instance that the fruitful
>algorithmic ideas should remain private awaiting an implementation?
Actually, this kind of case is exactly what I was talking about, at least from
the scanty details you've provided. It would have been far better if they had
said, "here is the idea; here is the pseudocode; here is a working example."
How long would it have taken them, after writing this reportedly very complex
pseudocode, a most rigorous effort if it is to actually represent the reality
of the idea (and it apparently did, as someone eventually implemented it), to
actually implement it when it was fresh in their minds, new, exciting, etc.? A
few weeks? Instead, we have a ten year gap. And what's to blame for this?
Pseudocode.
>For this would deny researchers access to these ideas not only for
>a decade, but in this case for perhaps much longer (assuming no independent
>rediscovery), because the implementation was ultimately undertaken by a
>group unrelated to the original.
Well, you're looking at it as if the academics could not implement it, and (I
think) implying that if implementation was a requirement, that this work would
be lost. If that's the case, then yes, the publication of the new idea as it
was, pseudocode only, is certainly a contribution that should not be lost.
But - is the idea that implementation of this - since we know someone DID
implement it - actually presents such a huge impediment, valid?
I don't see that it is. So, I am looking at it as if they *could* have
implemented it; I consider that implementing it would have prevented a rather
significant amount of the ten year gap you report. Although I don't know the
specifics and so of course am guessing, I rather think that perhaps the tasking
of the grad student (or a CS major, or whomever) to get it done would have made
the contribution far more worthwhile than an abstract that required such a
delay before becoming practical. And I find it very difficult to believe that
it would have taken long to do given the expertise available to that taskee,
and again, that the idea was new and fresh in the minds of those who conceived
it.
Some ideas can't be implemented at all, be they programatic, or more physical -
a concept for a fusion reactor is a little tough to present with an example,
for instance. Wormholes might be a little difficult to construct, and darn it,
we're just having a lot of trouble with the very perception of strings.
Generally, any idea that requires more data (or computing cycles, or
antimatter, or other resources) than are presently available due to the state
of the relevant art(s) is surely appropriate for "pseudocode only"
representation, whatever form "pseudocode" might take in that area of
application. And of course, these ideas are better off on the table than locked
away in someone's mind, there to wither and die.
But does that in any way excuse any academic from providing a working example
of something that is doable? I don't see that it does. I think (as I've made
fairly clear, I suppose :-) that it is, or it should be, part of the job to
implement one or more examples, where it is even marginally practical.
Thanks for the reply; I very much appreciate your words.
--Ben
Ben Blish
>The coders think that they are the true essence
>of implementation, and deprecate any implementation which is not aimed
>at "production use".
To extend a hand here: I am not in any way saying that ideal implementations or
even practical implementations are what ought to be provided as part of an
algorithm presentation. I am asking for a *working* implementation only. I am,
and I suspect that most even marginally competant programmers are, quite
capable of incrementally improving many types of OPC (other people's code), if
it is not reasonably high quality when I get it (high-quality in this context
== meets my needs, which of course are defined by my application(s) to start
with.) Once I've had some time with the code and what's actually "going on" has
sunken into my thick worker-bee programmer's skull, I may even be able to
impose large improvements on one or more areas. Or maybe not. But I'm perfectly
ready to take on that class of task and give it a try. It *has* been known to
happen. :-)
> They do ugly and obfuscating things because they
>think this makes things faster (and therefoe better).
Hmm. You know, sometimes ugly and obfuscating approaches DO make production
code faster, and therefore, specifically in terms of a production product,
better. Cases in point? Factoring. You can, in the case of some algorithms,
save may cycles by factoring; however, the structure of underlying process
becomes subsumed in the factors, and the more you do it, the less obvious (more
obfuscated!) the underlying process becomes. You can also pre-compute some
other things. You can unroll loops. You can do things as simple as replace
division by n with multiplication by 1/n when hardware hands you a cycles-cost
benefit if you do so, and you can do things as gnarly as approximate a
nonlinear result with a linear one below a threshold because "the results are
not different enough to matter" *for the product*, and it saves you significant
cycles. I know of examples where it saves *many* cycles. Etc., ad infinitum.
In other words, we, the programmers, generally try to do those things because
they provide real world benefits, and if done intelligently, they do so with no
harm whatsoever to counterpoint those benefits. You're the consumer of our
products; we're trying to save you time because we know that makes our products
more valuable and useful to you, and *everyone* benefits from that.
Now, I make no case that an academic presentation of an algorithm should make
use of any such approach. Clarity before everything in examples, absolutely.
For instance, I note that when teaching rotation, it is usually presented in
simple algebraic cosine, sine, X1,Y1...X2,Y2 form rather than as some opaque
matrix full of premultiplied "stuff", too. At least, if the instructor is
skilled at teaching as a task in itself, as well as in being an academic
repository of knowledge. That's the way to go as far as I'm concerned. Of
course, if you have suggested optimizations for us, by all means present them.
After you explain what the heck the basic idea is!
>...Any more than the coders should be allowed
>to present opaque code and call it an "algorithm".
Abso-bleeding-lutely. :-)
Thanks for speaking up on this.
--Ben
Wim Libaers
Jeff Erickson <je...@cs.uiuc.edu> schreef in berichtnieuws
UhGr5.3368$9N1....@vixen.cso.uiuc.edu...
> bbl...@TblackbeltsystemsDO.Tcom (Ben Blish) writes:
>
> | (a) you can't *test* pseudocode
>
> So what? Testing isn't good enough! The only way that I'll ever
> really believe that an algorithm works is if I see (and understand) a
> proof. And you *can* prove that pseudocode is correct.
Only if it is strictly defined. Normal natural languages are inadequate,
unless the meaning of words is restricted as is done in physics.
How about defining a processor with some opcodes, and writing the algorithm
in that assembly language? It can and has been done, your opinion?
--
Wim Libaers
Remove DONTSPAM from my reply address to send me mail.
Wim Libaers
Toby Sharp <TSh...@Serif.com> schreef in berichtnieuws
8onqic$8c6$1...@soap.pipex.net...
> Thanks, Dave.
>
> I'm sorry that this thread has digressed so far from the original point,
> which may have been obscured by terminology differences.
>
> In your teminology, what I was driving for is a compiler which can accept
> input in terms of well-defined problem statement, e.g.
>
> TWICE(x)
>
> and try different algorithms
>
> x+x, 2*x
So, in your opinion, x+x and 2*x are somehow bad, because they have a direct
mapping to processor opcodes, and you want an abstract function so that all
equivalent operations are tested? So, if the next generation of processors
has a Twice(x) opcode, that one will be bad too?
Toby Sharp
----- Original Message -----
From: "Toby Sharp" <TSh...@Serif.com>
Newsgroups: comp.graphics.algorithms,comp.compilers,comp.dsp
Sent: Sunday, August 27, 2000 9:25 PM
Subject: Seprerating algorithms from implementations (long)
>[Description of pain of hand-optimizing hi-performance code when
> platform changes]
>
> We might be able to solve this problem if there were some way to
> describe algorithms apart from their implementations. Such a
> description would need to be sufficiently concrete to allow an
> implementation to be derived, but needs to be sufficiently flexible to
> allow many different implementations. These could then be tested for
> speed, or various trade-offs could be chosen on the basis of knowledge
> of a target CPU.
>
> Then a very, very clever compiler could spend a lot of time looking at
> the algorithm description, assembling instructions into
> implementations, testing sample data, and making changes as
> appropriate. If successful, the compiled code should rival that of the
> hand-tuned implementation.
>
> So, has anyone done it? Suggested it? Any thoughts on whether
> theoretically possible? Or practically feasible? All comments welcome
> at this stage.
Conventional compiler optimizers are exactly a version of this.
But this has been suggested before in a more general framework,
as transforming specifications to code.
You need three notions:
1) Specifications
2) Possible transformations to code
3) A system to try combinations of 2 to acheive 3. ("compiler").
A specification suggests what is to be done.
A high level specification doesn't suggest very precisely how.
A low level specification is more "algorithmic" in hinting at the solution.
Ideally, you code specifications at as high a level as your tool will
accept and still generate code. (First order predicate calculus
is a very high level spec, but in general nobody knows how to compile it).
The possible transformations need to be designed to map pieces of the
specification
to code, such that all the spec pieces can be compiled consistently by some
covering set of transforms. Each covering set has some set of performance
properties.
In a naive model, one simply enumerates all the sets, and chooses
the "best" according to some other description of performance.
In a realistic implementation, one chooses transforms that typically lead
to high perfomance implementations, and attempts to find other transforms
to fill out a consistent set.
A really brute force version of this is done by Gnu superoptimizer, which
takes in very tiny
specifications ("x&y"), and enumerates sequences of machine instructions
to see which ones implement the spec. It often produces really surprising
sequences
of machine instructions.
Our DMS Reengineering toolkit offers a way to encode 1) and 2), and the next
version
will have 3).
Ira Baxter, Ph.D., CTO idba...@semdesigns.com 512-250-1018x140
Semantic Designs, Inc., www.semdesigns.com FAX 512-250-1191
12636 Research Blvd #C214, Austin, Texas 78759