기능적 언어로 작성된 프로그램에서는 스택 오버플로가 발생할 가능성이 더 높습니까?

StackOverflow https://stackoverflow.com/questions/1291402

문제

나는 ocaml을 배우기 시작했고 언어의 재귀의 힘을 정말로 높이 평가하고 있습니다.하지만 제가 걱정하는 것 중 하나는 스택 오버플로입니다.

ocaml이 함수 호출을 위해 스택을 사용하면 결국 스택이 오버플로되지 않나요?예를 들어 다음과 같은 기능이 있다고 가정해 보겠습니다.

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

결국 스택 오버플로가 발생해야 합니다.C++에서 (재귀를 사용하여) 동일한 작업을 수행한다면 오버플로될 것이라는 것을 알고 있습니다.

그래서 제 질문은 기능적 언어가 스택에서 오버플로되는 것을 방지하기 위한 보호 장치가 내장되어 있습니까?입니다.그렇지 않다면 for 루프를 사용하여 절차적 스타일로 작성된 위의 합산 알고리즘이 모든 숫자를 처리할 수 있기 때문에(정수 오버플로 무시) 유용성이 떨어지지 않습니까?

도움이 되었습니까?

해결책

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

따라서 우리는 IS tail recursive(그리고 현재 누적된 총계를 인수로 취하는) 보조 함수를 사용하는 방법을 곧 배우게 되어 최적화 프로그램이 해당 작업을 수행할 수 있습니다. 즉, 내가 녹슬었던 가능한 O'Caml 구문의 순은 다음과 같습니다.

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

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

여기서 합계는 재귀 호출에 대한 ARGUMENT(즉, 재귀 자체 이전)로 발생하므로 꼬리 최적화가 시작될 수 있습니다(왜냐하면 재귀가 일어나야 하는 마지막 일이기 때문입니다!).

다른 팁

기능적 언어는 일반적으로 훨씬 더 큰 스택을 갖습니다.예를 들어, OCaml에서 스택 제한을 테스트하기 위해 특별히 함수를 작성했는데, 호출이 발생하기 전에 10,000번이 넘는 호출이 발생했습니다.그러나 귀하의 주장은 유효합니다.스택 오버플로는 함수형 언어에서 여전히 주의해야 할 사항입니다.

함수형 언어가 재귀에 대한 의존도를 완화하기 위해 사용하는 전략 중 하나는 테일콜 최적화.현재 함수의 다음 재귀에 대한 호출이 함수의 마지막 문인 경우 현재 호출은 스택에서 삭제되고 그 자리에 새 호출이 인스턴스화될 수 있습니다.생성되는 어셈블리 명령어는 기본적으로 명령형 스타일의 while 루프에 대한 명령어와 동일합니다.

재귀가 마지막 단계가 아니기 때문에 함수는 마무리 호출을 최적화할 수 없습니다.먼저 반환해야 하며 그 다음 결과에 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;;

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

대부분의 다른 기능적 언어에서는 효율적으로 구현하기 위해 꼬리 재귀가 필요하지 않습니다.일부는 그렇게 하기로 선택하고 다른 일부는 그렇지 않습니다. 하지만 구현하기가 상대적으로 쉽기 때문에 대부분의 구현에서는 그렇게 할 것으로 예상됩니다.

초보자가 스택을 날려버리는 깊은 재귀를 작성하는 것은 확실히 쉽습니다.Objective Caml은 그 점에서 특이합니다. 도서관 List 함수는 긴 목록의 경우 스택으로부터 안전하지 않습니다..다음과 같은 애플리케이션 조화 실제로 Caml 표준을 대체했습니다. List 스택 안전 버전의 라이브러리.대부분의 다른 구현은 스택을 사용하여 더 나은 작업을 수행합니다.(부인 성명:내 정보는 Objective Caml 3.08을 설명합니다.현재 버전인 3.11이 더 나을 수도 있습니다.)

뉴저지의 표준 ML 스택을 사용하지 않는다는 점에서 특이하므로 힙이 부족할 때까지 깊은 재귀가 계속됩니다.Andrew Appel의 훌륭한 책에 설명되어 있습니다. 연속으로 컴파일하기.

나는 여기에 심각한 문제가 있다고 생각하지 않습니다.함수형 언어에서 수행할 가능성이 더 높은 많은 재귀 코드를 작성하려면 테일이 아닌 호출과 스택 크기를 다음과 같이 인식해야 한다는 "인식 지점"에 가깝습니다. 처리할 데이터의 크기와 비교합니다.

이것은 까다롭습니다. 원칙적으로는 그렇습니다. 그러나 기능적 언어의 컴파일러와 런타임은 기능적 언어의 재귀 정도를 증가시킵니다.가장 기본적인 것은 대부분의 기능적 언어 런타임이 일반적인 반복 프로그램이 사용하는 것보다 훨씬 더 큰 스택을 요청한다는 것입니다.그러나 그 외에도 기능적 언어 컴파일러는 언어의 훨씬 더 엄격한 제약으로 인해 재귀 코드를 비재귀 코드로 훨씬 더 쉽게 변환할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top