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

Are arrays functions?

futhark-lang.org

Post reply on HN
Print view View original

121–130 of 145 posts

Re: Are arrays functions?

#121

Post by Majromax »

VorpalWay wrote: post #88
tombert wrote: post #73

Earlier quoted context omitted.

I've been watching those Kaze Emanuar videos on his N64 development, and it's always so weird to me when "doing the expensive computation again" is cheaper than "using the precomputed value". I'm not disputing it, he seems to have done a lot of research and testing confirming the results and I have no reason to think he's lying, but it's so utterly counter-intuitive to me.

I haven't looked into N64, but the speed of CPUs has been growing faster than the speed of RAM for decades. I'm not sure when exactly that started, probably some time in the late 80s or early 90s, since that is about when PCs started getting cache memory I believe .

I wonder if a breakpoint was out-of-order execution. Many computations would use some values from memory plus other that could be computed, and out-of-order execution would allow the latter to proceed while waiting on memory for the former. That would improve utilization and be a 'win' even if the recomputation in isolation would be no faster than the memory load.

Re: Are arrays functions?

#122

Post by adastra22 »

wvenable wrote: post #67
adastra22 wrote: post #45

Earlier quoted context omitted.

There are two opposing philosophical viewpoints here. Some view mathematics as a model for understanding the real world. Some see the real world as instantiation of mathematics. Is an array a function? From one perspective, the array satisfies the abstract requirements we use to define the word "function." From the other perspective, arrays (contiguous memory) exist and are real things, and functions (programs) exist…

An array isn't a function -- indexing an array could be a function. But an array is a data structure. An array doesn't satisfy the requirements to be a function -- people are just confusing an array with array indexing.

In the mathematical sense a function is something that maps inputs to outputs. That’s also what an array is.

But this whole thing is uninteresting because it is ultimately just a disagreement about definitions.

Re: Are arrays functions?

#123

Post by eru »

VorpalWay wrote: post #68
eru wrote: post #36

Earlier quoted context omitted.

> It was odd to me, because it hadn't really occurred to me before that, given infinite memory (and within a mathematical framework), there's fundamentally not necessarily a difference between a "list" and a "function". You don't even need infinite memory. If your function is over a limited domain like bool or u8 or an enum, very limited memory is enough. However the big difference (in most languages) is that functio…

> However the big difference (in most languages) is that functions can take arbitrarily long. Array access either succeeds or fails quickly. For some definition of quick. Modern CPUs are usually bottlenecked by memory bandwidth and cache size. So a function that recomputes the value can often be quicker than a look up table, at least outside of microbenchmarks (since in microbenchmarks you won't have to compete with…

> For some definition of quick. Modern CPUs are usually bottlenecked by memory bandwidth and cache size.

I meant in most languages functions aren't guaranteed to return in finite time at all.

Re: Are arrays functions?

#124

Post by eru »

VorpalWay wrote: post #88
tombert wrote: post #73

Earlier quoted context omitted.

I've been watching those Kaze Emanuar videos on his N64 development, and it's always so weird to me when "doing the expensive computation again" is cheaper than "using the precomputed value". I'm not disputing it, he seems to have done a lot of research and testing confirming the results and I have no reason to think he's lying, but it's so utterly counter-intuitive to me.

I haven't looked into N64, but the speed of CPUs has been growing faster than the speed of RAM for decades. I'm not sure when exactly that started, probably some time in the late 80s or early 90s, since that is about when PCs started getting cache memory I believe .

The N64 was just really weirdly designed: they went with an overpowered CPU for bragging rights, and bet on the wrong RAM horse, Rambus.

Re: Are arrays functions?

#125

Post by swiftcoder »

antonvs wrote: post #80
swiftcoder wrote: post #71

This is one of those rare times when I read something coming out of the FP community and go "oh, you mean iterators, we've had those for decades over here in imperative-programming land"

Traditional FP has had functional equivalents to iterators since before most imperative languages existed. LISP had a map function (MAPCAR) in its earliest versions, in the 1950s. Later that was generalized to folds, and the underlying structures were generalized from linked lists to arbitrary “traversable” types, including unbounded streams. The language in the OP is a special-purpose language for data parallelism,…

That's not really the lens I'm looking at it through. It's just entertaining that we're still discussing arrayfunction equivalence in the year of our lord 2026, long after every mainstream language supports said equivalence in practice.

Re: Are arrays functions?

#126

Post by d-us-vb »

CyberDildonics wrote: post #116
d-us-vb wrote: post #52

Earlier quoted context omitted.

> No, the best thing you can do for simplicity is to not conflate concepts. This presumes the framework in which one is working. The type of map is and always will be the same as the type of function. This is a simple fact of type theory, so it is worthwhile to ponder the value of providing a language mechanism to coerce one into another. > This is cleverness over craftsmanship. Keeping data and execution as separate…

This presumes the framework in which one is working. One doesn't have to presume anything, there are general principles that people eventually find are true after plenty of experience. The type of map is and always will be the same as the type of function. This is a simple fact of type theory, so it is worthwhile to ponder the value of providing a language mechanism to coerce one into another. It isn't worthwhile to…

> One doesn't have to presume anything, there are general principles that people eventually find are true after plenty of experience.

I guess I just disagree with you here. Plenty of programmers with decades of experience have found no such general principle. There is a time and place for everything and dogmatic notions about "never conflate X and Y" because they're "fundamentally different" will always fall flat due to the lack of proof that they are in fact fundamentally different. It depends on the framework in which you're analyzing it.

> It isn't worthwhile to ponder because this doesn't contradict or even confront what I'm saying.

This is a non sequitur. What is worthwhile to ponder has no bearing on what you say. How arrogant can one person be?

> It might be personal research, but people have been programming for decades and this stuff has been tried over and over.

Decades? You think that decades is long enough to get down to the fundamentals of a domain? People have been doing physics for 3 centuries and they're still discovering more. People have been doing mathematics for 3 millennia and they're still discovering more. Let the cycle happen. Don't discourage it. What's it you?

> You're mentioning things that you expect to be self evident, but I don't see an explanation of why this simplifies programs at all.

It may not simplify programs, but it allows for other avenues of formal verification and proof of correctness.

----

Do you have other examples of where concepts were conflated that ended up "burning" the programmer?

Re: Are arrays functions?

#127

Post by antonvs »

swiftcoder wrote: post #125
antonvs wrote: post #80

Earlier quoted context omitted.

Traditional FP has had functional equivalents to iterators since before most imperative languages existed. LISP had a map function (MAPCAR) in its earliest versions, in the 1950s. Later that was generalized to folds, and the underlying structures were generalized from linked lists to arbitrary “traversable” types, including unbounded streams. The language in the OP is a special-purpose language for data parallelism,…

That's not really the lens I'm looking at it through. It's just entertaining that we're still discussing array function equivalence in the year of our lord 2026, long after every mainstream language supports said equivalence in practice.

I suspect there are two points you haven't fully understood:

1. The equivalence being discussed is not supported in "every mainstream language" in practice. If you disagree, read https://news.ycombinator.com/item?id=46699933 for a good overview of the equivalence in question and explain how you think mainstream languages support that.

2. The current discussion is in the context of a language targeting CUDA. Currently, very few languages aside from C++ have good CUDA support, and C++ certainly doesn't achieve that by having its arrays be equivalent to functions "in practice" or in any other sense.

Just as an example of what OP is addressing, FTA:

> "To allow for efficient defunctionalisation, Futhark imposes restrictions on how functions can be used; for example banning returning them from branches. These restrictions are not (and ought not be!) imposed on arrays, and so unification is not possible. Also, in Futhark an array type such as [n]f64 explicitly indicates its size (and consequently the valid indices), which can even be extracted at run time. This is not possible with functions, and making it possible requires us to move further towards dependent types - which may of course be a good idea anyway."

As such, it seems to me your comments about this are wildly off the mark.

Re: Are arrays functions?

#128

Post by antonvs »

brabel wrote: post #99
lioeters wrote: post #85

Earlier quoted context omitted.

That'a great example that demonstrates the idea in the article. And it concisely shows a functional insight in the language design of Clojure. I'm not a daily Lisp user yet, but as I learn more about it, I'm drawn to its many charms.

This particular case is unique to Clojure, I believe. You definitely can’t do that in Common Lisp , and Scheme I am not so sure. It was one of the main motivations for Rich Hickey to make the language more uniform so that a few functions work on any number of data structures.

> This particular case is unique to Clojure, I believe.

It also works in pure lambda calculus (assuming you define a vector type). But in lambda calculus, literally every value is a function.

Re: Are arrays functions?

#129

Post by CyberDildonics »

d-us-vb wrote: post #126
CyberDildonics wrote: post #116

Earlier quoted context omitted.

This presumes the framework in which one is working. One doesn't have to presume anything, there are general principles that people eventually find are true after plenty of experience. The type of map is and always will be the same as the type of function. This is a simple fact of type theory, so it is worthwhile to ponder the value of providing a language mechanism to coerce one into another. It isn't worthwhile to…

> One doesn't have to presume anything, there are general principles that people eventually find are true after plenty of experience. I guess I just disagree with you here. Plenty of programmers with decades of experience have found no such general principle. There is a time and place for everything and dogmatic notions about "never conflate X and Y" because they're "fundamentally different" will always fall flat due…

What is worthwhile to ponder has no bearing on what you say.

Ponder all you want, but what you said wasn't a reply to what I said.

Decades? You think that decades is long enough to get down to the fundamentals of a domain?

It is enough for this because people have been going around in circles constantly the entire time. It isn't the same people, it is new people coming in, thinking up something 'clever' like conflating execution and data, then eventually getting burned by it when it all turns into a quagmire. Some people never realize why their projects turned into a mess that can't move forward quickly without breaking or can't be learned without huge effort of edge cases.

It depends on the framework in which you're analyzing it.

No it doesn't. There are a bunch of fundamentals that are already universal that apply.

First is edge cases. If you make something like an array start acting like a function, you are creating an edge case where the same thing acts differently depending on context. That context is complexity and a dependency you have to remember. This increases the mental load you need to get something correct.

Second is dependencies. Instead of two separate things you now have two things that can't work right because they depend on each other. This increases complexity and mental load while decreasing modularity.

Third is that execution is always more complicated than data. Now instead of something simple like data (which is simple because it is static and self evident) you have it mixed with something complicated that can't be observed unless it runs and all of the states at each line or fragment are observed. Execution is largely a black box, data is clear. Mixing them makes the data opaque again.

Post reply on HN