Struct Parser

Source
pub struct Parser { /* private fields */ }
Expand description

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

Implementations§

Source§

impl Parser

Source

pub fn new() -> Parser

Source

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);
Source

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.

Source

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.

Source

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.

Source

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

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

Source

pub fn pause(&self) -> bool

Return whether pause mode is on or off.

Source

pub fn step(&self) -> bool

Return whether step mode is on or off.

Source

pub fn count_steps(&self) -> bool

Return whether the count step mode is on or off.

Source

pub fn set_non_interactive_mode(&mut self)

Turn on non-interactive mode.

Auto Trait Implementations§

§

impl Freeze for Parser

§

impl RefUnwindSafe for Parser

§

impl Send for Parser

§

impl Sync for Parser

§

impl Unpin for Parser

§

impl UnwindSafe for Parser

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.