Effect Systems

Effect Systems Skill

Design and implement algebraic effect systems for tracking and handling computational effects in programming languages.

Capabilities

• Design effect annotation syntax
• Implement effect inference algorithms
• Implement effect checking and tracking
• Design effect handlers (algebraic effects)
• Handle effect polymorphism
• Implement effect rows and extensibility
• Design effect subtyping
• Generate effect-based optimizations

Usage

Invoke this skill when you need to:

• Add an effect system to a language
• Implement algebraic effects and handlers
• Track computational effects in types
• Design effect polymorphism

Inputs

Effect Model Options

{
  "effectModel": "algebraic",  // Koka/Eff style
  "effectModel": "monadic",    // Haskell IO style
  "effectModel": "capability"  // Capability-based
}

Feature Options

{
  "features": [
    "effect-inference",
    "effect-handlers",
    "effect-polymorphism",
    "effect-rows",
    "effect-subtyping",
    "effect-abstraction",
    "resumption-control",
    "multi-shot-continuations"
  ]
}

Output Structure

effect-system/
├── syntax/
│   ├── effect-annotation.grammar    # Effect annotation syntax
│   ├── effect-handler.grammar       # Handler syntax
│   └── effect-operation.grammar     # Operation syntax
├── typing/
│   ├── effect-types.ts              # Effect type definitions
│   ├── effect-inference.ts          # Effect inference
│   ├── effect-checking.ts           # Effect checking
│   └── effect-rows.ts               # Row polymorphism
├── handlers/
│   ├── handler-impl.ts              # Handler implementation
│   ├── continuation.ts              # Continuation management
│   └── resumption.ts                # Resumption handling
├── runtime/
│   ├── effect-runtime.ts            # Runtime effect support
│   └── builtin-effects.ts           # Built-in effects
└── tests/
    ├── inference.test.ts
    ├── handlers.test.ts
    └── polymorphism.test.ts

Effect System Types

Algebraic Effects (Koka-style)

// Effect declaration
effect State<S> {
  get(): S
  put(s: S): ()
}

effect Exception<E> {
  raise(e: E): Nothing
}

// Effect types
type EffectType = {
  operations: Map<string, OperationType>;
}

interface OperationType {
  name: string;
  params: Type[];
  result: Type;
}

// Function types with effects
interface FunctionType {
  params: Type[];
  result: Type;
  effects: EffectRow;
}

// Effect rows (for polymorphism)
type EffectRow =
  | { type: 'empty' }
  | { type: 'single'; effect: EffectType }
  | { type: 'union'; effects: EffectType[] }
  | { type: 'variable'; name: string }           // Effect polymorphism
  | { type: 'extend'; base: EffectRow; effect: EffectType };

Effect Handlers

// Handler syntax
handle expr with {
  return(x) -> returnClause(x),
  get() -> getClause(resume),
  put(s) -> putClause(s, resume)
}

// Handler representation
interface Handler {
  effect: EffectType;
  returnClause: (value: any) => any;
  operationClauses: Map<string, OperationClause>;
}

interface OperationClause {
  operation: string;
  params: string[];
  resumeName: string;
  body: Expr;
}

// Handler typing
// handle[E] : (() -E> A) -> ((A -> B) & Handler[E]) -> B
function typeHandler(
  expr: Expr,
  handler: Handler,
  env: TypeEnv
): { resultType: Type; remainingEffects: EffectRow } {
  const exprType = inferType(expr, env);

  // Check that handler handles the effect
  checkHandlerCovers(handler, exprType.effects);

  // Result type comes from handler clauses
  const resultType = inferHandlerResult(handler, exprType.result, env);

  // Remove handled effect from row
  const remainingEffects = removeEffect(exprType.effects, handler.effect);

  return { resultType, remainingEffects };
}

Effect Inference

// Effect inference algorithm
function inferEffects(expr: Expr, env: TypeEnv): InferResult {
  switch (expr.type) {
    case 'var':
      return { type: lookupType(env, expr.name), effects: emptyRow() };

    case 'lambda':
      const bodyResult = inferEffects(expr.body, extendEnv(env, expr.param, expr.paramType));
      return {
        type: { type: 'function', param: expr.paramType, result: bodyResult.type, effects: bodyResult.effects },
        effects: emptyRow()  // Lambda itself is pure
      };

    case 'app':
      const fnResult = inferEffects(expr.fn, env);
      const argResult = inferEffects(expr.arg, env);
      const fnType = fnResult.type as FunctionType;
      return {
        type: fnType.result,
        effects: unionRows(fnResult.effects, argResult.effects, fnType.effects)
      };

    case 'perform':
      const opType = lookupOperation(env, expr.effect, expr.operation);
      const argEffects = expr.args.map(a => inferEffects(a, env).effects);
      return {
        type: opType.result,
        effects: unionRows(singleRow(expr.effect), ...argEffects)
      };

    case 'handle':
      const exprResult = inferEffects(expr.body, env);
      const handlerResult = checkHandler(expr.handler, exprResult, env);
      return handlerResult;

    // ... other cases
  }
}

Effect Polymorphism

// Effect-polymorphic function
// map : forall E. (a -E> b) -> List a -E> List b
interface EffectPolymorphicType {
  effectVars: string[];
  typeVars: string[];
  type: Type;
}

// Row polymorphism for effects
// foo : () -<State, E>-> Int   (E is a row variable)
type RowVariable = { type: 'rowVar'; name: string };

function unifyRows(row1: EffectRow, row2: EffectRow): Substitution {
  // Row unification algorithm
  if (row1.type === 'variable') {
    return { [row1.name]: row2 };
  }
  if (row2.type === 'variable') {
    return { [row2.name]: row1 };
  }
  if (row1.type === 'empty' && row2.type === 'empty') {
    return {};
  }
  // Handle union and extend cases...
}

Continuation Management

// Delimited continuations for effect handlers
interface Continuation<A, B> {
  resume(value: A): B;
}

// Multi-shot continuations (can resume multiple times)
interface MultiShotContinuation<A, B> extends Continuation<A, B> {
  clone(): MultiShotContinuation<A, B>;
}

// One-shot continuations (can only resume once)
interface OneShotContinuation<A, B> extends Continuation<A, B> {
  readonly consumed: boolean;
}

// Runtime continuation capture
class ContinuationCapture {
  capture<A, B>(
    prompt: Prompt,
    body: (k: Continuation<A, B>) => B
  ): B {
    // Capture the current continuation up to prompt
    const k = captureDelimited(prompt);
    return body(k);
  }
}

Built-in Effects

// Common built-in effects
const builtinEffects = {
  IO: {
    operations: {
      print: { params: [StringType], result: UnitType },
      readLine: { params: [], result: StringType },
      readFile: { params: [StringType], result: StringType },
      writeFile: { params: [StringType, StringType], result: UnitType }
    }
  },

  State: {
    typeParams: ['S'],
    operations: {
      get: { params: [], result: TypeVar('S') },
      put: { params: [TypeVar('S')], result: UnitType }
    }
  },

  Exception: {
    typeParams: ['E'],
    operations: {
      raise: { params: [TypeVar('E')], result: NothingType }
    }
  },

  Async: {
    operations: {
      await: { params: [PromiseType(TypeVar('A'))], result: TypeVar('A') },
      spawn: { params: [FunctionType([], TypeVar('A'), AsyncEffect)], result: TaskType(TypeVar('A')) }
    }
  },

  NonDet: {
    operations: {
      choice: { params: [], result: BoolType },
      fail: { params: [], result: NothingType }
    }
  }
};

Effect-Based Optimization

// Pure functions can be optimized more aggressively
function canOptimize(fn: FunctionType): OptimizationLevel {
  if (isEmptyRow(fn.effects)) {
    return 'pure';  // Full optimization: CSE, memoization, parallelization
  }
  if (onlyReads(fn.effects)) {
    return 'read-only';  // Can reorder, CSE
  }
  if (isLocalState(fn.effects)) {
    return 'local-state';  // Can inline, but not reorder
  }
  return 'effectful';  // Limited optimization
}

// Effect-based dead code elimination
function eliminateDeadCode(expr: Expr): Expr {
  const effects = inferEffects(expr);
  if (isEmptyRow(effects) && !isUsed(expr)) {
    return unit;  // Pure unused expression can be eliminated
  }
  return expr;
}

Workflow

1. Design effect syntax - Declarations, annotations, handlers
2. Define effect types - Operations, rows, polymorphism
3. Implement inference - Effect inference algorithm
4. Build effect checker - Verify effect annotations
5. Implement handlers - Handler evaluation/compilation
6. Add continuations - Delimited continuation support
7. Create builtins - Common effects (IO, State, etc.)
8. Generate tests - Inference, handlers, polymorphism

Best Practices Applied

• Row polymorphism for flexible effect composition
• Clear distinction between operations and handlers
• Support both inferred and annotated effects
• Efficient continuation representation
• Effect-based optimization opportunities
• Good error messages for effect mismatches

References

• Algebraic Effects for Functional Programming: https://www.microsoft.com/en-us/research/publication/algebraic-effects-for-functional-programming/
• Koka Language: https://koka-lang.github.io/
• Eff Language: https://www.eff-lang.org/
• Effect Handlers in Scope: https://www.cs.ox.ac.uk/people/nicolas.wu/papers/Scope.pdf
• Frank Language: https://arxiv.org/abs/1611.09259

Target Processes

• effect-system-design.js
• type-system-implementation.js
• concurrency-primitives.js