Reorganizing V’s Random Library

Update (September 2021)

I moved this post from my main website to this WordPress instance. There are some minor changes, but the content is mostly the same, including the “timeline”.

Update (April 2021)

My work on the rand module is reasonably complete. I believe the foundation is solid enough for future developers to work and build on top of it. I added a few non-uniform distribution functions, but there are several more. Adding them is a matter of implementing the correct function, preparing sufficient unit tests, informing the people on the Discord server, and getting the Pull Request merged.

The updated documentation is available here: rand | vdoc

Why I Chose V

I spent a lot of time writing code in Java (2013-2019) exclusively. From 2016 onwards, Oracle started collecting royalties at the expense of losing developers, and the Java community was increasingly pushed to rely on OpenJDK binaries. The speed at which new Java versions were being released meant that a lot of new breaking changes were being introduced, splitting the developers into those who relied on the older stable versions and those who wanted newer features in their projects. Several software projects broke. I didn’t want to side with either camp and looked for other languages to call home. I tried several languages before I realised a few things:

1. I had my start in a strongly typed language. Therefore, I ended up preferring the same.
2. I enjoyed Python because it was quick and easy to learn. It remains my language of choice when I want to prototype something. However, I dislike duck typing and runtime errors are a nightmare to debug.
3. I did not like JavaScript because of the myriad ways it can cause runtime errors without telling me what the problem is. Typescript, however, is amazing. It removes a lot of the complaints I have with JS. And I never use JS-based languages outside the browser.
4. C (not C++) is simple and therapeutic. I come back to C every frequently when I need to write software that is not too ambitious but needs to be simple and fast.

I came to know about V in late 2019 and it piqued my interest. I didn’t get around to using it though. It was only after the pandemic hit in March 2020 and cancelled my MTTS Summer Camp when I decided to give Open-Source development a shot.

Getting My Feet Wet

I joined the V Language Discord Sever towards the beginning of 2020. I lurked around, asked questions, got to know the community and the language. The compiler had just been rewritten from scratch and everyone was engrossed in ironing out the issues. I took a few weeks to study the codebase and came across the math.fractions package. It was a bit neglected in the sense that it was missing operator overloading and lacked several functions that I thought were important.

Meet the Team

I teamed up with @Delta456 and @x0r19x91 to help me with this project. We decided to split the work into several phases to make everything easier to manage and make sure that we do not inconvenience the other developers working on the main codebase.

From the organisation, @medvednikov and @spytheman were very helpful as well; they merged the pull requests, answered my queries and discussed viable implementation strategies. And thanks to @Larpon for being a great support. 😄

Deep Dive

I knew it was a monumental task to reorganize the existing rand module and it could not be updated in just one PR. Hence, I proposed three phases to execute this plan:

1. Phase 1: Add PRNG structs and encapsulate the default libc PRNG into the proposed SysRNG struct.
2. Phase 2: A clean-up of the existing rand module involving updating all usages of the module and putting the new structs to use. Also added a bunch of global functions for ease of use.
3. Phase 3 (Ongoing): Further refinement of the module, adding functions for non-uniform distributions and generic array utilities.

Phase 1

Link to the Pull Request: Phase 1

As stated before, the module lacked cohesion. I made a list of all the Pseudo Random Number Generators (PRNGs) that were either already present in the module, or V users would benefit from. I then proposed a common interface for all of them and we set to work implementing them and adding unit tests. I chose to support uniform functions only and minimize the amount of redundancy. The emphasis was to make each RNG independent and as fast as possible.

This was the most amount of grunt work and required a lot of unit tests to ensure the code written works correctly. This PR (pull request) added 3,800+ lines to the codebase and removed very little in comparison. I made sure that the generator outputs were uniform, had the correct sample mean, variance, and so on. Although, I was pleased to have an assignment that justified both my majors: Mathematics and Computing simultaneously. Owing to this PR, the following code works:

module main

import rand.seed
import rand.wyrand

fn main() {
    mut rng := wyrand.WyRandRNG{}
    rng.seed(seed.time_seed_array(2))

    for _ in 0 .. 10 {
    	println (rng.intn(100))
    }
}

Phase 2

Link to the Pull Request: Phase 2

Clean up time! This PR (Pull Request) added 592 lines of code and removed 397. This is small compared to Phase 1, but it’s still a large PR.

I removed all the old functions and all their usages in the library. I updated the global API for the module to mirror those of all the RNG, and I added a lot of documentation as well. It is because of this PR that the random API is greatly simplified.

module main

import rand
fn main() {
    for _ in 0 .. 10 {
        println(rand.intn(100))
    }
}

The default generator used is the WyRandRNG. The code is functionally the same, but it is a lot cleaner than in the last example.

Phase 3

Note: Check the update section at the top.

Link to the Issue/Roadmap: Phase 3

Until now, the redundancy in the module was acceptable owing to potential performance gains. However, the library is far from complete. It does not have any non-uniform distributions currently. Although, a bunch of new functions need to be introduced. I was considering the best way to ensure that programmers can use whatever generator they want while having access to these functions. We had a discussion on the Discord server, and it was decided to use interfaces for the job (a relatively new feature in V).

However, there is a fair amount of work left presently, but I am confident we can pull this off relatively quickly and have a feature-rich, easy-to-use random library in the end. We also need to fix the outdated documentation as soon as possible.

After this phase, users will be able to:

1. Change the generator for the default RNG.
2. Use non-linear distribution functions like Gaussian (Normal), Poisson, etc.
3. Use a single interface for all RNGs.

What Next?

After I am done with rand, I am planning to help with the development of the V Scientific Library. In the future, I also plan to lead the project on adding arbitrary precision numeric types like Integer, Decimal and Fraction.