Seq Bug: Type Checker Fails With 'n Roll' In If/Else

Hey there, fellow Seq enthusiasts! Today, we're diving into a rather peculiar bug that can sneak up on you when you're working with conditional logic in your Seq programs. It involves the humble n roll operation and how the type checker sometimes gets a little too enthusiastic about what's happening on the stack. Let's break down this Type checker bug: n roll inside if/else causes phantom 'roll_input' stack item and see what's going on.

The Nitty-Gritty of the Bug: n roll and Conditional Chaos

So, imagine you're writing some Seq code, and you've got an if/else statement. Pretty standard stuff, right? Now, within one of those branches, you decide to use n roll – you know, the operation that takes the n-th item from the top of the stack and brings it to the top, reordering things but not changing the overall stack depth. The weird thing is, when n is a literal integer (like 3 roll or 5 roll), the Seq type checker throws a bit of a fit. It starts reporting an extra, phantom stack item, something like roll_input$N, in the type signature of the branch where n roll is used. This mismatch in expected stack effects between the if and else branches is a real headache, as it prevents your code from compiling.

This particular Type checker bug: n roll inside if/else causes phantom 'roll_input' stack item is quite specific. It doesn't happen if you use n roll outside of any conditional blocks. It also seems to have a kinship with the n pick operation, which exhibits similar weird behavior in these contexts. Interestingly, simpler stack manipulation primitives like rot (which is essentially a specialized 3 roll) don't cause this issue when used inside conditionals. This suggests the bug is tied to how the type checker handles parameterized stack operations within conditional logic, rather than stack manipulation in general.

We've got a minimal reproduction case that perfectly illustrates the problem. Let's look at it:

# CASE 1: 3 roll outside conditional - WORKS
: works-outside ( Int Int Int Int -- Int Int Int Int )
  3 roll ;

# CASE 2: 3 roll inside else branch - FAILS
: fails-inside ( Int Int Int Int -- Int Int Int Int )
  dup 0 = if
    # then branch: no-op
  else
    3 roll
  then ;

# CASE 3: rot inside else branch - WORKS
: works-rot ( Int Int Int -- Int Int Int )
  dup 0 = if
  else
    rot  # Works! rot is a primitive
  then ;

: main ( -- )
  1 2 3 4 works-outside drop drop drop drop
  "done" io.write-line ;

When you try to compile fails-inside, you'll hit the error message:

Error: if/else branches have incompatible stack effects:
  then branch produces: (..rest Int Int Int Int)
  else branch produces: (..rest Int Int Int Int roll_input$3)
  Both branches of an if/else must produce the same stack shape.

See that roll_input$3? That's the phantom item causing all the trouble. The then branch correctly shows no change in stack effect, while the else branch, which also should have no net change, is flagged with this extra item. It's like the type checker is getting confused about whether the 3 roll actually added something to the stack when it was just rearranging it.

Why Does This Happen? A Deep Dive into the Type Checker's Logic

To truly understand this Type checker bug: n roll inside if/else causes phantom 'roll_input' stack item, we need to peek under the hood of Seq's type checker. The core of the problem lies in how the type checker attempts to unify the stack effects of different code branches, particularly within conditionals like if/else. Ideally, for a conditional to be valid, both the then and else branches must result in the exact same stack transformation. This means if you start with ( A B C -- X Y ) before the if, you must end with ( A B C -- X Y ) after the then and after the else.

When n roll (or n pick) is used inside a branch, Seq's type checker, during its analysis, seems to incorrectly associate a temporary, abstract stack item with these operations. It's as if it's trying to represent the input to the n roll operation itself as a distinct entity on the stack before the operation is conceptually completed. So, for 3 roll, it might internally think, "Okay, I need to operate on the 3rd item, so let's note that there's a roll_input$3 involved here." The issue is that this roll_input$N marker isn't being properly consumed or cancelled out by the n roll operation itself within the context of the type checker's unification algorithm when that operation is nested inside a conditional.

Contrast this with primitives like rot. When rot is used, the type checker likely has a direct, hardcoded understanding of its stack effect: it's a fixed permutation of the top three items. There's no ambiguity, and no intermediate "input" marker is generated that could be misinterpreted. For parameterized operations like n roll, the type checker might be using a more generic analysis that fails to account for the specific semantics of stack permutation within the conditional's unification process. It treats the parameter n as introducing a variable element that needs tracking, and this tracking mechanism gets entangled when the operation is guarded by an if or else.

Furthermore, the bug doesn't manifest when n roll is used at the top level. This suggests that the conditional structure introduces a layer of complexity in the type checker's state management. When analyzing if/else, the checker often needs to establish a common type context or