배열 언어로 사고하기

• K 프로그래밍은 REPL에서 실험한 코드를 스크립트로 옮기며, 큰 명령형 패턴을 더 작고 선언적인 배열 패턴으로 계속 줄이는 데 초점을 둠
• ngn/k 스크립트는 REPL 입력처럼 줄 단위로 실행되고, \l file.k로 저장된 데이터와 함수를 REPL에 로드할 수 있음
• Wikipedia식 3중 루프 행렬 곱셈을 그대로 옮기면 전역 변수, 중첩 루프, 변경이 많아져 K의 장점과 어긋남
• 개선 과정은 +/ fold, ' each, /: eachright, \: eachleft, 전치 제거, tacit 변환을 거쳐 matmul: {x{+/x*y}\:y}에서 matmul: (+/*)\:까지 응축됨
• 행렬 곱셈 예시는 K 실력이 코드 응축 과정을 반복하며 복잡한 절차를 더 읽기 쉬운 배열 표현으로 바꾸는 데 있음을 보여줌

---

REPL 중심의 K 개발 흐름

• 전체 소스 코드는 GitHub의 matmul.k에서 볼 수 있음
• K 프로그래밍은 대부분 REPL에서 이루어지며, 이전 코드 위에서 빠르게 실험하고 개선하기 좋음
• ngn/k와 rlfe 조합은 위/아래 화살표 히스토리를 지원해 더 큰 K 프로그램을 개발하기에 충분함
• 함수는 먼저 REPL에서 테스트한 뒤 실제 코드로 옮기는 흐름이 자연스러움
• ngn/k의 prettyprinting은 항상 유효한 K 데이터를 반환하므로, 일부 값을 미리 계산해 프로그램 속도를 높일 수 있음

K 스크립트 실행 모델

• K 스크립트는 REPL에 입력한 것처럼 실행됨
  • 각 줄이 순서대로 실행됨
  • 줄이 세미콜론으로 끝나지 않으면 반환값이 출력됨
• 스크립트는 여러 줄 정의를 허용해 가독성을 높일 수 있음
• 저장된 데이터와 함수를 REPL에서 쓰려면 \l file.k를 실행함
  • 파일이 실행됨
  • 파일의 데이터가 로드됨
  • 같은 파일을 여러 번 로드하면 이전 데이터를 덮어씀
• \로 접근하는 REPL 도움말에서 더 많은 명령을 확인할 수 있음

배열 언어에서 패턴을 줄이는 법

• K와 배열 프로그래밍은 패턴을 계속 단순화하는 과정임
• 크고 다루기 어려운 패턴도 더 작고 선언적이며 읽기 쉬운 형태로 줄일 방법이 하나 이상 있음
• 관련 논의는 Patterns and Anti-patterns in APL: Escaping the Beginner's Plateau - Aaron Hsu - Dyalog '17에서 자세히 볼 수 있음
• 흔한 출발점은 GeeksforGeeks나 Wikipedia의 잘 알려진 알고리듬을 K로 번역하려는 상황임
• 예제는 행렬 곱셈을 사용함

명령형 행렬 곱셈을 그대로 옮겼을 때

• Wikipedia의 Matrix multiplication algorithm은 i, j, k 3중 루프와 sum 누산으로 행렬 C를 채움
• 이를 K로 직접 번역하면 A, B, n, m, p, C, i, j, k, sum 같은 전역 값을 많이 할당하게 됨
• 이 코드는 K를 명령형 언어처럼 쓰는 방식이라 K의 설계와 잘 맞지 않음
• 문제는 세 가지로 좁혀짐
  • 전역 할당이 많음
  • 여러 단계의 중첩 루프가 남음
  • 변경이 자주 발생함

안쪽 루프부터 접어 줄이기

• 가장 안쪽 루프는 sum을 0으로 초기화하고 k를 돌며 A[i;k]*B[k;j]를 누산함
• 첫 개선은 fold인 /를 써서 합산을 +/로 바꾸는 것임
  • sum 전역이 사라짐
  • C[i;j]::+/... 형태로 정리됨
• 이어서 ' each가 배열을 반환한다는 점을 이용하면 C를 변경하지 않고 중첩 루프의 반환값을 그대로 사용할 수 있음
• 이 단계 이후에는 변경 없는 세 개의 루프만 남고, 핵심 변수는 i, j, k가 됨

k, j, i를 없애는 과정

• 세 변수의 역할은 다음과 같음
  • i는 A의 각 행을 인덱싱함
  • j는 B의 각 열을 인덱싱함
  • k는 A의 각 열과 B의 각 행을 인덱싱함
• k는 A의 각 행과 B의 각 열을 짝지어 곱하게 하므로, 중간 인덱스를 없애고 직접 매칭할 수 있음
  • 이 단계에서 루프 하나와 m이 필요 없어짐
• j를 제거하려면 B의 각 열을 가져와 A[i]와 짝지어야 함
  • B를 전치하고 eachright /:로 각 요소를 짝지음
• i도 같은 방식으로 없앨 수 있음
  • eachleft \:를 사용해 A의 각 행과 B의 각 열을 짝지음
• 이 과정을 거치면 전역 없이 다음 형태가 됨

matmul: {x{+/x*y}/:\:+y}

전치 제거와 최종 tacit 형태

• + 전치는 비용이 크므로 제거할 수 있음
• 기존 방식은 x의 각 행과 y의 각 열을 곱하는 순진한 방식임
• 대신 B의 각 행을 A 전체에 맞추면 같은 작업을 암묵적으로 수행할 수 있음

matmul: {x{+/x*y}\:y}

• 이 함수는 Chapter 3의 규칙을 적용해 tacit 형태로 바꿀 수 있음
• 최종 결과는 다음과 같음

matmul: (+/*)\:

연습으로 만드는 배열 언어 직관

• matmul: (+/*)\:는 K다운 행렬 곱셈 함수로 정리됨
• 응축 과정은 처음에는 단계가 많아 보일 수 있음
• K를 연습할수록 코드 응축이 더 쉽고 직관적인 작업으로 바뀜
• 행렬 곱셈은 K의 배열 지원과 잘 맞는 단순 절차임
• 이후 장에서는 K와 잘 맞지 않는 알고리듬과 그 처리 방법을 다룰 예정임

[GN⁺]

Hacker News 의견들

• 실제로 배열 언어의 가능성을 가장 설득력 있게 보여준 건 Aaron Hsu가 병렬 APL 컴파일러 Co-dfns를 개발하는 모습을 설명한 영상이었음: https://www.youtube.com/watch?v=gcUWTa16Jc0&t=860s
  그는 HN에서 arcfide라는 이름으로 의미 밀도에 대해서도 여러 번 썼고, APL 코드는 한 화면 안에서 동작 방식, 주변 맥락, 의존성을 거의 이동 없이 볼 수 있게 설계한다고 설명함: https://news.ycombinator.com/item?id=13571159
  알고리즘 이름이 알고리즘 자체를 풀어 쓴 길이와 비슷해질 정도로 간결해지면, 영어 구를 읽듯 관용구 단위로 코드를 읽게 되고, 재사용 추상화를 만들기보다 화면에 보이는 모든 사용처를 직접 바꾸는 편이 더 빠를 수 있다는 관점임

  • 유한한 문맥 창을 가진 LLM이 다른 언어보다 APL을 더 잘 다룰지도 궁금함
  • 저런 긴 설명을 써야 하는 건 코드가 보기 흉하기 때문이라고 봄. 기호들이 서로 붙었을 때 덜 못생겨 보이게 골랐다면, 언어가 별로가 아니라고 사람들을 설득하는 데 18시간씩 쓰지 않아도 됐을 것 같음

• 배열 프로그래밍을 잘 모른다면 입문 자료로 The Array Cast를 추천함: https://www.arraycast.com/episodes/
  RSS 주소는 https://www.arraycast.com/episodes?format=rss

  • 설득되려고 The Array Cast 초반 5편쯤을 들었지만 결국 납득하지 못했음. 진행자들은 배열 언어의 짧은 표기와 비ASCII 기호가 익숙해지면 괜찮고 장점 때문에 감수할 만하다고 했지만, 그 장점 대부분은 요즘 주류 언어의 고차 함수로 이미 익숙한 것들이었음
    map/filter/reduce는 이미 거의 어디에나 있고, 표어문자 같은 표기 체계를 새로 배우지 않아도 쓸 수 있다는 점을 놓친 느낌이었음
  • 이걸 통해 BQN을 알게 됐지만, 실제 운영 환경에서 쓸지는 아직 모르겠음. 좋아하긴 해도 R, NumPy, Julia 정도가 아니면 대부분의 배열 언어는 낯설고, APL, J, BQN으로 깊게 들어가면 나중에 도움을 받을 사람들을 스스로 멀어지게 할 것 같음

• 70년대에 종이 터미널에서 실제 겹쳐 찍기를 쓰던 APL/APL2를 접하고 바로 빠졌지만, 나중에 ML과 Haskell로 함수형 프로그래밍을 알게 된 뒤 내가 APL에서 정말 좋아한 건 배열보다 함수 합성 능력이었다는 걸 깨달음
  Haskell은 완전히 순수하고 타입이 전반에 적용되어 이 부분에서 훨씬 낫고, APL보다 더 재미있고 강력했음. 작은·중간 규모 프로젝트를 많이 만들었고, LLVM Flang의 파서를 parser combinator로 구현할 수 있음을 보이는 프로토타입도 만들었으며, 매년 Advent of Code도 전체 수백 줄 정도로 풂. APL을 좋아한다면 Haskell도 시도해볼 만함
  지금은 APL의 “생각의 도구로서의 표기”라는 측면이 과도한 간결함을 합리화하는 말처럼 보임. 합성의 힘을 보여주는 데는 좋지만, 명확성을 해칠 수도 있음

  • 이 주제에선 계속 같은 말을 하게 되지만, point-free Haskell을 어느 정도 잘 쓰게 된 뒤로 J와 K를 거의 만지지 않게 됐음. 함수자까지 섞이면 동사 열차보다 더 강력해지고, <=<는 이미 있으며 fmap에 해당하는 걸 쓰면 정말 잘 굴러감
    |||, +++, &&&, ***도 좋고, UTF-8 연산자를 직접 만들어 더 짧고 예쁘게 만들 수도 있음. 다만 실제 업무나 공개된 진지한 Haskell 코드는 이런 식으로 세로 화면 공간에 친절한 경우가 드물어서 아쉬움
  • Advent of Code 소스 링크를 볼 수 있으면 좋겠음

• 배열 언어에서 “N보다 작은 수 중 술어 P가 참인 모든 수 찾기” 같은 문제를 어떻게 일반적으로 다루는지 궁금함. 예를 들어 1000보다 작은 소수 찾기나 z가 1,000,000보다 작은 피타고라스 삼쌍 찾기 같은 형태임
  명령형 언어라면 반복문에서 술어를 검사하고, 함수형 언어라면 재귀나 지연 리스트에 map/filter를 쓰겠지만, 배열 언어에서는 보통 1..N 배열을 만들고, 술어를 적용해 마스크 배열을 만든 뒤, 그 마스크로 원래 배열을 거르는 식으로 이해하고 있음
  N이 10억처럼 크고 술어가 거의 참이 아니라면 1..N 배열과 마스크라는 거대한 임시 배열 두 개를 만드는 게 메모리와 자원 측면에서 매우 낭비처럼 보임. 배열 언어는 이런 임시 배열을 계속 만들어서 느려지는지, 구현이 지연 평가 같은 방식으로 최적화하는지 궁금함

  • 맞음, 메모리를 많이 낭비함. 다만 메모리는 싸고, 필요하면 계산을 블록 단위로 나눌 수 있음. 실제로 메모리가 다 떨어지는 경우는 드물지만, 더 낮은 캐시 계층에 머무르기 위해 블로킹은 유용함
    스칼라 언어는 반대로 한 번에 한 값씩 처리하는 게 기본이라, 배열 언어가 SIMD 알고리즘으로 활용하는 잠재적 병렬성을 낭비함. 이것도 현 상태가 익숙해서 큰 문제로 잘 보이지 않을 뿐이고, 해법 역시 블로킹임
    실제로 배열 언어가 좋은지는 문제에 따라 다름. 대다수 실용적 용도에서는 성능이 전혀 중요하지 않고, k의 평판도 k 구현 자체가 빠른 언어라기보다 kdb가 데이터베이스로 빠른 데서 온 것 같음. 그래도 기계별 세부 최적화보다 우아한 배열 알고리즘에 집중하는 것만으로 놀랄 만큼 빨라질 수 있음: https://mlochbaum.github.io/BQN/implementation/versusc.html
  • 우회 방법은 몇 가지 있음. 지연 평가도 하나의 방법이고, Kap은 이를 사용함: https://aplwiki.com/wiki/KAP
    또 다른 명확한 방법은 전체 본문을 루프 융합해서 임시 배열이 생기지 않게 하는 것임. 더 단순한 선택지는 입력·출력 배열을 수십 KB 정도의 청크로 나눠 불필요한 임시 메모리 사용량을 제한하는 방식인데, 아는 한 이를 자동으로 하는 배열 언어는 없고 언젠가 CBQN에서 해보고 싶음. 사용자가 수동으로도 할 수 있으며, 성능을 극대화하려면 실제로 자주 해야 함
  • 직관은 대체로 맞지만, 실전에서는 드문 문제임. k 계열, 예를 들어 ngn/k에는 !10000000처럼 0부터 천만까지의 iota를 실제 천만 개 정수 배열로 만들지 않고 단순한 범위로 다루는 지연 구조가 있음
    물론 어떤 연산자를 쓰느냐에 따라 결국 그런 배열이 생길 수 있음. 또한 +|x처럼 x를 뒤집고 첫 원소를 취하는 패턴을 그냥 마지막 원소를 취하는 것으로 바꾸는 최적화도 있음
  • 배열 생성이 문자 그대로 일어난다고 보는 것 같음. 배열 언어가 내부적으로 청크 단위로 처리하지 못할 이유는 없음. 100억 개 정수 배열을 달라고 해도 순진하게 그대로 만들지 않을 수 있음
  • 많은 배열 언어에는 실제로 이 문제가 있음. 정확히는 단순하고 직관적인 방식이 필요한 것보다 훨씬 많이 계산하는 경향이 있다는 게 문제임
    물론 다르게 작성해서 피할 수 있지만, 그런 해법은 더 길고 덜 예뻐질 수 있음. 내가 작업 중인 APL 방언 Kap은 결과가 필요할 때까지 계산을 미뤄, 직관적인 방식으로 코드를 쓰면서도 버려질 결과를 계산하지 않도록 여러 경우를 처리함

• 배열 언어, 특히 k를 쓰며 가장 크게 깨달은 점들은 다음과 같음. 동사는 알고리즘이며, 명령형·객체지향 언어에서는 find, sort, group 같은 공통 알고리즘을 직접 구현해야 하는 경우가 많음
  동사나 부사의 연속은 내가 써본 것 중 가장 직접적인 합성 형태였고, 합성이 쉽고 자연스러움. 프로그램은 문장과 표현식의 모음이 아니라 알고리즘의 합성으로 보이게 됨
  배열, 맵, 함수에서 정의역과 치역 개념을 일관되게 다루면 설계 선택이 단순해지고, 오른쪽에서 왼쪽으로 평가되면 코드를 읽을 때 시선이 여기저기 뛰지 않아도 됨
  데이터를 코드로 가져오기보다 코드를 데이터로 보내는 방식이 가능하고 선호됨. 큰 k 프로젝트 대부분은 주석을 제외하면 네트워크 MTU, 즉 1540바이트 안에 들어감. k의 보너스로는 뷰가 함수적 관계를 직접 구현할 수 있고, 인터프리터를 통한 핫 코드 로딩으로 “영원히” 도는 애플리케이션도 가능함

• 취업 면접 준비로 K 언어 문제를 풀어본 개인적이고 편향된 제한적 인상은, 언어가 의도적으로 난해하다는 쪽임. 퍼즐과 영리한 풀이에는 좋은 언어임
  하지만 배열 언어와 배열로 생각하는 법을 가르쳐주는 건 Python에서 NumPy 배열을 다루는 경험이라고 봄

  • 어디 면접이었는지 궁금함

• J를 50시간 정도 써본 경험으로는 이 패러다임이 솔직히 너무 한쪽으로 치우쳐 있다고 느꼈음
  모든 문제를 배열의 중첩으로 생각하는 게 생각의 도구로서 도움이 되는지 모르겠음. 문제를 잘 포착하는 자료구조를 자유롭게 만들 수 있으면 알고리즘 부분이 크게 단순해질 수 있음
  APL/J/K를 쓰려면 더 똑똑해야 한다고 봄. 더 유연한 언어에서는 바로 가능한 접근이 종종 불가능해서, 문제를 변환해야 하고 그 과정에 훨씬 많은 사고가 필요할 수 있음

• 이 예시는 K 기반이지만, 또 다른 배열 언어로 J가 있음: http://jsoftware.com
  J에서는 dot =: +/ . *, P =: 2 3 4, Q =: 1 0 2, P dot Q처럼 쓰면 P와 Q의 내적 10을 반환함

  • 원래 배열 언어는 APL이고, 내적은 dot←+.×로 쓸 수 있음. 그런데 풀어 쓴 표기가 적당히 짧은 이름만큼 짧다면 굳이 이름을 붙일 필요가 없고, 이름 주변에 공백까지 넣어야 할 수도 있음
  • Haskell보다 이게 어떤 장점인지 아직 잘 모르겠음. dot = (sum.) . zipWith (*), p = [2, 3, 4], q = [1, 0, 2], p `dot` q처럼 쓰면 됨
    내 눈에는 sum과 zipWith에 이름을 쓰고, 리프팅이나 구조 변환이 “마법처럼” 일어나지 않는다는 차이밖에 없어 보임
  • KlongPy에서 내적은 dot::{+/x*y}로 씀. P::[2 3 4], Q::[1 0 2], dot(P;Q) 형태임

• 예시를 보면 이게 무슨 의미가 있는지 모르겠음. 어떤 식으로든 성능이 더 좋은가?
  행렬 곱셈 문법은 더 짧지만, 그건 K 언어가 어떻게 동작하는지에 대한 많은 내장 맥락을 머릿속에 들고 있어야 하기 때문으로 보임

  • 더 간결하다는 점 자체가 가치 있음. 특히 수학이 점점 더 많은 개념을 더 높은 수준의 정의로 압축하는 과정이라는 걸 생각해보면 비슷함. 더 높은 수준의 개념이 원시 요소가 되면 더 빠르게 생각하고 더 복잡한 대상을 만들 수 있음
  • 성능이 더 좋을 수는 있음. 컴퓨터는 배열을 훑는 작업에 매우 빠르고, 특히 SIMD를 활용할 수 있으면 그렇지만, 그게 전부는 아님
    배열 언어를 써보며 패러다임이 이해될 때까지 가지고 놀아볼 가치가 있음. 명령형 코드가 배열 스타일로 더 잘 표현되는 경우가 자주 있고, 길고 자잘한 함수가 배열 연산만으로 또는 다른 스타일과 함께 쓰여 크게 단순해질 때도 있음
  • 장황함에도 비용이 있고, 정말 복잡한 함수에만 장황할 특권이 있다고 믿는다면 의미가 쉽게 보임
    Haskell에서 (+) <$> Just 1 <*> Just 2와 do x <- Just 1; y <- Just 2; Just (x + y)를 비교하면, 이 정도 복잡도에서는 항상 첫 번째를 선호함. 두 번째는 더 많은 공간을 차지해서 뭔가 더 복잡한 일이 일어나는 것처럼 느껴짐
    더 복잡한 작업이라면 두 번째 형태를 쓰기보다 첫 번째 변형이 말이 되도록 작은 함수들로 분해하고 싶음. 이는 “초보자 일부가 빠르게 읽을 수 있음”을 “초보자 이상이 읽을 수 있음”으로 바꾸는 절충임
    “초보자 일부가 읽을 수 있음”을 최적화 대상으로 삼으면 수확 체감이 매우 크다고 보고, 대신 “초보자 이상” 또는 경우에 따라 “중급자 이상”이 읽을 수 있게 하는 쪽을 목표로 함

• 어떤 언어든 쓸 이유도 많고 쓰지 않을 이유도 많음. 하지만 핵심은 짧은 표기, 상대적 명확성, 빠른 코드로 컴파일되는 능력이 아니라, 나중에 온 프로그래머가 그 코드를 실제 사용을 위해 수정하고 유지보수할 수 있느냐임
  너무 자주 프로그래머들은 자신의 leet 실력을 보여주고 싶어 하면서, 뒤에 와서 그 코드를 떠맡아야 하는 불쌍한 사람들을 고려하지 않음. 현실적으로 많은 leet 코드는 장기적으로 지원 가능한 무언가를 얻기 위해 버려지거나 완전히 다시 작성되어야 함
  이걸 이해하는 데 오래 걸렸고, 이후에는 다른 사람들이 유지보수할 수 있도록 깨끗하고 단순하며 이해 가능한 코드를 쓰려 했음. 버리는 코드가 조직의 기본 인프라가 되어 굳어지고, 다음 세대에게 이해 불가능한 것이 되는 경우가 너무 많음