4 ms·
But Lisp already had recursion, right? It was just Algol and the international standard that was held up. Similar to the situation with things like CoffeeScrip
by ilaksh 11y ago
But Lisp already had recursion, right? It was just Algol and the international standard that was held up.
Similar to the situation with things like CoffeeScript vs. ES6 etc.
What I think we need is a standard so flexible and meta that systems can evolve without waiting for society or standards to catch up. Which we have in Turing-complete languages.
But we should standardize somehow on a very meta level.
- pekk 11y agoLots of things from Lisp never made it into mainstream programming (meaning things like Fortran, C, Java).
- davexunit 11y ago>What I think we need is a standard so flexible and meta that systems can evolve without waiting for society or standards to catch up. This is why we must demand macro systems in the languages we use. Building new languages is part of the programming process. Everyone should be able to do it, not just standards committees.
- Gibbon1 11y agoWinging off a comment above, I find recursion generally intuitive, occasionally useful, and really really boring. Offhand years ago I used a dialect of C that had no recursion so I can see both sides of this argument. On the one hand, there is a pain point when you don't have access to recursion. On the other, boy can a compiler that eschews recursion produce small and fast code. (Because without recursion the call graph is acyclic)
- anindyabd 11y agoI wouldn't call recursion boring. Quicksort in Haskell is probably my favorite two lines of code: quicksort [] = [] quicksort (x:rest) = quicksort [y | y <- rest, y <= x] ++ [x] ++ quicksort [y | y <- rest, y > x]
- nemesisrobot 11y agoIt's been discussed before, but that's not really quicksort though (since it's not in-place)[0] 0: http://stackoverflow.com/q/7717691/1235548 http://stackoverflow.com/q/7717691/1235548
- emmelaich 11y agoDo we know that for sure? I mean - could a sufficiently smart compiler actually create machine code which _did_ do it in-place?
- jmount 11y agoThis variant (with the <= comparison) takes c N^2 on lists of length N that a repeated constant ( http://www.win-vector.com/blog/2008/04/sorting-in-anger/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/ ).
- copperx 11y ago> On the other, boy can a compiler that eschews recursion produce small and fast code. Are you really implying that if recursion was turned off in a modern compiler it could create better code?
- Gibbon1 11y agoThat would be hard to turn off. My experience is with a old 8051 compiler. Notable feature was it never pushed anything on the stack other than return addresses. Used the call tree to fold parameters and local variables into a small amount of common memory. I think modern compilers deal with this situation by in-lining. But that can cause the code size to swell vs calling a subroutine that accesses globals. Just saying, you add a feature to a language, you will pay something for it.