순수 함수형 언어에서는 참조 계산을 사용하지 않는 이유는 무엇입니까?

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

문제

순수 함수형 언어에서는 데이터가 불변입니다.참조 카운팅을 사용하면 참조 순환을 생성하려면 이미 생성된 데이터를 변경해야 합니다.순전히 함수형 언어에서는 순환 가능성에 대해 걱정하지 않고 참조 계산을 사용할 수 있는 것 같습니다.아 맞나요?그렇다면 왜 그렇지 않습니까?

많은 경우 참조 카운팅이 GC보다 느리다는 것을 이해하지만 적어도 일시 중지 시간은 줄어듭니다.일시정지 시간이 좋지 않은 경우 참조 카운팅을 사용할 수 있는 옵션이 있으면 좋을 것입니다.

도움이 되었습니까?

해결책

귀하의 질문은 잘못된 가정에 근거합니다. 순환 참조와 불변의 데이터를 갖는 것이 완벽하게 가능합니다. 불변의 데이터를 사용하여 원형 참조를 만드는 다음 c# 예제를 고려하십시오. 

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

이러한 유형의 트릭은 많은 기능적 언어로 수행 할 수 있으므로 모든 수집 메커니즘은 원형 참조의 가능성을 처리해야합니다. 나는 원형 참조로서 Ref Counting 메커니즘이 불가능하다고 말하는 것이 아닙니다.

편집 일시적인

의견에 대한 응답으로 ... 이것은 Haskell의 사소한 것입니다.

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

그리고 SML에 대한 노력은 거의 없습니다.

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

돌연변이가 필요하지 않습니다.

다른 팁

Java 및 C#과 같은 다른 관리 언어에 비해 순수 함수형 언어는 미친 듯이 할당합니다..또한 다양한 크기의 개체를 할당합니다.알려진 가장 빠른 할당 전략은 인접한 여유 공간("nursery"라고도 함)에서 할당하고 다음 사용 가능한 여유 공간을 가리키도록 하드웨어 레지스터를 예약하는 것입니다.힙에서의 할당은 스택에서의 할당만큼 빠릅니다.

참조 카운팅은 근본적으로 이 할당 전략과 호환되지 않습니다.Ref counting은 객체를 free list에 올렸다가 다시 제거합니다.참조 카운팅에는 새 개체가 생성될 때 참조 카운트를 업데이트하는 데 필요한 상당한 오버헤드가 있습니다(위에서 언급한 것처럼 순수 기능 언어는 미친 듯이 작동합니다).

참조 카운팅은 다음과 같은 상황에서 정말 잘 작동하는 경향이 있습니다.

  • 거의 모든 힙 메모리는 라이브 개체를 보관하는 데 사용됩니다.
  • 할당 및 포인터 할당은 다른 작업에 비해 자주 발생하지 않습니다.
  • 참조는 다른 프로세서나 컴퓨터에서 관리될 수 있습니다.

오늘날 최고의 고성능 참조 계산 시스템이 어떻게 작동하는지 이해하려면 다음을 참조하십시오. 데이비드 베이컨 그리고 에레즈 페트랑크.

몇 가지가 있다고 생각합니다.

  • 거기 ~이다 사이클: "Let Rec"는 많은 언어로 "원형"구조를 만들 수 있습니다. 이 외에도 불변성은 일반적으로주기를 의미하지 않지만 규칙을 깨뜨립니다.
  • Ref-Counts는 목록에서 나쁘다: 참조 카운트 컬렉션이 FP에서 자주 찾을 수있는 긴 단일 연결된 구조와 함께 잘 작동한다는 것을 모르겠습니다 (예 : 느리게, 꼬리 추방을 보장해야합니다 ...)
  • 다른 전략에는 이점이 있습니다: 당신이 암시하는 것처럼, 다른 GC 전략은 일반적으로 메모리 지역에 대해 여전히 더 좋습니다.

(한 번에 나는 이것을 정말로 알고 있다고 생각하지만, 이제는 기억/추측하려고 노력하고 있으므로이 권위로 받아들이지 마십시오.)

고려하다 이 우화 이야기했습니다 데이비드 문, 발명자 LISP 기계:

어느 날 학생이 달에 와서 말했다.

Moon은 참을성있게 학생에게 다음과 같은 이야기를했습니다.

"어느 날 학생이 달에 와서 말했습니다. '나는 더 나은 쓰레기 수집가를 만드는 방법을 이해합니다 ...

맞아요?

좀 빠지는. 상호 재고 값을 동시에 정의하여 순수한 기능 프로그래밍을 사용하여 순수한 데이터 구조를 만들 수 있습니다. 예를 들어 OCAML에서 :

let rec xs = 0::ys and ys = 1::xs

그러나 설계별로 순환 구조를 만들 수없는 언어를 정의 할 수 있습니다. 결과는 a로 알려져 있습니다 단방향 힙 그리고 주요 장점은 쓰레기 수집이 기준 계수만큼 간단 할 수 있다는 것입니다.

그렇다면 왜 그렇지 않습니까?

일부 언어는주기를 금지하고 참조 계산을 사용합니다. Erlang과 Mathematica가 그 예입니다.

예를 들어, Mathematica에서 값을 참조 할 때 값을 깊이 사본을 만들므로 원본을 돌리면 사본이 변모하지 않습니다.

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}

CPU에 좋지 않기 때문에 기준 계수는 GC보다 훨씬 느립니다. 그리고 GC는 대부분 유휴 시간을 기다릴 수 있으며 GC는 동시 (다른 스레드에서) 일 수 있습니다. 이것이 바로 문제입니다. GC는 최소한의 악이며 많은 시도가 그것을 보여줍니다.

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