5 ms·

I think the point was that recursion makes a better foundational primitive. For example, with Java and C#, their (somewhat arbitrary) Iterator and IEnumerator l

I think the point was that recursion makes a better foundational primitive. For example, with Java and C#, their (somewhat arbitrary) Iterator and IEnumerator library interfaces are baked into the syntax of the language (e.g. the foreach loops). This is not a good position to be in.

pjc50 8y ago
> This is not a good position to be in. Why not?
- willtim 8y ago
  Well the Java iterator interface has changed once already since Java was released (see the old java.util.Enumeration). The current one also has problems, it isn't clear from the API whether "hasNext" will or will not advance the stream (it often does). There are also issues with using it as the foundation for e.g. Async/Await coroutines. But, it simply cannot be changed or deprecated, as it is baked into the syntax of the language.
  - LgWoodenBadger 8y ago
    How is it not clear? "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.html#hasNext-- 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.
    - wffurr 8y ago
      It depends on whether the underlying stream supports "peek". If not, in order to determine whether there is a next element, the iterator must consume the next element and hold it in local memory until a call to next. That can matter in certain cases of large objects or slow or side-effecting stream access
  - chriswarbo 8y ago
    My problem with "iterators" is that they violate almost all OOP practices: they're not encapsulated (their cursor state is exposed by `hasNext`, `next`, etc.), they don't manage their own state (they rely on having their `next` method called), they resist other attempts at encapsulation (using the same iterator in two places will break both, so we must know implementation details like where that iterator is used), their methods are sequentially coupled, etc. With the main reason to do this being improvement to the `for` keyword, which is structured programming not OOP. Urgh. Far better to have something like `map` (or a `Mappable` interface or whatever), or even Javascript's `forEach` method IMHO.
    - barrkel 8y ago
      Iterators (Java-style) encapsulate a forward-only cursor. 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.)
      - chriswarbo 8y ago
        > Iterators (Java-style) encapsulate a forward-only cursor. > 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.
  - tigershark 8y ago
    And the whole enumerator/stream now it’s a mess in Java compared to C#. In c# you have IEnumerable that works perfectly with LINQ without using a .stream() method call. You don’t need to collect it explicitly, it will be just “materialised” at iteration time. If you instead try to pass a stream, even casting it to an enumerator, and it is used twice your software will fail at runtime. Honestly I can’t imagine how did they manage to over complicate so much Java streams implementation after that Linq was used successfully and in a very elegant way for years...
- chriswarbo 8y ago
  All else being equal, it's better to implement things in libraries rather than bake them into a language. 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.
  - Const-me 8y ago
    > it's better to implement things in libraries rather than bake them into a language. 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.
nabla9 8y ago
The problem with tail calls is that they are implicit. That's why it's usually called tail call optimization. There is nothing in the syntax to indicate that you actually have a tail call. You may have made a mistake and it actually blows up the stack. 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.
- willtim 8y ago
  It's debatable whether tail calls should be classified as an optimisation. In my view, they should be part of the operational semantics.
  - chriswarbo 8y ago
    I try to use the phrase "tail call optimisation" when an implementation may perform it but the language doesn't require it, and "tail call elimination" when the language requires it (and hence any implementation which doesn't is non-conforming).
- shakna 8y ago
  Tail calls were made explicit in Clojure, with the recur construct. It had more to do with the JVM than syntactic benefits, but it turns out to be a decent idea.
  - junke 8y ago
    "recur" can be used for self-call in tail position, but does not help with the general case where you may want to jump to another function.
  - steinuil 8y ago
    Tail calls do not just deal with recursive functions, in general TCO works on any function call in tail position. Maybe a more general recur construct (maybe called "jump") would be a good idea, but then you'd have to remember to use it.

pjc50 8y ago

> This is not a good position to be in. Why not?

willtim 8y ago
Well the Java iterator interface has changed once already since Java was released (see the old java.util.Enumeration). The current one also has problems, it isn't clear from the API whether "hasNext" will or will not advance the stream (it often does). There are also issues with using it as the foundation for e.g. Async/Await coroutines. But, it simply cannot be changed or deprecated, as it is baked into the syntax of the language.
- LgWoodenBadger 8y ago
  How is it not clear? "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.html#hasNext-- 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.
  - wffurr 8y ago
    It depends on whether the underlying stream supports "peek". If not, in order to determine whether there is a next element, the iterator must consume the next element and hold it in local memory until a call to next. That can matter in certain cases of large objects or slow or side-effecting stream access
- chriswarbo 8y ago
  My problem with "iterators" is that they violate almost all OOP practices: they're not encapsulated (their cursor state is exposed by `hasNext`, `next`, etc.), they don't manage their own state (they rely on having their `next` method called), they resist other attempts at encapsulation (using the same iterator in two places will break both, so we must know implementation details like where that iterator is used), their methods are sequentially coupled, etc. With the main reason to do this being improvement to the `for` keyword, which is structured programming not OOP. Urgh. Far better to have something like `map` (or a `Mappable` interface or whatever), or even Javascript's `forEach` method IMHO.
  - barrkel 8y ago
    Iterators (Java-style) encapsulate a forward-only cursor. 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.)
    - chriswarbo 8y ago
      > Iterators (Java-style) encapsulate a forward-only cursor. > 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.
- tigershark 8y ago
  And the whole enumerator/stream now it’s a mess in Java compared to C#. In c# you have IEnumerable that works perfectly with LINQ without using a .stream() method call. You don’t need to collect it explicitly, it will be just “materialised” at iteration time. If you instead try to pass a stream, even casting it to an enumerator, and it is used twice your software will fail at runtime. Honestly I can’t imagine how did they manage to over complicate so much Java streams implementation after that Linq was used successfully and in a very elegant way for years...
chriswarbo 8y ago
All else being equal, it's better to implement things in libraries rather than bake them into a language. 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.
- Const-me 8y ago
  > it's better to implement things in libraries rather than bake them into a language. 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.

nabla9 8y ago

The problem with tail calls is that they are implicit. That's why it's usually called tail call optimization. There is nothing in the syntax to indicate that you actually have a tail call. You may have made a mistake and it actually blows up the stack. 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.

willtim 8y ago
It's debatable whether tail calls should be classified as an optimisation. In my view, they should be part of the operational semantics.
- chriswarbo 8y ago
  I try to use the phrase "tail call optimisation" when an implementation may perform it but the language doesn't require it, and "tail call elimination" when the language requires it (and hence any implementation which doesn't is non-conforming).
shakna 8y ago
Tail calls were made explicit in Clojure, with the recur construct. It had more to do with the JVM than syntactic benefits, but it turns out to be a decent idea.
- junke 8y ago
  "recur" can be used for self-call in tail position, but does not help with the general case where you may want to jump to another function.
- steinuil 8y ago
  Tail calls do not just deal with recursive functions, in general TCO works on any function call in tail position. Maybe a more general recur construct (maybe called "jump") would be a good idea, but then you'd have to remember to use it.