haskell - sintaxis - validacion sintactica

¿Es posible representar la sintaxis abstracta de orden superior en Rust?

Question

En Haskell, es muy fácil escribir tipos de datos algebraicos (ADT) con funciones. Esto nos permite escribir intérpretes que se basan en funciones nativas para sustituciones, es decir, una sintaxis abstracta de orden superior (HOAS) , que se sabe que es muy eficiente. Por ejemplo, este es un simple intérprete de λ-cálculo que usa esa técnica:

data Term
  = Hol Term
  | Var Int
  | Lam (Term -> Term)
  | App Term Term

pretty :: Term -> String
pretty = go 0 where
  go lvl term = case term of
    Hol hol     -> go lvl hol 
    Var idx     -> "x" ++ show idx
    Lam bod     -> "λx" ++ show lvl ++ ". " ++ go (lvl+1) (bod (Hol (Var lvl)))
    App fun arg -> "(" ++ go lvl fun ++ " " ++ go lvl arg ++ ")"

reduce :: Term -> Term
reduce (Hol hol)     = hol
reduce (Var idx)     = Var idx
reduce (Lam bod)     = Lam (/v -> reduce (bod v))
reduce (App fun arg) = case reduce fun of
  Hol fhol      -> App (Hol fhol) (reduce arg)
  Var fidx      -> App (Var fidx) (reduce arg)
  Lam fbod      -> fbod (reduce arg)
  App ffun farg -> App (App ffun farg) (reduce arg)

main :: IO ()
main
  = putStrLn . pretty . reduce
  $ App
    (Lam$ /x -> App x x)
    (Lam$ /s -> Lam$ /z -> App s (App s (App s z)))

Observe cómo se usaron las funciones nativas en lugar de los índices de Bruijn. Eso hace que el intérprete sea mucho más rápido de lo que sería si sustituyéramos las aplicaciones manualmente.

Estoy consciente de que Rust tiene cierres y muchos tipos de Fn() , pero no estoy seguro de que funcionen exactamente como los cierres de Haskell en esta situación, y mucho menos de cómo expresar ese programa dada la naturaleza de bajo nivel de Rust. ¿Es posible representar a HOAS en Rust? ¿Cómo se representaría el tipo de datos Term ?

Answer 1

Como fanático del cálculo lambda, decidí intentarlo y, de hecho, es posible, aunque un poco menos interesante que en Haskell ( enlace del patio de recreo ):

use std::rc::Rc;
use Term::*;

#[derive(Clone)]
enum Term {
    Hol(Box<Term>),
    Var(usize),
    Lam(Rc<dyn Fn(Term) -> Term>),
    App(Box<Term>, Box<Term>),
}

impl Term {
    fn app(t1: Term, t2: Term) -> Self {
        App(Box::new(t1), Box::new(t2))
    }

    fn lam<F: Fn(Term) -> Term + ''static>(f: F) -> Self {
        Lam(Rc::new(f))
    }

    fn hol(t: Term) -> Self {
        Hol(Box::new(t))
    }
}

fn pretty(term: Term) -> String {
    fn go(lvl: usize, term: Term) -> String {
        match term {
            Hol(hol) => go(lvl, *hol),
            Var(idx) => format!("x{}", idx),
            Lam(bod) => format!("λx{}. {}", lvl, go(lvl + 1, bod(Term::hol(Var(lvl))))),
            App(fun, arg) => format!("({} {})", go(lvl, *fun), go(lvl, *arg)),
        }
    }

    go(0, term)
}

fn reduce(term: Term) -> Term {
    match term {
        Hol(hol) => *hol,
        Var(idx) => Var(idx),
        Lam(bod) => Term::lam(move |v| reduce(bod(v))),
        App(fun, arg) => match reduce(*fun) {
            Hol(fhol) => Term::app(Hol(fhol), reduce(*arg)),
            Var(fidx) => Term::app(Var(fidx), reduce(*arg)),
            Lam(fbod) => fbod(reduce(*arg)),
            App(ffun, farg) => Term::app(Term::app(*ffun, *farg), reduce(*arg)),
        },
    }
}

fn main() {
    // (λx. x x) (λs. λz. s (s (s z)))
    let term1 = Term::app(
        Term::lam(|x| Term::app(x.clone(), x.clone())), 
        Term::lam(|s| Term::lam(move |z| 
            Term::app(
                s.clone(),
                Term::app(
                    s.clone(),
                    Term::app(
                        s.clone(),
                        z.clone()
    ))))));

    // λb. λt. λf. b t f
    let term2 = Term::lam(|b| Term::lam(move |t| 
        Term::lam({
            let b = b.clone(); // necessary to satisfy the borrow checker
            move |f| Term::app(Term::app(b.clone(), t.clone()), f)
        })
    ));

    println!("{}", pretty(reduce(term1))); // λx0. λx1. (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 (x0 x1)))))))))))))))))))))))))))
    println!("{}", pretty(reduce(term2))); // λx0. λx1. λx2. ((x0 x1) x2)
}

Gracias a BurntSushi5 por la sugerencia de usar Rc que siempre olvido que existe y a Shepmaster por sugerir eliminar la Box innecesaria bajo Rc en Lam y cómo satisfacer al prestamista en cadenas Lam más largas.