TypeScript: Physical Code Organisation

February 21, 2015 1 comment

When I first started reading about TypeScript, I had one main concern: how am I going to make this work with the weird mix of modular code and old-school JS libraries in my existing codebase?

The features of the language itself are very well covered. I found various great introductions (and now there’s the awesome official Handbook), but they all seemed to gloss over certain fundamental questions I had about the physical organisation of code. So I’m going to go through the basics here and try to answer those questions as I go.

Modularity in the Browser

Let’s get the the controversial opinionated bit out of the way. (Spoiler: turns out my opinions on this are irrelevant to TS!)

How should you physically transport your JS into your user’s browser? There are those who suggest you should asynchronously load individual module files on the fly. I am not one of them. Stitch your files together into one big chunk, minify it, let the web server gzip it, let the browser cache it. This means it gets onto the user’s machine in a single request, typically once, like any other binary resource.

The exception would be during the development process: the edit-refresh-debug cycle. Clearly it shouldn’t be minified here. Nor should it be cached by the browser (load the latest version, ya varmint!) And ideally it shouldn’t be one big file, though that’s not as much of an issue as it was a few years ago (even as late as version 9, IE used to crash if you tried to debug large files, and Chrome would get confused about breakpoints).

But I’ve found it pretty straightforward to put a conditional flag in my applications, a ?DEBUG mode, which controls how it serves up the source. In production it’s the fast, small version. In ?DEBUG, it’s the convenient version (separate files).

In neither situation does it need to be anything other than CommonJS. For about four years now I’ve been using CommonJS-style require/exports as my module API in the browser, and it’s the smoothest, best-of-all-worlds experience I could wish for.

So what’s the point of AMD? Apparently “… debugging multiple files that are concatenated into one file [has] practical weaknesses. Those weaknesses may be addressed in browser tooling some day…” In my house they were addressed in the browser in about 2011.

But anyway… deep breath, calms down… it turns out that TypeScript doesn’t care how you do this. It turns us all into Lilliputians arguing over which way up a boiled egg must be eaten.

The kinds of file in TypeScript

In TS, modules and physical files are not necessarily the same thing. If you want to work that way, you can. You can mix and match. So however you ended up with your codebase, TS can probably handle it.

If a TS file just contains things like:

var x = 5;
function f() {
    return x;
}

Then the compiler will output the same thing (exactly the same thing, in that example). You can start to make it modular (in a sense) without splitting into multiple files:

module MyStuff {
    var x = 5;
    export function f() {
        return x;
    }
}

var y = MyStuff.f();

That makes an (or extends an existing) object called MyStuff with one property, f, because I prefixed it with export. Modules can nest. So just as in JavaScript there’s one big global namespace that your source contributes properties to, but you can achieve modularity by using objects to contain related things.

You can at this point roll your own pattern: write lots of separate files in the above style, each file being responsible for wrapping its code in a named module, then pass them to the TS compiler and stitch the result into one file.

Now try using export at the top level in your file:

var x = 5;
export function f() {
    return x;
}

The compiler will complain that you haven’t told it what module system you want to use. You tell it with the flag --module commonjs (or --module amd if you’re crazy). Now it works and does exactly what you’d expect as a user of your chosen module system.

But what does this mean in terms of the static type system of TS and so on? It means that this particular file no longer contributes any properties to the global namespace. By just using the export prefix at the top level, you converted it into what TS calls an external module.

In order to make use of it from another module, you need to require it:

import myModule = require("super-modules/my-module");

(Subsequent versions of TS will add more flexible ways to write this, based on ES6.)

Nagging question that can’t be glossed over: What happens to the string "super-modules/my-module"? How is it interpreted? In the output JS it’s easy: it is just kept exactly as it is. So your module system better understand it. But the compiler also wants to find a TS file at compile time, to provide type information for the myModule variable.

Suppose the importing module is saved at the location:

somewhere/awesome-code/not-so-much/domestic/toaster.ts

The compiler will try these paths, in this order, until one exists:

  • somewhere/awesome-code/not-so-much/domestic/super-modules/my-module.ts
  • somewhere/awesome-code/not-so-much/super-modules/my-module.ts
  • somewhere/awesome-code/super-modules/my-module.ts
  • somewhere/super-modules/my-module.ts

i.e. it searches up the tree until it runs out of parent directories. (It will also accept a file with the extension .d.ts, or it can be “tricked” into not searching at all, but we’ll get to that later).

This is a little different to node’s take on CommonJS, where you’d only get that behaviour if your import path started with ./ – otherwise it inserts node_modules in the middle. But this doesn’t matter, as we’ll see.

One advantage of external modules over the first pattern we tried is that it avoids name clashes. Every module decides what name it will use to “mount” modules into its own namespace. Also note that by importing an external module in this way, your module also becomes external. Nothing you declare globally will actually end up as properties of the global object (e.g. window) any more.

So we have two kinds of file: external modules, and what I’m going to call plain files. The latter just pollute the global namespace with whatever you define in them. The compiler classifies all files as plain files unless they make use of import or export at the top level.

How do you call JavaScript from TypeScript?

No need to explain why this is an important question, I guess. The first thing to note is that widely-used JS libraries are packaged in various ways, many of them having longer histories than any popular JS module systems.

What if you’re dealing with something like jQuery and in your own JS you’ve been blithely assuming that $ exists globally? What you’re wishing for is that someone would rewrite jQuery as a plain TS file that says something like:

function $(selector: any) {
    // Um...
}

No use of export, see? It’s a little trickier than that in reality because $ is not just a function; it has properties of its own. Don’t worry – TS has ways to declare that.

Of course, no one can be bothered to rewrite jQuery in TS and fortunately they don’t have to. TypeScript supports ambient declarations, which are prefixed with the keyword declare like this:

declare var x: number;
declare function f(): number; 

These tell the compiler that somehow arrangements will be made such that the global namespace has properties x and f with those particular shapes. Just trust that they’ll be there, Mr Compiler, and don’t ask any questions. In fact the compiler won’t generate any output code for ambient declarations. (If you’re familiar with the old world of C, think header files, prototypes and extern).

Note that I don’t initialise x or provide a body for f, which would not be allowed; as a result the compiler cannot infer their types. To make the declarations be worth a damn, I specify the type number where necessary.

Finally, you can make sure that a file contains only ambient declarations by naming it with the extension .d.ts. That way, you can tell at a glance whether a file emits code. Your linking process (whatever it is) never needs to know about these declaration files. (Again, by analogy to C, these are header files, except the compiler bans them from defining anything. They can only declare.)

(In case you’re panicking at this point, it isn’t necessary to write your own declarations for jQuery, or for many other libraries (whether in the browser or Node). See DefinitelyTyped for tons of already-written ones.)

What if third party code does use a module system such as CommonJS? For example, if you’re using TS in Node and you want to say:

import path = require("path");

You have a couple of options. The first, and least popular as far as I can tell, is to have a file called path.d.ts that you put somewhere so it can be found by the compiler’s searching algorithm. Inside that file you’d have declarations such as:

export declare function join(...path: string[]): string;

The other option is that you have a file called path.d.ts that you put anywhere you like, as long as you give it to the TS compiler to read. In terms of modules it will be a plain file, not an external module. So it can declare anything you want. But somewhere in it, you write a peculiar module declaration:

declare module "path" {
    export function join(...path: string[]): string;
}

Note how the module name is given as a quoted string. This tells the compiler: if anyone tries to import "path", use this module as the imported type structure. It effectively overrides the searching algorithm. This is by far the most popular approach.

Reference comments

In some TS code you’ll see comments at the top of the file like this:

///<reference path="something/blah.d.ts" />

This simply tells the compiler to add that file (specified relative to the containing directory of the current file) to the set of files it is compiling. It’s like a crummy substitute for project files. In some near-future version of TS the compiler will look for a tsconfig.json in the current directory, which will act as a true project file (the superb TypeStrong plugin for the Atom editor already reads and writes the proposed format).

In Visual Studio projects, just adding a .ts file to a project is sufficient to get the compiler to read it. The only reason nowadays to use reference comments is to impose an order in which declarations are read by the compiler, as TypeScript’s approach to overloading depends on the order in which declarations appear.

DefinitelyTyped and tsd

If you install node and then (with appropriate permissions) say:

npm install -g tsd

You’ll get a command-line tool that will find, and optionally download, type definition files for you. e.g.

tsd query knockout

Or if you actually want to download it:

tsd query knockout --action install

This will just write a single file at typings/knockout/knockout.d.ts relative to the current directory. You can also add the option --save:

tsd query knockout --action install --save

That will make it save a file called tsd.json recording the precise versions of what you’ve downloaded. They’re all coming from the same github repository, so they are versioned by changeset.

Migrating

I uhmm-ed and ahhh-ed for a while trying to decide what approach to take with my existing JS code. Should I write type declarations and only write brand new code in TS? Should I convert the most “actively developed” existing JS into TS?

The apparent dilemma stems from the way that .d.ts files let you describe a module without rewriting it, and “rewriting” sounds risky.

But it turned out, in my experience, that this is a false dilemma. The “rewriting” necessary to make a JS file into a TS file is

  1. Not that risky, as most of the actually code flow is completely unmodified. You’re mostly just declaring interfaces, and adding types to the variable names wherever they’re introduced.
  2. Phenomenally, indescribably worth the effort. By putting the types right in the code, the TS compiler helps you ensure that everything is consistent. Contrast this with the external .d.ts which the compiler has to trust is an accurate description. A .d.ts is like a promise from a politician.

In the end, I decided that the maximum benefit would come from rewriting two kinds of existing JS:

  • Anything where we have a lot of churn.
  • Anything quite fundamental that lots of other modules depend on, even if it’s not churning all that much.

You may come to a different conclusion, but this is working out great for me so far. Now when someone on the team has to write something new, they do it in TS and they have plenty of existing code in TS to act as their ecosystem.

I think that’s everything. What have I missed?

Categories: Uncategorized Tags:

Knockout.Clear: Fully automatic cleanup in KnockoutJS 3.3

February 21, 2015 Leave a comment

Note: This is the background discussion to a library called knockout.clear.

Introduction

Among the many libraries that try to help us manage the complexity of responsive web UIs, KnockoutJS takes a unique approach that ultimately relies on the classic observer pattern, but with the twist that it can automatically detect dependencies and do all subscribing for you. If you take full advantage of this, you end up with a pattern I call “eventless programming”, a concept which I explored in depth a while back by rebooting it in C#.

The fundamental problem with the Observer pattern

The observer pattern suffers from a problem known as the lapsed listener. In short, if thing A is dependent on thing B, the lifetime of A must be greater than or equal to the lifetime of B, because B is holding a reference to A on its list of observers. This means that if B lasts a very long time (say, forever), then A will too. The end result can be indistinguishable from a memory leak – the very thing that garbage collection is supposed to solve, dagnabbit.

When you are explicitly, manually writing code to subscribe, this is not a surprise: you wrote code to put something on a list, so you must write code to take it off the list. It’s still a pain, but it’s unsurprising.

Knockout’s surprising behaviour

On the contrary, in Knockout you don’t have to write that code. Give an observable containing a string, you can define an observable that contains the string in brackets:

var stringInBrackets = ko.computed(() => "[" + str() + "]);

Without you needing to say so, stringInBrackets has been silently placed on str‘s list of observers (called “subscribers” in Knockout), so when str changes, stringInBrackets gets recomputed. But what if str lives forever whereas stringInBrackets is an ephemeral bit of fluff that you cook up temporarily and then discard? Then you have a problem. And what’s worse, a counterintuitive one. It looks like I’m just getting the value of something. Why should that other thing stop my thing from getting cleaned up?

To solve it, you have to put this somewhere:

stringInBrackets.dispose();

When should you do that? When you are never going to need stringInBrackets again. This sounds easier to figure out than it sometimes is. In simple cases, it’s when you get rid of the DOM node that binds to it. But sometimes that’s only a temporary situation and you’ll later rebind it to another DOM node; if you’ve disposed it, it won’t work anymore.

Essentially, it’s the old problem of figuring out a hierarchical pattern of ownership, and making sure you don’t dispose too early, or not at all. Garbage collection is suppose to avoid this. Where you have the dispose pattern, you don’t have the benefits of GC.

Given this, it’s understandable that critics of Knockout sometimes accuse it of replacing one complexity problem with another.

Problem solved (mostly)

But in Knockout 3.2, an interesting new feature was added. We can change our code to say:

var stringInBrackets = ko.pureComputed(() => "[" + str() + "]);

Now when stringInBrackets is first created, it is asleep. Only when it gets its own first subscribe does it execute the evaluator function and become a subscriber to str, transitioning to being awake. Best of all, when stringInBrackets loses its final subscriber, it goes back to sleep, so it unsubscribes from str. Note that it can switch between the asleep/awake states as many times as required; this is in contrast to being disposed, which is a one-way street.

This makes all the difference in the world. Well-behaved UI bindings will take care of properly unsubscribing, which means that if your view model consists only of plain observables and pureComputeds you can wave goodbye to the lapsed listener problem!

Except…

… there’s a handy little trick you may have stumbled upon. I call it the “orphan computed”. It looks like this:

ko.computed(() => {
    items().forEach(item => {
        // do something with each item...
    });
});

It looks weird at first. It’s an observable that always has the value undefined. (In TypeScript, it’s of type void). And therefore nothing observes it; after all, what would be the point? So why do we need? Because of its side-effects. It’s not a pure function that returns a value. It changes the state of other things. An example would be that it makes minimal updates to another structure (e.g. grouped items).

If you can live without such chicanery you have nothing to worry about. But realistically, side-effects are very handy. There’s a very important example on the Knockout wiki that shows how to automatically unwrap promises, bridging the synchronous and asynchronous worlds, but internally it uses an orphan computed.

Can we switch these to using pureComputed?

ko.pureComputed(() => {
    items().forEach(item => {
        // do something with each item...
    });
});

In a word: no. The name itself is a clue: pure functions don’t have side-effects. But it’s really not the side-effects that are the problem; it’s the fact that its an orphan. The pureComputed will begin in the asleep state. As nothing ever asks for its value, it never wakes up, so never executes its evaluator at all.

So pureComputed, which promised so much, would seem to be a bust. But hold your horses, my fine friend. What’s that I hear coming over the hill like so many tedious metaphors? It’s our old friend lateral thinking!

In many situations, the solution is simple: don’t make it an orphan. Make the view observe its value, and do nothing with it. You can do this with a trivial binding, which I call execute:

ko.bindingHandlers.execute = {
    init: function() {
        return { 'controlsDescendantBindings': true };
    },
    update: function (element, valueAccessor) {
        // Unwrap recursively - so binding can be to an array, etc.
        ko.toJS(valueAccessor());
    }
};
ko.virtualElements.allowedBindings.execute = true;

You can use it like any other binding in your template. If you use a comment binding, it will make no difference at all to the DOM structure:

<!-- ko execute: mySideEffects --><!-- /ko -->

You can give it any pureComputed (or an array of them) that you want to keep awake. It’s the easy-to-understand, kinda-hacky way to keep a pureComputed awake so you can enjoy its side effects. A lot of the time, this gets you where you want to be, and doesn’t involve any extra weird concepts. It’s just more of the same, and it’s very easy to get right.

An alternative for more demanding scenarios

With the arrival of Knockout 3.3 we get a subtle enhancement that is another game-changer.

An observable can emit other events besides change (which it emits to notify of its value changing). In 3.3 pureComputed now emits awake and asleep events, as described in issue #1576, so we can react to its state changing. I know, it doesn’t sound that earth-shattering at first, but we can use it to build a new utility, which I’ve taken to calling ko.execute.

Here it is in a simplified form:

ko.execute = function(pureComputed, evaluator, thisObj) {

    function wake() {
        if (!disposable) {
            disposable = ko.computed(function() {
                evaluator.call(thisObj);
            }
        }
    }

    var disposable;
    pureComputed.subscribe(wake, null, "awake");
    pureComputed.subscribe(function() {
        if (disposable) {
            disposable.dispose();
            disposable = null;
        }
    }, null, "asleep");
}

You use it to make orphans, just like you used to with ko.computed. The difference is that rather than having to remember to dispose at exactly the right time, instead you pass it a pureComputed which will keep your orphan awake:

ko.execute(stringInBrackets, () => {
    items().forEach(item => {
        // do something with each item...
    });
});

It’s an alternative to the execute binding where, instead of referring to your side-effector from a binding, you associate it with something else to which you’re already binding. I’m going to call the first argument to execute the nanny, because it wakes your orphan up and puts it to sleep again.

But it has two limitations:

  • The nanny must be a pureComputed. This is a slight pain; in Knockout 3.3 ordinary observables don’t fire events to tell you when they transition between asleep and awake.
  • Your ko.execute‘s evaluator function must not depend on its nanny.

The second restriction is perhaps surprising, but think about it: your orphan will stay awake if there are any subscriptions to its nanny. If the orphan itself subscribes to the nanny, it will keep itself awake, and it will be no different to a plain ko.computed.

The full implementation of ko.execute, which can be found here, checks for both these conditions, making it impossible to use it incorrectly without finding out.

Using ko.unpromise to tame your asynchronous calls

Now we can re-examine that important use-case I mentioned earlier, involving asynchronous calls. The Knockout wiki gives a simple example implementation:

function asyncComputed(evaluator, owner) {
    var result = ko.observable();

    ko.computed(function() {
        evaluator.call(owner).done(result);
    });

    return result;
}

To make it work with modern standard-conforming promise libraries (as well as jQuery’s almost-promises) the done should be changed to then. But also we need to eliminate that ko.computed:

function asyncComputed(evaluator, owner) {
    var result = ko.observable();
    var wrapper = ko.pureComputed(result);

    ko.execute(wrapper, function() {
        evaluator.call(owner).done(result);
    });

    return wrapper;
}

See how it’s done? We dress up the result in pureComputed clothes, and that’s what we return, so our caller will be able to depend on it and so wake it up. And internally, we use that same pureComputed to be the “nanny” of our ko.execute, so it will wake up in sync with the nanny. When we get a result from the evaluator function, we poke it into the result observable.

Note how we obey the rules of ko.execute: we pass it a pureComputed as the first argument, and the second argument is an evaluator function that returns nothing and does not depend on the first argument.

Introducing knockout.clear

These few simple facilities combine to form a framework in which you can use Knockout without ever needing to dispose anything manually. Instead of your observables transitioning from alive to dead (or disposed), which is a one-way street, they are now able to transition between asleep and awake as necessary. When they are asleep, they are potentially garbage-collectable, not kept alive by being a lingering subscriber.

I’ve put them together in a very small library: knockout.clear

Let me know if you find it useful!

Categories: Uncategorized Tags:

TypeScript 1.5(?) – Async functions

February 1, 2015 4 comments

I realise that I’m in danger of writing the same blog post about once a year, and I am definitely going to start making notes on my experiences using TypeScript generally, now that I’m using it on an industrial scale (around 40,000 lines converted from JavaScript in the last month or so, and the latest features in 1.4 have taken it to a new level of brilliance).

But the fact is, we’re getting tantalisingly close to my holy grail of convenient async programming and static typing in one marvellous open source package, on JavaScript-enabled platforms. If you get TypeScript’s source:

git clone https://github.com/Microsoft/TypeScript.git
cd TypeScript

And then switch to the prototypeAsync branch:

git checkout prototypeAsync

And do the usual steps to build the compiler:

npm install -g jake
npm install
jake local 

You now have a TypeScript 1.5-ish compiler that you can run with:

node built/local/tsc.js -t ES5 my-code.ts

The -t ES5 flag is important because for the async code generation the compiler otherwise assumes that you’re targeting ES6, which (as of now, in browsers and mainstream node) you probably aren’t.

And then things are very straightforward (assuming you have a promisified API to call):

    async function startup() {

        if (!await fs.exists(metabasePath)) {
            await fs.mkdir(metabasePath);
        }
        if (!await fs.exists(coverartPath)) {
            fs.mkdir(coverartPath);
        }

        console.log("Loading metabase...");
        var metabaseJson: string;
        try {
            metabaseJson = await fs.readFile(metabaseFile, 'utf8');
        } catch (x) {
            console.log("No existing metabase found");
        }

        // and so on...

This corresponds very closely to previous uses of yield (such as this), but without the need to manually wrap the function in a helper that makes a promise out of a generator.

As explained in the ES7 proposal the feature can be described in exactly those terms, and sure enough the TypeScript compiler structures its output as a function that makes a generator, wrapped in a function that turns a generator into a promise.

This of course made me assume that ES6 generator syntax would also be implemented, but it’s not yet. But no matter! As I previously demonstrated with C#, if a generator has been wrapped in a promise, we can wrap it back in a generator.

To keep the example short and sweet, I’m going to skip three details:

  • exception handling (which is really no different to returning values)
  • passing values into the generator so they are “returned” from the next use of yield (similarly, passing in an Error so it will be thrown out of yield)
  • returning a value at the end of the generator.

The first two are just more of the same, but the last one turned out to be technically tricky and I suspect is impossible. It’s a quirky and non-essential feature of ES6 generators anyway.

To start with I need type declarations for Promise and also (for reasons that will become clear) Thenable, so I grabbed es6-promise.d.ts from DefinitelyTyped.

Then we write a function, generator that accepts a function and returns a generator object (albeit a simplified one that only has the next method):

    function generator<TYields>(
        impl: (yield: (val: TYields) => Thenable<void>
    ) => Promise<void>) {

        var started = false,
            yielded: TYields,
            continuation: () => void;

        function start() {
            impl(val => {
                yielded = val;
                return {
                    then(onFulfilled?: () => void) {
                        continuation = onFulfilled;
                        return this;
                    }
                };
            });
        }

        return {
            next(): { value?: TYields; done: boolean } {
                if (!started) {
                    started = true;
                    start();
                } else if (continuation) {
                    var c = continuation;
                    continuation = null;
                    c();
                }
                return !continuation ? { done: true } 
                    : { value: yielded, done: false };
            }
        };
    }

The impl function would be written using async/await, e.g.:

    var g = generator<string>(async (yield) => {

        console.log("Started");

        await yield("first");

        console.log("Continuing");

        for (var n = 0; n < 5; n++) {
            await yield("Number: " + n);
        }

        await yield("last");

        console.log("Done");
    });

Note how it accepts a parameter yield that is itself a function: this serves as the equivalent of the yield keyword, although we have to prefix it with await:

    await yield("first");

And then we can drive the progress of the generator g in the usual way, completely synchronously:

    for (var r; r = g.next(), !r.done;) {    
        console.log("-- " + r.value);
    }

Which prints:

Started
-- first
Continuing
-- Number: 0
-- Number: 1
-- Number: 2
-- Number: 3
-- Number: 4
-- last
Done

So how does this work? Well, firstly (and somewhat ironically) we have to avoid using promises as much as possible. The reason has to do with the terrifying Zalgo. As it says in the Promises/A+ spec, when you cause a promise to be resolved, this does not immediately (synchronously) trigger a call to any functions that have been registered via then. This is important because it ensures that such callbacks are always asynchronous.

But this has nothing to do with generators, which do not inherently have anything to do with asynchronicity. In the above example, we must be able to create the generator and iterate through it to exhaustion, all in a single event loop tick. So if we rely on promises to carry messages back and forth between the code inside and outside the generator, it just ain’t gonna work. Our “driving” loop on the outside is purely synchronous. It doesn’t yield for anyone or anything.

Hence, observe that when generator calls impl:

    impl(val => {
        yielded = val;
        return {
            then(onFulfilled?: () => void) {
                continuation = onFulfilled;
                return this;
            }
        };
    });

it completely ignored the returned promise, and in the implementation of yield (which is that lambda that accepts val) it cooks up a poor man’s pseudo-promise that clearly does not implement Promises/A+. Technically this is known as a mere Thenable. It doesn’t implement proper chaining behaviour (fortunately unnecessary in this context), instead returning itself. The onFulfilled function is just stashed in the continuation variable for later use in next:

    if (!started) {
        started = true;
        start();
    } else if (continuation) {
        var c = continuation;
        continuation = null;
        c();
    }
    return !continuation ? { done: true } 
                         : { value: yielded, done: false };

The first part is trivial: if we haven’t started, then start and remember that we’ve done so. Then we come to the meat of the logic: if this is the second time next has been called, then we’ve started. That means that impl has been called, and it ran until it hit the first occurrence of await yield, i.e.:

    await yield("first");

The TypeScript compiler’s generated code will have received our Thenable, and enlisted on it by calling then, which means we have stashed that callback in continuation. To be sure we only call it once, we “swap” it out of continuation into a temporary variable before we call it:

    var c = continuation;
    continuation = null;
    c();

That (synchronously) executes another chunk of impl until the next await yield, but note that we left continuation set to null. This is important because what if impl runs out of code to execute? We can detect this, because continuation will remain null. And so the last part looks like this:

    return !continuation ? { done: true } 
                         : { value: yielded, done: false };

Why do we have to use this stateful trickery? To reiterate (pun!) the promise returned by impl is meant to signal to us when impl has finished, but it’s just no good to us, because it’s a well-behaved promise, so it wouldn’t execute our callback until the next event loop tick, which is way too late in good old synchronous generators.

But this means we can’t get the final return value (if any) of impl, as the only way to see that from the outside is by enlisting on the returned promise. And that’s why I can’t make that one feature of generators work in this example.

Anyway, hopefully soon this will just be of nerdy historical interest, once generators make it into TypeScript. What might be the stumbling block? Well, TypeScript is all about static typing. In an ES6 generator in plain JavaScript, all names (that can be bound to values) have the same static type, known in TypeScript as any, or in the vernacular as whatever:

    function *g() {
        var x = yield "hello";
        var y = yield 52;
        yield [x, y];
    }

    var i = g();
    var a = i.next().value;
    var b = i.next(61).value;
    var c = i.next("humpty").value;

The runtime types are another matter: as the only kind of assignments here are initialisation, so each variable only ever contains one type of value, we can analyse it and associate a definite type with each:

x: number = 61
y: string = "humpty"
a: string = "hello"
b: number = 52;
c: [number, string] = [61, "humpty"]

But in TypeScript, we want the compiler to track this kind of stuff for us. Could it use type inference to do any good? The two questions to be answered are:

  • What is the type of the value accepted by next, which is also the type of the value “returned” by the yield operator inside the generator?
  • What is the type of the value returned in the value property of the object returned by next, which is also the type of value accepted by the yield operator?

The compiler could look at the types that the generator passes to yield. It could take the union of those types (string | number | [number, string]) and thus infer the type of the value property of the object returned by next. But the flow of information in the other direction isn’t so easy: the type of value “returned” from yield inside the generator depends on what the driving code passes to next. It’s not possible to tie down the type via inference alone.

There are therefore two possibilities:

  • Leave the type as any. This is not great, especially not if (like me) you’re a noImplicitAny adherent. Static typing is the whole point!
  • Allow the programmer to fully specify the type signature of yield.

The latter is obviously my preference. Imagine you could write the interface of a generator:

    interface MyGeneratorFunc {
        *(blah: string): Generator<number, string>;
    }

Note the * prefix, which would tell the compiler that we’re describing a generator function, by analogy with function *. And because it’s a generator, the compiler requires us to follow up with the return type Generator, which would be a built-in interface. The two type parameters describe:

  • the values passed to yield (and the final return value of the whole generator)
  • the values “returned” from yield

Note that the first type covers two kinds of outputs from the generator, but they have to be described by the same type because both are emitted in the value property of the object returned by the generator object’s next method:

function *g() {
    yield "eggs";
    yield "ham";
    return "lunch";
}

var i = g();
i.next() // {value: "eggs", done: false}
i.next() // {value: "ham", done: false}
i.next() // {value: "lunch", done: true} - Note: done === true 

Therefore, if we need them to be different types, we’ll have to use a union type to munge them together. In the most common simple use cases, the second type argument would be void.

This would probably be adequate, but in reality it’s trickier than this. Supposing in a parallel universe this extension was already implemented, but async/await was still the stuff of nightmares, how might we use it to describe the use of generators to achieve asynchrony? It’d be quite tricky. How about:

    interface AsyncFunc {
        *(): Generator<Promise<?>, ?>;
    }

See what I mean? What replaces those question marks? What we’d like to say is that wherever yield occurs inside the generator, it should accept a promise of a T and give back a plain T, where those Ts are the same type for a single use of yield, and yet it can be a different T for each use of yield in the same generator.

The hypothetical declaration above just can’t capture that relation. It’s all getting messy. No wonder they’re doing async/await first. On the other hand, we’re not in that universe, so maybe this stuff does’t matter.

These details aside, given how mature the prototype appears to be, I’m very much hoping that it will be released soon, with or without ordinary generators. It’s solid enough for me to use it for my fun home project, and it’s obviously so much better than any other way of describing complex asynchronous operations that I am even happy to give up IDE integration in order to use it (though I’d be very interested to hear if it’s possible to get it working in Visual Studio or Eclipse).

(But so far I’m sticking to a strict policy of waiting for official releases before unleashing them on my co-workers, so for now my day job remains on 1.4. And so my next post will be about some of the fun I’m having with that.)

Implementing a minimal social network in node (with generators and thunks)

June 25, 2014 7 comments

Yes, it’s time for another survey of the excruciatingly slow progress of generators in JavaScript! But with the happy conclusion that they are practically usable right now (and add massive value) in at least one context. Also I made my own social network!

Executive summary:

It’s over a decade since this concept first went mainstream in Python 2.3 (the yield keyword), almost a decade since they appeared in C# 2.0 (yield return) and only a year later they were added to Mozilla’s JavaScript 1.7 (yield again). And next year will mark 40 years since CLU originated this idea (can you guess what keyword CLU used to yield values?)

But getting a useable form of generators in browsers is taking ridiculously too long; ridiculous because they are a perfectly acceptable solution to the central problem of the browser API, which is managing a chain of asynchronous operations via callbacks. All you have to do is represent your asynchronous operation as a value that you yield from the generator. This allows some simple management code to detect when the result eventually arrives and so reawaken your generator where it left off. So control flips back and forth between your generator and the management code. The pain of asynchronicity is hidden from you and you get to relax in your underpants and drink hot chocolate like everything’s fine.

Thunks

How do you represent an operation as a value? There are two popular options. When I first got excited about this in JavaScript back in 2010, I did this:

var ASYNC = {
    ajax: function(url) {
        return function(receiver) { 
            jQuery.ajax({ url: url, success: receiver });
        };
    },

The caller of that function is writing a generator, so they say:

var secrets = yield ASYNC.ajax('readSecretEmail');

Therefore the management code responsible for cycling through the generator must be expecting a function to be yielded.

This pattern – in which a function (such as the above ASYNC.ajax) returns a value by the convoluted route of (deep breath) returning a function to which another function (which I called receiver) is passed that accepts the return value as a parameter – has somewhere picked up the name thunk, a name previously applied to many things, but let’s run with it.

This seems familiar…

If you’ve read my demystification of call-cc, you may remember I had to take a deep breath before tersely summarising it thus: “a function A that accepts a function B that will immediately be called by the language runtime, passing it a function C that when eventually (optionally) called will cause the previous call to A to return the argument previously passed to C and so take us back to where we started.”

These deep breaths are not a coincidence. There’s a deep parallel here. Replace that “function A” with the yield keyword. We give it “function B”, so that’s our thunk (such as the function returned by ASYNC.ajax). The “language runtime” is the management code driving the generator. It calls our thunk passing it a “function C”, so that must be the receiver accepted by our thunk. And when ASYNC.ajax passes a value to the receiver, “the previous call to A” (that is, the yield) will return that value so our code can carry on where it left off.

So this whole pattern (the combination of yield-ing thunks and some management code to drive the generator) is exactly the same shape as call-cc. There truly is nothing new under the sun (call-cc may be 50 years old). The only difference is that in the kind of thunks popular in node development, the receiver takes two parameters: (error, value). This mirrors the way ordinary functions can either return a value or throw an exception (and therefore error should be something like the standard Error object).

What about promises?

Another parallel is with promises. I’ve seen thunks described as a competing alternative to promises, but for our purposes they are almost homeomorphic: you can stretch one to make it look like the other, and back again. Let’s see how (and why it’s not quite a perfect homeomorphism, but we don’t care).

A promise has a then function that takes two callbacks, each taking one value: the first takes the actual value and the second takes an error, so only one of those callbacks will actually be called.

But of course if an object only has one interesting function, it might as well be that function. No good reason to make people say p.then(v, e) when they could just say p(v, e). Sure enough, a thunk is that function. Only instead of taking two callbacks, it takes one that will be passed both the parameters (the value and the error). According to node convention, they are the other way round: (error, value). But only one will have a meaningful value: if the error is not null or void, the value can be ignored.

So if we have a thunk, how would we wrap it in an equivalent promise?

var promise = {
    then: function(valCb, errCb) {
        thunk(function(err, val) {
            if (err) {
                errCb(err);
            } else {
                valCb(val);
            }
        });
    }
};

Well, not quite. I’ve left out a big chunk of what normally makes promises so useful: then should return another promise, one that is set up to resolve (or reject) based on the return value of valCb and errCb. Best of all is what they do if those callbacks return promises – they automatically “chain” to the promise returned by then.

But as we’re going to be using generators, we don’t give a crap about chaining because we have a much nicer solution. So in brief, that’s what I mean by an imperfect homeomorphism: not giving a crap about chaining. Where we’re going (puts on sunglasses), we don’t care if our async APIs return promises or thunks.

Running the generator

Back in the day I wrote my own helper called ASYNC.run that was responsible for launching a generator and stepping through it, re-awakening it whenever an async result appeared. But since then the API of generator objects has changed as part of standardisation. Also since generators were added to V8 and became accessible in non-stable builds of node, people have been working on little libraries that implement this same pattern (with the essential extra of dealing with errors as well as success values). There is one called suspend and another called co, and as you’d expect there’s not much to choose between them.

Koa

In fact if you use the delightful koa as the basis for your node web app then you’ll forget that anything needs to drive the generator. You just write (almost all) your code in generator functions and It Just Works. You may not need to directly depend on something like co at all.

bitstupid.com

I’ve been threatening my co-workers with the idea that I would start my own social network, ever since Twitter caught on. It struck me that 140 characters is a lot of information, pretty daunting for the average person to deal with. So why not restrict each user to a single bit, the theoretical minimum quantity of information? You can toggle the value of your own bit, you can toggle other people’s bits, they can toggle yours. It can be a society-changing metaphor for whatever sordid, disgusting animalistic activity you wish. That’s none of my business.

So now I finally got around to it. The code is very short. This is largely down to the choice of redis as the database. My data layer is in the data.js module. All the exports are generators, e.g.:

exports.getSecret = function* (of) {

    var secret = yield redis.hget('user:' + of, 'secret');
    if (secret === null) {
        var secret = (yield crypto.randomBytes(128)).toString('base64');
        if ((yield redis.hsetnx('user:' + of, 'secret', secret)) === 0) {
            secret = yield redis.hget('user:' + of, 'secret');
        } else {
            yield redis.set('secret:' + secret, of);
        }
    }

    if (secret === null) {
        throw new Error('Unexpected: could not get secret of ' + of);
    }

    return secret;
};

In other words, as with C# async/await, it makes the code look no different from the synchronous variety except for the constant repetition of a certain keyword (either yield or await) before every API call. I maintain that good design is about choosing the right defaults, and here we have the incorrect choice. An asynchronous API call should automatically work as if you prefixed it with yield. Only if you specifically want to obtain the underlying value representation (the promise, the Task, the thunk…) should you need to prefix it with a keyword. But I already complained about that and few people seem to understand what I’m talking about. In any case I can’t see how this could be solved efficiently in a dynamic language like Javascript (a statically typed language is another matter: TypeScript maybe has the opportunity to get it right).

But despite all the yield keywords cluttering up the code, this is still obviously a great leap ahead of normal callback-based node code. Try rewriting the above getSecret and you’ll see what I mean. It only just occurred to me to bother for explanatory purposes, so I don’t know if this is correct, but it’s roughly the right shape:

exports.getSecret = function(of, callback) {

    redis.hget('user:' + of, 'secret', function(err, secret) {
        if (err) {
            callback(err);
        } else {
            if (secret !== null) {
                callback(null, secret);
            } else {
                crypto.randomBytes(128, function(err, secret) {
                    if (err) {
                        callback(err);
                    } else {
                        secret = secret.toString('base64');
                        redis.hsetnx('user:' + of, 'secret', secret, function(err, result) {
                            if (err) {
                                callback(err);
                            } else {
                                if (result === 0) {
                                    redis.hget('user:' + of, 'secret', function(err, secret) {
                                        if (secret === null) {
                                            callback(new Error('Unexpected: could not get secret of ' + of));
                                        } else {
                                            callback(null, secret);
                                        }
                                    });
                                } else {
                                    redis.set('secret:' + secret, function(err) {
                                        callback(null, secret);
                                    });
                                }
                            }
                        });
                    }
                });
            }
        }
    });
};

It’s worth noting that a lot of the mess is due to the misery of having to explicitly pass back errors. To be fair to promise chaining, that alone would clean up the error-handling mess (again, this is just an untested rough guess):

exports.getSecret = function(of) { 
    return redis.hget('user:' + of, 'secret').then(function(secret) {
        return secret || crypto.randomBytes(128).then(function(secret) {
            secret = secret.toString('base64');
            return redis.hsetnx('user:' + of, 'secret', secret).then(function(result) {
                if (result === 0) {
                    return redis.hget('user:' + of, 'secret').then(function(secret) {
                        if (secret === null) {
                            throw new Error('Unexpected: could not get secret of ' + of);
                        }
                        return secret;
                    });
                }
                return redis.set('secret:' + secret).then(function() {
                    return secret;
                });
            });
        });
    });
};

But it’s still very noisy. Lots of then(function(secret) { and hence nesting. Also this isn’t even a particularly complex case.

ay

Try this seemingly innocuous example from server.js:

app.get('/bits/:of', function* () {
    var bit = yield data.readBit(
        this.params.of.toLowerCase(), 
        this.query.skip, 
        this.query.take);

    yield ay(bit.changes).forEach(function* (change) {
        change.info = yield data.getInfo(change.by);
    });

    this.body = bit;
});

First I get the bit object that described the state of the requested user’s bit. It includes a changes that lists a series of occasions on which someone toggled the bits. These include a username, by. I want to augment this with an info property that gives all the known information about the user, but data.getInfo is another async API of course. That rules out using the usual Array#forEach, because you can’t give it a generator. Same goes for map, filter, reduce and so on.

So I wrote a little library called ay (“array yield”) to get around this. It lets you chain the usual operations on an array but pass in generator functions, in such a way that any yields can escape out to the surrounding context. Here’s a more complete example of usage:

var num = yield ay(nums)
    .map(function* (i) {
        yield sleep(10);
        return i * 2;
    })
    .filter(function* (i) {
        yield sleep(10);
        return i > 2;
    })
    .reduce(function* (a, b) {
        yield sleep(10);
        return a + b;
    });

funkify

Another library I cooked up for bitstupid.com is funkify. There’s a widely cited library thunkify that can turn a single traditional node callback API into a thunk-returner. But what if you want to do a whole module or other object? I found a couple of libraries for doing that, but they both modified the original object. Didn’t like that; what if it breaks it? Also there is a subtlety in writing something that wraps another object: what if it is a function, but also has several function properties attached to it? An example of this is the widely used request, which can be called directly as a function but also has functions like get and post hanging off of it. Hence funkify, which is wise to such things:

var request = funkify(require('request'));

// In a generator...
var info = yield request.get({ uri: 'blah' });

Or to adapt the superb redis client library:

var redis = funkify(require('redis').createClient());

It’s a pain-free way to instantly turn a library into a thunk-returner ready for use from koa.

Generators on stable node versions

Generators are not yet available in mainstream V8 and so neither are they in stable node releases. It’s pretty easy to fix this if you’re happy running unstable builds – just install nvm:

curl https://raw.githubusercontent.com/creationix/nvm/v0.8.0/install.sh | sh

and then say:

nvm install 0.11

But if you’d rather run a stable build (or your host only lets your run some ancient version), what can you do? It’s wonderfully easy thanks to gnode:

npm install -g gnode

Then just use the gnode command instead of node. On my server I use the delightful forever to get the app running:

forever start /usr/local/bin/gnode server.js

That way when I disconnect, it stays up (and it gets restarted automatically if it crashes).

Categories: Uncategorized Tags: , , ,

Adventures in Roslyn: A new kind of managed lvalue pointer

April 27, 2014 3 comments

It’s already the evening and I haven’t yet added anything to the C# compiler today, so here goes!

Properties have special support in C#, but they are not “first class”. You can’t get a reference to a property and pass it around as a value. Methods are much better served in this regard: delegates are a way to treat a method as a value. But they are just objects with an Invoke method.

So all we need is an interface with a Value property. Objects supporting that interface can represent a single property that can be passed around like any other value:

public interface IProperty<T>
{
    T Value { get; set; }
}

This is closely analogous to an old-fashioned pointer in C and C++, as I mused aloud all those years ago. Let’s turn that whole idea into a strangely alluring language feature, which I’ll call “property references”, and then occasionally forget that terminology and call them pointers instead.

Firstly, syntax. We could use actual pointer syntax, but I already used some of that in yesterday’s feature. Dagnabbit! Fortunately C++/CX has already paved the way: it has the concept of a reference to a fancy object that must be explicitly dereferenced. The syntax is like this:

MyClass ^r = %x;

(*r).Foo();

If this looks weird, try replacing ^ with * and % with &. It’s then exactly like C/C++. ^ is a postfix modifier on a type declaration that means “Will store a pointer to one of those”, and % is a unary prefix operator that means “Give me a pointer to whatever comes next”. And for the sake of uniformity in common code, C++/CX always uses * to dereference.

Before getting into the nitty-gritty of changing the compiler, let’s survey the glorious sunny uplands we wish to invade. We should be able to do this in C#:

var x = 5;
var px = %x; // Take a "pointer" to x

Console.WriteLine(*px); // Prints 5

*px = 6; // Can assign "through" a pointer
(*px)++; // Or increment

Console.WriteLine(x); // Prints 7 - we modified x via px

Unlike old-school pointers, we can – of course – quite safely return one of these things from a method, referring to a local variable:

static int^ GetCounter(int init)
{
    var counter = init;
    return %counter;
}

// elsewhere...
var c = GetCounter(100);
Console.WriteLine(*c); // Prints 100

(*c)++;
Console.WriteLine(*c); // Prints 101

The trick is that each bit of new syntax expands very simply into some standard C#. All the heavy lifting is done by the compiler’s existing support for lambdas:

var x = 5;
System.IProperty<int> px = System.Property.Bind(v => x = v, () => x); // int *p = %x;
var y = px.Value; // var y = *x;

But of course, those helper types are not part of the standard System namespace. We need to add them:

namespace System
{
    public interface IProperty<T>
    {
        T Value { get; set; }
    }

    public static class Property
    {
        private class PtrImpl<T> : IProperty<T>
        {
            Action<T> _set;
            Func<T> _get;

            public PtrImpl(Action<T> set, Func<T> get)
            {
                _set = set;
                _get = get;
            }

            public T Value
            {
                get { return _get(); }
                set { _set(value); }
            }
        }

        public static IProperty<T> Bind<T>(Action<T> set, Func<T> get)
        {
            return new PtrImpl<T>(set, get);
        }
    }
}

These don’t need to be in mscorlib.dll (some of the later C# features rely on types in System.Core.dll). So we can just create a new “System.Extras.dll” assembly and stick them in there.

So, one thing that makes this a whole ‘nother level of crazy compared to my first two forays in to compiler features is that here we are adding new syntax. Fortunately Roslyn makes this quite easy. There’s a file called Syntax.xml from which the project generates classes for all the nodes that can appear in a syntax tree. We can (as usual) follow the example of what we find in there.

All the unary prefix operators are in here, so they share a single class that can be distinguished by the Kind property:

<Node Name="PrefixUnaryExpressionSyntax" Base="ExpressionSyntax">
  <Kind Name="UnaryPlusExpression"/>
  <Kind Name="UnaryMinusExpression"/>
  <Kind Name="BitwiseNotExpression"/>
  <Kind Name="LogicalNotExpression"/>
  <Kind Name="PreIncrementExpression"/>
  <Kind Name="PreDecrementExpression"/>
  <Kind Name="AddressOfExpression"/>
  <Kind Name="PointerIndirectionExpression"/>
  <Kind Name="AwaitExpression"/>
  <Kind Name="PropertyReferenceExpression"/>    
  <Field Name="OperatorToken" Type="SyntaxToken">
    <Kind Name="PlusToken"/>
    <Kind Name="MinusToken"/>
    <Kind Name="TildeToken"/>
    <Kind Name="ExclamationToken"/>
    <Kind Name="PlusPlusToken"/>
    <Kind Name="MinusMinusToken"/>
    <Kind Name="AmpersandToken"/>
    <Kind Name="AsteriskToken"/>
    <Kind Name="AwaitKeyword"/>
    <Kind Name="PercentToken"/>
    <PropertyComment>
      <summary>SyntaxToken representing the kind of the operator of the prefix unary expression.</summary>
    </PropertyComment>
  </Field>
  <Field Name="Operand" Type="ExpressionSyntax">
    <PropertyComment>
      <summary>ExpressionSyntax representing the operand of the prefix unary expression.</summary>
    </PropertyComment>
  </Field>
  <TypeComment>
    <summary>Class which represents the syntax node for prefix unary expression.</summary>
  </TypeComment>
  <FactoryComment>
    <summary>Creates an PrefixUnaryExpressionSyntax node.</summary>
  </FactoryComment>
</Node>

I’ve added the PropertyReferenceExpression and the PercentToken. For the type modifier ^ I have to cook up a whole new node type:

<Node Name="PropertyReferenceTypeSyntax" Base="TypeSyntax">
  <Kind Name="PropertyReferenceType"/>
  <Field Name="ElementType" Type="TypeSyntax">
    <PropertyComment>
      <summary>TypeSyntax node that represents the element type of the property reference.</summary>
    </PropertyComment>
  </Field>
  <Field Name="CaretToken" Type="SyntaxToken">
    <Kind Name="CaretToken"/>
    <PropertyComment>
      <summary>SyntaxToken representing the caret symbol.</summary>
    </PropertyComment>
  </Field>
  <TypeComment>
    <summary>Class which represents the syntax node for property reference type.</summary>
  </TypeComment>
  <FactoryComment>
    <summary>Creates a PropertyReferenceTypeSyntax node.</summary>
  </FactoryComment>
</Node>

Now, if we try to build the compiler we’ll get errors about missing names in the enum SyntaxKind, so we need to add them:

public enum SyntaxKind : ushort
{
    ...

    PropertyReferenceType,
    PropertyReferenceExpression
}

In SyntaxKindFacts.cs there’s a workaday switch statement that we need to modify so it takes care of mapping % tokens to our new unary operator:

public static SyntaxKind GetPrefixUnaryExpression(SyntaxKind token)
{
    switch (token)
    {
        case SyntaxKind.PlusToken:
            return SyntaxKind.UnaryPlusExpression;
        case SyntaxKind.MinusToken:
            return SyntaxKind.UnaryMinusExpression;
        case SyntaxKind.TildeToken:
            return SyntaxKind.BitwiseNotExpression;
        case SyntaxKind.ExclamationToken:
            return SyntaxKind.LogicalNotExpression;
        case SyntaxKind.PlusPlusToken:
            return SyntaxKind.PreIncrementExpression;
        case SyntaxKind.MinusMinusToken:
            return SyntaxKind.PreDecrementExpression;
        case SyntaxKind.AmpersandToken:
            return SyntaxKind.AddressOfExpression;
        case SyntaxKind.AsteriskToken:
            return SyntaxKind.PointerIndirectionExpression;

        // The new part:
        case SyntaxKind.PercentToken:
            return SyntaxKind.PropertyReferenceExpression;

        default:
            return SyntaxKind.None;
    }
}

And there’s a another that defines the precedence of operators, which is how the compiler decides what to do when you don’t fully parenthesise your expressions. I figure that the new % operator should copy the existing & operator:

private static uint GetPrecedence(SyntaxKind op)
{
    switch (op)
    {
        ...

        case SyntaxKind.AddressOfExpression:
        case SyntaxKind.PropertyReferenceExpression: // the new part
            return 16;
        default:
            return 0;
    }
}

For the all-new ^ operator we have to throw some code in to deal with it. Like I said yesterday, Roslyn’s structure seems surprisingly procedural. It’s not using functional parser combinators or anything “cool” and/or “academic”. It’s just a bunch of methods that examine the current token, do switch statements, etc. On the plus side, it is very easy to learn how it works by stepping through it in the debugger. That’s the saving grace of procedural code: ease of hacking.

I hooked into the same place that handles pointer syntax, as (again) its closely analogous.

private TypeSyntax ParsePointerTypeMods(TypeSyntax type)
{
    // Check for pointer types
    while (this.CurrentToken.Kind == SyntaxKind.AsteriskToken)
    {
        type = syntaxFactory.PointerType(type, this.EatToken());
    }

    // Check for property reference types (new)
    while (this.CurrentToken.Kind == SyntaxKind.CaretToken)
    {
        type = syntaxFactory.PropertyReferenceType(type, this.EatToken());
    }

    return type;
}

Note: we don’t have to write that syntaxFactory.PropertyReferenceType method. It’s one of the pieces that are auto-generated from what we added to Syntax.xml.

Now, we have the syntax. All we need now is to sort out the binding phase, which figures out whether the syntax actually makes sense (that when it refers to a variable called x, there actually is one called x, and every expression has a type, etc.)

And it is here that I am overcome with one of those attacks of laziness that are the hallmark of the truly great programmer, hem-hem. Faced with a pattern like this:

System.Property.Bind(v => o = v, () => o)

We don’t want to have to write screeds of code that builds the BoundExpression that make up that pattern (believe me: I got about half-way through the first lambda before realising I would be retired before finishing the whole thing). In any case, the compiler can already do it – that’s its job. Ideally we could use the existing parser to get a kind of “syntax template”, in which we can replace certain identifiers with chunks of other syntax, and then ask the existing binder to bind it. Then we’d have to do almost no thinking at all! Bliss.

So for example:

private static readonly SyntaxTemplate _propertyReferenceTemplate
    = new SyntaxTemplate("System.Property.Bind(__v_pr__ => o = __v_pr__, () => o)");

private BoundExpression BindPropertyReferenceExpression(PrefixUnaryExpressionSyntax node, DiagnosticBag diagnostics)
{
    return RedirectDiagnostics(diagnostics, node, redirected =>
        BindExpression(_propertyReferenceTemplate.Replace("o", node.Operand).Syntax, redirected));
}

We’ll come back to that RedirectDiagnostics part later. The key point is that I’m creating an instance of my new class SyntaxTemplate as a static, so it is reused for the lifetime of the compiler. It’s immutable, hence thread-safe. Then every time I need to bind something like %foo, I can just replace the o in the template with foo (which is in node.Operand). Replace returns a new SyntaxTemplate rather than modifying the original (that’s what immutability is all about).

Again, binding is a recursive, procedural system. There’s a big switch statement that calls out to methods that bind various things, so we need to hook our new method BindPropertyReferenceExpression into that:

private BoundExpression BindExpressionInternal(ExpressionSyntax node, DiagnosticBag diagnostics, bool invoked, bool indexed)
{
    if (IsEarlyAttributeBinder && !EarlyWellKnownAttributeBinder.CanBeValidAttributeArgument(node, this))
    {
        return BadExpression(node, LookupResultKind.NotAValue);
    }

    Debug.Assert(node != null);
    switch (node.Kind)
    {
        ...

        // New part
        case SyntaxKind.PropertyReferenceExpression:
            return BindPropertyReferenceExpression((PrefixUnaryExpressionSyntax)node, diagnostics);

See how there’s a switch statement on an enum, then a cast – all the kinds of thing that beginners are told not to do when they learn C#, because supposedly virtual method dispatch on a single object solves all problems. (Oh wait, no it doesn’t.) But still, it wouldn’t make sense to have a built-in type switch in languages like C#, Java or C++ (except apparently in one situation).

Anyway, BindExpression calls BindExpressionInternal, which calls our new BindPropertyReferenceExpression method, which expands our template and passes it to BindExpression… we’re going in circles! But it’s okay. The reason this doesn’t asplode the stack is because our template doesn’t include further references to %.

Now, about that RedirectDiagnostics wrinkle. The binding process has a DiagnosticBag object that gets passed around. Any errors found are thrown in the bag. Each error has a Location object, identifying the place in the user’s source code where the error was spotted, so the locations were discovered at the parsing stage. The problem we have is that we parse our template code separately, so the locations bear no relation to the user’s source code. This means that the IDE’s text editor cannot put red squiggles in the right place.

To fix this, I literally fix the diagnostics:

private T RedirectDiagnostics<T>(DiagnosticBag diagnostics, 
             CSharpSyntaxNode nodeWithLocation, 
             Func<DiagnosticBag, T> generate)
{
    var captured = new DiagnosticBag();
    var result = generate(captured);

    foreach (var diag in captured.AsEnumerable().OfType<DiagnosticWithInfo>())
        diagnostics.Add(new CSDiagnostic(diag.Info, nodeWithLocation.Location));

    return result;
}

The generate function does the binding, but to a “fake” temporary DiagnosticBag, which we then copy into the real one but replacing all the Location objects with a single good location. This isn’t ideal. Recall that some of the syntax tree was inserted from the user’s source and so had perfectly good locations. I need to figure out a way of detecting whether a location is junk or not. But it sort of works.

So, we have binding for %. For * we have to enhance the existing code, branching based on whether operand is a pointer:

private static readonly SyntaxTemplate _pointerIndirectionTemplate = new SyntaxTemplate("p.Value");

// Based on ExpressionBinder::bindPtrIndirection.
private BoundExpression BindPointerIndirectionExpression(PrefixUnaryExpressionSyntax node, DiagnosticBag diagnostics)
{
    BoundExpression operand = BindValue(node.Operand, diagnostics, GetUnaryAssignmentKind(node.Kind));

    // Try using the template on anything that isn't a pointer
    if (!operand.Type.IsPointerType())
        return RedirectDiagnostics(diagnostics, node, redirected => 
            BindExpression(_pointerIndirectionTemplate.Replace("p", node.Operand).Syntax, redirected));

    TypeSymbol pointedAtType;
    bool hasErrors;
    BindPointerIndirectionExpressionInternal(node, operand, diagnostics, out pointedAtType, out hasErrors);

    return new BoundPointerIndirectionOperator(node, operand, pointedAtType ?? CreateErrorType(), hasErrors);
}

We can even use the template technique for type declarations – just replace T with whatever we get from the user:

private static readonly SyntaxTemplate _propertyReferenceTypeTemplate = new SyntaxTemplate("System.IProperty<T>");

internal Symbol BindNamespaceOrTypeOrAliasSymbol(ExpressionSyntax syntax, DiagnosticBag diagnostics, ConsList<Symbol> basesBeingResolved, bool suppressUseSiteDiagnostics)
{
    switch (syntax.Kind)
    {
        ...

        case SyntaxKind.PropertyReferenceType:
            {
                return RedirectDiagnostics(diagnostics, syntax, redirected => BindNamespaceOrTypeOrAliasSymbol(
                    _propertyReferenceTypeTemplate.Replace("T", ((PropertyReferenceTypeSyntax)syntax).ElementType).Syntax, 
                    redirected, basesBeingResolved, suppressUseSiteDiagnostics));
            }

That’s every change needed to support the feature. If you want to play with it (and even add features of your own using the SyntaxTemplate class), I’ve updated my fork with all these changes. You will need to define the System.IProperty and System.Property types – it will work if you just paste the code.

Categories: Uncategorized Tags:

Adventures in Roslyn: Using pointer syntax as a shorthand for IEnumerable

April 26, 2014 1 comment

Another quickie extension to C#. In the current language, a type declaration T! is shorthand for Nullable.

But equally important in modern C# programs are sequences of values, so a similar shorthand for IEnumerable would be ideal. The asterisk symbol is underused (you can suffix a type with asterisk to make a pointer, but only in unsafe contexts), and this was the choice made by the intriguing research language Cω that influenced LINQ, so let’s copy that:

    int* numbers = new[] { 1, 6, 55, 4, 11 };

    foreach (var n in numbers)
        Console.WriteLine(n);

In Binder_Symbols.cs we find:

    case SyntaxKind.PointerType:
        {
            var node = (PointerTypeSyntax)syntax;            
            ReportUnsafeIfNotAllowed(node, diagnostics);

            var elementType = BindType(node.ElementType, diagnostics, basesBeingResolved);
            if (elementType.IsManagedType)
            {
                // "Cannot take the address of, get the size of, or declare a pointer to a managed type ('{0}')"
                Error(diagnostics, ErrorCode.ERR_ManagedAddr, node, elementType);
            }

            return new PointerTypeSymbol(elementType);
        }

The call ReportUnsafeIfNotAllowed is what checks for the unsafe context. So I commented that out and added my own check for not-unsafe, before doing something very similar to what happens for T? -> Nullable elsewhere in the same file:

    case SyntaxKind.PointerType:
        {
            var node = (PointerTypeSyntax)syntax;

            //ReportUnsafeIfNotAllowed(node, diagnostics);
            if (this.IsIndirectlyInIterator || !this.InUnsafeRegion)
            {
                NamedTypeSymbol enumerableT = GetSpecialType(SpecialType.System_Collections_Generic_IEnumerable_T, diagnostics, syntax);
                TypeSymbol typeArgument = BindType(node.ElementType, diagnostics, basesBeingResolved);
                NamedTypeSymbol constructedType = enumerableT.Construct(typeArgument);
                if (ShouldCheckConstraints)
                {
                    constructedType.CheckConstraints(this.Compilation, this.Conversions, syntax.Location, diagnostics);
                }
                return constructedType;
            }

            var elementType = BindType(node.ElementType, diagnostics, basesBeingResolved);
            if (elementType.IsManagedType)
            {
                // "Cannot take the address of, get the size of, or declare a pointer to a managed type ('{0}')"
                Error(diagnostics, ErrorCode.ERR_ManagedAddr, node, elementType);
            }

            return new PointerTypeSymbol(elementType);
        }

And we’re done! We can now say things like:

static int *Squares(int *nums)
{
    return nums.Select(n => n * n);
}

Roslyn may not be very pretty – it’s a hand-crafted top-down system, so it looks nothing like the “text book” functional parsers. But it’s a real product as opposed to a clean example, so that’s hardly surprising. Regardless, it is proving easy (even fun) to hack.

Categories: Uncategorized Tags:

Adventures in Roslyn: Adding crazily powerful operator overloading to C# 6

April 24, 2014 7 comments

I’m going to show you how to enable a new kind of operator overloading by adding exactly four (4) lines of code to a single file in the C# 6 compiler preview. Yes, I was surprised too!

After seeing the video of Anders Hejlsberg showing how easy it is to hack the new open source C# compiler, I had to give it a try.

My aim was (I assumed) a lot more ambitious and crazy than his demo. I thought it would take ages to figure out. But it was still tempting to aim high and actually implement a substantial new feature, because there are a few I’ve been wondering about over the years.

Ever since LINQ query syntax was added to the language, I’ve wished that operator overloading worked the same way. The where keyword gets turned into a call to a Where method. And it doesn’t matter where or how that method is defined. It can be an extension method, an ordinary method, a virtual method. In fact there are few other language features that map to well known member names: a collection initializer is turned into several calls to a method called Add, and the await keyword expands into calls to several methods.

So my use case is very simple. Suppose I have a couple of sequences of values:

var nums1 = new[] { 1, 2, 3 };
var nums2 = new[] { 4, 5 };

var nums3 = nums1 + nums2;

That last line, which I’d like to concatenate the two sequences, simply isn’t going to work because operator + is not defined on IEnumerable. Nor is there a way to make it work for all sequences in standard C#. That would require the ability to implement an operator overload using extension methods! Such a thing does not exist. But it would be pretty useful.

Suppose if the compiler couldn’t find a standard meaning for +, it tried looking for a method available the left-hand-side value called Addition. (NB. Add is already taken by collection initializers as I previously noted).

public static class EnumerableOperatorExtensions
{
    public static IEnumerable<T> Addition<T>(this IEnumerable<T> left, IEnumerable<T> right)
    {
        return left.Concat(right);
    }
}

Of course, Concat is already there to do the real work for us: the above incantation just makes it available under a standardised name.

So let’s get to work. To play along at home, download the Roslyn source, read the instructions for building/debugging, get all the prerequisites (the instructions seem to be flawless as far as I can tell), and make sure you’re able to build and hit F5 to bring up Visual Studio. You’ll find you can set breakpoints and they will be hit (from multiple threads) as VS2013 compiles code on the fly as you edit it, to provide intellisense, etc.

The first thing I had to do was find those well-known member names, such as Where. Obviously it wouldn’t be that easy, but I tried a simple search for the quoted string "Where"… Oh, turns out it really is that easy!

This is the first hit:

void ReduceWhere(WhereClauseSyntax where, QueryTranslationState state, DiagnosticBag diagnostics)
{
    // A query expression with a where clause
    //     from x in e
    //     where f
    //     ...
    // is translated into
    //     from x in ( e ) . Where ( x => f )
    var lambda = MakeQueryUnboundLambda(state.RangeVariableMap(), state.rangeVariable, where.Condition);
    var invocation = MakeQueryInvocation(where, state.fromExpression, "Where", lambda, diagnostics);
    state.fromExpression = MakeQueryClause(where, invocation, queryInvocation: invocation);
}

That MakeQueryInvocation looked intriguing. It calls onto another helper called MakeInvocationExpression, which takes a receiver for the method call, a method name and an immutable array of arguments, and is commented as:

// Helper method to create a synthesized method invocation expression.

On searching for calls to it, as you’d expect, I found it being used for collection initializers and await in exactly the same way. All I needed was to find a spot in the binding of operators where we’re just about to give up and emit an error, and then try MakeInvocationExpression.

The next part I did with a mixture of searching for likely words in the source and then setting breakpoints to see if they got hit. Eventually I found a method Binder.BindSimpleBinaryOperator in the file Binder_Operator.cs. Actually there are two overloads of it: the four-argument overload does the real work. (The two-argument overload is just a wrapper that avoids too much recursion when dealing with chained operators by implementing its own stack.)

Anyway, it works by calling another helper, BinaryOperatorOverloadResolution, which implements the standard C# rules, and then it checks if it worked:

if (!best.HasValue)
{
    resultOperatorKind = kind;
    resultType = CreateErrorType();
    hasErrors = true;
}

That’s where it gives up! So that’s where we need MOAR CODE:

if (!best.HasValue)
{
    string methodName = Enum.GetName(typeof(BinaryOperatorKind), kind);                
    var methodCall = MakeInvocationExpression(node, left, methodName, ImmutableArray.Create(right), diagnostics);
    if (methodCall != null && !methodCall.HasAnyErrors)
        return methodCall;

    resultOperatorKind = kind;
    resultType = CreateErrorType();
    hasErrors = true;
}

Look how damn lazy I was. The enum BinaryOperatorKind defines Addition, Subtraction, etc., so I just get the string name of the value to use as the method name. If MakeInvocationExpression seems to have worked, I return the result.

But I was also quite careful. By ensuring the standard is followed first, and the new behaviour only kicks in for code that would otherwise be malformed, I don’t change the meaning of existing programs.

And that’s it. Here’s a look at what happens in Visual Studio when I run it and enter my test case, but first without defining an extension method:

Rosyln shows error message

Note the error message! It’s telling us we need to write an Addition method that takes one argument. In the intellisense! I didn’t have to do anything in particular to make that happen.

Then when we add the declaration of the extension method:

Rosyln shows no error message

The red squiggle has gone, and num3 has the right type. And when I hit F5, I see the expected concatenated output.

I am astonished.

Here’s a fork with this small change.

There is still more to investigate. For example:

interface IThing
{
    IThing Addition(IThing other);
    IThing Subtraction(IThing other);
}

static void Test<T>(T a, T b) where T : IThing
{
    var r1 = a + b;
    var r2 = a - b;
}

That works! Oh yes, you can do operators on generic parameter types. Couldn’t do that before.

However, what about ==? That doesn’t work – it seems the compiler handles equality comparison separately, and doesn’t get to my new code. Maybe that’s a good thing… But on the other hand, maybe not. Will take another look tomorrow.

Categories: Uncategorized Tags:
Follow

Get every new post delivered to your Inbox.