Skip to main content

clm_rust_core/layer1/
bisimulation_ast.rs

1use std::collections::BTreeMap;
2
3/// Deterministic MCard tape store mapping handles to canonical numeric tokens.
4pub type Store = BTreeMap<String, String>;
5
6/// Canonical numeric representation across finite i64, NaN, signed zero, and 64-bit overflow.
7#[derive(Clone, Debug, PartialEq, Eq)]
8pub enum CanonNum {
9    Finite(i64),
10    Nan,
11    SignedZero(bool),
12    OverflowI64,
13}
14
15impl CanonNum {
16    /// Format canonical numeric token.
17    pub fn token(&self) -> String {
18        match self {
19            Self::Nan => "NAN".into(),
20            Self::OverflowI64 => "OVERFLOW_I64".into(),
21            Self::SignedZero(neg) => format!("SIGNED_ZERO:{}0", if *neg { "-" } else { "+" }),
22            Self::Finite(val) => format!("FINITE_I64:{}", val),
23        }
24    }
25}
26
27/// Single small-step coalgebra transition over AST and tape store.
28pub enum Step {
29    Ret(String),
30    Tau(serde_json::Value, Store),
31    Vis(String, serde_json::Value, Store),
32}
33
34pub(crate) fn encode_num_val(raw: &serde_json::Value) -> Result<CanonNum, String> {
35    if let Some(i) = raw.as_i64() {
36        return Ok(if i == 0 {
37            CanonNum::SignedZero(false)
38        } else {
39            CanonNum::Finite(i)
40        });
41    }
42    if raw.as_u64().is_some() {
43        return Ok(CanonNum::OverflowI64);
44    }
45    if let Some(f) = raw.as_f64() {
46        if f.is_nan() {
47            return Ok(CanonNum::Nan);
48        }
49        if f.is_infinite() || f.fract() != 0.0 {
50            return Ok(CanonNum::OverflowI64);
51        }
52        if f == 0.0 {
53            return Ok(CanonNum::SignedZero(f.is_sign_negative()));
54        }
55        if f >= (i64::MIN as f64) && f < 9223372036854775808.0 {
56            return Ok(CanonNum::Finite(f as i64));
57        }
58        return Ok(CanonNum::OverflowI64);
59    }
60    if let Some(raw_str) = raw.as_str() {
61        let trimmed = raw_str.trim();
62        if trimmed.eq_ignore_ascii_case("NAN") {
63            return Ok(CanonNum::Nan);
64        }
65        if trimmed == "OVERFLOW_I64" {
66            return Ok(CanonNum::OverflowI64);
67        }
68        if matches!(trimmed, "SIGNED_ZERO:+0" | "+0" | "+0.0" | "0" | "0.0") {
69            return Ok(CanonNum::SignedZero(false));
70        }
71        if matches!(trimmed, "SIGNED_ZERO:-0" | "-0" | "-0.0") {
72            return Ok(CanonNum::SignedZero(true));
73        }
74        let body = trimmed.strip_prefix("FINITE_I64:").unwrap_or(trimmed);
75        let digits = body
76            .strip_prefix('+')
77            .or_else(|| body.strip_prefix('-'))
78            .unwrap_or(body);
79        if !digits.is_empty() && digits.bytes().all(|b| b.is_ascii_digit()) {
80            return Ok(match body.parse::<i64>() {
81                Ok(0) => CanonNum::SignedZero(body.starts_with('-')),
82                Ok(val) => CanonNum::Finite(val),
83                Err(_) => CanonNum::OverflowI64,
84            });
85        }
86    }
87    Err(format!("Unsupported numeric literal: {}", raw))
88}
89
90pub(crate) fn apply_num_op(op: &str, left: &CanonNum, right: &CanonNum) -> CanonNum {
91    if matches!(left, CanonNum::Nan) || matches!(right, CanonNum::Nan) {
92        return CanonNum::Nan;
93    }
94    if matches!(left, CanonNum::OverflowI64) || matches!(right, CanonNum::OverflowI64) {
95        return CanonNum::OverflowI64;
96    }
97    let lv = if let CanonNum::Finite(v) = left { *v } else { 0 };
98    let rv = if let CanonNum::Finite(v) = right { *v } else { 0 };
99    if op == "add" || op == "sub" {
100        if let (CanonNum::SignedZero(ln), CanonNum::SignedZero(rn)) = (left, right) {
101            let neg = if op == "add" { *ln && *rn } else { *ln && !*rn };
102            return CanonNum::SignedZero(neg);
103        }
104        let checked = if op == "add" {
105            lv.checked_add(rv)
106        } else {
107            lv.checked_sub(rv)
108        };
109        return match checked {
110            None => CanonNum::OverflowI64,
111            Some(0) => CanonNum::SignedZero(false),
112            Some(val) => CanonNum::Finite(val),
113        };
114    }
115    let ln = match left {
116        CanonNum::SignedZero(neg) => *neg,
117        CanonNum::Finite(val) => *val < 0,
118        _ => false,
119    };
120    let rn = match right {
121        CanonNum::SignedZero(neg) => *neg,
122        CanonNum::Finite(val) => *val < 0,
123        _ => false,
124    };
125    match lv.checked_mul(rv) {
126        None => CanonNum::OverflowI64,
127        Some(0) => CanonNum::SignedZero(ln != rn),
128        Some(val) => CanonNum::Finite(val),
129    }
130}
131
132pub(crate) fn preserve_json_numeric_tokens(raw: &str) -> String {
133    let bytes = raw.as_bytes();
134    let mut out = String::with_capacity(raw.len() + 16);
135    let mut idx = 0;
136    let mut in_string = false;
137    let mut escaped = false;
138    while idx < bytes.len() {
139        let ch = bytes[idx] as char;
140        if in_string {
141            out.push(ch);
142            if escaped {
143                escaped = false;
144            } else if ch == '\\' {
145                escaped = true;
146            } else if ch == '"' {
147                in_string = false;
148            }
149            idx += 1;
150            continue;
151        }
152        if ch == '"' {
153            in_string = true;
154            out.push(ch);
155            idx += 1;
156            continue;
157        }
158        let prev_ok = idx == 0
159            || matches!(
160                bytes[idx - 1],
161                b':' | b',' | b'[' | b' ' | b'\n' | b'\t' | b'\r'
162            );
163        if (ch == '-' || ch.is_ascii_digit()) && prev_ok {
164            let start = idx;
165            idx += 1;
166            while idx < bytes.len() && (bytes[idx].is_ascii_digit() || bytes[idx] == b'.') {
167                idx += 1;
168            }
169            let tok = &raw[start..idx];
170            if tok.starts_with("-0") || tok.trim_start_matches('-').len() >= 15 {
171                out.push('"');
172                out.push_str(tok);
173                out.push('"');
174            } else {
175                out.push_str(tok);
176            }
177            continue;
178        }
179        out.push(ch);
180        idx += 1;
181    }
182    out
183}
184
185pub(crate) fn mk_obj(mut pairs: Vec<(&str, serde_json::Value)>) -> serde_json::Value {
186    pairs.sort_by(|a, b| a.0.cmp(b.0));
187    let mut map = serde_json::Map::new();
188    for (key, val) in pairs {
189        map.insert(key.to_string(), val);
190    }
191    serde_json::Value::Object(map)
192}
193
194fn bin_keys(tag: &str) -> Option<(&'static str, &'static str)> {
195    match tag {
196        "Add" | "Sub" | "Mul" => Some(("left", "right")),
197        "App" => Some(("fn", "arg")),
198        "Seq" => Some(("first", "second")),
199        _ => None,
200    }
201}
202
203pub(crate) fn canon_ast(raw: &serde_json::Value) -> Result<serde_json::Value, String> {
204    let tag = raw
205        .get("tag")
206        .and_then(|v| v.as_str())
207        .ok_or("Missing AST tag")?;
208    if let Some((lk, rk)) = bin_keys(tag) {
209        let lhs = canon_ast(raw.get(lk).ok_or("Missing lhs")?)?;
210        let rhs = canon_ast(raw.get(rk).ok_or("Missing rhs")?)?;
211        return Ok(mk_obj(vec![(lk, lhs), (rk, rhs), ("tag", tag.into())]));
212    }
213    match tag {
214        "Lit" => {
215            let tok = encode_num_val(raw.get("value").ok_or("Missing value")?)?.token();
216            Ok(mk_obj(vec![("tag", "Lit".into()), ("value", tok.into())]))
217        }
218        "Var" | "MCardGet" => {
219            let key = if tag == "Var" { "name" } else { "handle" };
220            let val = raw.get(key).and_then(|v| v.as_str()).ok_or("Missing key")?;
221            Ok(mk_obj(vec![(key, val.into()), ("tag", tag.into())]))
222        }
223        "AddZero" => {
224            let expr = canon_ast(raw.get("expr").ok_or("Missing expr")?)?;
225            Ok(mk_obj(vec![("expr", expr), ("tag", "AddZero".into())]))
226        }
227        "Lam" | "MCardPut" => {
228            let (child_key, str_key) = if tag == "Lam" {
229                ("body", "param")
230            } else {
231                ("expr", "handle")
232            };
233            let child = canon_ast(raw.get(child_key).ok_or("Missing child")?)?;
234            let text = raw
235                .get(str_key)
236                .and_then(|v| v.as_str())
237                .ok_or("Missing str")?;
238            Ok(mk_obj(vec![
239                (child_key, child),
240                (str_key, text.into()),
241                ("tag", tag.into()),
242            ]))
243        }
244        _ => Err(format!("Unknown AST tag: {}", tag)),
245    }
246}
247
248fn subst_ast(node: &serde_json::Value, param: &str, repl: &serde_json::Value) -> serde_json::Value {
249    let tag = node["tag"].as_str().unwrap_or("");
250    if tag == "Var" {
251        return if node["name"].as_str() == Some(param) {
252            repl.clone()
253        } else {
254            node.clone()
255        };
256    }
257    if tag == "Lam" && node["param"].as_str() == Some(param) {
258        return node.clone();
259    }
260    let pairs = node
261        .as_object()
262        .unwrap()
263        .iter()
264        .map(|(k, v)| {
265            let next = if v.is_object() {
266                subst_ast(v, param, repl)
267            } else {
268                v.clone()
269            };
270            (k.as_str(), next)
271        })
272        .collect();
273    mk_obj(pairs)
274}
275
276fn lift_step(step: Step, wrap: impl FnOnce(serde_json::Value) -> serde_json::Value) -> Step {
277    match step {
278        Step::Tau(next, store) => Step::Tau(wrap(next), store),
279        Step::Vis(event, next, store) => Step::Vis(event, wrap(next), store),
280        Step::Ret(val) => Step::Ret(val),
281    }
282}
283
284pub(crate) fn step_ast(expr: &serde_json::Value, store: &Store) -> Step {
285    let tag = expr["tag"].as_str().unwrap_or("");
286    if matches!(tag, "Lit" | "Lam" | "Var") {
287        let ret = if tag == "Lit" {
288            expr["value"].as_str().unwrap().into()
289        } else if tag == "Var" {
290            format!("ERR_UNBOUND:{}", expr["name"].as_str().unwrap())
291        } else {
292            format!(
293                "LAM:{}:{}",
294                expr["param"].as_str().unwrap(),
295                serde_json::to_string(&expr["body"]).unwrap()
296            )
297        };
298        return Step::Ret(ret);
299    }
300    if tag == "AddZero" || tag == "MCardPut" {
301        let inner = &expr["expr"];
302        let sub = step_ast(inner, store);
303        if !matches!(sub, Step::Ret(_)) {
304            return lift_step(sub, |next| {
305                if tag == "AddZero" {
306                    mk_obj(vec![("expr", next), ("tag", "AddZero".into())])
307                } else {
308                    mk_obj(vec![
309                        ("expr", next),
310                        ("handle", expr["handle"].clone()),
311                        ("tag", "MCardPut".into()),
312                    ])
313                }
314            });
315        }
316        if inner["tag"].as_str() != Some("Lit") {
317            return Step::Ret("ERR_TYPE".into());
318        }
319        if tag == "AddZero" {
320            let lhs = encode_num_val(&inner["value"]).unwrap();
321            let nv = apply_num_op("add", &lhs, &CanonNum::SignedZero(false)).token();
322            return Step::Tau(
323                mk_obj(vec![("tag", "Lit".into()), ("value", nv.into())]),
324                store.clone(),
325            );
326        }
327        let handle = expr["handle"].as_str().unwrap();
328        let tok = inner["value"].as_str().unwrap();
329        let mut next_store = store.clone();
330        next_store.insert(handle.into(), tok.into());
331        return Step::Vis(format!("PUT:{}:{}", handle, tok), inner.clone(), next_store);
332    }
333    if tag == "MCardGet" {
334        let handle = expr["handle"].as_str().unwrap();
335        let tok = store
336            .get(handle)
337            .cloned()
338            .unwrap_or_else(|| "SIGNED_ZERO:+0".into());
339        return Step::Vis(
340            format!("GET:{}:{}", handle, tok),
341            mk_obj(vec![("tag", "Lit".into()), ("value", tok.into())]),
342            store.clone(),
343        );
344    }
345    let (lk, rk) = bin_keys(tag).unwrap();
346    let (ln, rn) = (&expr[lk], &expr[rk]);
347    let ls = step_ast(ln, store);
348    if tag == "Seq" && matches!(ls, Step::Ret(_)) {
349        return Step::Tau(rn.clone(), store.clone());
350    }
351    if !matches!(ls, Step::Ret(_)) {
352        return lift_step(ls, |next| {
353            mk_obj(vec![(lk, next), (rk, rn.clone()), ("tag", tag.into())])
354        });
355    }
356    let rs = step_ast(rn, store);
357    if !matches!(rs, Step::Ret(_)) {
358        return lift_step(rs, |next| {
359            mk_obj(vec![(lk, ln.clone()), (rk, next), ("tag", tag.into())])
360        });
361    }
362    if tag == "App" {
363        if ln["tag"].as_str() != Some("Lam") {
364            return Step::Ret("ERR_TYPE".into());
365        }
366        let body = subst_ast(&ln["body"], ln["param"].as_str().unwrap(), rn);
367        return Step::Tau(body, store.clone());
368    }
369    if ln["tag"].as_str() != Some("Lit") || rn["tag"].as_str() != Some("Lit") {
370        return Step::Ret("ERR_TYPE".into());
371    }
372    let op = match tag {
373        "Add" => "add",
374        "Sub" => "sub",
375        _ => "mul",
376    };
377    let nv = apply_num_op(
378        op,
379        &encode_num_val(&ln["value"]).unwrap(),
380        &encode_num_val(&rn["value"]).unwrap(),
381    )
382    .token();
383    Step::Tau(
384        mk_obj(vec![("tag", "Lit".into()), ("value", nv.into())]),
385        store.clone(),
386    )
387}