I am currently writing a compile time SKI evaluator. So far it works well but I noticed something interesting and would like to know why it is not possible.
Some basic information: "Evaluation" is implemented by letting the compiler figure out if there exists an type that satisfies some trait bound. The type it has to find describes the evaluation of the SKI expression so always writing it out is out of question for my use case. The Eval trait:
trait Eval<WorkLeft> {
type Result;
fn eval(self) -> Self::Result;
}
Now for the interesting part. The following code works and shows a simple example of how to evaluate SKI expressions:
#[test]
fn test_I() {
let c4 = USize::<4>;
let identity = Application(Application(S, K), K);
let applied = Application(identity, c4);
let evaluated = applied.eval();
dbg!(evaluated);
}
Notice how we can call applied.eval() without specifying any types.
Now the next test fails, which tries to do the same as the previous one only using types:
#[test]
fn test_I2() {
type C4 = USize<4>;
type identity = Application<Application<S, K>, K>;
type applied = Application<identity, C4>;
type evaluated = applied::Result;
}
Here the compiler complains about an ambigous associated type on applied::Result.
My question: the compiler obviously knows to check for the existence of the type parameter WorkLeft and that it is unique (otherwise test_I should give a use fully qualified trait syntax error) on function calls, why does rustc not allow accessing associated types from such a trait?
For the interested the full code (180 lines of code including tests):
Code
use std::marker::PhantomData;
trait Eval<WorkLeft> {
type Result;
fn eval(self) -> Self::Result;
}
struct Done;
struct Todo<T>(PhantomData<T>);
struct TodoApplication<L, R>(PhantomData<L>, PhantomData<R>);
trait ConstVal {
type RuntimeType;
const VAL: Self::RuntimeType;
}
#[derive(Copy, Clone)]
struct S;
impl Eval<Done> for S {
type Result = S;
fn eval(self) -> Self::Result {
self
}
}
#[derive(Copy, Clone)]
struct S1<X>(X);
impl<X> Eval<Done> for S1<X> {
type Result = S1<X>;
fn eval(self) -> Self::Result {
self
}
}
#[derive(Copy, Clone)]
struct S2<X, Y>(X, Y);
impl<X, Y> Eval<Done> for S2<X, Y> {
type Result = S2<X, Y>;
fn eval(self) -> Self::Result {
self
}
}
#[derive(Copy, Clone)]
struct K;
impl Eval<Done> for K {
type Result = K;
fn eval(self) -> Self::Result {
self
}
}
#[derive(Copy, Clone)]
struct K1<X>(X);
impl<X> Eval<Done> for K1<X> {
type Result = K1<X>;
fn eval(self) -> Self::Result {
self
}
}
#[derive(Copy, Clone)]
struct Application<L, R>(L, R);
impl<R, TL, TR, X, Y> Eval<TodoApplication<TL, TR>> for Application<Application<X, Y>, R>
where
Application<X, Y>: Eval<TL>,
Application<<Application<X, Y> as Eval<TL>>::Result, R>: Eval<TR>,
{
type Result = <Application<<Application<X, Y> as Eval<TL>>::Result, R> as Eval<TR>>::Result;
fn eval(self) -> Self::Result {
Application(Application(self.0 .0, self.0 .1).eval(), self.1).eval()
}
}
impl<R, T> Eval<Todo<T>> for Application<S, R>
where
S1<R>: Eval<T>,
{
type Result = <S1<R> as Eval<T>>::Result;
fn eval(self) -> Self::Result {
S1(self.1).eval()
}
}
impl<R, T, X> Eval<Todo<T>> for Application<S1<X>, R>
where
S2<X, R>: Eval<T>,
{
type Result = <S2<X, R> as Eval<T>>::Result;
fn eval(self) -> Self::Result {
S2(self.0 .0, self.1).eval()
}
}
impl<R, T, X, Y> Eval<Todo<T>> for Application<S2<X, Y>, R>
where
R: Copy,
Application<Application<X, R>, Application<Y, R>>: Eval<T>,
{
type Result = <Application<Application<X, R>, Application<Y, R>> as Eval<T>>::Result;
fn eval(self) -> Self::Result {
Application(
Application(self.0 .0, self.1),
Application(self.0 .1, self.1),
)
.eval()
}
}
impl<R, T> Eval<Todo<T>> for Application<K, R>
where
K1<R>: Eval<T>,
{
type Result = <K1<R> as Eval<T>>::Result;
fn eval(self) -> Self::Result {
K1(self.1).eval()
}
}
impl<R, T, X> Eval<Todo<T>> for Application<K1<X>, R>
where
X: Eval<T>,
{
type Result = <X as Eval<T>>::Result;
fn eval(self) -> Self::Result {
self.0 .0.eval()
}
}
// Numbers
#[derive(Copy, Clone, Debug)]
struct USize<const N: usize>;
impl<const N: usize> ConstVal for USize<N> {
type RuntimeType = usize;
const VAL: Self::RuntimeType = N;
}
impl<const N: usize> Eval<Done> for USize<N> {
type Result = Self;
fn eval(self) -> Self::Result {
USize::<N>
}
}
impl<R, T, const N: usize> Eval<Todo<T>> for Application<USize<N>, R>
where
R: Eval<T>,
{
type Result = Application<USize<N>, <R as Eval<T>>::Result>;
fn eval(self) -> Self::Result {
Application(self.0, self.1.eval())
}
}
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_K1() {
type T = Application<K1<USize<1>>, USize<2>>;
type R = <T as Eval<Todo<Done>>>::Result;
const n: usize = R::VAL;
}
#[test]
fn test_K() {
type T = Application<Application<K, USize<1>>, USize<2>>;
type R = <T as Eval<TodoApplication<Todo<Done>, Todo<Done>>>>::Result;
const n: usize = R::VAL;
}
#[test]
fn test_I() {
let c4 = USize::<4>;
let identity = Application(Application(S, K), K);
let applied = Application(identity, c4);
let evaluated = applied.eval();
dbg!(evaluated);
}
#[test]
fn test_I2() {
type C4 = USize<4>;
type identity = Application<Application<S, K>, K>;
type applied = Application<identity, C4>;
type evaluated = applied::Result;
}
}