This post explores the challenges of generating deterministic random numbers and using cosine within Nix expressions. It highlights that Nix's purity, while beneficial for reproducibility, makes tasks like generating unique identifiers difficult without resorting to external dependencies or impure functions. The author demonstrates various approaches, including using the derivation name as a seed for a pseudo-random number generator (PRNG) and leveraging builtins.currentTime as a less deterministic but readily available alternative. The post also delves into the lack of a built-in cosine function in Nix and presents workarounds, like writing a custom implementation or relying on a pre-built library, showcasing the trade-offs between self-sufficiency and convenience.
Hillel Wayne's post dissects the concept of "nondeterminism" in computer science, arguing that it's often used ambiguously and encompasses five distinct meanings. These are: 1) Implementation-defined behavior, where the language standard allows for varied outcomes. 2) Unspecified behavior, similar to implementation-defined but offering even less predictability. 3) Error/undefined behavior, where anything could happen, often leading to crashes. 4) Heisenbugs, which are bugs whose behavior changes under observation (e.g., debugging). 5) True nondeterminism, exemplified by hardware randomness or concurrency races. The post emphasizes that these are fundamentally different concepts with distinct implications for programmers, and understanding these nuances is crucial for writing robust and predictable software.
Hacker News users discussed various aspects of nondeterminism in the context of Hillel Wayne's article. Several commenters highlighted the distinction between predictable and unpredictable nondeterminism, with some arguing the author's categorization conflated the two. The importance of distinguishing between sources of nondeterminism, such as hardware, OS scheduling, and program logic, was emphasized. One commenter pointed out the difficulty in achieving true determinism even with seemingly simple programs due to factors like garbage collection and just-in-time compilation. The practical challenges of debugging nondeterministic systems were also mentioned, along with the value of tools that can help reproduce and analyze nondeterministic behavior. A few comments delved into specific types of nondeterminism, like data races and the nuances of concurrency, while others questioned the usefulness of the proposed categorization in practice.
Classical physics is generally considered deterministic, meaning the future state of a system is entirely determined by its present state. However, certain situations appear non-deterministic due to our practical limitations. These include chaotic systems, where tiny uncertainties in initial conditions are amplified exponentially, making long-term predictions impossible, despite the underlying deterministic nature. Other examples involve systems with a vast number of particles, like gases, where tracking individual particles is infeasible, leading to statistical descriptions and probabilistic predictions, even though the individual particle interactions are deterministic. Finally, systems involving measurement with intrinsic limitations also exhibit apparent non-determinism, arising from our inability to perfectly measure the initial state. Therefore, non-determinism in classical physics is often a result of incomplete knowledge or practical limitations rather than a fundamental property of the theory itself.
Hacker News users discuss deterministic chaos and how seemingly simple classical systems can exhibit unpredictable behavior due to sensitivity to initial conditions. They mention examples like the double pendulum, dripping faucets, and billiard balls, highlighting how minute changes in starting conditions lead to vastly different outcomes, making long-term prediction impossible. Some argue that while these systems are technically deterministic, the practical limitations of measurement render them effectively non-deterministic. Others point to the three-body problem and the chaotic nature of weather systems as further illustrations. The role of computational limitations in predicting chaotic systems is also discussed, along with the idea that even if the underlying laws are deterministic, emergent complexity can make systems appear unpredictable. Finally, the philosophical implications of determinism are touched upon, with some suggesting that quantum mechanics introduces true randomness into the universe.
Summary of Comments ( 0 )
https://news.ycombinator.com/item?id=43669057
Hacker News users discussed the blog post about reproducible random number generation in Nix. Several commenters appreciated the clear explanation of the problem and the proposed solution using a cosine function to distribute builds across build machines. Some questioned the practicality and efficiency of the cosine approach, suggesting alternatives like hashing or simpler modulo operations, especially given potential performance implications and the inherent limitations of pseudo-random number generators. Others pointed out the complexities of truly distributed builds in Nix and the need to consider factors like caching and rebuild triggers. A few commenters expressed interest in exploring the cosine method further, acknowledging its novelty and potential benefits in certain scenarios. The discussion also touched upon the broader challenges of achieving determinism in build systems and the trade-offs involved.
The Hacker News post titled "RNG and Cosine in Nix" sparked a discussion with several interesting comments.
One commenter questioned the practicality of the approach, pointing out that using a hash function directly would likely be simpler and more efficient than the proposed cosine-based method. They also expressed concern about potential bias introduced by using cosine and suggested that a more rigorous statistical analysis would be necessary to validate the randomness quality.
Another commenter echoed this sentiment, emphasizing the importance of proper statistical testing for random number generation. They recommended using established test suites like TestU01 to thoroughly evaluate the randomness properties of the generated sequence.
One user focused on the security implications, warning that the proposed method might not be suitable for cryptographic purposes due to potential predictability. They advised against using custom RNG solutions in security-sensitive contexts and recommended relying on well-vetted cryptographic libraries instead.
A further commenter offered a different perspective, suggesting that the approach might be useful for generating deterministic random values based on a seed. They envisioned applications in procedural generation, where consistent results are desirable.
Another individual highlighted the importance of understanding the underlying distribution of the generated random numbers. They noted that different applications may require different distributions (uniform, normal, etc.) and that simply generating seemingly random numbers without considering the distribution could lead to incorrect results.
Several commenters discussed the mathematical properties of the cosine function and its suitability for RNG. Some expressed skepticism, while others defended its potential, albeit with the caveat that careful analysis and testing are crucial.
Finally, some comments touched on the specific use case within Nix, the package manager mentioned in the title. They speculated about the potential benefits and drawbacks of using this method for generating unique identifiers or other random values within the Nix ecosystem. However, no definitive conclusions were drawn regarding its practical application in Nix.