Y Combinator

요즘은 전산 전공자조차도 와이 컴비네이터(Y Combinator)가 Paul Graham이 설립한 실리콘밸리 스타트업 인큐베이터라고만 아는 경우가 많은 것 같습니다. 하지만 Y Combinator는 전산학에서 아주 중요한 개념입니다. 함수 언어, 특히 Lisp의 예찬론자인 Paul Graham도 여기서 회사 이름을 따왔습니다.

일단 combinator란 말은 Moses Schönfinkel와 Haskell Curry가 만든 Combinatory logic에서 왔습니다. Combinatory logic은 lambda calculus와 마찬가지로 전산학에서는 계산을 모델링하는 방법으로 사용되는데, 몇 가지 함수의 조합만으로 새로운 함수를 만들어내는 방법을 뜻합니다. 여기서 combinator는 free variable이 없는 함수라고 생각하면 됩니다. Combinatory logic에서는 다음과 같이 3개의 가장 기본적인 combinator를 정의합니다.

  • I combinator
var I = function (x) {
            return x;
        };
  • K combinator
var K = function (x) {
        return function(){
            return x;}
        };
  • S combinator
var S = function (x) {
           return function (y) {
               return function (z) {
                   return x(z)(y(z));
               }
           }
       };

(모든 combinator는 curried function으로 표현하였습니다.)

여기서 I combinator는 인자 그대로 리턴하는 identity 함수이고, K combinator는 항상 첫 번째 인자를 리턴하는 const 함수입니다. S combinator만 조금 복잡한 계산을 수행하는 것처럼 보입니다. Combinatory logic의 놀라운 점은 S와 K 단 2개의 combinator의 조합만으로 Turing machine이 계산 가능한 모든 계산을 할 수 있다는 점입니다. (I combinator는 S, K로 만들어 낼 수 있습니다.)

Y combinator는 fixed point combinator라고 불리는데, 재귀 함수를 만들어주는 combinator입니다. JavaScript 같이 재귀 함수를 직접 지원하는 언어만 사용하신 분은 이 개념이 다소 생소할 수 있습니다. 예를 들어, JavaScript로 팩토리얼을 구하는 함수 fac을 작성하면 다음과 같습니다. fac 함수 내에서 fac(n-1)을 호출하는 것을 확인할 수 있습니다.

function fac(n) {
    if (n === 1)
        return 1;
    else
        return n * fac(n - 1);
}

console.log(fac(5));
// 120

하지만 익명 함수(anonymous function)으로만 이 함수를 작성해야 한다면 어떨까요? 함수 내에서 자기 자신을 부를 수 있는 방법이 없기 때문에 더 이상 재귀 함수를 만들 수가 없게 됩니다.

var fac = function (n) {
    if (n === 1)
        return 1;
    else
        return n * ??(n - 1);
}

여기서 등장하는 함수가 Y combinator입니다. Y combinator를 이용하면 다음과 같이 fac 함수를 정의할 수 있습니다.

var fac = Y(function (fac) {
    return function (n) {
        return n === 1 ? n : n * fac(n - 1);
    };
});

JavaScript로 Y combinator를 다음과 같이 정의할 수 있습니다.

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

물론 S, K combinator만으로 모든 계산 가능한 함수를 만들어낼 수 있기 때문에 Y combinator를 S, K로 표현할 수도 있습니다.

Y = S S K (S (K (S S (S (S S K)))) K)

이 글은 Y combinator의 개념만 간단히 소개하는 것으로 마치고, 다음 글에서 fixed point의 개념 및 Y combinator 유도 과정에 대해 살펴보겠습니다.

JavaScript 함수: 스코핑, 클로저

오늘은 JavaScript 함수의 두 가지 대표적인 특징인 스코핑 규칙과 클로저에 대해 설명합니다.

스코핑(scoping)

JavaScript는 정적 스코핑(static/lexical scoping)하는 언어입니다. 초기 Lisp을 제외하고 동적 스코핑(dynamic scoping)하는 언어는 거의 없기 때문에 “정적” 스코핑이란 말은 크게 의미가 없습니다. 다만, 다른 언어와 달리 블록 스코핑(blocking scoping)이 아닌 함수 스코핑(function scoping)이라는 점이 특이합니다.

예를 들어, 아래 foo() 함수 호출은 x의 값을 리턴하는데, x 값은 1이 아닌 2가 리턴됩니다. 블록 안에서 새로 변수 x를 선언하고 2를 할당했지만, 자바스크립트는 함수 스코핑이기 때문에 함수 foo()x 변수는 단 하나만 존재합니다. 따라서 var x=2는 새로운 변수를 선언이 아니라 단순히 x=2라는 할당문으로 취급됩니다.

function foo() {
    var x = 1;
    {
        var x = 2;
    }
    return x;
}

var x = foo();
console.log(x);
// 2

함수 스코핑이 블록 스코핑에 비해 가지는 장점은 없습니다. 의도한 설계라기 보다는 초기 프로그래밍 언어 설계 오류라고 보는 편이 맞습니다. 실제로 ES6에서는 이 문제를 바로 잡기 위해 let 키워드를 이용한 블록 스코핑을 새로 도입하였습니다. 아래 foo_() 함수는 var 키워드를 let으로 바꾸었을 뿐인데, 1이 리턴되는 것을 확인할 수 있습니다.

function foo_() {
    let x = 1;
    {
        let x = 2;
    }
    return x;
}

var x_ = foo_();
console.log(x_);
// 1

ES6는 이전 버전 JavaScript와 호환성 때문에 varlet 키워드를 모두 허용하지만, 새로 작성되는 코드는 모두 let으로 작성하는 것이 좋습니다.

클로저

JavaScript 함수는 1등 시민(first-class citizen)이기 때문에 string이나 number와 마찬가지로 함수의 인자로 넘기거나, 함수의 리턴값으로 돌려주거나, 변수에 저장하는 등의 일이 가능합니다. 따라서 함수 안에서 numberstring을 생성하고 사용할 수 있는 것처럼 함수 안에서 새로운 함수를 선언하고 사용하는 것도 가능합니다.

function makeAdder() {
    function add(a, b) {
        return a + b;
    }
    return add;
}

var adder = makeAdder();
console.log(adder(1, 2));
// 3

위의 makeAdder() 함수를 호출하면 새로운 함수 add()를 리턴하는데, 이 함수는 인자 a, b를 받아서 합을 리턴하는 함수입니다. 호출 결과를 변수 adder에 저장하면 adder(1,2)처럼 함수 호출도 가능함을 확인할 수 있습니다. 이 경우, 함수 add()makeAdder() 안에 선언되어 있기 때문에 함수 밖에서 접근할 수 없다는 점을 제외하면 최상단에 정의한 함수와 다를 바가 없습니다.

JavaScript는 여기서 한발 더 나아갑니다. 아래 makeAdder() 함수는 인자 a를 받아서 a를 더해주는 함수 addA를 리턴합니다. 여기서 aaddA()에 선언된 변수가 아니라 makeAdder()에 선언된 변수라는 점이 특별합니다. JavaScript 함수는 해당 함수에 참조하고자 하는 변수가 없으면 여기서 포기하지 않고 바깥 함수(enclosing function)들에 있는 변수를 찾는 것입니다.

function makeAdder(a) {
    function addA(b) {
        return a + b;
    }
    return addA;
}

var add1 = makeAdder(1);
console.log(add1(2));
// 3

따라서 makeAdder(1)이 리턴하는 함수는 인자 b를 받아서 1을 더해주는 함수가 됩니다. addA()에서 참조한 변수 amakeAdder() 함수가 리턴된 후에도 addA()에서 사용할 수 있기 때문에 가비지 콜렉션되지 않도록 JavaScript 런타임에 처리를 해줍니다.

우리는 보통 함수를 코드로만 생각합니다. 데이터는 함수 호출 시 인자로 넘기는 것이고 함수 자체는 순수한 코드라고 생각하는 경향이 있습니다. 하지만 위 예에서 볼 수 있듯이 JavaScript 함수는 단순히 코드가 아니라 코드+데이터입니다. addA() 함수는 덧셈을 하는 코드도 가지고 있지만, a의 값인 데이터도 가지고 있기 때문입니다. 이렇게 코드와 데이터를 모두 가지고 있는 함수를 클로저(closure)라고 부릅니다.

클로저가 강력한 이유는 “코드+데이터 = 프로그램”이기 때문입니다. 즉, 클로저만 있으면 모든 프로그램을 표현할 수 있다는 뜻입니다. 오브젝트도 마찬가지입니다. “오브젝트 = 코드+데이터”이고, “코드+데이터 = 클로저”이므로 “오브젝트 = 클로저”라는 공식이 성립합니다.

실제로 JavaScript에서는 클로저를 이용해 오브젝트를 만드는 일이 흔합니다. 클로저를 이용해 counter 오브젝트를 만들면 다음과 같습니다. (이 코드는 MDN 클로저 페이지에서 차용했습니다.) changeBy(), increment(), decrement(), value() 함수 모두 privateCounter 변수에 접근하는 클로저임을 확인할 수 있습니다.

var counter = (function() {
  var privateCounter = 0;
  function changeBy(val) {
    privateCounter += val;
  }
  return {
    increment: function() {
      changeBy(1);
    },
    decrement: function() {
      changeBy(-1);
    },
    value: function() {
      return privateCounter;
    }
  };
})();

변화 예측

유지보수하기 좋은 코드를 만들려면 변경 사항에 대해 어느 정도 예측이 가능해야 합니다. 물론 이해하기 쉬운 코드를 작성하면 상대적으로 어떤 변화든 쉽게 대응할 수 있는 것이 사실이지만, 모든 종류의 변경 사항에 유연하게 대처할 수 있는 코드를 미리 작성하는 건 사실상 불가능하고 또 시간 낭비일 수도 있기 때문입니다.

리팩토링에서 코드 스멜이라고 이야기하는 것 중에 하나가 타입 혹은 enum 값을 체크하는 조건문이 반복되는 것입니다. Replace Conditional with Polymorphism은 이런 코드를 리팩토링해서 각 타입을 서브클래스를 만들고 다형성으로 해결하라고 이야기합니다.

예를 들어, 다음 코드는 _type에 따라 getSpeed() 메소드의 행동이 달라집니다.

class Bird {
   ...
   double getSpeed() {
       switch (_type) {
           case EUROPEAN:
              return getBaseSpeed();
           case AFRICAN:
              return getBaseSpeed() - getLoadFactor() * _numberOfCoconuts;
           case NORWEGIAN_BLUE:
              return (_isNailed) ? 0 : getBaseSpeed(_voltage);
       }
       throw new RuntimeException ("Should be unreachable");
   }
}

객체지향 프로그래밍의 일반적인 조언은 Bird 클래스의 getSpeed() 메소드를 abstract로 만들고, EuropeanBird, AmericanBird, NorwegianBlueBird 클래스를 만들어서 각각 getSpeed() 메소드를 오버라이드하라는 겁니다.

이렇게 했을 때 뭐가 더 좋아질까요? 일단 각 Bird 고유의 코드는 해당 클래스에 캡슐화(encapsulation) 된다는 장점이 있습니다. AmericanBird의 속도를 계산 방법이 바뀌었을 때 다른 코드에 영향을 주지 않고 구현을 변경할 수 있습니다. 또핸 새로운 Bird 종류가 추가되었을 때도 기존 Bird 구현을 수정하지 않고 추가할 수 있다는 장점이 있습니다.

여기서 가정한 변화의 방향은 Bird의 추가 혹은 특정 Bird의 구현 변경입니다. 하지만 변화의 방향이 다르면 예상과 달랐다면 어떻게 될까요?

Bird가 추가되는 대신 각 Bird에 계속 새로운 속성 혹은 행동이 추가되어야 한다면? 더 이상 변경 사항이 하나의 Bird에 국한되지 않고 모든 Bird 클래스를 수정해야 하는 상황이 됩니다. 예를 들어, 전반적인 속도 계산 알고리즘이 변경되어 모든 BirdgetSpeed() 메소드에 수정이 필요하다면, 오히려 리팩토링 전의 코드가 더 캡슐화가 잘 된 코드입니다. getSpeed() 메소드 하나만 수정하면 해결할 수 있고, 각 Bird의 속도 구현을 한 눈에 파악할 수 있기 때문입니다. 따라서 무조건 다형성을 추구할 것이 아니라 처음 Bird 클래스를 설계할 때 어떤 변경 사항이 많을지 예측을 하고 적절한 방식으로 구조를 잡아야 합니다.

Bird 추가나 특정 Bird 알고리즘의 수정이 동전의 앞면, 메소드 추가나 전체 Bird 알고리즘 수정이 동전이 뒷면이라면 객체지향 프로그래밍은 동전의 앞면에 베팅을 하고 있습니다. 하지만 우리가 이미 동전이 뒷면이 나올 확률이 더 높다고 예측을 했다면 이 경우 객체지향 방법론을 무조건적으로 적용하는 건 정답이 아니게 됩니다.

함수 언어는 보통 반대 방향으로 베팅을 합니다. ADT(Algebraic Data Type)의 Sum Type과 패턴 매칭은 우리가 코드 스멜이라고 생각하는 타입에 따른 조건문 사용을 오히려 장려합니다. 객체지향 프로그래밍과 달리 동전의 뒷면에 베팅을 하기 때문입니다. 마찬가지로 우리가 동전의 앞면이 나올 확률이 더 높다는 사실을 알고 있으면, 함수 프로그래밍을 적용하는 건 정답이 아니게 됩니다.

한 언어가 두 마리 토끼를 모두 잡는 것은 쉽지 않습니다. Philip Wadler 교수가 Expression Problem으로 이름 붙인 문제도 “프로그래밍 언어가 이런 두 가지 변화의 방향에 다 대처할 수 있는가?”입니다. 멀티 메소드나 헤스켈의 타입 클래스(Type Class) 등이 해법으로 나왔지만, 두 가지 모두 우리가 일반적으로 사용하는 프로그래밍 언어에 존재하지 않는 기능이므로 우리는 여전히 변화의 방향을 예측하고 베팅을 해야만 합니다.

객체지향 프로그래밍 원리나 리팩토링을 가르칠 때 가장 어려운 것도 내용이 아니라 맥락에 있습니다. 생각 없이 따르기만 하면 되는 프로토콜은 존재하지 않기 때문입니다. 같은 조언이라도 득이 될 때가 있고 실이 될 때가 있고, 결국 상황에 따라 판단이 필요합니다. 맥락 없이 “switch나 if로 타입 체크하는 코드는 무조건 나빠”라고 이야기하는 사람이 있다면 왜 그런 판단을 내리는지 물어보고 그 이유가 정말로 합당한지 한 번 더 고민해 보시기 바랍니다.

“조언자의 딜레마”라는 말이 있습니다. 세상에 좋은 조언을 널렸지만, 결국 어떤 조언을 취사선택할지의 문제는 나에게 있기 때문입니다. 디자인 패턴, 클린 코드, 리팩토링 등을 아무리 읽고 적용해도 결국 스스로 판단 없이 기계적으로 적용해서는 좋은 결과를 얻기 어렵습니다. 더 중요한 건 스스로 생각하는 훈련입니다.변화 예측

컴퓨터공학과 나와도 코딩 ‘쩔쩔’

오늘 페이스북을 보니 컴퓨터공학과 나와도 코딩 ‘쩔쩔’ 기사에 대한 이야기가 많던데, 이 블로그 주제가 코딩 스쿨인 만큼 코딩 교육에 대한 이야기를 해볼까 합니다.

사실 기사 자체는 새로운 내용도 없습니다. 컴퓨터공학을 전공한 대학 졸업생들이 현업에 투입될 만큼 코딩 실력이 없고, 원인은 정부 정책이나 교육에 있다는 겁니다. 제가 놀란 것은 기사가 아니라 댓글의 반응입니다. 이 기사에 대한 주된 비판은 컴퓨터공학과는 단순 기능에 불과한 “코딩”이 아니라 알고리즘, 데이터 구조, 운영체제, 네트워크, 소프트웨어 엔지니어링 등 컴퓨터 과학과 이론을 습득하는 곳이기 때문에 컴퓨터공학과 졸업생이 6개월 정도 코딩만 배운 학원생들에 비해 코딩을 못할 수도 있다는 겁니다.

그럴 듯한 변명이지만 현실과는 다릅니다. 댓글에 따르면 컴퓨터공학과 졸업생들이 4년 내내 컴퓨터 이론을 습득하느라 너무 바쁜 나머지 코딩에 쓸 시간이 없었다는 이야기인데, 그렇다면 다소 코딩은 미숙해도 이론은 컴퓨터학원 출신과는 비교할 수 없는 수준으로 잘 알고 있어야 할 겁니다. 하지만 제가 지난 7년간 (상위권 대학) 컴퓨터공학과 학생들을 면접해 본 결과는 오히려 정반대입니다. 그나마 API 문서보고 앱이나 웹페이지 정도는 만들어 본 경험은 있어도, 컴퓨터 이론을 제대로 공부한 학생은 손에 꼽을 정도로 적었습니다. 일례로, 분명히 알고리즘 수업을 들었는데도, Big-O 표기법이 무슨 뜻인지, binary tree 검색 시에 time complexity가 얼마인지도 모르는 친구들이 적지 않습니다. OS의 가상 메모리가 어떻게 구현되고, 이게 C/C++의 malloc()new와 어떤 관계가 있는지 설명할 수 있는 학생은 손에 꼽을 정도로 적었습니다.

많이 양보해서 이론 공부하느라 코딩할 시간이 없었다는 게 사실이라고 쳐도 여전히 문제입니다. 컴퓨터공학은 이론과 실습의 균형이 중요합니다. 내가 이론으로 배운 것들이라고 해도, 실제로 만들어보지 않고서는 제대로 이해하기가 불가능하기 때문입니다. 알고리즘과 데이터 구조 수업을 들으면서 여러 알고리즘 실제로 구현해보고, 운영체제 수업을 들으면서 간단한 운영체제를 직접 만들어보고, 프로그래밍 언어나 컴파일러 수업을 들으면서 간단한 프로그래밍 언어를 직접 구현해 보지 않고서나 해당 과목을 이수했다고 말하기가 어렵습니다. 수업을 듣고 당장 한 학기만 지나도 아마 대부분의 내용이 기억에서 사라질 겁니다.

또한 대학이든 회사든 “코딩”을 단순 기능으로 생각해서 교육하지 않는 것이 문제입니다. 대학 졸업생은 물론이고 10년 이상된 개발자들 중에서도 코딩을 제대로 하는 사람이 별로 없는 이유는, 어떻게 하면 코딩을 잘하는지에 대해 고민하지 않을 뿐만 아니라 소프트웨어 아키텍처나 비지니스 로직, 머싱 러닝 알고리즘 등 그럴 듯한 말에 비해 상대적으로 저급한 일로 취급하기 때문입니다. 코딩을 글쓰기에 많이 비유하는데, 이런 상황은 “노인과 바다”와 같은 대작을 머리 속에 그리고 있는데 글쓰기 실력은 초딩 수준인거나 마찬가지입니다.

코딩 잘 못하는 소프트웨어 대가 같은 건 없습니다. 1년 이상 자기 손으로 코드 한 번 안 짜본 사람이 와서 소프트웨어 아키텍처나 프로세스에 대해 이야기하면 바로 무시하시기 바랍니다. 이론도 마찬가지입니다. 해당 분야에 특허를 내고 논문을 쓴다고 소프트웨어를 만들 줄 아는 게 아닙니다. 변수 이름 하나 수준에서 많은 고민을 하고 좋은 코드를 작성하기 위해 오랜 시간 고민하고 실제로 코드를 작성해야 대학에서 배운 이론이라는 것도 쓸모가 있습니다.

대학에서 이론 안 가르치고 코딩 가르친다고 문제 해결되는 것도 아니고, 지금처럼 컴퓨터공학과는 고급 지식을 배우는 곳이니 코딩 따위는 못할 수도 있다고 당당하게 이야기하는 것도 해결책이 아닙니다. 지금 컴퓨터공학과, 소프트웨어 엔지니어의 문제점은 그저 절대적인 학습량, 절대적인 코딩량이 낮은데 있습니다. 대학에서는 이론도 지금보다 더 많이 가르쳐야 하고, 실습 과제도 더 많이 내서 컴퓨터공학과 졸업하는 것 자체가 자부심이 될 정도로 기준을 높여야 합니다.

대학이 졸업생들의 실력을 보증하는 방법은 이미 의대에서 찾을 수 있습니다. 의대는 사람의 생명을 다루는 직업인 만큼 이론과 실습 모두 일정 수준 이상 도달하지 않으면 유급도 시키고, 의사자격증도 안 주는 방식으로 일종의 품질 보증을 하고 있습니다. 컴퓨터공학과처럼 취업 잘 되는 학과라고 사람 많이 뽑아서 졸업장 팔아 장사하는 모델이 되면 졸업생의 품질을 보증하지 못하는 건 어찌 보면 당연한 것 아닐까요?

JavaScript Reduce 함수

자바스크립트에서 고차함수(higher-order function)하면 항상 언급되는 함수가 forEach, map, reduce입니다. 그 외에도 every, some, filter와 같은 함수들도 자주 사용됩니다.

이들 고차 함수의 공통점은 함수의 인자로 함수를 받거나 함수를 리턴한다는 점입니다. filter를 예로 들면, 배열의 각 원소에 대해 callback 함수를 호출하여 true가 리턴되는 경우에만 해당 인자를 리턴 값의 배열에 포함시킵니다. 아래 예제 코드를 보면, isBigEnough 함수를 통과하는 값(10보다 크거나 같은 값)만 리턴 값에 포함되는 것을 확인할 수 있습니다.

function isBigEnough(value) {
  return value >= 10;
}
var filtered = [12, 5, 8, 130, 44].filter(isBigEnough);
// filtered is [12, 130, 44]

이런 고차함수는 아주 작은 수준의 코드 재활용으로 생각할 수 있습니다. 만약 filter라는 함수가 없었다면, 우리는 필터링 조건이 달라질 때마다 새로운 함수를 작성했을 것입니다. 예를 들어, 아래 posneg 두 함수는 배열을 인자로 받아 각각 0보다 큰 숫자, 0보다 작은 숫자만 리턴하는 함수입니다.

function pos(arr)
{
    var ret = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] > 0) {
            ret.push(arr[i]);
        }
    }
    return ret;
}

function neg(arr)
{
    var ret = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < 0) {
            ret.push(arr[i]);
        }
    }
    return ret;
}

var xs = [0, -1, 2, 3, -4, 5];
console.log(pos(xs));
console.log(neg(xs));

// [ 2, 3, 5 ]
// [ -1, -4 ]

위 두 함수는 if 문 안의 조건을 제외하고는 사실상 모든 코드가 동일합니다. 따라서 이 부분만 인자로 빼내면 filter와 유사한 범용적인 함수가 나오게 됩니다. 그리고 이렇게 일단 filter 함수가 생기면 pos, neg 함수는 filter 함수를 재활용해서 쉽게 작성할 수 있게 됩니다.

function myfilter(arr, predicate) {
    var ret = [];
    for (var i = 0; i < arr.length; i++) {
        if (predicate(arr[i])) {
            ret.push(arr[i]);
        }
    }
    return ret;
}

function pos(arr) {
    return myfilter(arr, function (x) { return x > 0; });
}

function neg(arr) {
    return myfilter(arr, function (x) { return x < 0; });
}

var xs = [0, -1, 2, 3, -4, 5];
console.log(pos(xs));
console.log(neg(xs));

재미있는 건 재활용이 여기서 그치지 않습니다. posneg 함수가 서로 동일한 구조를 공유하고 있었기 때문에 filter라는 함수를 뽑아낼 수 있었던 것처럼 filter를 포함한 다른 고차함수들도 비슷한 구조를 공유하고 있기 때문에 공통점을 다시 뽑아낼 수 있습니다.

여기서 등장하는 함수가 reduce 함수입니다. reduce는 맥가이버칼처럼 여러 고차함수를 만들어낼 수 있는 표현력을 가지고 있습니다. reduce 함수는 배열의 각 원소를 돌면서 콜백 함수를 반복적으로 적용하여 하나 값을 뽑아내는 함수입니다. 아래 예제는, 배열을 돌면서 각 원소 값의 총합을 리턴하는 코드입니다.

function add(acc, value) {
  return acc + value;
}
[1, 2, 3, 4, 5].reduce(add, 0);

이 코드의 실행 결과는 add(add(add(add(add(0, 1), 2), 3), 4), 5)와 같습니다. reduce의 두 번째 인자가 acc의 초기값이 되고, 이후 각 원소를 덧셈한 결과가 계속 acc에 누적되어 넘어가는 방식입니다. 이 과정을 그림으로 표현하면 다음과 같습니다. 참고로 JavaScript의 reduce 함수는 사실 함수 프로그래밍에서는 foldl이라는 함수명으로 더 잘 알려져 있습니다.

얼핏 보기에 reduce 함수와 filter 함수는 크게 공통점이 없어 보입니다. filter 함수는 배열을 받아서 다른 배열을 리턴하는데, reduce 함수는 배열을 받아서 원소를 리턴하는 것처럼 보이기 때문입니다. 하지만 reduce 함수를 이용해 다음과 같이 filter 함수를 구현할 수 있습니다. acc에 빈 배열 []을 넘기고 predicate(x)가 참이면 해당 원소를 acc에 추가하면 최종적으로 predicate(x)를 만족하는 원소들을 리턴하게 됩니다.

function myfilter(arr, predicate) {
    return arr.reduce(function (xs, x) {
        if (predicate(x))
            xs.push(x);
        return xs;
    }, []);
}

비슷한 방식으로 map 함수도 구현할 수 있습니다.

function mymap(arr, f) {
    return arr.reduce(function (xs, x) {
        xs.push(f(x));
        return xs;
    }, []);
}

filtermap은 별개의 함수처럼 보이지만, reduce 함수를 통해 공통점을 뽑아낼 수 있는 수준의 유사점도 가지고 있음을 확인할 수 있습니다. 두 함수 모두 배열이라는 데이터 구조를 돌면서 각 원소에 대해 어떤 처리를 하고 결과값을 리턴합니다. filter는 각 원소가 predicate를 통과하는지 확인하고, 통과하는 원소들만 다시 배열로 리턴하는 반면 map은 각 원소에 함수 f를 적용하고 결과값을 조건 없이 배열로 리턴한다는 차이점이 있지만, 결과적으로 배열이라는 데이터 구조를 돌면서 결과값을 만들어내는 방식 자체는 동일한 셈입니다.

바꿔 말해, 배열로 뭔가를 해야 하는 거의 모든 함수는 reduce 함수 (혹은 reduceRight 함수)로 만들어 낼 수 있다는 뜻입니다. filtermap 외에도 underscore.js가 제공하는 대부분의 고차 함수를 reduce로 만들어 낼 수 있습니다.

fold 함수의 표현력이 궁금하신 분은 Graham Hutton 교수의 논문 A tutorial on the universality and expressiveness of fold을 읽어보시기 바랍니다.

TypeScript: Best Common Type

TypeScript tries to find the best common type when a type inference is made from several expressions.

Let’s experiment a bit with following types. Square is a subtype of Shape and Circle is also a subtype of Shape.

class Shape {
    color: string;
}

class Square extends Shape {
    sideLength: number;
}

class Circle extends Shape {
	radius: number;
}

The type of xs1 is Shape[] because Shape is the common supertype of Shape, Square and Circle. However, surprisingly the type of xs2 is not Shape[] though Shape is the common supertype of Square and Circle. Here the type of xs2 is (Circle | Square)[] because there is no object that is strictly of type Shape in the array.

var xs1 = [new Shape(), new Square(), new Circle()];
var xs2 = [new Square(), new Circle()];

You can override this type by annotating the type explicitly with Shape[].

var xs3: Shape[] = [new Square(), new Circle()];

Now let’s see how the return type of a function is inferred when the function returns two values with different types.

function createShape1(square: boolean) {
    if (square) {
        return new Square();
    } else {
        return new Shape();;
    }
}

The return type of createShape1 function is Shape as expected because Shape is the common supertype of Square and Shape.

function createShape2(square: boolean) { // Type Error
    if (square) {
        return new Square();
    } else {
        return new Circle();
    }
}

However, if we change the return value of else branch to new Circle(), createShape2 function no longer type checks. TypeScript complains about “error TS2354: No best common type exists among return expressions.” It fails to find the best common type though it can be inferred as either Square|Circle or Shape.

We can satisfy the type checker by giving an explicit type. The return type can be either Square | Circle or Shape.

function createShape3(square: boolean): Square | Circle {
    if (square) {
        return new Square();
    } else {
        return new Circle();
    }
}

function createShape4(square: boolean): Shape {
    if (square) {
        return new Square();
    } else {
        return new Circle();
    }
}

From the examples above, we can see that the type inference rule of TypeScript is not orthogonal. When you mix multiple types in an array, TypeScript finds the best common type that is the union of the types of the element expressions. But when a function mixes multiple return types in return values, it finds the best common type that is the first supertype of each of the others.

You can see the difference in the type inference rules taken from the TypeScript 1.4 specification.

Array Type

  • If the array literal is empty, the resulting type is an array type with the element type Undefined.
  • Otherwise, if the array literal is contextually typed by a type that has a property with the numeric name ‘0’, the resulting type is a tuple type constructed from the types of the element expressions.
  • Otherwise, the resulting type is an array type with an element type that is the union of the types of the element expressions.

Function Return Type

  • If there are no return statements with expressions in f’s function body, the inferred return type is Void.
  • Otherwise, if f’s function body directly references f or references any implicitly typed functions that through this same analysis reference f, the inferred return type is Any.
  • Otherwise, if f is a contextually typed function expression (section 4.9.3), the inferred return type is the union type (section 3.4) of the types of the return statement expressions in the function body, ignoring return statements with no expressions.
  • Otherwise, the inferred return type is the first of the types of the return statement expressions in the function body that is a supertype (section 3.10.3) of each of the others, ignoring return statements with no expressions. A compile-time error occurs if no return statement expression has a type that is a supertype of each of the others.

코드 주석

ZDNET에 올라온 나쁜 프로그래머가 되는 18가지 방법을 보면서 느낀 점을 몇 가지 적어봅니다. 이 글은 무려 18가지 방법에 대해 이야기하고 있는데, 일단 코드 주석에 대한 부분만 제 의견을 적어볼까 합니다.

9. 소스코드가 주석 하나 없이 깨끗하다

항상 주석 같이 읽기 쉬운 소스코드를 주장하면 주석 하나 없이 깨끗하게 코딩을 한다. 하지만 후배들은 주석이 없으면 이해하기 어렵다고 불평이다. 하지만 프로젝트 일정이 항상 너무 촉박해서 소스코드에 주석을 적을 시간이 없다.

보통 이런 상황은 주석이 없어서 코드가 이해하기 힘든 것이 아니라 코드가 이해하기 힘드니깐 주석이라도 달아서 설명을 해달라는 뜻입니다. 이런 불평이 나오면 주석을 쓸 게 아니라 코드를 리팩토링하거나 제대로 작성해야 하는 게 먼저입니다.

프로그래밍을 하다 주석이 필요하다고 느끼면 주석을 적기 전에 2번, 3번 다시 생각을 해야 합니다. 정말 주석을 달아야만 이해할 수 있는 코드인지, 주석이 아니라 코드에 작성자의 의도를 표현할 수 없는지 등을 고민하다 보면 대게의 경우 코드를 좀 더 잘 작성할 수 있는 방법을 찾게 됩니다.

주석은 코드가 아니기 때문에 시간이 지나면 코드와 주석이 따로 노는 현상이 빈번히 발생합니다. 변경이 잦은 코드일수록 주석은 빠르게 쓸모 없어지고, 코드를 읽을 때 오히려 혼란만 초라하게 되는 경우가 더 많습니다. 위 글 필자의 말처럼 프로젝트 일정이 항상 촉박하고 바쁜데, 코드뿐만 아니라 주석까지 유지보수할 개발자는 흔치 않기 때문입니다.

좋은 코드를 짜는 것도 어렵지만 좋은 주석을 다는 건 더 어렵습니다. 저는 코드 리뷰하면서 좋은 주석을 본 적이 거의 없습니다. 코드를 왜 이렇게 이상하게 짤 수밖에 없었는지 변명하거나, 코드에 이미 다 나와 있는 내용을 중복으로 기술하는 주석이 대부분입니다. 사실 이 정도도 글을 잘 쓰는 개발자나 할 수 있고, 대부분의 개발자는 함수 이름을 그대로 반복하는 수준의 주석만 씁니다. 예를 들어 함수 이름이 readFile이면 주석에 “파일을 읽는다”라고 쓰는 거죠. 그래서 저는 주석 쓸 시간에 코드를 좀 더 읽기 쉽게 짜라고 조언합니다.

물론 주석과 문서화는 다른 이야기입니다. 비전 문서, 아키텍처 문서, 설계 문서, API 문서 등 명확히 목적과 이유가 있는 문서들이 존재합니다. 하지만 우리가 흔히 “코멘트”라고 이야기하는 코드 주석은 명확한 목적성을 갖는 문서가 아니라 잘못을 변명 혹은 반성하는 경위서에 가깝습니다.

추가로 서두에 인용한 글처럼 소프트웨어 엔지니어링, 개발 프로세스 등에 대한 글을 쓸 때 “코드에 주석이 없으면 나쁜 개발자가 된다”는 식으로 결론만 이야기하는 건 무의미하다고 생각합니다. 이런 종류의 문제는 원래 정답이 없고 환경과 상황에 따라 적당한 수준을 찾는 과정이기 때문입니다.

코드 주석에 대해서 결론은 이미 정해져 있습니다. 필요한 만큼 적당한 수준으로 잘 적어야 잘하는 거죠. 이런 주제의 글을 쓰려면 여러 사례나, 본인의 경험담 등을 통해 그 뻔한 결론에 도달하는 과정을 보여줘야 합니다. 단순히 주석이 없으면 나쁘다는 글을 읽고 개발자들이 무엇을 배울 수 있는지 모르겠습니다.

Thoughts on Intersection Types

Facebook’s Flow is a static type checker, designed to find type errors in JavaScript programs. Flow’s type system is similar to that of TypeScript in that it is a gradual type system and relies heavily on type inference to find type errors.

One interesting feature of Flow that is missing in TypeScript is intersection types. For example, in Flow you can represent a function which takes either Bar or Foo with intersection types.

/* @flow */
class Foo {}
class Bar {}
declare var f: ((x: Foo) => void) & ((x: Bar) => void);
f(new Foo());
f(true); // Flow will error here.

The function f has type ((x: Foo) => void) & ((x: Bar) => void). The notation A & B represents the intersection type of A and B, meaning a value of A & B belongs to both A and B. We can capture this intuition with the following sub-typing rules:

[1] A & B <: A
[2] A & B <: B
[3] S <: A, S <: B ~> S <: A & B

In Flow, intersection types are primarily used to support finitary overloading. func takes either number or string and returns nothing. This can be represented as intersection of two function types as in the following:

type A = (t: number) => void & (t: string) => void
var func : A;

However, TypeScript doesn’t need intersection types to support finitary overloading because it directly supports function overloading.

interface A {
  (t: number): void;
  (t: string): void;
}
var func: A

Or in TypeScript 1.4, you can represent the same function more succinctly with union types.

interface A {
  (t: number | string): void;
}
var func: A

This is not a coincidence! Intersection types are the formal dual of union types. When an arrow is distributed over a union, the union changes to an intersection.

(A -> T) & (B -> T)  <:  (A | B) -> T

So it means the following two types are equivalent:

  • (t: number | string): void
  • (t: number) => void & (t: string) => void

So far intersection types seem redundant once a language have union types (or vice versa). However, there are some real world use cases where intersection type are actually required.

Let’s check how ES6’s new function Object.assign is typed in TypeScript (lib.core.es6.d.ts).

interface ObjectConstructor {
    /**
      * Copy the values of all of the enumerable own properties from one or more source objects to a 
      * target object. Returns the target object.
      * @param target The target object to copy to.
      * @param sources One or more source objects to copy properties from.
      */
    assign(target: any, ...sources: any[]): any;
    ...
}

Currently, both the argument types and the return type of Object.assign is any because the type system of TypeScript can’t represent the type correctly. Let’s try to type this function correctly. First, we can make this function polymorphic by assigning A to target and B[] to sources.

Object.assign<A,B>(target: A, ...sources: B[]): ?;

Okay. We are now stuck with the return type. The return value has all the properties of both A and B. It means with structural typing, the return value is a subtype of both ‘A’ and ‘B’ (belongs to both A and B). Yeah! We need intersection types to represent this value. So the correct signature of this function is:

Object.assign<A, B>(target: A, ...sources: B[]): A & B;

The same reasoning also applies to mixins.

mixins<A,B>(base: { new() :A }, b: B}) : { new(): A & B} 

TypeScript developers are still discussing on adding intersection types. Many people think that there are not enough compelling use cases. Also intersecting two primitive types like string & number makes no sense, which makes intersection types less desirable.

I think adding intersection types to TypeScript makes the language more consistent because these two concepts are the dual of each other and can’t really be separable. But I also think that the language design must be conservative. So let’s just wait until we have more compelling reasons to add intersection types.