Difficulties implementing a const list

Without any direct application, I was wondering how "easy" (as in time required to understand why it works) it is to implement something I would describe as const list (using any nightly features as needed).
What think when saying "const list":

  • Something that can be used as a list
  • Is calculated at compile time
  • And the difficult part: supports basic list operations (returning const list(s))

I know there are some crates out there that implement something similar (slist) but at least the ones I found lack on the third point noted above.

For brevity I'm going to use some Haskell notation :slight_smile:

For example a basic requirement for me under point 3 would be being able to zip two lists: [a] -> [b] -> [(a,b)]

For starters I began something using const generics and arrived at the following:

#![feature(const_generics, const_evaluatable_checked)]
struct List<const L: usize> {
    list: [usize; L],
}
impl<const L: usize> List<L> {
    fn concat<const L2: usize>(self, other: List<L2>) -> List<{ L + L2 }> {
        unimplemented!()
    }
}

which provides const list length but not const list content.
So the obvious next step I thought would be to make the list contents const but that sadly does not compile:

struct List<const L: usize, const C:  [usize; L]> {}

Because const generics are not allowed to depend on each other :frowning:

After hitting this roadblock I thought to myself "well, maybe let's try the more classic algebraic type way". After trying multiple times I always seem to get stuck at fundamental problems like:

  • using an enum List<H,T>{Empty,List(H,T)}: cannot seem to find a way to write the return type as it would depend on the concrete enum variant
  • using struct List<H,T>(H,T) in combination with struct Empty{}: couldn't find a way to properly define a recursion anchor when writing down const fn Zip.

In most cases I end up with something along these lines:

#[derive(Copy, Clone)]
struct List<H, T>(H, T);

//#[derive(Copy, Clone)]
//struct Empty {}

trait ZipList: Copy {
    type Output;
}

//impl ZipList for Empty {
//    type Output = Empty;
//}

impl<H, T> ZipList for List<H, T>
where
    T: ZipList + Copy,
    H: Copy,
{
    type Output = List<(H, H), T::Output>;
}

const fn Zip<H, T>(l1: List<H, T>, l2: List<H, T>) -> <List<H, T> as ZipList>::Output
where
    List<H, T>: ZipList,
{
    List((l1.0, l2.0), Zip(l1.1, l2.1))
}

Which doesn't compile and does not have a recursion anchor.

If anybody could point me in the right direction how something like this can be implemented I would be very thankfull :slight_smile:

The author of frunk has some nice articles about advanced type-level programming in Rust that you might be interested in.

If you treat each type as an individual value instead of a set of values, you can write something like this:

#![feature(min_const_generics)] // or `use::typenum;`

trait ConstVal {
    type RuntimeType;
    const VAL: Self::RuntimeType;
}

#[derive(Copy, Clone, Debug)]
struct List<H, T>(H, T);

impl<H:ConstVal, T:ConstVal> ConstVal for List<H,T> {
    type RuntimeType = List<H::RuntimeType, T::RuntimeType>;
    const VAL: Self::RuntimeType = List(H::VAL, T::VAL);
}

impl<H:ConstVal, T:ConstVal> ConstVal for (H,T) {
    type RuntimeType = (H::RuntimeType, T::RuntimeType);
    const VAL: Self::RuntimeType = (H::VAL, T::VAL);
}

#[derive(Copy, Clone, Debug)]
struct Empty;

impl ConstVal for Empty {
    type RuntimeType = Self;
    const VAL:Self = Empty;
}

trait ZipList<L2>: Copy {
    type Output;
}

impl ZipList<Empty> for Empty {
    type Output = Empty;
}

impl<H1, T1, H2, T2> ZipList<List<H2,T2>> for List<H1, T1>
where
    T1: ZipList<T2> + Copy,
    T2: Copy,
    H1: Copy,
    H2: Copy,
{
    type Output = List<(H1, H2), T1::Output>;
}

#[derive(Copy,Clone,Debug)]
struct USize<const N:usize>;

impl<const N:usize> ConstVal for USize<N> {
    type RuntimeType = usize;
    const VAL: usize = N;
}

macro_rules! get_const {
    ($name:ident = $val:ty) => { const $name: <$val as ConstVal>::RuntimeType = <$val as ConstVal>::VAL; }
}

macro_rules! list {
    () => { Empty };
    ($H:ty $(, $($T:tt)*)?) => { List<$H, list!{$($($T)*)?}> }
}

type Zip<A,B> = <A as ZipList<B>>::Output;

fn main() {
    get_const!{ SEVEN = USize<7> }
    dbg!(SEVEN);

    type L1ty = list![USize<2>, USize<4>];
    get_const!{ L1 = L1ty }
    dbg!(L1);

    get_const!{ LZIP = Zip<L1ty, list![USize<11>, USize<13>]> }
    dbg!(LZIP);
}

(Playground)

2 Likes

Thanks a lot for the link and the perfect example :slight_smile:
It will however take some time to get my head around whats happening there and why that works and my attempts did not :smiley:

Have a nice day!

Short update:
I finally came back to experimenting a bit with this and finally managed to implement a type level Map :slight_smile:


// Map Implementation
#[allow(dead_code)]
type Map<L, F> = <L as MapList<F>>::Output;

trait MapList<F> {
    type Output;
}

impl<F> MapList<F> for Empty {
    type Output = Empty;
}

impl<F, H, T> MapList<F> for List<H, T>
where
    F: Function<H>,
    T: MapList<F>,
{
    type Output = List<F::Output, T::Output>;
}

trait Function<T> {
    type Output;
}

// Function for MapList

struct MaxUSize;

impl<const N: usize, const M: usize> Function<(USize<N>, USize<M>)> for MaxUSize
where
    [usize; const_max(N, M)]: ,
{
    type Output = USize<{ const_max(N, M) }>;
}

const fn const_max(n: usize, m: usize) -> usize {
    if n > m {
        n
    } else {
        m
    }
}

Taking small steps towards understanding all the magic possible with traits and associated types :slight_smile: all thanks to your help!

1 Like

You might be interested in some of my thesis work, which builds a Lisp implementation on top of these ideas. (Warning: extremely early and incomplete draft)

1 Like

Maybe it's time to amend Greenspun's Tenth Rule?

2 Likes

I needed some duck-typing; writing an embedded lisp seemed like the easiest way— The alternative was trying to teach the type system about operations closed over a class of types, which felt like more than a 2-semester job.

I'm kind of doing the same albeit for databases. I've had a look at 3 popular Haskell SQL embeddings, as well as Diesel, and it does look like trying to completely replicate a complete relational type system is either a pain on the user if done "properly", or gives up some of the correctness guarantees when keeping a sane number (and structure!) of traits in mind.

With the exception of the uniqueness guarantee (which Codd considers important but real databases generally ignore), I think I’ve just about got relational algebra modelled correctly. Unfortunately, it doesn’t play nicely with Rust generics or impl syntax: There’s no way to capture all allowable operations in the bounds system, even though the concrete types all support them.

Combined with using a newtype for each column name/type pair, that makes the ergonomics suboptimal. But I think it’s not too bad as a proof-of-concept.

1 Like

Short update:
Since yesterday I got Fold, Push, Reverse, Concat, IfThenElse, and Filterworking (all with some small tests).
I'm currently not very happy with my limited ability to work with Functions and am pondering if I should try to implement a lambda calculus in order to have a clear "target".

Code
trait ConstVal {
    type RuntimeType;
    const VAL: Self::RuntimeType;
}

// List Representation

#[derive(Clone, Copy, Debug)]
struct List<H, T>(H, T);

impl<H: ConstVal, T: ConstVal> ConstVal for List<H, T> {
    type RuntimeType = List<H::RuntimeType, T::RuntimeType>;
    const VAL: Self::RuntimeType = List(H::VAL, T::VAL);
}

impl<H: ConstVal, T: ConstVal> ConstVal for (H, T) {
    type RuntimeType = (H::RuntimeType, T::RuntimeType);
    const VAL: Self::RuntimeType = (H::VAL, T::VAL);
}

#[derive(Clone, Copy, Debug)]
struct Empty;

impl ConstVal for Empty {
    type RuntimeType = Self;
    const VAL: Self::RuntimeType = Empty;
}

#[allow(unused_macros)]
macro_rules! list {
    () => { Empty };
    ($H:ty $(, $($T:tt)*)?) => { List<$H, list!{$($($T)*)?}> }
}

// Zip Implementation
#[allow(dead_code)]
type Zip<A, B> = <A as ZipList<B>>::Output;

trait ZipList<L2> {
    type Output;
}

impl ZipList<Empty> for Empty {
    type Output = Empty;
}

impl<H1, T1, H2, T2> ZipList<List<H2, T2>> for List<H1, T1>
where
    T1: ZipList<T2>,
{
    type Output = List<(H1, H2), T1::Output>;
}

// Generic Function Trait

trait Function<T> {
    type Output;
}

// Map Implementation

#[allow(dead_code)]
type Map<L, F> = <L as MapList<F>>::Output;

trait MapList<F> {
    type Output;
}

impl<F> MapList<F> for Empty {
    type Output = Empty;
}

impl<F, H, T> MapList<F> for List<H, T>
where
    F: Function<H>,
    T: MapList<F>,
{
    type Output = List<F::Output, T::Output>;
}

// Function for MapList

struct MaxUSize;

impl<const N: usize, const M: usize> Function<(USize<N>, USize<M>)> for MaxUSize
where
    [(); const_max(N, M)]: ,
{
    type Output = USize<{ const_max(N, M) }>;
}

const fn const_max(n: usize, m: usize) -> usize {
    if n > m {
        n
    } else {
        m
    }
}

// Fold

type Fold<L, F, A> = <L as FoldList<F, A>>::Output;

trait FoldList<F, A> {
    type Output;
}

impl<F, A> FoldList<F, A> for Empty {
    type Output = A;
}

impl<F, A, H, T> FoldList<F, A> for List<H, T>
where
    F: Function<(A, H)>,
    T: FoldList<F, <F as Function<(A, H)>>::Output>,
{
    type Output = T::Output;
}

// Function for FoldList

// Sum

struct SumUSize;

impl<const A: usize, const H: usize> Function<(USize<A>, USize<H>)> for SumUSize
where
    [(); (A + H)]: ,
{
    type Output = USize<{ A + H }>;
}

// Reverse

type Reverse<L> = Fold<L, Push, Empty>;

struct Push;

impl<S, A> Function<(S, A)> for Push {
    type Output = List<A, S>;
}

// Concat

type Concat<L1, L2> = Fold<Reverse<L1>, Push, L2>;

// If then else

type If<B, Then, Else> = <B as IfThenElse<Then, Else>>::Output;

trait IfThenElse<Then, Else> {
    type Output;
}

impl<Then, Else> IfThenElse<Then, Else> for Boolean<true> {
    type Output = Then;
}
impl<Then, Else> IfThenElse<Then, Else> for Boolean<false> {
    type Output = Else;
}
// Boolean
struct Boolean<const B: bool> {}

impl<const B: bool> ConstVal for Boolean<B> {
    type RuntimeType = bool;
    const VAL: Self::RuntimeType = B;
}

// Filter

type Filter<L, F> = Reverse<Fold<L, PushIf<F>, Empty>>;

struct PushIf<F>(F);

impl<F, S, A> Function<(S, A)> for PushIf<F>
where
    F: Function<A>,
    F::Output: IfThenElse<List<A, S>, S>,
{
    type Output = <F::Output as IfThenElse<List<A, S>, S>>::Output;
}

// example Filter

struct GreaterThan<const N: usize>;

impl<const N: usize, const M: usize> Function<USize<M>> for GreaterThan<N>
where
    Boolean<{ const_gt(N, M) }>: ,
{
    type Output = Boolean<{ const_gt(N, M) }>;
}

const fn const_gt(n: usize, m: usize) -> bool {
    n < m
}

// Numbers

struct USize<const N: usize>;

impl<const N: usize> ConstVal for USize<N> {
    type RuntimeType = usize;
    const VAL: Self::RuntimeType = N;
}
1 Like

Another short update:
I decided to further reduce the scope a bit and to implement SKI (actually just SK, but whatever) and actually got something working (140 loc, not too bad assuming I didn't forget something):

Summary
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;
}

impl Eval<Done> for bool {
    type Result = bool;
    fn eval(self) -> Self::Result {
        self
    }
}

impl Eval<Done> for u32 {
    type Result = u32;
    fn eval(self) -> Self::Result {
        self
    }
}

#[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())
    }
}

Which can be used as follows:

let c4 = USize::<4>;
let identity = Application(Application(S, K), K);
let applied = Application(identity, c4);
let evaluated = applied.eval();
dbg!(evaluated);

What currently bothers me is the inability to directly get the return type of applied.eval(). What I would like to be able to write would be something like:

type C4 = USize<4>;
type identity = Application<Application<S, K>, K>;
type applied = Application<identity, C4>;
type evaluated = applied::Result;

But I think I can solve that with something similar to the construction from @2e71828 if applied to all (most?) my types and trait bounds: