Рассмотрим следующую реализацию нетипизированного лямбда-исчисления:
pub enum Term {
Var(usize), // a variable with a De Bruijn index
Abs(Box<Term>), // an abstraction
App(Box<Term>, Box<Term>) // an application
}
impl Term {
...
}
Я чувствую, что этот дизайн, хотя и простой и лаконичный, мог бы выиграть от преобразования в трейты. Различные термины должны иметь разные наборы методов, например. только абстракции должны быть «неабстрагируемыми», и только приложения должны быть оценены.
Я знаю об обычных аргументах в enums vs. traits; даже если перечисления - лучший выбор, я все равно хотел бы знать, возможно ли это.
Мои основные строительные блоки до сих пор более или менее следующие:
#[derive(Clone, PartialEq, Eq)]
pub struct Var(usize);
#[derive(Clone, PartialEq, Eq)]
pub struct Abs<T: Term>(T);
#[derive(Clone, PartialEq, Eq)]
pub struct App<T: Term, U: Term>(T, U);
pub trait Term: Clone {
fn abs(self) -> Abs<Self> { Abs(self) }
fn app<T: Term>(self, other: T) -> App<Self, T> { App(self, other) }
fn update_free_variables(&mut self, added_depth: usize, own_depth: usize);
fn _apply<T: Term>(&mut self, other: &mut T, depth: usize); // this is a helper function that enables term tree traversal for Abs<T>::apply
fn is_reducible(&self, limit: usize, count: &usize) -> bool;
fn beta_reduce(&mut self, order: Order, limit: usize, verbose: bool) -> usize;
}
impl Var {
pub fn new(index: usize) -> Self {
assert!(index > 0);
Var(index)
}
}
impl<T: Term> Abs<T> {
fn unabs(self) -> T {
self.0
}
fn apply<U: Term>(mut self, other: &mut U) -> T {
self._apply(other, 0);
self.unabs()
}
}
impl<T: Term, U: Term> App<T, U> {
fn unapp(self) -> (T, U) {
(self.0, self.1)
}
}
// and some impl Term for X
Хотя реализовать базовые функции довольно легко, есть несколько моментов, в которых я изо всех сил пытаюсь найти правильное решение. Мне нужно уметь делать следующее:
- создать синтаксический анализатор, способный интерпретировать любой термин, от простых переменных до сложных терминов, с помощью одной функции
- заменить любую переменную (независимо от того, насколько глубоко она вложена) другой переменной или другим термином
- рекурсивно сокращать термины (я не уверен, что это возможно с проанализированным термином, который, вероятно, должен быть трейт-объектом)
Я бы предпочел попытаться реализовать это самостоятельно, мне просто нужен совет относительно направления. Возможно ли это вообще без оболочки enum? Если да, то какой подход я должен использовать (с точки зрения безопасности объекта, unsafe обмана и т. д.)?
