Erlangs의 재귀 함수는 단지 goto가 아닌가?

Question

내 머리에 똑바로 닿기 위해. 이 예제 Erlang 코드의 비트를 고려하십시오.

 test() ->
      receive
          {From, whatever} ->
                %% do something
               test();
          {From, somethingelse} ->
               %% do something else
               test();
 end.

test () 호출이 아니에요, 그냥 goto?

C에서는 기능 호출을 수행하면 리턴 위치가 항상 스택에 올려 있기 때문에 이것을 묻습니다. 나는 이것이 Erlang의 경우에 해당 될 것이라고 생각할 수 없다.

기본적으로. 우리는 goto와 gosub의 두 가지 다른 호출 방식을 가졌습니다. Goto는 방금 프로그램 흐름을 다른 곳으로 조종했으며 Gosub는 당신이 어디에서 왔는지 기억하여 돌아올 수있었습니다.

이런 사고 방식을 감안할 때, 나는 다음과 같이 읽으면 Erlang의 재귀를 더 쉽게 볼 수 있습니다 : test ()를 goto로 읽으면 전혀 문제가 없습니다.

따라서 내 질문 : Erlang은 스택의 리턴 주소를 기억하는 대신 GOTO를 사용하지 않습니까?

편집하다:

내 요점을 명확히하기 위해 :

나는 Goto 's가 어떤 언어로 사용될 수 있다는 것을 알고 있습니다. 그러나 몇 가지를 수행하는 대신 SuuPose 만 수행 할 수 있습니다. GOTO SomeFunction () 첫 번째 예제에서 흐름이 리턴되는 경우, 두 번째 예제에서는 흐름이 약간의 기능에서 계속되며 다시는 돌아 오지 않습니다.

따라서 우리는 메서드 시작점으로 점프 할 수있어 정상적인 goto 동작을 제한합니다.

이렇게 보면 Erlang 재귀 함수 호출이 Goto처럼 보입니다.

(내 의견으로는 goto는 당신이 온 곳으로 돌아올 수있는 기능이없는 기능 호출입니다). Erlang 예에서 일어나는 일입니다.

Answer 1

꼬리 재귀 호출은 수행 된 하우스 키핑으로 인해 GOTO보다 "반환 및 즉시 다른 기능을 호출"에 가깝습니다.

최신 포인트 해결 : 리턴 포인트를 녹음하는 것은 함수가 호출 될 때 수행되는 약간의 하우스 키핑 일뿐입니다. 리턴 포인트는 스택 프레임에 저장되며 나머지는 로컬 변수 및 매개 변수를 포함하여 정상 호출로 할당 및 초기화해야합니다. 꼬리 재귀를 사용하면 새 프레임을 할당 할 필요가 없으며 리턴 포인트를 저장할 필요가 없지만 (이전 값은 잘 작동합니다) 나머지 하우스 키핑을 수행해야합니다.

기능이 반환 될 때 수행 해야하는 하우스 키핑도 있습니다. 여기에는 로컬 주민과 매개 변수를 버리고 (스택 프레임의 일부로) 호출 지점으로 돌아갑니다. 꼬리 재귀 호출 중에, 현재 함수의 현지인들은 새 기능을 호출하기 전에 폐기되지만 반환은 발생하지 않습니다.

스레드가 프로세스보다 가벼운 체중 컨텍스트 전환을 허용하는 방식과 마찬가지로, 꼬리 통화는 일부 하우스 키핑을 건너 뛸 수 있기 때문에 가벼운 체중 기능 호출을 허용합니다.

"goto &NAME"Perl의 진술은 당신이 생각하는 것에 더 가깝지만, 현지인들을 폐기 할 때, 매개 변수는 새로 호출 된 기능에 대해 주위에 보관됩니다.

한 가지 더 간단한 차이 : 테일 콜은 기능 입력 지점으로 만 점프 할 수있는 반면, GOTO는 대부분의 곳에서 점프 할 수 있습니다 (일부 언어는 GOTO가 함수 밖으로 점프 할 수없는 C와 같은 GOTO의 대상을 제한합니다).

Answer 2

당신이 맞습니다. Erlang 컴파일러는 그것이 재귀적인 호출임을 감지하고 스택에서 계속 이동하는 대신 현재 기능의 스택 공간을 재사용합니다.

또한 원형 꼬리 추방을 감지 할 수 있습니다.

test() -> ..., test2().
test2() -> ..., test3().
test3() -> ..., test().

또한 최적화됩니다.

이것의 "불행한"부작용은 기능 호출을 추적 할 때 테일 재귀 함수의 각 호출을 볼 수 없지만 입력 및 종료 지점을 볼 수 있다는 것입니다.

Answer 3

여기에는 두 가지 질문이 있습니다.

첫째, 아니요,이 경우 테스트 ()에 대한 호출이 둘 다이기 때문에이 경우 스택을 초과 할 위험이 없습니다. 꼬리 재주문.

둘째, 아니요, 기능 호출은 goto가 아니며 함수 호출입니다. :) 문제를 해결하는 것은 코드의 모든 구조를 우회한다는 것입니다. 진술을 벗어나 진술로 뛰어 들고, 우회 할 과제 ... 모든 종류의 나사성. 기능 호출은 명백한 제어 흐름이 있기 때문에이 문제가 없습니다.

Answer 4

여기의 차이점은 "진짜"고토와 어떤 경우에는 goto처럼 보일 수있는 것 사이의 차이점이라고 생각합니다. 일부 특수한 경우 컴파일러는 다른 함수를 호출하기 전에 현재 기능의 스택을 자유롭게 정리할 수 있음을 감지 할 수 있습니다. 전화가 함수의 마지막 호출 일 때입니다. 차이점은 물론 다른 전화에서와 같이 인수를 새로운 기능에 전달할 수 있다는 것입니다.

다른 사람들이 지적 했듯이이 최적화는 재귀적인 전화로 제한되지 않고 모든 마지막 통화에만 국한됩니다. 이것은 FSM을 프로그래밍하는 "클래식"방식에 사용됩니다.

Answer 5

그것은 a입니다 goto 그 이유와 마찬가지로 if ~이다 goto 그리고 while ~이다 goto. (도덕적 동등한)를 사용하여 구현됩니다. goto, 그러나 그것은 전체 촬영-피트-피트 잠재력을 노출시키지 않습니다. goto 프로그래머에게 직접.

Answer 6

실제로, 이러한 재귀 함수는 다음과 같습니다 궁극적 인 Goto 가이 스틸에 따르면.

Answer 7

다음은 더 일반적인 대답입니다. 이전 답변이 수락되었으므로 텍스트를 대체하지 않을 것입니다.

프롤로그

일부 아키텍처에는 "호출"이라고하는 "기능"이라고 부르는 것이 없지만 유사한 것이 있습니다 (메시징은 "메소드"또는 "메시지 처리자"라고 부를 수 있습니다. 이벤트 기반 아키텍처에는 "이벤트 처리기"또는 간단히 "처리기"가 있습니다. ). 그러나 일반적인 경우 (엄격히 말하면) "코드 블록"에는 "코드 블록"이라는 용어를 사용하지 않는 것들이 포함될 수 있습니다. 몇 곳에서와 마찬가지로 "호출"또는 "호출"에 대한 적절하게 입원 된 "호출"을 대체 할 수 있습니다. "연속 통과 스타일"(CPS)에서와 같이 호출을 설명하는 아키텍처의 특징은 때때로 "스타일"이라고 불리지만 이전에는 공식 용어는 아닙니다. 상황이 너무 추상적이지 않도록하기 위해 콜 스택, 연속 통과, 메시징 (OOP) 및 이벤트 처리 호출 스타일을 검사합니다. 이 스타일에 사용하는 모델을 지정해야하지만 공간에 관심을 가지고 남겨두고 있습니다.

호출 기능

또는 C는 계속, 조정 및 맥락을위한 것입니다.

Hohpe 콜 스택 스타일의 세 가지 잘 알려진 호출 기능 : 연속, 조정, 컨텍스트 (단어의 다른 용도와 구별하기 위해 자본화)를 식별합니다.

• 계속하면 코드 블록이 완료되면 실행이 계속 될 위치가 결정됩니다. "연속"기능은 관련이 있습니다.일류 연속"(나에 의한 단순히 단순히"연속화 "라고 불림), 연속이 계속된다는 점에서 계속해서 기능을 프로그래밍 방식으로 볼 수있게한다.
• 조정은 필요한 데이터가 준비 될 때까지 코드가 실행되지 않음을 의미합니다. 단일 통화 스택 내에서 호출 된 함수가 완료 될 때까지 프로그램 카운터가 함수로 돌아 가지 않기 때문에 무료로 조정을받습니다. 조정은 (예 :) 동시 및 이벤트 중심 프로그래밍에서 문제가됩니다. 전자는 데이터 생산자가 데이터 소비자보다 뒤쳐 질 수 있고 후자는 핸들러가 이벤트를 시작하면 핸들러가 응답을 기다리지 않고 즉시 계속됩니다.
• 컨텍스트는 코드 블록에서 이름을 해결하는 데 사용되는 환경을 나타냅니다. 로컬 변수, 매개 변수 및 반환 값의 할당 및 초기화가 포함됩니다. 매개 변수 전달은 또한 전화 컨벤션 (alliteration을 유지); 일반적인 경우, 컨텍스트를 현지인, 하나는 매개 변수를 포괄하는 기능으로 나누고 다른 하나는 반환 값에 대해 나눌 수 있습니다. CPS의 경우 리턴 값은 매개 변수 전달로 덮여 있습니다.

세 가지 기능이 반드시 독립적 인 것은 아닙니다. 호출 스타일은 상호 관계를 결정합니다. 예를 들어, 조정은 콜 스택 스타일로 연속과 관련이 있습니다. 반품 값이 연속에 관여하기 때문에 연속과 컨텍스트는 일반적으로 연결됩니다.

Hohpe의 목록이 반드시 철저하지는 않지만 꼬리 집을 Gotos와 구별하는 것으로 충분합니다. 경고 : Hohpe의 특징을 기반으로 한 호출 공간을 탐색하는 것과 같은 탄젠트를 떠날 수도 있지만 나 자신을 포함 시키려고 노력할 것입니다.

호출 기능 작업

각 호출 기능에는 코드 블록을 호출 할 때 완료해야 할 작업이 포함됩니다. 연속적으로, 호출 된 코드 블록은 자연스럽게 호출 코드와 관련이 있습니다. 코드 블록이 호출되면 체인 끝에있는 호출 코드에 참조 ( "호출 참조")를 배치하여 현재 호출 체인 (또는 "Call Chain")이 확장됩니다 (이 프로세스는 아래에서 더 구체적으로 설명되어 있음). . 호출을 고려하면 코드 블록 및 매개 변수에 이름을 바인딩하는 것이 포함되며, 우리는 비 결론 및 훈련 언어조차도 같은 재미를 가질 수 있습니다.

꼬리 통화

또는 대답

또는 나머지는 기본적으로 불필요합니다

꼬리 호출은 계속해서 연속화를 최적화하는 것이며, 주요 연속 작업 (호출 참조 기록)을 건너 뛸 수있는시기를 인식하는 문제입니다. 다른 기능 작업은 스스로 서 있습니다. "GOTO"는 연속 및 컨텍스트를위한 작업을 최적화하는 것을 나타냅니다. 그것이 테일 콜이 간단한 "goto"가 아닌 이유입니다. 다음은 다양한 호출 스타일에서 어떤 꼬리 통화가 어떻게 생겼는지 살펴볼 것입니다.

특정 호출 스타일의 꼬리 호출

다른 스타일은 다른 구조물로 호출 체인을 배열하며, 더 나은 단어가 없기 때문에 "엉킴"이라고 부릅니다. 스파게티 코드에서 벗어난 것이 좋지 않습니까?

• 콜 스택을 사용하면 엉킴에 하나의 호출 체인 만 있습니다. 체인을 확장한다는 것은 프로그램 카운터를 푸시하는 것을 의미합니다. 꼬리 통화는 프로그램 카운터 푸시가 없음을 의미합니다.
• CPS 하에서, 엉킴은 현존하는 연속으로 구성되며 뒤집다 수목 (모든 모서리가 중앙 노드쪽으로 가리키는 지시 된 트리), 여기서 중앙으로의 각 경로는 호출 체인입니다 (참고 : 프로그램 진입 지점이 "널"연속으로 통과되면 엉킴이 전체 숲이 될 수 있습니다. 수목). 하나의 특정 체인은 기본값이며, 이곳은 호출 중에 호출 참조가 추가되는 곳입니다. 꼬리 통화는 기본 호출 체인에 대한 호출 참조를 추가하지 않습니다. 여기서 "호출 체인"은 기본적으로 "일류 연속"의 의미에서 "연속"과 동의어입니다.
• 메시지 통과하에, 호출 체인은 차단 된 방법의 체인이며, 각각 체인에서 메소드의 응답을 기다리고 있습니다. 다른 사람을 호출하는 방법은 "클라이언트"입니다. 호출 된 방법은 "공급 업체"입니다 ( "서비스"는 의도적으로 "공급 업체"가별로 나지는 않습니다). 메시징 엉킴은 연결되지 않은 호출 체인 세트입니다. 이 엉킴 구조는 오히려 여러 스레드 또는 프로세스 스택을 갖는 것과 같습니다. 이 방법이 단순히 다른 방법의 응답 자체의 응답을 반영 할 때,이 방법은 클라이언트가 자신이 아닌 공급 업체를 기다릴 수 있습니다. 이는 조정과 연속을 최적화하는 것이 약간 더 일반적인 최적화를 제공합니다. 메소드의 최종 부분이 응답에 의존하지 않는 경우 (응답은 최종 부분에서 처리 된 데이터에 의존하지 않음), 클라이언트의 대기 시간 종속성을 공급 업체에 전달하면 메소드가 계속 될 수 있습니다. 이것은 메소드의 최종 부분이 스레드의 기본 함수가되고 콜 스택 스타일 테일 호출이되는 새 스레드를 시작하는 것과 유사합니다.

이벤트 처리 스타일은 어떻습니까?

이벤트 처리를 사용하면 호출에는 응답이 없으며 처리기가 기다리지 않으므로 "호출 체인"(위의 사용과 같이)은 유용한 개념이 아닙니다. 엉킴 대신, 당신은 채널이 소유 한 이벤트의 우선 순위 대기열과 리스너 핸들러 쌍의 목록 인 구독이 있습니다. 어떤 경우에는 구동 아키텍처가, 채널은 청취자의 속성입니다. 모든 청취자는 정확히 하나의 채널을 소유하므로 채널은 청취자와 동의어가됩니다. 호출은 채널에서 이벤트를 발사하는 것을 의미하며, 구독 된 모든 청취자 핸들러를 호출합니다. 매개 변수는 이벤트의 속성으로 전달됩니다. 다른 스타일의 응답에 의존하는 코드는 관련 이벤트와 함께 이벤트 처리에서 별도의 핸들러가됩니다. 테일 콜은 다른 채널에서 이벤트를 발사하고 나중에 다른 일을하는 핸들러입니다. 테일 콜 최적화는 두 번째 채널에서 첫 번째로 이벤트에 대한 리스크를 다시 구독하거나 두 번째 채널에서 첫 번째 채널에서 이벤트를 발사 한 핸들러가있을 수 있습니다 (컴파일러가 아닌 프로그래머가 만든 최적화 /통역사). 최적화되지 않은 버전으로 시작하여 이전 최적화의 모습은 다음과 같습니다.

1. 청취자 Alice는 BBC News에서 "취임"이벤트에 가입합니다.
2. 채널 BBC News에서 Alice Firees 이벤트 "선거"
3. Bob은 BBC 뉴스에서 "선거"를 듣고 있으므로 Bob의 "OpenPolls"핸들러가 호출됩니다.
4. Bob은 Channel CNN에서 "취임"이벤트를 구독합니다.
5. 채널 CNN에서 Bob Fires 이벤트 "투표"
6. 다른 이벤트는 해고 및 처리됩니다. 결국, 그들 중 하나 (예 : "Win")는 CNN의 "취임"이벤트를 화재합니다.
7. BBC News에서 Bob의 금지 처리기 "취임"
8. 앨리스의 취임식 처리기가 호출됩니다.

그리고 최적화 된 버전 :

1. 청취자 Alice는 BBC News에서 "취임"이벤트에 가입합니다.
2. 채널 BBC News에서 Alice Firees 이벤트 "선거"
3. Bob은 BBC 뉴스에서 "선거"를 듣고 있으므로 Bob의 "OpenPolls"핸들러가 호출됩니다.
4. Bob은 BBC News에서 "취임"을 듣고있는 사람에게 CNN*의 취임 행사에 대해 구독합니다.
5. 채널 CNN에서 Bob Fires 이벤트 "투표"
6. 다른 이벤트는 해고 및 처리됩니다. 결국, 그들 중 하나는 CNN에서 "취임"이벤트를 화재합니다.
7. Alice의 취임식 처리기는 CNN의 취임 행사를 위해 호출됩니다.

참고 테일 호출은 구독을 고려해야하기 때문에 이벤트 처리에서 더 까다 롭습니다 (참조 할 수 없는가?). Alice가 나중에 BBC News에서 "취임"에서 구독 취소 된 경우 CNN의 취임 구독도 취소해야합니다. 또한 시스템은 청취자를 위해 핸들러를 여러 번 부적절하게 호출하지 않도록해야합니다. 위의 최적화 된 예에서 BBC 뉴스에서 "취임"을 해고하는 CNN에 "취임"에 대한 다른 핸들러가있는 경우 어떻게해야합니까? 앨리스의 "파티"이벤트는 두 번 해고되어 직장에서 그녀를 곤경에 빠뜨릴 수 있습니다. 한 가지 해결책은 *Bob이 4 단계의 BBC 뉴스에서 "취임식"의 모든 청취자를 구독하지 않도록하는 것입니다. 그러나 Alice가 CNN을 통해 오지 않는 취임 이벤트를 놓치는 또 다른 버그를 소개합니다. 어쩌면 그녀는 미국과 영국 취임식을 모두 축하하기를 원할 것입니다. 이러한 문제는 모델에서 제가하지 않는 차이점, 아마도 구독 유형을 기반으로 할 수 있기 때문에 발생합니다. 예를 들어, 특별한 종류의 원샷 구독이있을 수 있습니다 ( System-V 신호 처리기) 또는 일부 취급자는 스스로 구독을 취소하고 Tail Call 최적화는 이러한 경우에만 적용됩니다.

무엇 향후 계획?

계속해서 호출 기능 작업을보다 완전히 지정할 수 있습니다. 거기에서 어떤 최적화가 가능한지, 언제 사용할 수 있는지 알아낼 수 있습니다. 아마도 다른 호출 기능이 식별 될 수 있습니다. 호출 스타일의 더 많은 예를 생각할 수도 있습니다. 호출 기능 간의 종속성을 탐색 할 수도 있습니다. 예를 들어, 동기 및 비동기 호출에는 명시 적으로 커플 링 또는 커플 링 연속 및 조정이 포함됩니다. 결코 끝나지 않습니다.

그 모든 것을 얻습니까? 나는 아직도 그것을 직접 소화하려고 노력하고있다.

참조 :

1. Hohpe, Gregor; "이벤트 중심의 아키텍처"
2. Sugalski, Dan; "CPS 및 Tail Calls- 함께 맛이 좋은 맛이 좋은 맛"

Answer 8

이 경우 더 많은 작업을 수행하거나 로컬 변수를 사용할 필요가 없기 때문에 꼬리 통화 최적화를 수행 할 수 있습니다. 따라서 컴파일러는 이것을 루프로 변환합니다.

Answer 9

(내 의견으로는 goto는 당신이 온 곳으로 돌아올 수있는 기능이없는 기능 호출입니다). Erlang 예에서 일어나는 일입니다.

그것은 Erlang에서 일어나는 일이 아닙니다. 당신은 당신이 온 곳으로 돌아갈 수 있습니다.

통화는 꼬리 추방 적이며, 이는 "일종의"a goto임을 의미합니다. 코드를 이해하거나 작성하려고 시도하기 전에 Tail Recursion이 무엇인지 이해해야합니다. Joe Armstrong의 책을 읽는 것은 아마도 Erlang을 처음 접한다면 나쁜 생각이 아닙니다.

개념적으로, test ()를 사용하여 자신을 호출하는 경우 전달한 매개 변수를 사용하여 (이 예에서는 없음) 기능의 시작을 호출하지만 더 이상 스택에 추가되지 않습니다. 따라서 모든 변수가 버려지고 기능이 새로 시작되지만 새 리턴 포인터를 스택으로 밀지 않았습니다. 따라서 C 또는 Java에서와 마찬가지로 Goto와 전통적인 필수 언어 스타일 기능 호출 사이의 하이브리드와 같습니다. 그러나 호출 함수의 첫 번째 호출에서 스택에 여전히 하나의 항목이 있습니다. 따라서 다른 test ()를 수행하는 값을 반환하여 결국 종료하면 해당 리턴 위치가 스택에서 튀어 나와 호출 기능에서 실행이 재개됩니다.