작은 프로그램과 언어

요약

작은 프로그램과 작은 언어는 어려운 컴퓨팅 개념을 머릿속에 담을 수 있는 크기로 보여 줍니다.

개발자 데이브 가우어가 개인 사이트에 쓴 글입니다. 직접 Forth를 구현한 글에 아주 작은 Forth를 알려 주는 반응이 이어지자, 작은 것들에 끌리는 이유를 정리했습니다.

왜 중요한가

아주 작은 프로그램이 단순한 재주 자랑이 아니라 개념의 실제 복잡도를 드러낸다고 봅니다.
개념을 작은 크기로 이해하고 나면 크고 위압적인 시스템도 덜 두렵게 느껴진다고 했습니다.

핵심 내용

46바이트 Forth, 가비지 컬렉션(쓰지 않는 메모리를 자동으로 회수하는 기능)을 갖춘 436바이트 Lisp 같은 예를 듭니다.
JavaScript 25줄짜리 DOM 비교 라이브러리, C 122줄로 된 배열 언어 해석기도 소개합니다.
명함에 들어가는 레이 트레이서처럼, 작은 판은 그 개념이 머릿속에 들어간다는 증거라고 했습니다.
언어를 크기와 표현력으로 비교하며 Forth가 거의 모든 '작음' 경쟁에서 이긴다고 봤습니다.
작으면서도 쓰기 고통스럽지 않은 언어로는 Lua를 꼽고, 표현력보다 단순함이 중요하다고 했습니다.

HN 반응

uxn(아주 작은 가상 머신)으로 39바이트 16진수 디코더와 1,853바이트 카드 게임을 만들었다는 경험담 등 작은 프로그램 사례가 이어졌습니다.
기계어를 바로 생성하는 작은 언어를 만든다는 글에는 단계를 나눠야 검증이 쉽다는 조언과 단순함을 지키겠다는 답이 오갔습니다.

22개 표시 · 전체 30개

zzo38computer1일 전 HN

저는 uxn으로 쓸 만한 작은 프로그램을 몇 개 만들었습니다. 16진수 디코더(공백과 줄바꿈을 선택적으로 처리하고 대소문자도 가리지 않습니다)는 39바이트, JSON을 NDJSON으로 바꾸는 프로그램은 125바이트, DER을 TER의 부분집합으로 바꾸는 프로그램은 220바이트, BLAKE2s는 1024바이트입니다(정렬을 맞추려고 채워 넣은 패딩이 일부 있어서 딱 1024가 됩니다). 그래픽, 효과음, 글꼴, 점수 계산까지 갖춘 카드 게임은 1853바이트입니다. (이 프로그램들은 오류 검사를 항상 하지는 않습니다. 카드 게임은 올바른 수를 뒀는지는 검사합니다. 코드가 짧아지는 이유 중 하나가 바로 이것입니다. 때로는 그런 검사가 필요하기도 하니 그러면 다른 프로그램은 더 길어지겠지만, 이는 uxn이나 제가 만든 프로그램에만 해당하는 이야기가 아닙니다.) 다른 분들도 만들었을 수 있습니다.

uxn과 varvara의 명세도 작아서 두 쪽이면 충분할 수 있습니다(제가 쓴 것은 아닙니다).

또 어떤 책에서, 누군가 아타리용 게임을 2킬로바이트로 만들면서 어떻게 그 크기에 맞췄는지(맵을 대칭으로 만드는 등) 설명한 대목을 읽은 기억이 있습니다. 그때는 이미 4킬로바이트 카트리지가 나와 있어서 그 방식은 채택되지 않았다고 합니다. (이 글에도 (아마도) 다른 사람이 2킬로바이트로 만든 게임이 링크되어 있는데, 이쪽은 JavaScript와 HTML로 만든 것입니다. 다만 아타리나 uxn/varvara는 HTML/JavaScript보다 훨씬 단순한 시스템입니다.)
Skwid1일 전 HN

uxntal과 varvara는 정말 즐거워요. 한 번에 한 걸음씩 다가가면 모든 게 재미있는 퍼즐처럼 느껴지는, 딱 그런 복잡도거든요.

몇 년 전 처음 봤을 때는 회의적이었어요. 저는 뼛속까지 하드웨어 쪽 사람이라 명령어를 트랜지스터 수와 게이트 지연으로 보거든요. 16x16 곱셈에 그렇게 다 쏟아붓고서 오버플로 플래그 하나 둘 플립플롭도 못 아꼈다고요? 말도 안 되죠!

그런데 이미 작성된 소프트웨어가 에뮬레이트해 볼 만하다고 납득시킬 만큼 멋졌고, 에뮬레이터가 생기면 소프트웨어도 하나쯤 짜게 되잖아요. 짧은 프로그램 몇 개를 짜고 나니 푹 빠져 버렸어요. 코드를 효율적으로 돌리는 게 중점이 아니라, 효율적인 코드를 재미있게 쓸 수 있게 해 주는 거예요.

날카로운 모서리도, 예외적인 경우도 없고, 기계 상태도 대체로 최소한이에요. 제가 써 본 어떤 실제 어셈블리보다 인지 부담이 훨씬 작아요.

두서없는 딴소리를 이렇게 길게 늘어놓을 생각은 아니었는데, 아무튼 이 작은 녀석이 너무 좋아요. ( ⊖-w-⊖)
WalterBright1일 전 HN

할 피니는 Mattel Intellivision용 BASIC 인터프리터를 ROM 2K 정도로 만들었습니다.

물론 할은 천재였지만요.
shikaan1일 전 HN

좋은 글이네요 (: 저도 정확히 이렇게 배우는데, 요즘은 다 부질없게 느껴지기도 해요.

저한테는 빡빡한 제약 안에서 작업하는 것도 또 다른 매력이에요. 몇 년 전에 부트로더 안에 들어가는 운영체제를 만들었거든요(목록에서 찾을 수 있을까 은근히 기대했어요 :P). 골프라고 하긴 어렵지만, 제약 안에서 놀아 보는 연습으로는 분명 좋았어요.

관심 있는 분은 한번 보세요. https://github.com/shikaan/osle
bryancoxwell1일 전 HN

정말 즐겁게 읽었습니다. 요즘 소프트웨어 개발에 좀 시큰둥했는데, 이 글 덕분에 옛 관심사가 다시 살아났습니다.
abainbridge1일 전 HN

저는 정말 단순한 컴파일 방식의 스크립트 언어를 만들어 보고 싶습니다. 대부분의 스크립트 언어가 왜 바이트코드로 컴파일한 다음 그걸 해석하는지 이해가 안 됩니다. 그러려면 다음 단계가 필요합니다.

1: 바이트코드 설계. 2: 컴파일러 작성. 3: 인터프리터 작성.

1번과 3번을 건너뛰고 기계어를 바이트코드로 쓰면 더 간단할 것 같습니다. 덤으로 프로그램도 더 빨리 돌아갑니다.

최적화 컴파일러가 만들어 내는 코드보다 3배쯤 크고 느려도 상관없다면, x86_64, ARM64, risvc64용 기계어를 만드는 건 쉬울 거라고 생각합니다. 이 아키텍처들이 공통으로 지원하는 기능의 부분집합만 노리면 되니까 쉬울 수밖에 없습니다.

조금 시작해 봤는데, https://github.com/abainbridge/mortar , 피보나치 수열 생성기를 컴파일해서 돌리는 것 이상은 아직 못 갔습니다. 언어 설계나 컴파일러 구현 경험은 없습니다. 거의 똑같이 생긴 Python 프로그램보다 피보나치 생성기가 380배 빠르게 돌아서 꽤 얼떨떨했습니다.

의견이나 제안이 있으면 뭐든 좋습니다. "그건 나쁜 생각이다, XYZ 때문에 실패할 것이다"든, "고생하지 마라, 내가 전에 써 둔 게 여기 있다..."든요.
mrkeen1일 전 HN
빠뜨리고 계신 관점은 이거라고 생각합니다. 기계어가 소스 코드와 같은 뜻이라는 걸 어떻게 보장하느냐는 것입니다.

'print "hello world";' 같은 걸
```
  .LC0:
        .string "hello"
  "square":
        push    rbp
        mov     rbp, rsp
  ...
```
로 한 방에 바꾸려는 건 아마 시작부터 안 되는 일이라서, 컴파일러 개발자들은 문제를 여러 패스로 잘게 쪼개서 공략하는 경향이 있습니다.

가장 먼저 할 일은 당연히 AST로 파싱하는 것이고, 그다음에는 타입 검사, 클로저 처리, 일종의 IR로 단순화하는 패스 등을 선택적으로 넣고, 마지막에 코드를 생성합니다. 이 단계들은 하나하나 효과적으로 단위 테스트할 수 있습니다(마지막 단계는 예외일 수 있습니다). 파싱에서 실수를 했을 때(예를 들어 문장을 식으로 착각하는 경우) 그 오류를 기계어를 들여다보면서 잡고 싶지는 않을 겁니다. 각 패스를 쉽게 테스트할 수 있으면 좋습니다. 그리고 이를 테스트하는 간단한 방법 하나는 패스마다 인터프리터를 작성하는 것입니다(주된 이유는 작성에 쓰는 호스트 언어의 기능을 그대로 누릴 수 있기 때문입니다). 그러면 "모든 입력에 대해 AST를 해석한 결과는 타입 검사를 거친 AST를 해석한 결과와 같고, 이는 클로저를 처리한 AST를 해석한 결과와 같고, 이는 IR 명령어 목록을 해석한 결과와 같다"는 식으로 말할 수 있게 됩니다.

"이 아키텍처들이 공통으로 지원하는 기능의 부분집합만 노리면 되니까 쉬울 수밖에 없다"고 하셨는데, <- 그게 바로 당신의 IR입니다!

목표 기계어와 충분히 비슷하게 생긴 IR이 있으면 마지막 단계의 변환은 그리 어렵지 않을 겁니다. 아니면 그냥 LLVM을 쓰세요.

코드를 보니 C를 쓰고 계신데, 사실 그럴 필요는 없습니다. 언어가 꼭 계층 구조로 쌓여야 하는 건 아닙니다(예를 들어 Clojure는 JVM 위에 있고, JVM은 C++이고, C++은 asm으로 컴파일되는 식으로요). 컴파일러는 어떤 언어로 만들어도 됩니다. 소스 코드를 받아서 바이트를 뱉어내기만 하면 되니까요.
abainbridge23시간 전 HN

빠뜨리고 계신 관점은 이거라고 생각합니다. 기계어가 소스 코드와 같은 뜻이라는 걸 어떻게 보장하느냐는 것입니다.

아, 아닙니다. 저는 이미 AST가 있습니다. AST의 노드 타입 하나에 대한 코드 생성을 쓸 때는 보통 godbolt에 그 노드 타입이 나타내는 것과 같은 종류의 일을 하는 C 코드 몇 줄을 넣어 보는 것부터 시작합니다. 컴파일러와 최적화 설정을 몇 가지씩 바꿔 가며 무엇이 생성되는지 봅니다. 그중 단순하면서 충분히 괜찮아 보이는 방식을 고릅니다. 그런 다음 AI에게 컴파일러들이 쓰는 것으로 보이는 명령어를 어셈블해 달라고 합니다. AI에게 시키는 건, 명령어 인코딩의 각 비트가 무슨 일을 하는지 설명해 주고, ISA 문서를 읽는 건 저보다 실수가 적기 때문입니다. AI의 설명을 보다가 "점프 대상이 32비트 즉시값에 안 들어가면 어떻게 하지" 같은 질문이 떠오르기도 합니다.

제가 주장한 건 이 방식이 제가 고안한 바이트코드용 코드를 생성하는 것보다 쉽다는 것뿐입니다. 바이트코드를 새로 고안하지 않아도 되는 것도 이유이고, 기존 도구를 쓸 수 있는 것도 이유입니다. 출력을 확인하는 디스어셈블러나 디버거, C 같은 문장을 기계어로 바꾸는 방법에 대한 아이디어를 주는 컴파일러가 그런 도구입니다.

지금은 IR이 없습니다. IR이 어떤 이점을 줄지 생각해 보겠습니다.

제가 이 프로젝트를 최상위 스레드 아래에 올린 건 제가 작은 프로그램과 언어에 관심이 있어서입니다. 제 실험은 언어 구현을 더 단순하게 만들려면 무엇을 걷어낼 수 있는지를 보는 겁니다. LLVM 의존성을 추가하는 건 제 생각과 정반대입니다 :-)

C로 쓰는 데는 여러 이유가 있지만, 주로 제가 C를 좋아해서입니다.
ozgrakkurt1일 전 HN

프로그래밍 언어에 관한 책을 읽어 보시길 권합니다. 대부분 이런 내용을 설명해 줍니다.

제가 이해한 바로는, 바이트코드는 이식성이 있지만 기계어는 그렇지 않다는 것입니다.

그래서 C로 바이트코드 인터프리터를 짜면 완전한 크로스 플랫폼 툴체인이 생깁니다.

또 바이트코드가 x86_64 기계어나 어셈블리를 생성하는 것보다 만들기 쉽다고들 합니다.

어차피 중요한 건 아이디어보다 실행이라고 생각하니, 이런 건 신경 쓰지 않으셔도 됩니다.

의견이나 제안이 있으면 뭐든 좋습니다. "그건 나쁜 생각이다, XYZ 때문에 실패할 것이다"든, "고생하지 마라, 내가 전에 써 둔 게 여기 있다..."든요.
norir1일 전 HN

ISA를 하나 고르고 그것을 그대로 본뜬 IR을 설계하는 건 간단합니다. 그 IR에서 원래 ISA로 코드를 생성하는 건 아주 쉽습니다. 다른 ISA도 간단하지만, 가상 레지스터를 도입해야 하거나 1:1로 대응하지 않는 명령어를 여러 명령어로 구현해야 할 수 있습니다.

원글 작성자는 코드 크기와 성능에 대해 너무 비관적이라고 생각합니다. 예를 들어 TCC는 끔찍한 기계어를 만들지만, 제가 주로 쓰는 종류의 프로그램에서는 clang과 크기나 성능이 3배씩 차이 나는 경우를 거의 보지 못했습니다. clang의 옵티마이저가 터무니없이 나쁜 결정을 내리는 극단적인 경우를 찾기도 아주 쉽습니다. 사소한 예로, "Hello, world!"를 출력하기만 하는 인자 없는 헬퍼 함수와 그 헬퍼를 100만 번 호출하는 main 함수가 있는 프로그램을 쓴 적이 있습니다. 최적화를 켜면 제 컴퓨터의 clang 버전은 헬퍼 호출을 100만 번 인라인했고, 그 바람에 바이너리가 -O0일 때보다 4~6배 커졌던 걸로 기억합니다. -O0에서는 컴파일에 6초쯤 걸렸고 -O2에서는 15분쯤 걸렸던 것 같습니다(tcc는 250ms쯤 걸렸고, 만들어진 바이너리는 gcc -O0의 2배쯤 크기였던 걸로 기억합니다). 결국 하고 싶은 말은, 저는 최적화 컴파일러의 품질을 대부분의 사람들만큼 믿지는 않는다는 겁니다.
abainbridge23시간 전 HN

원글 작성자는 코드 크기와 성능에 대해 너무 비관적이라고 생각합니다.

제 코드 생성은 확실히 TCC보다 형편없습니다! 하지만 요즘 CPU는 쓸데없는 레지스터 간 이동을 보고 그냥 no-op으로 처리해 줄 겁니다. 그래서 성능은 TCC와 크게 다르지 않을 가능성이 있습니다. 다만 지금은 의미 있는 비교를 할 만큼 복잡한 프로그램을 컴파일하기가 어렵습니다.
abainbridge1일 전 HN

제가 이해한 바로는, 바이트코드는 이식성이 있지만 기계어는 그렇지 않다는 것입니다.

이 부분을 탐구해 보고 싶습니다. 제가 보기엔 예전만큼 맞는 말이 아닙니다. x86_32가 마지막으로 이식을 어렵게 만든 주요 아키텍처였고, 이제는 무시해도 됩니다. 데스크톱이나 서버급 CPU는 전부 8, 16, 32, 64비트 정수를 지원합니다. 범용 레지스터도 전부 최소 10개는 있습니다. 메모리 접근 모드도 다들 쓸 만한 세트를 갖추고 있습니다. 그래서 같은 코드 생성기가 전부에 통합니다. 지금 제 코드 생성기는 emit_indexed_load, emit_conditional_jump 같은 함수를 호출하는데, 그런 함수가 현재 26개이고 전부 간단합니다.

지금까지는 x86_64 기계어 출력용으로만 구현했습니다. 하지만 ARM64나 risvc용 버전을 쓰는 건 어렵지 않아 보입니다. 작은 문제가 생겨서 코드 생성이 의존하는 CPU 기능 집합을 손봐야 하는 일은 있겠죠.

바이트코드 생성이 x86_64 기계어 생성보다 쉽다는 데는 동의하지 않습니다. x86_64 기계어를 검증하는 도구(즉 디스어셈블러)는 많습니다. 제가 고안할 바이트코드용으로는 하나도 없습니다. 게다가 x86_64 기계어로 인덱스 로드를 하려면 어떻게 생성해야 하는지 AI에게 물으면 바로 답이 나옵니다. 효율적인 바이트코드 인코딩을 어떻게 만들지 고민할 필요도 없고요.

지금까지 부딪힌 가장 어려운 문제는 컴파일된 코드가 기존 함수(예: libc)를 호출할 수 있도록 ABI를 맞추는 것입니다. 하지만 인터프리터를 쓰더라도 그 일은 해야 합니다.
raddan1일 전 HN

꼭 해 보세요. 다만 컴파일러 설계 책을 한두 권 보시길 권합니다. SSA처럼 프로그램 분석을 단순하게 해 주는 유용한 기법이 있어서, 최적화 패스를 추가해 보기로 마음먹었다면 도움이 됩니다. 직접 어렵게 만들어 보는 게 배우는 데는 단연 최고입니다. 저도 시간이 무한하다면 그렇게 해 보고 싶습니다...

추가: 저는 Appel의 컴파일러 책이 좋습니다. 제 학생 하나는 Nora Sandler의 "Writing a C compiler"를 재미있게 읽었습니다. 세부 내용에 깊이 들어가 보면 더 와닿는 고전 컴파일러 책도 여럿 있습니다.
abainbridge1일 전 HN

Appel 책은 몰랐습니다. 한번 볼게요. 감사합니다.

컴파일러 설계를 쓰는 방식 자체도 복잡도를 줄일 수 있을 것 같습니다. Nora Sandler의 블로그 글을 읽어 봤는데, "드래곤 북"에 비하면 정말 잘 쓰셨더군요(그분 책 표지에도 용이 있어서 헷갈립니다). 그래도 "어휘 분석(lexical analysis)" 같은 표현은 "문자 묶기(character grouping)"로 바꿔야 한다고 생각합니다(이 표현을 제 머릿속에 억지로 심어 준 Sam H Smith 덕분입니다).
tromp1일 전 HN

콜모고로프 복잡도를 구체화하려고 설계된 언어가 Binary Lambda Calculus입니다. 이 언어의 자기 해석기는 168비트(21바이트)밖에 안 됩니다. 글에 나온 Lisp 자기 해석기와 달리 비트스트림 위에서 동작하기 때문에 파서도 포함해야 합니다.
mdup1일 전 HN

부모 댓글 작성자의 IOCCC 걸작을 추천합니다. https://www.ioccc.org/2012/tromp/
rramadass1일 전 HN

Jon Bentley의 Little Languages - https://news.ycombinator.com/item?id=40989069

Randy Kaplan의 Constructing Language Processors for Little Languages - https://www.amazon.com/dp/0471597538?lv=shuf&channelId=500&plpRedirect=mhFallback
anthk1일 전 HN

https://t3x.org

JimTCL도 있습니다.
rramadass1일 전 HN

정보가 많은 아주 흥미로운 사이트네요.

공유해 주셔서 감사합니다.
1vuio0pswjnm719시간 전 HN
"여기서 SNOBOL도 특별히 언급해야 합니다. 위에서 말한 엄격한 문법 때문에도 그렇고, 비슷한 제어 흐름 문제를 던진다는 점에서도 어셈블리어와 비슷합니다. CPU처럼 점프와 호출/반환만 이해하니까요."

"그렇다면 작고 단순하면서 피를 제물로 바칠 필요도 없는 건 어떨까요?

Lua 프로그래밍 언어가 딱 맞는다고 생각합니다."

저는 평균 이하 사양의 컴퓨터에서, 예를 들어 증가하는 변수가 들어간 문자열 5001개를 출력할 때 spitbol이 lua/luajit보다 바이너리가 작고 lua보다 빠릅니다.^1
1. 예를 들어 블로그 글쓴이는 ASUS eeePC 701에서 어셈블리를 써 왔습니다: https://ratfactor.com/assembly-nights
```
   * 1.spt
    x = 0
   a output = "http://example.com/" x
    x = x + 20 
    le(x,1000000) :f(end)s(a)
   end

-- 1.lua
   local x=0
   while x<=1000000 do
   print("http:///example.com/"..x) 
   x=x+20
   end

busybox time luajit 1.lua >/dev/null
   busybox time spitbol 1.spt >/dev/null
   busybox time lua 1.lua >/dev/null
```
luajit 2.1.1753364724 666.7K 정적 바이너리(musl) amd64

spitbol 4.0f 175.4K 정적 바이너리(musl) amd64: luajit보다 2.67배 느리고 3.8배 작음

lua 5.5.0 362.6K 정적 바이너리(musl) amd64: spitbol보다 2.38배 느리고 2.07배 큼

lua 5.3.6 255.0K 정적 바이너리(musl) amd64: spitbol보다 2.63배 느리고 1.45배 큼
1vuio0pswjnm712시간 전 HN
- http://example.com
bitwize21시간 전 HN

무엇보다 인간 정신의 아주 현실적인 한계를 말해 주는 이야기입니다.

LLM을 쓰면 꽤 큰 코드베이스도 버그 없는 상태로 수렴시킬 수 있습니다. 사람이 혼자서 이해할 수 있는 코드베이스의 크기는 아주 작기 때문에, 흥미롭거나 쓸모 있는 일을 하는 아주 작은 코드 조각이 우리에게는 아름답고 경이롭게 보입니다. LLM은 그 한계를 뚫고 한 번에 우리보다 훨씬 많은 것을 이해할 수 있습니다. 결국 코드를 사람이 이해할 수 있느냐는 더 이상 중요하지 않게 될 것이고, 우리는 머지않아 거대한 복잡성의 탑이 진화하는 것을 이끌게 될 것입니다. 그 탑은 가장 높은 추상화 수준을 제외하면 기계가 꼼꼼하게 검사했기 때문에 그냥 잘 돌아갑니다.

LLM이 지금 약한 부분은 뉘앙스입니다. "비즈니스 맥락"이나 사용자에게 실제로 어떤 정보 자원이 필요한지 같은 것들이요.

Hacker News에서 보기 ↗