Hacker News Reader

I suppose I can only speak for myself, but as a functional programmer I would never ask you to give up mutation completely.

I do think it's nice that most FP languages give us pure functions and persistent data structures that are easy to use and relatively performant, so we don't have to go out of our way to provide a pure (by construction) abstraction when we want to.

The key idea is to be honest when you are asking for mutation. Haskell would likely be far on the "left wing" (or right wing?) on your political spectrum but you can do mutation whenever you please as long as you're honest and mark it in the types with something like IO, State, or ST (Clojure does something similar in spirit with 'transient'). There is even unsafePerformIO if you are absolutely sure that you are wrapping an impure computation in a way that you know looks pure from the outside.

Purity isn't promoted because it's a virtue. It's that pure expressions generally come with nice commutativity and idempotency laws which give you the ability to refactor code while remaining confident you won't change its meaning or alter the behaviour of distance subsystems. It's worth preserving those properties when you can.

One can achieve commutativity and idempotency in a side effect based language as well...but one has to redo the programming model to achieve it:

http://research.microsoft.com/pubs/211297/managedtime.pdf

Maybe, what I am thinking is that a language which makes it easy to program in a functional style, should make it equally easy to program in an imperative one. By extension, this may mean that a good language for functional programming ought to make it easier to program imperatively than languages designed to facilitate imperative programming.

Of course, this begs the question of what is easier and harder and better and worse. There's a case to be made that Haskell's monads make imperative programming easier. It's essentially a mathematical argument - rather abstracto-theoretical versus the sort of concrete arguments that get advanced to avoid discussions of why it might be better to reason with lambda-calculus versus using von-Neumann as a model.

To put it another way, being able to abstract away von-Neumann into mathematics is useful. But the von-Neumann model is useful because it is a model that we can easily get our heads around.

If you asked a Haskell expert what their favorite imperative language is, they'll probably say "Haskell."

That is because it "makes it easier to program imperatively" more than any other language I've met.

Only after the learning curve, though. It isn't immediately approachable as an imperative language.

Yes, but suppose you could write the same program in two languages, a classic imperative one, and a purist and difficult FP language.

For the sake of argument, let's assume the classic imperative language is easier to approach for rookies. If it's also the easiest language to write bugs and make mistakes with, wouldn't the "harder" FP language still be a net win? As long as its learning curve isn't unapproachably steep -- i.e. so steep that your time to market becomes awful -- what is the advantage of the imperative language's ease to hit the ground running and writing lots of bugs?

If language 'a' lets a person write a program with 'b' bugs in time 't', and language 'aa' lets the same person write the same program with 'b' bugs in time 't-n' then there is a clear net win for all 'n' > zero.

If 'aa' also has the advantage of providing semantics for producing significantly less buggy code in time 't-n-m' at some future time then that is also an advantage but a distinctly different one and one which can be deferred [and probably will be given a significant learning curve].

The first step toward the modern automobile was the 'horseless carriage' not the Countach.

It's greatly overstating the learning curve. It's possible to pick up Haskell by simply writing a few small applications tackling different parts of the language in each one. This can be done in a few months. Not to mention there are now numerous resources available for free such as learn you a haskell, real world haskell, and countless blog posts.

I hear the Wikibook also has a good introduction.

> The first step toward the modern automobile was the 'horseless carriage' not the Countach.

Lamborghini makes shit cars. The only reason people rave about them is because they have giant engines. A car without a reverse gear is one of the stupidest ideas in automobile history.

I used "Countach" for its word value. It's alliterative and has little rhyming potential and is loaded suggestively with images of suits with shoulder pads. An absurdity is not accidental.

"But the von-Neumann model is useful because it is a model that we can easily get our heads around."

I am skeptical of this statement.

Programmers make a lot of errors when reasoning about mutable state, so I don't think it's fair to say "we can easily get our heads around the von-Neumann model". My intuition is programs written without mutable state will, on average, have fewer errors, which suggests to me the more "mathematical" nature of functional programming is actually easier to wrap one's head around.

Not sure what empirical data is out there to test this hypothesis.

I probably wasn't clear enough. My point is that the von-Neumann model allows us to walk up to a computer and point and say, "Here is the memory and here is the processing unit and here on this test probe of register 47 we see the instruction to move the contents of memory address 42 from memory into register 19." Even my mom can understand a sketch of the von-Neumann model to some degree.

Because functions are not a model of a computer, but a means of computation, there's no obvious picture. Indeed, if I look at the test probe, I don't see a function but an instruction to move the contents of memory address 42 from memory into register 19. I can draw a diagram of a Turing machine in a few minutes, not so with the lambda calculus. The equivalence is only mathematical, and that cuts both ways. There's no way to write a functional version of The Art of Computer Programming because mathematical equations don't have running times.

I think you hot the mail on the head there. That the delta between mathematics and programming is time. Lee Smolin makes a similar case for physics.

No, you shouldn't give up mutability or in-place algorithms. As you said, performance concerns demand them at times.

Haskell has a nice approach to that problem. Data is immutable by default, but mutable primitives are available. The type system forces you to be explicit about when you're using mutability, so that mutable data can never accidentally creep into logic where you relied on immutability for correctness.

Broadly speaking, most mutable data types fall into two categories: Those that are some flavor of "IO," and those that are some flavor of "ST." In brief, the IO type is Haskell's way of dealing with operations that logically must be performed in the right order. (In-place operations require as much.) You can think of IO as one continuous chain of operations that begins and ends with the lifetime of the program. In other words, you can't just drop in and out of IO at will; the chain must be unbroken.

ST is an interesting variant on the same idea, except it does allow you to drop in and out at will. That is, I can enter ST at any point in my program, including the functionally pure parts. How is this possible? Because it imposes a restriction that's not present with IO: You must not touch the outside world from within ST. In any ST function, you get your own little mutable sandbox, but as with any pure function, you can only see that which is passed to you, and all you can do to the outside world is return a value. So you can, e.g., take an immutable list, create a copy that you sort in-place, then return the sorted list as an immutable value.

IO and ST are each flexible in their own ways. With IO, you can do almost anything, including mutating something that's passed in by reference. That can be important for some programs' performance. ST is flexible in a different way: You can sneak it into pure functions.

Having finally decided to read Knuth's main works, I have to confess I am being drawn more and more heavily into this way of seeing things.

The beauty of how Dancing Links works is rather remarkable. Similarly, finally understanding how to read some of the algorithms as specified has helped to see just how "imperative" algorithms can be analyzed rather comprehensively.

Also, as a major aside, I would encourage more folks to try the Knuth works. Definitely feel free to skim the math, as that is some pretty hairy stuff. At the same time, keep trying to go back to it later. Most of it isn't undoable, so much as it is just completely foreign to what you probably do day to day. Seeing the connection between it and many typical programming tasks can be tough. (Indeed, I don't think I've done so, yet.)

I assume by Knuth's main works you're meaning his The Art of Computer Programming. If you've got a decent math background (college level with some discrete math and calculus, it will still be pretty difficult for solo study by someone with just a high school math background) and find the stuff in Volume 1 to be a bit too difficult, I recommend Concrete Mathematics. It's essentially the math portions of Chapter 1 extended to a full text. I found it much easier to get into. Some portions are essentially calculus for discrete functions. Reading it made a lot of the calculus things that I had difficulty with suddenly click (I passed Calculus II by willpower, not understanding).

:) I did indeed mean that. And, oddly enough, I did just pick up Concrete Mathematics. I am just close enough to "get" much of the math. What I can't do is make some of those leaps myself. Worse, I'm not entirely clear how they relate to what I do, day to day.

Despite all of that. I am loving every moment of these books. Highly highly recommended.

> What language is best for implementing mutable state?

I would say a language that is pure and has a strong static type system. And I say that because those languages allow you to track exactly where mutation is happening (you're using dynamite) and deal with it appropriately.

Actually, because Clojure is not ideological (though it is very opinionated) -- and certainly not pure -- but rather very pragmatic, it includes a very interesting feature called transients[1]. Transients temporarily turn a persistent collection into a mutable (in place) one in O(1), specifically to allow efficient in-place algorithms like quicksort.

[1]: http://clojure.org/transients

I'm pretty sure that it is possible to make a function in Haskell which, while it mutates variables, these variables are all local, so you are still able to offer up a purely functional interface to the world outside of that function.

Whether this is simple and straightforward or even demands some "magic" which isn't usually part of the language semantics - that I don't know. Imperative code seems very doable and maybe even pleasant in Haskell, but I don't know how simple it is to actually write imperative code that is efficient - e.g. destructive updates and all that, rather than making a new value for each "update" and programming in an imperative style though you are really just using immutable values all the time.

This is actually very simple and straightforward to do using the ST monad[0]. See the paper Lazy Functional State Threads[1] for details.

[0] http://hackage.haskell.org/package/base-4.7.0.0/docs/Control...

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144...

> I'm pretty sure that it is possible to make a function in Haskell which, while it mutates variables, these variables are all local, so you are still able to offer up a purely functional interface to the world outside of that function.

Indeed, it's called the ST monad. The internals aren't that magical, behind the scenes GHC does some state passing like IO but nothing too fancy. The real trick is using -XRankNTypes for the runST function[1] to track "state threads" at the type-level.

        example1 :: Int
	example1 = runST $ do
	  x <- newSTRef 0

	  forM_ [1..1000] $ \j -> do
	    writeSTRef x j

	  readSTRef x

[1]: http://research.microsoft.com/en-us/um/people/simonpj/Papers...

State can be local, but you need an escape analysis to verify that it doesn't leak the context if your language supports aliases, which I believe Haskell doesn't (or to say, aliases don't make sense in Haskell).

Clojure's syntax for transients is deliberately more cumbersome. A Scheme like 'loop! would flag the decision to employ mutation. Instead, Clojure steps outside the conventions of dynamic typing and expressions and requires something that looks like a static type specification and another thing that looks a lot like a 'return statement.

To put it another way, the language complects mutation instead of simplifying it and it's reasons for doing are...well, what's the difference between an ideology and an enforced opinion?

Clojure is rarely introduced with, ok here's how you can do exactly what you were doing before in Clojure, and now here are some ways that you might think about doing it differently. Instead, Quincy autopsying the corpse before the opening credits are even finished.

None of which is to say that I don't like Clojure. It's just that the really important question is part of the theology rather than evangelical outreach. Java in Clojure probably isn't good Clojure, but it might often be better Java. 20% less imperative code is probably an improvement.

This comment is very confusing. You spend a lot of time complaining about how Racket is overly focused on functional programming, leading to slower data structures. But the queue data structure you refer to is an imperative queue with O(1) operations for everything. Also, it isn't a priority queue.

The Rosetta code example for Priority Queues in Racket is also built on a mutable heap data structure. Of course, it has more complex time bounds, because of priorities, but not because of immutability.

Finally, the Rosetta code example for Queues in Racket uses `mcons` (which you claim is somehow taboo) explicitly.

For a non-FP quicksort in Clojure, see: http://stackoverflow.com/questions/12176832/quicksort-in-clo...

What do you think, in terms like this, of the ST monad work in Haskell?

You could look at Rust? It has mutable state but strict ownership which is enforced at compile time.

My irrational preferences fall along the lines of Lisp, and I think Scheme has the right syntactic approach to mutation: Put a '!' on the end so that it's explicit, but don't make it syntactically a mess like Racket does where mutable lists have to be 'mcons-ed up step by step rather than made in one pass (not that there's anything wrong with writing a macro, it just means that there's an additional layer of misdirection when using mutation, and that's exactly the place where you don't want it.

Ordersky's Scala takes an approach similar to Racket in regard to type casting - purposely making the syntax a bit more cumbersome as a flag rather than...well flagging the action explicitly. That said, I like Scala's ML like features, and Ordersky opens Scala by Example [1] by illustrating the transition from imperative to functional style in a Scala implementation of quickSort.

Rust looks interesting. One of the big things though that I look for is an over-abundance of documentation and resources. I'm learning Scala because Ordersky teaches a course on Coursera and the decade of people writing about it in general and the fact that one could write about Scala and potentially make money doing it due to the size of the JVM market, means that the literature about the language isn't so much some necessary evil for people who like writing languages more than documenting them.

[1] http://www.scala-lang.org/docu/files/ScalaByExample.pdf

> One of the big things though that I look for is an over-abundance of documentation and resources.

..... stay tuned.

I'm not sure what you mean by "syntactically a mess" but Racket provides `mlist` which sounds like exactly what you want [1].

[1] http://docs.racket-lang.org/compatibility/mlists.html

Thanks. It's not linked from the Racket Reference. Clicking on "mutable lists" in 4.10 is a 'did you mean recursion?' experience.

http://docs.racket-lang.org/reference/mpairs.html?q=mcons#%2...

That it takes an intimacy with the code base of a regular repo contributor to find it suggests how deeply buried 'mlist is.Or to put it another way, Racket the language does not provide 'mlist. Racket the ecosystem does but deliberately makes it hard to use (by obfuscation) on the moral ground that mutating a list ought incur the pain of iterative 'mcons-ing...and it's associated pretty-print. .

For us that were around when the default changed from mutable to immutable cons cells, known the rule "just prepend an m". I agree that the link in section 4.10 can be improved - but calling it "obfuscation" and "deliberate" is taken it too far. File a bug report, and I bet it will be fixed.

'mcons is part of 'racket/base. 'mlist is part of a library that contains two layers of warnings, is not linked to by the Racket Guide or Racket reference and lives under the 90th of 96 links on the Documentation page. It's lower in the great chain of being than "Unstable May Change without Warning".

(cons 1 (cons 2 (cons 3 '()))) is commonly required in the Racket family of languages for purely pedagogical purposes. That it is the only pattern for 'mcons provided by 'racket is a deliberate statement of community values in regard to mutable lists.

In regards to filing a bug report, the bug is that there is mention of mutable lists and a hyper-link in the documentation for the Racket Language. Because mutable lists are not part of the language the bug fix is properly removing the reference - at least in so far as maintaining consistency with the rest of the documentation because other libraries are not cross linked from the Guide and Reference. Linking "mutable lists" to 'compatibility/mlist, would just replace one bug with another...unless leaving 'mlist out of 'racket/base was itself a bug. That that is the case, is unlikely.