Grammar as a Service — contract cgt-gaas/0.1
A request names a versioned grammar (or an algorithm with declared capabilities), an operation expression, and limits; the response carries values, a layered rejection if any (syntax · semantics · execution), a cost report and provenance hashes. The reference implementation is a pure function you can call in-process — no account, key or network is needed for anything in the curriculum. Design rationale: the GaaS chapter.
Structures
| Name | Version | Description | Moves |
|---|---|---|---|
array | 1 | dynamic array | append(x) delete(i) get(i) insert(i, x) len pop set(i, x) |
linked_list | 1 | singly linked list | delete(i) get(i) insert(i, x) len pop_front push_front(x) set(i, x) |
stack | 1 | array-backed stack | empty pop push(x) top |
queue | 1 | circular queue | dequeue enqueue(x) front len |
deque | 1 | circular deque | len pop_back pop_front push_back(x) push_front(x) |
hash_table | 1 | open addressing, linear probing | contains(k) delete(k) get(k) len put(k, v) |
heap | 1 | binary min-heap | len peek pop_min push(x) |
trie | 1 | character trie | contains(w) count_prefix(p) insert(w) |
bst | 1 | BST / AVL | contains(k) delete(k) insert(k) min |
binary_tree | 1 | complete binary tree, pointer or heap representation | L R U goto(addr) here read root |
graph | 1 | edge-labelled digraph, relational semantics | edge labels + at(v), here |
Algorithms
| Name | Exactness | Declared cost | Description |
|---|---|---|---|
pagerank | approximate (certified bound) | O(k·(n+m)), k ≤ log(tol)/log(α) iterations | PageRank by power iteration; approximate with certified L1 error bound |
constrained_pagerank | approximate (certified bound) | O(k·|Q|·(n+m)) | grammar-constrained random surfer (CGT proposal) |
reach | exact | O(n+m), or O(|Q|(|Σ|n+m)) with a language | reachability, optionally language-constrained (THM-001) |
sssp | exact | O((n+m) log n) | Dijkstra single-source shortest paths |
scc | exact | O(n+m) | Tarjan strongly connected components |
Hard limits
max_calls≤ 10000max_cost≤ 5000000max_output_items≤ 100000timeout_ms≤ 5000max_n≤ 200000
A request may lower any limit and never raise one.
Example
{
"contract": "cgt-gaas/0.1",
"grammar": {
"structure": "array",
"version": "1"
},
"init": {
"values": [
5,
3,
8
]
},
"expression": "get(2); set(0, 9); get(0)"
}{
"contract": "cgt-gaas/0.1",
"status": "ok",
"exact": true,
"values": [
8,
null,
9
],
"cost": {
"total": 9,
"counts": {
"arith": 3,
"compare": 3,
"read": 2,
"write": 1
}
},
"provenance": {
"sdk": "0.1.0",
"request_sha256": "43fea76542d15e22df05f6b1f750939b1b72d3f5444e1185e9049afec390e0c9",
"result_sha256": "841664233f6c8d98809381bb52f967b1e22289a050a1be3c8a9d1826cced3f33",
"deterministic": true
}
}