프로그래밍: 무(無)보다 적은 것으로 프로그래밍하기

(joshmoody.org)

2P by GN⁺ 10일전 | ★ favorite | 댓글 1개

이 글은 면접 상황에서 지원자가 단순한 FizzBuzz 문제를 람다 대수 기반의 순수 함수 조합자로 구현하려는 풍자적 서사를 담음
주인공은 JavaScript로 시작하지만, 점차 S, K, I 조합자를 정의하며 언어의 기본 구조를 스스로 재구성함
이어서 불리언, 수, 리스트, 문자열을 모두 조합자만으로 표현하고, Y 조합자를 통해 재귀를 구현함
최종적으로 FizzBuzz를 완전한 포인트 프리(point-free) 스타일로 완성하지만, 코드가 인간이 이해할 수 없는 수준으로 확장됨
이 글은 프로그래밍 언어의 본질과 추상화의 극단을 유머러스하게 탐구하며, 개발자 문화의 자기 풍자를 드러냄

면접의 시작: FizzBuzz와 조합자

이야기의 시작은 면접관 Dana가 지원자에게 FizzBuzz 문제를 풀어보라고 요청하는 장면으로 시작
- 지원자는 일반적인 반복문 대신 S와 K 조합자를 정의하며 문제를 풀기 시작
- Dana는 의아해하지만, 지원자는 “조금만 더 하면 된다”고 말하며 계속 진행
지원자는 I, B, C, W, T 등 다양한 조합자를 정의하며, 이를 새로운 언어의 기본 구성 요소로 사용
- 각 조합자는 함수 합성, 인자 교환, 자기 적용 등 람다 대수의 핵심 개념을 구현
- 코드 주석에는 “Bluebird, Cardinal, Warbler, Thrush” 등 조합자 이름의 별칭이 등장

불리언과 수의 정의

지원자는 TRUE, FALSE, NOT을 조합자만으로 정의하며 불리언 논리를 구축
- Dana는 “람다 대수냐”고 묻지만, 지원자는 “람다 대수는 너무 비대하다”고 답함
이어서 ZERO, SUCC, PRED, IS_ZERO 등을 정의하며 수 체계(Church numeral) 를 구성
- SUCC는 후속자, PRED는 전임자, DECREMENT는 0 이하로 내려가지 않는 감소 연산을 구현
- ONE부터 TEN까지의 숫자를 순차적으로 정의

재귀와 Y 조합자

지원자는 ADD 함수를 정의하며, 점차 포인트 프리(point-free) 형태로 변환
- ADD_MAKER를 정의하고, 이를 Y 조합자로 감싸 재귀를 가능하게 함
- Dana는 “JavaScript에서도 재귀가 된다”고 지적하지만, 지원자는 “곧 JavaScript가 아닐 것”이라 답함
JavaScript의 엄격한 평가(eager evaluation) 로 스택 오버플로가 발생하자, 지원자는 Skoobert라는 “게으른(lazy)” JS 인터프리터로 코드를 실행
- 결과는 성공적으로 3을 출력

산술, 리스트, 그리고 문자열

지원자는 SUBTRACT, MULTIPLY, MOD, DIVIDE 등 산술 연산을 모두 조합자 기반으로 구현
- 각 연산은 IS_ZERO, PRED, SUCC 등을 재귀적으로 결합해 구성
이어서 CONS, FIRST, REST, EMPTY를 정의하며 리스트 구조를 구축
- MAP, FOLD, RANGE, CONCAT 등 고차 함수형 연산을 모두 조합자 형태로 구현
리스트를 문자열로 출력하기 위해 renderList, showLines 함수를 작성
- Dana는 이미 포기한 듯 반응하지 않음

문자와 문자열의 구성

지원자는 문자 코드를 1부터 9, 그리고 10단위로 조합자를 이용해 정의
- CHAR_A부터 CHAR_Z, CHAR_0부터 CHAR_9까지를 모두 수 조합으로 표현
ARRAY 함수를 통해 문자열을 리스트로 변환하고, FIZZ, BUZZ, FIZZBUZZ를 생성
- extractString 함수를 통해 리스트를 실제 문자열로 변환
- 콘솔 출력 결과는 "fizzbuzz"

숫자에서 문자열로의 변환

숫자를 자릿수 리스트로 바꾸는 NUMBER_TO_DIGIT_LIST와 이를 문자열로 바꾸는 NUMBER_TO_STRING을 정의
- DIVIDE, MOD, TEN 등을 이용해 각 자리수를 분리
- DIGITS_NUMERAL 리스트를 통해 숫자 문자 매핑 수행
이 과정을 통해 숫자 → 문자 → 문자열 변환이 완전한 조합자 체계 내에서 가능해짐

FizzBuzz의 완성

FIFTEEN, ONE_HUNDRED를 정의하고, MAP과 RANGE를 이용해 1부터 100까지의 리스트를 생성
- 각 숫자에 대해 3, 5, 15의 배수를 판별하여 "Fizz", "Buzz", "FizzBuzz" 또는 숫자 문자열을 출력
- showLines(extractString)(FIZZBUZZ_RESULT)로 최종 결과를 출력
Dana는 “이제 만족하냐”고 묻지만, 지원자는 모든 변수 정의를 제거하고 순수 조합자만으로 코드를 재작성
- 결과는 수천 줄에 달하는 S와 K만으로 구성된 거대한 표현식

결말과 의미

글은 프로그래밍 언어의 근본적 구성 요소를 탐구하는 동시에, 개발자들이 단순한 문제를 과도하게 복잡하게 만드는 경향을 풍자
- “무(無)보다 적은 것으로 프로그래밍한다”는 제목은 언어의 최소 단위로부터 세계를 재구성하려는 시도를 상징
이 작품은 함수형 프로그래밍, 람다 대수, 조합자 논리에 대한 깊은 이해를 유머와 서사로 풀어낸 기술 문학
- 동시에, “FizzBuzz조차 철학적 실험으로 바꾸는 개발자 정신”을 풍자적으로 드러냄

▲

GN⁺ 10일전 [-]

Hacker News 의견

사람들이 “이게 대체 뭐지?” 하는 것 같아서 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를 구현해봤음. 아침을 재밌게 낭비했음
  결과 링크
combinator logic 설명이 정말 멋졌음. 글 스타일이 이 시리즈를 떠올리게 함
- 설명이라기보단 보여주기용 퍼포먼스에 가까움. 그래도 꽤 인상적이었음
- 확실히 그 시리즈에서 영감을 받은 것 같음. 저자 이름을 언급했으면 더 좋았을 듯함
- 영국에서는 Online Safety Act 때문에 접근이 막혀 있어서 아쉬움
예전에 읽은 “FizzBuzz in TensorFlow” 글이 떠오름
링크
- 이번 글은 그래도 따라갈 수 있어서 좋았음
이런 프로그래밍 인터뷰 프레임은 좀 잘못된 것 같음
인터뷰의 목적은 (1) 지원자의 프로그래밍 지식 확인, (2) 회사의 프로그래밍 문화 적합성 확인임
예를 들어 JavaScript 포지션을 뽑는데 combinatory logic에 깊이 빠져 있다면, 그건 문화적으로 맞지 않을 가능성이 큼. 그래서 탈락해도 이상하지 않음
- 아마 이 시리즈를 참조한 것 같음. 다만 원문에는 명시되어 있지 않음
- 가끔은 HN 댓글러들이 재미를 잊은 사람들처럼 느껴짐
- 프로그래밍의 다양성을 강조한 건 맞지만, 그건 특정 생태계 전문성을 뽑는 한 형태일 뿐임. 대부분은 레거시 코드나 기존 생태계 활용을 위한 선택임
- “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 없이도 무한히 많은 방식으로 재귀를 구현할 수 있음

답변달기