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

7 Ways to Approach Soundness and Completeness

Soundness and completeness are important concepts that regularly tangle people up for some reason.  So, here's several different ways to think about them.  Choose the one that makes sense to you!

Grace for the CS1 Language Wars

We just changed the language for our intro CS course.  That change will probably obscure the underlying pedagogical change we also made for almost anyone outside UBC looking at the courses.

(Side Note: What's the pedagogical change?  From the perspective of someone who has not yet taught the course: A move toward a heavily structured approach to programming in which analysis of the features of a problem naturally leads to the process of solution.)

The language wars in intro CS courses, often called "CS1" courses, are powerful, engaging, frightening, and frequently pointless things.

So, why bother talking about them here?

Because once you start thinking about what you want in a language for your preferred CS1 pedagogy, you rapidly start throwing around words like syntax, semantics, closures, state, mutability, ...  And, understanding and slinging terms like that are part of what CPSC 311 is all about :^)

So, check out Andrew Black, Kim Bruce, and James Noble's thoughts on the syntax of an in-production CS1 language called Grace, particularly the section labeled "Block Semantics".

Grace uses eager evaluation but wants to allow programmers to introduce their own control constructs.  So.. they need to provide a simple syntax for a particular kind of expression.  Which one?

Sounds like an exam question!

Cheers,

Steve

"Little Language" for Elections

I got off topic discussing HCI-related issues in the Alaska senatorial race and valiantly connected (or tried to) that topic with our course by discussing Ka-Ping Yee's PVote, voting machine software as a concise interpreter for a ballot specification language.  I warmly recommend browsing through PVote (and the rest of Yee's work, voting-related or not).  It's a fascinating project that touches on elections, security, and languages.

Cheers,

Steve

Daily, 2010/11/10: Why Types?

Today was so exciting!  First, we finished up the (untyped, by the way) lambda calculus.  Everything's a single-argument function definition, function application, or an identifier

Then, we intro'd types.

SKIing and the Lambda Calculus

It's an amazing property of computation that we reduce all of our data (of which there is a staggering variety) to sequences of bits.

It is even more amazing that we can reduce the language of computation to a similarly lean representation.

In class, we've reduced lists, numbers, booleans, control flow operators, continuations, and recursion down to three things: single-argument function definitions, single-argument function applications, and identifiers.

We didn't get a chance to discuss the fact that we can go further.

The S, K, and I "combinators" (simple little functions) are one such representation.  Here's their definitions:

I x = x
K x y = x
S x y z = (x z) (y z)

Daily, 2010/10/18: call-by-X

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