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

Purely Functional Data Structures (1996) [pdf]

cs.cmu.edu

Post reply on HN
Print view View original

41–50 of 98 posts

Re: Purely Functional Data Structures (1996) [pdf]

#41

Post by dllthomas »

paulgb wrote: post #5
2-718-281-828 wrote: post #3

is this being upvoted onto the homepage based on upvoters actually understanding that this paper from 1996 is of contemporary relevance and interest or more due to keywords like "pure", "functional", "data" and "structure"?

I can’t speak for everyone, but I upvoted it from nostalgia, having read the book version over a decade ago. I happened to be thinking about ordering a copy for the office just yesterday.

I have a copy on my desk. The bit about designing data structures by analogy to number systems (and limiting carry propagation) is really fun.

Re: Purely Functional Data Structures (1996) [pdf]

#42

Post by shepherdjerred »

tmtvl wrote: post #39

It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.

> at some point the code has to hit hardware

Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader.

It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.

Re: Purely Functional Data Structures (1996) [pdf]

#44

Post by Gravityloss »

shepherdjerred wrote: post #42
tmtvl wrote: post #39

It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.

> at some point the code has to hit hardware Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader. It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.

Which profession is expected to make progress on actual software performance?

Re: Purely Functional Data Structures (1996) [pdf]

#46

Post by fjeifisjf »

shepherdjerred wrote: post #42
tmtvl wrote: post #39

It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.

> at some point the code has to hit hardware Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader. It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.

That's a very naive view of computer science. That is the attitude of people who have given up and decided that computers are too big for science now.

Re: Purely Functional Data Structures (1996) [pdf]

#48

Post by gnulinux »

tmtvl wrote: post #39

It's weird that there are so many claims in here that the data structures and algorithms are perfectly performant yet there isn't even one look at generated assembly or any acknowledgement of the underlying system that is supposed to run the code. Proving things are Big O performant is neat, but at some point the code has to hit hardware.

> It's weird

It's not weird, this is standard in academic computer science. It would be weird to do otherwise. In a theoretical dissertation/paper like this you can't just randomly bring up compiled assembly, it's completely and utterly off topic, it's not any more on topic than bringing up if the code was ran by an interpreter, or JVM, or transpiled to Haskell, or ran on GPU etc...

Re: Purely Functional Data Structures (1996) [pdf]

#49

Post by shepherdjerred »

fjeifisjf wrote: post #46
shepherdjerred wrote: post #42

Earlier quoted context omitted.

> at some point the code has to hit hardware Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader. It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.

That's a very naive view of computer science. That is the attitude of people who have given up and decided that computers are too big for science now.

You're right, there are plenty of papers focusing on real-world performance. I chose not to capture the nuance because I wasn't sure how to express it succinctly.

Re: Purely Functional Data Structures (1996) [pdf]

#50

Post by shepherdjerred »

Gravityloss wrote: post #44
shepherdjerred wrote: post #42

Earlier quoted context omitted.

> at some point the code has to hit hardware Yes, but that's not a concern of a computer scientist. Implementation and execution of the algorithm are up to the reader. It's like complaining that engineers don't do enough novel computer science research; of course they don't! It's not their job.

Which profession is expected to make progress on actual software performance?

Computer scientists (and of course engineers) both care about real-world performance, but some computer scientists just care about the theory.
Post reply on HN