Thanks for your reply. Let me try to get a bit more specific and maybe you see my problem.
I Implemented a typelevel SKI evaluator which looks like this:
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())
}
}
Tests
#[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;
}
}
playground
One of the "tricks" used is what I described in my first post: a Trait implementation for a Type generic over some other Type which is however only implemented for a single concrete type. This single concrete type however describes the whole process of reducing the "initial" SKI expression. In the reduced example I gave this would be the generic type Bar<X>
, in the full code this could be something like TodoApplication<Todo<Done>, Todo<Done>>
(see test_K1
and test_K
).
Now you could always specify this type, but thats not actually what I want: I want the compiler to check that this type exists and tell me what it is.
The part "check that it exists" in the simple example would be that foo.do_something()
compiles (therefore the compiler found an implementation and therefore a valid "reduction describing type".
But I what I don't yet know is how I can actually extract the type the compiler constructs nor the corresponding associated type from the trait.
That's correct, but my point with 2 is, that if the library owner implements the trait for another type the user library would break (since the user would then have to use the fully qualified syntax instead of the implicit one). If users always have to use the qualified syntax then my point is invalid and shame on me