[bug]: DMux4Way passes tests in Java version, fails in Web IDE

[hoosierEE]

Program

Hardware Simulator

Interface

Website (https://nand2tetris.github.io/web-ide)

Contact Details

No response

What happened?

The same DMux4Way.hdl file passes all the tests when run in the legacy Java HardwareSimulator, but the Web IDE HardwareSimulator fails with this output:

|in | sel  | a | b | c | d |
| 0 |  00  | 0 | 0 | 0 | 0 |
| 0 |  01  | 0 | 0 | 0 | 0 |
| 0 |  10  | 0 | 0 | 0 | 0 |
| 0 |  11  | 0 | 0 | 0 | 0 |
| 1 |  00  | 1 | 0 | 0 | 0 |
|   |      | 0 |   |   |   |
| 1 |  01  | 0 | 1 | 0 | 0 |
| 1 |  10  | 0 | 0 | 1 | 0 |
|   |      | 1 |   | 0 |   |
| 1 |  11  | 0 | 0 | 0 | 1 |

Copy-pasted same code into Java simulator, all tests pass:

NOTE: I dug a little deeper and it appears that the order of chip-part declarations is significant on the Web IDE.

For example this chip:

CHIP Foo {
  OUT out;
  PARTS:
  Not(in=true, out=x); // comment
  Not(in=x, out=out);
}

appears to work differently from this chip:

CHIP Foo {
  OUT out;
  PARTS:
  Not(in=x, out=out);
  Not(in=true, out=x); // comment
}

Did the language semantics change to make order significant?

Additional Comments

No response

Do you want to try to fix this bug?

• [ ] I want to try to add this feature!

Code of Conduct

• [X] I agree to follow this project's Code of Conduct

[hoosierEE]

I was looking at the code to see if I could offer a fix and I suspect it may be related to the ordering in the eval function (as noted in the // TODO topological sort comment here in the chip's eval method.

But I'm not sure if the sorting is the root cause, because the DFF chip has no clear "first" or "last" and it works regardless of the order of the part declarations, so that's a counterexample going against my hunch. 🤷

Also I realized my earlier example may be too trivial to reproduce so here's a complete example.

Fails tests on web-ide, passes Java tests:

CHIP Mux4Way16 {
  IN a[16],b[16],c[16],d[16],sel[2];
  OUT out[16];
  PARTS:

  Mux16(a=m0,b=m1,sel=sel[1],out=out); // NOTE position of this line

  Mux16(a=a,b=b,sel=sel[0],out=m0);
  Mux16(a=c,b=d,sel=sel[0],out=m1);
}

Passes tests (both web-ide and Java):

CHIP Mux4Way16 {
  IN a[16],b[16],c[16],d[16],sel[2];
  OUT out[16];
  PARTS:

  Mux16(a=a,b=b,sel=sel[0],out=m0);
  Mux16(a=c,b=d,sel=sel[0],out=m1);

  Mux16(a=m0,b=m1,sel=sel[1],out=out); // NOTE position of this line
}

[DavidSouther]

@hoosierEE thank you for the issue!

did the semantics change

Well, no, but the semantics were never formally defined, so the reliance has been on developing test cases that show possible points of divergence. Thank you for bringing this one to our attention!

Thank you also for digging into the issue! That comment comes from a similar comment at https://github.com/nand2tetris/nand2tetris_simulator/blob/master/SimulatorsPackageSource/Hack/Gates/CompositeGate.java#L25-L26.

The sort is performed here https://github.com/nand2tetris/nand2tetris_simulator/blob/master/SimulatorsPackageSource/Hack/Gates/CompositeGateClass.java#L82C43-L82C58

If you'd like to take a shot at it, please let me know!

[DavidSouther]

If you do pick it up, or for whomever does get to it - the Java graph impl is, IMHO, overbuilt for the task at hand. As most chips have only a handful of elements, and the full CPU only has a couple dozen, solutions should should optimized for that size.

To that end, I would suggest not pulling in any graph libraries (dagre, tsabre, agathon, etc). Instead, change Chip.parts to be an array; ensure uniqueness by other means when adding to Chip.parts, and provide a finalize method on Chip that uses a comparator to sort the parts array. The comparator should return -1 when a wires directly to b, 1 when b wires directly to a, and 0 when either there is a cross wiring (that's OK and will be allowed here with stable sort going by file-order precedence) or when there is no direct connection between the two.

[hoosierEE]

I'm pretty new to TypeScript but I'll give it a shot.

[DavidSouther]

Hey, sorry I missed your response - I was working on a few pieces last night and did this one as well. https://github.com/nand2tetris/web-ide/pull/309 - turned into a bit bigger change than I expected, because the chip wasn't tracking where pins had been connected.

[hoosierEE]

Awesome. Yeah I can see how the lack of a formal HDL specification can lead to needing to make sweeping changes.

[DavidSouther]

Leave it open until the PR lands