[plinth][plc][api] Draft implementation of 'modularExponentiation' builtin

[bezirg]

This is a draft implementation. Supporting GHC8.10 for this builtin needs extra work; so we discussed with @zliu41 and postpone it for a bit later. So as not to make the whole CI not build anymore with GHC8.10, the implementation of this builtin always fails for GHC8.10. The builtin is not enabled to run yet on the chain.

Pre-submit checklist:

• Branch
  • [x] Tests are provided (if possible)
  • [x] Commit sequence broadly makes sense
  • [x] Key commits have useful messages
  • [x] Changelog fragments have been written (if appropriate)
  • [ ] Relevant tickets are mentioned in commit messages
  • [x] Formatting, PNG optimization, etc. are updated
• PR
  • [ ] (For external contributions) Corresponding issue exists and is linked in the description
  • [x] Targeting master unless this is a cherry-pick backport
  • [x] Self-reviewed the diff
  • [x] Useful pull request description
  • [x] Reviewer requested

[bezirg]

Nikos very helpfully explained to me that the builtin already behaves like I want it to. Conversion of the last argument to Natural filters out negative integers and integerPowMod# returns an explicit failure when the last argument is 0. So by my standards it's all good, I'd only like to see unit tests demonstrating all this behavior.

@bezirg could you please add unit tests to Evaluation.Builtins.Definition similar to all the other unit tests that we have there (like those in test_Integer, test_Crypto etc)?

I was planning to add tests in another PR (to keep the PRs smaller), but I regret it; I should have done it in this PR, then the behavior of the builtin would be shown.

I will add the tests here, and I will ask for a second round of review. Thank you all for your feedback!

[kwxm]

Nikos very helpfully explained to me that the builtin already behaves like I want it to. Conversion of the last argument to Natural filters out negative integers and integerPowMod# returns an explicit failure when the last argument is 0. So by my standards it's all good, I'd only like to see unit tests demonstrating all this behavior.

I'd prefer to put an explicit check for modulus > 0 in the builtin. integerPowMod# does this itself (although you only discover that by looking at its source code), but let's be sure in case something changes. I've looked at a number of implementations in different languages and libraries and so far I've found three different behaviours when the modulus is zero. There's no commonly-accepted agreement on what the behaviour should be, and none of the things I've looked at actually document what the behaviour is: you have to use trial and error or examine the code to find out. This is really fragile, so let's just ban it outright! I think we should accept m=1 always giving you a^b mod m = 0 since that seems to be pretty universal , but we should still add a test.

I'm still a bit sceptical about using Natural to enforce bounds for us. We already have multiple builtins that do their own bound checks, but now we have two ways of checking n>=0, which could be confusing. Maybe we should use Natural everywhere we do that though.

[effectfully]

I'd prefer to put an explicit check for modulus > 0 in the builtin.

Just to be clear, I don't mind that at all. Only saying that for me both the options work, so if you feel like we should really make it an explicit check, we can invoke the "whoever has the strongest opinion wins" clause.

This is really fragile

I don't think it is! We should cover all edge cases with tests. We can even make both unit and golden tests just to be dead sure that the behavior isn't gonna change. And I don't feel like making the check explicit will contribute much towards stability of behavior, given proper testing.

I think we should accept m=1 always giving you a^b mod m = 0 since that seems to be pretty universal , but we should still add a test.

:+1:

I'm still a bit sceptical about using Natural to enforce bounds for us. We already have multiple builtins that do their own bound checks, but now we have two ways of checking n>=0, which could be confusing. Maybe we should use Natural everywhere we do that though.

The underlying primitive base function has Natural in its type, so we just conveniently wrap it directly instead of checking the bounds manually and converting the Integer argument manually to Natural in order to pass it to the function. Less boilerplate and it's still pretty clear what's going on, since we do the same for Int64, Word8 etc etc. Again, no strong inclinations from me, but I feel like using Natural is pretty reasonable and follows existing conventions.

I do agree that there are two ways to check bounds (explicitly and implicitly) and it may be confusing, but both are used extensively, are we going to implement bounds checking manually for all the various integral types just so that all bounds checking is done explicitly?

[bezirg]

I added some unit tests. I didn't add random testing of the builtin because of the stub code i have for ghc8.10