4 ms·

Another way to look at countfrom is that you have built--manually, as opposed to using any special syntax in your compiler--a "generator" for the sequence using

by saurik 6y ago

Another way to look at countfrom is that you have built--manually, as opposed to using any special syntax in your compiler--a "generator" for the sequence using a "coroutine". Had you written it in a language with support for typing the generator with syntax for coroutines, it would have looked directly recursive... but it wouldn't have been, as the implementation of that coroutine as expressed using normal routines would have had this property of storing thunks that are actually being called iteratively by the consumer. It thereby makes sense that the co-routine (which is sitting at a higher level to the routines which are used to implement it), being not a normal routine, doesn't have normal recursion: it instead has co-recursion. (Now, what is amazing to me, is that I open this document and not once does it even use the word "coroutine", even though all of this terminology makes a lot more sense if you are willing to do so ;P.)

kazinator 6y ago
It does look directly recursive Furthermore, in a lazily evaluated language, we could use the regular cons function, instead of an explicitly lazy lcons version. No coroutines are used here, only lexical closures. I changed my mind; lazy semantics plus recursion doesn't give rise to a new kind of recursion.
- saurik 6y ago
  > No coroutines are used here, only lexical closures. So first off, I just want to provide some clarity on the language I used, as this statement makes me think I was misunderstood: I appreciate what you typed wasn't "using a coroutine" any more than if you typed a structure and put some functions nearby in a nice and simple pattern you "used a class". I am saying the thing you typed "is" a coroutine, which is very different. I then explicitly said that what you were doing was "manually" building a coroutine, as you are in a language that doesn't use coroutines: it uses lazy execution. Like, I disagree with that sentence as what I said was you manually wrote what a compiler in a different language would have output if you could have directly used that feature, which you couldn't have because you didn't have it. > It does look directly recursive. However, that aside, you are correct here, and I noticed this a few hours ago during my tenth read of your code and it confused the hell out me, if it makes you feel any better. In particular, the thing that I realized is that the version of your code you would type if you were to do this as a generator in a language with coroutines actually doesn't* look recursive, and so I had played myself by getting the entire argument backwards. > I changed my mind; lazy semantics plus recursion doesn't give rise to a new kind of recursion. Ok, so the real issue to grok here is that this function wasn't "recursive", no matter that it looked recursive. An algorithm is recursive if it conceptually takes a large thing and breaks it down into smaller things in order to achieve some goal. If your thing is infinitely large on accident, this might never end, but the idea that there is an elusive "base case" looming in the future is a premise of recursion. The opposite of this is something which starts with something small and builds something large. You often can't even directly express (again, you can write something similar) this in a language without either coroutines or laziness (and while I don't think the language you are working with here has either, the DSL formed by the lcons macro and take function is close enough), as the function you are writing is highly unlikely to naturally terminate. Your list is something you are building up, not tearing down, so you are doing the opposite of recursion. FWIW, if you read the Wikipedia page on corecursion, which I just skimmed, it sets up a bunch of its examples using generators, as they are a natural way of expressing these kinds of algorithms in programming languages people are more likely to usr... but I no longer actually believe that the version of your code expressed with the syntax of a coroutine is "using" recursion at all (and yet, I think it "is" corecursive?) so I dunno: welcome to hell ;P.
  - kazinator 6y ago
    "To make a list of numbers starting from N, we make a list starting from N+1 and cons N onto the front". How is that not obviously recursive? If we make it a list from N to M, we can use eager evaluation, over ordinary non-tail recursion on a conventional run-time stack: 1> (defun count-from-to (n m) (cond ((> n m) nil) ((= n m) (list n)) (t (cons n (count-from-to (succ n) m))))) ;; no lcons count-from-to 2> (count-from-to 1 10) (1 2 3 4 5 6 7 8 9 10) What looks "funny" about the original is the lack of any termination test; how can you return a list of all the numbers from N+1, and then tack N onto the front? However, that doesn't require any new kind of recursion. The mathematical definition given in English at the top of my comment certainly has no issue; math uses whatever evaluation semantics is needed to make things work out, and frequently describes infinities.
    - saurik 6y ago
      Ir is just that you are working with a more general definition of recursion than the actual one: as I said, recursion isn't merely "a function which calls itself", it implies a certain problem solving strategy. Recursion is "a method of solving a problem where the solution depends on solutions to smaller instances of the same problem". If it isn't being broken down into smaller instances towards some base case--an instance small enough to solve on its own--it isn't recursion. The new function you have described is just different, because you have added the bounding into the code, and so now the function itself is solving a different problem: it includes the definition of take inside of it.
      - kazinator 6y ago
        Recursion can solve problems using larger objects than the input. For instance, a parser for telephone numbers of the form (123)-456-7890 might plausibly convert the case 1234567890 into this form, which is several characters longer, and then call itself recursively on that form. So that is to say, a recursive term-rewriting system can be used to solve a problem, and in a term-rewriting system, the path through the rewrites can involve growth as well as shrinkage. It meets the definition of solving a smaller instance of the sub problem if we take "smaller" as being, simply: "fewer steps remaining". Recursion can also divide into smaller objects which represent overlapping subdivisions of the input space, but that are together larger than the input and end up creating more work. For instance, naive Fibonacci recursion. Though, pedantically speaking, the numbers starting from N and the numbers from N+1 are sets of the same size ("countable infinity"), it's still the case that {N+1, ...} is "simpler" than {N, ...}. The latter contains all of the elements of the former, and also N, making it a proper superset, in spite of equivalent cardinality. Recursion that proceeds from a superset to a proper subset (though they be of the same cardinality) meets the definition of identifying and solving a "smaller instance", though we cannot insist that "smaller" is interpreted in terms of raw set cardinality.

by saurik 6y ago

kazinator 6y ago

It does look directly recursive Furthermore, in a lazily evaluated language, we could use the regular cons function, instead of an explicitly lazy lcons version. No coroutines are used here, only lexical closures. I changed my mind; lazy semantics plus recursion doesn't give rise to a new kind of recursion.

saurik 6y ago
> No coroutines are used here, only lexical closures. So first off, I just want to provide some clarity on the language I used, as this statement makes me think I was misunderstood: I appreciate what you typed wasn't "using a coroutine" any more than if you typed a structure and put some functions nearby in a nice and simple pattern you "used a class". I am saying the thing you typed "is" a coroutine, which is very different. I then explicitly said that what you were doing was "manually" building a coroutine, as you are in a language that doesn't use coroutines: it uses lazy execution. Like, I disagree with that sentence as what I said was you manually wrote what a compiler in a different language would have output if you could have directly used that feature, which you couldn't have because you didn't have it. > It does look directly recursive. However, that aside, you are correct here, and I noticed this a few hours ago during my tenth read of your code and it confused the hell out me, if it makes you feel any better. In particular, the thing that I realized is that the version of your code you would type if you were to do this as a generator in a language with coroutines actually doesn't* look recursive, and so I had played myself by getting the entire argument backwards. > I changed my mind; lazy semantics plus recursion doesn't give rise to a new kind of recursion. Ok, so the real issue to grok here is that this function wasn't "recursive", no matter that it looked recursive. An algorithm is recursive if it conceptually takes a large thing and breaks it down into smaller things in order to achieve some goal. If your thing is infinitely large on accident, this might never end, but the idea that there is an elusive "base case" looming in the future is a premise of recursion. The opposite of this is something which starts with something small and builds something large. You often can't even directly express (again, you can write something similar) this in a language without either coroutines or laziness (and while I don't think the language you are working with here has either, the DSL formed by the lcons macro and take function is close enough), as the function you are writing is highly unlikely to naturally terminate. Your list is something you are building up, not tearing down, so you are doing the opposite of recursion. FWIW, if you read the Wikipedia page on corecursion, which I just skimmed, it sets up a bunch of its examples using generators, as they are a natural way of expressing these kinds of algorithms in programming languages people are more likely to usr... but I no longer actually believe that the version of your code expressed with the syntax of a coroutine is "using" recursion at all (and yet, I think it "is" corecursive?) so I dunno: welcome to hell ;P.
- kazinator 6y ago
  "To make a list of numbers starting from N, we make a list starting from N+1 and cons N onto the front". How is that not obviously recursive? If we make it a list from N to M, we can use eager evaluation, over ordinary non-tail recursion on a conventional run-time stack: 1> (defun count-from-to (n m) (cond ((> n m) nil) ((= n m) (list n)) (t (cons n (count-from-to (succ n) m))))) ;; no lcons count-from-to 2> (count-from-to 1 10) (1 2 3 4 5 6 7 8 9 10) What looks "funny" about the original is the lack of any termination test; how can you return a list of all the numbers from N+1, and then tack N onto the front? However, that doesn't require any new kind of recursion. The mathematical definition given in English at the top of my comment certainly has no issue; math uses whatever evaluation semantics is needed to make things work out, and frequently describes infinities.
  - saurik 6y ago
    Ir is just that you are working with a more general definition of recursion than the actual one: as I said, recursion isn't merely "a function which calls itself", it implies a certain problem solving strategy. Recursion is "a method of solving a problem where the solution depends on solutions to smaller instances of the same problem". If it isn't being broken down into smaller instances towards some base case--an instance small enough to solve on its own--it isn't recursion. The new function you have described is just different, because you have added the bounding into the code, and so now the function itself is solving a different problem: it includes the definition of take inside of it.
    - kazinator 6y ago
      Recursion can solve problems using larger objects than the input. For instance, a parser for telephone numbers of the form (123)-456-7890 might plausibly convert the case 1234567890 into this form, which is several characters longer, and then call itself recursively on that form. So that is to say, a recursive term-rewriting system can be used to solve a problem, and in a term-rewriting system, the path through the rewrites can involve growth as well as shrinkage. It meets the definition of solving a smaller instance of the sub problem if we take "smaller" as being, simply: "fewer steps remaining". Recursion can also divide into smaller objects which represent overlapping subdivisions of the input space, but that are together larger than the input and end up creating more work. For instance, naive Fibonacci recursion. Though, pedantically speaking, the numbers starting from N and the numbers from N+1 are sets of the same size ("countable infinity"), it's still the case that {N+1, ...} is "simpler" than {N, ...}. The latter contains all of the elements of the former, and also N, making it a proper superset, in spite of equivalent cardinality. Recursion that proceeds from a superset to a proper subset (though they be of the same cardinality) meets the definition of identifying and solving a "smaller instance", though we cannot insist that "smaller" is interpreted in terms of raw set cardinality.