Crate temp_stack

TempStack is a linked list data structure based on the temp_inst crate. The intended use case is that list items are allocated on the call stack; then the list also represents a “stack” with “frames”. Via temp_inst, each frame can contain references to data that is available at the point where it is constructed, without having to add lifetime parameters.

Example

The following lambda expression parser uses TempStack as a context that specifies which variables are in scope, in order to determine the de Bruijn index corresponding to a given variable name.

#[derive(Clone, PartialEq, Debug)]
enum Expr {
    Var(usize), // A de Bruijn index that specifies which binder the variable references.
    App(Box<Expr>, Box<Expr>),
    Lambda(String, Box<Expr>),
}

// The context containing the variables that are in scope at any given point during
// parsing. Note how `Ctx` does not require any lifetime parameters, even though it
// references strings with arbitrary lifetimes.
type Ctx = TempStack<(), TempRef<str>>;

fn parse(s: &str) -> Result<Expr, String> {
    let root_ctx = Ctx::new_root(());
    let (expr, s) = parse_expr(s, &root_ctx)?;
    if !s.is_empty() {
        return Err(format!("unexpected character at `{s}`"));
    }
    Ok(expr)
}

fn parse_expr<'a>(s: &'a str, ctx: &Ctx) -> Result<(Expr, &'a str), String> {
    let (expr, mut s) = parse_single_expr(s, ctx)?;
    let Some(mut expr) = expr else {
        return Err(format!("expected expression at `{s}`"));
    };
    loop {
        let (arg, r) = parse_single_expr(s, ctx)?;
        s = r;
        let Some(arg) = arg else {
            break;
        };
        expr = Expr::App(Box::new(expr), Box::new(arg));
    }
    Ok((expr, s))
}

fn parse_single_expr<'a>(s: &'a str, ctx: &Ctx) -> Result<(Option<Expr>, &'a str), String> {
    let s = s.trim_ascii_start();
    if let Some(s) = s.strip_prefix('λ') {
        let s = s.trim_ascii_start();
        let name_len = s
            .find(|ch: char| !ch.is_ascii_alphanumeric())
            .unwrap_or(s.len());
        if name_len == 0 {
            return Err(format!("expected parameter name at `{s}`"));
        }
        let (name, s) = s.split_at(name_len);
        let s = s.trim_ascii_start();
        let Some(s) = s.strip_prefix('.') else {
            return Err(format!("expected `.` at `{s}`"));
        };
        // Create a new context with `name` added.
        let body_ctx = ctx.new_frame(name);
        let (body, s) = parse_expr(s, &body_ctx)?;
        Ok((Some(Expr::Lambda(name.into(), Box::new(body))), s))
    } else if let Some(s) = s.strip_prefix('(') {
        let (body, s) = parse_expr(s, ctx)?;
        let Some(s) = s.strip_prefix(')') else {
            return Err(format!("expected `)` at `{s}`"));
        };
        Ok((Some(body), s))
    } else {
        let name_len = s
            .find(|ch: char| !ch.is_ascii_alphanumeric())
            .unwrap_or(s.len());
        if name_len == 0 {
            Ok((None, s))
        } else {
            let (name, r) = s.split_at(name_len);
            // Determine the De Bruijn index of the nearest `name` in context.
            let Some(idx) = ctx.iter().position(|v| v == name) else {
                return Err(format!("variable `{name}` not found at `{s}`"));
            };
            Ok((Some(Expr::Var(idx)), r))
        }
    }
}

assert_eq!(
    parse("λx.x"),
    Ok(Expr::Lambda("x".into(), Box::new(Expr::Var(0))))
);

assert_eq!(
    parse("λx. x x"),
    Ok(Expr::Lambda(
        "x".into(),
        Box::new(Expr::App(Box::new(Expr::Var(0)), Box::new(Expr::Var(0))))
    ))
);

assert_eq!(
    parse("λx.λy. y (x y x)"),
    Ok(Expr::Lambda(
        "x".into(),
        Box::new(Expr::Lambda(
            "y".into(),
            Box::new(Expr::App(
                Box::new(Expr::Var(0)),
                Box::new(Expr::App(
                    Box::new(Expr::App(Box::new(Expr::Var(1)), Box::new(Expr::Var(0)))),
                    Box::new(Expr::Var(1)),
                ))
            ))
        ))
    ))
);

assert_eq!(
    parse("λx.λy. (λz.z) (x z x)"),
    Err("variable `z` not found at `z x)`".into())
);

Structs

TempStackIter

An iterator over frames of a shared TempStack.

TempStackIterMut

An iterator over frames of a mutable TempStack.

Enums

TempStack

A linked list consisting of a single item of type Root and arbitrarily many items of type Frame. Both types must implement temp_inst::TempRepr, which declares them as “temporary representations” of possibly lifetime-dependent types such as references.

Type Aliases

TempStackFrame

TempStackFrameMut

TempStackRef

TempStackRefMut