title: Can the untyped lambda calculus be implemented using generics only?
body: <p>Consider the following implementation of the untyped lambda calculus:</p>
  
  <pre><code>pub enum Term {
      Var(usize), // a variable with a De Bruijn index
      Abs(Box&lt;Term&gt;), // an abstraction
      App(Box&lt;Term&gt;, Box&lt;Term&gt;) // an application
  }
  
  impl Term {
      ...
  }
  </code></pre>
  
  <p>I feel that this design, while simple and concise, could benefit from being translated to traits. Different terms should have different sets of methods, e.g. only abstractions should be "unabstractable" and only applications should be evaluable.</p>
  
  <p>I'm aware of the usual arguments in the enums vs. traits; even if enums is the better choice here I'd still want to know if it's possible.</p>
  
  <p>My basic building blocks so far are more or less as follows:</p>
  
  <pre><code>#[derive(Clone, PartialEq, Eq)]
  pub struct Var(usize);
  
  #[derive(Clone, PartialEq, Eq)]
  pub struct Abs&lt;T: Term&gt;(T);
  
  #[derive(Clone, PartialEq, Eq)]
  pub struct App&lt;T: Term, U: Term&gt;(T, U);
  
  pub trait Term: Clone {
      fn abs(self) -&gt; Abs&lt;Self&gt; { Abs(self) }
  
      fn app&lt;T: Term&gt;(self, other: T) -&gt; App&lt;Self, T&gt; { App(self, other) }
  
      fn update_free_variables(&amp;mut self, added_depth: usize, own_depth: usize);
  
      fn _apply&lt;T: Term&gt;(&amp;mut self, other: &amp;mut T, depth: usize); // this is a helper function that enables term tree traversal for Abs&lt;T&gt;::apply
  
      fn is_reducible(&amp;self, limit: usize, count: &amp;usize) -&gt; bool;
  
      fn beta_reduce(&amp;mut self, order: Order, limit: usize, verbose: bool) -&gt; usize;
  }
  
  impl Var {
      pub fn new(index: usize) -&gt; Self {
          assert!(index &gt; 0);
          Var(index)
      }
  }
  
  impl&lt;T: Term&gt; Abs&lt;T&gt; {
      fn unabs(self) -&gt; T {
          self.0
      }
  
      fn apply&lt;U: Term&gt;(mut self, other: &amp;mut U) -&gt; T {
          self._apply(other, 0);
          self.unabs()
      }
  }
  
  impl&lt;T: Term, U: Term&gt; App&lt;T, U&gt; {
      fn unapp(self) -&gt; (T, U) {
          (self.0, self.1)
      }
  }
  
  // and some impl Term for X
  </code></pre>
  
  <p>While it's pretty easy to implement the basic functionalities, there are a few spots where I'm struggling to come up with the right solution. I need to be able to do the following:</p>
  
  <ul>
  <li>create a parser able to interpret any term, from plain variables to complex terms, with a single function</li>
  <li>substitute any variable (no matter how deeply nested) with another variable <em>or a different term</em></li>
  <li>recursively reduce terms (I'm not sure if that would be possible with a parsed term that would probably have to be a trait object)</li>
  </ul>
  
  <p>I'd prefer to attempt to implement it on my own, I just need some advice regarding the direction. Is it even possible without an enum wrapper? If so, what approach should I take (in terms of object safety, <code>unsafe</code> trickery etc.)?</p>