名称: 泛型实现描述: 实现参数化多态性的专家技能，包括类型参数边界、单态化、类型擦除、型变、高阶类型和关联类型。允许工具: 读取、写入、编辑、Bash、Glob、Grep

泛型实现技能

为编程语言实现参数化多态性，包括泛型、类型边界和编译策略。

能力

设计泛型语法和类型参数边界
实现单态化（Rust风格）
实现类型擦除（Java风格）
处理泛型类型中的型变
实现高阶类型（如适用）
设计特质/接口边界
处理关联类型
实现泛型方法分派

使用场景

在以下情况下调用此技能：

为语言添加泛型
实现单态化或类型擦除
设计特质边界和约束
处理泛型和子类型中的型变

输入参数

参数	类型	必填	描述
compilationStrategy	字符串	是	编译策略（单态化、擦除、字典传递）
features	数组	否	要实现的特性
varianceModel	字符串	否	型变处理（显式、推断、无）
boundsSystem	对象	否	边界系统配置

编译策略

{
  "compilationStrategy": "monomorphization",  // Rust, C++
  "compilationStrategy": "erasure",           // Java, TypeScript
  "compilationStrategy": "dictionary"         // Haskell, Swift 见证表
}

特性选项

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

输出结构

generics/
├── syntax/
│   ├── type-params.grammar         # 类型参数语法
│   ├── bounds.grammar              # 边界和约束
│   └── where-clause.grammar        # Where 子句语法
├── typing/
│   ├── generic-types.ts            # 泛型类型表示
│   ├── bounds-checking.ts          # 边界验证
│   ├── variance.ts                 # 型变检查
│   └── instantiation.ts            # 类型实例化
├── compilation/
│   ├── monomorphization.ts         # 单态化
│   ├── erasure.ts                  # 类型擦除
│   └── dictionary.ts               # 字典传递
├── inference/
│   ├── type-inference.ts           # 泛型类型推断
│   └── constraint-solving.ts       # 约束解析
└── tests/
    ├── bounds.test.ts
    ├── variance.test.ts
    └── compilation.test.ts

泛型类型系统

类型参数语法

// 基础泛型
struct Vec<T> {
    data: T[],
    len: usize
}

// 多个类型参数
struct HashMap<K, V> {
    buckets: Array<(K, V)>
}

// 类型参数边界
fn sort<T: Ord>(arr: &mut [T]) { ... }

// Where 子句用于复杂边界
fn process<T, U>(t: T, u: U) -> bool
where
    T: Clone + Debug,
    U: AsRef<T>
{ ... }

// 默认类型参数
struct Container<T = i32> {
    value: T
}

// 常量泛型
struct Array<T, const N: usize> {
    data: [T; N]
}

泛型类型表示

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

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

interface TypeBound {
  trait: TraitRef;
  // 额外约束
}

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

// 类型应用
interface TypeApplication {
  generic: GenericType;
  args: Type[];
}

单态化

// 单态化：为每个类型实例生成专用代码

interface MonomorphizationContext {
  instantiations: Map<string, Type[]>[];  // 跟踪所有实例
  generatedCode: Map<string, GeneratedFunction>;
}

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

  // 从入口点开始收集所有实例
  for (const entry of entryPoints) {
    collectInstantiations(entry, ctx);
  }

  // 为每个实例生成专用代码
  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 {
  // 将类型参数替换为具体类型
  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)
  };
}

// 单态化函数名称重整
function mangleName(baseName: string, typeArgs: Type[]): string {
  return `${baseName}_${typeArgs.map(typeToString).join('_')}`;
}

类型擦除

// 类型擦除：在运行时擦除泛型类型，使用类型转换

function eraseGenericType(type: Type): Type {
  if (type.kind === 'typeParam') {
    // 擦除到边界（如果无边界则擦除到 Object）
    return type.bounds.length > 0
      ? type.bounds[0]  // 擦除到第一个边界
      : ObjectType;
  }

  if (type.kind === 'application') {
    // 擦除类型参数
    return eraseGenericType(type.generic);
  }

  if (type.kind === 'generic') {
    // 擦除主体
    return eraseGenericType(type.body);
  }

  return type;
}

// 在使用点插入类型转换
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;
}

型变

// 型变检查
type Variance = 'covariant' | 'contravariant' | 'invariant' | 'bivariant';

interface VarianceChecker {
  // 计算类型在类型参数中的型变
  computeVariance(typeParam: TypeParameter, type: Type): Variance;

  // 检查型变注解是否正确
  checkVariance(generic: GenericType): VarianceError[];

  // 从使用中推断型变
  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':
      // 参数类型中逆变，返回值中协变
      const paramVariance = combineVariances(
        type.params.map(p => flipVariance(computeVariance(param, p)))
      );
      const returnVariance = computeVariance(param, type.returnType);
      return combineVariance(paramVariance, returnVariance);

    case 'application':
      // 基于类型构造器声明的型变组合
      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':
      // 可变位置是逆变
      return 'invariant';

    default:
      return 'bivariant';
  }
}

// 子类型化的型变规则
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;
      }
    });
  }
  // ... 其他情况
}

特质边界

// 特质边界检查
interface BoundsChecker {
  // 检查类型是否满足边界
  satisfiesBound(type: Type, bound: TypeBound): boolean;

  // 查找特质的实现
  resolveImpl(type: Type, trait: TraitRef): TraitImpl | null;

  // 检查 where 子句
  checkWhereClause(clause: WhereClause, env: TypeEnv): boolean;
}

function satisfiesBound(type: Type, bound: TypeBound): boolean {
  // 查找特质实现
  const impl = findTraitImpl(type, bound.trait);
  if (!impl) return false;

  // 检查关联类型约束
  for (const [name, constraint] of bound.associatedTypes) {
    const actualType = resolveAssociatedType(impl, name);
    if (!typesEqual(actualType, constraint)) return false;
  }

  return true;
}

// Where 子句示例：
// where T: Iterator<Item = U>, U: Display
interface WhereClause {
  constraints: BoundConstraint[];
}

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

关联类型

// 特质中的关联类型
trait Iterator {
  type Item;
  fn next(&mut self) -> Option<Self::Item>;
}

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

// 关联类型表示
interface AssociatedType {
  name: string;
  bounds: TypeBound[];
  default?: Type;
}

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

// 解析关联类型
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;
}

高阶类型

// 高阶类型：将类型构造器作为参数的类型

// 种类系统
type Kind =
  | { kind: 'type' }                    // * - 具体类型
  | { kind: 'arrow'; from: Kind; to: Kind };  // * -> * - 类型构造器

// 示例：Functor 接受类型构造器 F : * -> *
trait Functor<F: * -> *> {
  fn map<A, B>(fa: F<A>, f: A -> B) -> F<B>;
}

// 实现
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> : 检查 F : K1 -> K2 和 A : K1，结果是 K2
    const fnKind = inferKind(type.constructor);
    if (fnKind.kind !== 'arrow') throw new Error('Expected type constructor');
    checkKind(type.arg, fnKind.from);
    return fnKind.to;
  }
  // ... 其他情况
}

工作流程

设计泛型语法 - 类型参数、边界、where 子句
实现类型系统 - 泛型类型、实例化
添加边界检查 - 验证特质边界
实现型变 - 协变、逆变
选择编译策略 - 单态化或擦除
添加关联类型 - 如果使用特质
考虑高阶类型 - 用于高级用例
生成测试 - 边界、型变、编译

应用的最佳实践

类型检查和编译的清晰分离
高效的单态化与去重
正确的型变推断和检查
边界违规的清晰错误消息
支持泛型的类型推断
增量编译支持

参考资料

Rust 泛型：https://doc.rust-lang.org/book/ch10-00-generics.html
Java 泛型：https://docs.oracle.com/javase/tutorial/java/generics/
类型类 vs 对象：https://www.cs.cmu.edu/~rwh/papers/objects/popl93.pdf
高阶类型：https://typelevel.org/blog/2016/08/21/hkts-moving-forward.html

目标流程

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

名称: 泛型实现 描述: 实现参数化多态性的专家技能，包括类型参数边界、单态化、类型擦除、型变、高阶类型和关联类型。 允许工具: 读取、写入、编辑、Bash、Glob、Grep

泛型实现技能

能力

使用场景

输入参数

编译策略

特性选项

输出结构

泛型类型系统

类型参数语法

泛型类型表示

单态化

类型擦除

型变

特质边界

关联类型

高阶类型

工作流程

应用的最佳实践

参考资料

目标流程

名称: 泛型实现描述: 实现参数化多态性的专家技能，包括类型参数边界、单态化、类型擦除、型变、高阶类型和关联类型。允许工具: 读取、写入、编辑、Bash、Glob、Grep