Thursday, August 29, 2013

A Quibble in Advance

I'm still working through Shriram's new edition of PLAI.  

So far, I like it a lot!  I think it's a bit light on the "A for Application" of PLAI and on big picture discussion, but that's exactly what's natural to embellish in class.

However, there's one small point so far that I quibble with.  I raised this with Shriram, and I think he may agree with me.  In case he doesn't or it's not revised by the time you all get there, here's my quibble. 

WARNING: this may not make much sense until you've studied the concepts in the course!

Point number 2 in Section 8.1.8 is flawed; it discusses the relationship of the stack to lexical and dynamic scoping.

There are three "flows through the program" being discussed with two names. One is the flow followed by lexical scope, which we can name "lexical".  One is the flow followed by changes to the store, which we can name "persistent", but which is obviously related to the dynamic behaviour of the program, unlike lexical flow.  The third is the flow followed by dynamic scope, which is also obviously related to the dynamic behaviour of the program but is different from persistent flow.  I'm going to name it "control flow".

Before I go further, I'll mention that Shriram brought up tail-call optimization (TCO) in response to my discussion. That's where we effectively eliminate the stack frame for a function whose last action (dynamically) is to call a function.  That function's return will be the calling function's return.  Nothing more of the calling function is ever needed.  So, why keep it around?  The tail call effectively becomes a goto to the other function, and we save memory on the stack, which may have profound consequences on performance of the program.

TCO is one of the Great Ideas in Computer Science.  Shriram is very smart (smarter than me) and probably right to bring it up.  Nonetheless, I'm going to discard TCO as a red herring.  It has nothing to do with the semantics of the situation at hand.  Henceforth, I assume no TCO.

(Note for educational purposes: A big part of the reason Shriram mentioned TCO was because what I'm about to say will pollute your mind with the idea that the stack/continuation records "where a program has been", whereas it's more accurate and useful to think of it as recording "where a program will go".  Resist this pollution.  Despite this, I still think my argument stands.)

The text says that the stack matches the lexical flow, but it does not.  It is true that in a language with activation records stored on the stack, the local variables of the current function call are typically stored in that activation record.  However, it's also true that a language with dynamic scope could implement its scope by searching down the stack of activation records until it reaches the first occurrence of the identifier sought. A language with lexical scope cannot use the stack to implement scoping in such a straightforward way.  In other words, the stack (ignoring TCO) precisely matches dynamic scope and therefore control flow.  It neither matches lexical flow (e.g., the stack frame above this one may be from far away in the program or may be from the same program point but a different instantiation of it) nor persistent flow (in that the stack frame pops as functions terminate while changes to the store are never undone, even in the case of invoking a continuation).

This confusion is especially problematic in the context of a critique of C's conflation of two of these scopes.

Here's a code illustration of some of the ideas:

(let ([f (lambda (x) (begin (set-box! y (+ (unbox y) x)) y))])
  (let ([z (let ([y (box 0)]) (f 1)))])
    ...))

Under dynamic scoping rules, y is not available at the ellipsis.  So, replacing ...
with y or (f 1) would both fail.  However, the store location bound by (box 0) is
still available.  So, replacing ... with (unbox z) works fine.  In other words, these two different "bindings" follow different contours through the dynamic evaluation of the program.

Cheers,

Steve