Tree calculus interpreter in Vine

tree-calculus.vi

use std::option::Option;
use Option::{Some, None};

enum Program {
  Leaf,
  Stem(Program),
  Fork(Program, Program),
}

mod Program {
  pub fn graft(self: Program, other: Program) -> Program {
    use Program::{Leaf, Stem, Fork};
    match self {
      Leaf => Stem(other),
      Stem(self) => Fork(self, other),
      Fork(first, snd) => {
        match first {
          Leaf => snd,
          Stem(x) => snd.graft(other).graft(x.graft(other)),
          Fork(w, x) => other.graft(w).graft(x)
        }
      }
    }
  }
  pub fn to_string(self: Program) -> String {
    use Program::{Leaf, Stem, Fork};
    match self {
      Leaf => "()",
      Stem(self) => "(()" ++ self.to_string() ++ ")",
      Fork(first, snd) => "(()" ++ first.to_string() ++ snd.to_string() ++ ")"
    }
  }
}

/// Syntax:
/// () is a leaf
/// ab grafts b into a. This operation is left associative
/// this means that ()a is a stem of A and ()ab is a fork of a and b
struct Parser(String);

mod Parser {
  pub fn new(s: String) -> Parser {
    Parser(s)
  }
  pub fn pop_front(&Parser(s): &Parser) -> Option[Char] {
    s.pop_front()
  }
  pub fn push_front(&Parser(s): &Parser, c: Char)  {
    s.push_front(c)
  }
  pub fn expect(&state: &Parser, c: Char) -> Bool {
    if state.pop_front() is Some(i) {
      if i == c {
        true
      } else {
        state.push_front(i);
        false
      }
    } else {
      false
    }
  }
  pub fn parse_program_paren(&state: &Parser) -> Option[Program] {
    if state.expect('(') {
      let program = state.parse_program()
      if state.expect(')') {
        Some(program)
      } else {
        None
      }
    } else {
      None
    }
  }
  pub fn parse_program(&state: &Parser) -> Program {
    if state.parse_program_paren() is Some(program) {
      while state.parse_program_paren() is Some(graft) {
        program = program.graft(graft)
      }
      program
    } else {
      Program::Leaf
    }
  }
}

pub fn main(&io: &IO) {
  // K = (()())
  // I = (()(()())(()()))
  // the program below is (K I () (()())) = (false () (()()))
  // example program: (()())(()(()())(()()))(())(()())
  let s = Parser::new(io.full_input());
  let t = s.parse_program().to_string();
  io.println(t)
}

Example usage:

echo "(()())(()(()())(()()))(())(()())" | vine run tree-calculus.vi