One big idea we touched on briefly in class is that identifier binding—which means function application now that we've compiled withs away—is fundamental to several of the design axes we've considered in programming languages.
Clearly, call-by-value and call-by-reference are two different ways to manage binding function parameters during application. However, both of these, also contrast with lazy evaluation.
Two other names for lazy evaluation are call-by-name and call-by-need.
In call-by-name semantics, binding a parameter just gives a name for the expression supplied to the function (well, the expression closure, anyway). Any use of the name is replaced by the expression. That's lazy evaluation without caching.
In call-by-need semantics, the expression bound to a parameter is only evaluated (and subsequently stored and used as a value) if it's needed at some later point. That's lazy evaluation with caching.
Neither of these corresponds to call-by-reference or call-by-value (although we can think of call-by-value as being like call-by-need except that we artificially "need" the value right away).
Cheers,
Steve
Wednesday, October 20, 2010
Friday, October 15, 2010
Daily, 2010/10/15: mutable state and scope vs. extent
I'm going to make this short, because I've been laggard with my dailies, and the practical solution is to make them quicker to post!
Today, we finished up our implementation of mutable state using boxes. We touched again on the crucial idea that state "threads" through evaluation in a very different way from environments, in particular in a dynamic fashion. Mutable state's dynamic nature makes it both useful and dangerous to use.
In fact, it's even harder to understand where state changes come from than identifier bindings in dynamic scoping. That's because an identifier instance's binding in dynamic scope must be present in the dynamic context of the instance, the "call stack" in machine-oriented terminology. However, state changes can propagate from outside the dynamic context.
Our tree-labeling example illustrated that. Consider this tree:
When we label it, we'll make a recursive call on the left branch. The recursive call sets the leaf's contents to 1 and updates the counter's state. That function call is then over and gone: no longer "on the call stack", no longer part of the dynamic context of the program's evaluation. Then, we make a recursive call to label the right branch, and the label is 2 (not 1) because of changes that occurred in a function that's already over and done with.
The other important idea we discussed stems from the dynamic, threaded nature of the store. Identifiers have static scope (which we want), but the contents of the store have dynamic extent because they can escape the static scope in which they are created.
In our interpreter, we have no problem because we never remove anything from the store. So, values in the store have unlimited extent.
In C and C++, memory that is allocated "on the stack" (generally space associated with local variables of functions) is reclaimed when the function that allocated it terminates, at the same moment that the variable's name also goes out of scope.
This can cause serious problems with code like this from class:
This code compiles and may even run correctly, but it may also cause immediate or distant errors, depending on the structure of the program in which it is called and the implementation details of the compiler and machine used. Yuck!
(My version of gcc warns me about returning &y. Good for it! But it gives no warning when I change return &y; to return next(&y); or even if I call a different function expecting an int*.)
Lastly, I made a rather muddled point about whether we store values or store locations in the environment. I may defer discussion of this to tutorial on Tuesday.
Cheers,
Steve
Today, we finished up our implementation of mutable state using boxes. We touched again on the crucial idea that state "threads" through evaluation in a very different way from environments, in particular in a dynamic fashion. Mutable state's dynamic nature makes it both useful and dangerous to use.
In fact, it's even harder to understand where state changes come from than identifier bindings in dynamic scoping. That's because an identifier instance's binding in dynamic scope must be present in the dynamic context of the instance, the "call stack" in machine-oriented terminology. However, state changes can propagate from outside the dynamic context.
Our tree-labeling example illustrated that. Consider this tree:
(node (leaf 0) (leaf 0))
When we label it, we'll make a recursive call on the left branch. The recursive call sets the leaf's contents to 1 and updates the counter's state. That function call is then over and gone: no longer "on the call stack", no longer part of the dynamic context of the program's evaluation. Then, we make a recursive call to label the right branch, and the label is 2 (not 1) because of changes that occurred in a function that's already over and done with.
The other important idea we discussed stems from the dynamic, threaded nature of the store. Identifiers have static scope (which we want), but the contents of the store have dynamic extent because they can escape the static scope in which they are created.
In our interpreter, we have no problem because we never remove anything from the store. So, values in the store have unlimited extent.
In C and C++, memory that is allocated "on the stack" (generally space associated with local variables of functions) is reclaimed when the function that allocated it terminates, at the same moment that the variable's name also goes out of scope.
This can cause serious problems with code like this from class:
int * next(int * x)
{
int y = *x + 1;
return &y;
}
This code compiles and may even run correctly, but it may also cause immediate or distant errors, depending on the structure of the program in which it is called and the implementation details of the compiler and machine used. Yuck!
(My version of gcc warns me about returning &y. Good for it! But it gives no warning when I change return &y; to return next(&y); or even if I call a different function expecting an int*.)
Lastly, I made a rather muddled point about whether we store values or store locations in the environment. I may defer discussion of this to tutorial on Tuesday.
Cheers,
Steve
Tuesday, October 5, 2010
Daily, 2010/10/04: recursion via state and "applying yourself"
Announcement items:
We covered recursion, which was great.. except I think I biffed the motivation for even talking about recursion through state change. More below!
Details:
- 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!]]
We covered recursion, which was great.. except I think I biffed the motivation for even talking about recursion through state change. More below!
Details:
Daily, 2010/10/01: caching and high-level thoughts
Announcement items:
Up to now, we've been moving at a rapid clip. Today, we savoured caching and reflected on the term.
On the latter: we started class by discussing tradeoffs along (and sample languages lying at different points on) the static and dynamic typing design axis. Our familiarity with the notion of static vs. dynamic scope already makes a fabulous entry to deep understanding of the discussion of static and dynamic typing. (We framed the conversation in terms of some work a friend of mine at UW is doing, which I'll blog about later.)
Details:
- A#3 pairings: 12 people still need partners [list elided]
- Steve will assign partners after Monday's class if not already chosen
- Study session this weekend thanks to Ray: Sun 1-4; Steve should be there; +1BP to all!
- Reminder: the exam will be CLOSED BOOK but "open wiki appendix"
- Appendix is up: edit it!
- First 10 substantive edits: +1 BP!
Up to now, we've been moving at a rapid clip. Today, we savoured caching and reflected on the term.
On the latter: we started class by discussing tradeoffs along (and sample languages lying at different points on) the static and dynamic typing design axis. Our familiarity with the notion of static vs. dynamic scope already makes a fabulous entry to deep understanding of the discussion of static and dynamic typing. (We framed the conversation in terms of some work a friend of mine at UW is doing, which I'll blog about later.)
Details:
Friday, October 1, 2010
Braces in Python? No way.
In Python, whitespace is significant and used to delineate code blocks. Many other languages use braces (or BEGIN and END or some other matched pair of tokens). Will Python ever have braces?
Hat-tip to PEP 3099, a fascinating laundry list of Python language design ideas deemed so bad they're non-starters.
Cheers,
Steve
Take a close look. Hilarious.cascade:~> python Python 2.4.6 (#1, Dec 13 2009, 23:45:11) [C] on sunos5 Type "help", "copyright", "credits" or "license" for more information. >>> from __future__ import braces File "<stdin>", line 1 SyntaxError: not a chance >>>
Hat-tip to PEP 3099, a fascinating laundry list of Python language design ideas deemed so bad they're non-starters.
Cheers,
Steve
Subscribe to:
Posts (Atom)