Daily, 2010/10/04: recursion via state and "applying yourself"

Announcement items:

• A3 partners: no new e-mails; object now!
• Send e-mail NOW!!!!
• Steve assigned all others randomly to partners
• Reminder: the exam will be CLOSED BOOK but "open wiki appendix"
• Appendix is up: READ it; edit it!
• First 10 substantive edits: +1 BP!  [[well on the way!]]
  

High-level comment:

We covered recursion, which was great.. except I think I biffed the motivation for even talking about recursion through state change.  More below!

Details:

I was excited about this class section, since it's when our language becomes effectively as powerful as a real language, or at least when we discover that fact. 

For my part, the construction of recursive factorial that did not require a new expression type in the language felt compelling.  Then, we got to the "easy" part of introducing a language construct for recursion, and I felt like I lost the thread!

Here's what I would have and should have said about rec.  We're not introducing it because we need recursion.  Clearly, we can already do recursion, and that method of "doing recursion" will be our core semantics (just as up-front substitution was our core semantics for identifier binding).

That said, we'd like a convenient, efficient, easy-to-understand way to implement recursion in our interpreter.  To accomplish that, we'll build a cyclical environment, but building a cyclical environment (or any cyclical data structure) requires mutation.  That's because if there's a cycle, one part or the other needs to be built first.  Whichever part is built first cannot refer to the second part until that's built, too.

We solve this by building the environment first and then building the closure that slots into the environment.  The closure is "right" from the start (referring to the environment).  The environment becomes right when we use mutation/assignment to change the dummy value we started with to point to the closure instead.

So, our mutant solution is there to preserve the clean simplicity (and efficiency) of nested environments, not to make something possible that wasn't before.


Cheers,

Steve