Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!umd5!uflorida!novavax!proxftl!bill
From: bill@proxftl.UUCP (T. William Wells)
Newsgroups: comp.lang.c
Subject: Re: volatile
Summary: unsolvable problems are UNSOLVABLE
Message-ID: <227@proxftl.UUCP>
Date: 27 May 88 22:54:59 GMT
References: <20345@pyramid.pyramid.com> <502@wsccs.UUCP> <51431@sun.uucp> <11566@mimsy.UUCP>
Organization: Proximity Technology, Ft. Lauderdale
Lines: 97

In article <11566@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) writes:
> There are pragmatic reasons not to find all cases of volatility (it may
> take too long on a given machine), but it can be done.  When it can be
> done, it should be done.
> --
> In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
> Domain:       chris@mimsy.umd.edu     Path:   uunet!mimsy!chris

The reasons are NOT pragmatic, they are theoretical.  It is NOT
possible to find all cases of volatility in a program.  It is not
even reasonable to try to find most cases of volatility in a
program.

Let me show you why.

Consider a device register (Dr).  Consider a pointer variable
(dp) which is of type `pointer to type of' the device register.
We need to know whether the pointer variable ever points to
volatile memory.

Take your program.  Replace every exit() call with while (1);.

Wherever dp is assigned to, add the statement: if (dp == &Dr)
exit(0); just after the assignment.  Make any kludges necessary
to cope with embedded assignments.

Your fudged program will halt if and only if dp can be a pointer
to Dr, thus requiring that dp is a pointer to something
volatile.  Thus the problem of determining whether dp is a
pointer to volatile is the same problem as determining whether
your fudged program halts.

Now, in this contrived example, it is easy to see how one might,
by exmaining references to variables in the source, determine
that dp is a pointer to something volatile.  (Assuming that the
program does no memory allocation, anyway.) That is an example of
how the halting problem has easy solutions in certain cases.

Let us consider an unsolvable problem: a program which maps
memory from a file.  Is the mapped data volatile?  It is only if
the file can be modified.  This information is not available to
the compiler.

You, the program writer may know: "the data in this file will be
computed by a cooperating process, it is volatile" or "this is a
file of data which has been pre-computed and will not be
changed".  Your program might be designed to handle both cases.

You, the program writer may know: "this pointer variable is only
used when the mapped file is volatile" and "this pointer variable
is only used when the mapped file does not change".

The compiler CAN'T determine which is which, because the compiler
must assume that the mapped file is either one or the other.

Let's consider a related problem.  Suppose that your volatile
object (or a pointer to it) is going to be in dynamically
allocated memory.  NO algorithm is going to be able to determine
whether the object in question will even exist, much less that it
is volatile.

If you answer that that is bad programming practice, well perhaps
you have forgotten something: C is used to program systems.  Most
of these systems manage resources in some way or another.  Parts
of these managed resources will often be volatile, but, since it
is the management system itself which determines what is
volatile, there is no way that one can avoid writing code that
requires determination of volatility.  Since the compiler can't
do it, you, the programmer, must tell it.

As an example of this, consider one possible way to implement a
scheduler.  First, you have a low level scheduler which uses
fixed priorities to determine the next task to run.  Second, you
have a high level scheduler which periodically analyzes the
processor activity and adjusts the priorities accordingly.
(Hmmm, this sounds familiar.  UNIX perhaps? :-) Now, there may
be nothing in the low level scheduler which requires that the
priority be considered volatile.  Or you could say that the
existence of (/dev/kmem on UNIX) global accessing methods to the
data for the low level scheduler requires that every variable in
it be volatile.  You can't insist that the compiler have access
to the high level scheduler code, because that is a separately
compiled unit; there might even be more than one of them.

Or, you can assume that all variables in the low level scheduler
are not volatile unless specifically declared so.

Understamd: volatile is intended for programmers who write
programs that deal with multiprogramming or multiprocessing in
some way.  Said programmer, in the normal course of events,
writes programs where the volatility of an object is an important
aspect of the object.  And the programs which he writes can't be
analyzed by any algorithm to determine the volatility of the
objects.  The volatile keyword is there as an aid to the
programmer who is stuck with this problem.  Demanding that the
compiler writers `do something' will not accomplish anything.
Creating the volatile keyword will.