Sv: Separating algorithms from implementations (long)

> 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

Return to the comp.compilers page.
Search the comp.compilers archives again.