함수와 흐름제어

함수를 호출하면 함수의 본문에 지정된 특정 코드가 실행된다. 즉, 함수 호출로 원하는 코드를 실행시킬 수 있다. 흐름제어란 특정 상태에서 원하는 코드를 실행시키는 것이다. 흐름제어에서 원하는 코드를 함수로 지정할 수 있을 것이라는 아이디어를 얻을 수 있다.

예시

예시로 while을 함수로 구현해 보겠다. 예시에서 쓰일 언어는 Javascript이다.

function my_while(cond, body) {
    if (cond()) {
        body();
        return my_while(cond, body);
    }
}

let i = 0;
my_while((() => i < 10), () => {
    console.log(i);
    ++i;
});

my_while 함수는 조건 표현식과 실행될 본문 코드를 함수로써 인자로 받는다. 그다음에 cond 함수를 호출하고, 결과값이 참이면 body 함수를 실행한다. 그리고 재귀로 자기 자신을 호출하여 다음반복을 이어나간다.

my_while은 내부적으로 그냥 while을 써서 구현할 수도 있다. 하지만 뭔가 흥미로워 보이지 않을 것 같아서 tail call 재귀로 구현했다(Javascript가 표준으로 TCO(Tail Call Optimization)을 제공하는지는 모르겠다). 이런 것보다 중요한 것은, 내부가 어떻게 생겼든 함수를 통해 나만의 제어 구조를 정의했다는 사실이다.

고차함수는 커스텀 제어구조

함수를 인자로 받거나 반환하는 함수를 고차함수라고 한다. 이러한 고차함수 중에서 함수를 인자로 받아서 해당 함수를 호출하는 고차함수는 일종의 사용자 정의 제어구조(예를 들어 if, while, for)라고 볼 수 있다.

이러한 함수들중엔 대표적으로 iterator(또는 stream)에서 많이 쓰이는 map, filter, fold 함수 등이 있다.

이러한 특성을 적극적으로 활용하는 언어중에는 Koka가 있다. Koka는 마이크로소프트에서 만든 언어로, 미니멀하면서도 확장성있는 언어를 추구한다. Koka에는 while 문법이 없으며, while은 함수로 구현된다. 또한 인자없는 익명 함수 리터럴은 그저 코드를 { }로 감싸면 되기 때문에, Koka의 while 사용은 다음과 같다.

var i := 0
while { i < 10 } {
    println("hello")
    i := i + 1
}

위의 코드는 아래의 코드와 동일한 기능을 한다. 위의 코드가 동작하는 이유는 Koka가 "Trailing Lambdas"라는 문법을 지원하기 때문이다. 함수 호출 뒤에 익명 함수 리터럴이 따라오면 해당 리터럴을 함수에 넘기는 인자로 해석한다.

var i := 0
while({ i < 10 }, {
    println("hello")
    i := i + 1
})

1급 함수는 1급 코드

1급이라는 용어가 있다. 다음의 조건을 충족하는 것을 1급이라 부른다고 하는 것 같다.

• 함수에 인자로써 넘길 수 있다.
• 함수에서 반환될 수 있다.
• 변수에 할당할 수 있다.
• 동일 비교의 대상이 될 수 있다.

앞에서 고차 함수에 대해 설명했는데, 고차 함수를 위해서는 함수가 1급이여야 함을 알 수 있다. 1급 함수의 존재는 마치 코드가 1급인 것과 같은 느낌을 주어서, 코드를 함수에 인자로 넘기고, 함수에서 반환하고, 변수에 저장할 수 있는 듯한 느낌을 준다.

Curch Encoding

함수가 1급이라 함은, 함수가 숫자나 문자열과 다를 바 없는 값으로 취급된다는 의미이다. 그렇다면 숫자나 문자열이 정보를 담는것처럼, 오직 함수만을 사용해서 복잡한 데이터 구조를 표현하는 것도 가능할까? 이에대한 방법으로 church encoding이라는게 있다. 두개의 값을 가지는 pair(쌍)을 church encoding으로 어떻게 표현하는지 한번 살펴보자. 이를 위해서 3개의 함수를 구현할 것이다.

• cons 함수: construct의 줄임말로, 두개의 값을 인자로 받아 하나의 pair를 반환한다.
• first 함수: pair 하나를 인자로 받아 pair의 첫 번째 값을 반환한다.
• second 함수: pair 하나를 인자로 받아 pair의 두 번째 값을 반환한다.

세 함수는 Javascript로 다음과 같이 구현 가능하다.

function cons(a, b) {
    return k => k(a, b);
}
function first(pair) {
    return pair((a, b) => a);
}
function second(pair) {
    return pair((a, b) => b);
}

Continuation Passing Style

앞서 Church Encoding 챕터에서 봤던 first 함수는 pair 함수의 매개변수 k에 함수 (a, b) => a를 인자로 넘겨 호출한다. 이때 매개변수의 이름을 k라 지은 이유가 있다. pair 함수가 직접 값을 반환하는 대신, 값을 받아서 다음 처리를 할 함수 k를 인자로 받기 때문에 continuation passing style과 매우 유사하기 때문이다. k는 continuation의 약자이다. Church encoding으로 나타내는 다른 데이터 구조도 이러한 방식으로 나타내어진다. 즉, 소비자(continuation)을 받아서 소비자에게 값을 흘려보내는 형태인 것이다.

끝내며...

앞서 흐름제어란 특정 상태에서 원하는 코드를 실행시키는 것이라 했다. 또한 앞서 함수로 데이터를 표현할 수 있다고 했다. 그러면 함수라는 데이터에 따라 어떤 코드를 실행할지 결정하는 흐름제어를 할 수 있을 것이라고 생각할 수 있다. 참이면 A를 수행하고, 거짓이면 B를 수행하기 위한 boolean 데이터를 함수로 표현해보면 좋을 듯 하다. 도전해보고 싶으면 한번 해보기 바란다. 힌트는 first, second이다.