tag:blogger.com,1999:blog-8288194986820249216.post1738705082254774214..comments2024-03-22T05:09:17.789-07:00Comments on Abstract Heresies: ExercisesJoe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-8288194986820249216.post-19305389546317633772011-04-04T19:15:17.849-07:002011-04-04T19:15:17.849-07:00If tail-call optimization is defined only in terms...If tail-call optimization is defined only in terms of space used, then Exercise 1 requires a way to detect space usage without crashing unrecoverably. In a sufficiently underspecified language, this is impossible; e.g. in R5RS Scheme, memory might be infinite, and memory usage might vary arbitrarily for reasons unrelated to your program, and there's no way to ask about memory usage or catch out-of-memory errors — and any of these possibilities makes tail-recursion potentially unobservable. But anything is impossible in a sufficiently underspecified language, so this interpretation isn't very interesting. Given the realistic assumptions of upper and lower bounds on available memory, no arbitrary memory use (e.g. no more than a naive interpreter), and a way to catch out-of-memory errors, can't we always detect TCO by recursing to a depth exceeding the maximum possible memory, and catching out-of-memory errors? Or by measuring the maximum possible depth by nontail recursion, and seeing whether it varies when wrapped in different depths of tail recursion?<br /><br />I think the argument that a SSC could rewrite the program to run in constant space is not a problem, because a compiler that does so <i>is</i> a tail-recursive compiler, as far as is observable. We can't determine the implementation's behavior on *all* programs, only what it does for specific programs.<br /><br />It is odd that Scheme requires a space optimization without specifying anything else about space. Is the point you're trying to make here that tail-call optimization is meaningful only wrt the informal operational semantics?Arcane Sentimenthttps://www.blogger.com/profile/04144052171693893368noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-84992347448437264552011-04-01T16:51:07.314-07:002011-04-01T16:51:07.314-07:00mquander said...
here's a program that should...<a href="http://www.blogger.com/profile/04628649386002008189" rel="nofollow">mquander</a> said...<br><br /><i> here's a program that should work, but would crash if a compiler tried to naively apply TCO</i><br><br /><br><br />You're adding the additional assumption that your compiler has a particular kind of bug. Can you write a test that depends solely on the language definition and not on the quirks of a particular implementation of the compiler?<br><br><br />Assume this: I have an ANSI C interpreter that is very pedantic and perverse. It rigidly follows the defined semantics of ANSI C, but it handles `unspecified behavior' (according to the language spec) by silently modifying memory in an undocumented way. (I believe that `unspecified behavior' covers that possibility.)<br>So why do you think your program would properly distinguish a tail-recursive interpreter from a non-tail-recursive one?Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-34439020858298434492011-04-01T16:12:33.365-07:002011-04-01T16:12:33.365-07:00In the spirit of your 1a exercise and kbob's s...In the spirit of your 1a exercise and kbob's suggestion, here's a program that should work, but would crash if a compiler tried to naively apply TCO:<br /><br />http://pastebin.com/c8QbsqYm<br /><br />Happily, GCC is pretty smart! On -O2 and -O3, it will tail-call optimize acc_normal_rec, but it will refuse to tail-call optimize acc_evil_rec -- presumably it has a heuristic like "don't do TCO if the call takes any references to local variables."mquanderhttps://www.blogger.com/profile/04628649386002008189noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-7001573067776222192011-04-01T13:37:34.360-07:002011-04-01T13:37:34.360-07:00/*
* In a separate compilation unit, save is defi.../*<br /> * In a separate compilation unit, save is defined as:<br /> *<br /> * void save(int *p)<br /> * {<br /> * *p = (int)&p;<br /> * }<br /> */<br />extern void save(int *);<br /><br />void recurse(int n, int *p)<br />{<br /> if (n == 0)<br /> return;<br /> save(p);<br /> recurse(n - 1, p + 1);<br />}<br /><br />int is_tail_recursive(void)<br />{<br /> int a[2];<br /> recurse(2, a);<br /> return a[0] == a[1];<br />}<br><br />This code tests if the addresses of the arguments change during a recursive call. But you need two additional assumptions:<br><br />1. Without tail recursion a compiler is <em>prohibited</em> from moving stack frames.<br><br />2. With tail recursion, a compiler is <em>required</em> to use stack frames in a particular order.<br><br />It is unlikely someone would write a compiler that did not optimize tail recursion but nevertheless moved stack frames around, so the test for non tail recursion is unlikely to fail. (But it isn't inconceivable.) However, a compiler like Chicken, which most definitely supports tail recursion, would not pass this test.<br><br />Can you write a test that depends solely on the language definition and not on the quirks of a particular implementation of the compiler?Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-60735652565494046182011-04-01T12:31:44.093-07:002011-04-01T12:31:44.093-07:00kbob said...
I wrote a C function, is_tail_recursi...<a href="http://www.blogger.com/profile/11512820963025257647" rel="nofollow">kbob</a> said...<br><br /><i>I wrote a C function, is_tail_recursive,<br />that compares the addresses of local variables in different invocations. It works, at least for GCC 4.4.5.</i><br><br />Please post! (Convert leading space characters to &nbsp; chars for indentation.)<br><br />Why do you think it works?Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-33520934555923342092011-04-01T12:30:34.662-07:002011-04-01T12:30:34.662-07:00Here it is.
https://gist.github.com/898702Here it is.<br /><br />https://gist.github.com/898702kbobhttps://www.blogger.com/profile/11512820963025257647noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-6644845626495558312011-04-01T12:22:08.776-07:002011-04-01T12:22:08.776-07:00GCC can optionally optimize tail calls using the -...GCC can optionally optimize tail calls using the -foptimize-sibling-calls switch.<br /><br />I wrote a C function, is_tail_recursive,<br />that compares the addresses of local variables in different invocations. It works, at least for GCC 4.4.5.<br /><br />So that solves exercise 1. Given the predicate is_tail_recursive, exercise 1a is trivial, so I'm not sure why that's an extra credit problem. (-:kbobhttps://www.blogger.com/profile/11512820963025257647noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-453786904186803792011-04-01T12:07:15.758-07:002011-04-01T12:07:15.758-07:00Can your sufficiently smart compiler™ solve the ha...Can your sufficiently smart compiler™ solve the halting problem?<br><br />If not, how can it ‘remove the call to [cons]’ without <em>proving</em> that every ‘silly procedure you nest it in’ does in fact halt?<br><br />Consider this code:<br><br />(define (solution-exists? solution-finding-program)<br /> (let ((test-program<br /> (sufficiently-smartly-compile<br /> `(define (test)<br /> (forward-reference<br /> ,solution-finding-program)<br /> #t))))<br /> (assembly-code/contains-call?<br /> test-program<br /> 'forward-reference)))<br /><br><br />If the SSC™ can optimize this, then we can solve the halting problem. On the other hand, if the SSC™ <em>cannot</em> optimize it, then we have a suitable mechanism for reliably and predictably defeating tail recursion.Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-84349660611479748042011-04-01T11:58:18.375-07:002011-04-01T11:58:18.375-07:00John: You could easily set up a situation where, ...John: You could easily set up a situation where, to determine whether the optimization is possible, the compiler would need to solve the halting problem. So any optimizer would have to give up in some cases.mquanderhttps://www.blogger.com/profile/04628649386002008189noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-49730154994633126482011-04-01T11:38:38.627-07:002011-04-01T11:38:38.627-07:00I may be wrong, but it seems to me that anything y...I may be wrong, but it seems to me that anything you do to defeat tail recursion, short of calling write-char, can be removed by a compiler that does interprocedural optimization and effects analysis. For example, you can rewrite (f x) in tail position as (let ((y (f x))) (cons 'a 'b) y), but the SSC will see that the result of this cons is garbage no matter what silly procedures you nest it in, and remove the call to it. (I'll agree that even a SSC can't notice that the write-char is being done to a junk output file and remove it!)John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.com