generics-implementation

name	generics-implementation
description	Expert skill for implementing parametric polymorphism including type parameter bounds, monomorphization, type erasure, variance, higher-kinded types, and associated types.
allowed-tools	Read, Write, Edit, Bash, Glob, Grep
graph	{"domains":["domain:software-engineering"],"specializations":["specialization:programming-languages"],"skillAreas":["skill-area:compiler-implementation","skill-area:typescript-generic-programming"],"roles":["role:backend-engineer"]}

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

 ():  {
  
   substitution = (fn., typeArgs);

   {
    : (fn., typeArgs),
    : fn..( (p., substitution)),
    : (fn., substitution),
    : (fn., substitution)
  };
}


 ():  {
   ;
}

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):  {
   erasedExpected = (expectedType);
   erasedActual = (actualType);

   (!(erasedExpected, erasedActual)) {
     {
      : ,
      : expr,
      : erasedExpected
    };
  }

   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
       paramVariance = (
        ..( ((param, p)))
      );
       returnVariance = (param, .);
       (paramVariance, returnVariance);

     :
      
       (
        ..( {
           declaredVariance = ..[i].;
           usageVariance = (param, arg);
           (declaredVariance, usageVariance);
        })
      );

     :
      
       ;

    :
       ;
  }
}


 ():  {
   (sub. ===  && sup. === ) {
     (sub. !== sup.)  ;

     sub..( {
       supArg = sup.[i];
       variance = sub..[i].;

       (variance) {
         :
           (subArg, supArg);
         :
           (supArg, subArg);
         :
           (subArg, supArg);
         :
           ;
      }
    });
  }
  
}

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

   ;
}



  {
  : [];
}

  {
  : ;
  : [];
}

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(, trait);
   (!impl)   ();

   assocType = impl..(assocName);
   (!assocType)   ();

   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.;
  }
   (. === ) {
    
     fnKind = (.);
     (fnKind. !== )   ();
    (., fnKind.);
     fnKind.;
  }
  
}

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