Re: Definable operators

pjj@cs.man.ac.uk (Pete Jinks) writes:
><mfinney@lynchburg.net> wrote:
>>it has also been shown, that for any set of control structures,
>>there are programs which grow exponentially in size when compared to
>>the use of another control structure.


>That's very interesting - can you give any references?


Its been a long time, but if I recall correctly, Knuth published some
work in that area (what, maybe 15 or 20 years ago?) in the major
journals (CACM, SigPlans, etc.). Knuth, of course, was not the only
one. At one time, there was quite a bit of research going on about
different control structures.


And the general problem is a lot like that of an incomplete logic such
as second order logic. There is always another axiom that can be
added. I would guess that given any set of control structures, it is
possible to find a problem which does not "fit" the existing control
structures in terms of efficiency.


For example, assume that you have a language which has only a named
block, with exit and repeat of a block (using the name for multi-level
exits and repeats) and a single, one-way conditional statement. That
is adequate for any tree-structured program to be written.


But, there are tree structured programs which are not efficient using
the above mechanisms. For example, a three-way branch based on sign
needs an extra test. You could then add a three way branch. However,
then what about an n-way branch based on a integer? O.k. say you add
that. Now how about if the branch needs to be non-deterministic or
the branches are guarded?


And even where the code is "efficient", it may not be short. Again,
there is probably always another situation which doesn't match the
existing control structures well.


So, you can take the approach of using just the very basic control
structures needed from a theoretical standpoint, OR you can take the
approach of providing a very rich set of control structures. Many
similar, perhaps, but not identical. You improve the semantic match
between the problem domain and the solution domain -- which reduces
code size and improves readability. Up to a point. The question is
where that point lies. I think we can stand a quite a few more
control structures before we reach that point.
--

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