얼랭 : 꼬리 호출 최적화되지 않은 재귀 함수가있는 stackoverflow?

Question

얼랭에서 꼬리 호출 최적화되지 않은 함수로 stackoverflow를 얻을 수 있습니까? 예를 들면, 나는 그것은 충분히 큰 목록이 결국 스택 공간과 충돌이 부족할 것입니다 그것을 전달 된 경우처럼 보일 것이

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

같은 함수가 있다고 가정합니다. 나는 이것을 이렇게 시험해 보았다 :

> 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 

그러나 결코 충돌하지 않는다! 나는 100,000,000 개의 정수리스트를 가지고 시험해 보았고, 끝내기까지 시간이 걸렸지 만, 여전히 추락하지는 않았다! 질문 :

1. 정확하게 테스트하고 있습니까?
2. 그렇다면 왜 stackoverflow를 생성 할 수 없습니까?
3. 얼랭 (Erlang)이 스택 오버 플로우가 발생하지 않도록하는 작업을하고 있습니까?

Answer 1

올바르게 테스트하고 있습니다. : 함수가 실제로 꼬리 재귀가 아닙니다. 알아 내려면 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. 

함수의 다음 꼬리 재귀 버전 :

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

컴파일로 :

{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. 

공지 사항 allocate의 부족과 tail-의 call_only 오피 재귀 버전, allocate/call/deallocate/return 시퀀스를 비 재귀 함수에서 사용합니다.

얼랭 "스택"이 매우 커서 스택 오버플로가 발생하지 않습니다.. 실제로 스택 오버플로는 일반적으로 프로세서 스택 포인터가 너무 멀리 떨어져서 프로세서 스택이 오버 플로우되었음을 의미합니다. 프로세스는 전통적으로 운영 체제와 상호 작용하여 조정할 수있는 제한된 스택 크기를 가지고 있습니다. 예를 들어 POSIX의 setrlimit을 참조하십시오.

그러나 코드가 해석 될 때 얼랭 실행 스택은 이 아니고 프로세서 스택입니다. 각 프로세스에는 운영 체제 메모리 할당 기능 (일반적으로 Unix에서는 malloc)을 호출하여 필요에 따라 확장 할 수있는 자체 스택이 있습니다.

결과적으로 malloc 호출이 성공하면 함수가 충돌하지 않습니다.

레코드의 경우 실제 목록 L은 스택과 동일한 양의 메모리를 사용하여 처리합니다. 실제로 목록의 각 요소는 두 개의 단어 (정수 값 자체, 즉 작은 단어로 묶여 있음)와 목록의 다음 요소에 대한 포인터를 사용합니다. 반대로 스택은 allocate opcode에 의해 각 반복마다 두 단어 씩 증가합니다. CP에 대한 단어 하나는 allocate으로 저장되고 현재 값에 대해서는 하나의 단어가 요청 된대로 (allocate의 첫 번째 매개 변수) 저장됩니다.

64 비트 VM에서 100,000,000 단어의 경우 목록에 최소 1.5GB가 필요합니다 (다행스럽게도 실제 스택은 두 단어마다 증가하지 않으므로 더 많음). 많은 가치들이 살아 있기 때문에 쉘에서이를 모니터링하고 화를내는 것은 어렵습니다. 당신이 볼 수 있듯이

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). 

, 재귀 호출에 대한 메모리가 즉시 해제되지 않습니다 : 당신이 함수를 생성하면 메모리 사용량을 볼 수 있습니다.