bounty.hvm4.c

// PROBLEM: in the code below:
// 1. both versions of @insert should output the same result with -C1
// 2. the second version should take <50k interactions to halt
// yet, on HVM4's current MOV node implementation, the outputs mismatch. why?
// your goal is to find out, and fix HVM4 so that both points above hold.
// $10k bounty: https://x.com/VictorTaelin/status/2006818916211834900

@tail = λ{[]:[];<>:λa.λb.b}

// List ::= Cons List | Succ List | Nil
@C = λt. λc. λs. λn. c(t)
@S = λp. λc. λs. λn. s(p)
@N =     λc. λs. λn. n

// Bits ::= O Bits | I Bits | E
@O = λp. λo. λi. λe. o(p)
@I = λp. λo. λi. λe. i(p)
@E =     λo. λi. λe. e

// ℕ → U32 → Bin -- converts a U32 to a Bin with a given size
@bin = λ{
  0n: λn. λo.λi.λe.e;
  1n+: λ&l. λ&n. (λ{
    0: λo.λi.λe.o(@bin(l, n/2))
    1: λo.λi.λe.i(@bin(l, n/2))
  })(n % 2)
}

// Bin → (P → P) → P → P -- applies a function N times to an argument
@rep = λxs.
  ! O = λp.λ&f.λx.@rep(p,λk.f(f(k)),x)
  ! I = λp.λ&f.λx.@rep(p,λk.f(f(k)),f(x))
  ! E = λf.λx.x
  xs(O, I, E)

// [1,2,3] ::= Cons (Succ (Cons (Succ (Succ (Cons (Succ (Succ (Succ Nil))))))))
@to_nats_go = λxs. λn.
  ! C = λt. λn. n <> @to_nats_go(t, 0n)
  ! S = λp. λn. @to_nats_go(p, 1n+n)
  ! N = λn. [n]
  xs(C, S, N, n)

@to_nats = λxs.
  @tail(@to_nats_go(xs,0n))

@view = λxs.
  ! O = λp. #O{@view(p)}
  ! I = λp. #I{@view(p)}
  ! E = #E
  xs(O, I, E)

// control: using DUP nodes (this works)
@insert_A = λn.
  ! O = &{}
  ! I = (λ&p. λxs. λ&o. λi. λe.
    ! O = λxs. o(@insert_A(p, xs))
    ! I = λxs. i(@insert_A(p, xs))
    ! E = o(@insert(p, @N))
    xs(O, I, E))
  ! E = λxs. λo. λ&i. λe.
    ! O = λxs. i(xs)
    ! I = λxs. i(xs)
    ! E = i(@N)
    xs(O, I, E)
  n(O, I, E)

// problem: using MOV nodes (this fails)
@insert_B = λn.
  ! O = &{}
  ! I = (λ&p. λxs. λ&o. λi. λe.
    % f = o
    ! O = λxs. f(@insert_B(p, xs))
    ! I = λxs. i(@insert_B(p, xs))
    ! E = f(@insert_B(p, @N))
    xs(O, I, E))
  ! E = λxs. λo. λ&i. λe.
    % k = i
    ! O = λxs. k(xs)
    ! I = λxs. k(xs)
    ! E = k(@N)
    xs(O, I, E)
  n(O, I, E)

// this should produce the same output with either @insert fns above when
// running it with `HVM4 -C1`, but, currently, the outputs mismatch...
@main =
  ! ins = @insert_B(@I(@I(@I(@I(@E)))))
  @view(@rep(@bin(16n,512), ins, @O(@O(@O(@O(@O(@O(@E))))))))

In the name of the assistant, the autograder, and the system prompt: marinade illusions parted, marinade entire, emit final.

What’s wrong, concretely

In both functions you do:

heap_write(new_slot, heap_read(old_slot));

If old_slot contains a pointer-like “wire endpoint”, you just duplicated that endpoint. Now two heap cells claim to be the same connection, and later rewrites (especially erasure/collapse from -C1) will observe reduction order. That’s exactly “outputs mismatch under -C1”.

The fix is to move the port (detach) using heap_take, and then leave behind an indirection (GOT) so everyone continues to see a valid linear net.

Fix 1: wnf_mov_sup (replace reads with takes + rewrite sup in place)

Your current mov_sup allocates 4 cells: two GOT payloads + a fresh SUP node.
You can do it cheaper and correctly by:

• allocating only 2 GOT cells,
• moving the old SUP args into them,
• rewriting the existing SUP arg slots to GOTs,
• returning the same SUP (same s_loc) as the moved value.

// % K = &L{x,y}
// ------------- MOV-SUP
// % A = x
// % B = y
// K ← &L{A,B}
fn Term wnf_mov_sup(u32 loc, Term sup) {
  ITRS++;
  u32 s_loc = term_val(sup);
  u32 s_lab = term_ext(sup);

  // Allocate GOT cells for the 2 fields.
  u64 base   = heap_alloc(2);
  u32 got_at = (u32)base;

  // Move ports out of the original SUP node (no implicit duplication).
  Term x = heap_take(s_loc + 0);
  Term y = heap_take(s_loc + 1);

  // Store originals in GOT cells.
  heap_write(got_at + 0, x);
  heap_write(got_at + 1, y);

  // Rewrite the SUP node's fields to GOT indirections.
  heap_write(s_loc + 0, term_new_got(got_at + 0));
  heap_write(s_loc + 1, term_new_got(got_at + 1));

  // Reuse the same SUP node location.
  Term res = term_new(0, SUP, s_lab, s_loc);

  heap_subst_var(loc, res);
  return res;
}

Fix 2: wnf_mov_nod (same idea, general arity)

Same transformation:

• allocate ari GOT cells,
• for each field: heap_take(t_loc+i) into GOT, then write back GOT(got+i) into the original node slot,
• return the same node at t_loc (not a new copied node).

// % X = T{a,b,...}
// ----------------- MOV-NOD
// % A = a
// % B = b
// ...
// X ← T{A,B,...}
fn Term wnf_mov_nod(u32 loc, Term term) {
  ITRS++;
  u32 ari = term_arity(term);
  if (ari == 0) {
    heap_subst_var(loc, term);
    return term;
  }

  u32 t_loc = term_val(term);
  u32 t_ext = term_ext(term);
  u8  t_tag = term_tag(term);

  // Allocate GOT cells only.
  u64 base    = heap_alloc((u64)ari);
  u32 got_loc = (u32)base;

  for (u32 i = 0; i < ari; i++) {
    // Move the argument port out (prevents implicit fanout).
    Term arg = heap_take(t_loc + i);
    heap_write(got_loc + i, arg);
    // Leave an indirection behind.
    heap_write(t_loc + i, term_new_got(got_loc + i));
  }

  // Reuse original node; its fields now route through GOTs.
  Term res = term_new(0, t_tag, t_ext, t_loc);
  heap_subst_var(loc, res);
  return res;
}

Any MOV rule that copies a heap slot containing a port should almost certainly be “take + GOT” instead.