Absolutely right. By the same qualifications, it's possible, but also completely infeasible, to create a flat map that approximates any function. Because it is obvious that it won't be useful, nobody will write home about it.
It's trivially impossible with unrestricted aliasing. No compiler can statically predict the properties of an unrestricted arbitrary graph about which, in the limit, absolutely nothing is known until runtime.
Sure, it is possible to model these things as functions, for example by "passing" the entire world as a "parameter". However, it is an extremely contrived modelling, basically you're hammering the square problem domain into the round function hole with the biggest hammer you can find until it "fits".
It is also possible to model these things as Turing machines, or NAND gates...
I suppose, but outside certain mathematical systems that are designed that way, assuming that all functions are total is unrealistic. The languages we use every day are Turing-complete languages and infinite loops can happen.
It's not `noncomputable` in Lean though. Lots of computable functions use it.
I've read Bauer's paper before btw. I think topoi are cool, but I don't think it's a complexity worth thinking about for everyone else who isn't concerned about these things.
This is a discussion of the phrase "such a feature would be entirely impossible"
You're now explaining to me in response to my previous post that some languages are a better fit in certain dimensions to perform a data transform? I think this is a discussion that needs to end now.
I nowhere said impossible! All I say it is tricky and that likely the code you write will have to be adapted in certain cases (compared to current existing implementations of numerical algorithms).
I haven't yet met anyone that wasn't just trolling when they claimed something like that. It should be fairly obvious you can do practically everything at any level of abstraction. It will just get more or less efficient (and even that is not a given).
If this were possible, it would require the blackest of black magic, and mapping anything other than primitive types across the void would be essentially impossible, e.g. anything useful like a DataFrame.
It's impossible to have such a tool. Not even close. If there is that would be the biggest innovation in the history of computer science (yeah, seriously).
See also “Seemingly impossible functional programs” by Martin Escardo, from 2007 ([1], also at [2]).
It covers similar ground and is referenced at the bottom of the article (along with three other references also by Martín Escardó), but I thought it worth mentioning explicitly because I remember reading it many years ago and finding it really fun.
That kind of perfect is possible in math but not in software, which runs on physical machines and was written and verified by humans. It's like building your bridge inside a vacuum chamber with no entrances or exits—possible but not practical.
reply