- A#1 feedback should have been mailed; A#1 grades on Vista (both raw and actual)
- Go to next tutorial (and you should have gone to the last) or A#2 may be VERY HARD
- Practice Midterm out on Vista
We hit our second big design axis today: static vs. dynamic scope. As with lazy vs. eager evaluation, we'll dive much deeper into this axis once functions are first-class, but we've already seen how the choice can change the semantics of a program (with freevar). More generally, the contrast between static and dynamic properties of programs will come up again and again, not just in this course but in many other courses and in your CS career. (And life. After all, you are a dynamic expression of the static code in your DNA!)
On the practical side: I'm going to try to work from more pre-written code. Today (and last class), we delayed some key points too late in class. (OK, 1.5 minutes after the end!) I'll try to skip past the inessentials in the future.
Details:
Quick summary of what we did: patched up our fundefs interpreter and then optimized our interpreter by deferring substitutions.
And the fun stuff:
(1) I said that we didn't really asymptotically improve our interpreter's performance because we're using a simple data structure to keep track of bindings. You can probably imagine a more complex data structure that will yield better performance. But.. also read up on Section 3.5 of the book. If we replace identifiers with numbers (De Bruijn indices, that is), is there a quick way we could find the identifier we're looking for in an environment?
(2) Nicholas made a good point after class (easier to follow if you've taken CPSC 213 and 313):
One (class of) language with something like dynamic scoping is assembly. If your function looks in register R3, it finds whatever value was most recently placed there during execution, regardless of where in the program text that assignment occurred. If you've programmed in assembly you know both how painful this is and the careful stack discipline required to work around it. (Indeed, stack discipline allows us to reestablish something like (not very hierarchical) static scoping.)
However, this isn't really dynamic scoping but dynamic (changing) state. We can tell because a change to a register can "flow back" from a function call to its caller. That can't happen to an identifier binding in dynamic scoping.
Something in assembly that is dynamically scoped is the stack pointer. Its value is not dependent on code's location in the program text but on the dynamic context of a function call, just like an identifier with dynamic scoping takes on its most recent binding, where "most recent" means closest in the calling context. The stack pointer's value doesn't "flow back" from a called function; indeed, restoring the stack pointer after a call is central to stack discipline!
In fact, everything accessed relative to the stack pointer is dynamically scoped.. such as parameters. In every language you've used, parameters are dynamically scoped: they take their values from calling code, which may be unpredictably distant from the function's definition in the program text. (As with the "static scoping" stack discipline gives us, this is not very hierarchical dynamic scoping. Parameter values only come from the immediate calling context.)
That brings us to a fascinating point in the book: parameters let us introduce a simple, clear type of dynamic scoping. The function designer gets to decide and name (with a parameter list) just what information the function accepts dynamically. Everything else is statically scoped to avoid unintended consequences of distant code.
Cheers,
Steve
No comments:
Post a Comment