14 ms·

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

by mafribe 11y ago

dllthomas 11y ago
What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafePerformIO and unsafeCoerce and similar. Separately, "the unsafe stuff" is still part of the language as used, and while it's certainly better practice to avoid it when you can, it's silly to exclude it when asking whether it's possible to do something - they are sometimes appropriate.
- deleted 11y ago
  [deleted]
- mafribe 11y ago
  By ST you mean Haskell's StateT monad transfomer? Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?
  - dllthomas 11y ago
    "By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control-Monad-ST.html http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly when they say "Haskell isn't pure". Of course, we can fake mutability at a cost of O(log n), which is what makes the O(1) notable. If you do think ST is "pure" then it's not an open question whether you can implement update-heavy array based algorithms in a pure language without algorithmic penalty - you clearly can.
    - mafribe 11y ago
      SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effects to implement such scope extrusion without 'tricks'. All in all I feel that the notion of purity is controversial, insufficiently theorised, and that the community would benefit from a clearer understanding of the trade-offs involved in the different notions of purity
      - dllthomas 11y ago
        You are infuriating. If you object to notions of purity, why did you bring it up in the first place? The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp". In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply to a strict version of Haskell. Please just stop making claims about Haskell until you have some sense of what you're talking about (or at least add a caveat warning others that you might not).
        mafribe 11y ago
        I don't object to purity, I want to know what it means. I didn't realise that this is not a well-understood concept. (I mentioned Sabry's definition of purity which I found surprising.) The original discussion started because somebody complained that Haskell programmers often appear unable to transliterate imperative algorithms. I assume that this complaint was about transliteration into pure Haskell (whatever that may mean exactly). Clearly transliteration into full Haskell with actual mutability is possible. I mentioned Pippenger's article to bring to the debate the idea that the question whether such transliteration is always possible is an open research problem.
        11y ago

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

by mafribe 11y ago

Sure, if you use some of the unsafe stuff ... but what about the safe core of Haskell, do you consider that pure?

What's needed here is ST. It permits local O(1) mutable vectors, while enforcing referential transparency when viewed from outside the runST. ST is clearly not pure in the sense that theory requires to make "can we implement this algorithm with the same complexity" an interesting question. It seems wrong to consider it part of "the unsafe stuff", however - it doesn't have the same kind of unenforced caveats as unsafePerformIO and unsafeCoerce and similar. Separately, "the unsafe stuff" is still part of the language as used, and while it's certainly better practice to avoid it when you can, it's silly to exclude it when asking whether it's possible to do something - they are sometimes appropriate.

deleted 11y ago
[deleted]
mafribe 11y ago
By ST you mean Haskell's StateT monad transfomer? Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations? That would be an interesting proposal. But I wonder if it captures the conceptual content of the informal concept of purity. Maybe a time complexity restriction should be provable from purity?
- dllthomas 11y ago
  "By ST you mean Haskell's StateT monad transfomer?" No, I mean ST. An entirely different monad: http://hackage.haskell.org/package/base-4.7.0.0/docs/Control-Monad-ST.html http://hackage.haskell.org/package/base-4.7.0.0/docs/Control... "Are you suggesting to define purity by the inability to define O(1) mutable vector-like operations?" "Define", no, as that certainly doesn't encompass the full scope of purity. I think mutability runs counter to most people's notion of purity, particularly when they say "Haskell isn't pure". Of course, we can fake mutability at a cost of O(log n), which is what makes the O(1) notable. If you do think ST is "pure" then it's not an open question whether you can implement update-heavy array based algorithms in a pure language without algorithmic penalty - you clearly can.
  - mafribe 11y ago
    SPJ and J Launchbury seem to think ST is pure. Looking over the PLDI paper, I get the impression that the key difference between ST and the usual State monad is (1) the ability to name state, and (2) the use of parametric polymorphism to prevent scope-extrusion of state. Of course ML has scope-extrusion of state, and one of my questions/examples upthread was about the ability of Haskell's monadically controlled effects to implement such scope extrusion without 'tricks'. All in all I feel that the notion of purity is controversial, insufficiently theorised, and that the community would benefit from a clearer understanding of the trade-offs involved in the different notions of purity
    - dllthomas 11y ago
      You are infuriating. If you object to notions of purity, why did you bring it up in the first place? The first place it was used in this thread was your citing a paper entitled "Pure versus Impure Lisp". In that paper, it was used to mean prohibiting "set-car!" and "set-cdr!". ST provides the equivalent of "set-car!" and "set-cdr!", so in the presence of ST the result you were citing in the paper doesn't even apply to a strict version of Haskell. Please just stop making claims about Haskell until you have some sense of what you're talking about (or at least add a caveat warning others that you might not).
      - mafribe 11y ago
        I don't object to purity, I want to know what it means. I didn't realise that this is not a well-understood concept. (I mentioned Sabry's definition of purity which I found surprising.) The original discussion started because somebody complained that Haskell programmers often appear unable to transliterate imperative algorithms. I assume that this complaint was about transliteration into pure Haskell (whatever that may mean exactly). Clearly transliteration into full Haskell with actual mutability is possible. I mentioned Pippenger's article to bring to the debate the idea that the question whether such transliteration is always possible is an open research problem.
        11y ago