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

| Parameter | Type | Required | Description | |-----------|------|----------|-------------| | compilationStrategy | string | Yes | Strategy (monomorphization, erasure, dictionary) | | features | array | No | Features to implement | | varianceModel | string | No | Variance handling (explicit, inferred, none) | | boundsSystem | object | No | Bounds system configuration |

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);
        cas