Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Clojure’s Approach to Identity and State (2008)

clojure.org

Post reply on HN
Print view View original

31–40 of 69 posts

Re: Clojure’s Approach to Identity and State (2008)

#31

Post by slifin »

6thaccount2 wrote: post #26
agumonkey wrote: post #10

Earlier quoted context omitted.

IIUC Rich Hickey probably did just that too, writing ad-hoc version of clojure semantics in cpp before making his own language enforcing this.

I recall he was big into SBCL, but most IT organizations wanted all code to run on the JVM or CLR. So he had to make a Lisp to run on the JVM and Armed Bear Common Lisp apparently wasn't exactly what he wanted. I want to learn Clojure, but there are definitely some road blocks. I don't have the time for Emacs, it'd be a pain to get a Cursive license (although the cost is extremely reasonable I'd have to do paperwork…

If you're learning Clojure then you can use cursive for free until you go commercial with it?

Re: Clojure’s Approach to Identity and State (2008)

#32

Post by fazzone »

etbebl wrote: post #6

This is interesting. I've tried Clojure, and heard about the idea of avoiding mutable data and using pure functions plenty of times, but imperative/OOP have still always made the most sense to me. When reading this though, something clicked because I've encountered the problem of getting a stable state to read/write without blocking other operations, and dealt with it in C++ in a similar way to Clojure without realiz…

This is pretty much how clojure atoms [0] work. It's basically a Clojure wrapper around a Java AtomicReference, but Clojure's immutable data structures make an atomic reference type really useful because it is very cheap to read a "snapshot". It doesn't do upfront allocation, because like you mentioned, that requires you to have some knowledge about how the accessing code works. Additionally, whatever you are doing in Clojure is pretty likely to allocate memory anyway, so it probably wouldn't be that beneficial.

[0] https://clojure.org/reference/atoms

Re: Clojure’s Approach to Identity and State (2008)

#33

Post by sbov »

stuhood wrote: post #12

Immutability is very helpful, and the connection between values and identity is illuminating. But there have been very important developments in programming languages since this post/page was written: notably, the introduction of "borrow checking" (exemplified by Rust's implementation). Borrow checking has a very significant positive effect on the sustainability of imperative code, which makes the claim that "imperat…

Rust doesn't let you have a mutable reference while you have immutable ones. It's only a problem in Rust because mutating the underlying data would cause problems for chunks of code using the immutable data.

But in Clojure it's not a problem. I find lots of applications where working with stale, consistent data is just fine.

Also, if you ever need to rewind your state Clojure's immutability makes it trivial. I've used this in e.g. latency compensation for multiplayer games.

Re: Clojure’s Approach to Identity and State (2008)

#34

Post by etbebl »

fazzone wrote: post #32
etbebl wrote: post #6

This is interesting. I've tried Clojure, and heard about the idea of avoiding mutable data and using pure functions plenty of times, but imperative/OOP have still always made the most sense to me. When reading this though, something clicked because I've encountered the problem of getting a stable state to read/write without blocking other operations, and dealt with it in C++ in a similar way to Clojure without realiz…

This is pretty much how clojure atoms [0] work. It's basically a Clojure wrapper around a Java AtomicReference, but Clojure's immutable data structures make an atomic reference type really useful because it is very cheap to read a "snapshot". It doesn't do upfront allocation, because like you mentioned, that requires you to have some knowledge about how the accessing code works. Additionally, whatever you are doing i…

Oh neat, thanks! Yup, that sounds like a more general/flexible version of what I was trying to do.

I was focused on situations with just one writer (and originally also one reader), with the main thing being avoiding allocations. The situation where future values actually depend on past values, and specifically the current past value with other writers in the mix, is definitely trickier.

Re: Clojure’s Approach to Identity and State (2008)

#35

Post by skybrian »

sbov wrote: post #33
stuhood wrote: post #12

Immutability is very helpful, and the connection between values and identity is illuminating. But there have been very important developments in programming languages since this post/page was written: notably, the introduction of "borrow checking" (exemplified by Rust's implementation). Borrow checking has a very significant positive effect on the sustainability of imperative code, which makes the claim that "imperat…

Rust doesn't let you have a mutable reference while you have immutable ones. It's only a problem in Rust because mutating the underlying data would cause problems for chunks of code using the immutable data. But in Clojure it's not a problem. I find lots of applications where working with stale, consistent data is just fine. Also, if you ever need to rewind your state Clojure's immutability makes it trivial. I've use…

If you choose to create immutable snapshots of your objects, I imagine the same could be done in Rust?

Re: Clojure’s Approach to Identity and State (2008)

#36

Post by microcolonel »

neonate wrote: post #8
microcolonel wrote: post #4

This has been extremely useful to me while writing a (somewhat optimizing) compiler for spreadsheets. I can do subtree deduplication just by `assoc`ing into a map.

I want to hear more about your somewhat optimizing compiler for spreadsheets!

It's proprietary for the time being; but in short, it is more straightforward than I thought it would be.

We are working with LibreOffice Calc ODS sheets, which are pretty terrible as a format (since the references are not normalized in the formulas, they can't repeat them even when they behave identically, and they duplicate most of the XML namespaces in the attributes).

We parse and normalize the references from A1 to R1C1 form, and then deduplicate the formulas (by text) and extract all of the immediates (and mark some of them as input, so that they can be varied at runtime).

Then we pass the deduplicated formulas through instaparse (which is spectacular) with a relatively simple grammar, and propagate some of the constants.

I then extract the references from the AST, while at the same time replacing SUMIF/MINIFS/MAXIFS/AVERAGEIF and similar with simple addition/min/max of known cells, where the tests are known at compile time. Then those ASTs are complied to functions (ignoring our cross-function optimizations).

Then it's just down to generating a complete DAG of dependencies, and using that to sort the assignments (cells) topologically. The sheet can be evaluated naiively at that point by injecting the references into each subsequent assignment/cell and storing the result in a map (ranges injected as a seq over a range).

There's a lot more to it, and it's getting better all the time, but that's the gist of it. Many real spreadsheets are not well-behaved, and they have dependency patterns which are more difficult to handle (i.e. ranges that refer to the current cell, or future cells, dynamically). The compiled output is getting more and more static, and will probably be reduced to some form of ssa, possibly even well-formed enough to be popped casually into LLVM.

It would be some help if the ODS format were improved, it takes several seconds just to parse the hundreds of megabytes of XML in our amazing spreadsheet, and a lot of it is redundant.

Re: Clojure’s Approach to Identity and State (2008)

#37

Post by microcolonel »

louthy wrote: post #7
microcolonel wrote: post #5

Earlier quoted context omitted.

Regarding values: you can construct the same datastructure in any place, and compare it meaningfully with a datastructure from a completely different source (and you can do so efficiently). This is accomplished, as far as I know, by representing almost everything as persistent hash trees (with some implementation voodoo and shortcuts). Beyond that, you can actually just read the Clojure runtime code. It's a bit messy…

Persistent hash tries [1] I have an efficient C# implementation here [2] [1] https://michael.steindorfer.name/publications/phd-thesis-eff... [2] https://github.com/louthy/language-ext/blob/master/LanguageE...

I love seeing these datastructures show up in more languages. They completely change the set programs you could feasibly find time to write. Thanks for sharing your C# one, I'll remember that if I ever need to use Unity again. The claims about CHAMP are very impressive, in my experience, Clojure's datastructures perform great for what they do, and they claim CHAMP tends to be many times faster. :- )

> Compressed Hash Array Map Trie

Q: “What datastructure would you like?”

A: “Yes.”

Re: Clojure’s Approach to Identity and State (2008)

#38

Post by namelosw »

stingraycharles wrote: post #15
stuhood wrote: post #12

Immutability is very helpful, and the connection between values and identity is illuminating. But there have been very important developments in programming languages since this post/page was written: notably, the introduction of "borrow checking" (exemplified by Rust's implementation). Borrow checking has a very significant positive effect on the sustainability of imperative code, which makes the claim that "imperat…

Borrow checking and immutability solve two different problems. Immutability is about the absence of ownership and state, while borrow checking is a way to manage ownership. One does not replace the other, they coexist solving different problems.

Not totally different, with strict immutability enforced for the whole language there's no need for borrow checking. Because there's no identity at all. You don't have to borrow number 3 because another number 3 is the same 3 as any other 3.

Re: Clojure’s Approach to Identity and State (2008)

#39

Post by stuhood »

casion wrote: post #24
stuhood wrote: post #21

Earlier quoted context omitted.

Borrow checking allows even structures that support mutation to be safely (checked by the compiler) treated as immutable, and thus as values. Clojure also recognizes the connection between ownership and mutability in its "transients": https://clojure.org/reference/transients ... compile time borrow checking extends that idea to an entire language.

What do transients have to do with ownership? They are simply a way to gain new performance characteristics from an existing data structure.

The thing that makes it safe to use mutation in the context of a transient is that you can know with certainty that you have exclusive access to the value (because no other viewer has observed it yet). This is also what borrow checking can guarantee: except in significantly more positions in the code, and at compile time rather than runtime.

Re: Clojure’s Approach to Identity and State (2008)

#40

Post by wilsonthewhale »

stingraycharles wrote: post #15
stuhood wrote: post #12

Immutability is very helpful, and the connection between values and identity is illuminating. But there have been very important developments in programming languages since this post/page was written: notably, the introduction of "borrow checking" (exemplified by Rust's implementation). Borrow checking has a very significant positive effect on the sustainability of imperative code, which makes the claim that "imperat…

Borrow checking and immutability solve two different problems. Immutability is about the absence of ownership and state, while borrow checking is a way to manage ownership. One does not replace the other, they coexist solving different problems.

Yup, this is the reason why both Rust and Clojure are my favorite languages. The same problem (concurrency), with solutions pretty much on opposite ends of the spectrum. One with pervasive immutability and the other with static checking.
Post reply on HN