Enum StackType 

pub enum StackType {
    Empty,
    Cons {
        rest: Box<StackType>,
        top: Type,
    },
    RowVar(String),
}

Stack types with row polymorphism

Understanding Stack Type Representation

Seq uses row polymorphism to type stack operations. The stack is represented as a linked list structure using Cons cells (from Lisp terminology).

Components

• Cons { rest, top }: A “cons cell” pairing a value type with the rest of the stack

  • top: The type of the value at this position
  • rest: What’s underneath (another Cons, Empty, or RowVar)

• RowVar("name"): A row variable representing “the rest of the stack we don’t care about”

  • Enables polymorphic functions like dup that work regardless of stack depth
  • Written as ..name in stack effect signatures

• Empty: An empty stack (no values)

Debug vs Display Format

The Debug format shows the internal structure (useful for compiler developers):

Cons { rest: Cons { rest: RowVar("a$5"), top: Int }, top: Int }

The Display format shows user-friendly notation (matches stack effect syntax):

(..a$5 Int Int)

Reading the Debug Format

To read Cons { rest: Cons { rest: RowVar("a"), top: Int }, top: Float }:

1. Start from the outermost Cons - its top is the stack top: Float
2. Follow rest to the next Cons - its top is next: Int
3. Follow rest to RowVar("a") - this is the polymorphic “rest of stack”

Cons { rest: Cons { rest: RowVar("a"), top: Int }, top: Float }
│                                           │           │
│                                           │           └── top of stack: Float
│                                           └── second from top: Int
└── rest of stack: ..a (whatever else is there)

Equivalent to: (..a Int Float)  or in signature: ( ..a Int Float -- ... )

Fresh Variables (e.g., “a$5”)

During type checking, variables are “freshened” to avoid name collisions:

• a becomes a$0, a$1, etc.
• The number is just a unique counter, not semantically meaningful
• a$5 means “the 6th fresh variable generated with prefix ‘a’”

Example Error Message

divide: stack type mismatch. Expected (..a$0 Int Int), got (..rest Float Float)

Meaning:

• divide expects two Int values on top of any stack (..a$0)
• You provided two Float values on top of the stack (..rest)
• The types don’t match: Int vs Float

Variants

Empty

Empty stack - no values

Cons

Stack with a value on top of rest (a “cons cell”)

Named after Lisp’s cons (construct) operation that builds pairs. Think of it as: top is the head, rest is the tail.

Fields

rest: Box<StackType>

The rest of the stack (may be Empty, another Cons, or RowVar)

top: Type

The type on top of the stack at this position

RowVar(String)

Row variable representing “rest of stack” for polymorphism

Allows functions to be polymorphic over stack depth. Example: dup has effect ( ..a T -- ..a T T ) where ..a means “whatever is already on the stack stays there”.

Implementations

impl StackType

pub fn empty() -> Self

Create an empty stack type

pub fn singleton(ty: Type) -> Self

Create a stack type with a single value

pub fn push(self, ty: Type) -> Self

Push a type onto a stack type

pub fn from_vec(types: Vec<Type>) -> Self

Create a stack type from a vector of types (bottom to top)

pub fn pop(self) -> Option<(StackType, Type)>

Pop a type from a stack type, returning (rest, top) if successful

Trait Implementations

impl Clone for StackType

fn clone(&self) -> StackType

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for StackType

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for StackType

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Hash for StackType

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl PartialEq for StackType

fn eq(&self, other: &StackType) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for StackType

impl StructuralPartialEq for StackType