Struct lambda_calc::parser::Parser

pub struct Parser { /* fields omitted */ }

Our hand-written parser. Use with parse().

Implementations

impl Parser

pub fn new() -> Parser

pub fn parse(
    &mut self,
    line: &str,
    file_info: Option<String>
) -> Result<Option<Ast>, String>

Parse the string given in line and returns the corresponding Ast. Note that this function does not beta-reduce the expression.

This parser uses all usual rules for implicit parenthesization in lambda calculus, namely:

• Left associativity is assumed by default:

let mut parser = Parser::new();
assert_eq!(parser.parse("a b c d", None), parser.parse("(((a b) c) d)", None));

• The lambda body stretches as far as possible:

let mut parser = Parser::new();
assert_eq!(parser.parse("lambda x . a b c", None), parser.parse("(lambda x . a b c)", None));

let mut parser = Parser::new();
assert_eq!(parser.parse("lambda x . a lambda y . y", None),
    parser.parse("(lambda x . (a (lambda y . y)))", None));

• Unnecessary parentheses are ignored:

let mut parser = Parser::new();
assert_eq!(parser.parse("((((a))))", None), parser.parse("a", None));

Additionally,

• Multiple variables may be put under a same lambda:

let mut parser = Parser::new();
assert_eq!(parser.parse("lambda x y z . x y", None),
    parser.parse("lambda x . lambda y . lambda z . x y", None));

• Lambda terms may be bound to symbols and later used.

Note that the symbol substitution is lazy, meaning it is deferred until truly needed when perfoming a beta reduction:

let mut parser = Parser::new();
assert_eq!(parser.parse("K = lambda x y . x", None), Ok(None));
let redex = parser.parse("K a b", None).unwrap();
// we haven't asked for any beta reduction, so K has not been
// substituted yet
let expected = Ast::new(Expr::Redex(
    Box::new(Ast::new(Expr::Redex(
        Box::new(Ast::new(Expr::Var { name: "K".to_string(), is_free: true })),
        Box::new(Ast::new(Expr::Var { name: "a".to_string(), is_free: true })),
    ))),
    Box::new(Ast::new(Expr::Var { name: "b".to_string(), is_free: true })),
)); // ((K a) b)
assert_eq!(redex, Some(expected));
let reduced = redex.unwrap().beta_reduce_quiet(&parser);
let expected = Some(Ast::new(Expr::Var { name: "a".to_string(), is_free: true }));
assert_eq!(reduced, expected);

One must take care when binding an expression with free variables; because of the lazy substitution, these variables might misbehave when captured, e.g. in

let mut parser = Parser::new();
assert_eq!(parser.parse("foo = \\f -> f x", None), Ok(None));
let reduced = parser.parse("(\\x -> foo) a", None)
    .unwrap()
    .unwrap()
    .beta_reduce_quiet(&parser);
// the "x" in foo's definition is never replaced with "a",
// because the definition is only substituted later
let expected = parser.parse("foo", None)
    .unwrap()
    .unwrap()
    .beta_reduce_quiet(&parser);
assert_eq!(reduced, expected);

pub fn parse_file(&mut self, filename: Option<String>) -> Result<(), String>

Parse all lines in the file named filename, or stdin if filename is None.

pub fn get_symbol_names_with_prefix(&self, prefix: &str) -> Vec<&str>

Get an iterator for symbol names starting with prefix. May be used to implement TAB completion.

pub fn get_symbol(&self, name: &str) -> Option<&Ast>

Return an immutable reference to an expression if its name can be found in the symbol table.

pub fn insert_symbol(&mut self, name: &str, ast: Ast)

Insert a symbol and its corresponding expression into the symbol table.

pub fn pause(&self) -> bool

Return whether pause mode is on or off.

pub fn step(&self) -> bool

Return whether step mode is on or off.

pub fn count_steps(&self) -> bool

Return whether the count step mode is on or off.

pub fn set_non_interactive_mode(&mut self)

Turn on non-interactive mode.