Byłem wczoraj na konwencie StackOverflow Dev Days, a jeden z mówców mówił o Pythonie. Pokazał funkcję Memoize i zapytałem, czy istnieje jakikolwiek sposób, aby nie używać jej w funkcji nieczystej. Powiedział, że nie, to w zasadzie niemożliwe, a jeśli ktoś mógłby wymyślić sposób, by to zrobić, to byłaby świetna praca doktorska.

To mnie wprawiło w zakłopotanie, ponieważ kompilatorowi / interpreterowi nie wydaje się aż tak trudne do rozwiązania rekurencyjnego. W pseudokodzie:

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

To podstawowy pomysł. Oczywiście potrzebowałbyś pewnego rodzaju kontroli, aby zapobiec nieskończonej rekursji na wzajemnie zależnych funkcjach, ale nie jest to zbyt trudne do skonfigurowania.

Funkcje wyższego rzędu, które pobierają wskaźniki funkcji, mogą być problematyczne, ponieważ nie można ich zweryfikować statycznie, ale moje pierwotne pytanie zakłada, że ​​kompilator ma jakieś ograniczenie językowe do wyznaczenia, że ​​tylko czysty wskaźnik funkcji może zostać przekazany do określonego parametru . Gdyby taki istniał, mógłby zostać użyty do spełnienia warunku.

Oczywiście byłoby to łatwiejsze w języku skompilowanym niż w języku interpretowanym, ponieważ całe to chrupanie liczb wykonano by przed wykonaniem programu, a więc nie spowolniło niczego, ale tak naprawdę nie widzę żadnych fundamentalnych problemów, które uniemożliwiałyby oceniać.

Czy ktoś z odrobiną wiedzy w tej dziedzinie wie, czego mi brakuje?