Add MIPS with MARS 4.5

[DonaldKellett]

Please complete the following information about the language:

• Name: MIPS
• Website: http://courses.missouristate.edu/kenvollmar/mars/
• Language Version: MARS 4.5

The following are optional, but will help us add the language:

• Test Frameworks: customized testing framework written in MIPS for Codewars
• How to install:
  • Install a sufficiently recent Java runtime
  • Download the JAR: https://courses.missouristate.edu/KenVollmar/mars/MARS_4_5_Aug2014/Mars4_5.jar
• How to compile/run: Run it with java -jar /path/to/Mars4_5.jar ... where ... denotes command line arguments passed to MARS. Use h for help: java -jar /path/to/Mars4_5.jar h

MIPS is a RISC ISA which is commonly used in computer architecture courses taught in universities, for its simplicity compared to CISC ISAs such as the mainstream x86 architecture. RISC ISAs such as RISC-V and LoongArch are also gaining traction in the industry in recent years, so I think support for a RISC assembly language on Codewars would be an interesting addition.

Addendum: MIPS support was previously requested in #22 but fizzled out due to lack of interest and expertise in migrating MIPSUnit from JUnit 4 to JUnit 5. This time, I'll look into writing a minimal custom test framework wrapping command-line versions of existing simulators such as MARS or SPIM, and post updates here when there is progress.

---

• Choose a suitable emulator - MARS 4.5
• Figure out how to run user submissions - MARS 4.5 has a fairly documented CLI that can be used non-interactively
• Figure out how to validate user submissions - using a custom unit testing framework implemented in MIPS
  • Implement and demonstrate common assertions for integers
  • Implement and demonstrate common assertions for strings
  • Implement and demonstrate common assertions for arrays
  • Demonstrate the feasibility of implementing random tests

---

👍 reaction might help to get this request prioritized.

[DonaldKellett]

Created a repo https://github.com/DonaldKellett/codewars-mips to experiment with the idea

Initial idea: instead of integrating with MARS directly with Java JUnit (like what MIPSUnit does), use a multi-file setup and develop assertions that print Codewars output format in MIPS, then invoke MARS with the project files and use its output as the final runner output

[DonaldKellett]

@kazk I've written a minimal unit testing framework in MIPS that provides basic assertions for integer values, and an example examples/multiply/ that utilizes the framework. If desired, the repo can be transferred to Codewars now for further development and maintenance.

I'll probably also add basic string and (maybe) array assertions shortly, which should cover most typical cases.

EDIT (2022-07-24 14:53 GMT+8): I realized that transferring repo ownership to @codewars requires permissions to create a new public repo on their behalf so I've initiated transfer to @kazk instead.

UPDATE (2022-07-24 20:16 GMT +8): Basic string assertions have also been implemented and demoed in examples/string-reverse/. I probably won't have time today to implement array assertions, but I might add them another day depending on workload.

[kazk]

What are the differences from MIPS (#22)? Just testing it differently?
How different are the MIPS versions? This one is MIPS32 only? Which version is typically used?

I get that the easiest way to implement is to write tests in MIPS, but isn't it annoying to write? I'd like to know what potential authors think.

[DonaldKellett]

What are the differences from MIPS (#22)? Just testing it differently?

Mostly. The approach we tried 2 years ago was to adapt the existing MIPSUnit framework to output Codewars output format and migrate it from JUnit 4 to JUnit 5, which proved to be too tedious and cumbersome.

MIPSUnit integrates directly with MARS, which means it can inspect the state of the (emulated) processor directly, allowing assertions to be written about values of specific registers etc. However, this method of testing is vastly different from that taken by NASM (and pretty much every other language) on Codewars, where we only care about the return value of the solution for the most part.

How different are the MIPS versions? This one is MIPS32 only? Which version is typically used?

If you mean compared to #22 , no difference at all. The two most well-known MIPS emulators MARS and SPIM both emulate (a substantial subset of) MIPS32 only, with the former being more feature-complete. There might be MIPS64 emulators out there, but they're nowhere near as popular as those two and the ones I found seem to be GUI-only, or at least do not have a sufficiently documented command-line interface.

I get that the easiest way to implement is to write tests in MIPS, but isn't it annoying to write? I'd like to know what potential authors think.

It's not that much different from writing assertions in a higher-level language, actually. The general flow for writing an assertion is (1) compute the expected value (trivial for fixed tests), (2) invoke the solver's solution to compute the actual value, then (3) set up the argument registers correctly and (4) invoke the assertion method. For fixed tests at least, that is often under 10 instructions per assertion and much of it is repetitive work that can be copy-pasted.

[DonaldKellett]

Cross-posting from Discord for reference:

@nomennescio wrote:

Preferably, testcode should be written in C, not assembly.

donaldsebleung (@DonaldKellett ) wrote:

On a serious note, I wonder how much effort would be required though

I briefly mentioned the possibility of leveraging cross-compilation (x86_64 --> MIPS32) back in #22 , but looking back, it might not be nearly as straightforward, since the (emulated) MIPS processor in MARS isn't running a standard OS kernel like Linux, so we can't just, say, target Linux on MIPS32 and call it a day
It isn't freestanding either, so I doubt targeting MIPS32-elf or whatever would work either
It's kinda running a highly customized operating system specific to MARS, which also happens to be a superset of that used in SPIM (also highly customized)

[DonaldKellett]

I just re-discovered this StackOverflow question from #22 : Calling MIPS from C. The top-voted solution suggests that Open Virtual Platforms (OVP) provides a full-blown MIPS simulator that boots and runs Linux.

However, upon digging further into OVP, here are a few concerns I uncovered which suggest the solutions offered by OVP may not be suitable at all for our use case:

• Since it's a full-blown MIPS emulator running Linux and not a simplified one like MARS / SPIM, we'd probably need to boot the emulated machine before being able to process any submission code at all. Linux boot times are typically fast in the order of seconds (and perhaps ms for embedded Linux), but (1) emulation is gonna slow it down and (2) either way, would it be an acceptable overhead for every submission?
• The emulators are distributed as 32-bit binaries only as far as I can see - probably not a problem though since 64-bit Linux should be able to run 32-bit userspace programs
• Accessing any of the downloads requires creating an account on OVP, which isn't a big problem per se, but I'd rather not just for the purpose of testing them out for Codewars
• Some core components are distributed under an open-source license (modified Apache 2.0), but in particular, "the larger platforms (typically those including OS support) and the tools do need a license key", which suggests anything that could be remotely useful are proprietary and probably (1) requires some form of payment, and/or (2) has restrictions on its usage that forbids commercial use like on Codewars
• On the main download page, the only emulated MIPS processors with Linux I could find all boot Linux 2.6 only, which is a downright ancient kernel. Even if we get the emulator to boot successfully and manage to set up some sort of basic C (cross-)compiler, I'm not sure any sufficiently recent version of existing unit testing frameworks like Criterion would run on it

Since the primary objective of Codewars is education, I personally think that it isn't worth going the extra mile to find a full-blown emulator that models every tiny little detail of hardware proper. Most CS/CPEG/EE students having taken a computer organization course have probably been exposed to MARS or SPIM, and the former is effectively a superset of the latter, so I think using MARS should be good enough, not to mention that documentation and external resources for MARS MIPS are abundant and probably even better than that for Linux on MIPS.

As for the original approach in #22 of adapting MIPSUnit for Codewars and migrating it from JUnit 4 to JUnit 5, I'm not sufficiently well-versed in the Java ecosystem to undertake the work, so if someone else would like to take over, they're welcome to do so. The source code for MIPSUnit could be obtained by contacting @kurmasz , though we might need to ask for permission again to adapt it for Codewars since it's not released as open-source and it's been 2 full years since we last asked. But if no one is willing to step up and undertake the work related to MIPSUnit, I'll go with perfecting my custom assertion framework in MIPS in the meantime since that seems to be the next sensible option, and one that doesn't require me to learn the ins and outs of the Java ecosystem.

[DonaldKellett]

Further discussion on Discord replicated here for reference.

donaldsebleung (@DonaldKellett ) wrote:

Unless I'm terribly mistaken, the situation with MIPS is completely different from x86 (by which I suppose you mean x86_64?)

x86_64 is the native architecture for the cloud instances used by Codewars, so to integrate a solution written in x86_64 assembly with unit tests written in C, one just has to pass in specific flag(s) to compile the C unit tests down to assembly, then assemble it with the solver's solution using the same toolchain. No emulation needed, no cross-compilation needed

But for MIPS, since it isn't native, one has to run an emulator for it and use a cross-compiler at the very least, which already isn't as straightforward as using an ordinary compiler. But to compound the problem, the (emulated) MIPS processor in MARS doesn't even run a standard operating system like Linux, so there probably isn't any ready-made cross compiler that targets MARS MIPS specifically, i.e. you have to develop your own cross-compiler. At this point, this is starting to sound like OSDev level stuff that I'm not convinced is remotely worth the effort just to get MIPS support onto Codewars

@nomennescio wrote:

Running an emulator might be an option, but that's not the only option. As CW requires calls to functions only, using the C test framework seems not a bad idea. I wouldn't bother about supporting any I/O inside MIPS functions (so also no printf debugging...). But I agree, it's not exactly trivial. You for sure would need a cross-compiler anyway, as the host platform is Linux. Sorry, but as much as I admire your efforts, I currently don't have time to add much.

[DonaldKellett]

@kazk Common array assertions have been implemented and demoed as well. If everything over at https://github.com/DonaldKellett/codewars-mips looks good to you and there are no strong last-minute objections to the approach used there, we should be ready to officially deploy MIPS (Beta) support to Codewars.

[kazk]

Can you run failing examples in CI?
Also, what happens when the solution contains a syntax error or an invalid register name? Can you add examples for that and include it in CI as well?

[kazk]

It's missing <COMPLETEDIN::> for each test case.

[kazk]

It's not that much different from writing assertions in a higher-level language, actually. The general flow for writing an assertion is (1) compute the expected value (trivial for fixed tests), (2) invoke the solver's solution to compute the actual value, then (3) set up the argument registers correctly and (4) invoke the assertion method. For fixed tests at least, that is often under 10 instructions per assertion and much of it is repetitive work that can be copy-pasted.

How the assertions work is obviously similar, but the tests are difficult to read without duplicating static strings in comments like you did.

But like you wrote above, I can't think of a reasonable alternative for MIPS.

RISC ISAs such as RISC-V and LoongArch are also gaining traction in the industry in recent years, so I think support for a RISC assembly language on Codewars would be an interesting addition.

I think we can support RISC-V instead with a similar setup as ARM I experimented in #197 (comment). By running ARM/RISC-V container with QEMU emulation, I think we can test using Criterion like NASM. (I'm assuming Criterion can be compiled from the source when building the image.)

[DonaldKellett]

Thanks for the feedback - I'll implement them tonight if time allows.

It's missing <COMPLETEDIN::> for each test case.

Do you mean that each <IF::> block should have a corresponding <COMPLETEDIN::> as well? E.g.

<DESCRIBE::>The multiply() function
<IT::>should work for some fixed tests
<PASSED::>Test Passed
<COMPLETEDIN::>
<IT::>should work for some random tests
<PASSED::>Test Passed
<PASSED::>Test Passed
<PASSED::>Test Passed
<COMPLETEDIN::>
<COMPLETEDIN::>

I think we can support RISC-V instead with a similar setup as ARM I experimented in #197 (comment). By running ARM/RISC-V container with QEMU emulation, I think we can test using Criterion like NASM. (I'm assuming Criterion can be compiled from the source when building the image.)

Sure, I'll probably look into adding RISC-V support afterwards, but IMHO MIPS and RISC-V support need not be mutually exclusive as they are distinct architectures, like how C# and Java are distinct programming languages.

[kazk]

Yeah, <IT::> should have <COMPLETEDIN::>. See https://github.com/codewars/runner/blob/main/docs/messages.md#test-structure

IMHO MIPS and RISC-V support need not be mutually exclusive

It doesn't need to be. But what are some reasons to support MIPS in addition to RISC-V?

I don't think we should add MIPS just because we can, especially if the user experience isn't great (I don't think tests in assembly will be for both authors/maintainers and solvers). We can consider adding it later if we find a better way as well.

like how C# and Java are distinct programming languages.

Isn't it more like ActionScript and TypeScript?

[DonaldKellett]

Closing in favor of #199

The link posted in #197 (comment) also mentions mips64le as an available architecture, but I suppose we should focus on getting RISC-V out first and decide later whether to support MIPS64 as well based on demand.