tag:blogger.com,1999:blog-8288194986820249216.post8281834452108869852..comments2024-02-04T15:47:25.088-08:00Comments on Abstract Heresies: Too much exerciseJoe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-8288194986820249216.post-1223020049436202832011-04-19T11:01:01.545-07:002011-04-19T11:01:01.545-07:00Faré said...Trying to "late bind" a func...<a href="http://www.blogger.com/profile/14063105144178880818" rel="nofollow">Faré</a> said...<br><i>Trying to "late bind" a function so it won't be optimized away only works if you assume a static compiler. A more elaborate JIT like PyPy can still see through this try.</i><br><br>That's ok. I'm not trying to win a war with a compiler that is determined to prevent stack walking. The author of an elaborate JIT ought to keep debugging in mind and offer some mechanism to tune the compiler. What I <em>am</em> suggesting is that if tail recursion is simply ‘turned on’ under more or less ‘normal’ conditions it is fairly trivial to restore enough of the backtrace should the missing frames be vital to debugging.<br><br />But even if you were working with the world's most aggressive JIT, a trivial insertion of a call to print (an external side effect) would force the JIT to compile a call as a ‘subproblem’ (non tail recursive) rather than a ‘reduction’ (tail recursive).<br><br />Tail recursion is about removing returns to stack frames that are logically unnecessary. `Disabling' tail recursion simply involves adding a logical necessity to return to the caller. Passing the return value to a different callee is virtually guaranteed to work and causes the least amount of disruption, but there are some unusual scenarios involving highly optimizing compilers where it conceivably might not. Performing an external side effect *is* guaranteed to work, but it is rarely necessary to take extraordinary steps just to get a backtrace; simply turn off the extreme optimization.Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-84284509280067361732011-04-19T09:02:49.834-07:002011-04-19T09:02:49.834-07:00@Joe
Trying to "late bind" a function so...@Joe<br />Trying to "late bind" a function so it won't be optimized away only works if you assume a static compiler. A more elaborate JIT like PyPy can still see through this try.<br /><br />@Pascal<br />I'm pretty sure you could define a relatively simple macro to do that in Racket, and a much more elaborate macro to do that in any Lisp dialect well-defined enough to be code-walkable.Faréhttps://www.blogger.com/profile/14063105144178880818noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-27225879416952691352011-04-11T01:18:17.191-07:002011-04-11T01:18:17.191-07:00I can see one disadvantage of your suggested appro...I can see one disadvantage of your suggested approach to prevent tail calls: For debugging purposes, I may want to disable tail calls for a number of functions, for example in one or more modules, or in a whole program. A macro for tail call prevention could help in principle, because I can choose between two different versions of the macro. But this would mean that I would have to mark all tail calls manually, "just in case" I want to debug them.<br /><br />I think a Common Lisp-style declaration that allows me to turn off tail calls for some well-defined scope <i>without</i> marking all tail calls by hand would be better...Pascal Costanzahttps://www.blogger.com/profile/04512975624438301971noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-14105720139337759382011-04-10T16:26:16.249-07:002011-04-10T16:26:16.249-07:00I'm surprised about the logic here; it simply ...I'm surprised about the logic here; it simply doesn't make sense. For example, of course you can crash an iterative implementation of a VM where a recursive implementation wouldn't crash: you just do an infinite tail-call loop. The iterative version will never terminate, the recursive version will run out of stack space and so will perform whatever the implementation does for a stack overflow. This depends only on your language defining semantics for running out of stack space, which it happens that Python (for example) does reliably. (I just had to depend on this for a Turing tarpit language I've written. No, you don't want to know why.)<br /><br />You're being simply too abstract in your "heresies"; follow this line of thinking and there's absolutely nothing you can do on a computer.wtanksleyhttps://www.blogger.com/profile/03283393679440645366noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-2118356889713680952011-04-09T23:58:45.148-07:002011-04-09T23:58:45.148-07:00I worked on VMware's virtual machine monitor (...I worked on VMware's virtual machine monitor (VMM) from 2000 to 2009.<br /><br />Your assumption that a VMM must be undetectable to be correct is fallacious. It's the equivalent to saying AMD processors must pretend to be Intel processors to be correct. There's some intuitive force to this idea, but on reflection, requiring this would basically destroy the architecture/implementation distinction.<br /><br />VMMs are invariably detectable, like almost all other aspects of the hardware and software stack on which an application finds itself. While you can imagine elaborate heroics to avoid detection, the arms race is tilted in favor of the would-be detectors. Which, as I argue above, is fine. In fact, at VMware we went to special effort to architect a stable API for detecting and versioning our VMM.<br /><br /><br />I've written about this in a HotOS submission (http://www.usenix.org/events/hotos07/tech/full_papers/garfinkel/garfinkel.pdf) and a blog post (http://x86vmm.blogspot.com/2007/07/bluepill-detection-in-two-easy-steps.html) if you're curious about further details.Keith Adamshttps://www.blogger.com/profile/11187291538765358570noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-37704257649861995172011-04-09T21:26:26.294-07:002011-04-09T21:26:26.294-07:00You insist on a "portable" program. But...You insist on a "portable" program. But portable programs, by definition, are oblivious to the details of their environment's implementation.<br /><br />Although it doesn't come up as often as things like byte order and word size, one criterion for portability would be that a program behave identically in implementations that optimize tail calls and those that don't.<br /><br />So you're asking for a portable program that is nonportable. (-:kbobhttps://www.blogger.com/profile/11512820963025257647noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-54078588924125069862011-04-08T13:02:41.150-07:002011-04-08T13:02:41.150-07:00Hi,
Very nice post. This was actually very enligh...Hi,<br /><br />Very nice post. This was actually very enlightening. Thanks!<br /><br />PascalPascal Costanzahttps://www.blogger.com/profile/04512975624438301971noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-43058023260793612322011-04-08T12:12:05.518-07:002011-04-08T12:12:05.518-07:00Aaron asked...What prevents an implementation from...<a href="http://www.blogger.com/profile/10658555678500278995" rel="nofollow">Aaron</a> asked...<br><i>What prevents an implementation from optimizing "((lambda (x) x) y)" into "y", thereby undo-ing your attempts to prevent TCO?</i><br><br />Nothing. That is why I mentioned that you might want to late-bind the procedure:<br><br />(define *tail-call-preventer* #f)<br>(set! *tail-call-preventer* identity-procedure)<br><br>then the code becomes<br><br />(*tail-call-preventer* y)<br><br>and the compiler cannot optimize this because it cannot prove that the value of *tail-call-preventer* is always bound to the identity procedure.<br /><br />However, we can make life a tad easier for developers by turning off aggressive optimization when in debug mode (as is usually done).Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-78729137705755482242011-04-08T11:36:08.186-07:002011-04-08T11:36:08.186-07:00What prevents an implementation from optimizing &q...What prevents an implementation from optimizing "((lambda (x) x) y)" into "y", thereby undo-ing your attempts to prevent TCO?Aaronhttps://www.blogger.com/profile/10658555678500278995noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-29688884098477463672011-04-08T11:16:23.417-07:002011-04-08T11:16:23.417-07:00Perfect detection of substrates is obviously impos...Perfect detection of substrates is obviously impossible; it's a non-trivial predicate which means it almost surely falls prey to Rice's theorem.<br /><br />In practice, there are a bunch of techniques thanks to computer security concerns. (Unsurprisingly, researchers prefer to run worms & viruses in a virtual machine; even more unsurprisingly, the authors of said programs would prefer them not be runnable, much like they try to thwart using debuggers.) Some random links: http://weblogs.asp.net/jgalloway/archive/2006/10/27/Can-Operating-Systems-tell-if-they_2700_re-running-in-a-Virtual-Machine_3F00_.aspx & handlers.sans.org/tliston/ThwartingVMDetection_Liston_Skoudis.pdf & http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=5CB300F3BB2543B2B5AC460A838672B5?doi=10.1.1.99.3879&rep=rep1&type=pdfgwernhttps://www.blogger.com/profile/18349479103216755952noreply@blogger.com