Implementing Delimited Continuations in TypeScript

This challenge involves creating a type-safe implementation of delimited continuations in TypeScript. Delimited continuations are a powerful control flow mechanism that allows you to capture and manipulate the execution stack. This can be used for advanced programming patterns such as coroutines, backtracking, and effect systems.

Problem Description

You are tasked with designing and implementing a TypeScript type system that models delimited continuations. This system should allow for capturing a computation up to a certain point (the delimiter) and returning it as a value. This captured computation (the continuation) can then be invoked later, potentially with a different return value, resuming the original computation from where it was paused.

Key Requirements:

Continuation Type Definition: Define TypeScript types that represent a delimited continuation. This type should capture:
- The type of the value the delimited computation is expected to produce.
- The type of the value that will be used to re-invoke the continuation.
callcc (Call-by-Current-Continuation) Function: Implement a generic function named callcc. This function should take a higher-order function as an argument. This higher-order function will receive a captured continuation as its own argument. The callcc function should:
- Capture the current execution context (the continuation) up to the point of the callcc call.
- Pass this captured continuation to the provided higher-order function.
- The result of the higher-order function will be the final result of the callcc call, unless the continuation is explicitly invoked with a new value.
Continuation Invocation: Provide a mechanism to "invoke" a captured continuation with a new value. This invocation should "jump" back to the point where the continuation was captured and resume execution, but now using the new value instead of the original one.
Type Safety: The entire implementation must be strictly type-safe. TypeScript's type system should prevent invalid usages, such as invoking a continuation with a value of the wrong type or passing incompatible functions to callcc.

Expected Behavior:

A callcc block should behave like a normal function call until a continuation is captured and passed to the inner function.
When the inner function invokes the captured continuation with a value, the execution should immediately return that value from the callcc call, effectively abandoning the rest of the computation within the inner function.
If the inner function returns a value without invoking the continuation, that value becomes the result of the callcc call.

Edge Cases:

What happens if the continuation is invoked multiple times? (The current implementation might not support this, but consider the implications).
Nested callcc calls.

Examples

Example 1: Simple Return

// Assume callcc is implemented
const result1 = callcc((continuation) => {
  return 42; // No continuation invoked, simply returns a value
});

console.log(result1); // Expected output: 42

Example 2: Invoking Continuation

// Assume callcc is implemented
const result2 = callcc((continuation: (value: number) => never) => {
  console.log("Before continuation call");
  continuation(100); // Invoke continuation with value 100
  console.log("This will not be printed");
  return 99; // This return will be ignored
});

console.log(`Continuation returned: ${result2}`); // Expected output: Continuation returned: 100

Explanation: The callcc function is called. The inner lambda receives a continuation. It logs "Before continuation call", then calls continuation(100). This causes the callcc to immediately return 100. The subsequent console.log and return 99 within the inner lambda are never executed.

Example 3: Nested Scenario (Illustrative - actual implementation needed)

// Assume callcc is implemented

const result3 = callcc(outerCont => {
  console.log("Outer callcc started");
  const innerResult = callcc(innerCont => {
    console.log("Inner callcc started");
    outerCont(123); // Invokes the outer continuation
    return 5; // This return is never reached
  });
  console.log("This line after inner callcc might not be reached depending on outerCont behavior");
  return innerResult; // This return might be ignored if outerCont is invoked
});

console.log(`Final result: ${result3}`); // Expected output: Final result: 123 (if outerCont is invoked)

Explanation: The outer callcc starts. It then enters an inner callcc. Inside the inner callcc, outerCont(123) is called. This immediately unwinds the execution back to the point where the outer callcc was called, returning 123. The innerResult is never determined, and the execution within the inner callcc stops. The console.log and return innerResult in the outer callcc are also not reached.

Constraints

TypeScript Version: Use a recent stable version of TypeScript (e.g., 4.x or later) that supports advanced type features.
No External Libraries: Do not use any external libraries or Node.js built-in modules that directly implement continuations or similar control flow mechanisms. Your solution must be purely in TypeScript.
Runtime Behavior: The implementation might involve some runtime tricks (e.g., using exceptions or specific function constructs) to achieve the stack manipulation, but these should be abstracted away by the types and the callcc function.
Performance: While not the primary focus, the implementation should aim for reasonable performance characteristics. Avoid overly inefficient recursive type instantiations if possible.

Notes

This is a challenging problem that requires a deep understanding of TypeScript's type system and how to model complex control flow.
Consider how you can use features like conditional types, infer keywords, and potentially recursive types to define your continuation types.
Think about how to represent the "never returning" nature of a continuation invocation within the type system. The never type might be useful here.
The runtime implementation of callcc will likely involve some form of exception handling or a generator-like pattern to simulate jumping between execution points. The goal is to abstract this complexity behind a clean, type-safe API.
Success is defined by a type-safe implementation that correctly models the behavior of delimited continuations as demonstrated in the examples.