01_adding_approaches

adding approaches

Extension: Adding New Algorithmic Approaches

Purpose

This document provides the standard operating procedure for extending the ARES registry. It details the process of authoring new algorithmic intents, creating multi-language code templates, and registering them as first-class approaches. Following this specification ensures that new additions are correctly indexed by the compiler's Phase 3 (Semantic Analysis) and Phases 7/8 (Codegen/Emission) for all supported backends.

Prerequisites

  • Registry Layer Identification: Determine the taxonomy layer (1=Core to 4=Advanced).
  • Template Authoring: Requires finalized snippet implementations in C++, Python, and TypeScript.
  • Unique Handle: A canonical name (lowercase, underscore-separated) for the approach.

Dependencies

  • src/registry/categories/: The directory where the new category file should be created.
  • ApproachInfo Interface: The TypeScript contract defined in src/types.ts.

Formal Definition

Let AnewA_{new} be a new approach to be added to the registry R\mathcal{R}. The registration Reg\mathcal{Reg} is an additive transformation: R′=R∪{Anew}\mathcal{R}' = \mathcal{R} \cup \{ A_{new} \} Where Anew={name, complexity, templates, metadata}A_{new} = \{ \text{name, complexity, templates, metadata} \}.

Operational Behavior

  1. Intent Selection: Identify a recurring algorithmic pattern (e.g., convex_hull) not already in R\mathcal{R}.
  2. Category Mapping: Add the approach to an existing category file (e.g., cp_advanced.ts) or create a new one.
  3. Cross-Language Templating: Author the logic for each backend, ensuring that placeholder variables like {{target}} and {{params.name}} are used correctly for context injection.
  4. Alias Resolution: Add common synonyms (e.g., monotone_chain for convex_hull) to the aliases array for a broader semantic reach.
  5. Documentation Update: Author the corresponding Markdown specification in 8_registry_approaches/ following the 17-point structural standard.

Implementation Mapping

ARES Registry Addition vs. Final Result

Step 1: Modifying (or Creating) the Category File

Action (src/registry/categories/cp_new.ts):

typescript
import type { ApproachInfo } from "../../types.js";

export const CpNewApproaches: ApproachInfo[] = [
  {
    name: "new_alg",
    description: "An example new algorithm.",
    layer: 4, 
    complexity: "O(log N)",
    category: "new",
    cpp_template: "long long res = std::log2({{target}});", // v1.2: use long long
    py_template: "import math\nres = math.log2({{target}})",
    ts_template: "const res = Math.log2({{target}});",
  }
];

Step 2: Registering the Category

Action (src/registry/approach_registry.ts): You must import your new category and register it in the initializeRegistry() method:

typescript
import { CpNewApproaches } from "./categories/cp_new.js";

// ... inside initializeRegistry()
this.registerAll(CpNewApproaches);

Step 3: Use in ARES

ARES Source:

ares
read x as int
use new_alg on x

Emitted C++:

cpp
int n_x; cin >> n_x; long long x; cin >> x; // vector promotion logic (if x was vector)
// For simple int x:
long long x; cin >> x;
long long res = std::log2(x);

Mathematical Model

The total registry surface Stotal\mathcal{S}_{total} grows linearly with new additions: Stotal′=Stotal+δ(Anew)\mathcal{S}_{total}' = \mathcal{S}_{total} + \delta(A_{new}) Where δ(Anew)\delta(A_{new}) is the increase in the universal set of reachable intents.

Complexity

  • Registration Complexity: O(1)O(1) to append to the category array.
  • Resolution Complexity: O(1)O(1) average lookup in the registry hash map using the canonical name or alias.

Examples

Defining an Alias:

typescript
{
  name: "binary_search",
  aliases: ["lower_bound", "bsearch"],
  // templates...
}

Adding Dependencies:

typescript
{
  name: "hld",
  dependencies: ["dfs_sz", "decompose"],
  // templates...
}

Traces

Trace for ApproachRegistry.get("new_alg"):

  1. Retrieve name from dictionary.
  2. Follow aliases if applicable (recursive).
  3. Combine metadata and return the ApproachInfo object to the Emitter.
  4. Emitter identifies {{target}} and replaces it with the bound variable name.

Edge Cases

  • Naming Collisions: If a new approach has the same name as an existing one, the first one loaded (alphabetically by category file) is preserved.
  • Missing Backend Template: If a template is missing for a target backend, ARES will emit a "NOT_IMPLEMENTED" comment instead of crashing the compiler.
  • Recursive Dependencies: If an approach depends on itself, it triggers a 50-step overflow preventer in Phase 6.

Failure Modes

  • Syntax Errors in Templates: Will result in non-compilable output code in Phase 9, as ARES does not currently validate the static correctness of the registry snippets themselves.
  • Duplicate Aliases: May cause non-deterministic resolution if the same alias scales to multiple canonical names.

Compatibility

  • Tools: Any text editor capable of handling TypeScript.
  • Registry Loading: Automatically handled by ApproachRegistry during Phase 3.

Testing

  • Registry Load Test: tests/registry.test.ts ensures that after adding the new category to the indexer, registry.has("new_alg") returns true.
  • Template Substitution Check: Compiles a dummy script using the new approach and asserts that {{target}} was correctly replaced.

Related Entities

  • 8_registry_approaches/00_registry.md: Core architecture of the approach system.
  • src/types.ts: The schema to follow.

Source Attribution

  • Main Component: src/registry/approach_registry.ts.
  • Design Pattern: Strategy Pattern / Template Method.
ARES