Though the program can be executed sequential, the parallel interpretation seems never terminates.

[naiiren]

Reproducing the behavior

I was trying to use Bend to simulate the behavior of an 8-bit carry-lookahead adder circuit. I found that the program runs successfully with the sequential Rust interpreter using bend run-rs test.bend -s. It produces the output

Result: 65536
- ITRS: 96731497
- TIME: 2.36s
- MIPS: 41.01

However, the execution seems to never terminate when I try either:

bend run-c test.bend -s
bend run-cu test.bend -s

It’s worth noting that the problem does not occur when testing a 7-bit or smaller adder program. The issue only arises when testing an 8-bit adder program like the one below. I’m wondering if this behavior indicates a bug in Bend or if it’s due to a mistake in my program. Thanks in advance for any insights!

Below is the test.bend program I was running, and modifying the last two lines of the program allows me to change the bit-width of the adder.

type Bool:
  True
  False

def not(a: Bool) -> Bool:
  match a:
    case Bool/True:
      return Bool/False
    case Bool/False:
      return Bool/True

def or(a:Bool, b: Bool) -> Bool:
  match a:
    case Bool/True:
      return Bool/True
    case Bool/False:
      return b

def and(a: Bool, b: Bool) -> Bool:
  match a:
    case Bool/True:
      return b
    case Bool/False:
      return Bool/False

def xor(a: Bool, b: Bool) -> Bool:
  match a:
    case Bool/True:
      return not(b)
    case Bool/False:
      return b

def half_adder(a: Bool, b: Bool) -> (Bool, Bool):
  return (xor(a, b), and(a, b))

def full_adder(cin: Bool, a: Bool, b: Bool) -> (Bool, Bool):
  (s1, c1) = half_adder(a, b)
  (s2, c2) = half_adder(s1, cin)
  return (s2, or(c1, c2))

def app(head: Bool, list: List(List(Bool))) -> List(List(Bool)):
  match list:
    case List/Nil:
      return List/Nil
    case List/Cons:
      return List/Cons(
        List/Cons(head, list.head), 
        app(head, list.tail))

def gen(n: u24) -> List(List(Bool)):
  if n == 1:
    return [[Bool/True], [Bool/False]]
  else:
    return List/concat(
      app(Bool/True, gen(n - 1)), 
      app(Bool/False, gen(n - 1)))

def adder(a: List(Bool), b: List(Bool)) -> (List(Bool), Bool):
  match a:
    case List/Nil:
      return ([], Bool/False)
    case List/Cons:
      match b:
        case List/Nil:
          return ([], Bool/False)
        case List/Cons:
          sum_t, cout_t = adder(a.tail, b.tail)
          sum, cout = full_adder(cout_t, a.head, b.head)
          return (List/Cons(sum, sum_t), cout)

def test_on_b(a: List(Bool), b: List(List(Bool))) -> List(List(Bool)):
  match b:
    case List/Nil:
      return List/Nil
    case List/Cons:
      sum, cout = adder(a, b.head)
      return List/Cons(sum, test_on_b(a, b.tail))


def test_on_a(a: List(List(Bool)), b: List(List(Bool))) -> List(List(Bool)):
  match a:
    case List/Nil:
      return List/Nil
    case List/Cons:
      return List/concat(test_on_b(a.head, b), test_on_a(a.tail, b))


def main() -> u24:
  length, _ = List/length(test_on_a(gen(8), gen(8))) # Change '8' to modify bit-width
  return length

System Settings

Running with:

• HVM: 2.0.22
• Bend: 0.2.37
• OS: Linux (Ubuntu 24.04)
• CPU: Intel i9-13900H
• GPU: RTX 4070 Max-Q
• Cuda Version: release 12.0, V12.0.140

Additional context

No response

[naiiren]

Also, there is a typo in the README. It says in the section Running Bend Programs that bend run uses the sequential rust interpreter as default, but in the section Running the file, it says the command uses the parallel C interpreter by default.

[developedby]

It's also very suspicious how the program gets slower with run-c even though it has a reasonable degree of parallelism

[wirkelzirkel]

Is this the same issue as #538 ? If it is, there is unfortunately no fix yet.