2

This older question tells us that in functional programming "true" randomness cannot be achieved since in FP functions are pure/idempotent and return the same value irrespective of number of invocations without any side effects.

But if that is true, how is FP applicable for problems like picking randomly a Captcha or some puzzle to question the user before entering the system?

I considered taking system time as a seed inside the function. But that is depending on external state.

Could anyone please demonstrate it with a code snippet in Haskell/Clojure etc?

Vicky
  • 399
  • 3
  • 6
  • 2
    How does your hypothetical functional language handle I/O? – Philip Kendall Jan 03 '18 at 06:55
  • Several options are: (1) make it an impure function that interacts with the outside and/or maintain (use and update) its own state with each call. (2) Use an external tool to pre-generate a huge but finite-size stream of random data, then allow the "random function" to take this stream and feed its values one-by-one to its consumers. In the simplest case, consider zip-with the (fixed, pre-generated) random stream with another input stream. – rwong Jan 03 '18 at 07:14
  • The code (algorithm) that requires a random source will now need to be rewritten, so that each time it requires a random value, it needs to pass in a "invoke number". An example is, say, incrementing integers, 0, 1, 2,..., where the "fixed random function" will simply look up the corresponding pre-generated random number from the list. This ensures that, given the same "invoke number", the returned pre-generated number is the same. This removes the dependence on order of evaluation. – rwong Jan 03 '18 at 07:18
  • Another option that does not depend on having a pre-generated list as initialization is to choose a cryptographic hash generating function, and use the hash of the "invoke number" as the random value. – rwong Jan 03 '18 at 07:19
  • Basically you need to enrich your understanding in order to understand answers to your question. – rwong Jan 03 '18 at 07:19
  • @rwong, basically what you are describing is a lookup table. But eventually, for a table of non-infinite length, the values must repeat in a fixed sequence (and thus the function is not random, even if the lookup table was randomly generated). Also, usually the point of a random number generator is to avoid the possibility that anyone with a knowledge of the inputs can calculate the outputs - the very existence of a lookup table that links inputs to outputs violates the requirement of *randomness*. – Steve Jan 03 '18 at 07:27
  • @DocBrown : I wanted a fresh thread explaining the logic in a simpler way to people like us coming from imperative background. The earlier thread doesn't account for that. It assumes the asker has a functional background. Kindly take a look at my edited question. It is not a dupe. – Vicky Jan 03 '18 at 07:35
  • 1
    @JörgWMittag, to be fair to the OP, I don't think that link is clear enough that the answer to her question "how to functional languages handle random numbers", is that "they don't". Functions don't handle non-determinism, and "functional languages" handle non-determinism essentially by being non-functional (that is, by stepping outside the functional paradigm and employing non-functional code) - and so-called functional languages actually allow non-functional code (and non-functional programs) to be written. In the same way that "structured languages" permit unstructured code (e.g. `GOTOs`). – Steve Jan 03 '18 at 07:36
  • @Steve: Your response is correct, but it is a major topic in reproducible software building, execution, and results. The use of lookup table is what allows deterministic results. Executions using different lookup tables are assembled into an "ensemble" so that ensemble statistics can be extracted from all of them. – rwong Jan 03 '18 at 07:41
  • @Steve - the use of a monad to provide a sequence of random numbers (potentially initialized via the use of IO or some other externally-sourced seed) as shown in the accepted answer to that question is not "non-functional" in any way. Every line of code in that answer consists only of deterministic, pure functions that always give the same result for the arguments passed to them. The trick is in arranging for your non-deterministic values to be passed to a user-specified function, rather than returned from a system-called one. – Jules Jan 03 '18 at 07:54
  • @rwong, don't get me wrong, I'm not saying lookup tables would never be acceptable for a particular use case. Pseudo-random, or even just obscurely deterministic, operation is often perfectly sufficient, or even desirable. I'm just addressing the OP in terms of first principles, that "randomness" and "functional-ness" are two fundamentally opposed and irreconcilable concepts. – Steve Jan 03 '18 at 07:59
  • @Jules, if a function is "pure" (i.e. its output is a function of its input), then its output ceases to be random (i.e. it's output is functional). That circle cannot be squared. I'm not railing against functional languages - I'm simply pointing out that any functionalism of a value detracts from its randomness. Any functional program that is said to be random, must merely shift the problem (and the requirement for non-functionalness) outside of the scope of the program, by operating deterministically on its non-deterministic inputs. – Steve Jan 03 '18 at 08:07
  • 1
    This does feel like a "trick question"; under the conditions specified (no IO, deterministic machine execution), you can't implement "true" randomness in an imperative language either. – pjc50 Jan 04 '18 at 09:57
  • @pjc50, the difference is that an imperative program can (pseudo-)randomise it's own output regardless of its starting conditions (because it operates under fewer constraints) - it can acquire new input during its operation. A (true) functional program cannot - its output is predictable before it begins (as soon as its inputs are known), and repeatable. That is why functional programs have a smaller scope of use (than imperative programs) and are typically short-running affairs, because frequently it is desirable for a program to interact with its environment and take new input as it goes. – Steve Jan 04 '18 at 16:57
  • @Steve well, if you want IO, there's a monad for that. But my point was that setting up conditions where one program is allowed input randomness and the other isn't is setting up a lopsided comparison. – pjc50 Jan 04 '18 at 16:59
  • @pjc50, there is a monad for it, but there is not a function for it, and anything program that uses an I/O monad forfeits its functionalness (and the guarantees that came with it). I'm not trying to compare functional languages adversely - I'm just exploring certain lesser-considered aspects of them (including the fact that an I/O monad is not a function, and it also depends on an imperative order of execution/evaluation, having dire implications for concurrent evaluation of the program, whereas the order of evaluating pure functions depends only on analysing the availability of inputs). – Steve Jan 04 '18 at 17:18

3 Answers3

4

Your question in a bit unclear in that you don't specify whether you are talking about true random numbers or pseudo-random numbers, so I will answer both.

True Random Numbers

You are correct that functional programs can't produce true random numbers. But neither can imperative programs. Computers are still deterministic machines, regardless of whether they are running a C program or a Haskell program.

Pseudo-Random Numbers

Pseudo-Random Numbers are generated by a Pseudo-Random Number Generator (aka PRNG). PRNGs are just algorithms like any other algorithm. They can be expressed in a functional language just as well as they can be expressed in an imperative language.

So, there is really no difference between functional languages and imperative languages when it comes to random numbers. Both can compute pseudo-random numbers and neither can compute true random numbers (since they can't be computed at all).

in functional programming "true" randomness cannot be achieved since in FP functions are pure/idempotent and return the same value irrespective of number of invocations without any side effects.

Again, the same thing is true for imperative programming. If you call srand with the same seed number, you will deterministically get the same pseudo-random number sequence from rand, every time.

The only way to get true randomness is through I/O. But, functional languages can model I/O just fine, whether that be with an I/O Monad (or something more specialized like a Random monad), linear types, world types, effect types, an effect system, or like Scala, ML, Clojure, and F♯ do it, by simply allowing them and trusting the programmer to not make mistakes.

So, in other words, it makes no sense to be asking about Random Numbers specifically. A PRNG is just a function, so if you are asking how functional programming can be used to deal with pseudo-random numbers, then you should rather ask how functional programming can be used to deal with functions, because there is nothing special about a PRNG, it's just a function. And True Randomness is just I/O, so again, it doesn't make sense to ask about them specifically.

If you accept that you can write functions in FP, then you must also accept that you can write PRNGs in FP. And if you accept that you can read the clock, read input from the user, read a file, access a database, access the web, etc., then you must also accept that you can read True Random Numbers. (In fact, on Unix, for example, device drivers are typically exposed as files, and a true random number device would typically be exposed as a file you read from. And there is a web service that serves true random numbers.)

Community
  • 1
Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318
  • This is a good answer except to add that any PRNG generates a (potentially) infinite array of numbers from a given seed. That array is generated without any side effects. That said, it would have been nice to show some Haskell/Clojure code that actually does it. – Daniel T. Jan 04 '18 at 03:16
  • I agree with the tenor of your analysis here about any PNRG that is implemented purely in terms of its inputs (and does not reference things like the system clock or any other environmental variable), but I would still make it clear that I/O is something that fundamentally breaks the functional-ness of the program and the guarantees that come with following a functional coding pattern, and puts the onus back on the programmer to manage all the potential difficulties of mutable state. "Functional" languages "model I/O just fine" simply by deviating from being functional, and that's a key point. – Steve Jan 04 '18 at 08:03
  • @Steve: There are plenty of ways of modeling I/O *without* deviating from being functional. Linear types, effect types, world types, effect systems, I/O monads, are but a few. Haskell alone tried out two other approaches (continuations and lazy streams) before settling on the I/O monad. – Jörg W Mittag Jan 04 '18 at 17:07
  • @JörgWMittag, it depends what you mean by "being functional". If it means "employing a language described as functional", yes functional languages have I/O - but that is because those languages actually have non-functional features which allow code to be implemented imperatively, not because I/O is actually being implemented as a "function" (in the theoretical sense, rather than in the sense of a language construct or syntax). And the use of the imperative code causes the loss of the guarantees and the potentials that exist for the evaluation of functions. – Steve Jan 04 '18 at 17:31
  • Nice analysis. I think it's worth emphasizing that by "simply" allowing I/O in languages like Scala, etc. one does break the idempotence aspect of FP, which was part of the question. It's possible to stay purely functional by using monads, as @JörgWMittag stated. That way the function is still idempotent but the randomness is represented in the result. It's like collapsing the wave function of a quantum system when you measure it, or something like that. :) – wensveen Feb 10 '21 at 10:46
3

The whole point of a random number generator is to return a value that is not a deterministic function of its input.

A "random number function" is therefore a contradiction in terms. It is not even on par with I/O, which can still be modelled purely as a function as part of a deterministic system.

What we do in a functional language is simply implement a non-functional, non-deterministic method call - it may look like a function, have the garb of functional syntax, and assemble together as a function (and be called or evaluated, and its results used, in a deterministic order relative to other functions), but it is clearly not actually a function (because its outputs do not relate to its inputs) - and the whole program that depends on it ceases to be a function anymore (because the program does not execute deterministically according to its inputs).

Steve
  • 6,998
  • 1
  • 14
  • 24
  • Perfect. Hence my question is: Is FP applicable in the below scenario for production environment where want to throw Captcha and Various puzzles to question the user before entering the system? – Vicky Jan 03 '18 at 07:37
  • I don't see why Captcha cannot be reconciled with deterministic execution. With a Captcha, the aim is not for the program or results to be non-deterministic - the Captcha system does not depend fundamentally on randomness, but on analytical complexity and obscurity to differentiate the human perception of the information within an image from machine analysis and extraction of the information. In other words, a purely deterministic set of Captchas, would still be unamenable to accurate machine analysis (unless a human first evaluated them all and provided a lookup table). – Steve Jan 03 '18 at 07:48
  • 1
    This isn't true of most functional languages I've seen. The approach taken, for example, in Haskell is to set up the user program so that rather than calling a function that returns a random number (which, as you say, would make it *not actually a function*), the user program passes their own function to the system, and then the system calls that passing it a random number as an argument. This side-steps the issue: there is no non-function involved, just a non-deterministic behaviour that is caused by the environment interacting with the program, which remains purely functional. – Jules Jan 03 '18 at 08:01
  • 6
    There are two kinds of random numbers. Computers are deterministic devices, they cannot produce random numbers. They can only produce pseudo-random numbers, which behave statistically is if they *were* random. However, pseudo-random number generators are still just algorithms like any other algorithm and can be modeled by pure functions. "True" random numbers can only be generated by a physical process and read from the environment. However, this is just I/O like any other I/O, and if your language can model I/O, then it can model this as well. So, I really don't see the problem.. – Jörg W Mittag Jan 03 '18 at 08:12
  • @Jules, but where does the "random number" come from in this program, which is then "passed as an argument"? It has to be an input at the entry point of the program (from a non-functional source). But the OP asked how to *get* a random number *from* a function, not how to *provide* an (already-) random number *to* a function. – Steve Jan 03 '18 at 08:13
  • @JörgWMittag, agreed on everything you say about pseudo-random numbers. Usually, pseudo-random generators employ something from the state of the machine which it would be difficult for an attacker to gain knowledge of. For example, the system clock (to millisecond or nanosecond resolution) and the distance travelled by the mouse cursor can be measured, but without complete and ongoing access to the machine, it becomes incredibly difficult to determine the next output from any knowledge of previous outputs, because there is no facility to measure the inputs with the necessary precision. – Steve Jan 03 '18 at 08:20
  • @Steve: I modified the question to make it "less duplicate" than the former. You may check if your answer still applies to this modified one. – Doc Brown Jan 03 '18 at 08:43
  • @Steve : As per your answer, NO FP language which claims to address the real world use cases, can claim that it has only pure functions and a true FP language. For randomness (or pseudo-randomness), it has to support non-determinism. – Vicky Jan 03 '18 at 09:15
  • @DocBrown, the only point I would make is that the accepted answer to the previous question did not clearly examine the reason why the concepts of functionality and randomness are opposed. The use of the jargon terms "pure" and "impure" really equates to "functional" and "non-functional". That's why I think the analogy with structured programming is apt - that functional languages are those that are designed to express functional patterns, but they also retain non-functional features and a whole compiled program will rarely be a function (unless it is a library which is not free-standing). – Steve Jan 03 '18 at 09:21
  • @Vicky: pseudo-randomness is still deterministic. If that is "random enough" for a real-world problem depends on the problem. – Doc Brown Jan 03 '18 at 09:25
  • 1
    @Vicky, that is true. But bear in mind that all computers are supposed to be deterministic, including imperative code. A functional language is one that is designed to *aid* the use of functional *patterns* - it does not matter (to me) that it does not strictly enforce them. The reason a true random number generator cannot be a function, is because the meaning of that concept can't be expressed in terms of the functional pattern of inputs relating to outputs, and even the full workings of a useful pseudo-random system would be almost impossible to describe entirely in functional terms. – Steve Jan 03 '18 at 09:35
  • Describing a PRNG in functional terms is trivial. It is just a function which takes some input and produces some output. If it relies on state, then it is a function that takes the current state as input and returns a pair of a number and the next state as its output. For many PRNGs, the state of the system is fully described by a number (aka *seed*), so it is just a function which takes a number and produces a pair of numbers. Also, for many PRNGs, the output is the seed for the next round, so it becomes even simpler, a function that takes a number and produces a number. – Jörg W Mittag Jan 03 '18 at 23:15
1

Short Answer

Randomness is handled just like other kinds of input.

Long Answer

Random is Input

Random is like reading the state of the hardware clock. And that is like reading the state of the camera to take a profile picture about the computer user, or like reading the content of a certain file. Random is just a special kind of input.

Handling Random Differently than Other Input

In theory some need exists to handle randomness differently from other kinds of input. For example : for security. And the theory of purely functional programming can answer that need. But in practice this direction happens to be not pursued. Even more important security needs are not addressed yet in practice simply because of deficit in software engineering capacity.

How Input is Handled by Purely Functional Programming ?

This topic is discussed in much material over the web. If it to be discussed here on StackExchange then it deserves its own question.

Some Concrete Help to your question Anyway

A pure function returns not the final, concrete result that depends on random, but a [possibly composite] action, like a little algorithm, that says : get a random value; compute some other action with it and perform that other action. A pure function returns just a deterministic value that represents, describes what the program is to do. It forwards the "dirty" problems of non-determinism, IO to the runtime system. A pure function does not do anything, it just computes [and returns] what to do.

libeako
  • 159
  • 3
  • "A pure function does not do anything" - there is a grain of underlying philosophical truth there I think, which explains why all useful functional languages contain general purpose, non-functional features, and why most programs written in functional languages are not themselves functions. – Steve Jan 04 '18 at 10:12