함수 언어로 된 프로그램이 스택 오버플로를 일으킬 가능성이 더 높습니까?

Question

나는 ocaml을 배우기 시작했으며, 언어에서 재귀의 힘을 정말로 감사하고있다. 그러나 내가 걱정하는 한 가지는 스택 오버플로입니다.

ocaml이 함수 호출 용 스택을 사용하는 경우 스택 오버플로가 발생하지 않습니까? 예를 들어, 다음 함수가있는 경우 :

let rec sum x = 
    if x > 1 then f(x - 1) + x 
    else x;; 

결국 스택 오버플로가 발생해야합니다. C++에서 동일한 작업을 수행했다면 (재귀를 사용하여) 오버플로가 발생합니다.

내 질문에, 함수 언어가 스택 오버플로를 방지하기위한 안전 장치가 내장되어 있습니까? 그렇지 않은 경우, for 루프를 사용하여 절차 스타일로 작성된 위의 합계 알고리즘이 임의의 수를 처리 할 수 ​​있기 때문에 (정수 오버플로를 무시함) 이와 같이 덜 유용하지 않습니까?

Answer 1

모두 (적절한 구현은 ;-) 기능 언어가 꼬리 재귀를 최적화하지만 재귀 호출이 마지막 작업이 아니기 때문에 (여기에 추가가 필요함) 여기에서 수행 한 작업이 아닙니다.

그럼, 곧 IS 꼬리 재귀 적 (그리고 총 합계가 인수로 누적되는) 보조 함수를 사용하는 것을 배웁니다. 따라서 옵티마이 저는 자신이 할 수있는 작업, 즉 가능한 O'Caml 구문의 net '녹슨 M :

let sum x = 
    aux(x)(0);; 

let rec aux x accum = 
    if x > 1 then aux(x - 1)(accum + x) 
    else (accum + x);; 

여기서 합은 재귀 자체 전에, 즉 재귀 호출, 인수로 발생하는, 그래서 꼬리 최적화에 찰 수 (재귀 일어날 필요가 마지막이기 때문에 !).

Answer 2

스키마와 같은 일부 기능 언어는 tail recursion은이 반복과 동일하도록 최적화되어야한다고 지정합니다. 따라서 Scheme의 꼬리 재귀 함수는 반복 횟수에 관계없이 스택 오버플로를 발생시키지 않습니다. (물론 끝나지 않은 다른 곳에서도 상호 재귀를 반복하거나 반복하지 않는다고 가정해야합니다.)

대부분의 다른 함수형 언어는 꼬리 재귀를 효율적으로 구현할 필요가 없습니다. 일부는 그렇게하기로 선택하고 다른 일부는 그렇지 않지만 구현하기가 상대적으로 쉽기 때문에 대부분의 구현이 그렇게 할 것으로 기대합니다.

Answer 3

일반적으로 기능 언어에는 더 큰 스택이 있습니다. 예를 들어 OCaml에서 스택 제한을 테스트하기위한 함수를 작성했으며, barfed 전에 10,000 개 이상의 호출을 처리했습니다. 그러나 귀하의 요지는 유효합니다. 스택 오버플로는 여전히 기능적 언어로주의해야합니다.

재귀에 의존하지 않도록 기능 언어에서 사용하는 전략 중 하나는 tail-call optimization을 사용하는 것입니다. 현재 함수의 다음 재귀 호출이 함수의 마지막 문인 경우 현재 호출을 스택에서 삭제하고 새 호출을 그 위치에서 인스턴스화 할 수 있습니다. 생성 된 어셈블리 명령어는 기본적으로 while-loops for 명령형 명령어와 동일합니다.

재귀가 마지막 단계가 아니기 때문에 함수가 마무리 호출을 최적화 할 수 없습니다. 먼저 반환해야하고 결과에 x를 더할 수 있습니다.일반적으로이 방금이 까다 롭습니다

let rec sum x = 
    let sum_aux accum x = 
    if x > 1 then sum_aux (accum + x) (x - 1) 
    else x 
    in sum_aux 0 x;; 

Answer 4

다른 매개 변수와 함께 어큐뮬레이터를 전달하는 도우미 함수 작성, 주위에 쉽게 얻을 - 원칙 예에서,하지만 기능적인 언어에 대한 컴파일러와 런타임은 차지 기능적 언어에서 재귀 정도가 증가했습니다. 가장 기본적인 것은 대부분의 함수형 언어 런타임이 일반적인 반복 프로그램이 사용하는 것보다 훨씬 더 큰 스택을 요청한다는 것입니다. 그러나 기능적 언어 컴파일러는 언어의 훨씬 엄격한 제한으로 인해 재귀 코드를 비 재귀 적으로 변환 할 수 있습니다.

Answer 5

초심자가 스택을 날리는 깊은 재귀를 작성하는 것은 확실히 쉽습니다. 목표 Caml이 특이한 점은 라이브러리 List 함수가 긴 목록에 대해 스택 안전하지 않음을 나타냅니다. Unison과 같은 응용 프로그램은 실제로 Caml 표준 List 라이브러리를 스택 안전 버전으로 대체했습니다. 다른 대부분의 구현은 스택에서 더 나은 작업을 수행합니다. (면책 조항 : Objective Caml 3.08에 대한 나의 정보는 3.11의 현재 버전이 더 좋을 수 있음을 나타냅니다.)

Standard ML of New Jersey은 스택을 사용하지 않으므로 드문 편이지만, 힙이 부족할 때까지 계속 깊은 재귀를 수행합니다. . Andrew Appel의 우수 서적 Compiling with Continuations에 설명되어 있습니다.

여기 심각한 문제가 있다고 생각하지 않습니다. 기능적인 언어로 할 가능성이 더 많은 재귀 코드를 작성하려고한다면 비 꼬리 호출과 스택 크기를 다음과 같이 인식해야한다는 "인식의 요점"이 더 중요합니다. 처리 할 데이터의 크기와 비교합니다.