r/elm • u/johnorford • Mar 29 '17
Remove Recursion?
Conceptually, could Elm do everything it does today without recursion? I guess yes... Some edge cases would make fold an ugly replacement, but not too many I suspect
7
u/jfbourget Mar 29 '17
Allow me to ask "Why in hell would we remove recursion? It's such a powerful tool"
4
u/johnorford Mar 29 '17
Power is not necessarily a good thing. Power and complexity are correlated, and I rather keep things simple - esp when the power may not be even necessary (fold can do almost everything recursion can)
6
u/jfbourget Mar 29 '17
But isn't recursion a true primitive, or a well-known citizen of any functional programming language? I'm not trying to force a functional banner above Elm's head, i'm just saying that to me, it is as natural as any other iteration mechanism. It's a design tool i use very often when, for example, i need a fold but also want to stop iterating prematurely, when a condition is met.
Losing recursion would feel like a stepback for me.
I also feel like it is really not on the forefront when it comes to "patterns" used by Elm beginners. Recursion in Elm is not a driving force like it is in Lisp or clojure. Does it really "pollute" or give a "over complicated view" over how Elm handles problem solving?
1
u/johnorford Mar 29 '17
Good pt, I too am a fan of recursion, I suppose I am getting myself into a mindset of what a beginner would require to learn and use Elm - and recursion is probably bottom of the list or even superfluous. I am also being a bit mischievous of course : )
6
u/ianmackenzie Mar 29 '17 edited Mar 30 '17
To me the main argument is to avoid crashes - right now you can still pretty easily crash an Elm app by calling a recursive function on a large data structure. It's particularly worrying because it's the sort of bug that can show up only once you start testing with large amounts of data (or in production, if you only ever test with small test cases). Just yesterday I got a runtime error in the Elm debugger since it was trying to introspect a large mesh (a few thousand vertices) that I loaded from JSON to render in WebGL - it was fine with little cubes and the like but got a stack overflow when I tried to load the Stanford teapot model.
I don't think the answer is to do away with recursion entirely, but I think stuff like compiler warnings for recursive functions that aren't tail recursive could be useful. And in the long term perhaps function annotations so you can declare that a certain function should be tail recursive (so it should trigger a compile error if it isn't) or explicitly not tail recursive (so the compiler won't even issue a a warning).
3
u/binaryblade Mar 29 '17
Why would you remove goto, it's such a powerful tool? Why would you remove mutability it's such a powerful tool? Why would you remove dynamic typing it's such a powerful tool?
4
u/jfbourget Mar 29 '17 edited Mar 29 '17
We should not compare goto statements to recursion, if you ask me. Then again, every tool has pros and cons, i agree.
Removing recursion from elm simply does not seem like a logical path to follow.
I also agree that recursion in Elm has its flaws.
2
u/jfbourget Mar 29 '17
I feel like immutability, purity, static typing, as well as recursion, are parts of what makes Elm what it is. A powerful, robust and FAIRLY safe statically typed language, with a strong mind on how you should code, while still allowing a proper degree of developer creativity and expressiveness.
Recursion is not the problem. The way its handled, perhaps, should be looked at. When it comes to how recursion is implemented and handled within Elm however, i won't pretend that I have the knowledge or skill to be relevant in the conversation.
2
u/binaryblade Mar 29 '17
You absolutely should compare the two. In both cases you are trading flexibility for readability and compiler guarantees. When you remove goto from a language the goto isn't gone, compilers still create jump instructions, we just bundle that concept up and let the compiler and the compiler alone deal with it. This makes it easier to reason about and write correct programs, it also enables the compiler to perform more powerful optimizations. The same is true for dynamic typing and mutability. "Removing" them ultimately makes the code easier to reason about and easier to write.
Generality and flexibility comes at a cost. You probably understand this for types really well. You can chose to use enumerated types, or you can use an Int. Ints are more general but they are less expressive. By choosing to use enumerated types you tell the compiler exactly what you want and, as a result, the compiler gives you some additional guarantees. You trade the general Int type for a specific Enum and doing so makes your code more expressive. This is true for languages as well. By using more specific statements your code becomes less general, but more expressive.
These same sentiments are true of recursion as well. You shouldn't use recursion unless you absolutely have too. Recursion is general, map and fold are specific and expressive. However, removing recursion from the language at this point would be problematic because there is currently no mechanism for traversing tree structures without it.
I also agree that recursion in Elm has its flaws.
Everything has it's flaws but I didn't mention any. The reason I mentioned lack of dynamic typing or mutability is because removing those things from a language makes it more effective. They are good things.
2
u/jfbourget Mar 29 '17
I understand and agree with all of the above, and they are all good and well informed points.
However, I still don't see bounded recursion as something to avoid at all cost, unless absolutely necessary. My functional background is very "lispy", and perhaps thats why i am biased.
I'm not sure what you mean when you say "Recursion is general, map and fold are specific and expressive".
Well-made recursion can be very clean and expressive and is as generic/specific as any other "iteration/etc" mechanism. Then again, i might not clearly understand what you meant.
As you've stated, I think this topic, although philosophically challenging and interesting, can not even be considered until there are other ways of traversing (with premature-stop capabilities) unorthodox data structures.
6
u/Ahri Mar 29 '17
How would you iterate without recursion and without mutable variable references? Fold is implemented as a recursive function.
1
u/johnorford Mar 29 '17
True, at some level deep in the internals it would do recursion - just as type classes and mutability are done now.
2
u/jessta Mar 30 '17
Foldrequires a fixed length loop. Any time you want to loop based on a condition (ie. a while loop),Foldisn't the answer.Anything that loops based on a condition will always have the possibility of never completing or never completing within an amount of time you feel is appropriate.
2
u/binaryblade Mar 29 '17
That's like asking how do you implement loops without goto
2
u/Ahri Mar 29 '17
In the sense that I'm interested how it can be achieved, yes. Feel free to enlighten me.
The only way I can think of is to add a language construct that cheats for you: iter f l, but then you basically have a crippled fold anyway.
1
4
u/pwgen-n1024 Mar 29 '17
the answer to that is clearly no, as removing recursion and not having loops would stop the language from being turing complete.
fold and map and similar are themselves implemented using recursion.
2
u/johnorford Mar 29 '17
Turing completeness is a bug not a feature - if it doesn't actually add anything to the functionality. I think there's a lot of scope for well targeted Turing-Incomplete languages...
7
u/VeggiePaninis Mar 29 '17
Why is this dowvoted?
Turing completeness inherently makes languages not completely defined. Programming languages as is already aren't fully Turing complete because they don't have infinite tape/memory. So it's clear being Turing complete isn't a requirement for being a productive language.
Ensuring the language only supported bounded recursion instead of unbounded recursion, would ensure that no programs ran till they crashed, but still would cover 99% of all programs today.
The future of programming languages will be to remove Turing completeness and move closer to mathematical purity and being well / completely defined.
Removing dynamic typing via Hindley-Miller typing goes a long way to eliminating classes of program failure, and I believe removing unbounded recursion from languages will be next.
4
u/johnorford Mar 29 '17
thanks - enlightening!
1
Mar 30 '17 edited Mar 31 '17
enlightening
Uh, I don't think so. I'm calling BS on that post in general and on this claim in particular:
Ensuring the language only supported bounded recursion instead of unbounded recursion, would ensure that no programs ran till they crashed, but still would cover 99% of all programs today.
First off, I don't see how the writer of this arrived at the conclusion that bounded recursion prevents crashes. Stack overflow (and related conditions) is not caused by infinite recursion but rather by recursion beyond a certain (finite) threshold. Bounded recursion in and of itself doesn't prevent that unless you have a reliable way to figure out the safe bound, which you typically don't have. (You'd need to only target a specific hardware + software configuration, think spacecraft.)
Second, I'm not buying that such a language would cover 99% of programs, I'm not going to believe that unless backed up by solid evidence. Which IMHO would amount for a scientific breakthrough worth of awards.
Besides, you complained about recursion being complex. You do realize these ML-style languages are way more complex than simple recursion, right?
4
u/jessta Mar 30 '17
The languages are Turing complete, the machines they run on aren't and we specifically and intentionally limit the size of problems we solve to fit within those limitations, but the general case of those problems requires a Turing machine.
Unbounded recursion (the while loop) is essential in any program that needs to deal with any form of communication or user input, where knowing the bounds requires knowing the future. You can limit unbounded recursion for a certain subset of programs but web applications definitely have requirements too general for such a limitation. A common example is polling a server, "while we haven't got a response, request again every 2 mins". How many times should we poll the server?
2
u/VeggiePaninis Mar 30 '17
The languages are Turing complete, the machines they run on aren't and we specifically and intentionally limit the size of problems we solve to fit within those limitations, but the general case of those problems requires a Turing machine.
Agreed, but this is just another way of saying what I was saying. We don't require the full power of infinite recursion to be productive.
There are definitely situations where we don't know how long to iterate. So maybe a better more accurate statement is "removing the ability for unbounded recursion to produced undefined program results". In haskell terms the difference between running fold vs scan on an infinite datastream.
In the case you called out, we would label the server poll results as co-data, and appropriate for co-recursion, since we don't know how long we'd have to poll for. But we could statically prevent any code from calling 'tail', 'max', or any other function whose behavior would be undefined on this infinite stream of data. This allows us to eliminate classes of invalid programs.
3
Mar 30 '17
We don't require the full power of infinite recursion to be productive.
Yes, we do.
A huge percentage of useful software is one way or another based around event loops that are infinite and process requests - for example all sorts of network daemons, DBMs, heck, even simple GUI programs. These programs hang in an infinite loop by design. When processing requests, we need to allocate arbitrary amounts of memory. Of course, we don't want programs to actually allocate an arbitrary amount of memory (potentially larger than what's available on the actual machine), and so having the program respect some upper bound is a nice thing, but this upper bound cannot be statically defined as part of the program's source code, because we need to change it dynamically. It's a matter of configuration.
3
0
u/pwgen-n1024 Mar 29 '17
what the fuck is wrong with you?
first the "shouldn't elm look more like javascript" and now this?
i sure hope you are trolling.
3
u/EffBott Mar 30 '17
These threads have been absolutely hilarious to read. The next thread will probably be "What do think about removing functions?"
1
u/Ahri Mar 29 '17
I think it's an interesting discussion to have, especially given /u/VeggiePaninis' response.
2
u/witoldsz Apr 02 '17
One thing I've got from this discussion is that we all were promised no runtime exceptions, but clearly lots of us get it while traversing data structures. Something must be possible to eliminate such problems. Is allowing for recursive calls only with TCO an option? Or is there anything else we could do, other than education?
0
13
u/[deleted] Mar 29 '17
Removing recursion would make it impossible to traverse custom defined data structures, like trees. Sure, you can do most List things with a fold, but now you're stuck using lists for everything.