On 4/18/13 7:57 AM, Joseph Spinden wrote:
"Another result (the unsolvability of the halting problem) may be
interpreted as implying the impossibility of constructing a program
for determining whether or not an arbitrary given program is free of
'loops'."
Well, compilers can't reason about all forms of loops, but note how the
compiler realized that the accumulating
"sum" didn't require iteration. (In the assembly it collapses to a
"movl $30,%eax".) Flat maps and reductions with simple
transformation/aggregation functions can be determined to exit.
$ cat collapse.c
int
main ()
{
unsigned i;
unsigned sum = 0;
for (i = 0; i < 10; i++) sum += 3;
return sum;
}
$ gcc -S -O3 collapse.c
$ cat collapse.s
.file "collapse.c"
.section .text.startup,"ax",@progbits
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
movl $30, %eax
ret
.cfi_endproc
.LFE0:
.size main, .-main
.ident "GCC: (GNU) 4.7.2 20121109 (Red Hat 4.7.2-8)"
.section .note.GNU-stack,"",@progbits
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
