## Friday, September 04, 2015

### Simulating any biased coin with a fair coin

I recently discovered this cutie on the web.
1. Using a fair coin, you can simulate a coin with any desired bias.
2. The expected number of tosses you need to do this is just two!
Preliminaries: let's count heads as 1, tails as 0, and we'll write the desired probability of heads in our simulated biased coin as the binary fraction p = 0.p_1p_2p_3... where p_i is the ith binary digit of the probability p.

Procedure: toss the fair coin, matching toss number k against p_k.  When the toss differs from p_k, return p_k as the result and stop.

Proof this works: the probability of seeing a "head" (i.e., a 1) in this process is P(head) = sum_(1<=k)p_k/2^k which is exactly p by definition.

Expected number of tosses: the expected number of tosses is E(k) = sum_(1<=k)k/2^k.  Now, we can rewrite this two different ways.  One way, we can do a "change of variable" from k to k+1, giving E(k) = sum_(0<=k)(k+1)/2^(k+1).  Let's call this form, A.  Another way, we can take the original equation and add a harmless zero term to the front of the sum, giving E(k) = sum_(0<=k)k/2^k.  Let's call this form, B.  Now, since E(k) = A = B we must have
E(k) = 2A - B
qquad = 2sum_(0<=k)(k+1)/2^(k+1) - sum_(0<=k)k/2^k
qquad = sum_(0<=k)(k+1)/2^k - sum_(0<=k)k/2^k
qquad = sum_(0<=k)(k + 1 - k)/2^k
qquad = sum_(0<=k)1/2^k
qquad = 2.

I find it delightful that the expected number of tosses is independent of the target probability!

## Sunday, December 14, 2014

### Rawb - efficient Knockout-friendly web controls

I've released Rawb (http://rawb.codeplex.com), a library of efficient web controls for use with Knockout (http://www.knockoutjs.com). The grid control is a particularly nice piece of work, in my opinion.

### Spanner released

I thought I'd posted this months ago! Oh, well: Spanner is now available for download from http://spanner.codeplex.com . A tutorial site with documentation can be found at http://www.spannerjs.com . In case you have forgotten, Spanner is my attempt to provide an integrated scheme for writing web applications as embedded domain-specific languages in C#. It's rather nice, if I say so myself.

## Monday, February 10, 2014

### Ahh, JavaScript, how I loathe thee.

Okay, to be fair, this complaint isn't really about JavaScript so much as the JavaScript/DOM interface. Specifically, the ordering of event handlers.

Whenever one finds oneself struggling with interacting event handlers, the order of which is not consistent across browsers, one ends up doing something horrid like this:

    myEventHandler = function (evt) {
setTimeout(function () {
... my intended side-effect ...
},
100 // Magic delay in milliseconds,
// which we pray will force the
// right order of events.
};


Bleh. A thousand times, bleh. Please write in if you have a good solution to this problem.

## Tuesday, October 29, 2013

### How to find the parameter names of a C# lamba

Last night I tweaked Spanner so function parameter names in the generated JavaScript match the parameter names of the C# Func from which they were generated. I had a horrible feeling I'd have to stoop to using and parsing Expression values, but it turns out that isn't necessary at all. Behold, the answer: And...

## Monday, October 14, 2013

### Spanner is released!

I have, this day, made Spanner available on Codeplex. It's an alpha release, which means I intend to make minor changes to the design and major improvements to the documentation, add tutorials, and all that. The ToDoMVC example is temporarily broken. Fixing that is first on my (real) to-do list -- as my old PhD supervisor used to say to me, beware of showing an idiot something half finished.

## Friday, September 20, 2013

### A taste of Spanner

Spanner is the name of my soon-to-be-released open source statically typed domain specific language for building Knockout web applications in C#. Here is a very brief sample, which I will let stand by itself: Build and run this program and you get the following web page:
+ = which is .

Now, this is a fairly trivial example, but it illustrates some of the key points about Spanner.
• A Spanner program is completely, strongly, statically typed -- it's just C#. As soon as you make a type error in your program, Visual Studio will list the problem areas in the error window. The generated JavaScript code cannot contain type errors (well, up to the point where you start including third-party JavaScript libraries). This alone makes Spanner valuable.
• Strong typing means you get strong refactoring support from Visual Studio.
• You don't need special syntax for expressions: you can freely use +, -, /, *, etc.
• Because you are writing in C#, you have all the usual mechanisms for abstraction (i.e., functions!). You are not limited to the ad hoc hodge podge of compromises necessary in ordinary HTML + JavaScript development.
• You don't need special syntax for Knockout observables -- Spanner knows which variables are observables and which are plain old JavaScript variables and generates the appropriate code for reading and writing them. Indeed, observables are much more transparent in Spanner than they are in JavaScript.
• All the documented, well-typed parts of Knockout are supported.
• Every HTML element and every well-typed JavaScript construct is represented by a correspondingly named Spanner function.
• The correspondence between HTML attributes and view model variables is transparent -- you never need to embed code or identifiers in HTML strings. This is another key benefit of Spanner.
• Spanner handles all the usual types (int, double, string, arrays, enums, POCOs). There are no special cases.
• Spanner supports modularisation via view/view-models pairs, "global" models (i.e., libraries), strongly typed templates, and use of arbitrary third-party libraries.
• Spanner will sort all your code dependencies for you and emit modules and variable definitions in the right order.
• Spanner provides mechanism rather than policy. As long as you are happy using Knockout for your observables, it is entirely up to you how to structure your web application.
• Spanner makes it easy to mix hand-written JavaScript with Spanner-generated JavaScript. The two worlds work quite comfortably together, provided the non-Spanner JavaScript has a well-typed API (hah!).
• Building happens in the blink of an eye. If you are used to waiting ages for MVC to do its thing, Spanner's instant turn-around will be a relief.
• Normal web development is excruciating for anyone used to more sophisticated languages. You spend so much of your working day chasing down trivial bugs and the primitive languages involved practically force you to turn your code into a mess of expedient short cuts. I wrote Spanner as a reaction, to see how far I could Do It Right while using a mainstream programming language (trust me, if we all migrated to F# or Haskell, Spanner would look a lot less cunning).
• Using Spanner will clearly make you more attractive to members of your favourite sex.
Watch this space. I have the code completed, tested, and documented. I am just putting together a web site with a tutorial and some demonstrations (as my old PhD supervisor said to me, never show an idiot something half finished :-)). Being a family man with a full time job, this may take a week or three...

## Thursday, September 19, 2013

### Damn you, C# !

For some time now I have been working on a pet project: a domain specific language implemented as a set of C# types intended to support the creation of complex single-page web applications, generating everything including the HTML, CSS, and JavaScript.  I am more than a little pleased with the result and will be making it open source any day now.  [My motivation for this is that I've spent the last two years immersed in the web world, which is clearly a brilliant idea implemented by psychopaths and idiots -- I will rant in more detail on this topic at some later point.]

Speaking of points, back to the subject in hand.

My DSL is, in large part, based around a type Expr<T> denoting a JavaScript expression of type T.  To make life convenient, I have added implicit casts from string to Expr<string> (etc.) and overridden the standard operator set {+, -, *, /, %, ==, !=, <, <=, etc.}.  So far so good.  I can write expressions such as x + (y * z) in my DSL directly in C# where x, y, and z are Expr<int> or Expr<double>, and so forth.

There are two flies in the ointment.

Ointment fly number 1: you can't freely overload the indexing operator.

I would like to be able to write xs[i] to denote the JavaScript expression for the ith element of the array xs.  Tragically, I can't do this.  Here's what the implementation might look like if you could:

public static Expr<T>this[Expr<int>i] { get { return ...; } }

But, noooo, I can't do this because this has to be defined in the Expr<T> class and that means this has type Expr<T> rather than Expr<T[]>, which is what is required.  Instead I have to provide some awkward named function, Ith(xs, i) to do the job.  Ugh.

Damn you, C# !

Ointment fly number 2: you can't freely overload the << operator.

I would like to express assignments in my DSL as x := y or x <- y, but I can't do that because C# won't let you create new infix operators.  Hmm, well, I reckon << is hardly ever used, so maybe I could hijack x << y instead for assignment.  It has as slightly tainted C++ flavour, but it's the best thing on offer.

But, noooo, I can't do this because if I write

public static Act operator <<(Var<T>x, Expr<T>e) { ... }

I get a complaint from the C# compiler that not only is the first argument not of type Expr<T> (the hosting class), but the second argument is not a plain old int!  Great googly moogly, what were they thinking?  Even if I wanted to implement << as bitwise left shift in my little DSL, I couldn't because of the idiotic second constraint.  Instead I have to provide some awkward named function, Set(x, e) to do the job.  Ugh.

Damn you, C# !

Why would you expect any of this to work?

I just so happens I spent most of my life doing functional programming (I taught Haskell, I worked on the Mercury language team for a very long time).  In sane, modern languages (i.e., ones invented since ~1970 by people who actually passed a few hard exams -- OO, I am not talking about you) this sort of thing is done as a matter of course.

Arghghghghghgh.