11 Sep 2000 02:18:50 -0400

Related articles |
---|

Seprerating algorithms from implementations (long) TSharp@Serif.com (Toby Sharp) (2000-08-27) |

Re: Separating algorithms from implementations (long) dara_gallagher@my-deja.com (Dara Gallagher) (2000-09-09) |

Sv: Separating algorithms from implementations (long) anitac@heaven.dk (Anita Christensen & Jacob Andresen) (2000-09-11) |

From: | "Anita Christensen & Jacob Andresen" <anitac@heaven.dk> |

Newsgroups: | comp.graphics.algorithms,comp.compilers,comp.dsp |

Date: | 11 Sep 2000 02:18:50 -0400 |

Organization: | CyberCity Internet |

References: | 00-08-124 00-09-072 |

Keywords: | design, functional |

*> Toby Sharp <TSharp@Serif.com> wrote:*

*> > We might be able to solve this problem if there were some way to*

*> > describe algorithms apart from their implementations.*

*>*

*> I think functional and logical languages come closest in this*

*> regard. Unfortunately there are some disadvantages; space and time*

*> complexity is very difficult to calculate for functional programs.*

*> (This crops up on comp.lang.functional frequently.)*

*>*

*> Also, I remember hearing (from at least 10 years ago) claims to the*

*> effect that the high-level and abstract nature of modern functional*

*> programming languages (i.e. after ML) would allow compilers to*

*> perform highly extensive optimization which would be impossible*

*> with imperative languages. Unfortunately these "wonder compilers"*

*> still haven't appeared.*

If we are going to draw ML into this discussion, we should also

consider some of its benefits. I understand it is used as a

introductory language on many colleges around the world by now -- and

with good reason. It is one of the most clearcut and concise languages

I have come across. At first I also thought that this must be the

ultimate language to use to describe your algorithms in (ie

prototyping) before going ahead and coding them in a system specific

language.

As a prototyping language it is quite functional for your

mathematical needs as it tends to resemble mathematical functions. By

some hacking it is also possible to use it with OpenGL:

http://www.dina.kvl.dk/~sestoft/mosml.html

http://www.home.gil.com.au/~mthomas//

I am not going to participate in the academic discussions on what an

algorithm is, but if you have a specific programming problem and you

want to describe in a implementation-independent manner, you often

need to seek to imitate the way the problem itself is described. If

our field were psychology and we were seeking to implement algorithms

relevant to that field of study we would use natural language to

describe them. But as our field is computer graphics we tend to

describe problems in mathematical equations or theorems founded on a

mathematical basis. This is why a language for describing algorithms

in computer graphics should resemble a mathematical description as

much as possible.

This is why ML in theory should be good for a 'description language'

(hmm.. did I coin a term there?) .. but only in theory.. because an

implementation would be so much different from the description by the

time/space constraints of a functional language. Żou could argue that

using a functional language is good for understanding and for

clarification of an algorithm - but my point is that when an

implementation demands speed and is constrained to the available

hardware implementation you better 'stick to reality' and take a

practical approach.

My experience tells me that developing an initial sketch of the algorithm

in C/C++ gets you ahead further than an effort to describe the algorithm in

pseudo-code first. Even though that it might be longer than the pseudocode

it eliminates doubts that occur later in the process. For instance you could

do:

int Place(Vertex& p){

Matrix RotateaboutX= ( .., ..., ..., ... 16 floats);

Vertex out=RotateaboutX*p;

*};*

..where we have

Matrix operator*(const Matrix& LHS, const Vertex& RHS){ ... }

..and in the process assume that the class Matrix and Vertex already

are implemented an Vertex resemple a vector. By using overloaded

operators you also make the code look like its problem description in

mathematics (in this case '*' is matrix multiplication). This could be

a practical way to hide the implementation from description by using

OOP methods and some simple assumptions (in some cases you may even

have the assumed code lying around somewhere).

By doing this you also gain the benefits from at functional language

(here I think about the clarity.) From my point of view, an algorithm

is first implemented when you come around considering how the results

actually are stored inside the computer. Here OOP steps in again with

a helping hand, by giving os the standard library, thus letting us

concentrate on the algorithms themselves. Usage of STL also leads us

to the simplicity of SML.

summary:

Usage of overloaded operators and the standard library makes the

pseudocode/prototype look more like the mathematical description (thus

eliminating the need for prototyping in ML)

greetz,

J

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.