Archive

Author Archive

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

June 25, 2014 3 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 5 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:

Desktop Apps in JavaScript+HTML

March 7, 2014 Leave a comment

Part of the reason I did Eventless (apart from it being fun and explanatory) was so I’d have something almost as convenient as Knockout available to me the next time I had to write a desktop app with a UI. It has now been many years since we could regard web UI development as a hairshirt chore, where we have to make do without the comforts of familiar mature environments and tools. Quite the opposite: whenever I have to write and support a desktop app I curse the fact that I can’t hit F12 and “inspect the DOM” of my UI while it’s running, or immediately debug the code on the tester’s machine when they find a problem.

In the decade-before-last, Microsoft quietly released an IE feature called HTA, or “HTML application”. It’s the neat (but trivially obvious) idea of switching off the usual browser security checks and allowing you to create any ActiveX scriptable objects, so you could write applications with HTML UIs. Neat, but horrible in practise because… well, you had to be there to appreciate the overall shoddiness. And so that’s why they of course had to rush down to the patent office.

But fast forward to the last few years. We can develop complex server or command-line applications in JavaScript using the Node platform and its ecosystem of libraries. We can use a variety of front end languages to fill in the deficiencies of raw JavaScript. The debugging experience inside modern browsers is the best debugging experience anywhere. And so on. It’s well beyond the time for HTAs done right.

It being such an obvious idea, there are a few implementations floating around, but the best I’ve seen is node-webkit. Which is a fine technical name (because it tells you honestly that it’s just node mashed together with webkit), but I think they should pick some cool and memorable “marketing” name for it, because it’s just too brilliant a combination to go without a name of its own. I suggest calling it 长裤. Or failing that, 内裤.

The easiest way to get started with it is to install node, then the nodewebkit package with the -g flag (it’s not a module that extends node; rather, it’s a separate runtime that has its own copy of node embedded). Then you create a package.json with an HTML file as its main:

"main": "index.html"

From that HTML file you can pull in scripts using the script tag in the usual way. But inside those scripts you can use node’s require. Yup.

The sweet combination for me is the beautiful TypeScript, plus the phenomenal Knockout, plus whatever node modules I want to call (along with TypeScript declarations from DefinitelyTyped). This gives me the best of everything: static typing, Chrome-like debugging, the smoothest most scalable/flexible form of two-way binding, the whole works. So I’ll probably never use Eventless in a real project.

I actually started writing a UI for conveniently driving Selenium (which I hopefully will have time to describe soon) in C#/Windows Forms. After getting it all working, I trashed it and switched to node-webkit and it was ridiculous how quickly I was able to get back to the same spot, plus a huge momentum boost from the fun I was having.

(Though admittedly quite a lot of that fun was probably the first flush of joy from using TypeScript.)

(I’m a nerd, did I mention that?)

Categories: Uncategorized Tags: ,

JavaScript for Java programmers

December 7, 2013 2 comments

I just found on my hard drive a talk I gave over two years ago. If you’re a reasonably experienced Java programmer looking for a way to really understand how JavaScript works (especially functions as object, closures, etc.) it may be of help to you:

http://www.youtube.com/watch?v=FGNKoHv7xPY

Categories: Uncategorized Tags: , ,

Rich Text Editor in the HTML Canvas – Part 1: Introducing CAROTA

November 4, 2013 4 comments

I’m developing a rich text editor from scratch in JavaScript, atop the HTML5 canvas. It’s called Carota (Latin for carrot, which sounds like “caret”, and I like carrots).

Here is the demo page, which is very self-explanatory, in that it presents a bunch of information about the editor, inside the editor itself, so you can fiddle with it and instantly see how it persists the text in JSON. As you can see, it’s quite far along. In fact I suspect it is already good enough for every way I currently make use of rich text in browser applications. If your browser is old, it will not work. (Hint: IE8 is way old.)

So… Why? What a crazy waste of time when browsers already have the marvellous contentEditable feature, right?

A quick survey of the state-of-the-art suggests otherwise. Google Docs uses its own text layout and rendering system, only using the DOM as low-level display mechanism (the details on that link are very relevant and interesting). Go to Apple’s iCloud which now has a beta of their Pages word processor, and use your browser to look at how they do it: the text is rendered using absolute, meticulously positioned SVG elements, so they too perform their own layout.

And having tried for the last year to get contentEditable to serve my purposes, in the same way on all browsers (actually, even one browser would be something), I can understand why the Twin Behemoths of the Cloud have taken control of their own text layout. So I’m going to do the same thing, but with Canvas. (My previous plan was to do a plugin for Windows so I’d be able to use the Win32 Rich Edit control, but that kind of plugin is about to die out.)

Before I got as far as drawing any text on screen, I had to be very careful to build up a fundamental model of how flowing text actually works. I wanted to end up with beautiful components that each do something extremely simple, and plug together into a working editor. That way it’s easier to change stuff to meet future needs. I’ve designed it from the ground up to be hacked by other people to do whatever they want.

So, hopefully I’ll be back soon to start describing how it works. In the meantime, fork me on github and you can also get the development set-up via the usual:

npm install carota

For a really quick minimal demo, try this jsfiddle, which just creates an editor in an empty DIV and then uses load and save for persistence.

per: composable forward-passing processor functions

October 31, 2013 Leave a comment

The other day I tried implementing SICP streams in JavaScript as part of a fun project I’m tinkering with. I noticed that (unsurprisingly, given how they work) they generate a lot of memory garbage during the main loop of whatever operation you’re doing, and the overhead of this can actually become significant.

So I blogged them, sighed to myself, and then ripped them out of my project. What should I use instead? I want a combination of high performance and convenience. Also I miss generators, which of course I can’t (yet) assume are available on my target platforms, as they include browsers dating as far back as the ancient IE9 (ask your grandmother) and Chrome 30 without the about:flags experimental JavaScript features enabled.

My building block will be a function of this shape, which I’ll refer to as a processor:

function timesTwo(emit, value) {
    emit(value * 2); // this part is optional
}

It takes two parameters, the first being a function to which it can pass values forward, and then second being a value for it to process. So you have to call it to give it a value, and it may or may not emit values onwards to wherever you tell it.

Of course it can emit nothing, or many values:

function triplicate(emit, value) {
    emit(value);
    emit(value);
    emit(value);
}

If you’re into Ruby this will be very familiar to you as a way of representing a sequence of values, and if you implement this kind of function it’s nice and easy, like using yield in a true generator.

The difference here from the Ruby pattern is that we’re discussing a pure function, rather than a method on an object. So we take a second argument as an input that can be used to determine what we emit. For example, we could assume our values will be arrays, and “flatten” them:

function flatten(emit, value) {
    value.forEach(emit); // JS array's forEach fits perfectly
}

If you called this three times passing an array each time, emit would get all the elements of the three arrays as a flat stream of elements (in separate calls), not knowing which arrays they were originally from.

Alternatively we can ignore the second parameter (not even bothering to declare it) and so define a pure source of data that emits its sequence of values when called:

function chatter(emit) {
    emit('hi');
    emit('whatever');
    emit('bye');
}

So far, so patterny. But the pain with these kinds of building blocks is that they don’t directly compose. An intermediate processor like flatten wants two arguments: where to emit its output and what value to process. But any preceding step just wants a function called emit that accepts one argument: a value.

We can take any two processors and turn them into a single processor that chains the two (put on your higher-order functional programming spectacles now):

function compose(first, second) {
    return function(emit, value) {
        return first(function(firstValue) {
            return second(emit, firstValue);
        }, value);
    };
}

(Note: I pass back the return value through the layers because it has a use that we’ll go into later.)

See how it works? compose creates and returns a new function. It weaves first and second together. The new wrapper receives the outer emit, and that is given to second, so that’s where the final results will be sent. The first function is passed another new function to emit to, which is where we call second.

That’s the beautiful version. But it means that we have allocate a function object every time a value is passed in. And let’s be crazy C++ programmers for a moment and assume that’s Just Not Good Enough. We could rewrite compose to be butt-ugly and yet still do what we want, without doing any dynamic allocation after initial setup:

function compose(first, second) {
    var secondEmit;
    function firstEmit(firstVal) {
        return second(secondEmit, firstVal);
    }
    return function(emit, value) {
        secondEmit = emit;
        return first(firstEmit, value);            
    };
}

Yes, EEWWW indeed. We use a local variable, secondEmit, in which we stash the outer emit as soon as we know it. And we create a firstEmit function once, so we can reuse it.

In simple scenarios this will behave the same as the beautiful version. But not always:

function troubleMaker(emit, value) {
    setInterval(function() { emit(value); }, 100);
};

var doubleTrouble = compose(troubleMaker, timesTwo);

doubleTrouble(function(value) { console.log(value); }, 3);
doubleTrouble(function(value) { document.write(value); }, 4);

Now we have the value 6 being printed to the console and the value 8 being appended to the document. Except… not if we use the second version of compose, because then the second call to foo would redirect both streams to the new destination (by updating that secondEmit local variable). What a mess.

Fortunately, we’re not C++ programmers! Phew! This doesn’t mean that we don’t care about performance. It just means that we do some measuring before going crazy about imaginary overhead. And on V8 I find that the “faster” version is approximately… 1% faster. Screw that. Let’s stick with the beautiful, easy-to-predict version.

The one other interesting feature of the pattern is what we can use the return value for: to signal that the receiver doesn’t want to receive any more data. To do this they return true. So our flatten example should actually look like this:

function flatten(emit, value) {
    return value.some(emit);
}

That way, we stop looping unnecessarily when there’s no need to keep going (because that’s what a JavaScript array’s some method does: quits and returns true when the function you gave it returns true).

So that’s the pattern. What more is there to say? Well, although writing a processor (or pure value generator) is very easy, because you just write imperative code and call emit whenever you like, it’s not so convenient to use them as components. Yes, we have combine to efficiently pipeline processors together, but there are a lot of “standard” things we tend to do on sequences where it would be nice not to have to write boilerplate code. Especially when writing tests (shudder).

To make this really easy and succinct, I’ve cooked up a little library called per:

npm install per

(Source code)

It’s reminiscent of jQuery, in that it puts a lightweight wrapper around something so that we can call useful operations on it. Most operations return another instance of the wrapper, so calls can be chained. The only entry point into the whole library is a single function called per, so in node (or browserify or webmake) you’d say:

var per = require('per');

In the browser you could just load per.js via the script tag and then you get a global per. Then you can wrap functions like this:

var numbers = per(function(emit) {
    for (var n = 0; n < 100; n++) {
        emit(n);
    }
});

The simplest methods on a per are ways to capture and return the emitted values:

var f = numbers.first(),    // f == 0
    l = numbers.last(),     // l == 99
    a = numbers.all()       // array [0... 99]

The function wrapped by a per is available in a property called forEach, so named because for a simple generator you can treat it a little like an array:

numbers.forEach(function(value) {
    console.log(value);
});

To compose functions, there is a per method which is exactly like the compose function we figured out above.

var odds = numbers.per(function(emit, value) {
                           if (value % 2) {
                               emit(value);
                           }
                       });

The above pattern is an example of a filter, which evaluates an expression to decide whether or not to forward a value. This is such an obvious pattern that we should have a built-in formalization of it:

var odds = numbers.filter(function(value) {
                              return value % 2
                          });

For extra brevity we support passing a string expression in terms of x:

var odds = numbers.filter('x%2');

Another common pattern is to transform a value and pass it on, which is captured by the map method:

var evens = numbers.filter('x%2').map('x-1');

How can we use the resulting combination? As always it has a forEach property, and because numbers doesn’t need a value parameter we only need to pass it a function to emit to (or we can use first, last or all).

There are operators skip and take that work like their corresponding Linq operators:

odds.skip(3).all()          // [7, 9, 11, 13...]
odds.skip(2).take(3).all()  // [5, 7, 9]

These are examples of stateful transformers, because they have an internal counter that controls their behaviour.

We can also construct an initial per by passing an array:

var a = per([1, 2, 3, 4, 5]);

console.log(a.first()); // 1
console.log(a.last()); // 5

You can even pass per a simple value and it will act as a function that merely emits that one value. For example that value might be something complex, such as a whole document that you’re going to pass through several parsing stages.

The above examples all use a fairly simple structure: the first call to per provides an initial value (or stream of values), then there is a chain of transformations, then the final step collects the results. This is fine if you want to process a stream of data in a single quick operation.

But what if you have a source of data that occasionally delivers you a value, and you want to send it through a pipeline of transformers? That is, rather than a single deluge you have more of a drip, drip, drip of information. You can prepare a chain of transformers:

var p = per(foo1).per(foo2)
                 .map(bar1)
                 .filter(bar2)
                 .listen(function(value) {
                     console.log(value);
                 });

The listen is used to inject a function in the pipeline that just receives values, but otherwise has no effect on the stream. So in fact it’s like per but you don’t have to write emit(value) – that just happens automatically.

So now you need a way to pass values into the front, for which you can use submit:

p.submit(5);
p.submit(41);
p.submit('hi');

Sometimes you need to direct the flow of information through multiple separate sections simultaneously. This is where multicast comes in handy:

var p = per(foo1).per(foo2).multicast(
    per(foo1).filter('!(x%2)').take(72).into(results1),
    per(foo2).filter('x%2').take(68).into(results2)
);

You can pass as many arguments as you like to multicast (they can be instances of per or plain transformer functions) and they will each receive every value. By the way, multicast is built on listen, so it doesn’t affect the stream, except that when all the recipients have returned true to indicate that they are full, then multicast itself will do the same.

But really the core idea is break up a complex multi-stage task into functions like this:

function transformer(emit, value) {
    // do something interesting and maybe call emit
    // a few times, passing forward values to the next stage
}

The per library merely provides some common ways to stitch such functions together.

Categories: Uncategorized Tags: ,

SICP-style Streams in JavaScript

October 29, 2013 1 comment

In the not-famous-enough book Structure and Interpretation of Computer Programs (Abelson & Sussman, or “The Wizard book”) we learn about streams.

A stream is a tempting variation on the old school Lisp style of linked list. To get a plain old list, we can set up objects like this:

var a = {
    value: 'apple',
    next: null
};

var b = {
    value: 'banana',
    next: a
};

var c = {
    value: 'cantaloupe',
    next: b
};

So here our whole list is represented by c, and we can loop through it and print all the fruits:

for (var i = c; i != null; i = i.next) {
    console.log(i.value);
}

So far, so boring. The idea with a stream is very simple. Instead of storing the next object in the next property, we store a function that, if called, will return the next object. That is, we make it lazy. Note that our loop would still look much the same:

for (var i = c; i != null; i = i.next()) {
    console.log(i.value);
}

The only difference is we call next() instead of just reading it. And to set up the objects we’d have to say:

var a = {
    value: 'apple',
    next: function() { return null; }
};

var b = {
    value: 'banana',
    next: function() { return a; }
};

var c = {
    value: 'cantaloupe',
    next: function() { return b; }
};

So far, so pointless. But the value of this does not come from silly hand-built examples. In real software you would use this to generate streams from other data sources, or from other streams. It’s like Linq-to-objects in C#, but the foundations are actually more purely functional, because even the iteration process involves only immutable objects, and so everything is repeatable, nothing is destroyed merely by using it. Part-way through a stream you can stash the current node, and come back to it later. It will still represent “the rest of the stream”, even though you already used it once.

It is this extreme level of generality that persuaded me try using streams in a real JavaScript library. I want to write a rich text editor for HTML Canvas (more of that in a later post, hopefully). So I would have streams of characters, streams of words, streams of lines, etc. It seemed to fit, and also I have a week off work and it’s fun to re-invent the wheel.

I start with an object representing the empty stream. This is nicer than using null, because I want to provide member functions on streams. If you had to check whether a stream was null before calling methods on it, that would suck mightily.

var empty = {};

function getEmpty() {
    return empty;
}

Then we need a way to make a non-empty stream:

function create(value, next) {
    return Object.create(empty, {
        value: { value: value },
        next: { value: next || getEmpty }
    });
}

It uses the empty stream as its prototype, and adds immutable properties for value and the next function. If no next function is passed, we substitute getEmpty. So calling create('banana') would make a stream of just one item.

One very handy building block is range:

var range = function(start, limit) {
    return start >= limit ? empty : create(start, function() {
        return range(start + 1, limit);
    });
};

Note the pattern, as it is typical: the next works by calling the outer function with the arguments needed to make it do the next step. And you may be thinking – AHGGHGH! Stack overflow! But no, as long as we loop through the stream using our for-loop pattern, the stack will not get arbitrarily deep.

Here’s a favourite of mine, so often forgotten about:

var unfold = function(seed, increment, terminator) {
    return create(seed, function() {
        var next = increment(seed);
        return next === terminator ? empty :
            unfold(next, increment, terminator);
    });
};

You call it with a seed value, which becomes the first value of the stream, and also an increment function that knows how to get from one value to the next, and a terminator value that would be returned by the increment function when it has no more values. So in fact you could implement range in terms of unfold:

var range = function(start, limit) {
    return unfold(start, function(v) { return v + 1; }, limit);
};

It can also turn a traditional linked list into a stream:

var fromList = function(front) {
    return unfold(front, function(i) { return i.next; }, null);
};

Groovy! Now we have several ways to originate a stream, so lets add some methods. Recall that empty is the prototype for streams, so:

empty.forEach = function(each) {
    for (var s = this; s !== empty; s = s.next()) {
        each(s.value)
    }
};

Nothing to it! And we can use forEach to get a stream into an array:

empty.toArray = function() {
    var ar = [];
    this.forEach(function(i) { ar.push(i); });
    return ar;
};

Of course, how could we live without the awesome power of map?

empty.map = function(mapFunc) {
    var self = this;
    return self === empty ? empty : create(mapFunc(self.value), function() {
        return self.next().map(mapFunc);
    });
};

Again, that lazy-recursive pattern. And now we can very easily implement converting an array into a stream:

var fromArray = function(ar) {
    return range(0, ar.length).map(function(i) {
        return ar[i];
    });
}

How about concat? Well, this has a slight wrinkle in that if the argument is a function, I treat it as a lazy way to get the second sequence:

empty.concat = function(other) {
    function next(item) {
        return item === empty
            ? (typeof other === 'function' ? other() : other)
            : create(item.value, function() { return next(item.next()); });
    }
    return next(this);
};

And with concat we can easily implement the holy grail of methods, bind (known as SelectMany in Linq and flatMap in Scala):

empty.bind = function(bindFunc) {
    var self = this;
    return self === empty ? empty : bindFunc(self.value).concat(function() {
        return self.next().bind(bindFunc);
    });
};

Think that one through – it’s a mind-bender. The bindFunc returns a sub-stream for each item in the outer stream, and we join them all together. So:

assertEqual(

    // ordinary array of numbers
    [1, 2, 3, 4, 5, 6, 7, 8, 9],

    // making that same array in an interesting way
    Stream.fromArray(
        [[1, 2, 3], [4], [5, 6], [], [7], [], [], [8, 9]]
    ).bind(function(ar) {
        return Stream.fromArray(ar);
    }).toArray()

);

Anyway, I wrote my rich text layout engine using this stream foundation, and (as I like to do with these things) I set up an animation loop and watched it repeatedly carry out the entire word-break and line-wrap process from scratch in every frame, to see what frame rate I could get. Sadly, according to the browsers’ profilers, the runtime was spending a LOT of time creating and throwing away temporary objects, collecting garbage and all the other housekeeping tasks that I’d set for it just so I could use this cool stream concept. Interestingly, in terms of this raw crunching through objects, IE 10 was faster than Chrome 30. But I know that by using a simpler basic abstraction it would be much faster in both browsers.

How do I know? Well, because I found that I could speed up my program very easily by caching the stream of words in an ordinary array. And guess what… I could just use arrays in the first place. I am only scanning forward through streams and I definitely want to cache all my intermediate results. So I may as well just build arrays. (Even though I haven’t started the rewrite yet, I know it will be way faster because of what the profilers told me).

So, for now, we say: fair well streams, we hardly knew ye.

Eventless Programming – Part 5: Async/Await and Throttling

March 3, 2013 2 comments

Posts in this series:

Last time we were able to throw a few more working features into our UI with relatively little effort, following very simple patterns. The result is that the UI automatically updates itself according to every change the user makes to the state of a control.

Which raises the question: what if that involves working a little too hard? If the user makes half a dozen changes in quick succession (say, they impatiently click the “Increase Radiation” button five times) then it makes little sense to do a ton of work to update the UI after every single click. It would be wiser to wait until they stop clicking it for half a second or something.

This is especially important when the updating work involves something really costly like downloading content over the network. And that’s another point – how do we integrate with asynchronous background calls? Oh no, my whole universe is starting to crumble!

Except it’s not. There are simple answers to both questions. Let’s start with the rapid-fire-recomputations problem. Recall that in our Notes view model, we cook up this:

SelectedNotes = Computed.From(
    () => AllNotes.Where(n => n.IsSelected.Value).ToList());

This means that every time you check or uncheck the selection CheckBox for a note, a Where/ToList is re-executed, and then various bits of UI infrastructure get rejigged as a result of SelectedNotes changing. In fact we can easily monitor how often this happens by adding this line:

Computed.Do(() => Debug.WriteLine("SelectedNotes: " + SelectedNotes.Value.Count()));

Now try clicking Select all and you’ll see the crazy results:

SelectedNotes: 0
SelectedNotes: 1
SelectedNotes: 2
SelectedNotes: 3
SelectedNotes: 4
SelectedNotes: 5
SelectedNotes: 6
SelectedNotes: 7
SelectedNotes: 8
SelectedNotes: 9
SelectedNotes: 10
SelectedNotes: 11
SelectedNotes: 12
SelectedNotes: 13
SelectedNotes: 14
SelectedNotes: 15
SelectedNotes: 16

Yes, as we loop through the notes setting IsSelected to true, every single time the SelectedNotes list is recomputed and so triggers UI updates. It may not be a problem in this little example, but it’s not to hard to see how it could become a problem if the UI update were more expensive.

So that’s why it needs to be this easy to fix it:

SelectedNotes = Computed.From(
    () => AllNotes.Where(n => n.IsSelected.Value).ToList()
).Throttle(100);

Yep, you just tack .Throttle(100) on the end, and it configures the Computed to wait until it hasn’t been notified of a change in its dependencies for at 100 milliseconds before acting on it; that is, it waits for stability. There’s actually a second parameter bool that lets you select between two behaviours:

1. true: wait for n milliseconds of stability (the default)
2. false: recompute no more than once every n milliseconds during instability

The default behaviour means that if the user keeps making changes back and forth indefinitely, the UI will never update. But of course in reality they don’t do that, so it’s usually fine. But if you wanted to show continuous feedback while (say) the user drags a slider, maybe the second behaviour would be more suitable. There’s no hard and fast rule here, which is why it’s an option.

Now let’s do some asynchronous downloading. Say we have a TextBox where the user types a URL, and we are going to download it automatically as they type. In reality they’d be adjusting a more restricted set of parameters than just a raw URL, of course, but it serves as an example. First we’d bind the TextBox to a Setable.

var urlText = Setable.From(string.Empty);
textBoxUrl.BindText(urlText);

Then from that we’d compute a Uri object, or null if the string isn’t yet a valid URI.

var uri = Computed.From(() =>
{
    Uri result;
    Uri.TryCreate(urlText.Value, UriKind.Absolute, out result);
    return result;
});

So far, so obvious. But it turns out the last part isn’t too surprising either:

var response = Computed.From(async () =>
{
    if (uri.Value == null)
        return "You haven't entered a valid url yet...";

    try
    {
        return await new HttpClient().GetStringAsync(uri.Value);
    }
    catch (HttpRequestException x)
    {
        return "Error: " + x.Message;
    }
}).Throttle(1000);

You just put the async keyword in front of the lambda you pass into Computed.From (and of course you should probably use Throttle, as I’ve done here). So what is response? It’s an IGetable, as you’d expect, but what type of Value does it hold? By inspecting the various return statements of our lambda, it’s pretty clear that it returns a string, but it is an async lambda so therefore it returns Task<string>.

But Computed.From has a special overload for Task<T> that takes care of await-ing the result value. So the upshot is that response is simply a IGetable<string> and can immediately be bound to a control:

textBoxResponse.BindText(response);

When used inside a UI application, async/await automatically ensures that if you launch a task from the UI thread and await it, the await will return on that same UI thread. So your UI code never has to worry about threads much at all, which is very reassuring (it’s not like the old days, when you had to manually use Control.Invoke to ensure that your UI updating operations happened on the right thread).

The complete source code for this series of articles is available here:

https://github.com/danielearwicker/eventless

It’s a Visual Studio 2012 solution.

Next time… well, actually I’m going to pause here for a while. The next step would be to see how we can apply these ideas to a more current UI framework like Windows Runtime. In the meantime, I hope it’s been interesting to see how the core ideas of Knockout are applicable in environments that have nothing to do with HTML and JavaScript, and it’s not actually about binding to the UI. The key thing is providing a highly productive way to transform your raw data. That’s what makes the binding part easy. So unless you make the data transformation easy, then you’ve just moved the problem without solving it. Computed observables are what make it possible to declare your data transformations, and so enable eventless programming. They are the secret sauce of Knockout.

Categories: Uncategorized Tags: , ,
Follow

Get every new post delivered to your Inbox.