Erlang: stackoverflow z funkcją rekurencyjną, która nie jest zoptymalizowana?

Question

Czy można uzyskać stackoverflow z funkcją, która nie jest zoptymalizowana w Erlang? Na przykład załóżmy, że mam funkcję jak ten

sum_list([],Acc) -> 
    Acc; 
sum_list([Head|Tail],Acc) -> 
    Head + sum_list(Tail, Acc). 

Wydawałoby się, jak gdyby to wystarczająco duża lista została przyjęta w nim w końcu zabraknie miejsca stosu i katastrofy. Próbowałem przetestować to tak:

> L = lists:seq(1, 10000000). 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29|...] 
> sum_test:sum_list(L, 0). 
50000005000000 

Ale nigdy się nie zawiesza! Wypróbowałem go z listą 100 000 000 liczb całkowitych i ukończenie trwało dość długo, ale wciąż nie uległo awarii! Pytania:

1. Czy testuję to poprawnie?
2. Jeśli tak, dlaczego nie mogę wygenerować stackoverflow?
3. Czy Erlang robi coś, co zapobiega występowaniu stackoverflows?

Answer 1

Testujesz to poprawnie: Twoja funkcja nie jest rekursywna. Aby się o tym przekonać, możesz skompilować swój kod za pomocą erlc -S <erlang source file>.

{function, sum_list, 2, 2}. 
    {label,1}. 
    {func_info,{atom,so},{atom,sum_list},2}. 
    {label,2}. 
    {test,is_nonempty_list,{f,3},[{x,0}]}. 
    {allocate,1,2}. 
    {get_list,{x,0},{y,0},{x,0}}. 
    {call,2,{f,2}}. 
    {gc_bif,'+',{f,0},1,[{y,0},{x,0}],{x,0}}. 
    {deallocate,1}. 
    return. 
    {label,3}. 
    {test,is_nil,{f,1},[{x,0}]}. 
    {move,{x,1},{x,0}}. 
    return. 

porównania następujące ogona rekurencyjne wersja funkcji:

tail_sum_list([],Acc) -> 
    Acc; 
tail_sum_list([Head|Tail],Acc) -> 
    tail_sum_list(Tail, Head + Acc). 

zestawia jako:

{function, tail_sum_list, 2, 5}. 
    {label,4}. 
    {func_info,{atom,so},{atom,tail_sum_list},2}. 
    {label,5}. 
    {test,is_nonempty_list,{f,6},[{x,0}]}. 
    {get_list,{x,0},{x,2},{x,3}}. 
    {gc_bif,'+',{f,0},4,[{x,2},{x,1}],{x,1}}. 
    {move,{x,3},{x,0}}. 
    {call_only,2,{f,5}}. 
    {label,6}. 
    {test,is_nil,{f,4},[{x,0}]}. 
    {move,{x,1},{x,0}}. 
    return. 

zauważyć brak allocate i call_only opcode w tail- wersja rekursywna, w przeciwieństwie do wersji /sekwencja w funkcji nierekurencyjnej.

Nie otrzymujesz przepełnienia stosu, ponieważ "stos" Erlanga jest bardzo duży. Rzeczywiście przepełnienie stosu zwykle oznacza przepełnienie stosu procesora, ponieważ wskaźnik stosu procesora wyszedł zbyt daleko. Procesy tradycyjnie mają ograniczony rozmiar stosu, który można dostroić poprzez interakcję z systemem operacyjnym. Zobacz na przykład POSIX's setrlimit.

Jednak stos wywoływania Erlanga to , a nie stos procesora, ponieważ kod jest interpretowany. Każdy proces ma swój własny stos, który może rosnąć w miarę potrzeby poprzez wywoływanie funkcji alokacji pamięci systemu operacyjnego (zazwyczaj malloc na systemie Unix).

W wyniku tego funkcja nie ulegnie awarii, o ile połączenia malloc zakończą się powodzeniem.

Dla celów rzeczywistej listy L używa się tej samej ilości pamięci, co stos do jej przetworzenia. Rzeczywiście, każdy element na liście przyjmuje dwa słowa (samą wartość całkowitą, która jest zapakowana w słowo, ponieważ są małe) i wskaźnik do następnego elementu do listy. Odwrotnie, stos jest rozwijany przez dwa słowa w każdej iteracji kodem allocate: jedno słowo dla CP, które jest zapisywane przez allocate i jedno słowo jako żądane (pierwszy parametr allocate) dla bieżącej wartości.

Dla 100 000 000 słów na 64-bitowej maszynie wirtualnej lista zajmuje co najmniej 1,5 GB (więcej, niż faktyczny stos nie rośnie co dwa słowa, na szczęście). Monitorowanie i garbowanie tego jest trudne w powłoce, ponieważ wiele wartości pozostaje aktywnych. Jeśli tarło funkcję, można zobaczyć wykorzystanie pamięci:

spawn(fun() -> 
    io:format("~p\n", [erlang:memory()]), 
    L = lists:seq(1, 100000000), 
    io:format("~p\n", [erlang:memory()]), 
    sum_test:sum_list(L, 0), 
    io:format("~p\n", [erlang:memory()]) 
end). 

Jak widać, pamięć dla wywołania rekurencyjnego nie jest uwalniany natychmiast.