Fun With Rust's Traits

Rust's trait system is wonderful. Everyone I know that has used it agrees with this statement. It's a great way to encode shared behaviour between data types, and create flexible APIs.

It's also great for writing nonsense like this:

use std::f64::consts::PI;
use lisp::prelude::*;

fn main() {
    let r = 3.0;
    let res = eval((mul, PI, (mul, r, r)));
    println!("{}", res);
}

This program prints the area of a circle with radius 3: 28.274.

# Good grief, what have you done?

At its core, Lisp is just a tree where each node evalutes to some value. The node is easy to express in Rust:

trait Node {
    type Return;
    fn eval(self) -> Self::Return;
}

Then our eval function is a one-liner. We just take a node and evaluate it:

pub fn eval<N, R>(n: N) -> R
where
    N: Node<Return = R>,
{
    n.eval()
}

In Lisp, the first element in a node is usually a function, and the rest of the elements are the arguments to that function. Here's the simplest case: a function that takes no arguments.

impl<F, R> Node for (F,)
where
    F: Fn() -> R,
{
    type Return = R;
    fn eval(self) -> Self::Return {
        self.0()
    }
}

This is saying that a single element tuple, containing a function that takes no arguments and returns a value, is evaluated by executing that function and returning its value.

This would allow us to write and execute this main function:

use lisp::prelude::*;

fn hello_world() {
    println!("Hello, world!");
}

fn main() {
    eval((hello_world,));
}

Scaling up to functions that take arguments is a case of adding those arguments to the Node implementation:

impl<F, A, R> Node for (F, A)
where
    F: Fn(A) -> R,
{
    type Return = R;
    fn eval(self) -> Self::Return {
        self.0(self.1)
    }
}

But wait. This is where we hit our first snag. In Lisp, arguments to a function can also be nodes in the tree that need evaluating. Consider the following expression:

(+ 1 (+ 2 3))

We would expect the value to be 6. In the trait we just defined, this wouldn't work. We aren't accounting for arguments also being nodes. Fortunately the fix isn't too complicated:

impl<F, A, B, R> Node for (F, A)
where
    F: Fn(B) -> R,
    A: Node<Return = B>,
{
    type Return = R;
    fn eval(self) -> Self::Return {
        self.0(self.1.eval())
    }
}

And we can keep scaling this to as many arguments as we expect functions to need.

impl<F, A1, A2, A3, A4, R1, R2, R3, R4, R> Node for (F, A1, A2, A3, A4)
where
    F: Fn(R1, R2, R3, R4) -> R,
    A1: Node<Return = R1>,
    A2: Node<Return = R2>,
    A3: Node<Return = R3>,
    A4: Node<Return = R4>,
{
    type Return = R;
    fn eval(self) -> Self::Return {
        self.0(self.1.eval(), self.2.eval(), self.3.eval(), self.4.eval())
    }
}

With these trait definitions, we have made it possible to evaluate Rust tuples recursively in much the same way Lisp is evaluated.

The last thing we need now is to define primitive types as nodes, otherwise we won't be able to evaluate anything.

impl Node for i32 {
    type Return = Self;
    fn eval(self) -> Self::Return {
        self
    }
}

To avoid the drudgery of repeating these 6 lines of code for every type I can think of, I wrote a small macro to help me.

macro_rules! identity_node {
    ( $($t:ty),* ) => {
      $(
        impl Node for $t {
            type Return = $t;
            fn eval(self) -> Self::Return {
                self
            }
        }
      )*
    };
}

identity_node!(char, i8, i16, i32, i64, i128, u8, u16, u32, u64, u128, f32, f64, String);

With all of this in place it's possible to evaluate expressions. I made some helper functions for arithmetic operations to avoid the ugliness of using Mul::mul and Add::add directly:

use std::ops::{Add, Div, Mul, Sub};

pub fn add<A, B, C>(a: A, b: B) -> C
where
    A: Add<B, Output = C>,
{
    a + b
}

pub fn sub<A, B, C>(a: A, b: B) -> C
where
    A: Sub<B, Output = C>,
{
    a - b
}

pub fn mul<A, B, C>(a: A, b: B) -> C
where
    A: Mul<B, Output = C>,
{
    a * b
}

pub fn div<A, B, C>(a: A, b: B) -> C
where
    A: Div<B, Output = C>,
{
    a / b
}

# Further work

The above allows the first example, calculating the radius of a circle, to compile and run. But what about more useful examples like iterating over things, mapping them, and reducing them?

use lisp::prelude::*;

fn add_one(a: i32) -> i32 {
    a + 1
}

fn main() {
    let v = vec![1, 2, 3];
    let res: Vec<i32> = eval((to_vec, (reduce, 0, add, (map, add_one, vec![1, 2, 3]))));
    println!("{:?}", res);
}

Wouldn't it be cool if this worked?

Alas, I couldn't figure out a way to do it. I was able to define the functions:

use std::iter::Map;

pub fn map<I, E, F, R>(f: F, i: I) -> Map<I::IntoIter, F>
where
    F: FnMut(E) -> R,
    I: IntoIterator<Item = E>,
{
    i.into_iter().map(f)
}

pub fn reduce<I, E, F, R>(init: R, f: F, i: I) -> R
where
    F: FnMut(R, E) -> R,
    I: IntoIterator<Item = E>,
{
    i.into_iter().fold(init, f)
}

pub fn to_vec<T, I>(i: I) -> Vec<T>
where
    I: IntoIterator<Item = T>,
{
    i.into_iter().collect()
}

But I wasn't able to figure out how to make it possible to pass functions as arguments. I hit compile-time errors every time I tried.

For example, this does not compile:

impl<F, A, R> Node for F
where
  F: Fn(A) -> R
{
    type Return = Self;
    fn eval(self) -> Self::Return {
        self
    }
}

The error is:

error[E0207]: the type parameter `A` is not constrained by the impl trait, self type, or predicates
  --> src\lisp\node.rs:98:9
   |
98 | impl<F, A, R> Node for F
   |         ^ unconstrained type parameter

error[E0207]: the type parameter `R` is not constrained by the impl trait, self type, or predicates
  --> src\lisp\node.rs:98:12
   |
98 | impl<F, A, R> Node for F
   |            ^ unconstrained type parameter

This does compile:

impl<A, R> Node for fn(A) -> R
{
    type Return = Self;
    fn eval(self) -> Self::Return {
        self
    }
}

But if I try and use it like so:

use lisp::prelude::*;

fn run<A, R>(f: impl Fn(A) -> R, a: A) -> R {
    f(a)
}

fn hello(name: String) {
    println!("Hello, {}!", name);
}

fn main() {
    let name = "Sam".to_owned();
    eval((run, hello, name));
}

I get this error:

error[E0277]: the trait bound `fn(std::string::String) {hello}: lisp::prelude::Node` is not satisfied
  --> examples\fn_as_arg.rs:13:10
   |
13 |     eval((run, hello, name));
   |          ^^^^^^^^^^^^^^^^^^ the trait `lisp::prelude::Node` is not implemented for `fn(std::string::String) {hello}`
   |
  ::: C:\Users\hello\Documents\GitHub\rust-lisp-with-traits\src\lisp\mod.rs:11:8
   |
11 |     N: Node<Return = R>,
   |        ---------------- required by this bound in `lisp::prelude::eval`
   |
   = note: required because of the requirements on the impl of `lisp::prelude::Node` for `(fn(_, std::string::String) -> _ {run::<std::string::String, _, _>}, fn(std::string::String) {hello}, std::string::String)`

If I implement the following:

impl<A, R> Node for Box<dyn Fn(A) -> R> {
    type Return = Self;
    fn eval(self) -> Self::Return {
        self
    }
}

impl<T> Node for Box<T> {
    type Return = T;
    fn eval(self) -> Self::Return {
        *self
    }
}

I can get away with this:

eval((run, Box::new(hello), name));

And it works as expected, but feels a bit meh. If you've read this far, and know how to get this to work without needing to box the function, I'd love to hear from you. I'm @samwhoo on Twitter, and the full code is here: https://github.com/samwho/rust-lisp-with-traits.