On 6/28/07, Chuck Esterbrook <[EMAIL PROTECTED]> wrote:
On 6/27/07, Christopher Smith <[EMAIL PROTECTED]> wrote: > On Jun 27, 2007, at 5:12 PM, Chuck Esterbrook wrote: > > >> The functional programming term for this is memoization, and not only > >> does it do this automatically, but it provides the added benefit of > >> being able to prove when a cached value can be safely reused (the > >> logic you describe works great with functional programming, but > >> because of the wonders of state and side effects, it is much more > >> difficult to prove in a non-functional context). > > Anyway, I just read this statement: "However, memo-functions are not > > supported in Haskell, so we will need to do some extra work to > > construct and use an explicit cache." Chris, does this conflict with > > your statement above or are we talking two different topics? Or > > perhaps you were referring to languages other than Haskell. > I was referring to Haskell. I believe the paper is referring to > explicit memoization tied to the output from monads (i.e. where state > is involved). I'm referring to the "automagic" memoization that the > compiler & runtime do for you for the parts of your code that don't > interact with monads (like this sort function). > > "Automagic" memoization isn't really a function of a language at all, > but rather the implementation. All a language can do is make it > easier for the implementation to figure out when it can do it (which > Haskell and C++ templates both do very well... but only one of them > looks at all elegant ;-). Okay this is a bit pie in the sky, but here I go anyway: Given that functional code can be mathematically reasoned about (perhaps not including code that contains monads?) and things about the code can be proved, would it be possible at some point for a program to rewrite a function to be more efficient, but identical in definition (not code definition but input --> output definition)?
Short answer; Yes. Example: Trig identities. More genrally all kinds of functional identities. Abtract answer: Category theory, functors http://www.freetechbooks.com/about469.html BobLQ And is anyone researching something like this that you know of?
-Chuck
-- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
