7 ms·

As far as I'm concerned, purity is more fundamental than impurity, because we can always emulate impurity using a pure language (as is shown in this article), b

• nine_k 9y ago
  > it's not possible to emulate purity using an impure language It sounds as if a pure language cannot be implemented in terms of an impure language. E.g. a pure language won't be implementable in an instruction set of any modern CPU. I must be missing something.
  • Retra 9y ago
    The CPU instructions are pure functions over the state of the machine. :)
    • TheCoreh 9y ago
      Only if you ignore cosmic rays :)
      • pka 9y ago
        Then every CPU instruction is just (Universe -> Universe) :D
  • inimino 9y ago
    In this context, purity means the contract between caller and callee. You can write the same code, but you can't rely on the enforcement of the same contract unless it is built into the language.
  • T-R 9y ago
    Impurity is a lack of constraints. You can, with impure code, write an interpreter for a language that constrains code to being pure, and implemented correctly, you can then depend on code written in that langauge to be pure. His point is that there's no lost benefit in calling pure code from impure code - the code is already unconstrained. Calling impure code from pure code, though, means you've lost the purity constraint, which means you've lost the nice emergent properties you get from that constraint. Even if you write 'pure' code in an impure environment, you can't depend on it being pure, because that constraint isn't actually enforced. No matter how pure I try to keep my Javascript, I can never depend on it being pure - there could be a bug, or someone could add impurity at the bottom of the callstack, breaking referential transparency.
    • arximboldi 9y ago
      Following your argument to the extreme, Haskell is also an impure language: there could be a bug in the compiler, or someone could introduce impurity in it! Even worse, someone could call unsafePerformIO! You would argue: but that goes against the Haskell specification, that impurity is not proper Haskell! And exactly: the "purity" comes from an abstraction, which is a contract between you and some other developers. The fact that JavaScript the language does not enforce such contracts does not mean that you can not get into agreements with other developers. Sure, the JavaScript interpreter won't complain when the contract is broken, in the same way that the CPU is not complaining when Haskell has a bug, in this case, JavaScript is not the one making the purity promise---a developer is. As such, I believe that in JavaScript, a library author can make claims about the purity of some code. Sure, some adversarial coder could use monkeypatching to break it---and some adversarial coder could also gives you instances of some type class that call unsafePerformIO under the hood. In the end, we are talking about degrees to which some purity can be ensured, and levels at which the contracts are enforced. I know some Haskell developers would like to think that they are programing in this perfect language and that it is impossible to do functional programming in other languages. But I disagree, and actually, I believe that bringing the design tools of functional programming to mainstream languages is a worthy goal that should not be discouraged.
      • 9y ago
  • runeks 9y ago
    It's important that we separate the concept of a language and its implementation. You cannot define a pure language using an impure language, but what type of language you use to implement a pure language is up to you.
    • s_ngularity 9y ago
      I fail to see how you couldn't specify a pure language using a pure subset of a sufficiently expressive impure language.
    • Retra 9y ago
      Purity is not a really property of functions, but of optimizations. A pure function is simply those functions for which a "pure optimization" is desirable, and that ultimately depends on what you care about. Every impure function can become pure just by finding a context where the side-effects are moot. (Redirect all output to /dev/null and suddenly you won't care if your printf calls get elided or memoized.)
• lgas 9y ago
  I tried to do some quick benchmarks: % make hs Results: [25872791,24253954,21258158] make hs 6.53s user 3.99s system 245% cpu 4.282 total % make py 24029582 25343914 20814678 make py 22.37s user 0.11s system 99% cpu 22.593 total You can see the code as tested here[0]. I am not an expert on either Haskell or Python performance, all I did was use -O for python3 and -O2 for GHC. This was on a 2.8 GHz Core i7 Macbook, FWIW. Edit: Since 'contents' was unspecified I used one million random ints. [0]: https://github.com/lgastako/compimp/tree/as-tested https://github.com/lgastako/compimp/tree/as-tested
  • lgas 9y ago
    I was playing around a little more and I noticed that stack sets the following ghc-options by default: -threaded -rtsopts -with-rtsopts=-N which I assumed explained some of the speedup, so I disabled them and got a reduction to 99% cpu as expected, but unexpectedly the single threaded version was about twice as fast: % make hs Results: [24605537,25150983,21576960] make hs 3.13s user 0.07s system 99% cpu 3.211 total
    • bojo 9y ago
      Depending on your problem you can actually lose performance with a multi-threaded app due to the context switching overhead.
    • sbergot 9y ago
      Haskell threaded runtime can have poorer performances than the non-threaded one on single threaded programs.
  • vaibhavsagar 9y ago
    I took `contents` from here[0] but I like your random ints much better! [0]: https://github.com/vaibhavsagar/thursday-presentations/blob/6466b312ef07b4289c878356ddfcd6e4fba2f1d6/imperative-haskell/QuickSort.txt https://github.com/vaibhavsagar/thursday-presentations/blob/...
  • etatoby 9y ago
• cousin_it 9y ago
  Purity is tricky to define. For example (stolen from Reddit user gasche), if you can measure how much time a computation takes, then Haskell is impure, because a lazy value takes longer to compute the first time than the second. You could try to patch it up by saying the impurity must be observable via pure code, but that makes the definition circular. And that raises another problem, where printing to standard output becomes "pure" if the standard output can't be observed by pure code (which is true in Haskell). Another problem with seeing purity as fundamental is that our physical reality isn't a persistent data structure (past states aren't accessible), so the best algorithms possible won't treat it as one. Among the tons of papers describing fast algorithms, practically none are using purity, unless they required purity to begin with. And there's a third problem, specific to Haskell, that might interest you. The article is using ST to implement an impure computation. You'd think that ST itself can be implemented in pure Haskell, maybe with the usual logarithmic slowdown. But unfortunately no one knows how to do it, and there's a strong suspicion that the (pure) type signature of runST has no pure implementation at all, even with quadratic or exponential slowdowns. The reason is tricky to explain, but it's well covered on StackOverflow and Reddit. (That's not even going into the issues of quicksort. Suffice to say that a pure quicksort is hard to write, ST or no. The problem is that you need good pivot selection to prevent the quadratic worst case, but randomized pivot selection will lead to observable impurity in the output, because quicksort isn't stable. So you must use something like median of medians, making the algorithm much slower and more complicated.)
  • lmm 9y ago
    A pure language is one in which replacing any subexpression of any expression with the evaluation of that subexpression yields an equivalent expression. Of course this means "pure" is not an absolute term but rather relative to a given definition of "equivalent". But this isn't circular and is practically useful: if you're working in a context where precise execution time matters (e.g. cryptography) you really do need to use a different concept of "pure" language from what you would use in a more "normal" context where two programs that produce the same output are equivalent even if they take a different amount of time to execute.
    • 9y ago
• flavio81 9y ago
  Python (in its CPython) incarnation is pretty slow usually. You can use PyPy (a JIT implementation of most of the Python spec) for dramatically more speed, but the code needs to be ported to work under PyPy. The real comparison should be a language that is both functional and imperative and that allows you to write as brief a source code as you can do in Haskell. Such a language is Common Lisp, and it will compile directly to machine language doing many optimizations.
  • masklinn 9y ago
    > the code needs to be ported to work under PyPy. The only incompatibility is the `.copy()` calls which should be replaced by `list(contents)`, then it'll be cross-compatible between P2 and P3. Here's what I get with that (on a 2010 MBP) using the random generation of lgas above (1M random ints): > time python2.7 qs.py python2.7 qs.py 41.92s user 0.37s system 98% cpu 42.837 total > time python3.6 qs.py python3.6 qs.py 42.99s user 0.32s system 98% cpu 44.047 total > time pypy qs.py pypy qs.py 3.27s user 0.12s system 94% cpu 3.603 total There's a fair bit of variation but pypy is between 3.4 and 4
    • Veedrac 9y ago
      PyPy supports Python 3, so you don't need to port it at all.
• theoh 9y ago
  But since Haskell of course compiles to C or C--, it obviously doesn't follow that you can't implement purity in an impure language -- just not at the level of the typical metacircular interpreter beloved of FP people. I'm not sure what you'r saying exactly. A related issue is the "monads let us do things that are difficult to express in other ways" argument of Wadler's paper Essence of Functional Programming. I believe it, but also it's clear that the real attraction of monads is their rigorous foundation. They are simple to reason about correctly and mathematically about while providing useful features. What I'd argue is not the case is that it's difficult for a programming language implementer to come up with an abstraction that does something similar in an adhoc, less well-founded way. Maybe it's the same with implementing purity in a non-pure language. It's harder to hit the target of elegance, but it's the de facto situation on any existing hardware.
  • theoh 9y ago
    Since I've got a stray downvote, let me clarify: I'm pro-FP. Purity amounts to referential transparency which is uncomplicated. Haskell and similar languages have the character of arithmetic expressions (no side effects) evaluated mechanically. This claim is uncontroversial and is supported by the well known papers of Strachey and Landin. Monads are useful but their use does represent a decision to bring "the awkward squad" of side effects etc. into the clean elegant world of calculating the value of expressions. Alternative approaches might see imperative code written separately from pure code. It's surely a category error to say that purity is more essential than impurity. What's pure is the expression one types in, and its various reduced forms, culminating in a value. Impure is the messy causal world of real hardware and objects which have stubborn or mutable properties: the whole address-based system of letters in postboxes, for example. The world has state. That doesn't make the platonic ideal of an arithmetic expression any less real, but it's an abstraction of a certain circumscribed set of operations that we perform, typically on a blackboard or with pencil and paper. It's a tiny part of reality.
• etatoby 9y ago
  > it's not possible to emulate purity using an impure language The fact that Haskell code is routinely compiled into machine language, which is the most impure and imperative kind of code possible, disproves your point.
• mpweiher 9y ago
  Hmm...you mention x86 assembly. For some reason, we seem to be able to implement ("emulate") all these different languages in x86 assembly.