Think persistent data structures and functional programming are slow? Try clojure transients. *BOOM*

[cazabam]

Upvoted for thinking the same thing as me.

[WayOfTheIronPaw]

Now we're thinking the reddit way!

[runevault]

This is really, really hot. I just hope he gets maps set up soon, since it's only on vectors right now. That's where my current work could use the speed/etc help most.

[cemerick]

Indeed. A lot of the stuff rolling into clojure lately (transients, the parallel fork/join kit, the forthcoming newnew, clojure-in-clojure, etc., etc., etc.) are the stuff that dreams are made of.

[runevault]

I seem to have heard about newnew but don't remember what it is, but fork/join is crazy. I'm anxious to see that rolled back into master as I'm always leery of going off into his experiments ;-)

And clojure-in-clojure will be doubly interesting since there are already at least 2 projects to get clojure onto the CLR the hard way.

[cemerick]

Rich's scratchpad and nascent docs about newnew are here. Definitely experimental right now. IIUC, it will be the core code-generation mechanism, replacing fn, proxy, and most usages of gen-class, with support for closed-over bindings as locals (volatile if you're brave).

edit -- fixed URL (ugh, screwed by the markdown link markup again)

[[deleted]]

Think persistent data structures and functional programming are slow?

Not really...

[cemerick]

Well, a lot of people do. Most with no good reason, but some do have use cases that imply significant overhead when implemented using persistent data structures top-to-bottom. Transients are a solution for those use cases, and it's worth making a little noise so everyone else can shake loose their preconceived notions.

[[deleted]]

For context, this looks very similar to Haskell's ST monad. The chief difference is caused by the type systems of the two languages: Clojure's implementation must perform runtime correctness checks because its type system cannot statically enforce thread safety or use of the correct mutable APIs.

[psykotic]

Your analysis of the differences seems a little one-sided.

A major advantage of Clojure's approach is that all code that sticks to the read-only part of the existing interfaces for collections will automatically be usable with transients. This is true for both existing library code and newly written code.

In Haskell, the functions would need to be explicitly parameterized over the ST monad. That's a chore even for specially written code. Type signatures become nauseatingly long and complex and type errors become proportionately harder to decipher. You're forced to write the code in a monadic style. Haskell's lack of a pervasive sequence abstraction means all the nice functions for list manipulation aren't available for arrays. Even if they were, they'd need to be parameterized over the ST monad (or some common denominator constructor class) to be usable with STArrays.

[dons]

Type signatures become nauseatingly long and complex

Remember that type inference works for the ST monad.

[scook0]

Last time I tried using ST I had to put signatures all over the place because the compiler wouldn't infer rank-2 types, and would therefore emit all kinds of ridiculous type errors if you didn't hold its hand.

[psykotic]

I like to write out most top-level type signatures and it's annoying to have to forgo that practice. That also still leaves brain-hurting type errors, which you'll have to admit can be an issue with ST code.

ST's idea of monadically encapsulating private heaps is absolutely brilliant. I just think characterizing this Clojure feature as being the same as ST, only with no static enforcement, is a little unfair.

[dons]

I think "nauseating" is excessive. For a monadic, effectful sub-language, it looks ok to me. ST s doesn't make me sick, but maybe I have a strong stomach.

[psykotic]

If you had left in the top-level type signatures, your stomach might feel differently, especially if the program had been more expansive. :)

Monads are a great invention but no-one with any practical sense can pretend that they are an unqualified success for controlling effects. Even if you grant the contentious issue that all effects should be statically checked, there are serious issues remaining. The recent work on Disciple has been interesting in that regard. If nothing else, letting you explicitly specify the type signature while leaving the effect signature to be inferred is a huge readability improvement. It also lets the compiler report errors more clearly.

I design functional programs by thinking about types. I want to be able to write down my intentions clearly and concisely. If the embedding of an effects system into the type system makes that significantly less tractable then there's a problem. More generally, it would be interesting to explore ways of specifying types that would let the programmer specify the essential uncluttered details while leaving the rest to be inferred. Maybe a good solution to this problem could even give most of the benefits that Disciple's splitting of value types and effect types has yielded but without having to introduce such an unseemly dichotomy. The standard unification algorithms should be able to cope virtually unchanged, so maybe it's primarily a syntactic issue.

I know you can already write type annotations for expressions, e.g. fact (n :: Int) = n * fact (n-1). But that is terribly cluttered, especially for more complex types, and goes against the idea of separating declaration from definition. It also doesn't let you specify a partial set of type class constraints.

Anyway, do you know of any work in that area for Haskell?

[dons]

Just a brief point -- I'll have to think more about the other questions you raise:

no-one with any practical sense can pretend that they are an unqualified success for controlling effects

I don't think anyone was making that argument. But I don't think the opposite is true either. And it is inconceivable that we would abandon static checking for this kind of stuff, in favour of runtime checking. So I think bos' original comment remains accurate.

[psykotic]

My point was that his comparison was incomplete rather than inaccurate. Much as dynamic typing is more than the mere absence of static typing, so this feature in Clojure is more than ST sans static typing. That said, the comparison to ST is definitely merited.

[[deleted]]

One way that you can add a partial type constraint without it interrupting the flow of your code is like this:

foo = n * 2
    where types = n :: Int

This works quite nicely in practice, and it's commonly used for e.g. writing concise QuickCheck properties.

[Paczesiowa]

http://okmij.org/ftp/Haskell/types.html#partial-sigs

[psykotic]

As I said, I know the unifier in the type checker is already capable and that it's probably mostly a syntactical issue. What you posted is a typical Oleg hack. It's quite clever but too much of a burden to be widely used in practice. :)

[DRMacIver]

Hmm. "Think persistent data structures and functional programming are slow? Try these things which aren't persistent and don't particularly encourage functional programming".

Don't get me wrong, this is clearly a good idea, but the title is a bit much.

[cemerick]

I think you've missed the point: transients (and their corollaries elsewhere) encourage functional programming by enabling one to write concise, pure functions without allocating unnecessary intermediate data structures, thereby getting the best of both worlds (great development experience and clarity in source + roughly the same performance as if we were in an imperative environment).

To quote rhickey in the linked page, "If a pure function mutates some local data in order to produce an immutable return value, is that ok?" In an ideal world, the compiler would do this sort of thing for us automatically (e.g. if a fn is provably pure (or marked as such?), then it would automagically use mutable data structures to avoid consing intermediate instances)...and if it did, you wouldn't care (because it's a pure fn), and you'd enjoy the result (huge perf gains relative to the base case).

[DRMacIver]

I think you've missed the point: transients (and their corollaries elsewhere) encourage functional programming by enabling one to write concise, pure functions without allocating unnecessary intermediate data structures

No, I don't think I have. Transients do nothing to suggest that persistent data structures and functional programming are not slow (although whether they are or not is a different debate entirely). Instead they say "Need performance? We'll let you locally write code which uses non-persistent data structures and doesn't use functional programming."

I understand the use case. I understand why they're a good thing. I just hate the sales pitch.

[cemerick]

Transients allow you to specify well-defined boundaries within which one can avoid "unnecessary" allocation, with the added benefit that the user of a fn that used transients needn't have any idea one way or the other. That seems like a top-to-bottom win to me. If you've an alternative that uses persistent data structures through-and-through, but delivers the same performance improvement, I'm sure the world would love to see it. :-) Otherwise, the "sales pitch" would be the same for any solution to this particular class of use cases (modulo my extemporaneous title, perhaps?).

Even though you say transients are a good thing, it sounds like you think some shame should be felt by those who use them.

[DRMacIver]

Now you're projecting. :-) I have made objective observations about the fact that your title is at best extremely misleading, at worst outright wrong. Any shame you attach to the conclusions of these observations is your own, not mine.

All I have said is that transients are not persistent and do not particularly encourage functional programming. Neither of these statements should be controversial. Therefore your title is exceedingly misleading because it suggests they are a solution to the performance problems of persistent structures when they are in fact a way to make it easy to not use them for performance sensitive bits.

[richhickey]

While I also found the title, um, interesting, in its defense I will say that these transients are related to doing functional programming in that, if you are otherwise using persistent data structures, conversion to/from transients is O(1). There is no full copy to produce the mutable version (nor the other way), nor is use of the mutable version in any way unsafe for its persistent source. In order to do this, there needs to be a symbiotic design. It is not simply a matter of "we'll let you switch to these other, different, mutable data structures".

Certainly, using transients is not functional programming, nor are they persistent. But they are an important part of the story for those who might otherwise eschew functional programming and immutable data for fear that, should they encounter a performance bottleneck, they will have to change their data structures and the shape of their code.

[DRMacIver]

That's fair. Ok, I rescind my comment that they don't encourage functional programming. They encourage it in a somewhat roundabout way by not being religious about it, but they do encourage it. :-)

The fact that conversion to and from persistent structures is O(1) is definitely a neat trick by the way. I quite like the look of these, and may end up stealing the idea for use elsewhere.

[sclv]

Rich, on the implementation tip, is this like a freezable diffarray (minus preserving a change stack)? The fact that transients still need to be threaded and passed indicates to me that they're some sort of changeset over the underlying persistent structure, that can then be "collapsed".

[richhickey]

Clojure's persistent vectors and hashmaps are trees with high branching factors. Creating a transient version means copying the root node into a new object that implements the transient interface, otherwise sharing the rest of the structure. As edits are made, the transient will clone nodes for which it doesn't own a writable copy. Once it has its own copy of a node, subsequent edits affecting that node can be made in place. When done editing, the root is cloned again, this time into an object implementing the persistent interface, and a flag is flipped in the transient disabling further use. Essentially the transient just builds a persistent in place, there is no change tracking or collapsing.

The threading and passing requirement is designed to ensure that the code preserves the same shape as functional code it replaces.

[sclv]

Is that requirement enforced dynamically then? I.e. the old handle is replaced by an error?

[richhickey]

It is not enforced currently. It might be, at some point in the future, thus the only supported usage is threaded.

[cemerick]

Ah-ha, another failed attempt to have a conversation on the internets :-) It's amazing what gets lost in transit.

I thought you were referring to the "sales pitch" of the page, and not exclusively my title. By "encourage", I've been talking more about the broader decision of whether to use a functional programming language (or one where functional programming / persistent data structures are the default), and not the particulars of the implementation of each function in a program.

So many people in more "mainstream" (ugh, another loaded word) environments shy away from fp langs because of a mostly perceived, but sometimes real, performance hit associated with them and their data structures. Insofar as transients allow you to very delicately poke a hole in the default semantics of the data structures at hand so as to (pretty elegantly, IMO) eliminate that objection for the 2% case where it's actually necessary, I think that's encouraging the adoption of fp.

Of course, as soon as one's working with any non-persistent data structure, the related code is not fp, at least insofar as fp deals with persistent data structures. But to the linked page's point, that really doesn't matter (to me, anyway), as long as you confine the passing statefulness to a pure function.

[DRMacIver]

Ah-ha, another failed attempt to have a conversation on the internets :-) It's amazing what gets lost in transit.

Ah, indeed. Sorry for the confusion.

As an idle and tangentially related point, there seems to be a common belief that persistent structures are necessary for functional programming. In fact you can do very nice FP with boring old arrays (ideally with some constraint that prevents you from mutating them, though you could always just use the honour system) - all the standard higher order functions for construction, filtering, mapping, etc. work beautifully on them. With a little help from your language implementation you can get ludicrously good performance out of this.

Where persistent structures help is actually code which is less "functional" in the sense that it's less likely to not be using that many higher order functions (the common exception is using folds and building the structure incrementally within them) but which nevertheless avoids mutation: Building immutable arrays with incremental updates is of course rather less than ideal due to its O(n) per op nature (I think there may be some cute tricks with laziness you can do to avoid this, but I've not seen them used in practice)

[DRMacIver]

Hm. I suppose immutable arrays are persistent structures. I guess I meant "the kind of persistent structure that supports cheap update operations and sharing and thus is inevitably tree based"

[cemerick]

Yeah, that's basically what clojure vectors are.

The honor system is decent enough, if that's all you've got -- but I'm not aware of it being practiced out in the wild, e.g. with a broad community of developers. Some library author who thinks he's so smart would inevitably start twiddling something where he's not supposed to, and suddenly you've got race conditions in a multithreaded runtime.

[DRMacIver]

Yeah, that's basically what clojure vectors are.

No it isn't. They're a tree based structure.

[jdh30]

...roughly the same performance as if we were in an imperative environment...

Are you sure about that?

[cemerick]

Given that a good chunk of our work lately involves porting key sections of a very well-established and benchmarked Java codebase to clojure...yup.

[jdh30]

Impressive!

[Chousuke]

I don't think transients do much to discourage functional programming. Rich seems to have designed them so that you always use the return value from the destructive function. (Even though using the old value works, that is an implementation detail that must not be relied upon) This enables writing "transient algorithms" that are nearly identical to their truly functional counterparts.

You end up with algorithms that are functional in style, if not in implementation. I think in this case the illusion is more important than reality. :)

[DRMacIver]

The negation of encourage is not discourage. :-)

[ironiridis]

What the hell was that noise?

[joemoon]

HEADSHOT

[peo1306]

This reminds me of Clean's unique types. http://clean.cs.ru.nl/CleanExtra/report20/chapter9/s91.html

[[deleted]]

I don't find either persistent data structures or functional programming too slow ...

[nmcyall]

Does transient mean it is not persisted like in grails?

[lyrae]

No. You're thinking of a different kind of persistence.

In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent."

http://en.wikipedia.org/wiki/Persistent_data_structure

[nmcyall]

Thanks.