Say how aup chooses what a state outlives, and computes in memory (018)

1 files changed, 199 insertions, 0 deletions

diff --git a/docs/design/018-lifetimes-and-computation.md b/docs/design/018-lifetimes-and-computation.md
new file mode 100644
index 0000000..901ab08
--- /dev/null
+++ b/docs/design/018-lifetimes-and-computation.md
@@ -0,0 +1,199 @@
+# 018 — 상태의 수명과 메모리 안의 계산
+
+작성일: 2026-10-04. 상태: 설계와 착수 기준(구현 전).
+[외부 리뷰 005](../outside-feedback/feedback-005.md)의 (1) "순수 인메모리 연산 및 알고리즘의 단절"과, 상태의 영속성과 상태성을 aup
+안에서 정할 수단이 필요하다는 요청에서 시작한다.
+
+## 문제
+
+- **알고리즘을 쓸 수 없다.** aup의 반복은 리스트의 항목을 도는 걷기(`for x in xs`, Pure의 EACH) 하나다. 걷기 안에 걷기가 없고,
+  수를 세며 도는 반복이 없고, 중간에 멈출 수 없다. 이벤트 동안만 쓰는 리스트도 없다: 리스트는 저장되는 상태이거나 메시지의
+  행이다. 그래서 BFS의 큐와 방문 집합, DFS의 스택, 다익스트라, 동적 계획법, 뉴턴 반복 같은 계산을 aup로 쓸 수 없다. 005가
+  우려한 대로 "무거운 계산은 바깥 프로세스로"가 유일한 답이 된다.
+- **저장할지 고를 수 없다.** 모든 `state`는 저장된다. 접속 수, 캐시, 계산의 중간값처럼 다시 시작한 뒤에는 뜻이 없는 상태도
+  커밋마다 저장소에 쓰인다. SD 카드에서는 그 쓰기가 비싸다.
+- **읽기만 하는 계산도 소유자를 잡는다.** 경로 찾기나 통계처럼 상태를 바꾸지 않는 계산은 보기가 맞는 자리다. 보기는 스냅숏을
+  읽는 스레드(연결 스레드)에서 돌아 소유자를 막지 않는다. 그런데 보기는 식 하나라서 반복과 중간값을 둘 수 없다. 핸들러에서
+  계산하면 그 시간만큼 소유자가 다른 이벤트를 받지 못한다.
+
+## 원칙
+
+- **언어 안에서 푼다.** 작은 계산 하나를 위해 프로세스 경계나 다른 언어를 끌어오게 하지 않는다(005). 네이티브 모듈을 물리는
+  길(005의 3장)은 이 설계 밖이다.
+- **수명은 선언이 말한다.** 값이 어디에 얼마나 사는지를 런타임이 추측하지 않는다. 셋이다: 저장되는 상태, 앱이 도는 동안의
+  상태, 이벤트의 값.
+- **모든 이벤트는 끝난다.** 지금은 구조가 이것을 보장한다(반복이 리스트의 항목뿐이다). 수를 세는 반복이 들어오면 구조만으로는
+  묶이지 않는다(`for i in 0 .. 1e15`). 그래서 이제 **모든 앱이 실행량 예산과 메모리 한도를 가진다.** 호스트가 정하지 않으면
+  기본값이다. 예산은 명령 수와 바이트로 센다(017): 같은 앱과 입력이면 어느 기기에서나 같은 자리에서 같은 이유로 실패한다.
+- **읽는 계산은 보기에서, 쓰는 계산은 핸들러에서.** 상태를 바꾸지 않는 계산은 보기의 본문에 쓰고 스냅숏에서 돌린다(소유자를
+  막지 않는다). 결과를 저장해야 하면 보기로 계산하고 입력으로 넣는다. 핸들러의 계산은 원자적이고 소유자에서 돈다.
+- **지금의 앱은 그대로다.** 지금의 모듈은 바이트 그대로 같은 뜻이다. 새 것은 지금의 로더가 거절한다(모르는 명령, 모르는 상태
+  타입). 형식 이름(v6)은 그대로 둔다.
+
+## 모양
+
+### 수명 셋
+
+| | 실패한 이벤트 | 이벤트가 끝나면 | 저장소 | 다시 시작하면 | 모듈을 바꾸면 | 메모리 예산 |
+|---|---|---|---|---|---|---|
+| `state` | 되돌린다 | 남는다 | 쓴다 | 저장된 값 | 이름으로 잇는다 | 센다 |
+| `transient state` | 되돌린다 | 남는다 | **쓰지 않는다** | **초기값** | 이름으로 잇는다 | 센다 |
+| `let` (수, bool, i64, 인덱스, 리스트) | 버린다 | 버린다 | 없다 | — | — | 리스트는 자라는 대로 센다 |
+
+```text
+record Hit { path: text, count = 0 }
+record Seen { node = 0, depth = 0 }
+record Step { node = 0 }
+# nodes, edges(키: 출발 × 2^20 + 도착), tasks, reached는 이 앱의 다른 상태다
+
+state visits = 0                         # 저장한다(지금과 같다)
+transient state online = 0               # 앱이 도는 동안만: 저장하지 않고, 다시 시작하면 0
+transient state recent: list of Hit by path
+transient state picked: index of tasks   # 저장되는 리스트를 가리키는 저장되지 않는 선택
+
+on route {
+  let seen: list of Seen by node         # 이벤트의 리스트: 비어서 시작하고 이벤트가 끝나면 버린다
+  let queue: list of Step
+  queue.append(Step { node: route.from })
+  seen.add(Seen { node: route.from })
+  for i in 0 .. nodes.count {            # 수를 세는 반복: 0부터 nodes.count 앞까지
+    if i >= queue.count { break }        # 가장 안쪽 반복을 끝낸다
+    let q = queue.first + i
+    for e in edges[q.node * 1048576 .. q.node * 1048576 + 1048576] {   # 걷기 안의 걷기
+      if !seen.has(e.to) {
+        seen.add(Seen { node: e.to, depth: seen[q.node].depth + 1 })
+        queue.append(Step { node: e.to })
+      }
+    }
+  }
+  if seen.has(route.to) { reached = reached + 1 }
+}
+
+view distance(from: u32, to: u32) = {    # 보기의 본문(3단계): 스냅숏에서 돈다
+  let seen: list of Seen by node
+  ...
+  if seen.has(to) { seen[to].depth } else { -1 }   # 마지막 줄이 보기의 값
+}
+```
+
+- **`transient state`** 는 어떤 상태든 된다(수, bool, i64, text, 리스트, 커서, 인덱스). 저장되지 않는 text나 리스트를 가리키는
+  커서와 인덱스는 저장되지 않아야 한다(aup가 진단하고 Pure가 거절한다). 저장되는 것을 가리키는 transient 커서·인덱스는 된다
+  (위의 `picked`).
+- 모듈을 바꿀 때 저장되던 상태가 transient가 되면 그 값은 메모리에서 이어지고, 저장소의 옛 값은 모듈이 버린 상태의 값처럼
+  남는다(지금도 버린 상태는 지우지 않는다). 다시 저장되는 상태가 되면 그때 시작하는 앱은 저장소의 그 값을 받는다(버렸던
+  상태를 다시 들인 것과 같다). transient였던 것이 저장되는 상태가 되면 바꾸는 그 저장에서 지금의 값이 쓰인다.
+- **`let 이름: list of 레코드 [by 필드]`** 는 이벤트의 리스트다. 핸들러(3단계부터는 보기 본문)의 맨 바깥 블록에만 둔다. 저장되는
+  리스트가 하는 것을 모두 한다(`add`, `append`, `remove`, `[키]`, `has`, `count`, `first`, `last`, `+ n`, 집계, 걷기). 이벤트가
+  시작할 때 비어 있고, 끝나면(성공이든 실패든) 비워진다. 되돌리기를 기록하지 않는다.
+- **`for 이름 in 낮음 .. 높음 { }`** 은 이름을 낮음부터 높음 앞까지 1씩 올리며 블록을 돈다. 둘 다 수(정수여야 한다: 아니면
+  `limit`으로 실패, 2^53까지)이거나 둘 다 i64다. 이름은 읽기만 한다. 높음이 낮음 이하면 돌지 않는다.
+- **`break`** 는 가장 안쪽의 `for`(걷기든 세기든)를 끝낸다. 그 반복의 블록 안 어디서든(조건 안에서도) 쓴다.
+- **중첩.** `for` 안에 `for`를 쓴다(걷기와 세기 모두, 깊이 8까지). 바깥 걷기의 항목은 안쪽에서 읽는다. 안쪽 반복은 바깥 걷기가
+  도는 리스트에 넣거나 그 리스트에서 지우지 못한다(가장 안쪽 걷기는 지금처럼 자기 리스트에서 지울 수 있고 넣지 못한다).
+
+### Pure 모듈
+
+- **상태 타입 워드의 비트 8**: 저장하지 않는 상태. 나머지 비트는 지금 그대로(0–7 타입, 그 위 0). 저장층(텍스트 초안, 리스트의
+  이미지와 로그, 값 묶음)은 이 상태를 열지도 쓰지도 않는다. 되돌리기 기록은 그대로 한다.
+- **이벤트의 리스트**: 리스트의 플래그 256(지금의 "메시지의 행 목록")을 "이벤트의 리스트"로 넓힌다. 이름이 `입력.필드`이면
+  그 메시지 필드가 채우고, `let.이름`이면 코드만 채운다. 둘 다 이벤트가 끝나면 비워지고 저장되지 않고 되돌리기를 기록하지
+  않는다(지금의 행 목록 그대로). aup는 같은 이름의 `let` 리스트를 쓰는 핸들러들에게 슬롯 하나를 준다(레코드와 키가 같아야 한다).
+  상태는 지금처럼 모두 합쳐 32개까지다(이벤트의 리스트 포함).
+- **LOOP**: 인자는 지역 칸(비트 0–7), i64 여부(비트 8), 뒤따르는 블록의 길이(16–31). 낮음과 높음을 꺼내고, 블록을 돌 때마다
+  지역 칸에 지금의 값을 둔다.
+- **BREAK**: 가장 안쪽의 LOOP나 EACH 블록 안에서, 스택이 빈 자리에서만. 그 반복을 끝내고 반복 다음 명령으로 간다. 검증기는
+  블록 끝으로의 무조건 점프처럼 다룬다.
+- **EACH 안의 EACH와 LOOP.** 검증기는 바깥 걷기들이 도는 리스트의 집합을 들고 내려간다: 그 리스트에 넣거나 지우는 명령을
+  거절한다. 그래서 실행기는 지금처럼 가장 안쪽 걷기만 자리를 고친다. 바깥 걷기의 항목은 컴파일러가 안쪽 반복 앞에서 인덱스
+  지역 칸에 담는다(ROW → LOCAL_STORE). 깊이는 8까지다.
+
+### 실행량과 메모리
+
+- **기본 실행량 예산 2^28 명령**(268,435,456). `--work N`(앱마다 `work=N`)이 바꾼다. `pure_app_work(app, 0)`은 기본값이다.
+  "없음"은 없다.
+- LOOP는 **도는 대로** 센다(반복마다 블록 길이). `break`로 일찍 끝나는 반복이 쓰지 않을 몫으로 실패하지 않게 하려는 것이다.
+  EACH와 FOLD는 지금처럼 시작할 때 항목 수 × 블록 길이를 센다. 곱은 넘치지 않게 센다(넘치면 예산을 넘은 것이다).
+- **메모리는 자라는 대로 센다.** 이벤트가 리스트(저장되든 아니든, 이벤트의 리스트도)와 text에 더하는 바이트를 더할 때마다
+  센다. 예산이 있으면 이벤트가 시작할 때 가진 것 + 더한 것이 예산을 넘는 순간 `memory`로 실패한다(지금은 이벤트가 끝난 뒤에
+  본다). 예산이 없으면 한 이벤트가 더하는 것이 2^28 바이트(256 MiB)를 넘는 순간 실패한다. 그래서 고장 난 반복이 기기의
+  메모리를 다 쓰기 전에 멈춘다.
+- 보기의 평가(3단계의 본문 포함)도 같은 실행량 예산과 같은 2^28 바이트(이벤트의 리스트)를 쓴다.
+
+### 보기의 본문 (3단계)
+
+- `view 이름(인자…) = { 문장… 식 }`: 수, bool, i64, text 보기의 값을 블록으로 쓴다. 블록 안에 `let`(값과 리스트), `for`,
+  `break`, `if`, 걷기를 쓴다. 마지막 줄의 식이 값이다. 표 보기의 열과 필터는 지금처럼 식이다.
+- 본문은 상태를 바꾸지 못한다. 바꾸는 것은 지역 칸과 이벤트의 리스트뿐이다(검증기가 보기 안의 다른 효과를 거절한다).
+- 스냅숏을 읽는 쪽(`pure_app_read`)은 이벤트의 리스트를 자기 것으로 따로 가진다. 그래서 여러 연결 스레드가 같은 보기를 다른
+  인자로 동시에 평가한다. 소유자에서 평가하는 보기(`pure-run`, Vega의 호스트)는 평가가 끝나면 그 리스트를 비운다.
+- 보기를 미는 일(다음 작업, SSE)은 바뀔 때마다 보기를 다시 계산한다. 무거운 본문의 보기를 밀면 그만큼 든다. 그 설계에서 다룬다.
+
+## 단계
+
+1. **transient** (`transient state`). 사용자가 명시적으로 요청한 것이고 가장 작다.
+2. **핸들러의 계산.** 이벤트의 리스트, LOOP와 BREAK, 중첩, 기본 예산과 자라는 대로 세는 메모리.
+3. **보기의 본문.** 스냅숏에서 도는 계산.
+
+각 단계는 Pure의 형식 문서(008)와 aup의 문서(001의 표 "반복이 없고", 002)를 그 단계의 코드와 같은 커밋 단위에서 고친다.
+
+## 1단계의 착수 기준
+
+- **바꿀 결정:** aup에 `transient state`를 둘지. 아래를 채우지 못하면 모든 상태를 지금처럼 저장한다.
+- **최소 확인:**
+  - test-module: 저장하지 않는 상태(수, bool, i64, text, 리스트, 커서, 인덱스)가 다시 시작하면 초기값이고, 저장되는 상태는
+    그대로다. 실패한 이벤트는 transient도 되돌린다. 모듈 교체가 transient를 이름으로 잇는다. 저장되는 것과 transient가 서로
+    바뀌는 교체가 위의 규칙대로다. transient text나 리스트를 가리키는 저장되는 커서·인덱스를 가진 모듈은 거절된다.
+  - 저장소(`tests/check.py`의 `server_transient`): 같은 저장 이벤트열 사이에 transient만 바꾸는 이벤트를 섞어도, 끝난 뒤 저장소의
+    파일과 바이트가 섞지 않은 것과 같다. transient만 바꾸는 이벤트는 저장소에 아무것도 쓰지 않는다. `kill -9` 뒤에 다시 띄우면
+    transient는 초기값이다.
+  - aup: 진단(상태가 아닌 것의 transient, 저장되는 커서·인덱스가 transient를 가리킴)과 모듈의 바이트(transient가 없는 앱은 지금과
+    바이트가 같다).
+  - Pure, aup, Vega의 모든 검사가 초록이다.
+- **통과 조건:** 위의 검사가 전부다(실행 경로는 커밋이 값을 묶을 때 상태 하나의 비트를 보는 것뿐이다). pure-serve에서 transient만
+  바꾸는 쓰기와 저장하는 쓰기의 처리량을 RAM과 SD 카드에서 견주어 밝힌다(기준은 두지 않는다).
+
+## 2단계의 착수 기준
+
+- **바꿀 결정:** 핸들러에 이벤트의 리스트, 세는 반복, `break`, 중첩을 두고 모든 앱에 기본 예산을 둘지. 아래를 채우지 못하면
+  반복은 지금의 걷기로 남고, 무거운 계산은 앱 밖에 둔다.
+- **최소 확인:**
+  - test-module: LOOP(정수가 아닌 경계, 빈 범위, 음수, i64, 2^53 근처), 여러 깊이의 BREAK, 걷기 안에서 지우는 중첩 걷기, 검증기의
+    거절(바깥 걷기의 리스트에 넣기와 지우기, 반복 밖의 BREAK, 스택이 빈 자리가 아닌 BREAK, 깊이 9, 이벤트의 리스트가 아닌
+    `let.` 이름). 실행량: LOOP가 도는 대로 세고, 곱이 넘치는 시작이 `work`로 실패한다. 메모리: 이벤트의 리스트나 text가
+    예산(그리고 예산 없이 2^28 바이트)을 넘는 순간 `memory`로 실패하고 아무것도 바뀌지 않는다.
+  - 알고리즘을 모델과 대조한다(aup로 컴파일해 `pure-run`과 `pure-serve`에서): 무작위 그래프 20개의 BFS 거리, DFS(스택)의 방문
+    순서, 가중치 있는 그래프의 다익스트라, 뉴턴 반복의 제곱근(Python에서 같은 연산 순서로 계산한 binary64와 비트까지 같다),
+    배낭 문제의 동적 계획법.
+  - 고장 난 반복(`for i in 0 .. 1e15 { xs.append(…) }`)이 예산 없이 띄운 호스트에서 `work`나 `memory`로 끝나고, 그동안 호스트의
+    RSS가 300 MiB 넘게 늘지 않는다(`research/guard.py` 아래에서).
+  - 새 예제의 `pure-run` 출력과 모듈 바이트가 Pi, WSL2 x86_64, M3 Mac에서 같다(029의 방법).
+  - 기본 예산으로 Pure, aup, Vega의 모든 검사가 초록이다.
+- **통과 조건**(RAM의 Pi 5):
+  - 지금의 앱: TPC-C(W=1, 64터미널)와 은행 질의를 전과 후 번갈아 여섯 쌍 재서 중앙값이 3% 넘게 느려지지 않고, 은행 질의의 명령
+    수(110의 `count.py`)가 1% 넘게 늘지 않는다.
+  - 노드 10만 개, 간선 100만 개의 그래프에서 한 이벤트의 BFS가 기본 예산 안에 든다. 그 시간을 같은 그래프의 C와 CPython BFS와
+    견주어 밝힌다(기준은 두지 않는다: 바이트코드 실행기가 네이티브보다 느린 것은 005의 3장이 이미 말한다).
+
+## 3단계의 착수 기준
+
+- **바꿀 결정:** 보기에 본문을 둘지. 아래를 채우지 못하면 읽는 계산도 핸들러에서 한다.
+- **최소 확인:**
+  - 같은 상태에서 보기 본문의 BFS가 2단계 핸들러의 BFS와 같은 답을 낸다. 64연결이 무작위 인자로 동시에 물어도 모든 답이 모델과
+    같다(읽는 쪽마다 이벤트의 리스트가 따로다).
+  - 검증기가 보기 본문의 효과(상태 쓰기, 이벤트의 리스트가 아닌 리스트에 넣기, SEND, REPLY)를 거절한다. 평가마다 이벤트의
+    리스트가 비어서 시작한다(`pure-run`과 Vega의 호스트처럼 소유자에서 평가할 때도).
+  - 실행량과 메모리 한도를 넘는 보기는 `work`·`memory`로 답하고 상태는 그대로다.
+- **통과 조건**(RAM의 Pi 5):
+  - 소유자를 막지 않는다: 한 앱에 쓰기(16연결)를 보내는 동안 다른 연결 둘이 BFS 보기를 쉬지 않고 물어도, 쓰기 처리량의 중앙값이
+    보기를 묻지 않을 때의 95% 이상이다.
+  - 연결 스레드 둘에서 BFS 보기의 처리량이 하나일 때의 1.6배 이상이다.
+
+## 하지 않는 것
+
+- `while`과 재귀. 모든 반복은 시작할 때 횟수의 상한이 정해진다(세기의 범위, 걷기의 항목 수). 끝을 모르는 반복은 상한을 적은
+  세기와 `break`로 쓴다.
+- 걷는 동안 자라는 리스트를 따라가는 걷기(BFS의 큐를 그대로 걷기). 위치로 읽는 세기(`queue.first + i`)로 쓴다. 필요하다는 측정이
+  나오면 따로 잰다.
+- 문장을 가진 `fn`. `fn`은 지금처럼 식이다. 같은 계산을 여러 곳에서 쓰는 필요가 나오면 다시 본다.
+- JIT, SIMD, 네이티브 모듈. 실행기의 속도는 측정으로 따로 다룬다.
+- 반복 중의 선점. 이벤트는 끝까지 돈다. 길이는 실행량 예산이 묶는다(017).