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". With pure functions, you could in "theoretical-land", replace any "function" with an array, where the "argument" is replaced with an index.
And it makes sense to me now; TLA+ functions can be defined like maps or lists, but they can also be defined in terms of operations to create the values in the function. For example, you could define the first N factorials like
Fact == <<1, 2, 6, 24, 120>>
or like this:
Fact[n \in Nat] ==
IF n = 0 THEN 1
ELSE n * Fact[n - 1]
in both cases, if you wanted to get the factorial of 5, you'd call Fact[5], and that's on purpose because ultimately from TLA+'s perspective they are equivalent.
[1] At least sort of; they superficially look like functions but they're closer to hygienic macros.
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 into a table (requiring "only" a couple million rows or so), then I could use a join in place of function application, and be done with it. An obvious idea in retrospect, but the sudden dredging of the set-theoretic formulation of functions--that they are simply collections of tuples--from deep within my memory was certainly startling at the time.
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)
I've seen this as a "solution" to implementing a function for fibbonacci numbers. The array of all of the fibbonacci numbers that can fit into a 32-bit integer is not particularly large, so sticking it into a static local variable is easy to do.
> 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 functions can take arbitrarily long. Array access either succeeds or fails quickly.
> 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 the rest of the code base about cache usage).
Of course this depends heavily of how expensive the function is, but it is worth having in mind that memory is not necessarily quicker than computing again. If you need to go to main memory, you have something on the order of a hundred ns that you could be recomputing the value in instead. Which at 2 GHz would translate to 200 clock cycles. What that means in terms of number of instructions depends on the instruction and number of execution units you can saturated in the CPU, if the CPU can predict and prefetch memory, branch prediction, etc. But RAM is really slow. Even with cache you are talking single digit ns to tens of ns (depending on if it is L1, L2 or L3).
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.
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.
I don’t understand this argument. Just because functional extensionality is undecidable for arbitrary functions doesn’t mean that it is undecidable for every class of functions.
In the specific situation, let’s say that by an array we mean a finite, ordered list whose entries are indexed by the numbers 0, 1, …, n - 1 for some natural number n. Let’s also say that two arrays are equal if they have the same length and the same value at each position (in other words, they have “the same elements in the same order”).
If we now want to represent a function f as an array arr such that f(i) = arr[i] for every possible input i of f, then this will only be possible for some very specific functions: those whose domain are the set {0, 1, …, n - 1} for some natural number n. But for any two such functions f, g : {0, 1, …, n - 1} → t, their extensional equality is logically equivalent to the equality of the corresponding arrays: you really can check that f and g are extensionally equal by checking that they are represented by equal arrays.
Very similar, referential transparency is the ability to replace a function call (or expression, generally) with its result (or value). So using an array (or other tabling mechanism) you can take advantage of this to trade off space for time.
Reminds me of many years ago when people were fascinated by the discussion about whether closures are objects or objects are closures. Yes... Yes they are.
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.
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<T> 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<T, IndexOutOfBounds>. 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.
> 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.)
Yes, as I said, you must use bounds checking or dependent types or effects or monad returns.
Arrays are the effect choice in most languages. The signature as a function becomes a gnarly continuation passing if you insist on the equivalence and so most people just tend to think of it imperatively.
Functions are partial in most programming languages, so the fact that arrays are best modelled as partial functions (rather than total functions) isn’t a huge obstacle.
Can you? Yes, and TFA demonstrates this quite clearly.
Should you?
This is where I'd be more careful. Maybe it makes sense to some of the langs in TFA. But it reminds me of [named]tuples in Python, which are iterable, but when used as tuples, in particular, as heterogeneous arrays¹ to support returning multiple values or a quick and dirty product type (/struct), the ability to iterate is just a problem. Doing so is almost always a bug, because iteration through a such tuple is nigh always nonsensical.
So, can an array also be f(index) -> T? Sure. But does that make sense in enough context, or does it promote more bugs and less clear code is what I'd be thinking hard about before I implemented such a thing.
¹sometimes tuples are used as an immutable homogeneous array, and that case is different; iteration is clearly sane, then
Seconded. The call syntax is priveliged, and overloading it to serve as array indexing is a cute demonstration of how arrays approximate piecewise functions, but the same can be said for every data structure in some capacity.
The definition of a function is that for any given input A, I give you an output B. In fact anything that encodes a kind of transformation and yield new information based an input could be seen as a function. From that point of view, array is a function that when "touched", it gives you the information about its items.
In fact, from wikipedia:
```
In mathematics, a tuple is a finite sequence or ordered list of numbers or, more generally, mathematical objects, which are called the elements of the tuple. An n-tuple is a tuple of n elements, where n is a non-negative integer. There is only one 0-tuple, called the empty tuple. A 1-tuple and a 2-tuple are commonly called a singleton and an ordered pair, respectively. The term "infinite tuple" is occasionally used for "infinite sequences".
Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2, 7, 4, 1, 7) denotes a 5-tuple. Other types of brackets are sometimes used, although they may have a different meaning.[a]
An n-tuple can be formally defined as the image of a function that has the set of the n first natural numbers as its domain. Tuples may be also defined from ordered pairs by a recurrence starting from an ordered pair; indeed, an n-tuple can be identified with the ordered pair of its (n − 1) first elements and its nth element
And all three are tuple [input, output] pattern matches, with the special case that in “call/select tuples”, input is always fully defined, with output simply being the consequence of its match.
And with arrays, structures and overloaded functions being unions of tuples to match to. And structure inputs (I.e. fields) being literal inline enumeration values.
And so are generics.
In fact, in functional programming, everything is a pattern match if you consider even enumeration values as a set of comparison functions that return the highly used enumerations true or false, given sibling values.
In Haskell specifically, arrays really do allow for the more general definition. This makes the library documentation[1] quite a bit more intimidating to newcomers (speaking from personal experience), but saves you the boilerplate and hassle of figuring out the mapping yourself if you're indexing your array by some weird nonsense like `[(False, 'a', 5000, 0)..(True, 'z', 9001, 4)] :: (Bool, Char, Integer, Int8)`.
That is typical in most languages, but Haskell's Data.Array is actually parametric over both the index type and the element type, with the index type required to provide a mapping to contiguous integers. This makes it similar to eg. a hashmap which is parametric over both key and element types, with the key type required to provide hashing.
No, the best thing you can do for simplicity is to not conflate concepts. The perpetual idea of mixing data and execution is a misguided search for a silver bullet and it never makes things better in the long term.
This is cleverness over craftsmanship. Keeping data and execution as separate as possible is what leads to simplicity and modularity.
The exception is data structures which need the data and the functions that deal with it to expose that data conveniently to be closely tied to each other.
Everything else is an unnecessary dependency that obscures what is actually happening and makes two things that could be separated depend on each other.
> 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 as possible is what leads to simplicity and modularity.
No, this is research and experimentation. Why are you so negative about someone’s thoughtful blog post about the implications of formal type theory?
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 ponder because this doesn't contradict or even confront what I'm saying.
No, this is research and experimentation.
It might be personal research, but people have been programming for decades and this stuff has been tried over and over. There is a constant cycle where someone thinks of mixing and conflating concepts together, eventually gets burned by it and goes back to something simple and straightforward. What are you saying 'no' to here? You didn't address what I said.
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.
> 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?
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.
It is clear now that you don't understand the claim. It sounds like like you're conflating pure and impure functions. It's obvious from context (did you even read the blog post?) that the title of the blog post is referring to pure functions.
You obviously can't treat an impure function as an array and no one would ever claim that. The blog itself isn't claiming that either given that the author is commenting on a nugget from Haskell documentation, and the author is explaining design choices in his own pure functional language.
Your three points only make sense if you're definition of "function" allows side effects. If we're talking about pure functions, then due to referential transparency, arrays are in fact equivalent to functions from contiguous subsets of the integers to another type, as the Haskell documentation indicates.
It sounds like like you're conflating pure and impure functions.
No I'm not, this applies to both in different ways.
If we're talking about pure functions, then due to referential transparency, arrays are in fact equivalent to functions
Never ever. You're talking about a function that generates data from an index, which is trivial to make. Just because it is possible to disguise it as an array in haskell, C++ or anything else doesn't mean it is a good idea. An array will have vastly different properties fundamentally and can be examined at any time because the data already exists.
Confusing the two is again conflating two things for no reason. Making a function that takes an index and returns something is a trivial interface, there is no value in trying to mix up the two.
Evidence of this can be found in the fact that you haven't tried to explain why this is a good idea, only that it works under haskell's semantics. Being clever with semantics is always possible, that doesn't mean conflating two things and hiding how things actually work is a good idea.
Notice that I never once in this discussion claimed that it was a "good idea". This is about research and experimentation. The blog post has the title because of the Haskell documentation. Also, claiming that the lack of an argument is evidence to the contrary is argument from silence, a logical fallacy.
The good idea surrounding this isn't about treating functions as data, but maintaining the purity of the type system allowing the implications of the type system to run their course. You seem to be a very pragmatic programmer and so the way Haskell builds up its own universe in terms of its own type system and Hask (the pseudo-category of Haskell objects) probably seems pointless to you. I can't say for certain, though.
I completely reject most of your claims because they appear to be incoherent within the framework of type theory and functional programming. It looks like you're using reasoning that applies only to procedural programming to attempt to prove why an idea in functional programming is bad.
Haskell is 36 years old. It isn't research and experimentation any more, it is ideas that everyone with experience has had a look at. Some people might be learning haskell for the first time, but that doesn't mean it's still research, that all happened decades ago.
The good idea surrounding this isn't about treating functions as data, but maintaining the purity of the type system allowing the implications of the type system to run their course.
And what are the benefits here? How do they help the things I talked about? How do they avoid the pitfalls?
Also, claiming that the lack of an argument is evidence to the contrary is argument from silence, a logical fallacy.
Not really, because if you could contradict what I've said you would have.
within the framework of type theory and functional programming.
People can gather in a room and tell each other how great they are and how they have all the answers, but in 36 years there is a single email filtering program that was made with haskell.
you're using reasoning that applies only to procedural programming to attempt to prove why an idea in functional programming is bad.
I explained why this is a bad idea from fundamental and universally agreed upon ideas about the best ways to write software.
Functional programing languages had lots of ideas and features that turned out to work well. That doesn't mean that conflating two completely separate concepts is a good idea, no matter what 'type theory' someone comes up with to support it.
Saying something is good because haskell says it is good is circular religious thinking. These two things aren't the same, they are literally two different things and trying to unify them doesn't make life easier for anyone. It's just programming cleverness, like the 'goes to operator --> '
When it says "arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers", is it saying that this:
const list = ['a', 'b', 'c']
is syntactic sugar for expressing something like this:
function list(index) {
switch (index) {
case 0: return 'a'
case 1: return 'b'
case 2: return 'c'
}
}
No. Quick version: They have the same type. Both take an integer and return a string, so their type would be Integer -> String in your example.
They are computationally equivalent in the sense that they produce the same result given the same input, but they do not perform the exact same computation under the hood (the array is not syntactic sugar for the function).
For the distinction there, consider the two conventional forms of Fibonacci. Naive recursive (computationally expensive) and linear (computationally cheap). They perform the same computation (given sufficient memory and time), but they do not perform it in the same way. The array doesn't "desugar" into the function you wrote, but they are equivalent in that (setting aside call syntax versus indexing syntax) you could substitute the array for the function, and vice versa, and get the same result in the end.
Functions are first class objects. Funsors generalize the tensor interface to also cover arbitrary functions of multiple variables ("dims"), where variables may be integers, real numbers or themselves tensors. Function evaluation / substitution is the basic operation, generalizing tensor indexing. This allows probability distributions to be first-class Funsors and make use of existing tensor machinery, for example we can generalize tensor contraction to computing analytic integrals in conjugate probabilistic models.
I think a more interesting extension would be to see objects as functions. An object maps a set of keys to values. In most languages those keys must be strings. But I don't see why they couldn't be anything. For instance a key could be a function, and to access the value of such a key you would need to pass in exactly that function like this:
let v = myObject [ myFunk ];
Like with arrays-as-functions, the domain of the object-as-function would be its existing keys. Or we could say the domain is any possible value, with the assumption that value of keys which are not stored in the object is always null.
Whether new keys could be added at runtime or not is a sepearate question.
It should be easy to extend the syntax so that
myObject (anything) === myObject [anything]
whether myObject is an object, or a 'function' defined with traditional syntax.
Yes, we can look at an object as a function that accepts a key and returns a value (or null). Depends on language, it's called a set, map, or associative list.
type AnObject = {
[key: any]: any
}
type FunkyObject = (key: any) => Maybe<any>
Then we can see arrays as a limited type of object/function that only accepts a number (index) as key.
type FunkyList = (index: number) => Maybe<any>
We can even consider any variable as a function whose key is the name.
type FunkyVariable = (name: string) => Maybe<any>
And any operation as a function whose key is the operator, with arguments, and the return value is the result.
type FunkyOperator = (name: string, ...values: any) => any
FunkyOperator('+', 1, 2) // => 3
Even an `if` statement can be a function, as long as the values are functions that return values instead of the values themselves, to allow for "short-circuiting" (latter values are unevaluated if an earlier value is true).
So we approach some kind of functional language land where all data structures are modeled using functions.
Yes, and as you point out even conditional statements.
In Smalltalk constructs like
b ifTrue: [ ... ]
mean that the boolean value 'b' has its method (-function) ifTrue: called with the argument [...] which is a "closure" meaning it is a free-standing function (as opposed to bound functions which are the methods).
There are similarly library methods in class Boolean for whileTrue: etc. Functions all the way.
What would be the point of implementing conditional statements as methods/functions? It makes it posssible to extend the set of conditional statements to for instance 3-valued logic by adding a method #ifTrue:ifFalse:ifUnknown: . And of course it makes the syntax of the language very simple.
Right.. So not only all data structures and operators, but all kinds of control flow can be described as functions. What an interesting way to look at programs, I'll study more in this direction.
I wonder how languages support this question of "unevaluated arguments", like in the `if` conditional function. I guess in Lisp(s) they're simply quoted expressions, and in the above Smalltalk example, it sounds like the syntax [...] calls a function with lazily evaluated arguments.
I think that's right. The "closure" is a function, it is not called until method #ifTrue: of the boolean value in question gets it as argument. But it is not just "a function", it is a "closure" meaning it carries with it values from its outer scope that were there at the time the #ifTrue: -method was called, which includes arguments to the outer method being called.
Forgetting Haskell, technically speaking, everything could be expressed as a function. I thought about writing a type of shell script that reflected everything as a function to clean up the likes of bash.
Take the command `ls` for example, it could be expressed as either:
The analog of a dot product of vectors is an integral over the product of functions.
The matrix multiplication of vectors - or a row and a column vector - which is then just taking the dot product is called an inner product. So for functions the inner product is an integral over where the functions are defined -
< f, g> = \int f(x) g(x) dx
Likewise you can multiply functions by a "kernel" which is a bit like multiplying a vector by a matrix
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 input space for that purpose.
No, not when you're designing processes based on a Von Neumann (sequential RAM) architecture. This is the characteristic feature of what the 'array tool' represents.
That depends on the language. I have used (and implemented) languages where arrays are modeled as a function from an index space to some expression. During compilation, this is used to drive various optimisations. For those arrays that need a run-time representation, they may be stored in the classic way (a dense region of memory accessed with offsets computed from indexes), but also in more complicated ways, such as some kind of tree structure. These are still, semantically, arrays at the language level.
For the downvoters, I think giving examples of what's NOT a function would start an interesting conversation, especially if you don't know how it could possibly be interesting!
For me, a x86 interrupt service routine that services a hardware interrupt[1] doesn't strike me as something I'd consider a function. It shouldn't return a value, and it typically has side effects. So why is it a function?
I mean trivially you could say it's a function from (entire machine state) to (entire machine state), but typically we ignore the trivial solution because it's not interesting.
I think it depends on what you mean by "is a function". You can think of a constant, `x` as `x_: () -> {x}` (i.e. everything can be indirected). It could be argued that this is "philosophically" "useful" since getting (using) the value of `x`, even as an actual constant, requires at the least loading it as an immediate into the ALU (or whatever execution unit).
Even non-functional relations can be turned into functions (domain has to change). Like a circle, which is not a function of the x-axis, can be parameterized by an angle theta (... `0 <= theta < 2pi`)
not a downvoter (actually, an upvoter), so grain of salt, but in my experience people cannot stand this framing. my best guess is that they dislike how impractical it is. obviously it's too abstract to be useful for most practical application. but that doesn't make it any less true.
it's a bit like saying "everything is a process", or "everything is a part of the same singular process that has been playing out since observable history". there's some interesting uses you can get out of that framing, but it's not generally applicable in the way that something like "all programs are unable to tell when a process will halt" is.
but if you really want to harvest the downvotes, I haven't found a better lure than "everything, including the foundations of mathematics, is just a story we are telling each other/ourselves." I know it's true and I still hate it, myself. really feels like it's not true. but, obviously, that's just the english major's version of "everything is a function".
I didn't downvote but I'd be interested to know what the domain is here -- I'm not going to play dumb and be like, 'rocks are not functions', but I'm not sure exactly what class of thing you're asking for examples of.
I think it's just that you can make alternative (to set theory) formalizations of mathematics in terms of functions and in consequence anything that is thinkable of in terms of mathematics (which includes all computation).
If you extend the definition of functions to include state, sure, closures are functions. It would be more correct to call them procedures though, which are a superset of functions and operators with side effects.
> An fexpr is a function.
Try to implement a short circuiting logical `and` operator as a function :-)
This is to say that (length-indexed) "Arrays" are Representable functors[1]. A `Vec n a` is isomorphic to (Fin n -> a), where Fin n = { x :: Nat | x < n }.
instance pi n. Representable (Vec n) where
type Rep (Vec n) = Fin n
index :: Vec n a -> (Fin n -> a)
index = ..
tabulate :: (Fin n -> a) -> Vec n a
tabulate = ..
IIRC, K rationalizes arrays and dictionaries with functions, e.g. you see arr[x;y] and fun[x;y]. Interestingly, this also highlights the connection between currying and projection, i.e. we can project/curry the above like arr[x] and fun[x].
It makes obvious sense to consider an array as a function with the index as its input argument and the element its output, i.e. f(x) = A[x]... but this isn't the first time I've encountered this and I still don't see the practical benefit of considering things from this perspective.
When I'm writing code and need to reach for an array-like data structure, the conceptual correspondence to a function is not even remotely on my radar. I'm considering algorithmic complexity of reads vs writes, managed vs unmanaged collections, allocation, etc.
I guess this is one of those things that's of primary interest to language designers?
If you know that Arrays are Functions or equivalently Functions are Arrays, in some sense, then Memoization is obvious. "Oh, yeah, of course" we should just store the answers not recompute them.
This goes both ways, as modern CPUs get faster at arithmetic and yet storage speed doesn't keep up, sometimes rather than use a pre-computed table and eat precious clock cycles waiting for the memory fetch we should just recompute the answer each time we need it.
I think this is an after-the-fact connection, rather than an intuitive discovery. I wouldn't explain memoization this way. Memoization doesn't need to specifically use an array, and depending on the argument types, indexing into the array could be very unusual.
>Well for example this insight explains Memoization
I don't think it does.
In fact I don't see (edit: the logcial progression from one idea to the other) at all. Memorization is the natural conclusion of the thought process that begins with the disk/CPU trade off and the idea that "some things are expensive to compute but cheap to store", aka caching.
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.
> 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.
I agree completely here. But I think that undermines some of the earlier claims. The math definition only serves as inspiration, we're not using the math definition when we memoize. And the important part you need for that inspiration is a lot narrower than full equivalence.
> And the important part you need for that inspiration is a lot narrower than full equivalence.
The blogpost is discussing exactly what you gain (and lose) when arrays and functions fit this strict definition, allowing a unification of the syntax and possible compiler optimizations.
I think the point they're making is exactly that having only a loose equivalence between arrays and functions might be a programming status quo that could be holding us back from a higher level abstraction.
> I think the point they're making is exactly that having only a loose equivalence between arrays and functions might be a programming status quo that could be holding us back from a higher level abstraction.
Maybe. I'll sit here ready for those insightful uses of stricter connections.
But the memoization example is very loose, and memoization is what I was replying to.
There are some appealing-sounding arguments for designing languages around functions. Having given this a very fair shot with things like Erlang... turns out this optimizes for rare use cases at the expense of common ones. There's no 100% general-purpose language, they all have use cases in mind, and I guess some people are still trying to find a way around that.
Similar conclusion for using a graph DB for something you'd typically do in a relational DB. Just because you can doesn't mean you should.
>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 granted that "/" is given special treatment so it can be employed as part of identifiers.
Or, more elegantly, if you had some sort of infix composition operator (say @, by analogy to matrix multiplication) you would slice an array inline via
sliced_array = array @ lambda x: x - start
I think what this really clarifies is that it's quite important that arrays expose their lengths, which there isn't one clear way to do if arrays and functions are interchanged freely.
The post explains that 'a[i]' can easily enough be written as 'a i'. Your suggestions do not resemble the current function application syntax in the language discussed in the post. The question is not whether a terse slice syntax can exist (clearly it can), but whether a syntactic similarity between indexing and application can also be extended to a syntactic similarity between slicing and application.
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.
> and what is obvious to one can be surprising to someone else.
That is how obvious things work. If you were not surprised that a[i:j] and :[a;i;j] are the same (: a i j) then it is because it was obvious to you, and now that you have had it pointed it out to you, you were able to show all of the different other variants of this thing without even being prompted to, so I think you understand the answer to your question now.
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.
Any expression-value can be a function, if you simply define the meaning of applying the the expression-value to another expression-value to be something compatible with your definition of a function.
In Object Oriented programming, yes, arrays are objects and the functions are a property of another object that can perform instructions on the data of the Array Object.
Similarly in Lisp, (a list-oriented language) both functions and arrays are lists.
This article however is discussing Haskel, a Functional Language, which means they are both functions.
> Similarly in Lisp, (a list-oriented language) both functions and arrays are lists.
In which Lisp? Try this in Common Lisp and it won't work too well:
(let ((array (make-array 20)))
(car array))
What is the car of an array? An array in Lisp (since Lisp 1.5 at least, I haven't read earlier documentation) is an array, and not a list. It does not behave as a list in that you cannot construct it with cons, and you cannot deconstruct it with car or cdr.
To quote John McCarthy
"Since data are list structures and programs are list structures, we can manipulate programs just like data."
Yes, I know most people consider it to be a functional language, and some variants like 'common lisp' make that more explicit, but the original concept was markedly different.
Yeah I guess a c++ programmer might say `std::array::operator[]` is a function (or method, whatever), just like `std::array::size` is. And that identifying the array with just one of those functions (or even the collection of all methods offered) is to miss the point -- not just contiguous indices, but contiguous storage. A red-black tree with added constraints is not an array.
TFA does allude to this. An "array indexing function" that just met the API could be implemented as an if-else chain, and would not be satisfactory.
Depending on how you look at things, functions can also be mutated at run-time. Most impure languages allow you to define a function that has some internal state and changes it whenever it is applied. In C you would use 'static' variables, but languages with closures allow for a more robust approach. Scheme textbooks are full of examples that use this trick to define counters or other objects via closures. You can well argue that these functions do not "mutate", they merely access some data that is mutated, but there is no observable difference from the perspective of the caller.
Functions are rarely used this way, it’s bad practice. Typically when this is done the mutating state is scoped in an object and the function is not called a “function” it’s called a method.
> Arrays are functions whose domains are isomorphic to contiguous subsets of the integers
Yes. And a sandwich is "a stack-based heterogeneous data structure with edible semantics." This is not insight. It is taxonomy cosplay.
Look, arrays and functions share some mathematical structure! - Irrelevant. We do not unify them because representation matters.
When a language makes arrays "feel like functions," what it usually means is: "You no longer know when something is cheap." That is not abstraction. That is obscurity.
Industry programmers do not struggle because arrays lack ontological clarity. They struggle because memory hierarchies exist, cache lines exist, branch predictors exist, GPUs exist, deadlines exist.
> the correspondence between arrays and functions [...] is alluring, for one of the best ways to improve a language is to make it smaller
No. The best way to improve a language is to make it faster, simpler to reason about, and less painful to debug.
> I imagine a language that allows shared abstractions that work for both arrays and appropriate functions
What if we invented increasingly abstract our own words so we don’t have to say ‘for loop’, map, SIMD, kernels?
Making arrays pretend to be functions achieves exactly none of those things. It achieves conference papers that end with “future work”.
Why is this academic slop keep happening ? - Professors are rewarded for novel perspectives, not usable ones.
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, targeting GPUs, and explicitly described as “not intended to replace existing general-purpose languages” (quote from the language’s home page.) As such, it has requirements and constraints that most languages don’t have. Looking at its design through a general-purpose languages lens doesn’t necessarily make sense.
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.
> very few languages aside from C++ have good CUDA support
CUDA happens to be (loosely) source-compatible with C++, but I'm not sure that's the same as saying C++ has good CUDA support. The majority of C++ code does not compile to CUDA (although the inverse is often true).
> C++ certainly doesn't achieve that by having its arrays be equivalent to functions "in practice" or in any other sense
The syntax may not be unified, but what else do you think iterators are for? They are an abstraction to let us ignore pesky details like the underlying storage of arrays, and instead treat them like any other generator function. This is perhaps more evident in a language like Python where generators and iterators are entirely interchangeable.
> 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
These are specific oddities of Furthark - we have languages (i.e. C/C++) where the size of an array is not knowable, and we have languages where the range of inputs to a function are knowable (at least for numeric inputs, i.e. Ada)
> 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
Again, this is a case of Furthark's own design decisions restricting it. This is only a problem because their arrays are carrying around runtime size information - if they didn't have that, one wouldn't be able to usefully return them from branches anyway. Alternately, there are plenty of ML-family languages where you can return a function from a branch.
No - An array is a data structure that stores pre-calculated values in memory, whereas a function is executable logic that computes a result only when it is called.
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 and are something else.
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.
> Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers.
> I found this to be a hilariously obtuse and unnecessarily formalist description of a common data structure.
Well it is haskell. Try to understand what a monad is. Haskell loves complexity. That also taps right into the documentation.
> I look at this description and think that it is actually a wonderful definition of the essence of arrays!
I much prefer simplicity. Including in documentation.
I do not think that description is useful.
To me, Arrays are about storing data. But functions can also do that, so I also would not say the description is completely incorrect either.
> who can say that it is not actually a far better piece of documentation than some more prosaic description might have been?
I can say that. The documentation does not seem to be good, in my opinion. Once you reach this conclusion, it is easy to say too. But this is speculative because ... what is a "more prosaic description"? There can be many ways to make a worse documentation too. But, also, better documentation.
> To a language designer, the correspondence between arrays and functions (for it does exist, independent of whether you think it is a useful way to document them) is alluring, for one of the best ways to improve a language is to make it smaller.
I agree that there is a correspondence. I disagree that Haskell's documentation is good here.
> currying/uncurrying is equivalent to unflattening/flattening an array
So, there are some similarities between arrays and functions. I do not think this means that both are equivalent to one another.
> would like to see what it would be like for a language to fully exploit the array-function correspondence.
Does Haskell succeed in explaining what a Monad is? If not, then it failed there. What if it also fails in other areas with regards to documentation?
I think you need to compare Haskell to other languages, C or Python. I don't know if C does a better job with regards to its documentation; or C++. But I think Python does a better job than the other languages. So that is a comparison that should work.
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". With pure functions, you could in "theoretical-land", replace any "function" with an array, where the "argument" is replaced with an index.
And it makes sense to me now; TLA+ functions can be defined like maps or lists, but they can also be defined in terms of operations to create the values in the function. For example, you could define the first N factorials like
or like this: in both cases, if you wanted to get the factorial of 5, you'd call Fact[5], and that's on purpose because ultimately from TLA+'s perspective they are equivalent.[1] At least sort of; they superficially look like functions but they're closer to hygienic macros.
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 into a table (requiring "only" a couple million rows or so), then I could use a join in place of function application, and be done with it. An obvious idea in retrospect, but the sudden dredging of the set-theoretic formulation of functions--that they are simply collections of tuples--from deep within my memory was certainly startling at the time.
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)
I've seen this as a "solution" to implementing a function for fibbonacci numbers. The array of all of the fibbonacci numbers that can fit into a 32-bit integer is not particularly large, so sticking it into a static local variable is easy to do.
> 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 functions can take arbitrarily long. Array access either succeeds or fails quickly.
> 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 the rest of the code base about cache usage).
Of course this depends heavily of how expensive the function is, but it is worth having in mind that memory is not necessarily quicker than computing again. If you need to go to main memory, you have something on the order of a hundred ns that you could be recomputing the value in instead. Which at 2 GHz would translate to 200 clock cycles. What that means in terms of number of instructions depends on the instruction and number of execution units you can saturated in the CPU, if the CPU can predict and prefetch memory, branch prediction, etc. But RAM is really slow. Even with cache you are talking single digit ns to tens of ns (depending on if it is L1, L2 or L3).
> 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.
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.
The N64 was just really weirdly designed: they went with an overpowered CPU for bragging rights, and bet on the wrong RAM horse, Rambus.
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.
And you need to burn even more cycles before you’ve amortized the cost of using a cache line that could have benefitted some other work.
I used to develop for the N64 and I can confirm that it is true. It is crazy how much faster the CPU is compared with not-in-cache RAM access.
Optimizing for RAM access instead of CPU instruction speed can make your code magnitudes faster.
It's a classic space / time trade-off. The special relativity of programming, if you like.
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.
I don’t understand this argument. Just because functional extensionality is undecidable for arbitrary functions doesn’t mean that it is undecidable for every class of functions.
In the specific situation, let’s say that by an array we mean a finite, ordered list whose entries are indexed by the numbers 0, 1, …, n - 1 for some natural number n. Let’s also say that two arrays are equal if they have the same length and the same value at each position (in other words, they have “the same elements in the same order”).
If we now want to represent a function f as an array arr such that f(i) = arr[i] for every possible input i of f, then this will only be possible for some very specific functions: those whose domain are the set {0, 1, …, n - 1} for some natural number n. But for any two such functions f, g : {0, 1, …, n - 1} → t, their extensional equality is logically equivalent to the equality of the corresponding arrays: you really can check that f and g are extensionally equal by checking that they are represented by equal arrays.
Arrays/maps/lists are extensionally defined functions, where as functions/TLA+ operations are intensionally defined functions
Is this what the fp community calls referential transparency?
Very similar, referential transparency is the ability to replace a function call (or expression, generally) with its result (or value). So using an array (or other tabling mechanism) you can take advantage of this to trade off space for time.
Reminds me of many years ago when people were fascinated by the discussion about whether closures are objects or objects are closures. Yes... Yes they are.
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:
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.
> 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.
is pure lambda calculus something i can install and use to host a web server?
No reason why not, in principle. Using Church-encoded numerals and so on might be a little inefficient. Probably not as bad as Python though.
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<T> 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<T, IndexOutOfBounds>. 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.
> 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.)
Yes, as I said, you must use bounds checking or dependent types or effects or monad returns.
Arrays are the effect choice in most languages. The signature as a function becomes a gnarly continuation passing if you insist on the equivalence and so most people just tend to think of it imperatively.
Functions are partial in most programming languages, so the fact that arrays are best modelled as partial functions (rather than total functions) isn’t a huge obstacle.
Yeah, in languages with effects (exceptions/panics). That is a bit more than a partial function though.
Can you? Yes, and TFA demonstrates this quite clearly.
Should you?
This is where I'd be more careful. Maybe it makes sense to some of the langs in TFA. But it reminds me of [named]tuples in Python, which are iterable, but when used as tuples, in particular, as heterogeneous arrays¹ to support returning multiple values or a quick and dirty product type (/struct), the ability to iterate is just a problem. Doing so is almost always a bug, because iteration through a such tuple is nigh always nonsensical.
So, can an array also be f(index) -> T? Sure. But does that make sense in enough context, or does it promote more bugs and less clear code is what I'd be thinking hard about before I implemented such a thing.
¹sometimes tuples are used as an immutable homogeneous array, and that case is different; iteration is clearly sane, then
Seconded. The call syntax is priveliged, and overloading it to serve as array indexing is a cute demonstration of how arrays approximate piecewise functions, but the same can be said for every data structure in some capacity.
The definition of a function is that for any given input A, I give you an output B. In fact anything that encodes a kind of transformation and yield new information based an input could be seen as a function. From that point of view, array is a function that when "touched", it gives you the information about its items.
In fact, from wikipedia:
```
In mathematics, a tuple is a finite sequence or ordered list of numbers or, more generally, mathematical objects, which are called the elements of the tuple. An n-tuple is a tuple of n elements, where n is a non-negative integer. There is only one 0-tuple, called the empty tuple. A 1-tuple and a 2-tuple are commonly called a singleton and an ordered pair, respectively. The term "infinite tuple" is occasionally used for "infinite sequences".
Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2, 7, 4, 1, 7) denotes a 5-tuple. Other types of brackets are sometimes used, although they may have a different meaning.[a]
An n-tuple can be formally defined as the image of a function that has the set of the n first natural numbers as its domain. Tuples may be also defined from ordered pairs by a recurrence starting from an ordered pair; indeed, an n-tuple can be identified with the ordered pair of its (n − 1) first elements and its nth element
```
(https://en.wikipedia.org/wiki/Tuple)
From a data structure standpoint, a tuple can be seen as an array of fixed arity/size, then if an array is not a function, so shouldn't a tuple too.
Arrays and structures are functions.
And all three are tuple [input, output] pattern matches, with the special case that in “call/select tuples”, input is always fully defined, with output simply being the consequence of its match.
And with arrays, structures and overloaded functions being unions of tuples to match to. And structure inputs (I.e. fields) being literal inline enumeration values.
And so are generics.
In fact, in functional programming, everything is a pattern match if you consider even enumeration values as a set of comparison functions that return the highly used enumerations true or false, given sibling values.
What about replacing
> Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers.
with
> Haskell provides indexable arrays, which are functions on the domain [0, ..., k-1]?
Or is the domain actually anything "isomorphic to contiguous subsets of the integers"?
In Haskell specifically, arrays really do allow for the more general definition. This makes the library documentation[1] quite a bit more intimidating to newcomers (speaking from personal experience), but saves you the boilerplate and hassle of figuring out the mapping yourself if you're indexing your array by some weird nonsense like `[(False, 'a', 5000, 0)..(True, 'z', 9001, 4)] :: (Bool, Char, Integer, Int8)`.
[1] https://hackage.haskell.org/package/array-0.5.8.0/docs/Data-...
That is typical in most languages, but Haskell's Data.Array is actually parametric over both the index type and the element type, with the index type required to provide a mapping to contiguous integers. This makes it similar to eg. a hashmap which is parametric over both key and element types, with the key type required to provide hashing.
No, the best thing you can do for simplicity is to not conflate concepts. The perpetual idea of mixing data and execution is a misguided search for a silver bullet and it never makes things better in the long term.
This is cleverness over craftsmanship. Keeping data and execution as separate as possible is what leads to simplicity and modularity.
The exception is data structures which need the data and the functions that deal with it to expose that data conveniently to be closely tied to each other.
Everything else is an unnecessary dependency that obscures what is actually happening and makes two things that could be separated depend on each other.
> 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 as possible is what leads to simplicity and modularity.
No, this is research and experimentation. Why are you so negative about someone’s thoughtful blog post about the implications of formal type theory?
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 ponder because this doesn't contradict or even confront what I'm saying.
No, this is research and experimentation.
It might be personal research, but people have been programming for decades and this stuff has been tried over and over. There is a constant cycle where someone thinks of mixing and conflating concepts together, eventually gets burned by it and goes back to something simple and straightforward. What are you saying 'no' to here? You didn't address what I said.
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.
> 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?
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.
It is clear now that you don't understand the claim. It sounds like like you're conflating pure and impure functions. It's obvious from context (did you even read the blog post?) that the title of the blog post is referring to pure functions.
You obviously can't treat an impure function as an array and no one would ever claim that. The blog itself isn't claiming that either given that the author is commenting on a nugget from Haskell documentation, and the author is explaining design choices in his own pure functional language.
Your three points only make sense if you're definition of "function" allows side effects. If we're talking about pure functions, then due to referential transparency, arrays are in fact equivalent to functions from contiguous subsets of the integers to another type, as the Haskell documentation indicates.
It sounds like like you're conflating pure and impure functions.
No I'm not, this applies to both in different ways.
If we're talking about pure functions, then due to referential transparency, arrays are in fact equivalent to functions
Never ever. You're talking about a function that generates data from an index, which is trivial to make. Just because it is possible to disguise it as an array in haskell, C++ or anything else doesn't mean it is a good idea. An array will have vastly different properties fundamentally and can be examined at any time because the data already exists.
Confusing the two is again conflating two things for no reason. Making a function that takes an index and returns something is a trivial interface, there is no value in trying to mix up the two.
Evidence of this can be found in the fact that you haven't tried to explain why this is a good idea, only that it works under haskell's semantics. Being clever with semantics is always possible, that doesn't mean conflating two things and hiding how things actually work is a good idea.
Notice that I never once in this discussion claimed that it was a "good idea". This is about research and experimentation. The blog post has the title because of the Haskell documentation. Also, claiming that the lack of an argument is evidence to the contrary is argument from silence, a logical fallacy.
The good idea surrounding this isn't about treating functions as data, but maintaining the purity of the type system allowing the implications of the type system to run their course. You seem to be a very pragmatic programmer and so the way Haskell builds up its own universe in terms of its own type system and Hask (the pseudo-category of Haskell objects) probably seems pointless to you. I can't say for certain, though.
I completely reject most of your claims because they appear to be incoherent within the framework of type theory and functional programming. It looks like you're using reasoning that applies only to procedural programming to attempt to prove why an idea in functional programming is bad.
This is about research and experimentation.
Haskell is 36 years old. It isn't research and experimentation any more, it is ideas that everyone with experience has had a look at. Some people might be learning haskell for the first time, but that doesn't mean it's still research, that all happened decades ago.
The good idea surrounding this isn't about treating functions as data, but maintaining the purity of the type system allowing the implications of the type system to run their course.
And what are the benefits here? How do they help the things I talked about? How do they avoid the pitfalls?
Also, claiming that the lack of an argument is evidence to the contrary is argument from silence, a logical fallacy.
Not really, because if you could contradict what I've said you would have.
within the framework of type theory and functional programming.
People can gather in a room and tell each other how great they are and how they have all the answers, but in 36 years there is a single email filtering program that was made with haskell.
you're using reasoning that applies only to procedural programming to attempt to prove why an idea in functional programming is bad.
I explained why this is a bad idea from fundamental and universally agreed upon ideas about the best ways to write software.
Functional programing languages had lots of ideas and features that turned out to work well. That doesn't mean that conflating two completely separate concepts is a good idea, no matter what 'type theory' someone comes up with to support it.
Saying something is good because haskell says it is good is circular religious thinking. These two things aren't the same, they are literally two different things and trying to unify them doesn't make life easier for anyone. It's just programming cleverness, like the 'goes to operator --> '
When it says "arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers", is it saying that this:
is syntactic sugar for expressing something like this:https://en.wikipedia.org/wiki/Church_encoding
Advanced version (which defines the ADT we use today): https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encodin...
No. Quick version: They have the same type. Both take an integer and return a string, so their type would be Integer -> String in your example.
They are computationally equivalent in the sense that they produce the same result given the same input, but they do not perform the exact same computation under the hood (the array is not syntactic sugar for the function).
For the distinction there, consider the two conventional forms of Fibonacci. Naive recursive (computationally expensive) and linear (computationally cheap). They perform the same computation (given sufficient memory and time), but they do not perform it in the same way. The array doesn't "desugar" into the function you wrote, but they are equivalent in that (setting aside call syntax versus indexing syntax) you could substitute the array for the function, and vice versa, and get the same result in the end.
Yes.
This reminds me of funsors in the Pyro probabilistic programming language. From the design document (https://docs.google.com/document/d/1NVlfQnNQ0Aebg8vfIGcJKsnS...)
More in the paper: https://arxiv.org/abs/1910.10775I think a more interesting extension would be to see objects as functions. An object maps a set of keys to values. In most languages those keys must be strings. But I don't see why they couldn't be anything. For instance a key could be a function, and to access the value of such a key you would need to pass in exactly that function like this:
Like with arrays-as-functions, the domain of the object-as-function would be its existing keys. Or we could say the domain is any possible value, with the assumption that value of keys which are not stored in the object is always null.Whether new keys could be added at runtime or not is a sepearate question.
It should be easy to extend the syntax so that
whether myObject is an object, or a 'function' defined with traditional syntax.Yes, we can look at an object as a function that accepts a key and returns a value (or null). Depends on language, it's called a set, map, or associative list.
Then we can see arrays as a limited type of object/function that only accepts a number (index) as key. We can even consider any variable as a function whose key is the name. And any operation as a function whose key is the operator, with arguments, and the return value is the result. Even an `if` statement can be a function, as long as the values are functions that return values instead of the values themselves, to allow for "short-circuiting" (latter values are unevaluated if an earlier value is true).So we approach some kind of functional language land where all data structures are modeled using functions.
Yes, and as you point out even conditional statements.
In Smalltalk constructs like
mean that the boolean value 'b' has its method (-function) ifTrue: called with the argument [...] which is a "closure" meaning it is a free-standing function (as opposed to bound functions which are the methods).There are similarly library methods in class Boolean for whileTrue: etc. Functions all the way.
What would be the point of implementing conditional statements as methods/functions? It makes it posssible to extend the set of conditional statements to for instance 3-valued logic by adding a method #ifTrue:ifFalse:ifUnknown: . And of course it makes the syntax of the language very simple.
Right.. So not only all data structures and operators, but all kinds of control flow can be described as functions. What an interesting way to look at programs, I'll study more in this direction.
I wonder how languages support this question of "unevaluated arguments", like in the `if` conditional function. I guess in Lisp(s) they're simply quoted expressions, and in the above Smalltalk example, it sounds like the syntax [...] calls a function with lazily evaluated arguments.
I think that's right. The "closure" is a function, it is not called until method #ifTrue: of the boolean value in question gets it as argument. But it is not just "a function", it is a "closure" meaning it carries with it values from its outer scope that were there at the time the #ifTrue: -method was called, which includes arguments to the outer method being called.
Forgetting Haskell, technically speaking, everything could be expressed as a function. I thought about writing a type of shell script that reflected everything as a function to clean up the likes of bash.
Take the command `ls` for example, it could be expressed as either:
For pipes, they could be expressed as either: I thought about writing this with something like Micropython that could have a very small memory footprint.The analog of a dot product of vectors is an integral over the product of functions.
The matrix multiplication of vectors - or a row and a column vector - which is then just taking the dot product is called an inner product. So for functions the inner product is an integral over where the functions are defined -
< f, g> = \int f(x) g(x) dx
Likewise you can multiply functions by a "kernel" which is a bit like multiplying a vector by a matrix
< A f, g> = \int \int A(x,y) f(y) g(x) dx dy
The fourier transform is a particular kernel
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 input space for that purpose.
> the inputs are dimensionally rich
Well, that makes arrays a subset of functions. What is still a "yes" to the questions "are arrays functions?"
And yeah, of course the article names Haskell on its second phrase.
> arrays are a notation for address offsetting
That's an implementation detail, though.
No, not when you're designing processes based on a Von Neumann (sequential RAM) architecture. This is the characteristic feature of what the 'array tool' represents.
That depends on the language. I have used (and implemented) languages where arrays are modeled as a function from an index space to some expression. During compilation, this is used to drive various optimisations. For those arrays that need a run-time representation, they may be stored in the classic way (a dense region of memory accessed with offsets computed from indexes), but also in more complicated ways, such as some kind of tree structure. These are still, semantically, arrays at the language level.
It reminds me of a saying I heard from an Italian:
"...and if my Grandmother had wheels she would have been a bike."
Everything is a function. Next question?
For the downvoters, I think giving examples of what's NOT a function would start an interesting conversation, especially if you don't know how it could possibly be interesting!
In the mathematical sense, all functions are relations, but not all relations are functions.
What are relations, if not an indicator function of a cartesian product?
For me, a x86 interrupt service routine that services a hardware interrupt[1] doesn't strike me as something I'd consider a function. It shouldn't return a value, and it typically has side effects. So why is it a function?
I mean trivially you could say it's a function from (entire machine state) to (entire machine state), but typically we ignore the trivial solution because it's not interesting.
[1]: https://alex.dzyoba.com/blog/os-interrupts/
I think it depends on what you mean by "is a function". You can think of a constant, `x` as `x_: () -> {x}` (i.e. everything can be indirected). It could be argued that this is "philosophically" "useful" since getting (using) the value of `x`, even as an actual constant, requires at the least loading it as an immediate into the ALU (or whatever execution unit).
Even non-functional relations can be turned into functions (domain has to change). Like a circle, which is not a function of the x-axis, can be parameterized by an angle theta (... `0 <= theta < 2pi`)
I think in this context, it is function as in a lambda in LC.
The answer is pretty much, yes, everything can be a function. e.g. A KV Map can be a function "K -> Maybe V"
P.S. If this style of thinking appeals to you, go read Algebra Driven Design! https://leanpub.com/algebra-driven-design
Take a parabola and rotate it 90 degrees. The forumula for that is not a function of the x axis: it has two values for all but one point on the curve.
It's still a function of many other things: y, t, angle, ...
not a downvoter (actually, an upvoter), so grain of salt, but in my experience people cannot stand this framing. my best guess is that they dislike how impractical it is. obviously it's too abstract to be useful for most practical application. but that doesn't make it any less true.
it's a bit like saying "everything is a process", or "everything is a part of the same singular process that has been playing out since observable history". there's some interesting uses you can get out of that framing, but it's not generally applicable in the way that something like "all programs are unable to tell when a process will halt" is.
but if you really want to harvest the downvotes, I haven't found a better lure than "everything, including the foundations of mathematics, is just a story we are telling each other/ourselves." I know it's true and I still hate it, myself. really feels like it's not true. but, obviously, that's just the english major's version of "everything is a function".
Waiting for the m word.
I didn't downvote but I'd be interested to know what the domain is here -- I'm not going to play dumb and be like, 'rocks are not functions', but I'm not sure exactly what class of thing you're asking for examples of.
I think it's just that you can make alternative (to set theory) formalizations of mathematics in terms of functions and in consequence anything that is thinkable of in terms of mathematics (which includes all computation).
Closures and fexprs
Well a closure is a kind of a record with a function hiding inside it and a record is a function which returns its contents.
An fexpr is a function.
If you extend the definition of functions to include state, sure, closures are functions. It would be more correct to call them procedures though, which are a superset of functions and operators with side effects.
> An fexpr is a function.
Try to implement a short circuiting logical `and` operator as a function :-)
This is to say that (length-indexed) "Arrays" are Representable functors[1]. A `Vec n a` is isomorphic to (Fin n -> a), where Fin n = { x :: Nat | x < n }.
[1] https://hackage-content.haskell.org/package/adjunctions-4.4....From a mathematical point of view, a real vector of length n is a function from Z_n to R.
When I was learning programming, I was surprised that in most programming languages we write f(k), but vec[k].
However, we do have syntax vec.at(k) or vec.get(k) in quite a few languages.
IIRC, K rationalizes arrays and dictionaries with functions, e.g. you see arr[x;y] and fun[x;y]. Interestingly, this also highlights the connection between currying and projection, i.e. we can project/curry the above like arr[x] and fun[x].
It makes obvious sense to consider an array as a function with the index as its input argument and the element its output, i.e. f(x) = A[x]... but this isn't the first time I've encountered this and I still don't see the practical benefit of considering things from this perspective.
When I'm writing code and need to reach for an array-like data structure, the conceptual correspondence to a function is not even remotely on my radar. I'm considering algorithmic complexity of reads vs writes, managed vs unmanaged collections, allocation, etc.
I guess this is one of those things that's of primary interest to language designers?
Well for example this insight explains Memoization
https://en.wikipedia.org/wiki/Memoization
If you know that Arrays are Functions or equivalently Functions are Arrays, in some sense, then Memoization is obvious. "Oh, yeah, of course" we should just store the answers not recompute them.
This goes both ways, as modern CPUs get faster at arithmetic and yet storage speed doesn't keep up, sometimes rather than use a pre-computed table and eat precious clock cycles waiting for the memory fetch we should just recompute the answer each time we need it.
I think this is an after-the-fact connection, rather than an intuitive discovery. I wouldn't explain memoization this way. Memoization doesn't need to specifically use an array, and depending on the argument types, indexing into the array could be very unusual.
>Well for example this insight explains Memoization
I don't think it does.
In fact I don't see (edit: the logcial progression from one idea to the other) at all. Memorization is the natural conclusion of the thought process that begins with the disk/CPU trade off and the idea that "some things are expensive to compute but cheap to store", aka caching.
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.
> If you actually read the article
Needless.
> 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.
I agree completely here. But I think that undermines some of the earlier claims. The math definition only serves as inspiration, we're not using the math definition when we memoize. And the important part you need for that inspiration is a lot narrower than full equivalence.
> And the important part you need for that inspiration is a lot narrower than full equivalence.
The blogpost is discussing exactly what you gain (and lose) when arrays and functions fit this strict definition, allowing a unification of the syntax and possible compiler optimizations. I think the point they're making is exactly that having only a loose equivalence between arrays and functions might be a programming status quo that could be holding us back from a higher level abstraction.
> I think the point they're making is exactly that having only a loose equivalence between arrays and functions might be a programming status quo that could be holding us back from a higher level abstraction.
Maybe. I'll sit here ready for those insightful uses of stricter connections.
But the memoization example is very loose, and memoization is what I was replying to.
There are some appealing-sounding arguments for designing languages around functions. Having given this a very fair shot with things like Erlang... turns out this optimizes for rare use cases at the expense of common ones. There's no 100% general-purpose language, they all have use cases in mind, and I guess some people are still trying to find a way around that.
Similar conclusion for using a graph DB for something you'd typically do in a relational DB. Just because you can doesn't mean you should.
>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
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 granted that "/" is given special treatment so it can be employed as part of identifiers.Unsupervised, in a language where arrays and functions could be called with the same syntax, one would be tempted to do
Or, more elegantly, if you had some sort of infix composition operator (say @, by analogy to matrix multiplication) you would slice an array inline via I think what this really clarifies is that it's quite important that arrays expose their lengths, which there isn't one clear way to do if arrays and functions are interchanged freely.The post explains that 'a[i]' can easily enough be written as 'a i'. Your suggestions do not resemble the current function application syntax in the language discussed in the post. The question is not whether a terse slice syntax can exist (clearly it can), but whether a syntactic similarity between indexing and application can also be extended to a syntactic similarity between slicing and application.
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:
And there are plenty of other options. For example considering method call noted through middot notation: 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.> and what is obvious to one can be surprising to someone else.
That is how obvious things work. If you were not surprised that a[i:j] and :[a;i;j] are the same (: a i j) then it is because it was obvious to you, and now that you have had it pointed it out to you, you were able to show all of the different other variants of this thing without even being prompted to, so I think you understand the answer to your question now.
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 xfy<=>f[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.
Doesn't lambda calculus show that you can let everything be functions?
You can consider any vector a function, though it's not always helpful to do so
Right, and you can also consider a function to be a vector.
Right, that was how I first encountered that idea; it only just struck me that it works both ways.
Any expression-value can be a function, if you simply define the meaning of applying the the expression-value to another expression-value to be something compatible with your definition of a function.
> Composition is like applying a permutation array to another
Composing injective functions is like applying a permutation array to another.
Arrays are objects (allocated memory and metadata if you will). The function is what takes the array and an int and returns an item.
In Object Oriented programming, yes, arrays are objects and the functions are a property of another object that can perform instructions on the data of the Array Object.
Similarly in Lisp, (a list-oriented language) both functions and arrays are lists.
This article however is discussing Haskel, a Functional Language, which means they are both functions.
> Similarly in Lisp, (a list-oriented language) both functions and arrays are lists.
In which Lisp? Try this in Common Lisp and it won't work too well:
What is the car of an array? An array in Lisp (since Lisp 1.5 at least, I haven't read earlier documentation) is an array, and not a list. It does not behave as a list in that you cannot construct it with cons, and you cannot deconstruct it with car or cdr.To quote John McCarthy "Since data are list structures and programs are list structures, we can manipulate programs just like data."
Yes, I know most people consider it to be a functional language, and some variants like 'common lisp' make that more explicit, but the original concept was markedly different.
Yeah I guess a c++ programmer might say `std::array::operator[]` is a function (or method, whatever), just like `std::array::size` is. And that identifying the array with just one of those functions (or even the collection of all methods offered) is to miss the point -- not just contiguous indices, but contiguous storage. A red-black tree with added constraints is not an array.
TFA does allude to this. An "array indexing function" that just met the API could be implemented as an if-else chain, and would not be satisfactory.
This is actually why Matlab uses the same syntax for function calls as array indexing.
An array is a function that can be mutated at runtime. That’s essentially the main difference.
Depending on how you look at things, functions can also be mutated at run-time. Most impure languages allow you to define a function that has some internal state and changes it whenever it is applied. In C you would use 'static' variables, but languages with closures allow for a more robust approach. Scheme textbooks are full of examples that use this trick to define counters or other objects via closures. You can well argue that these functions do not "mutate", they merely access some data that is mutated, but there is no observable difference from the perspective of the caller.
Functions are rarely used this way, it’s bad practice. Typically when this is done the mutating state is scoped in an object and the function is not called a “function” it’s called a method.
Sets are functions in Clojure, and so are vectors, but lists are not.
> Arrays are functions whose domains are isomorphic to contiguous subsets of the integers
Yes. And a sandwich is "a stack-based heterogeneous data structure with edible semantics." This is not insight. It is taxonomy cosplay.
Look, arrays and functions share some mathematical structure! - Irrelevant. We do not unify them because representation matters.
When a language makes arrays "feel like functions," what it usually means is: "You no longer know when something is cheap." That is not abstraction. That is obscurity.
Industry programmers do not struggle because arrays lack ontological clarity. They struggle because memory hierarchies exist, cache lines exist, branch predictors exist, GPUs exist, deadlines exist.
> the correspondence between arrays and functions [...] is alluring, for one of the best ways to improve a language is to make it smaller
No. The best way to improve a language is to make it faster, simpler to reason about, and less painful to debug.
> I imagine a language that allows shared abstractions that work for both arrays and appropriate functions
What if we invented increasingly abstract our own words so we don’t have to say ‘for loop’, map, SIMD, kernels?
Making arrays pretend to be functions achieves exactly none of those things. It achieves conference papers that end with “future work”.
Why is this academic slop keep happening ? - Professors are rewarded for novel perspectives, not usable ones.
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, targeting GPUs, and explicitly described as “not intended to replace existing general-purpose languages” (quote from the language’s home page.) As such, it has requirements and constraints that most languages don’t have. Looking at its design through a general-purpose languages lens doesn’t necessarily make sense.
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.
> very few languages aside from C++ have good CUDA support
CUDA happens to be (loosely) source-compatible with C++, but I'm not sure that's the same as saying C++ has good CUDA support. The majority of C++ code does not compile to CUDA (although the inverse is often true).
> C++ certainly doesn't achieve that by having its arrays be equivalent to functions "in practice" or in any other sense
The syntax may not be unified, but what else do you think iterators are for? They are an abstraction to let us ignore pesky details like the underlying storage of arrays, and instead treat them like any other generator function. This is perhaps more evident in a language like Python where generators and iterators are entirely interchangeable.
> 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
These are specific oddities of Furthark - we have languages (i.e. C/C++) where the size of an array is not knowable, and we have languages where the range of inputs to a function are knowable (at least for numeric inputs, i.e. Ada)
> 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
Again, this is a case of Furthark's own design decisions restricting it. This is only a problem because their arrays are carrying around runtime size information - if they didn't have that, one wouldn't be able to usefully return them from branches anyway. Alternately, there are plenty of ML-family languages where you can return a function from a branch.
idk probably?
No - An array is a data structure that stores pre-calculated values in memory, whereas a function is executable logic that computes a result only when it is called.
Not a semantic difference, just a performance difference ... and a function can cache for the same performance anyway.
Correct. But indexing into an array is logic that computes a result when it is called.
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 and are something else.
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.
> Haskell provides indexable arrays, which may be thought of as functions whose domains are isomorphic to contiguous subsets of the integers.
> I found this to be a hilariously obtuse and unnecessarily formalist description of a common data structure.
Well it is haskell. Try to understand what a monad is. Haskell loves complexity. That also taps right into the documentation.
> I look at this description and think that it is actually a wonderful definition of the essence of arrays!
I much prefer simplicity. Including in documentation.
I do not think that description is useful.
To me, Arrays are about storing data. But functions can also do that, so I also would not say the description is completely incorrect either.
> who can say that it is not actually a far better piece of documentation than some more prosaic description might have been?
I can say that. The documentation does not seem to be good, in my opinion. Once you reach this conclusion, it is easy to say too. But this is speculative because ... what is a "more prosaic description"? There can be many ways to make a worse documentation too. But, also, better documentation.
> To a language designer, the correspondence between arrays and functions (for it does exist, independent of whether you think it is a useful way to document them) is alluring, for one of the best ways to improve a language is to make it smaller.
I agree that there is a correspondence. I disagree that Haskell's documentation is good here.
> currying/uncurrying is equivalent to unflattening/flattening an array
So, there are some similarities between arrays and functions. I do not think this means that both are equivalent to one another.
> would like to see what it would be like for a language to fully exploit the array-function correspondence.
Does Haskell succeed in explaining what a Monad is? If not, then it failed there. What if it also fails in other areas with regards to documentation?
I think you need to compare Haskell to other languages, C or Python. I don't know if C does a better job with regards to its documentation; or C++. But I think Python does a better job than the other languages. So that is a comparison that should work.
Some people really do look at a painting and see only brush strokes huh
At this point I look at a painting and think, they should've used JS