7

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?

fuz
  • 88,405
  • 25
  • 200
  • 352
Babu Srinivasan
  • 2,339
  • 23
  • 24
  • 1
    Do I understand correctly that the body of the function is (partially) written in the imperative style and you use locally defined `IORef`s to hold LSFRs? Maybe you should consider using `STRef` instead and run the computation inside an `ST` monad. – rkhayrov May 20 '11 at 15:38
  • 1
    Could you post the code for your function? Perhaps it should be in IO in the first place. – augustss May 20 '11 at 15:50
  • 1
    Is it impossible to make the LFSR pure by giving them as parameters? If not, that could be a solution. – fuz May 20 '11 at 15:53
  • 3
    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... – stephen tetley May 20 '11 at 16:59
  • 4
    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. – C. A. McCann May 20 '11 at 17:09
  • @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. – fuz May 20 '11 at 18:01
  • @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. – C. A. McCann May 20 '11 at 18:33
  • @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](http://stackoverflow.com/questions/5897845/relax-ordering-constraints-in-monadic-computation/5901748#5901748)) – fuz May 20 '11 at 21:44
  • (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. – fuz May 20 '11 at 21:47
  • @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. – C. A. McCann May 20 '11 at 22:12
  • @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. – fuz May 20 '11 at 22:17
  • 2
    The functions I wrote in haskell are the SNOW ciphering and integrity algorithms. The algorithm and reference C code can be found [here](http://www.etsi.org/WebSite/document/Algorithms/ts_135201v070000p.pdf) The functions are f9 (integrity) and f8 (ciphering). – Babu Srinivasan May 21 '11 at 05:12
  • @Babu: Can you send me the code? It would be intersting to modify it in order to be pure. – fuz May 22 '11 at 15:29

3 Answers3

13

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.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • 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. – John L May 20 '11 at 22:54
  • @John L, in fact, IO is defined in terms of ST, with some magic extra hooks. – Don Stewart May 20 '11 at 22:57
  • 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. – Babu Srinivasan May 21 '11 at 05:28
  • Link to paper I mentioned: [Lazy Functional State Threads](http://www.haskell.org/ghc/docs/papers/lazy-functional-state-threads.ps.gz) by John Launchbury and Simon Peyton Jones – Babu Srinivasan May 21 '11 at 05:32
5

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.

fuz
  • 88,405
  • 25
  • 200
  • 352
  • 6
    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. – C. A. McCann May 20 '11 at 15:40
  • Perhaps the most annoying mis-use of `unsafePerformIO` is in the presence of static buffers (not a thread-safe use), so be very careful! – Thomas M. DuBuisson May 20 '11 at 15:45
  • 2
    @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. – C. A. McCann May 20 '11 at 17:13
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.

augustss
  • 22,884
  • 5
  • 56
  • 93