However, if iteration and tail-recursion are equally powerful constructs, the implication that recursion is morally superior to iteration seems misplaced.
For example, if you can express a finite state machine (FSM) as a number of mutually (tail) recursive functions. Then you can reuse this FSM as part of a larger FSM via a tail call. You can't do this with the iterative constructs in C et al---the whole FSM must be defined in one spot.
Doesn't it depend on how the iterations are compiled? Seeing how e.g. a normal continuation is compiled in C#.
foreach(var thing in Things)
{
if (thing.IsAlive)
yield return thing;
}
Any decent compiler will handle it just fine. If you want to include crappy compilers, well, then we need to include the same for LISP and Scheme. Whatever the language specification may claim about tail recursion is not relevant when you sit down to produce code for the actual system at hand.
In Scheme, local functions are used for looping (via tail recursion). C doesn't even have those (other than as a GNU C extension).
Why not?
"boolean hasNext()
Returns true if the iteration has more elements. (In other words, returns true if next() would return an element rather than throwing an exception.)
Returns: true if the iteration has more elements"
https://docs.oracle.com/javase/8/docs/api/java/util/Iterator...
Also, the for-each construct takes an Iterable, not an Iterator, though Iterable produces Iterators.
That can matter in certain cases of large objects or slow or side-effecting stream access
Far better to have something like `map` (or a `Mappable` interface or whatever), or even Javascript's `forEach` method IMHO.
Do you feel the same way about stream abstractions? They are also cursor-based. How about network connections?
`Mappable`, `forEach` or any other mechanism that inverts control via a callback is less composable - how would you implement a `zip` function over such streams?
(I'm not a huge fan of Java's Iterator interface specifically. I marginally prefer IEnumerator from .net, which is peekable by default and doesn't have the awkward `remove()` method, which is seldom reliable through transformed iterator pipelines. And for that matter, I'm not that much of a fan of OOP; but an OOP encapsulation of a forward-only cursor isn't problematic.)
> Do you feel the same way about stream abstractions? They are also cursor-based. How about network connections?
It's not the implementation if Iterable I'm complaining about (e.g. whether they use a forward-only cursor) and it's not the use of Iterable to implement e.g. a stream processor over a pair of zipped streams, or whatever.
I'm specifically complaining that the Iterable interface is a very poor basis for implementing looping (which is the goalpost location set by the post title). A looping construct like `for (MyClass myElem : myCollection) { foo }` denotes that `foo` should be executed once for each element in `myCollection`, with that element bound to `myElem`. If the implementation does anything else, it's not conforming to what was denoted, which violates the principle of least surprise and can be thought of as spooky action at a distance. In particular, 'skipping' an element (i.e. where the Iterable produces an element but the loop body does not get executed for that element) indicates that the loop's state has been interfered with, i.e. it is poorly encapsulated. The loop construct specifies what to loop over, the loop body can decide to skip a given element using `continue` and `break`, and no lexically-separate code should be able to mess with that (modulo exceptions, etc. if you want those in the language).
To use this looping construct in Java, `myCollection` must be `Iterable`. It is up to the particular class what this means, e.g. what counts as an element, what counts as the next element, etc. For example, `myCollection` could contain an array, and its `Iterable` implementation might return only the odd-indexed elements of that array. That's fine, and wouldn't be a case of "skipping" since the even-indexed elements are never produced by the iterator. In other words, given such an iterator, the construct `for (MyClass myElem : myCollection) { foo }` is implicitly asking to loop over the odd-indexed elements (since what-gets-looped-over is defined by `myCollection`, and in this case we've assumed that `myCollection` only returns the odd-indexed elements).
If we aspire for the for-loop construct to behave in this way (which I would argue we should), then we find that Java's `Iterable` interface violates that encapsulation: the state of the loop can leak out via the Iterable (`myCollection`) such that code that's lexically-distinct from the loop body (e.g. methods called from the loop body, anything called by those methods, etc. as well as anything running in another thread) can call `myCollection.next()` and cause an element to be skipped.
> `Mappable`, `forEach` or any other mechanism that inverts control via a callback is less composable
The first remark I'd make here is that I'd class a `for` loop as a `mechanism that inverts control via a callback`, since a loop body is nothing other than an anonymous "callback" function with a single argument (`myElem` in my example) and dynamic (rather than lexical) scope. I would also claim that a `for` loop inverts control. The aspiration above is that `myCollection` controls what elements the loop body should be run with, yet it is not given control over the running of the loop body. Instead, the control is inverted such that the `for` construct (which wraps the loop body) controls the argument of the loop body, and the `Iterable` is merely consulted each time that `for` decides to perform an iteration (which, crucially, may occur after something else has interacted with the `Iterable`).
Secondly, I would claim that mechanisms like `forEach` are not only more composable than `for` + `Iterator`, but that `for` + `Iterator` is so uncomposable that it can be unsafe to even have two loops exist in the same program! This is a simple consequence of the fact that the state of one `for` loop can leak out via an `Iterable`, that an `Iterable` is a value which can be passed around between arbitrary parts of a program, and that one way to clobber the state of an `Iterable` is to use it in a `for` loop.
On the other hand, not only can we have as many calls to something like `myCollection.forEach` as we like in a program, but we can even nest them!
> how would you implement a `zip` function over such streams?
`Mappable` does not represent a "stream", it represents a collection whose elements can be transformed individually. Alternatively, we can think about it as representing a context within which parameterised computations can be performed (I think this second perspective makes it clearer how `Mappable` is a natural generalisation of `for`, where our computation is parameterised by the current element, compared to `Iterable` which inverts control by exposing elements to an intermediary layer (the `for`) which performs the actual computation).
On the other hand a stream (as generally understood) represents a producer of elements, or alternatively a collection of one-shot (linear) elements, or alternatively a time-varying parameter (where we can't "go back in time"). That's a separate concern to looping, where something like an Iterator may be appropriate.
If we don't require that our code propagates the guarantees of a stream, it becomes trivial to `zip` two `Mappable`s: if they're finite and small we can get away with using map/forEach to build lists of the elements of each and count how many there are, then our new `Mappable` just maps over the range `0` to `count` and invokes the given function as `f([this.list1[i], this.list2[i]])`. If our `Mappable`s are large or infinite, we can zip them by performing two maps concurrently and using a shared reference to pass accumulate the current iteration's elements from each of the maps. The concurrency could be done with asynchronous calls, threads, lazy evaluation, etc. and would be safely encapsulated inside the resulting `Mappable`.
Or, alternatively, we could use Iterators, since this is a reasonable use case for them. I'd still avoid using them with `for` though; we could use some generic Iterable-zipper to compose our streams, and use map/forEach if we ever want to loop over it. Also note that it's fine for a class to implement `Iterable` alongside `Mappable`; I'm just saying that `Iterable` does not provide a good basis for looping, and it's unfortunate that a language might force us to do it anyway.
If we want to do something that requires a change to the language, e.g. the "async/await" stuff that seems to be popular these days, then we must convince the language designers that it's a good idea, wait for it to be implemented, wait for a new release of the language, and maybe (if we want our code to be portable) wait a few years for it to become widespread (e.g. new versions of RedHat, Debian, etc. to include it by default). Alternatively we could maintain a fork or patchset, which might be a lot of work and receive little support. We may also have to do this for multiple implementations, e.g. GCC + Clang + MSVC + .... We might also have to go through some form of standardisation effort (e.g. C++14, Haskell2010, etc.).
Our change may impact every user (e.g. if we add exceptions to a language, everyone must now worry about catching them, e.g. from callbacks). This impact may last for decades, even if that feature falls out of favour, since it must remain for backwards compatibility. Any subsequent language features must take our feature into account (e.g. if we added exceptions, and someone wants async/await, that person must consider how async/await deals with exceptions and vice versa).
On the other hand, if something can be implemented as a library then we don't have to wait for anyone: we can just write it. It will work with multiple implementations of the language. Those who don't want or care about our feature can just avoid the library. If the feature falls out of favour, we can just avoid importing that library in our new projects.
That’s debatable and there’re also strong arguments why not. I don’t work on programming languages but I use them a lot. I generally prefer built-in features over libraries, here’s why.
Language designers are usually conservative, in a good way. If they implemented a feature into the language or into a standard library, it’s likely to stay. As a user, this gives me a good chance my code will compile by a version of compiler 10 years in the future.
Libraries are easier to fork, modify and evolve. This is good for development of language and libraries but not necessarily good for developers using them, first I need to pick one, then I need to ensure all developers on the project agree on the set of libraries and their version. Both take time. For languages with batteries included, I don’t need to worry about that.
Libraries baked into a language are of better quality, on average. They receive higher users count, the bugs are more likely to be found and fixed.
Not everything can be implemented in libraries. C++ designers made a mistake with multithreading, only fixed recently. Async-await feature is the same, note how in .NET and golang it spawns across the whole stack: libraries, compiler & language, runtime, OS kernel interface.
Minor correction: In Haskell and F#, Async/Await can and is implemented as a library.
For example, built-in features are usually better quality than libraries due to survivorship bias, caused by the difficulties I listed. Libraries can also undergo scrutiny, need for buy-in, etc. and I claim that if those are equally rigorous for both a language feature and a library, then the library would be preferable.
Likewise, rather than relying on the language designers to pick a consistent set of features, we could instead rely on some other external entity to pick a consistent set of features in the form of libraries. I claim that if those two groups are equally competent, recognised, etc. then the set of libraries would be preferable.
And so on.
As an aside, regarding your preference to have exceptions baked into a language: I personally think that exceptions are dangerous and confusing-inducing (compared to Maybe, continuations, etc.). If they were a library, I could ignore them; baking them into a language makes me less inclined to use that language ;)
Yes, they’re better. No, that’s not survivorship bias, the reason is more careful selection (for third-party built-in libraries like C++ standard library) or better design (for first party libraries like .NET framework or JRE).
> and I claim that if those are equally rigorous for both a language feature and a library
I claim that’s impossible in practice, especially for powerful languages with multiple ways of doing same things. Look at C++ for an example.
> we could instead rely on some other external entity
Again, this is theory. In practice there’s no such external entities. Picking consistent features = doing design. Collective bodies, like committees or markets, are terrible at designing things.
> regarding your preference to have exceptions baked into a language
You’re probably replying to someone else’s comment?
> baking them into a language makes me less inclined to use that language
Most mainstream languages include them. You can stop programming such languages but you can’t stop using software written in them, exceptions are baked in e.g. C++ and JavaScript languages.
"More careful selection" is exactly what I meant by survivorship bias, i.e. the only language features we encounter (outside one-person pet languages) are those which managed to survive this selection process. Rejected proposals aren't as visible, and we'll never know about all those ideas which were never even proposed due to their low chance of being selected.
Libraries don't have this selection pressure, so we can see many more of bad ideas, poor implementations, throw-away experiments and learning exercises.
As for better design, this is another survivorship effect: after a feature is selected (e.g. "we're going to add exceptions"), those features go through critique and consensus-building processes ("should they work like this? how should this edge-case be handled? etc.") which weed out low-quality suggestions and (hopefully) spit out generally better designs.
Libraries don't undergo as much scrutiny and collective-ownership, unless they become popular.
> I claim that’s impossible in practice
I never claimed it wasn't. Still, I'd point to projects like Boost for C++, Rails for Ruby, Numpy/Scipy/Pandas/etc. for Python, etc. as examples of third-party libraries which offer features comparable in quality, stability, etc. to that of language built-ins (but not necessarily their own language's features; e.g. C++ is way more stringent than Boost, but Boost's API may be more stable than e.g. Nim's).
> Collective bodies, like committees or markets, are terrible at designing things.
Like programming language features? ;)
> You’re probably replying to someone else’s comment?
Oops, you're right about that part; apologies!
On Windows I tend to avoid Boost when I can. At least when I worked on Boost-based C++ projects a few years ago, boost’s quality varied a lot between different parts of the library. Also it’s huge, affects complexity of build process, may affect compilation times, by default it links to some very large dynamic libraries i.e. complicates and inflates installer. Also they have a lot of code for compatibility with older versions of the language, they support C++0x. I usually have much newer versions, always C++14 usually 17. In short, with boost I feel like I’m paying for a lot of things I don’t need.
> Like programming language features? ;)
Some languages have core design teams, who aren’t a collective body, have clear shared vision, and are therefore able to do better design. When I’m looking at what’s happening with Rust, or Golang, or C#, I see rate of improvements faster than that of C++ or Python or JavaScript.
I was in the extensible languages camp for so long. Now I believe that widely used stuff should be part of the language. The reason is that people love to write libraries to scratch their own itch, but it takes a whip to make them write libraries that work together: use consistent naming, accept and return the same types, avoid overlaps in functionality, etc. It's just nobody's job. Except if you call your collection of libraries a "language" and try your best to harmonize them. That's what a language should be. Being minimal is no virtue.
My favorite example is Unicode: the best languages are those that bake it in and force everyone to use it. Or exception handling: you could give people the tools to build their own error handling mechanism, or you could build one good mechanism (with deep language integration, stacktraces etc) and force everyone to use it. When everything uses the same kind of strings and the same kind of errors, programmers can focus on what matters.
If I remember correctly, there was briefly discussed interesting proposal to add explicit tail calls into Python almost decade ago. You would use keyword or syntax to perform tail-calls explicitly (not the tail call decorator hack). This would make tail calls actual looping construct.
--> return myself(...) # tail call
--> return var * myself(...) # not a tail call
x = f(a)
...
...
return xIf "x" is declared there and never mutated in the subsequent code, and the code in the "..." doesn't perform any side effects, then such an optimization could occur... but then again, if the code in the "..." in your example didn't perform any side effects, it'd be dead code.
Both
If (b == 3):
x = f(a)
else:
x = g(a)
return x
if (b == 3):
x = f
else:
x = g
return x(a)
if (b == 3):
return f(a)
else:
return g(a)
That's what I did in my Forth dialect; I called it "goto".
(define (map proc lst)
(if (null? lst)
'()
(cons (proc (car lst)) (map proc (cdr lst)))))
For example (using CL), the code could be turned into two auxiliary map%% and map% functions (map% would be what a call to map expands into).
(defun map%% (cons function list)
(declare (optimize (speed 3) (debug 1) (safety 1))
(type function function)
(type list list)
(type cons cons))
(when list
(map%% (setf (cdr cons)
(list (funcall function (first list))))
function
(rest list))))
(defun map% (function list)
(let ((fresh (cons nil nil)))
(map%% fresh function list)
(rest fresh)))
(map% #'1+ '#1=(5 6 8 4 5 1 3 . #1#))
Heap exhausted, game over.oh, sorry, I was reading peoples comments about map. both for iteration and recursion, the compiler (and it author) has to think pretty hard. with higher order functions it just says 'great'