마지막 귀속 및 Continuation

 

귀착과 미귀착

귀속 조작에 관해서는 모두가 이미 낯설지 않을 것이라고 믿는다.간단하게 말하면 하나의 함수가 직접 또는 간접적으로 자신을 호출하는 것은 직접 또는 간접적으로 귀속되기 위한 것이다.예를 들어, 반복을 사용하여 단일 방향 체인 테이블의 길이를 계산할 수 있습니다.

public class Node
{
    public Node(int value, Node next)
    {
        this.Value = value;
        this.Next = next;
    }

    public int Value { get; private set; }

    public Node Next { get; private set; }
}

반복 GetLength 메서드를 작성합니다.

public static int GetLengthRecursively(Node head)
{
    if (head == null) return 0;
    return GetLengthRecursively(head.Next) + 1;
}

호출할 때 GetLengthRecursively 방법은 귀속 출구를 만족시킬 때까지 끊임없이 자신을 호출합니다.귀환에 대해 잘 아는 친구들은 한 항목의 체인 시계가 매우 길면 위의 이 방법은 창고가 넘쳐흐르는 것을 만날 수 있다. 즉, Stack Overflow Exception을 던지는 것이다.이것은 모든 스레드가 코드를 실행할 때 일정한 사이즈의 창고 공간(Windows 시스템에서 1M)을 분배하고 매번 방법이 호출될 때마다 창고에 일정한 정보(예를 들어 매개 변수, 국부 변수, 되돌아오는 주소 등)를 저장하기 때문이다. 이런 정보는 아무리 적더라도 일정한 공간을 차지하기 때문에 수천 수만 개의 이런 공간이 누적되면 자연히 스레드의 창고 공간을 초과할 것이다.그러나 이 문제는 결코 풀리지 않는 것이 아니다. 우리는 귀속을 다음과 같은 형식으로 바꾸면 된다. (이 글에서 우리는 비귀속의 해법을 고려하지 않는다).

public static int GetLengthTailRecursively(Node head, int acc)
{
    if (head == null) return acc;
    return GetLengthTailRecursively(head.Next, acc + 1);
}

GetLengthTailRecursively 방법은 acc 매개 변수가 하나 더 있는데 acc는 accumulator(누적기)의 줄임말로 그 기능은 귀속 호출할 때'축적'하기 전에 호출한 결과로 다음 귀속 호출에 전송된다. 이것이 바로 GetLengthTailRecursively 방법과GetLengthRecursively 방법은 귀속 방식에 비해 가장 큰 차이가 있다. GetLengthRecursive 방법은 귀속 호출 후에'+1'을 한 번 더 해야 한다.GetLengthTailRecursively의 귀속 호출은 방법의 마지막 작업에 속한다.이것이 바로 이른바'꼬리 귀속'이다.일반적인 귀속에 비해 꼬리귀속의 호출은 방법의 마지막에 있기 때문에 방법 이전에 축적된 각종 상태는 귀속 호출 결과에 아무런 의미가 없기 때문에 이번 방법에서 창고에 남겨진 데이터를 완전히 제거하고 마지막 귀속 호출에 공간을 줄 수 있다.이러한 최적화 1은 컴파일러가 호출 창고에 쌓이지 않게 하고 즉각적으로'무한'컴파일러가 창고를 넘치지 않도록 한다.이것이 바로 뒤따르는 우세다.
일부 친구들은 꼬리 귀속의 본질은 귀속 방법에 필요한'모든 상태'를 방법의 매개 변수를 통해 다음 호출에 전달하는 것이라고 생각했을 것이다.GetLengthTailRecursively 메서드의 경우 호출할 때 acc 매개 변수의 초기 값을 입력해야 합니다.

GetLengthTailRecursively(head, 0)

미귀착의 사용 방식을 더욱 익히기 위해서 우리는 유명한'피포나집'수열을 하나의 예로 삼았다.전통적인 귀속 방식은 다음과 같다.

public static int FibonacciRecursively(int n)
{
    if (n < 2) return n;
    return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
}

끝 귀환으로 바꾸려면 두 개의 누적기를 제공해야 한다.

public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
    if (n == 0) return acc1;
    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}

따라서 호출할 때 두 개의 누적기의 초기 값을 제공해야 한다.

FibonacciTailRecursively(10, 0, 1)

마지막 귀속 및 Continuation

Continuation, 즉'어떤 일을 완성한 후에'더 해야 할 일'을 위한 것이다.예를 들어,.NET에서 표준적인 APM 호출 방식은 바로 BeginXXX 방법과 EndXX 방법으로 구성되어 있는데 이것은 사실은Continuation의 일종이다. BeginXXX 방법을 완성한 후에 EndXX 방법을 호출해야 한다.이런 방법은 미귀속 구조에도 나타난다.예를 들어 다음과 같은 레벨업 방법의 기존 반복 정의가 있습니다.

public static int FactorialRecursively(int n)
{
    if (n == 0) return 1;
    return FactorialRecursively(n - 1) * n;
}

분명히 이것은 꼬리 귀속 방식이 아니다. 물론 우리는 그것을 이전에 언급한 꼬리 귀속 호출 방식으로 쉽게 전환할 수 있다.그러나 우리는 지금 그것을 이렇게 이해한다. 매번 n의 곱셈을 계산할 때 사실은'n-1의 곱셈을 먼저 얻는다'는 다음에'n과 곱하고 돌아간다'는 것이다. 그래서 우리의Factorial Recursively 방법은 다음과 같이 바꿀 수 있다.

public static int FactorialRecursively(int n)
{
    return FactorialContinuation(n - 1, r => n * r);
}

// 6. FactorialContinuation(n, x => x)
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
    ...
}

Factorial Continuation 방법의 의미는'n의 곱셈을 계산하고 결과를 continuation 방법으로 전송하여 호출 결과를 되돌려준다'는 것이다.따라서 Factorial Continuation 메서드 자체가 반복 호출임을 쉽게 알 수 있습니다.

public static int FactorialContinuation(int n, Func<int, int> continuation)
{
    return FactorialContinuation(n - 1,
        r => continuation(n * r));
}

Factorial Continuation 방법의 실현은 다음과 같이 설명할 수 있다.'n의 곱셈을 계산하고 결과를 continuation 방법에 전송하여 되돌려준다'. 즉,'n-1의 곱셈을 계산하고 결과를 n과 곱한 다음continuation 방법을 호출한다'.'결과를 n과 곱하기 위해continuation 방법을 다시 호출합니다' 라는 논리를 실현하기 위해 코드는 또 하나의 익명 방법을 구성하여factorialContinuation 방법을 다시 전송합니다.물론 우리는 그것을 위해 귀속되는 수출 조건을 보충해야 한다.

public static int FactorialContinuation(int n, Func<int, int> continuation)
{
    if (n == 0) return continuation(1);
    return FactorialContinuation(n - 1,
        r => continuation(n * r));
}

Factorial Continuation은 후행 반복을 구현한 것이 분명합니다.n의 계승을 계산하려면 다음과 같이 Factorial Continuation 방법을 호출하여 "10의 계승을 계산하고 결과를 직접 되돌려줍니다"라고 표시해야 합니다.

FactorialContinuation(10, x => x)

다시 한 번 인상을 깊게 하면 여러분은 다음과 같은'피포나끈'수열 n항의 값을 계산하는 방법을 이해할 수 있습니까?

public static int FibonacciContinuation(int n, Func<int, int> continuation)
{
    if (n < 2) return continuation(n);
    return FibonacciContinuation(n - 1,
        r1 => FibonacciContinuation(n - 2,
            r2 => continuation(r1 + r2)));
}

함수 프로그래밍에서 이러한 호출 방식은 CPS(Continuation Passing Style)를 형성합니다.C#의 Lambda 표현식은 쉽게 익명 방법을 구성할 수 있기 때문에 우리는 C#에서 이러한 호출 방식을 실현할 수 있다.당신은 땀을 생각할 수도 있습니다. 이렇게 복잡하게 할 필요가 있습니까? 계산 곱하기와 '피보나 끈기' 수열은 단번에 꼬리 귀속 형식으로 바뀔 수 있지 않습니까?그런데 아래의 예를 보시겠어요?
두 갈래 트리에 대해 먼저 순서대로 반복(pre-order traversal)하는 것은 전형적인 반복 작업으로 다음과 같은 TreeNode 클래스가 있다고 가정합니다.

public class TreeNode
{
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        this.Value = value;
        this.Left = left;
        this.Right = right;
    }

    public int Value { get; private set; }

    public TreeNode Left { get; private set; }

    public TreeNode Right { get; private set; }
}

그래서 우리는 전통적인 순서를 두루 살펴보자.

public static void PreOrderTraversal(TreeNode root)
{
    if (root == null) return;

    Console.WriteLine(root.Value);
    PreOrderTraversal(root.Left);
    PreOrderTraversal(root.Right);
}

"일반"방식으로 그것을 꼬리 귀속 호출로 바꿀 수 있습니까?여기에 두 차례나 PreOrder Traversal이 호출되었는데, 이것은 반드시 한 번의 호출이 끝에 놓이지 않는다는 것을 의미한다.이제 Continuation 을 활용해야 합니다.

public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation)
{
    if (root == null)
    {
        continuation(null);
        return;
    }

    Console.WriteLine(root.Value);

    PreOrderTraversal(root.Left,
        left => PreOrderTraversal(root.Right,
            right => continuation(right)));
}

우리는 현재 매번 귀속 호출을 코드의 마지막 조작으로 하고 다음 조작을 Continuation으로 포장함으로써 꼬리 귀속을 실현하고 데이터의 퇴적을 피한다.이를 통해 알 수 있듯이 Continuation을 사용하는 것은 약간 괴이한 사용 방식이지만, 때로는 기교를 빼놓을 수 없다.

Continuation의 개선 사항

방금 전의 순서가 두루 실현된 것을 보십시오. 당신은 좀 이상한 점을 발견했습니까?

PreOrderTraversal(root.Left,
    left => PreOrderTraversal(root.Right,
        right => continuation(right)));

마지막 단계에 관해서, 우리는 두 번째 PreOrder Traversal에서 호출하는Continuation으로 익명 함수를 구성했지만, 그 내부에서continuation 파라미터를 직접 호출했다. 그러면 우리는 왜 그것을 두 번째 호출에 직접 전달하지 않았을까?다음과 같습니다.

PreOrderTraversal(root.Left,
    left => PreOrderTraversal(root.Right, continuation));

우리는 Continuation을 사용하여 마지막 귀속을 실현했는데, 사실은 창고에 분배되어야 할 정보를 위탁 관리 더미에 잃어버렸다.모든 익명 방법은 위탁 관리 더미의 대상이다. 이런 생존 주기가 짧은 대상은 메모리 자원에 큰 문제가 되지 않는다고 하지만 가능한 한 이런 대상을 줄이는 것이 성능에 도움이 될 것이다.여기서 더 뚜렷한 예를 하나 더 들어 두 갈래 나무의 크기를 구한다(Size).

public static int GetSize(TreeNode root, Func<int, int> continuation)
{
    if (root == null) return continuation(0);
    return GetSize(root.Left,
        leftSize => GetSize(root.Right,
            rightSize => continuation(leftSize + rightSize + 1)));
}

GetSize 방법은 Continuation을 사용합니다. "루트의 크기를 가져와 continuation에 결과를 보내고 호출 결과를 되돌려줍니다."이를 다시 작성하여 Continuation 방법의 구조 횟수를 줄일 수 있습니다.

public static int GetSize2(TreeNode root, int acc, Func<int, int> continuation)
{
    if (root == null) return continuation(acc);
    return GetSize2(root.Left, acc,
        accLeftSize => GetSize2(root.Right, accLeftSize + 1, continuation));
}

GetSize2 방법은 누적기 파라미터가 많아졌고 이해 방식도 달라졌다. "루트의 크기를 acc에 누적한 다음 결과를 continuation에 전송하고 호출 결과를 되돌려줍니다."즉, GetSize2가 반환하는 값은 루트 매개변수의 실제 크기가 아니라 누적된 값입니다.물론 GetSize2를 호출할 때 누적기를 0으로 설정하면 됩니다.

GetSize2(root, 0, x => x)

잘 아시겠어요?

끝맺다

명령식 프로그래밍에서, 우리는 일부 문제를 해결할 때, 왕왕 순환을 사용하여 귀속을 대체할 수 있다. 이렇게 하면 데이터 규모로 인해 창고가 넘치지 않는다.그러나 함수식 프로그래밍에서'순환'을 실현하는 유일한 방법은'귀속'이기 때문에 꼬리귀속과 CPS는 함수식 프로그래밍에 대한 의미가 매우 크다.꼬리를 이해하는 것은 프로그래밍 사고에도 큰 도움이 되기 때문에 여러분은 이런 방식을 자신에게 사용하도록 사고와 연습을 많이 해도 무방합니다.