Self-Recursive Enums as DSTs

Continuing the discussion from Infinite types as unsized?:

I came across this discussion while doing research to see if I could find a workaround for Rust not allowing (something similar to) the following type:

pub enum Symbol {
    Constant(NumberType),
    NamedVariable(VarID),
    Addition(Symbol, Symbol),
    Multiplication(Symbol, Symbol),
    Negation(Symbol),
    Reciprocal(Symbol),
}

I wrote that knowing full well that it would almost certainly not work, but I had to try. I was hoping that it would cause Symbol to be a dynamically sized type, which would be represented as a slice of discriminants (with some NumberTypes and VarIDs wherever the expression terminated). For example, let's say that we're representing the expression:

(1 - x) / 2x

Given this, one might want to write something like:

let expr = 
Symbol::Multiplication(
    Symbol::Addition(
        Symbol::Constant(1.into()),
        Symbol::Negation(
            Symbol::NamedVariable(x.id())
        )
    ),
    Symbol::Reciprocal(
        Symbol::Multiplication(
            Symbol::Constant(2.into()),
            Symbol::NamedVariable(x.id())
        )
    )
);

And hope that would be represented in memory something like:

(Where Add is the discriminant for Addition, Mul is the discriminant for Multiplication, etc, and x is whatever x.id() returned in the previous example)
[Mul, Add, Const, 1, Neg, NamedVar, x, Recip, Mul, Const, 2, Namedvar, x]

I think that in particular, the ability to have (at least some of) the normal semantics of enums, while preserving memory locality, would make leveraging Rust's type system for something like a computer algebra system significantly easier.

Interesting. The challenge is that the size is implicit and requires recursive matching to compute. So then would &Symbol still be a thin pointer?

  • If it's thin, then cloning would require the nontrivial recursive logic to compute the number of bytes to copy.
  • If it's a fat pointer storing the slice length in bytes, then matching on a &Symbol to get a (fat) reference to the second argument of Addition would require figuring out the size of the first argument which would require the same recursive parsing.

One can address this issue by storing the slice length inline in the slice before or after each discriminant and then the reference would be a thin pointer. But then the representation bloats up - though no worse than putting Symbol behind a Box.

But then this would also mean that you can't mutate the data structure locally. It requires potentially shifting all the data to the right of the mutated field and also updating any sizes stored to its left, which doesn't seem practical.

2 Likes

In theory I don't think this is too unreasonable, but in practice it will probably be hard to implement/use.

Since Symbol is a DST it can only appear as the last field, so this would be invalid.

Since Symbol is a DST it cannot be stored in a variable, at least for now.

The problem with this representation is that to get the value of the right side of the Mul you'll have to traverse the whole left side and similarly to get the whole size. Similarly this would be needed in order to compute the size of the whole Expr.

Another problem is that this might store data other than the discriminants, meaning all the discriminants have to be suitably aligned for that data and that might be a big memory waste.

I've been thinking of the recursion in Symbol as basically really extensive syntax sugar. So, &Symbol would be fat pointer in that model, storing the length of the slice of what I'll tentatively call UnderlyingSymbols.

I agree that the non-locality issue with storing lengths inline is probably a deal breaker. I definitely prefer the tradeoff of requiring recursive parsing to get the second argument of Addition. I always imagined that recursive parsing would be necessary for this sort of structure, and I think that as long as it's obvious when it's being made to happen it's an acceptable concession for the added flexibility, especially since the alternative of many layers of boxes is likely to hurt performance just as much by destroying cache-locality.

I don't really see how that's relevant; every part of this is invalid currently. The point of the proposal is to see if we can make it valid. Since Symbols are constructed from the leaf nodes up, every individual instance has a definite size at every point in time, and storing them consecutively is well-defined, just not (currently) valid Rust.

Good point; I probably should have clarified my assumption that this would perform a heap allocation, and that expr would end up having type &Symbol (which is effectively &[UnderlyingSymbol] with special match semantics).

Correct me if I'm wrong, but surely that's a problem with any slice of enums?

The structure/layout is completely reasonable for a serialization. So you can totally do this now and define your own fat pointer to different parts of it. I don't see any advantage of making this a primitive type:

  1. I don't see matching being implemented for it if field lookup is O(n) and requires recursive logic.
  2. There's not a choice of idiomatic pointer representation that results in both a compact serialization representation and O(1) field lookups - there are nontrivial trade-offs and different users may want to pick one vs the other.
2 Likes

It is relevant because they are needed for the proposal but are not explicitly listed in the proposal itself. I would interpret "just" making self-recursive enums as allowing an enum to be a field of one or more of its variants, which implies making it unsized. Everything's fine until here, but nowhere is said that this also changes the rules about unsized fields (which currently can only be the last field of a struct) or unsized variables (which currently are not allowed except using the unsized-locals feature).

I think a feature must be considered together with its other requirements on the language, otherwise it may become unusable or blocked on other features never being implemented.

You cannot have a reference (&Symbol) own a heap allocation. And a totally hidden heap allocation in the base language (where heap allocations may not even be available) is a big no for me.

That's assuming the implementation must be a slice of enums, but if I had to implement this manually I would use a different arena for each variant, avoiding the need to store most padding.

3 Likes

Only allow Addition(Box<Symbol>, Symbol), (as far as I know that is already possible), means Symbol is a dynamically sized type and it gives at least some cache locality.

Allowing Addition(Symbol, Symbol) is (as others have mentioned problematic because you'd have to find out where the second Symbol starts. This means either: (1) Adding the length of the first Symbol before it (basically length prefix encoded) (2) Adding an offset (relative pointer) to the second Symbol (basically the same as above) (3) Making it an (absolute/normal) pointer to the second Symbol, which is just appended.

All of these mean you wouldn't have to parse the entire left side to figure out the location of the right side. (3) would make the type immovable (Pin) because it is self referential.

(1) and (2) have the problem that any modification to the left side will require moving the entire right side, which may not be desirable. On the other hand the use case you've mentioned probably doesn't require modification of the left side after creation. But one problem I see with that is that modifications could result in having to move big chunks of memory, which already contains (relative) references which would thus break.

And the &[Symbol] approach is an option, too, though that requires that symbol must be a non-DST.

You might be interested in the Gibbon compiler: Gibbon | A compiler for operating on serialized trees

1 Like

The basic problem of this is that any scheme that doesn't use Dyn memory allocation can't allow mutation, since mutation can result in arbitrarily increasing the size required to store the type.

Even with a read-only approach, the approach proposed in the OP makes field lookup O(n) in the size of the preceding fields, which means that it is better represented with an iterator over the tree.

Alternatively, one could include the field offsets in the type, which would result in a read-only O(1) field lookup implementation, with some tradeoffs on how to store the fields (64-bit integer is fastest but most space-consuming, variable-sized int is tersest but most time-consuming).

Currently the best approach would be to write a macro to generate whatever is best for your use case, or just use Box if mutability is needed or optimization isn't critical.

This is an implementation supporting both mutable, indexed and iterator-based types.

pub enum Symbol<T = ()> {
    Constant(NumberType),
    NamedVariable(VarID),
    Addition(T, T),
    Multiplication(T, T),
    Negation(T),
    Reciprocal(T),
}

mod dyn_box {
	/// SAFETY: layout_for(x.clone()) == layout_of(construct(x))
	unsafe trait DynSize {
	    fn layout_of(&'a self) -> std::alloc::Layout;
	}

	/// SAFETY: layout_for(x.clone()) == layout_of(construct(x))
	unsafe trait DynFrom<T> {
	    fn layout_for(x: &T) -> std::alloc::Layout;
	    fn construct<'a>(mem: &'a mut [MaybeUninit<u8>], x: T) -> &'a mut Self;
	}


	#[repr(transparent)]
	pub struct DynBox<T: DynSize>(Pin<&'static mut T>);

	impl<T: DynSize> DynBox<T> {
	    pub fn new<U>(x: U) -> Self where T: DynFrom<U> {
		let layout = T::layout_for(&x);
		let mem = alloc(layout);
		Self(transmute(T::construct(mem, x)))
	    }
	}

	impl<T: DynSize> Drop for DynBox<T> {
	    fn drop(&mut self) {
	    	let layout = T::layout_of(self.ptr);
		drop_in_place(self.0);
		dealloc(self.0, layout);
	    }
	}

	impl<T: DynSize> Deref for DynBox<T> {
	    type Target = T;
	    
	    fn deref(&self) -> &Self::Target {
	    	self.0
	    }
	}
	
	impl<T: DynSize> DynBox<T> {
	    fn get_mut(&mut self) -> Pin<&mut T> {
	    	self.0
	    }
	}
}

mod tree {
	use super::dyn_box::*;

	trait NumChildren {
	    fn num_children(&self) -> usize
	}

	trait Children: NumChildren {
	    fn children(&self, first: usize, out: &mut [&Self]);
	}

	trait SetChild<T>: NumChildren {
	    fn set_child(self: Pin<&mut self>, idx: usize, value: T) -> T;
	}

	/// offsets so field access is O(1)
	pub struct RaTree<T: NumChildren> {
	    pub head: T,
	    offsets: [usize; 0],
            pinned: PhantomPinned,
	    tail: ()
	}
	
	impl<T: NumChildren> NumChildren for RaTree<T> {
	    fn num_children(&self) -> usize {self.head.num_children()}
	}
	
	impl<T: NumChildren> DynSize for RaTree<T> {
	    fn layout_of(&self) -> Layout {
	    	// iteratively visit rightmost parent
	    }
	}

	impl<T: NumChildren, U: IntoIterator<Item = Option<T>>> DynFrom<T> for RaTree<T> {
	    // ...
	}
	
	/// Some(Tree) when opening a tree node, None when closing a tree node
	impl<'a, T: NumChildren> IntoIterator for &'a RaTree<T> {
	    type Item = Option<T>;
	    // ...
	}
	
	impl<T: NumChildren> Deref for RaTree<T> {
	    type Target = T;
	}


	/// No offsets so field lookup is O(n)
	pub struct IterTree<T: NumChildren> {
	    pub head: T,
            pinned: PhantomPinned,
	    tail: ()
	}

	impl<T: NumChildren> NumChildren for IterTree<T> {
	    fn num_children(&self) -> usize {self.head.num_children()}
	}

	impl DynSize for IterTree {
	    fn layout_of(&self) -> Layout {
		Self::layout_for(&self)
	    }
	}

	impl<T: NumChildren, U: IntoIterator<Item = Option<T>>> DynFrom<T> for IterTree<T> {
	    // ...
	}

	/// Some(Tree) when opening a tree node, None when closing a tree node
	impl<'a, T: NumChildren> IntoIterator for &'a IterTree<T> {
	    type Item = Option<T>;
	    // ...
	}

	#[repr(trasparent)]
	pub struct IterTreeChildrenIsSlow<T: NumChildren>(pub IterTree<T>);

	impl<T: NumChildren> Children for IterTreeChildrenIsSlow<T> {
	    fn children(&self, first: usize, out: &mut [&Self]) {
		// call layout_of on non-last children to compute size and thus offset of next child
	    }
	}
	
	impl<T: NumChildren> Deref for RaTree<T> {
	    type Target = T;
	}

	

	pub struct MutTree<T: NumChildren> {
	    pub head: T,
            pinned: PhantomPinned,
	    tail: [DynBox<MutTree<T>>; 0]
	}

	impl<T: NumChildren> NumChildren for MutTree<T> {
	    fn num_children(&self) -> usize {self.head.num_children()}
	}

	impl DynSize for MutTree {
	    fn layout_of(&self) -> Layout {

	    }
	}

	impl<T: NumChildren, U: IntoIterator<Item = Option<T>>> DynFrom<T> for MutTree<T> {
	    // ...
	}

	/// Some(Tree) when opening a tree node, None when closing a tree node
	impl<'a, T: NumChildren> IntoIterator for &'a MutTree<T> {
	    type Item = Option<T>;
	    // ...
	}

	impl<T: NumChildren> Children for MutTree<T> {
	    fn children(&self, first: usize, out: &mut [&Self]) {

	    }
	}
	
	impl<T: NumChildren> SetChild<DynBox<MutTree<T>>> for MutTree<T> {
	}
	
	impl<T: NumChildren> Deref for MutTree<T> {
	    type Target = T;
	}
}
use tree:*;

impl<T> NumChildren for Symbol<T> {
    fn num_children(&'a self) -> usize {
        match self.deref() {
            Symbol::Addition(_, _) => 2,
            ...
        }
    }
}

trait AsSymbol {
    fn as_symbol(&'a self) -> Symbol<&'a Self>;
}

impl<T: Children + Deref<Item = Symbol>> AsSymbol for T
{
    fn as_symbol(&'a self) -> Symbol<&'a Self> {
        match self.deref() {
            Symbol::Addition(_, _) => {let mut c = [self; 2]; self.children(0, &mut c); Symbol::Addition(c[0], c[1])},
            ...
        }
    }
}

type RaSymbol = RaTree<Symbol>;
type IterSymbol = IterTree<Symbol>;
type MutSymbol = MutTree<Symbol>;

type RaSymbolRef<'a> = Symbol<&'a RaSymbol>;
type IterSymbolRef<'a> = Symbol<&'a IterSymbol>;
type MutSymbolRef<'a> = Symbol<&'a MutSymbol>;

type BoxRaSymbol = DynBox<RaSymbol>;
type BoxIterSymbol = DynBox<IterSymbol>;
type BoxMutSymbol = DynBox<MutSymbol>;

For matching, match on symbol.as_symbol() for RaTree/MutTree or *symbol for any trees.

2 Likes