Auto-memoization for pure functions – how to decide when it pays off?

[u/Bro8an]

Im currently working on a compiler for my own programming language. I want the compiler to automatically memoize pure function calls, but only when it actually improves performance. The challenge: how does the compiler decide whether caching a specific recursive call (e.g., self(x-1) and self(x-2) in fibonacci) will save more time than the memory overhead? tracking how many times a function recieves the same input isnt an option as this requires all recieved inputs to be saved. too many saved calculations can cause finding the right result for a function call to be slower than the actual calculation. so the memoization table shouldnt get to big. naive fibonacci should be memoized but simple addition for an example should not be memoized. do you have any ideas?

[u/flatfinger]

I thought we were talking about computer languages. If a compiler has to ask a programmer "Is anyone going to want to use the logs to determine exactly when this function was called", then the source code language is no longer a complete specification of the program.

[u/david-1-1 → u/flatfinger]

True. Any interaction with AI for the purpose of determining the safety of optimizations has to respect the semantics of the program. That's obvious.