🚀 go-pugleaf

In article <gZy9221w164w@mantis.co.uk> mathew@mantis.co.uk (CNEWS MUST DIE!) writes:
>In general, though, determining whether a program will halt on a real
>computer by analysing it as a FSM requires knowledge about exactly how much
>memory is available.
>

The way you cast the problem evades the TM/FSM question.  Yes. Programs
that depend on particularities of machine configuration do depend on
particularities of machine configuration. If we write a program P that
requests specific machine configuration information, and then choses
a path based on that data, then the operation of the program will not
be the same on all machines. But, this is essentially the same situation
as i/o dependencies. I argue that it is possible, in theory, for a C
compiler to detect all paths that lead to non-terminating loops and to
flag these paths. It is not possible for a "C" compiler to determine,
in advance, the result of checking the current time, asking how much
memory is available, or reading the next character typed on a terminal.
These questions are not undecidable in the technical sense, they are
simply undetermined.

>How many non-trivial C programs don't use dynamic memory allocation?  Sure,
>you can restrict yourself to fixed-size data structures, but that leads to
>even WORSE problems when you try to handle I/O.

If we give X.c to the hypothical smart compiler and it tells us that
X.c contains a path that exceeds the process memory limits on this
machine, or that X.c contains a path that will cause it to enter a
non-terminating loop if "alloc" fails, then the compiler has solved
the halting problem for this code.

>>Again, you raise a valid issue, but I'm not clear how it applies to the
>>point at hand. If I write a program that can run correctly given a "C"
>>compiler that uses 32bits to represent integers, but which will loop
>>given an 8 bit "C" compiler, the compilers can flag the error, without
>>requiring the programmer to worry about exact representation.
>
>Eh?  The programmer wants his program to work. If it works for 32 bit ints
>but not for 16 bit ints, then he has to worry about exact representation.
>Having the compiler say "your program doesn't work because this machine has
>16 bit ints" does not mean that the programmer doesn't have to worry about
>it.

You've lost me here. The correctness of "C" programs can depend on how
the compiler implements "ints". This is a feature of the "C" language, not
an artificial constraint that I'm inventing. Programmers cannot treat
"C" as if it were more high level than it is, and expect to get away with
it. 


>>                                                 A correctly written program
>>will not depend on exactly how much memory is available, and if the compiler
>>flags such a dependency, then it has found what is most likely an error.
>
>In that case, there are no correctly-written programs which perform
>non-trivial tasks.
>

Can you give me an example of such a program. The "C" compiler, lisp
interpreter, emacs editor, news-reader, operating system, computer
algebra programs and and theorem provers we have around here seem to 
be able to tolerate wide variations in available memory.

>
>>If I had a "C" compiler that would run on, say, an IBM PC with at least
>>6 meg of memory and a large disk, which would tell me within a few days
>>whether or not an arbitrary "C" program would fail given at most
>>X bytes of memory (X < 3 meg), then 
>>I believe that at least a few people would be interested
>>in using it.
>
>Indeed. But you can't do it. Even knowing the exact value of X doesn't help;
>you have to know other things such as the value of the system clock.
>(Consider "if seconds = 32 then while (1)").
>

Again, you mistake the nature of the problem. If I claim that P
implements the function f: D -> D', then I am claiming that for any
x in the appropriate domain running P on input x will result in 
the value f(x). If the compiler can tell me that there is an x inthe
domain that causes P to enter a non-terminating loop, then the compiler
has detected a bug in my program. You are arguing that the compiler will
not be able to predict x. So what? Generally, we want to know whether the
program will compute the correct value given any input, and we include
such things as system time among the inputs. 

yodaikenchelm.cs.umass.edu (victor yodaiken) writes:

> I argue that it is possible, in theory, for a C compiler to detect all
> paths that lead to non-terminating loops and to flag these paths. 
[ ... ]
> If we give X.c to the hypothical smart compiler and it tells us that
> X.c contains a path that exceeds the process memory limits on this
> machine, or that X.c contains a path that will cause it to enter a
> non-terminating loop if "alloc" fails, then the compiler has solved
> the halting problem for this code.

Good.  Perhaps Mr. Yodaiken would care to convince us infidels once and
for all by posting some source code to do what he has so eloquently
argued can be done?  And if Mr. Yodaiken is unable/unwilling to do so,
then is this "discussion" accomplishing anything more than blowing warm
air back and forth across the networks?

The proof of the pudding, Mr. Yodaiken, is in the eating.  You've argued
that it's possible to decide the halting problem for "real computers".  
So show us.

-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@cs.arizona.edu
     uucp:       uunet!arizona!debray

In article <3409@optima.cs.arizona.edu> debray@cs.arizona.edu (Saumya K. Debray) writes:
>yodaikenchelm.cs.umass.edu (victor yodaiken) writes:
>
>> I argue that it is possible, in theory, for a C compiler to detect all
>> paths that lead to non-terminating loops and to flag these paths. 
>[ ... ]
>> If we give X.c to the hypothical smart compiler and it tells us that
>> X.c contains a path that exceeds the process memory limits on this
>> machine, or that X.c contains a path that will cause it to enter a
>> non-terminating loop if "alloc" fails, then the compiler has solved
>> the halting problem for this code.
>
>Good.  Perhaps Mr. Yodaiken would care to convince us infidels once and
>for all by posting some source code to do what he has so eloquently
>argued can be done?


I'm flattered that you have so much confidence in my abilites: if I can't
come up with an algorithm, then clearly, such an algorithm cannot exist.
There is an obvious, and obviously impractical algorithm, however. Let's
first consider the case of programs that just compute a function of 
their arguments: i.e. programs that perform no i/o but  can be written
as subroutines of the form prog( type: x, type: y .... ). 
For example, suppose we have a C function  "int f(x,y,z) int x,y,z ..."
Now we look at how "ints" are implemented on the target machine, suppose
that each int is a 32 bit value. We then emulate f(x,y,z) for each of
the mere 2^96 possible assignments. The emulation consists of single
stepping the computation of "f" either on the target computer or within
a program emulating this computer. At each step, we make a copy
of the entire memory space of the emulation. The program is sure to
either repeat state (a non-terminating loop) or exit within a bounded
amount of time because it can only reference a bounded amount of memory.

[BTW, this is not as impractical as it seems. H. Massalin has written
an ingenious assembly language optimizer that, given a short
assembly language routine that computes a simple result, will find the
shortest possible sequence of assembly statements that computes the
same function. Masslin's "Super-optimizer" essentially makes an
exhaustive search of the set of all 1 line assembly programs, then all
2 line programs, ..... With some smart heuristics the optimizer comes up with
some incredible sequences of code (e.g., a min function that has no
branch). There is a paper on the optimizer in some recent ASPLOS
proceeedings. So, enough of this whining about what we can't do. ]

Now we return to the impractical algorithm and extend it to programs that
have system calls. Ther are a couple of strategies here, but we'll take
the dumbest, since it requires the least effort  from me. Each system
call, i/o driven or not, changes program state in only a bounded number
of ways. For example, a call "read(filedescriptor,bufferaddr,n)"
will change the values of the "n" bytes of memory begining a 
"bufferaddr" in some way. Whenever we encounter such a call in the
"C" program, we simply try all 2^(n*8) possibilities. Similarly, with
calls to "alloc" which either add some non-determined data to the program
data space (up to a known limit) or return a fail code. We just test
all branches. Pretty simple, hey? 

This algorithm will work. And in some cases it might even be practical.
In hardware design it is already common to build special purpose machines
that do brute force emulations of chip behavior.  Is there a smarter
algorithm, a better programing language, a well defined o.s. interface
that will make this type of analysis practical without special purpose
hardware? No idea. But, there is emphatically no mathematical theorem
that eliminates the possibility of such an algorithm.

>The proof of the pudding, Mr. Yodaiken, is in the eating.  You've argued
>that it's possible to decide the halting problem for "real computers".  
>So show us.