Czy program MATLAB przeprowadza optymalizację połączeń?

Question

Niedawno nauczyłem się Haskella i staram się przenosić czysty funkcjonalny styl do mojego drugiego kodu, jeśli to możliwe. Ważnym aspektem tego jest traktowanie wszystkich zmiennych jako niezmiennych, tzn. Stałych. Aby to zrobić, wiele obliczeń, które byłyby implementowane za pomocą pętli w stylu imperatywnym, musi być wykonane przy użyciu rekurencji, która zwykle powoduje karę pamięci z powodu przydzielenia nowej ramki stosu dla każdego wywołania funkcji. W specjalnym przypadku wywołania typu "tail" (gdy zwracana wartość wywoływanej funkcji jest natychmiast zwracana do wywołującego wywołanie), kara ta może zostać ominięta przez proces zwany optymalizacją wywołania końcowego (w jednej metodzie może to być wykonane przez zasadniczo zastępując połączenie jmp po poprawnym ustawieniu stosu). Czy MATLAB wykonuje domyślnie TCO, czy jest jakiś sposób, żeby to powiedzieć?

Answer 1

Gdybym zdefiniować prosty ogon rekurencyjnej funkcji:

function tailtest(n) 
    if n==0; feature memstats; return; end 
    tailtest(n-1); 
end 

i nazywają to tak, że będzie przeszukanie dość głęboko:

set(0,'RecursionLimit',10000); 
tailtest(1000); 

to nie wygląda tak, jakby ramki stosu są jedząc dużo pamięci. Jednakże, jeśli zrobię to recurse znacznie głębiej:

set(0,'RecursionLimit',10000); 
tailtest(5000); 

następnie (na moim komputerze, dzisiaj) MATLAB po prostu wywala: proces bezceremonialnie umiera.

Nie sądzę, że jest to zgodne z tym, że MATLAB wykonuje jakiekolwiek TCO; przypadek, w którym funkcja "wywołuje" samą siebie, tylko w jednym miejscu, bez zmiennych lokalnych innych niż pojedynczy argument, jest tak prosty, na jaki każdy może liczyć.

Tak: Nie, wygląda na to, że MATLAB w ogóle nie wykonuje TCO, przynajmniej domyślnie. Nie szukałem (jak dotąd) opcji, które mogłyby to umożliwić. Byłbym zaskoczony, gdyby były jakieś.

W przypadku, gdy nie zdmuchniemy stosu, ile kosztuje rekursja? Zobacz mój komentarz do odpowiedzi Billa Cheathama: wygląda na to, że czas nad głową jest nietrywialny, ale nie szalony.

... Tyle że Bill Cheatham usunął odpowiedź po tym, jak opuściłem ten komentarz. OK. Tak więc podjąłem prostą, iteracyjną implementację funkcji Fibonacciego i prosty rekursywny ogonek, wykonując w zasadzie te same obliczenia w obu przypadkach i ustalając je w czasie na fib(60). Wdrożenie rekursywne trwało około 2,5 razy dłużej niż w wersji iteracyjnej. Oczywiście, względny narzut będzie mniejszy dla funkcji, które wykonują więcej pracy niż jedno dodawanie i jedno odejmowanie na iterację.

(Zgadzam się również z sentymentem delnan za:. Wysoce rekurencyjne kod rodzaju, że czuje naturalny w Haskell jest zazwyczaj prawdopodobnie unidiomatic w MATLAB)