16 events
when toggle format what by license comment
Jan 15 at 23:26 answer Neel Krishnaswami timeline score: 2
Jan 14 at 21:00 history tweeted twitter.com/StackCSTheory/status/1482095187606360065
Jan 14 at 16:50 history edited wlad CC BY-SA 4.0
fixed link
Jan 14 at 8:33 comment added wlad @SarielHar-Peled I've already mentioned memoisation in my question. In Python, it's even easier than you said: docs.python.org/3/library/functools.html - This results in a "top-down" style of dynamic programming instead of a (loosely defined) "bottom-up" style. I think the tape-based approach to autodiff is an instance of bottom-up style, and so memoisation alone is not enough.
Jan 14 at 2:25 comment added naasking Related are compiler optimizations like "fusion" (stackoverflow.com/questions/38905369/…), and supercompilation (stackoverflow.com/questions/9067545/what-is-supercompilation), although those are pretty advanced compared to basic recursion elimination. I mention them because it's not always possible to eliminate recursion without adding allocation, but this can sometimes be done via fusion/supercompilation passes.
Jan 14 at 2:20 comment added naasking There are many posts on eliminating recursion, such as: softwareengineering.stackexchange.com/questions/347582/…
Jan 13 at 22:29 comment added Sariel Har-Peled Such an automatic system seems to be unlikely to exist... Specific toy problems (like the above) can of course be handled. Automatic memoization (which is already enough to reduce the running time to polynomial) are supported by some languages like lisp and scheme. A nice description of this is in en.wikipedia.org/wiki/… . A more "standard" description how to do this transformation is in Jeff Erickson algorithms book. Maybe ask in compilation/programming-languages forum about this...
Jan 13 at 20:19 history edited wlad CC BY-SA 4.0
added 178 characters in body
Jan 13 at 20:01 history edited wlad CC BY-SA 4.0
deleted 3 characters in body
Jan 13 at 19:46 history edited wlad CC BY-SA 4.0
added 18 characters in body
Jan 13 at 19:37 history edited wlad CC BY-SA 4.0
added 4 characters in body
Jan 13 at 19:30 history edited wlad CC BY-SA 4.0
added 88 characters in body
Jan 13 at 19:20 history edited wlad CC BY-SA 4.0
edited title
Jan 13 at 19:11 history edited wlad CC BY-SA 4.0
added 11 characters in body
Jan 13 at 19:05 history edited wlad CC BY-SA 4.0
deleted 1 character in body
Jan 13 at 18:58 history asked wlad CC BY-SA 4.0