What is Expressiveness in a Computer Language

Matthias Blume find at my.address.elsewhere
Mon Jun 26 04:43:23 CEST 2006


Gabriel Dos Reis <gdr at integrable-solutions.net> writes:

> rossberg at ps.uni-sb.de writes:
>
> | think that it is too relevant for the discussion at hand. Moreover,
> | Harper talks about a relative concept of "C-safety".
>
> Then, I believe you missed the entire point.
>
>    First point: "safety" is a *per-language* property.  Each language
>    comes with its own notion of safety.  ML is ML-safe; C is C-safe;
>    etc.  I'm not being facetious; I think this is the core of the
>    confusion. 
>
>    Safety is an internal consistency check on the formal definition of
>    a language.  In a sense it is not interesting that a language is
>    safe, precisely because if it weren't, we'd change the language to
>    make sure it is!  I regard safety as a tool for the language
>    designer, rather than a criterion with which we can compare
>    languages.

I agree with Bob Harper about safety being language-specific and all
that.  But, with all due respect, I think his characterization of C is
not accurate.  In particular, the semantics of C (as specified by the
standard) is *not* just a mapping from memories to memories.  Instead,
there are lots of situations that are quite clearly marked in C's
definition as "undefined" (or whatever the technical term may be).  In
other words, C's specified transition system (to the extend that we
can actually call it "specified") has lots of places where programs
can "get stuck", i.e., where there is no transition to take.  Most
actual implementations of C (including "Unix") are actually quite
generous by filling in some of the transitions, so that programs that
are officially "legal C" will run anyway.

Example:

The following program (IIRC) is not legal C, even though I expect it
to run without problem on almost any machine/OS, printing 0 to stdout:

#include <stdio.h>

int a[] = { 0, 1, 2 };

int main (void)
{
  int *p, *q;
  p = a;
  q = p-1;  /** illegal **/
  printf("%d\n", q[1]);
  return 0;
}

Nevertheless, the line marked with the comment is illegal because it
creates a pointer that is not pointing into a memory object.  Still, a
C compiler is not required to reject this program.  It is allowed,
though, to make the program behave in unexpected ways.  In particular,
you can't really blame the compiler if the program does not print 0,
or if it even crashes.

AFAIC, C is C-unsafe by Bob's reasoning.

---

Of course, C can be made safe quite easily:

Define a state "undefined" that is considered "safe" and add a
transition to "undefined" wherever necessary.

Kind regards,
Matthias



More information about the Python-list mailing list