diff options
Diffstat (limited to 'docs/design/027-computation-core.md')
| -rw-r--r-- | docs/design/027-computation-core.md | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/docs/design/027-computation-core.md b/docs/design/027-computation-core.md new file mode 100644 index 0000000..4df67f9 --- /dev/null +++ b/docs/design/027-computation-core.md @@ -0,0 +1,189 @@ +# 027 — 계산의 핵: 상태는 값 하나, 값은 몇 가지로 짓는다 + +작성일: 2026-10-13. 상태: 설계와 단계. [026](026-app-contract.md)이 얼릴 계약 안에서 계산의 언어를 다시 세운다. 잴 도구는 +[140](../research/140-spec-suite.md)의 명세 묶음이다. 1.0 전이라 호환은 챙기지 않는다. 사용자의 말: "진행해" (2026-10-13). + +## 쉬운 말로 + +- **지금의 꼴.** aup와 Pure는 패턴마다 종류와 명령을 둔다. 커서, 인덱스, 문서, 표 보기, 메시지의 행이 각각 따로다. 그래서 세상의 + 명세를 담지 못하고(140), 새 패턴마다 형식과 세 실행 길이 함께 자란다. +- **이 설계의 꼴.** 그것을 "값 몇 가지와, 그 값들이 서로를 담는 법"으로 바꾼다. + - 상태는 타입 있는 값 하나다. + - 값은 수(정수, 실수, bool), 바이트(text는 UTF-8인 바이트), 레코드, 갈래, 리스트(키가 있으면 맵)다. +- **계산.** 함수(재귀 포함)와 접기다. 끝남은 문법이 아니라 예산이 보증한다. 이더리움의 가스와 같은 생각이다. 가스가 다하면 그 + 호출의 상태 변경이 모두 되돌아가는데, 이것이 026의 원자성과 같다. +- **빠름.** 뜻이 아니라 구현에서 온다. 열로 담기, B+트리, 묶음 실행, 같은 답일 때만 차례 바꾸기가 그 수단이다. +- **단계.** 다섯이다. + - 1단계(바이트, 비트, 수의 리스트)로 SHA-256을 쓴다. + - 2단계(중첩, 갈래, 재귀, 글자)로 JSON을 쓴다. + - 3단계에서 중첩된 상태를 저장한다. + - 4단계에서 패턴을 모은다. + - 5단계에서 수의 모델을 정한다. +- **근거.** + - 140의 탐침 + - 지금의 구현: 값의 칸 `Slot`, 열로 담은 B+트리 `PureList`, aup의 타입 여덟 + - 선행 기술: 아래 "선행" 절 +- **다음 결정.** 1단계를 만든다. + +## 핵 + +### 값 + +| 값 | 뜻 | 지금 | 바뀌는 것 | +|---|---|---|---| +| `bool` | 참, 거짓 | 같음 | — | +| `i64` | 정확한 정수, −2^63 … 2^63−1, 넘치면 `overflow` | 같음 | 비트 연산(1단계). 이름과 리터럴의 기본은 5단계 | +| `number` | 유한한 binary64 | 같음 | 5단계(수의 모델) | +| `bytes` | 바이트의 열, 불변 | 길이와 text 변환뿐 | 자리로 읽기, 자르기, 잇기, 짓기(1단계) | +| `text` | UTF-8로 검사한 바이트 | 같은 표현 | 글자로 읽기는 그 위의 견해(2단계) | +| 레코드 | 이름 있는 필드의 곱 | 필드는 수, text, bool, i64 | 필드에 아무 값(2단계) | +| 갈래 | 태그 붙은 경우의 합 | 없음 | 새로. `match`가 모든 경우를 다룬다(2단계) | +| `list of T [by k]` | 차례 있는 열. `by k`면 k의 차례이고 키마다 하나다 | 레코드만, 상태와 이벤트와 메시지의 행으로 따로 | 아무 T(1단계 수, 2단계 전부). 키 없는 리스트의 키는 자리다 | +| 앵커 | 편집을 따라가는 위치 | 커서와 인덱스(상태의 종류 둘) | 하나로(4단계) | + +### 계산 + +- **그대로 두는 것.** 식, `let`, `if`, `for`(세기와 걷기), `break`. +- **함수.** + - 자신을 부를 수 있다(2단계). + - 인라인은 구현의 선택이다. 작은 fn은 지금처럼 인라인하고, 재귀하는 fn은 부른다. + - 매개변수에 타입을 적지 않는 것은 그대로다. 부르는 타입마다 한 벌을 만든다(단형화). +- **`match`.** 갈래의 모든 경우를 다룬다. 빠진 경우는 컴파일 오류다(2단계). +- **끝을 모르는 반복.** `while`을 둔다(2단계). 세기의 상한은 뜻에서 필요하지 않다. 묶음 실행이 시작할 때의 횟수를 쓰는 것은 구현이 + 상한을 알아볼 수 있을 때다. +- **접기.** 뜻은 차례대로의 왼쪽 접기다. 구현은 같은 답과 같은 실패를 낼 때만 차례를 바꾼다. 묶음 실행기의 차례 없는 모으기가 이미 + 이 규칙을 따른다. +- **비트 연산.** 정수를 무한한 2의 보수로 보고 정한다. 파이썬의 정수와 같은 뜻이다. + - `&`, `|`, `^`, `~`: 비트마다의 연산이다. + - `x << n`은 x·2^n이다. i64를 넘으면 `overflow`다. + - `x >> n`은 floor(x / 2^n)이다. + - n은 0부터 63까지다. 밖이면 `limit`이다. + - 어느 기계에서나 같은 뜻이고, C의 정의되지 않은 동작이 없다. +- **끝남과 결정성.** + - 모든 걸음은 실행량을 쓰고, 부름의 깊이는 프레임의 바이트로 메모리 몫에 센다. 넘으면 `work`나 `memory`로 끝나고, 이벤트는 + 통째로 되돌아간다. + - 결정성의 단위는 모듈이다. 같은 모듈과 같은 이벤트열이면 실패의 자리까지 같다. + - 소스는 컴파일러의 판에 묶인다. EVM의 바이트코드와 가스표가 그렇다. 이것이 026의 의심 6(예산의 단위)에 대한 답이다. + +### 효과 + +026 그대로다. 상태에 쓰기, 보내기, 답하기, `require`. + +### 상태는 값 하나 + +- 앱의 상태는 레코드 값 하나다. 선언한 상태들이 그 필드이고, 수명(저장, transient)은 필드의 성질이다. +- 저장은 바뀐 부분만 쓴다. 지금 리스트가 이미지와 로그로 하는 그대로다. 중첩된 리스트도 제 이미지와 로그를 가진다(경로로 이름을 + 붙인다, 3단계). +- 값은 불변이라 스냅숏은 나누기만 한다. 지금 리스트의 공유 사본이 그 구현이다. + +### 뜻과 표현 + +| 뜻 | 표현(구현이 고른다) | +|---|---| +| 레코드의 리스트 | 열로 담은 B+트리, 값만큼 좁힌 열, HASHED(지금) | +| 수의 리스트 | 필드 하나인 레코드의 리스트(1단계), 나중에 배열 | +| 바이트 짓기(`out = out + byte(x)`의 반복) | 왼쪽이 이벤트 공간의 끝에 있으면 제자리 덧붙이기 | +| 표 보기 | 물을 때 칸 계산 | +| 접기 | 묶음 실행, 차례 없는 모으기(같은 답일 때만) | +| 작은 fn | 인라인 | + +## 026의 의심에 대한 답 + +| 의심 | 답 | 단계 | +|---|---|---| +| 1. 입력의 종류 | 입력은 메시지 하나다. 키, 글자, 틱은 표면과 호스트가 만드는 메시지다 | 4 | +| 2. 보기의 종류 | 보기는 아무 값을 낸다 | 4 | +| 3. 커서와 인덱스 | 앵커 하나로 모은다. 다만 키가 있는 리스트에서 인덱스는 키와 같을 수 있다. 4단계에서 앵커가 text에만 필요한지 본다 | 4 | +| 4. 키별 문서 | 없앤다. 키 있는 리스트가 한다 | 4 | +| 5. 수의 모델 | 정할 것: 정수 리터럴의 기본, `/`와 `//`, 돈을 위한 십진수 | 5 | +| 6. 예산의 단위 | 모듈로 정한다(위) | 이 문서 | +| 7. 고정 한도 | 뜻에는 예산(실행량, 메모리)과 모듈의 크기만 남긴다. 상태 32, 입력 32, 레코드 16, 필드 16, 컬렉션 1, 중첩 8, aup 소스 32 KB는 뺀다 | 4 | +| 8. 교체의 세부 | 수의 모델 뒤에 다시 본다 | 5 | +| 9. 메시지의 행 | 메시지의 필드가 아무 값을 가지면 따로 둘 까닭이 없다 | 2 | + +## 단계 + +### 1단계: 바이트, 비트, 수의 리스트 (SHA-256) + +- **Pure.** + - 바이트를 자리로 읽기(`b[i]` → i64, 밖이면 `limit`), 자르기, 잇기, 한 바이트로 짓기 + - i64의 비트 연산 여섯 + - 이벤트의 지역 칸이 바이트를 담는다 +- **aup.** + - `b[i]`, `b[a .. c]`, `b + c`, `byte(n)` + - i64의 `& | ^ ~ << >>`, 16진 리터럴 `0x…` + - `list of i64`와 `list of number`(안에서는 필드 하나인 레코드), 리스트 리터럴 `[ … ]` + - 키 없는 리스트를 자리로 읽고 쓰기 `xs[i]` +- **막대.** + - aup로 쓴 SHA-256이 NIST의 짧은 메시지 벡터와 긴 메시지 벡터를 모두 지난다(Pure의 검사 안에서). + - 줄 수가 같은 일을 하는 파이썬 참조 이하다. + - C 대비 시간은 재고 기록하되 막대는 두지 않는다. 바이트와 비트의 일은 실행기로 돈다. 빠르게 하는 것은 핵이 선 뒤다. + - 실행기만의 길에서 다섯 일(041)의 명령 수가 ±0.1%, 은행 질의의 명령 수가 ±1% 안이다. 새 명령은 기존 길을 바꾸지 않는다. +- **검증.** 새 명령마다 경계(밖의 자리, 음수 시프트, 넘침)를 단위 시험으로 본다. 무작위 입력의 다이제스트는 파이썬 `hashlib`와 같아야 + 한다. + +### 2단계: 중첩, 갈래, 재귀, 글자 (JSON) + +- 레코드의 필드와 리스트의 원소가 아무 값을 가진다. +- 갈래와 `match`를 둔다. +- 재귀하는 fn과 `while`을 둔다. Pure에는 부르기와 돌아가기, 함수마다의 검증이 생긴다. +- `for c in t`로 글자(코드 포인트)를 읽는다. +- 메시지의 필드가 아무 값을 가진다. JSON의 배열과 객체가 곧 리스트와 레코드다. +- 먼저 이벤트와 보기의 값(메모리 안)에서 한다. 상태는 3단계다. +- **막대.** + - JSON 파서가 JSONTestSuite의 `y_`를 모두 받고 `n_`을 모두 거절한다. `i_`는 정한 쪽을 적는다. + - 줄 수가 파이썬 참조 이하다. + - 시간을 기록한다. + - TPC-C와 은행 질의가 그대로다(026의 중단 기준). + +### 3단계: 중첩된 상태의 저장 + +- 중첩된 리스트의 이미지와 로그를 경로로 이름 붙인다. +- 스냅숏의 나누기와 교체의 이름 잇기가 깊이에서도 그대로 성립해야 한다. +- **막대.** 메모리 앱과 수시로 재시작하는 저장 앱이 매 단계 비트까지 같다(지금의 대조를 중첩으로 넓힌다). 커밋의 모든 단계에서 + 죽여도 전부 아니면 없음이다. + +### 4단계: 패턴 모으기 + +- 앵커, 메시지 하나인 입력, 아무 값인 보기를 둔다. +- 키별 문서와 고정 한도를 없애고, 메시지의 행을 중첩으로 옮긴다. +- **막대.** + - Pure, aup, Vega의 모든 검사를 옮긴 뒤 초록이다. + - 명령과 상태 종류의 수, 코어의 줄 수가 줄었다(세어 적는다). + - TPC-C와 은행 질의가 그대로다. + +### 5단계: 수의 모델 + +- 정수 리터럴의 기본, `/`와 `//`, 돈의 십진수, 묶음 실행기의 2^53 검사를 정한다. +- **막대.** TPC-C가 SQLite와 행마다 같은 상태를 남기는 것이 그대로다. + +**순서의 까닭.** +- 1과 2가 묶음의 명세 대부분을 연다. 가장 값이 크다. +- 3은 중첩을 상태까지 넓힌다. +- 4는 쌓인 것을 줄인다. 2 뒤에 해야 모을 곳(중첩, 갈래)이 생긴다. +- 5는 모든 앱의 수를 건드리므로 마지막이다. + +## 선행 + +- **EVM의 가스.** 끝없는 반복과 재귀를 허락하고, 끝남과 결정성을 가스로 얻는다. 가스가 다하면 그 호출의 상태 변경이 되돌아간다. 가스는 + 명령마다 명세의 표로 정한다. 모든 노드가 같은 가스를 센다. Pure의 예산, 원자성, "모듈이 단위"와 같은 꼴이다. +- **파이썬의 정수 비트 연산.** 무한한 2의 보수 위의 뜻이다. Pure는 i64 안에서 같은 뜻을 쓰고, 넘으면 실패한다. +- **Elm.** 모델, 업데이트, 뷰와 레코드, 커스텀 타입(갈래)이다. aup 앱의 모양과 같다. 영속, 트랜잭션, 전달은 없다. +- **영속 자료 구조**(Clojure의 벡터와 맵). 구조를 나눠 스냅숏을 싸게 한다. Pure의 공유 리스트 사본이 그 한 예다(B+트리). + +## 의심 (이 설계 안의) + +- **바이트와 text를 따로 둘 것인가?** 표현은 하나이고 타입만 둘이다. 불변식(UTF-8)이 보기와 경계에 필요해서 타입은 남긴다. +- **앵커가 필요한가?** 항목에 키가 있으면 인덱스는 키다. text의 커서는 편집에 따라 옮겨야 하므로 남는다. 4단계에서 정한다. +- **`number`(binary64)는 앱 런타임에 필요한가?** 물리와 그래픽에는 필요하다. 돈에는 맞지 않는다(5단계). +- **세는 `for`가 필요한가?** 뜻으로는 `while`과 예산이면 된다. 다만 세기는 읽기 쉽고, 상한을 구현에 알려 준다. 남긴다. + +## 1단계의 착수 기준 + +- **바꿀 결정.** 바이트, 비트, 수의 리스트로 SHA-256을 얇게 쓸 수 있으면 받아들이고, 2단계로 간다. +- **남은 질문.** + - 새 명령이 실행기, 묶음 실행기, JIT의 기존 길을 바꾸지 않는가? + - 한 블록에 드는 명령 수와 시간은 얼마인가? +- **최소 확인.** aup로 쓴 SHA-256, NIST 벡터, 파이썬 참조의 줄 수, C 대비 시간, 다섯 일과 은행 질의의 명령 수. +- **중단 기준.** 기존 일의 명령 수가 막대를 넘으면 멈추고, 새 명령이 기존 길을 건드린 곳을 찾는다. SHA-256이 파이썬보다 길면, 무엇이 + 길게 했는지 적고 그것을 1단계에서 고칠지 정한다. |