Generics Implementation

Generics Implementation Skill

Implement parametric polymorphism for programming languages including generics, type bounds, and compilation strategies.

Capabilities

• Design generic syntax and type parameter bounds
• Implement monomorphization (Rust-style)
• Implement type erasure (Java-style)
• Handle variance in generic types
• Implement higher-kinded types (if applicable)
• Design trait/interface bounds
• Handle associated types
• Implement generic method dispatch

Usage

Invoke this skill when you need to:

• Add generics to a language
• Implement monomorphization or type erasure
• Design trait bounds and constraints
• Handle variance and subtyping with generics

Inputs

Compilation Strategies

{
  "compilationStrategy": "monomorphization",  // Rust, C++
  "compilationStrategy": "erasure",           // Java, TypeScript
  "compilationStrategy": "dictionary"         // Haskell, Swift witness tables
}

Feature Options

{
  "features": [
    "type-parameters",
    "trait-bounds",
    "associated-types",
    "variance",
    "higher-kinded-types",
    "default-type-parameters",
    "const-generics",
    "where-clauses",
    "specialization"
  ]
}

Output Structure

generics/
├── syntax/
│   ├── type-params.grammar         # Type parameter syntax
│   ├── bounds.grammar              # Bounds and constraints
│   └── where-clause.grammar        # Where clause syntax
├── typing/
│   ├── generic-types.ts            # Generic type representation
│   ├── bounds-checking.ts          # Bounds verification
│   ├── variance.ts                 # Variance checking
│   └── instantiation.ts            # Type instantiation
├── compilation/
│   ├── monomorphization.ts         # Monomorphization
│   ├── erasure.ts                  # Type erasure
│   └── dictionary.ts               # Dictionary passing
├── inference/
│   ├── type-inference.ts           # Generic type inference
│   └── constraint-solving.ts       # Constraint resolution
└── tests/
    ├── bounds.test.ts
    ├── variance.test.ts
    └── compilation.test.ts

Generic Type System

Type Parameter Syntax

// Basic generics
struct Vec<T> {
    data: T[],
    len: usize
}

// Multiple type parameters
struct HashMap<K, V> {
    buckets: Array<(K, V)>
}

// Type parameter bounds
fn sort<T: Ord>(arr: &mut [T]) { ... }

// Where clauses for complex bounds
fn process<T, U>(t: T, u: U) -> bool
where
    T: Clone + Debug,
    U: AsRef<T>
{ ... }

// Default type parameters
struct Container<T = i32> {
    value: T
}

// Const generics
struct Array<T, const N: usize> {
    data: [T; N]
}

Generic Type Representation

interface GenericType {
  name: string;
  typeParams: TypeParameter[];
  body: Type;
}

interface TypeParameter {
  name: string;
  bounds: TypeBound[];
  variance: Variance;
  default?: Type;
}

interface TypeBound {
  trait: TraitRef;
  // Additional constraints
}

type Variance = 'covariant' | 'contravariant' | 'invariant' | 'bivariant';

// Type application
interface TypeApplication {
  generic: GenericType;
  args: Type[];
}

Monomorphization

// Monomorphization: generate specialized code for each type instantiation

interface MonomorphizationContext {
  instantiations: Map<string, Type[]>[];  // Track all instantiations
  generatedCode: Map<string, GeneratedFunction>;
}

function monomorphize(
  program: Program,
  entryPoints: FunctionRef[]
): MonomorphizedProgram {
  const ctx: MonomorphizationContext = {
    instantiations: [],
    generatedCode: new Map()
  };

  // Collect all instantiations starting from entry points
  for (const entry of entryPoints) {
    collectInstantiations(entry, ctx);
  }

  // Generate specialized code for each instantiation
  for (const [signature, typeArgs] of ctx.instantiations) {
    const original = lookupGenericFunction(signature);
    const specialized = specializeFunction(original, typeArgs);
    ctx.generatedCode.set(mangleName(signature, typeArgs), specialized);
  }

  return buildMonomorphizedProgram(ctx);
}

function specializeFunction(
  fn: GenericFunction,
  typeArgs: Type[]
): SpecializedFunction {
  // Substitute type parameters with concrete types
  const substitution = buildSubstitution(fn.typeParams, typeArgs);

  return {
    name: mangleName(fn.name, typeArgs),
    params: fn.params.map(p => substituteType(p.type, substitution)),
    returnType: substituteType(fn.returnType, substitution),
    body: substituteInBody(fn.body, substitution)
  };
}

// Name mangling for monomorphized functions
function mangleName(baseName: string, typeArgs: Type[]): string {
  return `${baseName}_${typeArgs.map(typeToString).join('_')}`;
}

Type Erasure

// Type erasure: erase generic types at runtime, use casts

function eraseGenericType(type: Type): Type {
  if (type.kind === 'typeParam') {
    // Erase to bound (or Object if unbounded)
    return type.bounds.length > 0
      ? type.bounds[0]  // Erase to first bound
      : ObjectType;
  }

  if (type.kind === 'application') {
    // Erase type arguments
    return eraseGenericType(type.generic);
  }

  if (type.kind === 'generic') {
    // Erase body
    return eraseGenericType(type.body);
  }

  return type;
}

// Insert casts at usage sites
function insertCasts(expr: Expr, expectedType: Type, actualType: Type): Expr {
  const erasedExpected = eraseGenericType(expectedType);
  const erasedActual = eraseGenericType(actualType);

  if (!typesEqual(erasedExpected, erasedActual)) {
    return {
      type: 'cast',
      expr: expr,
      targetType: erasedExpected
    };
  }

  return expr;
}

Variance

// Variance checking
type Variance = 'covariant' | 'contravariant' | 'invariant' | 'bivariant';

interface VarianceChecker {
  // Compute variance of type parameter in type
  computeVariance(typeParam: TypeParameter, type: Type): Variance;

  // Check if variance annotation is correct
  checkVariance(generic: GenericType): VarianceError[];

  // Infer variance from usage
  inferVariance(generic: GenericType): Map<TypeParameter, Variance>;
}

function computeVariance(param: TypeParameter, type: Type): Variance {
  switch (type.kind) {
    case 'typeParam':
      return type.name === param.name ? 'covariant' : 'bivariant';

    case 'function':
      // Contravariant in parameter types, covariant in return
      const paramVariance = combineVariances(
        type.params.map(p => flipVariance(computeVariance(param, p)))
      );
      const returnVariance = computeVariance(param, type.returnType);
      return combineVariance(paramVariance, returnVariance);

    case 'application':
      // Combine based on declared variance of type constructor
      return combineVariances(
        type.args.map((arg, i) => {
          const declaredVariance = type.generic.typeParams[i].variance;
          const usageVariance = computeVariance(param, arg);
          return multiplyVariance(declaredVariance, usageVariance);
        })
      );

    case 'mutable':
      // Mutable positions are invariant
      return 'invariant';

    default:
      return 'bivariant';
  }
}

// Variance rules for subtyping
function isSubtype(sub: Type, sup: Type): boolean {
  if (sub.kind === 'application' && sup.kind === 'application') {
    if (sub.generic !== sup.generic) return false;

    return sub.args.every((subArg, i) => {
      const supArg = sup.args[i];
      const variance = sub.generic.typeParams[i].variance;

      switch (variance) {
        case 'covariant':
          return isSubtype(subArg, supArg);
        case 'contravariant':
          return isSubtype(supArg, subArg);
        case 'invariant':
          return typesEqual(subArg, supArg);
        case 'bivariant':
          return true;
      }
    });
  }
  // ... other cases
}

Trait Bounds

// Trait bound checking
interface BoundsChecker {
  // Check if type satisfies bound
  satisfiesBound(type: Type, bound: TypeBound): boolean;

  // Find implementation for trait
  resolveImpl(type: Type, trait: TraitRef): TraitImpl | null;

  // Check where clause
  checkWhereClause(clause: WhereClause, env: TypeEnv): boolean;
}

function satisfiesBound(type: Type, bound: TypeBound): boolean {
  // Look for trait implementation
  const impl = findTraitImpl(type, bound.trait);
  if (!impl) return false;

  // Check associated type constraints
  for (const [name, constraint] of bound.associatedTypes) {
    const actualType = resolveAssociatedType(impl, name);
    if (!typesEqual(actualType, constraint)) return false;
  }

  return true;
}

// Where clause example:
// where T: Iterator<Item = U>, U: Display
interface WhereClause {
  constraints: BoundConstraint[];
}

interface BoundConstraint {
  type: Type;
  bounds: TypeBound[];
}

Associated Types

// Associated types in traits
trait Iterator {
  type Item;
  fn next(&mut self) -> Option<Self::Item>;
}

impl Iterator for Range {
  type Item = i32;
  fn next(&mut self) -> Option<i32> { ... }
}

// Associated type representation
interface AssociatedType {
  name: string;
  bounds: TypeBound[];
  default?: Type;
}

interface TraitImpl {
  trait: TraitRef;
  forType: Type;
  associatedTypes: Map<string, Type>;
  methods: Map<string, Function>;
}

// Resolve associated type
function resolveAssociatedType(
  type: Type,
  trait: TraitRef,
  assocName: string
): Type {
  const impl = findTraitImpl(type, trait);
  if (!impl) throw new Error(`No impl of ${trait} for ${type}`);

  const assocType = impl.associatedTypes.get(assocName);
  if (!assocType) throw new Error(`Associated type ${assocName} not found`);

  return assocType;
}

Higher-Kinded Types

// Higher-kinded types: types that take type constructors as parameters

// Kind system
type Kind =
  | { kind: 'type' }                    // * - concrete type
  | { kind: 'arrow'; from: Kind; to: Kind };  // * -> * - type constructor

// Example: Functor takes a type constructor F : * -> *
trait Functor<F: * -> *> {
  fn map<A, B>(fa: F<A>, f: A -> B) -> F<B>;
}

// Implementation
interface HigherKindedType {
  name: string;
  kind: Kind;
}

function checkKind(type: Type, expectedKind: Kind): boolean {
  const actualKind = inferKind(type);
  return kindsEqual(actualKind, expectedKind);
}

function inferKind(type: Type): Kind {
  if (type.kind === 'typeParam') {
    return type.declaredKind;
  }
  if (type.kind === 'application') {
    // F<A> : check F : K1 -> K2 and A : K1, result is K2
    const fnKind = inferKind(type.constructor);
    if (fnKind.kind !== 'arrow') throw new Error('Expected type constructor');
    checkKind(type.arg, fnKind.from);
    return fnKind.to;
  }
  // ... other cases
}

Workflow

1. Design generic syntax - Type parameters, bounds, where clauses
2. Implement type system - Generic types, instantiation
3. Add bounds checking - Verify trait bounds
4. Implement variance - Covariance, contravariance
5. Choose compilation - Monomorphization or erasure
6. Add associated types - If using traits
7. Consider HKT - For advanced use cases
8. Generate tests - Bounds, variance, compilation

Best Practices Applied

• Clear separation of type checking and compilation
• Efficient monomorphization with deduplication
• Proper variance inference and checking
• Clear error messages for bound violations
• Support for type inference with generics
• Incremental compilation support

References

• Rust Generics: https://doc.rust-lang.org/book/ch10-00-generics.html
• Java Generics: https://docs.oracle.com/javase/tutorial/java/generics/
• Type Classes vs Objects: https://www.cs.cmu.edu/~rwh/papers/objects/popl93.pdf
• Higher-Kinded Types: https://typelevel.org/blog/2016/08/21/hkts-moving-forward.html

Target Processes

• generics-polymorphism.js
• type-system-implementation.js
• code-generation-llvm.js
• ir-design.js