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 PI;
use *;
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:
Then our eval
function is a one-liner. We just take a node and evaluate it:
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.
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 *;
Scaling up to functions that take arguments is a case of adding those arguments to the Node implementation:
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:
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:
And we can keep scaling this to as many arguments as we expect functions to need.
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.
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.
identity_node!;
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 ;
# 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 *;
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 Map;
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:
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:
But if I try and use it like so:
use *;
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:
I can get away with this:
eval;
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.