Re: pseudo code v/s algorithm
- From: Paul Hsieh <websnarf@xxxxxxxxx>
- Date: Sun, 4 Jan 2009 05:59:46 -0800 (PST)
On Dec 27 2008, 7:15 pm, p...@xxxxxxxxxxxxxxxxx (Pascal J.
Bourguignon) wrote:
Neil <NeilKu...@xxxxxxxxxxxxxxxx> writes:
An algorithm is the plan of action how you are going to do it.
pseudo code is the next step a list of steps more in english ( or
insert your language here) than code. More like a recipe.
There is absolutely no difference between algorithm and code, as long as
code is considered in its more abstract, mathematical level.
Tagore is not the only one confused.
Two very distinct and different pieces of code can be described by a
common algorithm. For example, *MY* Karatsuba multiplier, and GMP's
Karatsuba multiplier are both still Karatsuba multipliers (which is an
algorithm described by Karatsuba and most popularly re-explained by
Donald Knuth) regardless of the fact that I have never looked at GMP's
implementation and I use an abstracted 2s complement system, while GMP
uses signed magnitude (so its unlikely that they are really the same;
they can't be at the bit level). However the converse cannot be
true. If I have an implementation or pseudo-code it cannot be
described by multiple algorithms without breaking it down into sub-
parts or nestings.
Pseudo-code is just an informal way to express such a mathematical
being.
Not necessarily. Pseudo-code can contain choices that specify things
in more detail than an algorithm describes, while the converse is not
true.
That is, if your code is the description of a valid Turing Machine, or
lambda-calculus function, then it is equivalent to the algorithm.
This is only true in trivial cases, or overly specific algorithms.
[...] Note
that very little is needed from your programming language for this
condition to be realized. Obviously, if your programming language is
implemented in a finite memory Von Neumann computer, then it can be
implemented in a Turing Machine or lambda-calculus function, and if your
language is worth its bits, you will be able to trivially implement a
Turing Machine or lambda-calculus in it, modulo the infinite memory
requirement.
You clearly have a specific idea in mind that's way off the mark of
the question. Because you don't see any difference between algorithms
and pseudo-code, you've now translated this question into the
difference between pseudo-code and implementations. An interesting
discussion in of itself, but its not what Tagore is asking.
Our computers and programming languages only approximate these
mathematical beings. For example, there is no computer that is
equivalent to a Universal Turing Machine, because there is no computer
with infinite memory. (But a given Turing Machine can be implemented in
a specific computer with enough memory, because one condition for an
algorithm is to be finite, and to terminate, therefore the explored
state space is finite, and may in practice be held in the amount of
memory available to our computers.
An algorithm does not have to discuss only idealized mathematical
objects. Neither does pseudo-code. Your view of the universe is
convenient if, say, you wanted to discount the existence of practical
algorithms such as "hash tables". In a theoretical mathematical
sense, hash tables are a totally worthless mechanism. In the real
world they are critically important to a wide variety of
applications. Its almost as if you have an agenda in mind ...
For example, C is a poorer approximation than Comon Lisp, because in C,
there sizeof(int) is finite, and pointers and array indexes must be
enumerable by integers, therefore the memory available to a C program,
even if it would run on a computer with infinite memory, would be very
finite.
Aha! There we go ... "Lisp is king" (even if you cannot convince even
a small fraction of the worlds developers to program in it.) I have 5
questions for you:
1) How do you implement a hash table in Lisp?
2) Assuming a black hat hacker has access to your memory image upon
your program's completion, how do you ensure that any data processed
by your program that has been identified as private is unavailable to
that hacker?
3) In a very famous paper by some Sun researchers (I don't have the
citation off hand) they demonstrated that keeping pools of pre-
allocated structures dramatically improved performance of both their
OS and applications which used the technique. Describe how you would
implement this in Lisp.
4) What is the accuracy of the transcendental functions (sin, cos,
etc) in Lisp?
5) How might you exhaust all possible floating point values in a given
range? (To test a function for monotonicity, for example.)
[...] On the contrary, in Common Lisp, there's no limit imposed on
the size of integers,
And what about the size of floating point numbers?
[...] and there's no limit imposed on the number of
different objects that can be referenced (there's no equivalence between
references and integers in CL), so if there existed a computer with
infinite memory, there could exist an implementation of Common Lisp
equivalent to lambda-calculus, with infinite memory (but you will never
be able to use C to implement an infinite memory lambda calculus or
Turing Machine). We can say that Common Lisp is a better algorithmic
language than C.
That would imply that Common Lisp has functionality that is not
mappable to C. What language are most Common Lisps implemented in?
[...] However, my thesis here is that it is in general ridiculous to try to
specify an algorithm with an informal language pseudo-code, because of
the lack of formalism and precision. Pseudo-code is necessarily more
ambiguous than any formally specified programming language.
Which is understandable see as how you changed Tagore's question from
"Algorithm vs Pseudo-code" into "Pseudo-code vs Implementation".
It would be better to just use mathematics to formalize algorithms, that
is, Turing Machines or lambda-calculus. You will soon notice that
lambda-calculus is more expressive than Turing Machines, and that using
a subset of lisp (or any other functional programming language) as an
extension to lambda calculus is even more expressive, and sufficiently
formal to be usable to describe precisely algorithms, with the level of
abstraction needed.
Full abstractions like this are mostly useful for the confines of the
classroom. Its necessary for giving precise meaning to things like "P
vs NP" but is fairly worthless for doing things like, say,
implementing real time operating systems.
I see no reason to use a more informal and ambiguous pseudo-language.
So you don't see the differences between the various choices you can
make in an algorithm like Quicksort?
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
.
- Follow-Ups:
- Re: pseudo code v/s algorithm
- From: Pascal J. Bourguignon
- Re: pseudo code v/s algorithm
- Prev by Date: Re: pseudo code v/s algorithm
- Next by Date: Re: pseudo code v/s algorithm
- Previous by thread: Re: pseudo code v/s algorithm
- Next by thread: Re: pseudo code v/s algorithm
- Index(es):
Relevant Pages
|
Loading
