Gotos may be Harmful, but Labels are Neat!

For quite a while using of goto statements in all the programming
languages have been considered as a bad style of programming. The
harmfulness of goto comes from a discovery in the field of structured
programming that any program with goto statements can be automatically
rewritten with loops, and that it is hard to verify automatically
constraints on the variables if goto is used. In practice, it is hard to
understand the logic of the complex execution paths following the web of
gotos.


While the demise of goto may be helpful, together with goto labels are
gone as well. But labels may be used without gotos: below I show that
compilers and programmers may take advantage of labels without using gotos
in any (imperative) programming language. The basic idea is to use labels
at compile and at run-time to verify the intended logic of a program:
first, a programmer defines possible execution paths using labels -- then
the compiler and run-time system verify the actual execution paths against
the specified. In order to better understand this idea, first consider a
similar idea of a type declaration.


Traditionally, a program in an imperative language with types can be
construed of two logical parts: the declaration of types and typed
variables, and the executable part that uses declared variables. A
programmer designs a set of types and a set of variables and places them
in the declarative part of a program. Then, she encodes the imperative
part of a program where she uses the already declared types and variables.
The compiler and run-time system check the use of the variables in the
imperative part against their declarations stored in the declarative part.
This scheme is consid- ered useful in catching so-called `type' errors
before and during run-time.


Now let us get back to labels: they may be used in order to verify the
control flow of a program following the same pattern as types are used to
verify the use of variables above: a programmer encodes possible ways in
which the run-time system will reach different points in the program using
sequences of labels. Let us call these sequences paths. Then, when writing
an imperative part of a program, she places the labels that have been used
in the paths in the appropriate places of the program. After that, the
compiler and the run-time system may try to match the already declared
paths with the paths that could be construed from the labels placed in the
imperative part of a program.


As in the case of types and variables, paths may prevent a programmer from
gruesome logical errors at compile time when writing or modifying any part
of a program: the compiler may verify some violations of the intended path
declarations against the control-flow graph. Also, at run-time, the price
of verifying the execution path is negligent, while the quality diagnostic
of a path violation is invaluable.


Seems that checking the execution paths can be easily done by declaring
those paths with regular expressions and/or with context-free grammars.
At least the run-time checks can be implemented orthogonnaly to the
compiler and run-time system -- using a small library of fucntions used
instead of labels that print out the name/code of the label. lex and/or
yacc could then analyze the printed stream of labels at run-time, or
afterwards.


I have not implemented such a system (yet). Have somebody heard of systems
like this?


Regrads, Boris.


EXAMPLE


Consider using paths in the following program that calculates the roots of
a quadratic equation:


Labels:
NotSquare /* when it is a linear equation */
NoRoots /* equation has no roots */
DiscrLess /* when discriminant is less than zero */
DiscrNull /* when discriminant is null */
DiscrGreater /* when discriminant is more than zero */
ImRoots /* no real roots */
SameRoots /* single root */
TwoRoots /* two roots */


Possible Paths:
NotSquare <OneRoot | NoRoots>
DiscrNull SameRoots
DiscrLess ImRoots
DiscrGreater TwoRoots


A C program with labels:
/* calc. roots r1, r2 of the equation a*x^2 + b*x +c = 0
          returns the nonegative number of real roots,
                    or -2 for imaginary roots */
int square(int a, int b, int c, float *r1, float *r2)
{
if ( !a )
{
  NotSquare:
  if ( !b )
  {
      NoRoots:
      return 0;
  }
  *r1 = *r2 = ((float)c)/((float)b);
  OneRoot:
  return 1;
}
else
{
  int discr = b*b - 4*a*c;
  if ( !discr )
  {
    DiscrNull:
    *r1 = *r2 = ((float)(-b))/((float)(2*a));
    SameRoots:
    return 1;
  }
  else if ( discr < 0 )
  {
    DiscrLess:
    *r1 = ( ((float)(-b)) + sqrt((float)-discr) )/((float)(2*a));
    *r2 = ( ((float)(-b)) - sqrt((float)-discr) )/((float)(2*a));
    ImRoots:
    return -2;
  }
  else
  {
    DiscrGreater:
    *r1 = ( ((float)(-b)) + sqrt((float)discr) )/((float)(2*a));
    *r2 = ( ((float)(-b)) - sqrt((float)discr) )/((float)(2*a));
    TwoRoots:
    return 2;
  }
}
}
--

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