From db28e3401e5a137845fdb1661e1af6297477b0c8 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Sat, 26 Sep 2026 11:23:07 +0100 Subject: Add count, sum, max and min over a list count(t in tasks where !t.done), sum(t.points for t in tasks), and max and min in the same form compile to Pure's FOLD: the value and the where condition become a block run once per item, as a column of the list, so views count and add without a copy of the list or a state kept in step. max(a, b), min(a, b) and fns of the same names stay calls, told apart by the `for` after the first expression or the `name in` after count(. Inside the block only its item and states can be read; a parameter of the fn outside, the enclosing column's row, dt and a fold inside a fold are compile errors that say why. The checks run 3,600 random steps against a Python model and add seven diagnostics. --- docs/design/002-dsl-direction.md | 21 +++++++ src/compile.c | 127 +++++++++++++++++++++++++++++++++++++-- tests/check.py | 86 ++++++++++++++++++++++++++ 3 files changed, 229 insertions(+), 5 deletions(-) diff --git a/docs/design/002-dsl-direction.md b/docs/design/002-dsl-direction.md index 3692866..9d695f9 100644 --- a/docs/design/002-dsl-direction.md +++ b/docs/design/002-dsl-direction.md @@ -152,6 +152,27 @@ view board = each task in tasks { # 항목마다 한 행 검증: 표 열과 조건 보기를 더한 할 일 목록이 참조 모델과 4,800단계에서 같고, 고르지 않은 가지가 계산되지 않음을 확인한다. 7단계 중첩은 컴파일되고 Pure가 받아들이며, 8단계는 aup가 거부한다(Pure도 거부하는 깊이). 진단 16건을 더했다. +### 집계: count, sum, max, min + +```text +view open = count(t in tasks where !t.done) +view points = sum(t.points for t in tasks) +view best = max(p.score for p in players where p.active) +view summary = "{count(t in tasks where !t.done)} open of {tasks.count}" +``` + +- **모양.** `count(항목 in 리스트 [where 조건])`, `sum|max|min(값 for 항목 in 리스트 [where 조건])`. 값을 둘 받는 + `max(a, b)`·`min(a, b)`는 그대로 호출이고, 같은 이름의 fn(`fn sum(a, b)`)도 그대로 부를 수 있다. 첫 식 뒤의 + `for`, 또는 `count(`의 `이름 in`으로 가른다. +- **의미.** 항목마다 블록을 계산해 센다(조건이 참인 항목), 더한다, 가장 큰·작은 값을 고른다. 포함된 항목이 없으면 + count·sum은 0이고 max·min은 값이 없다(보기는 비고, 핸들러는 `not_found`로 실패). +- **블록은 표의 열처럼 돈다.** Pure의 FOLD가 뒤따르는 블록을 항목마다 열로 실행한다. 블록은 자기 항목과 상태만 + 읽는다. 바깥 fn의 매개변수, 둘러싼 열의 행, `dt`, 메시지 필드는 쓸 수 없다(쓰면 컴파일 오류로 이유를 알린다). + 집계 안에 집계는 없다. 그래서 비용은 블록 길이 × 항목 수로 한정되고, 목록의 사본이나 집계용 상태가 필요 없다. + +검증: 무작위 추가·토글·이동·삭제 3,600단계에서 네 집계(조건 있는 것 포함, 빈 max·min, 보간 안의 집계)가 파이썬 +참조 모델과 같다. 진단 7건(중첩, 리스트 아님, text 합, 열의 행, 바깥 매개변수, `dt`, `in` 누락)을 더했다. + ### 구현된 fn과 use (v0c-3) ```text diff --git a/src/compile.c b/src/compile.c index 234991f..0c90e18 100644 --- a/src/compile.c +++ b/src/compile.c @@ -17,7 +17,8 @@ enum { CONST, LOAD, DT, ADD, SUB, MUL, DIV, NEG, LT, LE, GT, GE, EQ, NE, AND, OR CUR_LOAD, CUR_START, CUR_END, CUR_MOVE, CUR_STORE, TEXT_INSERT, TEXT_REMOVE, TEXT_LINE, TEXT_SET, TEXT_FROM, BYTES_FROM, CUR_COUNT, LIST_COUNT, LIST_APPEND, LIST_INSERT, LIST_REMOVE, ITEM_GET, ITEM_SET, INDEX_LOAD, INDEX_STORE, INDEX_MOVE, INDEX_FIRST, INDEX_LAST, INDEX_NUM, ROW, - PICK, SLIDE }; + PICK, SLIDE, FOLD }; +enum { FOLD_COUNT, FOLD_SUM, FOLD_MAX, FOLD_MIN }; enum { KIND_KEY = 1, KIND_MESSAGE = 2, KIND_TEXT = 3, FIELD_U32 = 1, FIELD_BYTES = 2 }; enum { STATE_NUM = 0, STATE_TEXT = 1, STATE_CURSOR = 2, STATE_LIST = 3, STATE_INDEX = 4, UNIT_CHAR = 0, UNIT_LINE = 1 }; typedef enum { NUM = 1, BYTES, TEXT, CURSOR, UNIT, INDEX } Type; @@ -46,6 +47,7 @@ typedef enum { E_RECORD, /* name { fields }: E_FIELD nodes linked from args[0] */ E_FIELD, /* member: args[0] */ E_IF, /* if args[0] { args[1] } else { args[2] } */ + E_FOLD, /* op(args[1] for name in member where args[0]): count (no value), sum, max, min */ } ExprKind; typedef struct Expr { ExprKind kind; @@ -140,6 +142,12 @@ typedef struct { /* Code generation. */ int message; /* message or text input of the handler being generated, or -1 */ int row; /* the table whose column is being generated, or -1 */ + /* The fold whose block is being generated: its item's name and list, and + * the fn scope it began in (whose parameters its block cannot read). */ + bool folding; + char fold_name[NAME]; + int fold_list; + Scope *fold_scope; /* Libraries: module 0 is the main source; each module lists the libraries it uses. */ struct { char name[NAME], path[AUP_PATH]; bool uses[MODULES], parsing; } modules[MODULES]; unsigned module_count; @@ -383,8 +391,8 @@ static void index_key(Compiler *c) { } /* (a, b, ...) after a fn name. */ -static Expr *arguments(Compiler *c, Expr *call) { - expect(c, "(", "'('"); +/* Arguments once the opening parenthesis is taken. */ +static Expr *arguments_after(Compiler *c, Expr *call) { newlines(c); while (!is(c, ")")) { if (call->count == PARAMS) fail_at(c, c->token.line, c->token.column, "a call takes at most 8 arguments"); @@ -398,6 +406,11 @@ static Expr *arguments(Compiler *c, Expr *call) { return call; } +static Expr *arguments(Compiler *c, Expr *call) { + expect(c, "(", "'('"); + return arguments_after(c, call); +} + static Expr *postfix(Compiler *c, Expr *e) { const Token *next = is(c, "[") ? lookahead(c) : NULL; if (e->kind == E_NAME && next && next->kind == T_NAME && !strcmp(next->text, "key")) { @@ -575,6 +588,30 @@ static Expr *conditional(Compiler *c, const Token *token) { return e; } +/* The rest of a fold, after its value (none for count): for item in list, + * then an optional where condition, then ')'. */ +static Expr *fold(Compiler *c, const Token *name, int how, Expr *value) { + Expr *e = node(c, E_FOLD, name->line, name->column); + e->op = how; + Token item = expect_name(c, "a name for each item"); + memcpy(e->name, item.text, NAME); + newlines(c); + if (!word(c, "in")) fail_at(c, c->token.line, c->token.column, "expected 'in' and a list, as in %s(%s in tasks)", + name->text, item.text); + take(c); + Token list = expect_name(c, "a list"); + memcpy(e->member, list.text, NAME); + newlines(c); + e->args[1] = value; + if (word(c, "where")) { + take(c); + e->args[0] = expression(c, 0, true); + newlines(c); + } + expect(c, ")", "')'"); + return e; +} + static Expr *expression(Compiler *c, int minimum, bool multiline) { if (++c->depth > DEPTH) fail_at(c, c->token.line, c->token.column, "expression nesting exceeds 64"); if (multiline) newlines(c); @@ -597,13 +634,53 @@ static Expr *expression(Compiler *c, int minimum, bool multiline) { } else if (token.kind == T_NAME) { static const struct { const char *name; unsigned count; int op; } calls[] = {{"min", 2, MIN}, {"max", 2, MAX}, {"clamp", 3, CLAMP}, {"text", 1, TEXT_FROM}, {"bytes", 1, BYTES_FROM}}; - int call = -1; + int call = -1, how = -1; for (int i = 0; i < 5; ++i) if (!strcmp(token.text, calls[i].name)) call = i; - if (call >= 0 && is(c, "(")) { + static const char *const folds[] = {"count", "sum", "max", "min"}; + for (int i = 0; i < 4; ++i) if (!strcmp(token.text, folds[i])) how = i; + Expr *first = NULL; + /* count(t in tasks ...), sum(t.x for t in tasks ...): folds; max(a, b) stays a call. */ + if (how >= 0 && is(c, "(")) { take(c); + newlines(c); + if (how == FOLD_COUNT && c->token.kind == T_NAME && lookahead(c)->kind == T_NAME && + !strcmp(lookahead(c)->text, "in")) { + left = fold(c, &token, how, NULL); + goto parsed; + } + if (how != FOLD_COUNT) { + first = expression(c, 0, true); + newlines(c); + if (word(c, "for")) { + take(c); + left = fold(c, &token, how, first); + goto parsed; + } + } + if (call < 0) { + /* A fn of that name. */ + if (reserved_name(token.text)) fail_at(c, token.line, token.column, "expected a number, state, or expression"); + left = node(c, E_FN, token.line, token.column); + memcpy(left->name, token.text, NAME); + if (first) { + left->args[left->count++] = first; + if (is(c, ",")) take(c); + else if (!is(c, ")")) fail_at(c, c->token.line, c->token.column, "expected ',' or ')'"); + } + left = postfix(c, arguments_after(c, left)); + goto parsed; + } + } + if (call >= 0 && (first || is(c, "("))) { + if (!first) take(c); left = node(c, call >= 3 ? E_CONVERT : E_CALL, token.line, token.column); left->op = calls[call].op; newlines(c); + if (first) { + left->args[left->count++] = first; + if (is(c, ",")) { take(c); newlines(c); } + else if (!is(c, ")")) fail_at(c, c->token.line, c->token.column, "expected ',' or ')'"); + } while (!is(c, ")")) { if (left->count == 3) fail_at(c, token.line, token.column, "%s expects %u arguments", token.text, calls[call].count); left->args[left->count++] = expression(c, 0, true); @@ -628,6 +705,7 @@ static Expr *expression(Compiler *c, int minimum, bool multiline) { left = postfix(c, left); } } else fail_at(c, token.line, token.column, "expected a number, state, or expression"); +parsed: /* 1 char, n line: a distance that moves a cursor. */ if (word(c, "char") || word(c, "line")) { Token unit = take(c); @@ -1375,6 +1453,7 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) { switch (e->kind) { case E_NUMBER: emit(c, e->line, e->column, CONST, 0, e->number); return (Kind){NUM, -1}; case E_DT: + if (c->folding) fail_at(c, e->line, e->column, "dt is not available in count, sum, max or min"); if (!handler) fail_at(c, e->line, e->column, "dt is only available in handlers"); emit(c, e->line, e->column, DT, 0, 0); return (Kind){NUM, -1}; @@ -1391,7 +1470,14 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) { return (Kind){TEXT, -1}; } case E_NAME: { + if (c->folding && c->scope == c->fold_scope && !strcmp(e->name, c->fold_name)) { + emit(c, e->line, e->column, ROW, (uint32_t)c->fold_list, 0); /* the item a fold's block runs for */ + return (Kind){INDEX, c->fold_list}; + } int param = parameter(c, e->name); + if (param >= 0 && c->folding && c->scope == c->fold_scope) + fail_at(c, e->line, e->column, + "'%s' is a parameter outside this count, sum, max or min; its block reads only its item and states", e->name); if (param >= 0) { emit(c, e->line, e->column, PICK, (uint32_t)(height - 1 - (c->scope->base + param)), 0); return c->scope->kinds[param]; @@ -1399,6 +1485,8 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) { if (fn_index(c, c->module, e->name) >= 0) return inline_fn(c, e, c->module, e->name, handler, height); if (c->module) fail_at(c, e->line, e->column, "'%s' is not a parameter; a library fn reads only its parameters", e->name); if (!c->scope && c->row >= 0 && !strcmp(e->name, c->view_row[c->row])) { + if (c->folding) + fail_at(c, e->line, e->column, "'%s' is the column's row; a count, sum, max or min reads only its own item", e->name); int list = state_index(c, c->view_list[c->row]); emit(c, e->line, e->column, ROW, (uint32_t)list, 0); return (Kind){INDEX, list}; @@ -1555,6 +1643,33 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) { c->joins = saved; return kind; } + case E_FOLD: { + /* The block after FOLD runs once per item, as a column of the list: it + * starts with an empty stack and reads only its item and states. */ + app_name(c, e, e->member); + int list = state_index(c, e->member); + if (list < 0 || c->state_types[list] != STATE_LIST) fail_at(c, e->line, e->column, "'%s' is not a list", e->member); + if (c->folding) fail_at(c, e->line, e->column, "a count, sum, max or min cannot hold another"); + unsigned at = c->code_count, joins = c->joins; + emit(c, e->line, e->column, FOLD, 0, 0); + c->folding = true; + c->fold_list = list; + c->fold_scope = c->scope; + memcpy(c->fold_name, e->name, NAME); + c->joins = 0; + if (e->op != FOLD_COUNT) { + Kind kind = value(c, e->args[1], false, 0); + if (kind.type != NUM) + fail_at(c, e->args[1]->line, e->args[1]->column, "sum, max and min take numbers, not %s", type_name(kind.type)); + } + if (e->args[0]) number(c, e->args[0], false, e->op != FOLD_COUNT); + else emit(c, e->line, e->column, CONST, 0, 1); + c->folding = false; + c->fold_list = -1; + c->joins = joins; + c->code[at].arg = (uint32_t)e->op | (uint32_t)list << 8 | (uint32_t)(c->code_count - at - 1) << 16; + return (Kind){NUM, -1}; + } case E_RECORD: case E_FIELD: fail_at(c, e->line, e->column, "a record value goes into a list, as in list.append(%s { ... })", e->name); case E_UNIT: @@ -1817,6 +1932,7 @@ static void generate(Compiler *c, unsigned char **module, size_t *size) { c->view_code[i][1] = c->code_count - c->view_code[i][0]; } c->row = -1; + c->fold_list = -1; for (unsigned i = 0; i < c->handler_count; ++i) { int input = handler_input[i]; c->message = input >= 0 && c->inputs[input].kind != KIND_KEY ? input : -1; @@ -1936,6 +2052,7 @@ bool aup_compile(const char *source, size_t length, AupLoad load, void *context, c->line = c->column = 1; c->error = error; c->row = -1; + c->fold_list = -1; c->load = load; c->load_context = context; c->module_count = 1; /* the main source */ diff --git a/tests/check.py b/tests/check.py index 7f94235..ef8549f 100644 --- a/tests/check.py +++ b/tests/check.py @@ -166,9 +166,21 @@ DIAGNOSTICS = [ ('state n = 0\nview v = n(1)\n', '2:10', "'n' is a state, not a fn"), ('use missing\n', '1:5', "cannot find library 'missing' (missing.aup)"), ('view v = shapes.area(1, 2)\n', '1:17', "unknown library 'shapes'; write use shapes first"), + (LIST + 'view v = count(x in xs where count(y in xs) > 0)\n', '6:30', 'a count, sum, max or min cannot hold another'), + (LIST + 'view v = count(x in at)\n', '6:10', "'at' is not a list"), + ('record T {\n t: text\n}\nstate xs: list of T\nview v = sum(x.t for x in xs)\n', '5:14', + 'sum, max and min take numbers, not text'), + (LIST + 'view w = each r in xs {\n n = count(x in xs where x.a == r.a)\n}\n', '7:34', + "'r' is the column's row; a count, sum, max or min reads only its own item"), + (LIST + 'fn f(n) = count(x in xs where x.a == n)\nview v = f(1)\n', '6:38', + "'n' is a parameter outside this count, sum, max or min"), + (LIST + 'view v = sum(dt for x in xs)\n', '6:14', 'dt is not available in count, sum, max or min'), + (LIST + 'view v = sum(x.a for x xs)\n', '6:24', "expected 'in' and a list, as in sum(x in tasks)"), ] ACCEPTED = [ + # fns named like folds stay calls, and max of two values stays max + 'fn sum(a, b) = a + b\nfn count(x) = x\nview v = sum(1, count(2)) + max(3, 4) + min(\n 5,\n 6\n)\n', # else on the next line, else if chains, multiline arguments, semicolons. 'state a = 0\non frame {\n if a > 1 {\n a = 1\n }\n else {\n a = 2\n }\n}\n', 'state a = 0; state b = 1\nview v = clamp(\n a,\n 0,\n b\n)\non frame { a = a + 1; b = b + 2 }\n', @@ -948,6 +960,79 @@ def server_bursts(aup, pure, work, clients=8, edits=30, shards=1): 'acknowledged_before_kill': sum(count for count, _ in acknowledged) - clients * edits} +FOLDS_SOURCE = """record Task { + title: text + done = 0 + points = 0 +} +state tasks: list of Task +state at: index of tasks +input add = text +input toggle = key Space +input up = key ArrowUp +input down = key ArrowDown +input drop = key Delete +on add { + tasks.append(Task { title: add, points: add.chars }) + at = tasks.last +} +on toggle.down { at.done = !at.done } +on up.down { at = at - 1 } +on down.down { at = at + 1 } +on drop.down { tasks.remove(at) } +view open = count(t in tasks where !t.done) +view points = sum(t.points for t in tasks) +view done_points = sum( + t.points for t in tasks + where t.done +) +view longest = max(t.title.chars for t in tasks) +view fewest_open = min(t.points for t in tasks where !t.done) +view summary = "{count(t in tasks where !t.done)} open of {tasks.count}" +""" + + +def folds(aup, pure_run, work, seeds, steps=300): + """count, sum, max and min over a list against a Python model after + random adds, toggles, moves and removals (an empty max or min has no + value).""" + source = work / 'folds.aup' + source.write_text(FOLDS_SOURCE) + compile_module(aup, source, work / 'folds.pmod') + words = ['a', 'bbb', '가나', '😀', '', 'x y z', '\n'] + compared = 0 + for seed in seeds: + rng, tasks, at, commands, expected = random.Random(seed + 4200), [], 0, [], [] + for _ in range(steps): + roll = rng.random() + if roll < 0.35: + word = rng.choice(words) + commands.append('type add ' + (word.encode().hex() or '-')) + tasks.append({'title': word, 'done': 0, 'points': len(word)}) + at = len(tasks) - 1 + else: + name = rng.choice(['toggle', 'up', 'down', 'drop']) + commands.append(f'down {name}') + if name == 'up': at = max(at - 1, 0) + elif name == 'down': at = min(at + 1, max(len(tasks) - 1, 0)) + elif tasks and name == 'toggle': tasks[at]['done'] = int(not tasks[at]['done']) + elif tasks and name == 'drop': + del tasks[at] + at = min(at, max(len(tasks) - 1, 0)) + open_tasks = [t for t in tasks if not t['done']] + expected.append({'open': len(open_tasks), 'points': sum(t['points'] for t in tasks), + 'done_points': sum(t['points'] for t in tasks if t['done']), + 'longest': max((len(t['title']) for t in tasks), default=None), + 'fewest_open': min((t['points'] for t in open_tasks), default=None), + 'summary': f'{len(open_tasks)} open of {len(tasks)}'}) + # Toggling or removing in an empty list fails; pure-run then exits 1 but shows every event. + lines = run(pure_run, work / 'folds.pmod', stdin='\n'.join(commands) + '\n', check=False).stdout.splitlines() + shown = [json.loads(line)['views'] for line in lines] + assert shown == expected, (seed, [(a, b) for a, b in zip(shown, expected) if a != b][:2]) + compared += len(shown) + return compared + + def conditionals(aup, pure_run, work): """Only the chosen branch runs (10 / x is never computed at x = 0), else-if chains pick the first true arm, and conditionals nest inside arithmetic.""" @@ -1076,6 +1161,7 @@ def main(): report['list_model_snapshots'], report['list_model_failed_events'] = \ tasks_parity(aup, pure_run, work, range(args.text_seeds)) report['conditional_snapshots'] = conditionals(aup, pure_run, work) + report['fold_snapshots'] = folds(aup, pure_run, work, range(args.seeds if hasattr(args, 'seeds') else 8)) report['stored_snapshots'], report['stored_restarts'] = stored_runs(aup, pure_run, work, range(args.text_seeds)) report['library_programs'], report['library_diagnostics'] = libraries(aup, pure_run, work) report['editor_parity_operations'], report['editor_parity_outcomes'] = \ -- cgit v1.2.3