hvm-problem.md

Based on the code you shared and the HVM3 codebase I've reviewed, I can explain why you're seeing four universes instead of two when the program collapses.

Understanding the Collapse Mechanism

Looking at the HVML.Collapse module, the issue is related to how HVM3 handles superpositions (represented with the & notation in the code). The collapseDupsAt and collapseSups functions create a tree structure that represents all possible combinations of choices.

Why You're Getting 4 Universes

The key is in how the code processes nested superpositions. In your example:

//! a = λb λc #P{
  //&2{* &2{d        &2{e               *}}}
  //&2{* &2{&3{* &3{* &3{f *}}} &2{&3{* &3{g &3{* *}}} *}}}}

This creates nested superposition layers:

• An outer &2 superposition
• Inside each branch of the outer superposition is another &2 superposition
• Some branches contain further &3 superpositions

When the flatten function processes this tree structure in the doCollapseFlatAt function, it produces all possible combinations, which is a cartesian product of the choices at each level.

In your specific case:

• You have 2 choices at the outer level
• Each of those has 2 choices at the inner level
• This creates 2×2 = 4 possible combinations

The Relevant Code

The culprit is in the flattenBFS function in HVML.Collapse:

flattenBFS :: Collapse a -> [a]
flattenBFS term = go term (SQ [] [] :: SQ (Collapse a)) where
  go (CSup k a b) sq = go CEra (sqPut b $ sqPut a $ sq)
  go (CVal x)     sq = x : go CEra sq
  go CEra         sq = case sqPop sq of
    Just (v,sq) -> go v sq
    Nothing     -> []

This function traverses the collapse tree in breadth-first order, pushing both branches of each superposition onto a queue. It effectively explores all possible combinations of choices, resulting in 4 outcomes instead of 2.

Why You Expected 2

You might have expected only 2 universes because you're thinking of each &2 as a binary choice that replaces the previous choice, rather than creating a product of all choices. However, the collapse mechanism is designed to enumerate all possible combinations.

If you want just 2 universes, you'd need to structure your code differently, perhaps by avoiding nested superpositions or by using a different encoding that makes certain dependencies explicit.

In summary, the behavior you're seeing is a consequence of how HVM3's collapse mechanism is designed to handle superpositions - it creates all combinations of choices at different levels, resulting in a multiplicative effect on the number of outcomes.

Improvement possibilities

To improve the flattenBFS function in the HVM3 code, I would focus on addressing the issue you encountered where it produces all combinations of superpositions rather than preserving the hierarchical relationships. Here's how I would improve it:

flattenBFS :: Collapse a -> [a]
flattenBFS term = go term (SQ [] [] :: SQ (Collapse a)) [] where
  -- Add a tracking parameter for active labels
  go (CSup k a b) sq activeLabels 
    | k `elem` activeLabels = 
        -- If this label is already active, treat as a nested choice within the same group
        go a sq activeLabels ++ go b sq activeLabels
    | otherwise = 
        -- Otherwise, start a new choice group
        go a sq (k:activeLabels) ++ go b sq (k:activeLabels)
  go (CVal x) sq _ = x : go CEra sq []
  go CEra sq activeLabels = case sqPop sq of
    Just (v,sq) -> go v sq activeLabels
    Nothing     -> []

Why This Improvement Is Needed:

1. Respects Hierarchical Superpositions: The current implementation treats each superposition independently, resulting in combinatorial explosion. The improved version tracks which superposition "contexts" are active.

2. Preserves Semantic Intent: In your example, nested superpositions with different labels (&2 and &3) likely represent different decision points in the program. The improved version respects this by tracking active labels.

3. Prevents Exponential Growth: With the current implementation, N nested superpositions produce 2^N outcomes. The improved version would produce outcomes proportional to the number of superpositions rather than their combinations.

4. Maintains Quantum-Like Behavior: If we want the system to mimic quantum computing's notion of entangled states, then superpositions with the same label should remain "entangled" across the program.

5. Improves Performance: Beyond correctness, this approach would significantly reduce the number of states that need to be processed, improving performance for complex programs.

The fundamental issue is that the current flattening algorithm doesn't preserve the relationships between superpositions - it flattens the tree structure completely. My improved version maintains the relationships by tracking the context of each superposition, ensuring that nested superpositions with the same label are treated as part of the same decision rather than independent choices.

This would fix your "4 universes" problem by recognizing that the nested superpositions should collapse to just 2 universes instead of all possible combinations.