사람들이 “이게 대체 뭐지?” 하는 것 같아서 combinator의 요점을 설명해봄
combinator는 전역 상태를 변경하지 않고 외부 변수를 캡처하지 않는 함수임. 같은 인자를 주면 항상 같은 결과를 내고, 시스템의 나머지 부분에는 아무 영향도 주지 않음
이런 순수 함수들을 조합하면 또 다른 combinator가 만들어짐. 즉, 순수 함수의 합성은 여전히 순수 함수라는 뜻임
이런 함수들은 어셈블리나 C로도 쉽게 작성 가능함. 예를 들어 x64에서 S와 K를 직접 구현하고, 그 위에 combinator 기반으로 Common Lisp을 컴파일하면, 결국 두 개의 어셈블리 함수 위에서 Lisp이 돌아가는 셈임
성능은 별로겠지만, 수백 개 정도의 자주 쓰이는 패턴을 인라인 combinator로 만들어 이름 붙이면 꽤 실용적인 “기계”가 됨
이런 구조는 mutation을 두려워하는 Forth나, bytecode VM, 혹은 combinator를 “명령어”라 부르는 CPU와도 비슷함
결국 combinator는 구현 세부사항을 최대한 무시한 채 응용 컴퓨터 과학의 표현이라고 할 수 있음. 그래서 람다 계산보다 단순하다고 말할 수 있음
만약 람다 계산을 몇 개의 combinator로 구현하고, 그 위에 Lisp을 얹는다면, 스택의 가장 아래쪽에서 해야 할 기계 의존적 작업이 극도로 줄어듦
어딘가에서 함수 하나가 자기 자신을 호출하고 seed round를 받았을 것 같은 기분임
학생 시절에 비슷한 걸 해봤는데 (Lisp은 아니고 람다 계산으로 매크로 확장되는 간단한 언어였음) S와 K만으로 모든 걸 구현할 수 있다는 게 정말 충격적이었음. 하지만 동시에 얼마나 비효율적인지도 놀라웠음. 다만 명령어 집합이 커질수록 상황은 훨씬 나아짐
이론적으로는 다 가능하지만, 실제로는 그래프 재작성보다는 훨씬 실용적인 컴퓨팅 기반을 택해야 함. 계산 가능성의 한계를 실험하려는 게 아니라면, 이건 거의 파티 트릭 수준임. 게다가 숫자 표현도 문제임. 최소한 2의 보수 정수와 효율적인 소멸자를 써야 감탄할 만함
혹시 이런 식으로 combinator 위에 구현된 Lisp이 실제로 존재하는지 궁금함. 있다면 포팅하기 꽤 재미있을 듯함
let A = (x) => (y) => (z) => x(z)(y((w) => z))
이걸 몇 번만 조합하면 됨
let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
“람다 계산 따위는 절대 안 쓴다. 너무 부풀려진 언어다.”
하지만 실제로는 combinatory logic이 더 부풀려져 있음. 같은 프로그램을 표현하려면 더 많은 비트가 필요함
람다 계산은 오히려 가장 간결한 언어 중 하나임
JavaScript처럼 eager한 언어에서도 인자를 더미 람다로 감싸면 lazy하게 만들 수 있음. 예시는 이 JS BLC 인터프리터 참고
관련 논문은 이 PDF와 IOCCC 예제 참고
흥미로운 점은, 람다 계산 인터프리터 중 가장 빠른 것들(예: uni.c)이 결국 람다식을 combinatory logic으로 변환해 계산한다는 점임. 다만 S, K보다 더 큰 기본 집합을 사용함
“bloated language”란 불필요한 기능이 많은 언어를 뜻함. 예를 들어 C++은 C보다 코드가 짧을 수 있어도 훨씬 더 복잡한 언어임
저 코드 블록을 보고 있자니 입에서 나오는 소리가 인자 목록과 거의 일치함
K와 S 정의에 괄호 오류가 있는 것 같음. 수정 버전은 다음과 같음
let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
그리고 eager 언어를 lazy하게 만드는 건 이런 식으로 가능함
let A = x => y => z => () => x()(z())(y()(w => z()));
“w가 뭐지?”라는 의문이 생김
“FizzBuzz 알아요?”
“물론이죠. 10자짜리 코드골프 버전이요, 주니어도 이해할 수 있는 12줄짜리 버전이요, 아니면 기괴한 지식 자랑용 완전 엉뚱한 버전이요?”
이걸 보고 C64 BASIC으로 가장 빠른 FizzBuzz를 구현해봤음. 아침을 재밌게 낭비했음 결과 링크
이런 프로그래밍 인터뷰 프레임은 좀 잘못된 것 같음
인터뷰의 목적은 (1) 지원자의 프로그래밍 지식 확인, (2) 회사의 프로그래밍 문화 적합성 확인임
예를 들어 JavaScript 포지션을 뽑는데 combinatory logic에 깊이 빠져 있다면, 그건 문화적으로 맞지 않을 가능성이 큼. 그래서 탈락해도 이상하지 않음
프로그래밍의 다양성을 강조한 건 맞지만, 그건 특정 생태계 전문성을 뽑는 한 형태일 뿐임. 대부분은 레거시 코드나 기존 생태계 활용을 위한 선택임
“IQ가 낮으면 탈락” 같은 말은 웃기지만, 결국 돈만 충분하면 어떤 OOP/FP/FRP 스타일이든 맞춰줄 수 있음
현실에서는 이런 이상적인 인터뷰가 거의 없음. 대부분은 좌절한 면접관들이 자기 세계관을 강요함. 실제 업무는 인터뷰 내용과 거의 무관함
Moses Schönfinkel을 기억해야 할 시점임
그는 1920년 Hilbert의 제자 시절에 combinatory logic을 발명했음. 러시아로 돌아간 뒤 정신질환을 앓았고, 가난 속에 모스크바에서 사망함. 위키피디아에 따르면 그의 논문들은 이웃들이 난방용으로 태워버렸다고 함
마지막 코드 블록은 스크롤이 생길 정도로 큼 (166KB)
S와 K는 커리된 함수로, 한 번에 하나의 인자만 받음
자세한 내용은 이 StackOverflow 답변 참고
스크롤 내릴 때 문법 하이라이팅이 포기하는 순간이 제일 웃겼음
“Bluebird, cardinal, warbler, thrush” 같은 새 이름들 너무 마음에 듦. 새로운 명명 규칙으로 삼고 싶음
“Barendregt. Church는 너무 메이저하잖아.”
“곧 JavaScript도 아니게 될 거야.”
Douglas Adams가 SICP를 가르치는 느낌임
새 이름들은 Smullyan의 『To Mock a Mockingbird』에서 온 것임. 거기엔 더 많은 새들이 등장함
“그게… Y combinator야?”
“그렇지. 재귀하려면 필요하지.”
재미있는 사실: 고정점 조합자(fixed-point combinator) 는 무한히 많음. 즉, Y combinator 없이도 무한히 많은 방식으로 재귀를 구현할 수 있음
Hacker News 의견
사람들이 “이게 대체 뭐지?” 하는 것 같아서 combinator의 요점을 설명해봄
combinator는 전역 상태를 변경하지 않고 외부 변수를 캡처하지 않는 함수임. 같은 인자를 주면 항상 같은 결과를 내고, 시스템의 나머지 부분에는 아무 영향도 주지 않음
이런 순수 함수들을 조합하면 또 다른 combinator가 만들어짐. 즉, 순수 함수의 합성은 여전히 순수 함수라는 뜻임
이런 함수들은 어셈블리나 C로도 쉽게 작성 가능함. 예를 들어 x64에서 S와 K를 직접 구현하고, 그 위에 combinator 기반으로 Common Lisp을 컴파일하면, 결국 두 개의 어셈블리 함수 위에서 Lisp이 돌아가는 셈임
성능은 별로겠지만, 수백 개 정도의 자주 쓰이는 패턴을 인라인 combinator로 만들어 이름 붙이면 꽤 실용적인 “기계”가 됨
이런 구조는 mutation을 두려워하는 Forth나, bytecode VM, 혹은 combinator를 “명령어”라 부르는 CPU와도 비슷함
결국 combinator는 구현 세부사항을 최대한 무시한 채 응용 컴퓨터 과학의 표현이라고 할 수 있음. 그래서 람다 계산보다 단순하다고 말할 수 있음
만약 람다 계산을 몇 개의 combinator로 구현하고, 그 위에 Lisp을 얹는다면, 스택의 가장 아래쪽에서 해야 할 기계 의존적 작업이 극도로 줄어듦
이걸 몇 번만 조합하면 됨
“람다 계산 따위는 절대 안 쓴다. 너무 부풀려진 언어다.”
하지만 실제로는 combinatory logic이 더 부풀려져 있음. 같은 프로그램을 표현하려면 더 많은 비트가 필요함
람다 계산은 오히려 가장 간결한 언어 중 하나임
JavaScript처럼 eager한 언어에서도 인자를 더미 람다로 감싸면 lazy하게 만들 수 있음. 예시는 이 JS BLC 인터프리터 참고
관련 논문은 이 PDF와 IOCCC 예제 참고
“FizzBuzz 알아요?”
“물론이죠. 10자짜리 코드골프 버전이요, 주니어도 이해할 수 있는 12줄짜리 버전이요, 아니면 기괴한 지식 자랑용 완전 엉뚱한 버전이요?”
결과 링크
combinator logic 설명이 정말 멋졌음. 글 스타일이 이 시리즈를 떠올리게 함
예전에 읽은 “FizzBuzz in TensorFlow” 글이 떠오름
링크
이런 프로그래밍 인터뷰 프레임은 좀 잘못된 것 같음
인터뷰의 목적은 (1) 지원자의 프로그래밍 지식 확인, (2) 회사의 프로그래밍 문화 적합성 확인임
예를 들어 JavaScript 포지션을 뽑는데 combinatory logic에 깊이 빠져 있다면, 그건 문화적으로 맞지 않을 가능성이 큼. 그래서 탈락해도 이상하지 않음
Moses Schönfinkel을 기억해야 할 시점임
그는 1920년 Hilbert의 제자 시절에 combinatory logic을 발명했음. 러시아로 돌아간 뒤 정신질환을 앓았고, 가난 속에 모스크바에서 사망함. 위키피디아에 따르면 그의 논문들은 이웃들이 난방용으로 태워버렸다고 함
마지막 코드 블록은 스크롤이 생길 정도로 큼 (166KB)
S와 K는 커리된 함수로, 한 번에 하나의 인자만 받음
자세한 내용은 이 StackOverflow 답변 참고
“Bluebird, cardinal, warbler, thrush” 같은 새 이름들 너무 마음에 듦. 새로운 명명 규칙으로 삼고 싶음
“Barendregt. Church는 너무 메이저하잖아.”
“곧 JavaScript도 아니게 될 거야.”
Douglas Adams가 SICP를 가르치는 느낌임
“그게… Y combinator야?”
“그렇지. 재귀하려면 필요하지.”
재미있는 사실: 고정점 조합자(fixed-point combinator) 는 무한히 많음. 즉, Y combinator 없이도 무한히 많은 방식으로 재귀를 구현할 수 있음