Abigail

Potatoe, Potatoe.

Combine two algorithms, what do you get? Right, another algorithm. Repeat this several times, now you have a very large algorithm.

The only thing that separates a program from an algorithm is data. So why does it seem that an algorithm is so much different from a whole program? It's really quite simple - we suck. Programming hasn't yet evolved to the point where our products resemble actual engineering. So what we have is a mess of unprovable code that we can't even guarantee will work as intended.

An algorithm is commonly viewed as a tried and tested method of accomplishing a very basic goal. The next step is transcending simple sorts and being able to create real solutions with the same reliability.

Programming hasn't yet evolved to the point where our products resemble actual engineering. So what we have is a mess of unprovable code that we can't even guarantee will work as intended.

The main thing that stops programming being as reliable and reproducable as mechanical engineering can be summed up with the term 'metrics'. Software has yet to evolve a reliable and universal system of metrics. And I'm not talking about 'klocs' :)

You can take an engineering drawing (specification) for a mechanically engineered part to any workshop, anywhere in the world, and the chances are that they will be able to produce the 'part', within the specified tolorences reasonably quickly. The thing that allows them to be able to do this is the accuracy of the specification which comes down to the accuracy and universality of the metrics used to define the specification. Inches/millimetres, pounds/foot, Nm, pounds/kilos, etc. etc.

We can write reliable, efficient and interchangable sort routines because the metrics used to define and measure the output are very simple and easily defined.

The specification of a "well designed, easily navigable, clearly presented" webpage, or "well-structured, efficient and flexible" database schema, are considerably harder to specify, measure and agree. The difference is that the metrics of 'well', 'easily', 'efficient' and 'flexible' are all either subjective, or relative, or context sensitive, or some combination thereof.

The person that finds a way of specifying these things, and software in general, in an unambiguous, measurable and universally acceptable way will be my hero.

I won't hold my breath waiting for the discovery though, because I seriously doubt that it will be achieved in my lifetime. The reason for my pessimism is that there are several vaguely comparable fields of human endevour which are similar in nature (IMO) to software that we (the human race) have been practicing for much, much longer than software, but for which there is still no universally accepted specification, development or measurement method vailable.

I'm thinking of good books, good music, good paintings. Even one of the least recognised 'big industries' of this world, fashion, has no mechanism for deciding what is or is not good design and implementation, other than public opinion, and that changes wildly. Have you looked back at the clothes we all thought were cool in the 80s? Never mind the 70's or 60's or 50's should any of us go back that far.

I don't think your point is sound. What does "combine two algorithms" mean? Does that mean that mean that we place the two algorithms into a container, and then provide a way to choose which operates? If so then when I stick a toaster and an alarm clock in a box with the power cords sticking out then have I combined the two machines? Because algorithms are just machines, and most programs are like the box.

Now if by "combining two algorithms" you mean putting the two algorithms together in such a way that we have created a wholly new algorithm (much as a man and woman put their algorithms together and create a new algorithm: a child) then I think we are talking about something different and useful. Certainly one can combine algorithms in this sense. Heap sort would be an example, as would quick sort, as would hybrid sorts, etc. However by writing a program that has a heap sort in it (say to sort file dirtectory listings), and a ray tracing algorithm for some kind of flashy display, we cant say that the two together is an algorithm unless the two are part of an integral whole. Now if the heap sort was used by the ray tracing algorithm, and that it was critical to it, then I might agree it was an new algorithm. But just because I reach both algorithms by running the same executable image doesnt make them a new algorithm at all.

If you weaken the definition of algorithm to the point that you have then it becomes a useless term. Thats fine, we can play such games with just about any term, but I wonder what the objective is? Personally I dont think that "a tried and tested method of accomplishing a very basic goal" is a good description of an algorithm. For instance we might use such a term to describe using crime or ethnic scare-tactics in an election. Or fishing in a favorite location, or yelling "Fire" in a restaurant to get the waiters attention. Yet I think no computer scientist would grant that these are algorithms.

To me an algorithm is a deterministic process provably able to achieve a well definied objective. (Which is pretty close to Knuths definition below) From that definition it is difficult to consider many programs to be algorithms at all.

Incidentally the following is exerpted/quoted from Knuths Art of Programming Vol I in the introduction.

[The word algorithm is new word, not being in Websters dictionary as late as 1957. It stems from the word algorism which] comes from the name of the famous Persian textbook author Abu 'Abd Allah Muhammad ibn Musa al-Khwarizmi (c.825) ... Al-Khwarizmi wrote the celebrated book Kitab al-jabr wa'l-muqabala ("Rules of restoring and equating"); another word, "algebra," stems from the title of this book, which was a systematic study of the solution of linear and quadratic equations.[Personally I find this slightly amusing considering that modern day Persia is basically Iraq. (demerphq)]

Gradually the form and meaning of algorism became corrupted; as explained by the OED the wrod "passed through many pseudo-etymological perversions, including a recent algorithm in which it is lernedly confused" with the Greek root of the word Arithmetic. ... An early German mathematical dictionary, Vollstandiges mathematisches Lexicon (Leipzeig 1747) gave the following definition for the word Algorithmus: "Under this designation are combined the notions of the four types of arithmetic calculations, namely addition, multiplication, subtraction, division." The latin phrase algorithmus infitesmalis was at that time used to denote "ways of calculation with infinitely small quantities as invented by Leibniz."

... he then discusses Euclids algorithm for determining the GCD of two positive integers ...

The modern meaning of an algorithm is quite similar to that of a recipe, process, method, technique, procedure, routine, rigmarole, except that the word algorithm connotes something just a little different. Besides being merely a finite set of rules that gives a sequence of operations for solving a specific type of problem, an algorithm has five important features:

1. Finiteness. An algorithm must always terminate after a finite number of steps. (A procedure that has all of the characteristics of an algorithm except that it possibly lacks finiteness maybe be called a computational method. An example of a nontermination computational method is a reactive process, which continually interacts with its environment.)
2. Definateness. Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specififed for each case. ... An expression of a computational method in a computer language is a program
3. Input. An algorithm has 0 or more inputs: quantities that are given to it initially before the algorithm starts, or dynamically as the algorthm runs. These inputs are taken from specified sets of objects.
4. Output. An algorithm has one or more outputs: quantities that have a specified relation to inputs.
5. Effectiveness. An algorithm is also generally expected to be effective, in the sense that its operations must be sufficiently basic that can in principle be done exactly and in a finite length of time by someone using pencil and paper.

He goes on to discuss the ramifications of the above and then moves on to a mathematical definition:

Let us formally define a computational method to be a quadruple (Q,I Ω,f), in which Q is a set containing subsets I and Ω and f is a function from Q into itself. Furthermore f should leave Ω pointwise fixed; that is, f(q) should equal q for all elements q of Ω. The four quantities Q, I, Ω, f are intended to represent respectively the states of the computation, the input, the output, and the computational rule. Each input x in the set sequence x₀, x₁,x₂,..., as follows

x₀=x and x_k+1=f(x_k) for k>=0
the computational seuence is said to teminate in k steps if k is the smallest integer for which x_k is in Ω, and in this case it is said to produce the output x_k from x. (Note that if x_k is in Ω, so is x_k+1, becuase x_k+1=x_k in such a case.) Some computational sequences may never terminate; an algorithm is a computational method that terminates in finitely many steps for all x in I.

He then adds a discusion of effectiveness from a mathematical view, including adding such a definition to the one above. I think that if you are correct that we have not moved into proper software engineering (which is an interesting debate in itself, similar to the one about whether programming is an art or science) then using proper rigourous mathematically based deifnitions is crucial. Not wishy washy define it away to meaninglessness kind of thinking or talking.

Anyway, I guess I got carried away with the quote here, I hope its useful to this thread. :-)


---
demerphq

<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

---

• Update:  
Fixed some typos, etc. (BTW, I didnt realize that I was repeating Abigail-IIs quote in more detail until afterwards. That'll teach me to reply to a node before I finish reading the whole thread :-)