Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!uunet!mcsun!ukc!slxsys!ibmpcug!mantis!mathew From: mathew@mantis.co.uk (CNEWS MUST DIE!) Newsgroups: comp.lang.misc Subject: Will this *thread* ever halt? Message-ID: Date: 20 May 91 13:22:03 GMT Organization: Mantis Consultants, Cambridge. UK. Lines: 129 yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >In article mathew@mantis.co.uk (CNEWS MUST DIE!) writes: >>Yes, but do you want to have to be aware of exactly how much memory is >>available to your programs? > >Not always. But, for the compiler to warn me that >"while(1)i =i+1" will either crash or cycle state forever does not require >me to know this information. Indeed. There are always simple cases which can be analysed easily. The compiler I use gives warnings about while loops with constant boolean conditions. 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. >>Consider the following pseudo-code: >> >>i = 0 >>repeat >> allocate 1 byte of memory >> i++ >>until allocation fails >>if i is prime, while(1); >>end >> >>You can write such a program in ANSI C. In order to predict whether it will >>enter a non-terminating loop you have to know exactly how much memory is >>available to the program when it runs, to the byte. > >If your point is that one can write ANSI "C" programs that are machine >specific, sure. The above program is not machine specific. You can write it so that it will compile and run on any machine which supports ANSI C. You just can't tell whether it will terminate or not unless you know exactly how much memory that machine has. > And if your point is that one can write ANSI "C" programs >that will depend on I/O or operating system behavior, I also agree. [...] >The compiler cannot predict such paths, but it can warn us when our >programs contain i/o dependent paths that can lead to indefinite cycles. 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. >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. > We provide >abstractions in our programmng languages, but these are conveniences which >do not negate the facts that real machines do not have "integers" and >"real numbers", but only have limited representations of these mathematical >abstractions. "Real numbers" are a complete con. I'd rather leave them out of it. "Integers" _do_ exist in some programming languages; the limitation is the amount of hardware you give the language to work in. I have commented on this in another posting. > Even if the compiler implements "i" with a variable format >(e.g. bignums), the programmer will want to know if the program may >exceed thelimits of machine representation. When working with integers mathematically you have to know whether your result will become too big to work with on paper. > 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. >>The restrictions you have to place on a language in order to enable >>guaranteed termination are such that the language is not useful for general >>programming. > >Demonstrate this? Any demonstraton would seem to require unusually >precise information about the limits of ingenuity. I was talking in the present tense. If you want to start speculating wildly about future developments in program proving, then go ahead. I was also taking as given the assumption that most people require an imperative language for general programming. Given the relative popularity of pure functional languages vs C, BASIC, FORTRAN and so on, I think that that is reasonable. >>Secondly, I want to know whether my programs will work on my friends' >>machines. > >Try compiling on those machines, or compile with a "portability" flag. What is this "portability" flag supposed to do? Not bother reporting about termination? >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)"). You might be able to write a compiler which could predict whether or not a C program would run on a machine with 3104272 bytes of memory, if started at precisely 3:15:22 PM on Tuesday 21st May with no other programs resident. Whether it would be worth your while to do so is another matter. mathew