Re: pseudo code v/s algorithm
- From: pjb@xxxxxxxxxxxxxxxxx (Pascal J. Bourguignon)
- Date: Sun, 04 Jan 2009 17:05:20 +0100
Paul Hsieh <websnarf@xxxxxxxxx> writes:
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.
Here is an algorithm:
(defun gcd (x y)
(cond ((= x y) x)
((< x y) (gcd (- y x) x))
(t (gcd (- x y) y))))
Is it using two-complement arithmetic, or is it using sign-magnitude
arithmetic?
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.
By definition, pseudo-code is not code. If you give a formal definition
of your pseudo-code, it becomes ipso-facto code, because you can take
this formal definition and implement it into an interpreter.
Therefore I stand on my affirmation that pseudo-code is informal, and
therefore ambiguous, and therefore erroneous, worse than nothing,
because you need a mathematician to recover the algorithm from it
anyways.
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 ...
Not at all. For example, think about that: how do you "implement"
O(1) arrays in lambda-calculus?
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?
You take the hash-table algorithms and implement them, just like in any
other programming language. Lisp is a universal algorithmic programming
language.
That said, in most case, you don't need to because Common Lisp, like
most lisps, has already implemented hash-tables. (or to answer your
question otherwise, just have a look at the sources of some Common Lisp
implementations, such as sbcl, or openmcl).
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?
How is this related to our discussion? Think about it!
Then see answer to the first question.
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.
This is an optimization that is routinely done, in all the big
24/24 365/365 lisp programs, at least all that I've seen. See answer to
the first question.
4) What is the accuracy of the transcendental functions (sin, cos,
etc) in Lisp?
I'd say about LEAST-POSITIVE-LONG-FLOAT.
But in the implementation I use, it's actually user selectable.
C/USER[93]> (sin (/ pi 3))
0.866025403784438646763723170752936183471402626905190314027903489725966508454400018540573093378624287837813070707703351514984972547499476239405827756047186824264046615951152791033987410050542337461632507656171633451661443325336127334460918985613523565830183930794009524993268689929694733825173753288025378309173L0
I fail to see how it's related to this thread. See answer to the first
question.
5) How might you exhaust all possible floating point values in a given
range? (To test a function for monotonicity, for example.)
C/USER[94]> (log (loop :for x :from 0.0e0 :to (/ 1.0e0 1024) :by single-FLOAT-EPSILON :sum 1) 2)
14
Perhaps you could learn some Common Lisp, have a look at
http://www.gigamonkeys.com/book/
and then you may go to news:comp.lang.lisp to ask your questions.
[...] 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?
The Common Lisp standard defines four floating point types of (possibly)
different sizes. Some implementations let the user define the size they
want (see answer to question 4).
But still no relationship with the thread at hand...
[...] 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.
In terms of language specification, yes, I think it has. For example,
no memory model is specified. (In particular, the standard doesn't
specifies for example a garbage collector, this is just an optimization
that is often provided, but anything else would do).
What language are most Common Lisps implemented in?
But of course, the standard is termed in ways allowing the
implementations to differ in some details, so you can implement the
language efficiently, if with some limitations, on current hardware.
The language most often used to implement Common Lisp is Common Lisp.
Of course since it's the best programming language, why would we do
otherwise? Now there are some implementations that are written in
different programming language, but it's the exception, for
bootstrapping reasons. For example, clisp is implemented in C, so you
can bootstrap it on Unix systems. Then you can use clisp to compile
sbcl, and finally use sbcl to compile sbcl.
[...] 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".
A formally ___***SPECIFIED***___ programming language is not an
implementation. I understand now your confusion and your questions about
implementation details of Common Lisp. This is the important point to
understand, a formal specification of a programming language gives a
semantic to the formal notation, and this is what allows the
mathemtatician to use it to write an algorithm.
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.
FSVO implementing. If you mean producing a bug-ridden artifact barely
passing for an operating system that with the help of some con-man you
can convice "customers" to buy, then ok.
Otherwise, you specify, define and write your operating system in maths,
and you use automatic tools to translate the prooved mathematical
description into executable code. If (some) silicium founders can do
it, why not system programmers?
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?
A formal specification of an algorithm is not more and not less
commiting than any hand waving. But it is a proved (or provable)
reference of what is meant.
--
__Pascal Bourguignon__
.
- References:
- Re: pseudo code v/s algorithm
- From: Paul Hsieh
- Re: pseudo code v/s algorithm
- Prev by Date: Re: pseudo code v/s algorithm
- Next by Date: test for single 1-bit or two consecutive 1-bits
- Previous by thread: Re: pseudo code v/s algorithm
- Next by thread: Re: Women are too dumb to prgram a computer!!!
- Index(es):
Relevant Pages
|
