How to write a haskell function without IO in type sig by hiding 'state' changes

Question

I wrote a function in haskell that takes a few parameters like Word32, String (ignore currying) and outputs IO Word32. Now, this is a function in the true sense: for the same inputs, the output will always be the same. There are no side-effects. The reason the function returns IO Word32 instead of Word32 is that the function updates many 32 bit Linear Feedback Shift registers (lfsr) and other registers several times in a loop in order to compute the final Word32 output.

My question is this: Given that this function effectively has no side-effects, is it possible to hide those register updates inside the function implementation so that the function returns Word32 and not IO Word32? If so, how?

Purposeful

Do I understand correctly that the body of the function is (partially) written in the imperative style and you use locally defined IORefs to hold LSFRs? Maybe you should consider using STRef instead and run the computation inside an ST monad. – Carmacarmack

Could you post the code for your function? Perhaps it should be in IO in the first place. – Humic

Is it impossible to make the LFSR pure by giving them as parameters? If not, that could be a solution. – Erickson

If the Linear Feedback Shift registers are implemented in hardware then your function has side-effects. Presumably you wouldn't want concurrent threads to be interleaved... – Ekaterinburg

Just to emphasize what @stephen tetley points out: "side effects" doesn't just mean "deliberately changing the outside world". Any dependency on the outside world in either direction qualifies, which includes things like observing the value of mutable data, doing non-thread-safe things with hardware, etc. This is important because if you tell GHC something is pure, it will actually believe you and act accordingly, which includes applying optimizations that would be incredibly reckless in a C compiler. – Alcinia

@camccann: By the way, I believe, that GHC does not treats pure and IO values in any way differently. It is merely that the way a programmer uses IO values (via monads, for instance), forces the compiler to evaluate them in order. – Erickson

@FUZxxl: And it's the evaluation that triggers the side effects, which with IO is normally when evaluating (>>=) applied to that value in a subexpression of main. With unsafePerformIO, I think the side effects trigger whenever the thunk holding the value is forced, an event invisible to the code itself, and are subject to being rearranged at will by GHC's optimizer in ways that can change both the ordering and number of times the side effects occur. – Alcinia

@camccann: I think, you don't got the point. IO is defined as a state monad. The state token is of a special type called RealWorld. Each (ordinary) IO action is strict in this token and only returns anything, when the IO is finally done. There is no magic involved. It's just that the evaluation order is forced by the use of a token. You can manually deconstruct IO values and juggle with their tokens - than the compiler happily changes their order. (See for instance here) – Erickson

(Out of chars) unsafePerformIO works similiar - the IO operation passed to the function becomes deconstructed. Then they pass a new token to it and drop the resulting token - that's all what is needed to do unsafe IO. – Erickson

@FUZxxl: If by "that's all" you mean monkeying with implementation details in ways that can break the semantics of core language constructs, then yes. The real point is don't mess with that stuff unless you're absolutely certain that what you're doing behaves correctly, like runST does. And no, IO is not "just" a state monad, unless you think the RealWorld token actually contains the state of the entire outside universe, and that nothing in the universe changes until the token is returned. – Alcinia

@camccann: IO uses the idea of a state monad - RealWorld is of course just a dummy token that represents the whole universe. It's just a convenient way to implement IO. Hm... I don't wanted to start such an argument. In the beginning, I just wanted to say, that there is nothing special with IO. The ordering is defined via clever use of the haskell semantics. – Erickson

The functions I wrote in haskell are the SNOW ciphering and integrity algorithms. The algorithm and reference C code can be found here The functions are f9 (integrity) and f8 (ciphering). – Purposeful

@Babu: Can you send me the code? It would be intersting to modify it in order to be pure. – Erickson

Answer 1

Yes! Haskell can do this.

The ST monad

If you actually use mutable state (registers), that are entirely hidden from the observer outside the function, then you are in the ST monad, a monad for memory effects only. You enter the ST world via runST, and when you exit the function, all effects are guaranteed to not be visible.

It is precisely the right computational environment for working with local, mutable state.

Purely functional state: the State monad

If, however, you're not actually mutating registers or cells, but rather updating a purely functional value many times, a simpler environment is available: the State monad. This doesn't allow mutable state, but gives an illusion of local state.

IO, and unsafePerformIO

Finally, if you have local, mutable effects, like in the ST monad, but for some reason or another, you are going to need IO operations on that state (such as via an FFI call), you can simulate the ST monad, with almost as much safety, by using unsafePerformIO, instead of runST, to introduce a local IO environment. As the IO monad doesn't have nice types to enforce abstraction, you will need to manually assure yourself that the side effects will not be observable.

Transcript

Another nice benefit of the ST monad is that it's extremely efficient. I've often found ST code to be faster than equivalent IO code. – Grand

@John L, in fact, IO is defined in terms of ST, with some magic extra hooks. – Transcript

Don,mutable state is entirely hidden from observer outside function. I read a 1994 paper called Lazy Functional State Threads by John Launchbury & Simon Peyton, which says Some algorithms make critical internal use of updatable state,even though their external specification is purely functional .. we present a way of securely encapsulating stateful computations that manipulate multiple,named,mutable objects,in the context of a non-strict,purely-functional language. Paper,which talks about ST was a bit too technical first time I read it. I will read it again & implement f8,f9 using ST monad. – Purposeful

Link to paper I mentioned: Lazy Functional State Threads by John Launchbury and Simon Peyton Jones – Purposeful

Answer 2

If you imported that function using the FFI, just remove the IO from the return type. Else, use unsafePerformIO :: IO a -> a from System.IO.Unsafe. Please note, that this function is one of the most dangerous functions in Haskell. Don't use it, if you're not really shure about the consequences. But for your purpose, it seems okay.

Erickson

Should probably note that one of the few "correct" uses of unsafePerformIO is as a flat assertion to the compiler that a function actually is externally pure, which is exactly what this question is about. Most of the ways that unsafePerformIO can bite you arise from using it on functions that are only "mostly" pure in some sense. – Alcinia

Perhaps the most annoying mis-use of unsafePerformIO is in the presence of static buffers (not a thread-safe use), so be very careful! – Myungmyxedema

@TomMD: Sometimes I think it's counterproductive to talk about purity in terms of "side effects" that involve "doing something" as much as Haskell programmers tend to. The most insidious bugs in impure functions--and in most impure languages, really--are often those involving read-only access to the outside world. – Alcinia

Answer 3

Yes, this would be a legitimate use of unsafePerformIO. But it's only OK if you are really sure there are no visible effects.

Humic