Dynamic scope

Now I'm confused by another aspect of JavaScript scope:

var f = function() { alert("default") }
function test(b) {
    if (b) {
        function f() { alert("shadowed") }
    }
    f()
}

Evaluate test(true), and you'll see "shadowed". Evaluate test(false), and you'll see "default". Apparently function declarations are another instance where JavaScript is not lexically scoped (in addition to this, arguments, and the behavior of references to unbound variables).

Update: Oh, I forgot to mention the with construct -- another instance of dynamic scope.

Update: Also note that this is not the same thing as the behavior of var. If we write this function instead:

var f = function() { alert("default") };
function test(b) {
    if (b) {
        var f = function() { alert("overridden") };
    }
    f()
}

Then with test(true) we still get "overridden", but with test(false) we get an error from trying to apply undefined as a function. In other words, in this example, we have normal lexical scope with hoisting.

Update: I think this settles it--it's pretty much what it looks like. In chapter 13 of ECMA-262, the dynamic semantics of a FunctionDeclaration is to create a new binding in the "variable object" (ECMA-262 terminology for an environment frame) upon evaluation of the declaration.

If you imagine an environment as a list of frames, then in a lexically scoped language, this is a statically computable list. In a language with dynamic scope, frames in the environment may be generated or mutated at runtime, so it's not statically computable. JavaScript has some of both, so there are some things you can know statically about a variable reference, and some things you can't.

Update: The saga continues... I realized that I couldn't actually derive the above example from the official ECMAScript grammar! I see that others have made this surprising discovery as well: you can't nest FunctionDeclarations beneath Statements. Furthermore, you can't begin an ExpressionStatement with a FunctionExpression. As a result, it's impossible to derive the above program.

However, in practice, JavaScript engines do appear to accept the program, and use the dynamic semantics from chapter 13 as I describe above. But for strict ECMAScript, I can't seem to produce an example. I thought I could still force the issue by placing the nested function at the top-level of the enclosing function body and conditionally returning. But I was thwarted by two more interesting phenomena. First of all, when a var declaration and a function declaration compete to bind the same identifier, the var always wins, apparently. So this always produces "default", regardless of the value of b:

function test(b) {
    var f = function() { alert("default") };
    if (!b) {
        f();
        return;
    }
    function f() { alert("overridden") }
    f()
}

Second, nested function declarations appear to be hoisted to the top of the function body. So the following example always produces "overridden":

var f = function() { alert("default") };
function test3(b) {
    if (!b) {
        f();
        return;
    }
    function f() { alert("overridden") }
    f()
}

Curious. At any rate, the behavior of popular JavaScript engines (Firefox and Rhino) seem to be a generalization of ECMAScript (by allowing FunctionDeclarations to appear nested within Statements) that is consistent with the spec (by obeying the behavior specified by section 13).

Now I need to confirm these two more properties of the language with the spec.

Dynamic languages need modules

A dynamic language starts as an implementation. And that implementation almost always includes some variation on a REPL. Look at Lisp, Scheme, Python, Ruby, JavaScript, Lua, etc. One of the things that makes these languages "dynamic" is that they're attached to some long-running process: an IDE, a user prompt, an embedding application, a web page. So these languages are simply implemented with some global table of definitions that gets updated through the lifetime of the host process. Easy enough to understand from the implementor's perspective, but what happens to the user of the embedded language?

The problem with the "top-level" (that ever-changing table of program definitions) is the creeping specter of dynamic scope. While static vs. dynamic typing may be a debate that civilization takes to its grave, the dust seems to have more or less settled on dynamic scoping. The fact is, even though many decisions a program makes must depend on its context, it's very hard to understand a program if you can't nail down its definitions.

To some degree, if a dynamic language has lambda, you can escape the top-level with a design pattern that simulates a poor man's module. The module pattern is almost always a variation of what Schemers call "left-left-lambda"--the immediate application of a function literal. Bindings inside the lambda are no longer floating in that airy and transient stratosphere of the top-level; they're nailed to the function that is being applied. And you know that function is being applied only once, because once you've created it, it's applied an discarded.

This pattern goes a long way, and if you have macros, you can create sugar to give the pattern linguistic status. But a module system it ain't.

Linking: Nothing in this pattern deals with the relationships between modules. There's no way to declare what a module's imports and exports are. In fact, if you want a module to communicate with any other modules, the top-level's poison tends to seep back in. To export a value, a lambda-module can mutate some global variable, or it can return a value--but where does the caller save the value? You can always nest these solutions within more lambda-modules, but ultimately there's a problem of infinite regress: in the end you have to have at least one special top-most module surrounding your program.

Separate development: And that's only if you have control over the whole program. If you want to create a library and share it, there needs to be some shared common framework in which people and organizations can share code without stomping on each other's invariants or polluting each other's global environments. To be sure, a built-in module system doesn't eliminate all such issues (you still need conventions for naming and registering modules within a common framework), but modules help to standardize on these issues, and they can provide helpful errors when modules step on each other's toes, rather than silently overwriting one another.

Loading: There's not much flexibility in the loading of an immediately applied function. If your language involves multiple stages of loading, the implementation may be able to be smarter about loading and linking multiple modules at once.

Scoping conveniences: Lexical scope is a widget in the programmer's UI toolkit, and for different scenarios, there are different appropriate designs. The tree shape of expressions makes the lexical scoping rule ("inner trumps outer") appropriate; it favors the local over the global. But, ignoring nested modules for the moment, modules aren't tree shaped; they're more like a global table. In a sense, all modules are peers. So when you import the same name from two different modules, which one should win? You could say that whichever you import later wins, but this is much more subtle than the obvious nesting structure of ordinary variable bindings. I find it's more helpful for the module system to give me an error if I import the same name from different sources (unless it's a diamond import). Other useful facilities are selective import, import with renaming, or import with common prefixes. These are subtle usability designs where modules differ from lambda.

Extensibility: In PLT Scheme, we've used the module system as the point for language design and extension. By allowing modules to be parameterized over their "language", we have a natural way for introducing modalities into PLT Scheme. As languages grow, these modalities are an inevitability (cf. "use strict" in Perl and ECMAScript Edition 4). Buried within pragmas or nested expressions, this makes the design of the language much harder. But within a module, bindings are sacrosanct and interactions with other modules are limited to imports and exports. This significantly cuts down on the space of possible interactions and interferences between the language's modalities. As an example, Sam Tobin-Hochstadt has made good use of this for the design of Typed Scheme, a statically typed modality of PLT Scheme that can still interact reliably with dynamically typed modules.

The unrestricted mutation of the top-level environment is a good thing thing for many purposes: interactive development, self-adjusting execution environments, etc. But it's terrible for nailing down program definitions. Modules are a way of circumscribing a portion of code and declaring it "finished". It can still be useful to have an environment where modules can be dynamically loaded and possibly even replaced, but it's critical for the language to provide the programmer with basic invariants about the definitions within a module.

All of this is stuff I wish I'd had a clearer head about earlier in the ES4 process. But I hope that, down the road, we'll consider a module system for ECMAScript.

Late and early binding

It's taken me a long time to figure out what people mean when they talk about "late binding" and "early binding." Little by little, I was beginning to get a handle on it, when Brendan showed me this Python spec which used the terms to refer to order of expression evaluation in a syntactic form! According to the spec's terminology, evaluating an expression earlier is ostensibly "early binding." This freaked me out, but Brendan reassured me that this was probably just a misuse of terminology on the part of the Pythonistas.

At any rate, as I understand them, late and early binding describe the point in the lifetime of a computer program (usually, compile-time versus runtime) at which a particular variable reference becomes dereferenced, i.e., at what point its binding is discovered. Lisp, which is dynamically scoped, doesn't dereference function arguments until runtime, based on the dynamic context. Scheme variables, by contrast, can be early bound, since all variables' bindings are based on their lexical scope. Dynamic dispatch is another instance of late binding, where method names are resolved at runtime.

Dynamic scope is generally regarded as a liability, because it completely violates abstractions, exposing programmers' choice of variable names and making them vulnerable to accidental capture. Dynamic dispatch is a somewhat more restricted form of late binding, where the programmer has finer control over what names can be overridden by unknown external parties.

Compiler writers like early binding because it's an opportunity for optimization--variable references can be compiled into direct pointer dereferences rather than map lookups. From the perspective of program design, early binding is good because it results in clearer programs that are easier to reason about. However, in certain restricted forms, late-bound variables can be useful as a way of leaving a program open to subsequent extension. This is the purpose behind dynamic dispatch, as well as implicit parameters such as in MzScheme or Haskell.

Updated javascript.plt

I've just updated my implementation of JavaScript in PLT Scheme. The latest version fixes some of the subtle ways I'd deviated from the spec with respect to variable binding. Back in the day, I was wooed into thinking that JavaScript was so similar to Scheme that I could pretty easily just compile JavaScript variable bindings directly to similar Scheme variable bindings. For the most part, I got variable hoisting (i.e., the scope of var-declarations being hoisted to the top of their nearest enclosing function body) right. But the real subtlety comes in with the with (dynamically add a computed object value to the runtime environment as a new environment frame) and eval constructs.

I almost had with right: as soon as I detect that the programmer is using with, I enter a "stupid" mode, where I synthesize an explicit runtime environment and populate it with whatever's currently in the static environment. Within the body of the with, variable lookup is performed dynamically in this runtime environment. So outside of a with, you get normal, efficient lexical scope; inside a with, you get stupid, slow, dynamic scope. My only mistake there was forgetting to make the runtime environment entries aliases to the existing variables so that mutations persist after the with-block returns.

But eval is hard: Scheme's eval doesn't have access to the lexical environment where it is called, whereas JavaScript's does. And JavaScript's eval also inherits the ambient "variable object" (ECMA-262 10.1.3), which means that eval code can create variable bindings in the caller's scope. Getting all of this right means simulating the variable object similarly to the way I simulate the runtime environment, and switching into "stupid" mode whenever I detect a potential application of eval. (The standard allows you to refuse to run eval in situations other than a "direct" call to a variable reference spelled e-v-a-l, so you don't have to treat every single function call as a potential call to eval. It's messy, but it's better than forcing you to implement a dynamic environment everywhere.)

Javascript surprises

Javascript is not a wholly unpleasant language to work in, but it has its share of surprises.

Lexical scope: Functions are first-class values, and variables declared within the var keyword are sort of lexically scoped with respect to the nesting of functions. However, despite the C-like syntax, there is no block-style scoping. This means that you can write strange-looking functions like

function f(b) {
    if (b) {
        var x = 3;
    }
    alert(x);
}

I think the meaning of this function is that the lexical scope of x is lifted to the entire function body, but if the if-branch isn't taken, x has the default undefined value. This means that in the following example:

var x = 2;
 
function g(b) {
    if (b) {
        var x = 3;
    }
    alert(x);
}

the variable x is always shadowed in the body of g, so that it displays either 3 or undefined, and never 2.

Furthermore, you can assign to variables that have not been declared with var, which is subtly necessary because of the dynamic scope of this (see below). Basically, if you assign to a variable that hasn't been declared lexically with var, the language first searches the dynamically scoped this object for a member of that name, and then up the prototype chain. Somewhat unfortunately, if it doesn't find any member of the given name, it silently generates a new global variable of that name and performs the assignment.

this is everywhere: There is always a special this variable available, but its binding is dynamically scoped. The upshot is that you can create an ordinary function that refers to this in its body, and then later assign that function as a member of an object, and the this automatically gets wired to the new container.

Bizarrely, there is a special "global" object, so that if such a function is not a member of any object, this refers to that special object; even more bizarre is that particular Javascript engines seem to be free to make that global object whatever they want. In DHTML engines it's some kind of window object or something, whereas in Rhino it might be something else (this is hearsay--I haven't tried it). Furthermore, all global variables are actually member variables of this global object.

It gets even weirder: this means that global function declarations of the form

function foo() { ... }

are really just syntactic sugar for

foo = function() { ... };

which is a declaration of a global variable, i.e., a member variable of the global object, whose value is a function. It's truly strange, but it has a sort of internal consistency, and you kind of have to admire their chutzpah.

Object system: Javascript is the only prototype-based OO language I've ever worked with, so this was all new to me. To start with, objects are essentially just associative arrays, i.e., tables mapping names to values, much like Python or Lua. But every object is also linked to a "prototype" object, and name resolution searches the chain of prototype references. This is quite different from class-based inheritance, but it does provide a kind of dynamic dispatch, so it serves similar purposes. (It can also be used to simulate class-based inheritance.) The prototype of an object is exposed via its prototype member variable, which is mutable like everything else in Javascript.

Rather than being defined in classes, constructors in Javascript are simply functions that, when called with the new operator, have their new object implicitly available via this. By convention, people usually capitalize the name of constructor functions, which makes it look like Java-style, class-based object creation. But that "class name" is in fact just an ordinary Javascript function.

for ... in: In addition to the ordinary integer-indexed for loops, Javascript has a for ... in syntax. But it's not at all what you'd expect! This special form is only used to range over the keys (i.e., member names) in an object. It has nothing to do with iterating over collections. Specifically, if you use this to try to use this form on an array, you end up iterating over all the names of the member variables of the array object (which includes the elements of the array, because they are also member variables, whose names are integers! wow). That one took some head-scratching the first time I encountered it.

Extension by mutation: It seems an industry standard form of "extension" is to mutate the prototype of an object. Lord help you if you accidentally overwrite an existing method. What, me, namespaces?

IE has "alien" types: All right, this isn't Javascript's fault. But it's annoying. In IE, the elements of the core DOM are not actually derived from the standard Object prototype, and their prototypes are not even visible. So there's no way to extend the behavior of the core DOM prototypes.

Jewels of the lambda calculus: scope

If abstraction is the grand prize-winning jewel of the lambda calculus, then scope is the first runner-up. Mitch Wand teaches his graduate students that the scoping properties of a language are one of the Four Questions we ask in order to understand its semantics ("why is this language different from all other languages?").

Scope is the first static property of any programming language. Lexical scope gives us a static context in which to understand a fragment of a program. Within the following program:

λy.λx.y

we can look at the inner portion, λx.y, and in order to understand what portion of the program gives meaning to its body, we must understand that y is bound to--i.e., will receive its runtime meaning from--the static context of the fragment that binds it, i.e., the outer binding.

The static aspects of a program are what communicate its properties to the reader, allowing the reader to understand its behavior logically, as opposed to experimentally. Scope is the property that communicates the relationships between fragments of a program, whether through arguments, module imports, or class hierarchies. Scope is the static assignment of responsibility to these units of the program for communicating dynamic information.

PLT System Facilities (Software Components): Modules

Lexical scope in general and lambda in particular go a long way towards supporting modular, separate development. As I mentioned before, PLT Scheme builds a number of first-class, module-like component systems on top of lambda. But it also contains a more primitive module system in which modules are not first-class. This serves a number of purposes.

First of all, static modules provide systematic support for packaging, compiling, and deploying code. First-class modules are flexible and expressive, but they don't have anything to say about compilation and deployment. Somewhere along the line there has to be a notion of what the compiler takes as input, and when you have separate development, you need separate deployment and ideally separate compilation.

Another critical purpose of static modules is the ability to modularize static entities in a language. In ML, for example, modules can import and export types. Scheme is of course more [ed: dynamic] than ML, but it still has its own crucial compile-time abstractions: macros. With dynamic modules, there's no straightforward way to import and export static entities like macros. A secondary benefit of static modules is that you can import all the bindings from another module at once without having to spell them all out; this is admittedly less important but still very convenient.

Finally, PLT Scheme was designed to support multiple languages. For pedagogical purposes, this has allowed them to design multiple, concentric subsets of the language tailored to the How to Design Programs curriculum. This has also facilitated language research by making it easy to design and implement new languages (by macro-compiling them to Scheme) and to research language interactions in a multi-language environment. The relevant piece of the module system is a single hook at the beginning of a module definition: the grammar of a module is an S-expression containing the symbol module, a symbol naming the module, and an S-expression indicating the language of the body:

(module foo scheme body ...)

Typically the language chosen is the special built-in language scheme, as above, or the somewhat leaner scheme/base. But the language position works by simply importing another module that implements the required macros for compiling the body. In place of scheme, you can put in a module path for any module installed on the system.

It's also possible to specify a custom reader for a PLT language so it doesn't even have to be restricted to an S-expression syntax. The initial reader allows you to specify a language with the special shebang-like #lang syntax:

#lang scheme/base
body ...

From that point on, the language's reader has access to the input stream to parse it any way it likes.

Anyone can implement a language module, which means people have developed PLT implementations of Algol, Java, ML, and JavaScript, to name a few.

Update: Added in the missing word "dynamic" above. Also, this is a better link for module paths.

Also, Sam is right in the comments: the scheme language really isn't special or built-in in any significant way. It's simply another module provided in the standard PLT collections.

Nice filesystem testing pattern

I've come across a useful pattern for unit testing with the filesystem: frequently I want to create some "sandbox" directory where I'll stick a bunch of temporary files and subdirectories for testing, and when the test is over, I want to delete the whole thing. But any intermediate files or directories I create during testing should not be deleted, because I may still need them later in the test. So only the first directory I create should be automatically deleted.

This requires two things: 1) a macro for creating a new directory and evaluating subexpressions in the context of that directory, and 2) a facility for enabling and disabling the automatic deletion of temporary directories.

(define keep-new-directories? (make-parameter #f))

(define-syntax in-new-directory
 (syntax-rules ()
   [(_ dir-e e1 e2 ...)
    (let ([dir dir-e])
      (rm-rf dir)
      (make-directory dir)
      (let ([result (parameterize ([current-directory dir]
                                   [keep-new-directories? #t])
                      e1 e2 ...)])
        (unless (keep-new-directories?)
          (rm-rf dir))
        result))]))

Another nice property of this pattern is that if I want to test my test, i.e., to inspect the files it's creating, I can temporarily disable the automatic deletion of the sandbox directory by wrapping the whole thing in a (parameterize ([keep-new-directories? #t]) ...).

Meta-conclusion: dynamic scope is useful.

The death of namespaces

As promised in my post on ECMAScript Harmony, I want to talk about the problems with the proposed namespaces feature and why I'm glad it's gone.

In ES3, one of the problems for information hiding is that the language's primary datatype is a mutable table mapping transparent strings to values. As a result, sharing an object creates abstraction hazards: anyone can view -- or even modify! -- an object's internals. Namespaces were an attempt to facilitate hidden properties by generalizing objects in a backwards-compatible way.

So objects became mutable tables mapping namespace/string pairs to values. This has precedent in Common Lisp, and it seems natural. But here's where it started going awry: JavaScript has an ill-conceived history of specifying variable scope by way of a specification construct known as the variable object: a fictional JavaScript object that serves as a rib in the lexical environment. So JavaScript variables are conceptualized as being the same thing as properties. (I'm sure I know where this came from: implementors could use the same internal mechanism to lookup properties in an object inheritance chain as for looking up variables in the environment.) So now with namespaces, variable names were not just strings but also these (namespace × string) pairs.

But namespaces were first-class values. There were even forms for qualifying variable references with a dynamically computed namespace! Lexical scope was slipping away from JavaScript as an almost-was. Even more troubling was the concept of "open namespaces." For convenience and backwards-compatibility, there has to be a reasonable default namespace for looking up unqualified variable and field references. The proposed spec allowed multiple namespaces to be given as candidates for defaults, with a particular search order. Now, variable lookup is tough enough in JavaScript. With bizarre dynamic constructs like with, lexical eval, and the global object, there can be two dimensions of lookup: up the environment and up the inheritance chain of an object. Now with default namespaces there was a third dimension of lookup. For implementors, this creates all sorts of efficiency nightmares. For language users, it would likely be a usability nightmare.

There are ways to simplify namespaces; even Common Lisp's approach is simpler that what was originally on the table for ECMAScript. But when I heard that namespaces, which had been a part of the proposed standard since before I got involved, were on the chopping block, I was thrilled. It had never even occurred to me that they might be cut! I proposed a simpler solution: if we just add gensym to the operations on property names, then we can create private, unguessable properties. No property name pairs, no extra dimension of search, just opaque names. In an OO world, this is more likely to look like new Name() than gensym(), but same difference.

The design space of continuations

I mentioned earlier that the design space for first-class continuations has a lot of historical research behind it. This list of papers on continuations up to around 2005 is a start, but by no means complete. (The history of continuations is actually pretty astoundingly far-reaching. Apparently my PhD advisor's PhD advisor was one of a number of people who independently discovered continuations in different research programs and under different guises.)

The research literature has been helpful to me in understanding the design space of control operators better, particularly because it gives me good models for reasoning, formally or informally, about control effects.

Here are some of the design questions raised by the research literature and good modeling frameworks. This isn't a complete list, and it isn't the place to cite adequately. All I'm interested in is highlighting some of the takeaways.

How much of the continuation can be captured?

Scheme's call/cc allows you to capture the "whole" continuation, up to wherever the language implementor decides is the limit. But delimited continuations make this boundary more explicit, which has a couple benefits. First, by installing a delimiter, you can prevent code that you call from capturing parts of your continuation that you want to keep private. Second, when you capture a continuation, you have a clearer picture of what you're capturing.

What elements of the continuation are captured?

The answer at first seems obvious: you capture the control context and the environment (aka scope chain). But it gets trickier when you have things like exception handlers and other information associated with the dynamic state of the control context.

What kinds of delimiters do you give to users?

In our case, we're only interested in an implicit delimiter at function boundaries. But there are a number of different designs of control delimiters.

What kinds of control-abort operators do you give to users?

Turns out there's at least one in every C-like language: return. That's probably enough for our purposes. But there are several possibilities there, too, and they can get surprisingly subtle.

Does executing a captured continuation install a new delimiter?

This is the key difference between Felleisen's F/# operators [*] and Danvy and Filinski's shift/reset operators. With the former, you capture a continuation up to the nearest delimiter, but when you invoke the captured continuation, there's no new delimiter. With the latter, a captured continuation reinstalls a new delimiter every time you invoke it.

How many times can you enter a continuation?

The most general design allows a captured continuation to be used any number of times. With "one-shot" continuations, you can only enter a continuation once. Notice that "entering a continuation" could mean a number of things: returning normally, unwinding it by throwing exceptions, or calling into it later via a captured continuation.

When do we abort the current continuation?

This one is really, really variable. There are many plausible points in the semantics where an exit can occur, and many of them lead to plausible but distinct designs.

[*] That's pronounced "eff" and "prompt" -- no relation to F#. I just noticed that!