함수만으로 지연성까지

소개

제가 함수형 프로그래밍으로 개발한다고 말하면, 때때로 저에게 함수만으로 무엇을 할 수 있는지 물어보는 분들이 있습니다. 저는 그분들에게 무엇이든 할 수 있다고 답합니다. 하지만 이 말로는 부족할 때가 많습니다. 오늘은 그 질문에 대한 저만의 답변이 될 만한 이야기들을 간단하게 적어보려고 합니다.

자연수 만들기

함수만으로 우리는 자연수를 표현할 수 있습니다. 저는 처치 인코딩(Church numerals)을 이용하려고 합니다. 자세한 설명은 다음 링크를 참고해주시기 바랍니다. [1][5] 개발자는 코드로 말하므로 이론적인 설명은 치우고 곧바로 코드를 만들도록 하겠습니다.

숫자 0, 1, 2, 3 만들어 보겠습니다. 숫자의 크기는 함수f가 얼마나 감싸고 있느냐로 표현합니다. 언어는 자바스크립트를 사용합니다.[4]

1var zero = (f) => (x) => x;
2var one = (f) => (x) => f(x);
3var two = (f) => (x) => f(f(x));
4var three = (f) => (x) => f(f(f(x)));

다음 수, 더하기, 곱하기 함수를 만들어보겠습니다. (빼기, 나누기, 지수 등 추가적으로 관심이 있으시다면 [5]를 참고해주세요)

1// f를 1개 추가합니다.
2var SUCC = (n) => (f) => (x) => f(n(f)(x));
3// f를 n개 추가합니다.
4var PLUS = (m) => (n) => m(SUCC)(n);
5var MULT = (m) => (n) => m(PLUS(n))(zero);

하지만 람다표현식이 정말로 제대로 동작하는지 확인하기는 쉽지 않습니다. 모두 함수로 감싸져있기 때문입니다. 임의로 출력하는 함수는 만들어보았습니다. 함수로 문자를 표현하는 것은 생각하겠습니다.

1var printNumber = (f) => f((n) => n + '+1')('0');

실제로 출력을 해보겠습니다.

1console.log(printNumber(zero)); // 0
2console.log(printNumber(one)); // 0+1
3console.log(printNumber(two)); // 0+1+1
4console.log(printNumber(three)); // 0+1+1+1

계승, 더하기, 곱하기는 잘 작동하는지 보겠습니다.

1console.log(printNumber(SUCC(three))); // 0+1+1+1+1
2console.log(printNumber(MULT(two(one)))); // 0+1+1
3console.log(printNumber(MULT(two)(three))); // 0+1+1+1+1+1+1

함수로 만드는 자료구조

우리는 자료구조 중에 두 개의 요소를 저장할 수 있는 pair를 만들어 볼 것입니다. 이제부터 숫자는 자바스크립트 타입을 그대로 사용하겠습니다.

1var pair = (a) => (b) => (f) => f(a)(b);
2var first = (a) => (b) => a;
3var second = (a) => (b) => b;
4
5pair(1)(2)(first); // 1
6pair(1)(2)(second); // 2

이렇게 구현한 pair를 이용하여 우리는 N개의 요소를 나열하는 자료구조를 만들 수 있습니다.

1pair(1)(pair(2)(3))(first); // 1
2pair(1)(pair(2)(3))(second)(first); // 2

함수로 만드는 조건절

조건절을 만드려면 참과 거짓이 있어야합니다.

1var TRUE = (a) => (b) => a;
2var FALSE = (a) => (b) => b;

이 함수가 참과 거짓을 잘 나타내는지 확인해보기위해 AND, OR 를 만들어보겠습니다.

1var AND = (a) => (b) => a(b)(FALSE);
2var OR = (a) => (b) => a(TRUE)(b);

진리표에 부합하는 값이 나오는지 테스트해보겠습니다.

1AND(TRUE)(TRUE); // [Function: TRUE]
2AND(TRUE)(FALSE); // [Function: FALSE]
3AND(FALSE)(TRUE); // [Function: FALSE]
4AND(FALSE)(FALSE); // [Function: FALSE]
5
6OR(TRUE)(TRUE); // [Function: TRUE]
7OR(TRUE)(FALSE); // [Function: TRUE]
8OR(FALSE)(TRUE); // [Function: TRUE]
9OR(FALSE)(FALSE); // [Function: FALSE]

조건절은 아래처럼 만들 수 있습니다.

1var COND = (p) => (a) => (b) => p(a)(b);

TRUE, FALSE 가 잘 작동하는지 보겠습니다.

1COND(TRUE)(1)(2); // 1
2COND(FALSE)(1)(2); // 2

실제로 사용을 하려면 TRUE, FALSE 람다를 리턴하는 함수가 필요합니다. 위에서 생성한 숫자를 테스트하는 ISZERO 를 만들어 보겠습니다.

1var ISZERO = (f) => f((a) => FALSE)(TRUE);
2ISZERO(zero); // [Function: TRUE]
3ISZERO(one); // [Function: FALSE]

COND 에 대입하면 작동하는 것을 볼 수 있습니다.

1COND(ISZERO(zero))(10)(20); // 10
2COND(ISZERO(one))(10)(20); // 20

함수로 만드는 반복문

함수로 반복문을 만들 때는 재귀를 이용합니다. 하지만 만약 이름이 없는 익명함수(람다)인 경우는 어떻게 할 수 있을까요?

오로지 익명함수만으로 재귀를 호출할 수 있는 '와이콤비네이터'라는 것이 있습니다. 이것은 일전에 제가 블로그로 소개하는 것이 있으니 그것을 참고해주시면 감사하겠습니다. [2]

함수로 만드는 지연성

대부분의 프로그래밍 언어는 함수가 실행되기 전에 인자를 먼저 평가합니다. [3] 아래 코드에서 우리는 1 + 1 표현식의 평가를 지연시켜야 합니다.

1someFunction(1 + 1);

그러기 위해서 우리는 함수로 감싸서 평가를 지연시킬 것입니다.

1var delayedTwo = () => 1 + 1;

다시 실행하려면 인자가 없이 함수를 실행시키면 됩니다.

1delayedTwo();
22;

이제 우리는 아주 쉽게 평가가 지연된 배열을 만들 수 있습니다.

1// 가독성을 위해 인자 2개를 한번에 받도록 하였습니다.
2var l = pair(1)(() => 2);
3l(second)();

하지만 중간중간마다 () 을 이용하여 지연(delay)된 값을 강제로 평가해서 가져와야 합니다. 우리는 이것을 force라는 함수로 대신하도록 할 것입니다.

1var force = (a) => a();

이제 second의 경우 수행될 때마다 한번은 강제로 평가를 수행하는 force를 추가로 수행해야 합니다.

1var force = (a) => a();
2var secondForce = (a) => (b) => b(force);

이제 다음처럼 호출할 수 있습니다.

1l(secondForce);
22;

우리는 이제 특정 범위의 숫자를 지연된 리스트로 만들어낼 수 있습니다.

1var range = (start) => (end) => {
2  if (start > end) {
3    return null;
4  } else {
5    return pair(start)(() => range(start + 1)(end));
6  }
7};

테스트를 해보겠습니다.

1var a = range(1)(3);
2a(first); // 1
3a(secondForce)(first); // 2
4a(secondForce)(secondForce)(first); // 3

테스트하기 위해 좀 지연된 리스트를 모두 리턴하는 함수를 만들어 보겠습니다.

1var printAll = (list) => {
2  while (list != null) {
3    console.log(list(first));
4    list = list(secondForce);
5  }
6};
7
8printAll(range(1)(10));

무한으로 반복하는 repeat이라는 함수도 만들 수 있습니다.

1var repeat = (n) => pair(n)(() => repeat(n));
2
3var ones = repeat(1);
4ones(first); // 1
5ones(secondForce)(first); // 1
6ones(secondForce)(secondForce)(first); // 1
7// printAll() // 브라우저가 멈출 수 있습니다.

우린 방금 무한으로 만들어지는 자료구조를 생성하였습니다. 이제 take라는 함수를 이용해서 무한 자료구조에서 N개만을 가져올 수 있도록 해볼 것입니다.

1var take = (n) => (list) => {
2  if (n <= 0) return null;
3  return pair(list(first))(() => take(n - 1)(list(secondForce)));
4};
5
6printAll(take(100)(repeat(1))); // 1이 100번 출력됩니다.
7printAll(take(1)(range(1)(10000000000000000000000000000000000))); // 1

아래는 지금까지 소개한 코드를 모두 모아놓은 것입니다.

1var zero = (f) => (x) => x;
2var one = (f) => (x) => f(x);
3var two = (f) => (x) => f(f(x));
4var three = (f) => (x) => f(f(f(x)));
5
6var SUCC = (n) => (f) => (x) => f(n(f)(x));
7var PLUS = (m) => (n) => m(SUCC)(n);
8var MULT = (m) => (n) => m(PLUS(n))(zero);
9
10var printNumber = (f) => f((n) => n + '+1')('0');
11
12var pair = (a) => (b) => (f) => f(a)(b);
13var first = (a) => (b) => a;
14var second = (a) => (b) => b;
15
16var TRUE = (a) => (b) => a;
17var FALSE = (a) => (b) => b;
18
19var AND = (a) => (b) => a(b)(FALSE);
20var OR = (a) => (b) => a(TRUE)(b);
21
22var COND = (p) => (a) => (b) => p(a)(b);
23
24var ISZERO = (f) => f((a) => FALSE)(TRUE);
25
26var force = (a) => a();
27var secondForce = (a) => (b) => b(force);
28
29var range = (start) => (end) => {
30  if (start > end) {
31    return null;
32  } else {
33    return pair(start)(() => range(start + 1)(end));
34  }
35};
36
37var repeat = (n) => pair(n)(() => repeat(n));
38
39var take = (n) => (list) => {
40  if (n <= 0) return null;
41  return pair(list(first))(() => take(n - 1)(list(secondForce)));
42};
43
44var printAll = (list) => {
45  while (list != null) {
46    console.log(list(first));
47    list = list(secondForce);
48  }
49};

Clojure Macro로 Javascript의 한계를 넘어보기

이번장은 람다표현식에 대한 장이 아닙니다. 함수를 넘어서 매크로를 설명하는 번외편입니다.

우리는 지금까지 자바스크립트를 사용하여 함수의 강력함을 알아보았습니다. 자바스크립트의 함수는 가능한 모든 것을 만들기에 충분합니다. 하지만 저에게는 한 가지 아쉬운 점이 남아있습니다.

바로 지연하기 위한 코드를 함수로 만들 수 없다는 점입니다.

1var delay = (a) => () => a;

이 코드는 지연이 되는 것 같지만 우리가 원하는 대로 수행되지 않습니다.

1delay(console.log('지연되지 않는다'));

왜냐하면 delay 가 수행되기 전에 인자가 먼저 평가되기 때문입니다. [3] 우리는 아래처럼 직접 익명함수로 감싸줘야합니다.

1// 이렇게 말이지요
2() => console.log('지연되었습니다.');

하지만 지연성이 필요할 때마다 () => 를 직접 넣고 싶지는 않습니다. 저는 코드가 좀 더 가독성 있고 자연스러웠으면 좋겠습니다. 저는 이름을 붙이고 싶습니다.

우리는 자바스크립트로 이것을 해결하기 위해 eval, new Function을 이용한다면 코드를 문자열로 변경해야 할 것입니다. 혹은 바벨이나 직접 트랜스파일링을 할 수도 있겠죠. 그렇다면 일이 엄청나게 커질 것입니다.

하지만 이번에는 그린랩스에서 사용하는 Clojure코드를 이용하여 delay가 얼마나 쉽게 생성되는지 소개하겠습니다. 우리는 delay라는 매크로를 사용하여 아래 코드를 지연시킬 것입니다.

1(delay (println "지연이 되어야 합니다."))

생성된 코드는 다음과 같습니다.

1(defmacro delay [expr]
2  `(fn [] ~expr))
3
4(def delayed-print (delay (println "지연되어야 합니다."))) ;; 이곳에서는 아무것도 출력되지 않습니다.
5(delayed-print)  ;; "지연되어야 합니다." 가 출력됩니다.