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

91–100 of 145 posts

Re: Are arrays functions?

#91

Post by jwarden »

tombert wrote: post #5

I remember I got a little confused when I was first learning TLA+, because what you normally call "functions" are "operators" [1], and what you'd normally call "maps" or "lists" are called "functions". 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".…

One case where a function is often not substitutable for an array is equality testing. In a language where any two arrays with the same elements in the same order are equal ([1,2] == [1,2]), the same cannot always be true of two equivalent functions. That is because extensionally equality is undecidable for arbitrary functions.

Arrays and functions may be mathematically equivalent but on a programming language level they are practically different.

Re: Are arrays functions?

#92

Post by BlackFly »

Arrays are syntactic sugar over something that resembles a function, sure.

Real signature of an array implementation would be something like V: [0, N] -> T, but that implies you need to statically prove that each index i for V[i] is less than N. So your code would be littered with such guards for dynamic indexing. Also, N itself will be dynamic, so you need some (at least limited) dependent typing on top of this.

So you don't want these things in your language so you just accept the domain as some integer type, so now you don't really have V: ℕ -> T, since for i > N there is no value. You could choose V: ℕ -> Maybe and have even cases where i is provably less than N to be littered with guards, so this cure is worse than the disease. Same if you choose V: ℕ -> Result. So instead you panic or throw, now you have an effect which isn't really modeled well as a function (until we start calling the code after it a continuation and modify the signature, and...).

So it looks like a function if you squint or are overly formal with guards or effects, but the arrays of most languages aren't that.

> for one of the best ways to improve a language is to make it smaller.

I think this isn't one of those cases.

Re: Are arrays functions?

#93

Post by KK7NIL »

Dylan16807 wrote: post #65
KK7NIL wrote: post #26

Earlier quoted context omitted.

Both arrays and (pure) functions are just mappings of inputs to outputs, this is why memoization is possible without any loss of functionality. Whether storing (arrays) or computing (functions) is faster is a quirk of your hardware and use case.

Memoization is a different way around though. You're turning part of a function into an array and a traditional function is still in charge. It doesn't depend on arrays being functions. I would also reject the idea that "Arrays are Functions" is equivalent to "Functions are Arrays". They're both true in a sense, but they're not the same statement.

We're talking past each other because we're using different definitions.

If you actually read the article you'll see that the type of arrays and functions they're talking about are not necessarily the types you'll find in your typical programming language (with some exceptions, as others noted) but more in the area of pure math.

The insights one can gain from this pure math definition are still very much useful for real world programming tough (e.g. memoization), you just have to be careful about the slightly different definitions/implementations.

Re: Are arrays functions?

#94

Post by psychoslave »

geocar wrote: post #81
psychoslave wrote: post #75

>Futhark supports a fairly conventional Python-like notation for array slices, namely a[i:j]. This does not have such a simple correspondence with function application syntax. I don't get it. How is that not trivial with something like array·slice(from: initial, to: juncture) Which is not much different from a·/(i,j) when one want to play the monograph game instead. It can be further reduced to a/(i,j) taking from gr…

The "monograph game" as you put it, is not for mere funsies: We say x+y instead of plus(x,y) because the former is obviously better.

Anything can be credited better for some metric and evaluation scale, and what is obvious to one can be surprising to someone else.

x+y is several step away from plus(x,y), one possible path to render this would be:

  x+y
  x + y
  + x y
  + x , y
  + ( x , y )
  + ( x , y )
  +(x,y)
  plus(x,y)
And there are plenty of other options. For example considering method call noted through middot notation:

  x·+(y)
  x·plus(y)
  x·plus y
  augend·plus(addend)
  augend·plus addend
And of course the tersest would be to allow user to define which operation is done on letter agglutination, so `xy` can be x×y or x+y depending on context. The closest things I aware being used in an actual programming language is terms like `2x` in Julia interpreted as "two times x". But I don’t think it allows to configure the tacit operation through agglutination, while it’s allowing to switch first index to be 0 or 1 which is really in the same spirit of configurability over convention.

Re: Are arrays functions?

#95

Post by geocar »

volemo wrote: post #86
geocar wrote: post #81

Earlier quoted context omitted.

The "monograph game" as you put it, is not for mere funsies: We say x+y instead of plus(x,y) because the former is obviously better.

I say (+ x y). :P

I was distracted by this too; I programmed largely in CL and emacs from 1999-2014.

I highly recommend reading: https://dl.acm.org/doi/10.1145/358896.358899

One thing that helped me tremendously with k (and then APL) was when I noticed the morphism xfyf[x;y](f x y).

This wasn't a new idea; it's right there in:

https://web.archive.org/web/20060211020233/http://community....

starting almost the first page (section 1.2). I simply had not considered the fullness of this because a lot of lispers prefer S-expressions to M-expressions (i.e. that there's more study of it), largely (I conjecture) because S-expressions preserve the morphism between code and data better, and that turns out to be really useful as well.

But the APL community has explored other morphisms beyond this one, and Whitney's projections and views solve a tremendous amount of the problems that macros solve, so I promise I'm not bothered having macros slightly more awkward to write. I write less macros because they're just less useful when you have a better language.

Re: Are arrays functions?

#96

Post by bux93 »

nimih wrote: post #47
tombert wrote: post #5

I remember I got a little confused when I was first learning TLA+, because what you normally call "functions" are "operators" [1], and what you'd normally call "maps" or "lists" are called "functions". 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".…

I remember having a similar sort of realization early in my career when trying to implement some horribly convoluted business logic in SQL (I no longer remember the actual details of what I was trying to do, just the epiphany which resulted; I think it had something to do with proration of insurance premiums and commissions): I realized that if I simply pre-computed the value of the function in question and shoved it…

BTW this is extremely common in life insurance systems, where premiums (provisions, surrender values, etc.) depend on formulas applied to mortality tables; these data themselves are simply tables for people from 0 to 100 years of age, so many formulas end up with only 100 possible outputs and are precomputed. (or 200 for combined probabilities, or gender-specific ones)

Re: Are arrays functions?

#97

Post by zozbot234 »

BlackFly wrote: post #92

Arrays are syntactic sugar over something that resembles a function, sure. Real signature of an array implementation would be something like V: [0, N] -> T, but that implies you need to statically prove that each index i for V[i] is less than N. So your code would be littered with such guards for dynamic indexing. Also, N itself will be dynamic, so you need some (at least limited) dependent typing on top of this. So…

> but that implies you need to statically prove that each index i for V[i] is less than N. So your code would be littered with such guards for dynamic indexing.

You just need a subrange type for i. Even PASCAL had those. And if you have full dependent types you can statically prove that your array accesses are sound without required bounds checking. (You can of course use optional bounds checking as one of many methods of proof.)

Re: Are arrays functions?

#98

Post by brabel »

tombert wrote: post #73
VorpalWay wrote: post #68

Earlier quoted context omitted.

> 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…

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.

Doing maths is extremely fast. You need a lot of maths to get to the same amount of time as a single memory access that is not cached in L1 or L2.

Re: Are arrays functions?

#99

Post by brabel »

lioeters wrote: post #85
sethev wrote: post #28

In Clojure, vectors literally are functions. You can supply a vector (~= array) or map any place that a single parameter function is expected. So for example: (map v [4 5 7]) Would return you a list of the items at index 4, 5, and 7 in the vector v.

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.

Re: Are arrays functions?

#100

Post by themafia »

riazrizvi wrote: post #61

No, not in a programming language sense, because arrays are a notation for address offsetting, whereas functions change the execution context of the machine, which is critical to processing performance (think Horner's method). Not even in a functional sense because, even though functions are input-output maps we define, the inputs are dimensionally rich, it's nowhere close to equivalent to jerry rig a contiguous inpu…

It reminds me of a saying I heard from an Italian:

"...and if my Grandmother had wheels she would have been a bike."

Post reply on HN