4 ms·
> One way to define codata is by corecursion: for example CountFrom(n) = cons(n, CountFrom(n + 1)) defines CountFrom(n) to be the infinite list starting from n:
by kazinator 6y ago
> One way to define codata is by corecursion: for example
CountFrom(n) = cons(n, CountFrom(n + 1))
defines
CountFrom(n) to be the infinite list starting from n:
TXR Lisp:
1> (defun countfrom (n) (lcons n (countfrom (succ n))))
countfrom
2> (take 5 (countfrom 1))
(1 2 3 4 5)
So that's what I was doing there: codata and corecursion. Who woulda figured?
It makes sense to have some terminology, I suppose. The definition of the list is clearly recursive. But the implementation doesn't actually recurse: it's not the case that countfrom calls itself, in spite of superficial appearances. A closure produced inside countfrom is (potentially) invoked, which happens after countfrom has terminated. If that happens, that closure then calls countfrom.
- JadeNB 6y ago> So that's what I was doing there: codata and corecursion. Who woulda figured? I can't quite make out the tone of it, and guessing tone is a fool's game, so I'll take it literally. I think that this is one thing that people miss who complain about the proliferation of mathematical terminology in modern functional programming. I see no reason to think that you're such a person, so, just to be clear, when I say 'you' below, I am addressing only a hypothetical such person, not actually you. No-one wants to force you to think in terms of codata, coinduction, and corecursion if you're comfortable with your mental model of what lazy lists are doing; the point is rather to allow you to think in those terms—to leverage the vast theoretical power that already exists in the mathematics, rather than requiring it to be re-discovered in an ad hoc way.
- saurik 6y agoAnother 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 agoIt 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.