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

Are arrays functions?

futhark-lang.org

Post reply on HN
Print view View original

111–120 of 145 posts

Re: Are arrays functions?

#111

Post by bArray »

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:

    ls -la *.png # lazy
    ls(-la, *.png); # formal
For pipes, they could be expressed as either:

    ls -la *.png | grep cat # lazy
    ls(-la, *.png) | grep(cat)
    |(ls(-la, *.png), grep(cat)); # formal
I thought about writing this with something like Micropython that could have a very small memory footprint.

Re: Are arrays functions?

#112

Post by lioeters »

galaxyLogic wrote: post #90
lioeters wrote: post #78

Earlier quoted context omitted.

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 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 We can even consider any variable as a f…

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

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.

Re: Are arrays functions?

#113

Post by trenchgun »

tombert wrote: post #5

I remember I got a little confused when I was first learning TLA+, because what you normally call "functions" are "operators" [1], and what you'd normally call "maps" or "lists" are called "functions". It was odd to me, because it hadn't really occurred to me before that, given infinite memory (and within a mathematical framework), there's fundamentally not necessarily a difference between a "list" and a "function".…

Arrays/maps/lists are extensionally defined functions, where as functions/TLA+ operations are intensionally defined functions

Re: Are arrays functions?

#114

Post by [deleted] »

winwang wrote: post #6
nomel wrote: post #3

Earlier quoted context omitted.

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!

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

[deleted]

Re: Are arrays functions?

#115

Post by [deleted] »

catapart wrote: post #30
nomel wrote: post #3

Earlier quoted context omitted.

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!

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…

[deleted]

Re: Are arrays functions?

#116

Post by CyberDildonics »

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

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…

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

This presumes the framework in which one is working.

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

The type of map is and always will be the same as the type of function. This is a simple fact of type theory, so it is worthwhile to ponder the value of providing a language mechanism to coerce one into another.

It isn't worthwhile to 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.

Re: Are arrays functions?

#117

Post by kibwen »

deathanatos wrote: post #50

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

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.

Re: Are arrays functions?

#118

Post by QuadmasterXLII »

psychoslave wrote: post #75

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

Unsupervised, in a language where arrays and functions could be called with the same syntax, one would be tempted to do

    def slice(array, start, end):
        def new_array(index):
            return array(index - start)
        return new_array
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.

Re: Are arrays functions?

#119

Post by BlackFly »

zozbot234 wrote: post #97
BlackFly wrote: post #92

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

> but that implies you need to statically prove that each index i for V[i] is less than N. So your code would be littered with such guards for dynamic indexing. You just need a subrange type for i. Even PASCAL had those. And if you have full dependent types you can statically prove that your array accesses are sound without required bounds checking. (You can of course use optional bounds checking as one of many metho…

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.

Re: Are arrays functions?

#120

Post by BlackFly »

fanf2 wrote: post #105
BlackFly wrote: post #92

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

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.
Post reply on HN