Re: About Random Integer without IO
On 11 Nov 2004, at 22:02, karczma wrote:
Thomas Davie writes:
This method unfortunately depends on having a seed first though.
Which "this method"? Please, quote the text you are referring to *before* your answer.
One must use a different value every time the program is started, commonly time or the first few bytes from /dev/random. Any one of these is going to require a monadic function to generate (i.e. it must come from the environment in some way - it must change every time you run the program) So while this eliminates the IO monad from most of the program, it must still be initiated using it.
I understand that you mean the seed-propagation method. You are *partly* right, that the same program executed several times will generate the same sequence, if initialized identically. But there is no need for monads, it suffices to pass a parameter, or to read a different initialization file each time. Of course, anybody, especially somebody contributing to this list has the right to be a nit-picker. But, if one is a *practical* user of random stuff, then he/she usually knows such details. Moreover, it is sometimes very useful to control absolutely the initialization, to be able to repeat the experiment, so, professionals in Monte Carlo, etc. rarely if ever, use time, or system-dependent (and hidden) random values. For me the initialization is a *context* problem, which I separate from the properties of the random generator. It is its quality, lack of correlations, etc. which is important. Do you know of many problems requiring an automated, truly random initialization? In this case one may well delegate this issue to the *launching* of the functional program, instead of struggling with it from within. This is my personal philosophy, everybody is entitled to his/hers.
While I agree that it is often useful to start your program with different parameters each time to seed the random number generator, I would argue that this is often inappropriate - supposing we are writing a very simple program to roll a virtual dice. If the user finds one input that rolls a six, they can then use this repeatedly. Reading an initialisation file is back to the situation of using IO to generate our seed. Thanks Tom Davie
Thomas Davie writes, commenting my statement that one does need any 'stateful' (monadic, etc.) RN generator initializer within the program, since you can always pass a parameter during its launching.
While I agree that it is often useful to start your program with different parameters each time to seed the random number generator, I would argue that this is often inappropriate - supposing we are writing a very simple program to roll a virtual dice. If the user finds one input that rolls a six, they can then use this repeatedly. Reading an initialisation file is back to the situation of using IO to generate our seed.
I believe there is no conflict between us, I agree with you. But the difference betwen us is that I do think rather about serious usages of RN, not about contrived examples. I think that if somebody faced a purely functional program to roll a virtual dice, there would be a good deal of sheer madness involved, either the conceptor/implementor madness, or the user's, or both. Haskell is not for *that* kind of problems. I used Haskell and Clean to do some Monte-Carlo, or to generate sound using random algorithms (say, Karplus-Strong string initialized by a white noise). I generated random fractals, etc. It didn't cost me anything to put different initializations by hand on every run when I wanted to have different behaviour. But it was MUCH more important to repeat the same sequence, e.g., after making fast some nice fractal sketch, I relaunched the program with bigger size/precision, but exploiting the same random sequence. I repeat, such is my philosophy. Yours is easier, since you are just discussing, most probably you never used RN for a serious work. If I am wrong, I apologize. Jerzy K.
This really really should have moved to haskell-cafe as previously suggested (sending to both with this in mind); apologies for being a little confising to haskell-cafe This isn't a language design issue, it is a FAQ, or at best a nebulous conceptual debate (speaking of which, has anyone got something more specific than http://www.haskell.org/hawiki/ThatAnnoyingIoType). This question comes up again and again with Haskell newbies - the answer is of course you can't - not maybe, not sometimes, not sort of, but no. What you can do is confine the IO-ness at the outermost layer of the program - by seeding a psudo-random list at program initialization, as both solutions suggested - giving the original question the benefit of the doubt, we'll assume this was what the questioner wanted. Suggesting parameters is not an escape - it is exactly the same as using /dev/random in that they are also IO, weaker IO but still IO (getArgs:: IO [String], though there are counter arguments); besides, reproducability was not a requirement mentioned or implied by the original question (though relevent, not actually haskell specific.. haskell-cafe, again). Chaotic is not the same as Random (Jerzy you obviously know this, but please be clear about it, don't add to the confusion). Chaotic algoritms are used as a 'random-extender'. Random only happens when you seed you algorithm with a non-deterministic value (ie random). karczma wrote:
noise). I generated random fractals, etc. It didn't cost me anything to put different initializations by hand on every run when I wanted to have different behaviour. But it was MUCH more important to repeat the same sequence, e.g., after making fast some nice fractal sketch, I relaunched the program with bigger size/precision, but exploiting the same random sequence. I repeat, such is my philosophy. Yours is easier, since you are just discussing, most probably you never used RN for a serious work. If I am wrong, I apologize.
Jerzy K.
I have to say this.. SERIOUS WORK?! I don't know what Thomas does, but I'm working with security at the moment, and a "serious" random program with default constant seeding strikes me as serious and not in a good way. Overridable seeding sure, if the application demands it, but not broken by default. It's not random; it may be alright for screensavers, but it's not a good coding habit. Clive (Sorry, pet peeve)
Hmm... It is impossible to write a purely functional program to generate random numbers. Not only that it is impossible for a computer to generate random numbers (except using hardware like a noise generator). Pseudo random numbers require a seed. Functional programs by definition only depend on their inputs - therefore the seed is either fixed (same numbers each run) or one of the inputs (which means it must be IO). So all programs have the same limitation, and ising the IO Monad to initialise a sequence of random numbers is the way to do it (In any language this _will_ involve IO). I can see an argument that command line parameters to a program should be presented as arguments to 'main' and not as the result of an IO action - but this would only help eliminate any IO in the case where the seed was to be input by the user. Keean. karczma wrote:
Thomas Davie writes, commenting my statement that one does need any 'stateful' (monadic, etc.) RN generator initializer within the program, since you can always pass a parameter during its launching.
While I agree that it is often useful to start your program with different parameters each time to seed the random number generator, I would argue that this is often inappropriate - supposing we are writing a very simple program to roll a virtual dice. If the user finds one input that rolls a six, they can then use this repeatedly. Reading an initialisation file is back to the situation of using IO to generate our seed.
I believe there is no conflict between us, I agree with you. But the difference betwen us is that I do think rather about serious usages of RN, not about contrived examples. I think that if somebody faced a purely functional program to roll a virtual dice, there would be a good deal of sheer madness involved, either the conceptor/implementor madness, or the user's, or both. Haskell is not for *that* kind of problems. I used Haskell and Clean to do some Monte-Carlo, or to generate sound using random algorithms (say, Karplus-Strong string initialized by a white noise). I generated random fractals, etc. It didn't cost me anything to put different initializations by hand on every run when I wanted to have different behaviour. But it was MUCH more important to repeat the same sequence, e.g., after making fast some nice fractal sketch, I relaunched the program with bigger size/precision, but exploiting the same random sequence. I repeat, such is my philosophy. Yours is easier, since you are just discussing, most probably you never used RN for a serious work. If I am wrong, I apologize.
Jerzy K.
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
This is my *last* word, promised... Keean Schupke wrote:
Hmm... It is impossible to write a purely functional program to generate random numbers. Not only that it is impossible for a computer to generate random numbers (except using hardware like a noise generator). Pseudo random numbers require a seed. Functional programs by definition only depend on their inputs - therefore the seed is either fixed (same numbers each run) or one of the inputs (which means it must be IO).
Will some of you, folks, finally *will to understand* what the issue is about? First, we don't care about 'real random' numbers, actually there are problems even with their definition. We need sequences which *behave* randomly, from the point of view of feasible tests, spectral/statistical; correlational, etc. RN generators work well, and that's it. Stop with that slogans that computers don't do anything random. It reminds me some discussion on other lists, where people for three months discuss whether the brain is a computer, or if the Universe can be assimilated to a Turing machine. I wish them and you all the best... Second, as the example of the ergodic function I told you about before demonstrates, there exist plenty of functions which are pure, don't propagate any 'seed', and which behave "wildly", which *can* be used as a pure "random function". I hate to do this, but you will find such a definition and even the plot thereof in my recent paper abount sound synthesis: http://users.info.unicaen.fr/~karczma/arpap/cleasyn.pdf Clive Brettingham-Moore points out very correctly that a Chaos is not the same as the Randomness. But, still, unstable dynamical systems, hardware and simulated, are used to make noise, "random" sequences with adequate properties. Continuous systems produce quasi-regular functions: Lorenz equations, Chua circuit, etc., but if discretized, the results of, say, Hénon system, etc. may be used as weakly correlated random generators. Third, OK, let's assume we need a seed, and we use a standard RN gen. which propagates it. Now, of course everybody knows that if you launch a functional program 57686514 times, you will get 57686514 identical results. My goodness, what a tragic perspective, what horror!! Of course everybody launches the same program several times just in order to get different results, no? Seriously, if somebody has a computational problem which is <<par excellence>> stateful, let him use Monads, or whatever. Haskell conceptors put a lot of effort into it. But, conceptually, I thought that Haskell is mainly for people who elaborate functional programs in functional style, using functional design patterns and thinking functionally. And, personally I use random streams. Or, once constructed Perlin noise, and then used in different program instances with different initializations. I provide these initializations manually, outside any 'random' context, since I still think that Georg Martius is really wrong writing
I think automatic random initialisation is very important and handy in programs that run non-deterministic simulations.
This is perhaps my own idiosyncrasy, but I taught simulation for some years, I am not a speculator. The first slogan I tried to convey to my students is: -- The FIRST thing you should learn is that a good simulation should share one common property with a good experiment: that you be able to REPRODUCE IT. -- People who do Monte-Carlo requiring many weeks of computing, and who break their program in temporal slices: Two days now, let's see, then continue for a week more... never, repeat *never* initialize their RNG automatically. The first run outputs the result together with the current value of the seed, and this value is reinjected into the next run,in order to prevent the improbable, but possible repetition of the sequence, which would invalidate the soundness of the gathering of statistical data. Thank you for your interest (if you got down to here...) Jerzy Karczmarczuk
I am sorry, but you are wrong. You cannot programmatically generate a sequence of random numbers - this is a mathematical fact and has nothing to do with discussions about brains and turing machines. Secondly the 'ergodic' functions you describe _will_ produce the same sequence every time they are calculated unless the seed is different (also an indisputable mathematical fact) The only way to get 'randomness' into a functional program it through IO (fact). Pseudo random numbers are stateful, you do (in kind of pseudo code): random :: Seed -> (Number, NewSeed) So at the end of the day you have two choises, propogate a seed, or do IO. As for getting your seed, well it is either a constant or the result of IO. Actually pseudo random number generators are not sufficently random for good cryptography, which is why linux provides /dev/random. This is the result of statistics collected from real world events - so you can see this problem is not limited to haskell but to all programming languages. If you want randomness in 'C' you have to seed the generator as well. Keean. Jerzy Karczmarczuk wrote:
This is my *last* word, promised...
Keean Schupke wrote:
Hmm... It is impossible to write a purely functional program to generate random numbers. Not only that it is impossible for a computer to generate random numbers (except using hardware like a noise generator). Pseudo random numbers require a seed. Functional programs by definition only depend on their inputs - therefore the seed is either fixed (same numbers each run) or one of the inputs (which means it must be IO).
Will some of you, folks, finally *will to understand* what the issue is about?
First, we don't care about 'real random' numbers, actually there are problems even with their definition. We need sequences which *behave* randomly, from the point of view of feasible tests, spectral/statistical; correlational, etc. RN generators work well, and that's it. Stop with that slogans that computers don't do anything random. It reminds me some discussion on other lists, where people for three months discuss whether the brain is a computer, or if the Universe can be assimilated to a Turing machine. I wish them and you all the best...
Second, as the example of the ergodic function I told you about before demonstrates, there exist plenty of functions which are pure, don't propagate any 'seed', and which behave "wildly", which *can* be used as a pure "random function". I hate to do this, but you will find such a definition and even the plot thereof in my recent paper abount sound synthesis: http://users.info.unicaen.fr/~karczma/arpap/cleasyn.pdf Clive Brettingham-Moore points out very correctly that a Chaos is not the same as the Randomness. But, still, unstable dynamical systems, hardware and simulated, are used to make noise, "random" sequences with adequate properties. Continuous systems produce quasi-regular functions: Lorenz equations, Chua circuit, etc., but if discretized, the results of, say, Hénon system, etc. may be used as weakly correlated random generators.
Third, OK, let's assume we need a seed, and we use a standard RN gen. which propagates it. Now, of course everybody knows that if you launch a functional program 57686514 times, you will get 57686514 identical results. My goodness, what a tragic perspective, what horror!! Of course everybody launches the same program several times just in order to get different results, no? Seriously, if somebody has a computational problem which is <<par excellence>> stateful, let him use Monads, or whatever. Haskell conceptors put a lot of effort into it. But, conceptually, I thought that Haskell is mainly for people who elaborate functional programs in functional style, using functional design patterns and thinking functionally. And, personally I use random streams. Or, once constructed Perlin noise, and then used in different program instances with different initializations. I provide these initializations manually, outside any 'random' context, since I still think that Georg Martius is really wrong writing
I think automatic random initialisation is very important and handy in programs that run non-deterministic simulations.
This is perhaps my own idiosyncrasy, but I taught simulation for some years, I am not a speculator. The first slogan I tried to convey to my students is: -- The FIRST thing you should learn is that a good simulation should share one common property with a good experiment: that you be able to REPRODUCE IT. --
People who do Monte-Carlo requiring many weeks of computing, and who break their program in temporal slices: Two days now, let's see, then continue for a week more... never, repeat *never* initialize their RNG automatically. The first run outputs the result together with the current value of the seed, and this value is reinjected into the next run,in order to prevent the improbable, but possible repetition of the sequence, which would invalidate the soundness of the gathering of statistical data.
Thank you for your interest (if you got down to here...)
Jerzy Karczmarczuk
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Fri, Nov 12, 2004 at 02:15:51PM +0100, Jerzy Karczmarczuk wrote:
First, we don't care about 'real random' numbers, actually there are problems even with their definition. We need sequences which *behave* randomly, from the point of view of feasible tests, spectral/statistical; correlational, etc.
While this is true (and important) for the applications you have in mind, there are other applications. For instance, in cryptography there is often a need for true random numbers, or as close as you can get. I'm not sure what the whole discussion is about, anyway. Is it about dealing with random numbers practically in Haskell? Peace, Dylan
participants (6)
-
Clive Brettingham-Moore -
dpt＠lotus.bostoncoop.net -
Jerzy Karczmarczuk -
karczma
-
Keean Schupke -
Thomas Davie