Skip to content

Instantly share code, notes, and snippets.

@pyrocto
Last active Aug 24, 2021
Embed
What would you like to do?
A modest proposal for operator overloading in JavaScript
/*
It is a melancholy object-oriented language to those who walk through
this great town or travel in the country, when they see the JavaScript
programs crowded with method calls begging for more succinct syntax.
I think it is agreed by all parties, that whoever could find out a
fair, cheap and easy method of making these operators sound and useful
members of the language, would deserve so well of the publick, as
to have his statue set up for a preserver of the nation. I do therefore
humbly offer to publick consideration a pure JS library I've written
for overloading operators, which permits computations like these:
Complex numbers:
>> Complex()({r: 2, i: 0} / {r: 1, i: 1} + {r: -3, i: 2}))
<- {r: -2, i: 1}
Automatic differentiation:
Let f(x) = x^3 - 5x:
>> var f = x => Dual()(x * x * x - {x:5, dx:0} * x);
Now map it over some values:
>> [-2,-1,0,1,2].map(a=>({x:a,dx:1})).map(f).map(a=>a.dx)
<- [ 7, -2, -5, -2, 7 ]
i.e. f'(x) = 3x^2 - 5.
Polynoomials:
>> Poly()([1,-2,3,-4]*[5,-6]).map((c,p)=>''+c+'x^'+p).join(' + ')
<- "5x^0 + -16x^1 + 27x^2 + -38x^3 + 24x^4"
Big rational numbers (with concise syntax!):
// 112341324242 / 22341234124 + 334123124 / 5242342
// > with(Rat){Rat()(n112341324242d22341234124 + n334123124d5242342).join(' / ')}
// "2013413645483934535 / 29280097495019602"
The implementation is only mildly worse than eating babies.
*/
((global) => {
// Increase for more complicated fancier expressions
var numVars = 5;
var vars = Array.from(Array(numVars)).map((_,i)=>i);
var randoms = vars.map(() => Math.random());
var table = {};
// n is number of internal nodes
// f is a function to process each result
var trees = (n, f) => {
  // h is the "height", thinking of 1 as a step up and 0 as a step down
  // s is the current state
  var enumerate = (n, h, s, f) => {
    if (n === 0 && h === 0) {
      f(s + '0');
    } else {
      if (h > 0) {
        enumerate(n, h - 1, s + '0', f)
      }
      if (n > 0) {
        enumerate(n - 1, h + 1, s + '1', f)
      }
    }
  };
  enumerate(n, 0, '', f);
};
var toFunction = (s, pos, opCount, varCount) => {
if (s[pos] == '0') {
return [`x[${varCount}]`, pos + 1, opCount, varCount + 1];
}
var left, right, op;
pos++;
op = `ops[${opCount}]`;
[left, pos, opCount, varCount] = toFunction(s, pos, opCount + 1, varCount);
[right, pos, opCount, varCount] = toFunction(s, pos, opCount, varCount);
return [`${op}(${left},${right})`, pos, opCount, varCount];
};
var add = (x,y) => x+y; add.toString = ()=>'+';
var sub = (x,y) => x-y; sub.toString = ()=>'-';
var mul = (x,y) => x*y; mul.toString = ()=>'*';
var div = (x,y) => x/y; div.toString = ()=>'/';
var round = (x) => {
var million = Math.pow(2,20);
return Math.floor(x * million) / million;
};
var populate = (expr, ops, opCount) => {
if (ops.length == opCount) {
var result;
var order=[];
var x = vars.map(y => ({
valueOf:()=>{
order.push(y);
return randoms[order.length - 1];
}
}));
with ({ops, x}) { result = round(eval(expr)); }
table[result] = {ops: ops.map(x => '' + x), expr, order};
} else {
populate(expr, ops.concat(add), opCount);
populate(expr, ops.concat(sub), opCount);
populate(expr, ops.concat(mul), opCount);
populate(expr, ops.concat(div), opCount);
}
};
var allExprs = (s) => {
var [expr, , opCount, ] = toFunction(s, 0, 0, 0);
populate(expr, [], opCount);
};
vars.forEach(x=>trees(x, allExprs));
var makeContext = (constr, opTable) => () => {
// Set up values array
var V = [];
// Install temporary valueOf
var valueOf = constr.prototype.valueOf;
constr.prototype.valueOf = function () {
return randoms[V.push(this) - 1];
};
// Return function expecting key
return (key) => {
var {ops, expr, order} = table[round(+key)];
constr.prototype.valueOf = valueOf;
var result;
var index = 0;
var W = [];
V.forEach((v, i) => W[order[i]] = V[i]);
with ({ops: ops.map(x => opTable[x]), x: W}) { result = eval(expr); }
V = [];
return result;
};
};
global.makeContext = makeContext;
})(this);
var Complex = makeContext(Object, {
'+': (x, y) => ({r: x.r + y.r, i: x.i + y.i}),
'-': (x, y) => ({r: x.r - y.r, i: x.i - y.i}),
'*': (x, y) => ({r: x.r * y.r - x.i * y.i, i: x.r * y.i + x.i * y.r}),
'/': (x, y) => {
const norm = y.r**2 + y.i**2;
return {r: (x.r * y.r + x.i * y.i) / norm, i: (x.i * y.r - x.r * y.i) / norm};
}
});
var Dual = makeContext(Object, {
'+': (a, b) => ({x: a.x + b.x, dx: a.dx + b.dx}),
'-': (a, b) => ({x: a.x - b.x, dx: a.dx - b.dx}),
'*': (a, b) => ({x: a.x * b.x, dx: a.x * b.dx + a.dx * b.x}),
'/': (a, b) => ({x: a.x / b.x, dx: (a.dx * b.x - a.x * b.dx) / (b.x ** 2)})
});
var Poly = makeContext(Array, {
'+': (a, b) => (a.length >= b.length ? a.map((x,i) => x + (b[i]?b[i]:0)) : b.map((x,i) => x + (a[i]?a[i]:0))),
'-': (a, b) => (a.length >= b.length ? a.map((x,i) => x - (b[i]?b[i]:0)) : b.map((x,i) => x - (a[i]?a[i]:0))),
'*': (a, b) => {
var result = [];
for (var i = 0; i < a.length; ++i) {
for (var j = 0; j < b.length; ++j) {
result[i+j] = result[i+j] ? result[i+j] : 0;
result[i+j] += a[i] * b[j];
}
}
return result;
},
'/': (a, b) => { throw new Error('Not implemented'); }
});
var Str = new Proxy(makeContext(Array, {
'+':(a,b) => [a[0]+b[0]],
'*':(a,b) => [Array.from(Array(b[0])).map(x=>a[0]).join('')]
}), {
has (target, key) { return key.match(/^[a-z0-9A-Z_]+$/) && key !== 'Str'; },
get(target, prop, receiver) {
if (typeof prop == 'string') {
return [prop];
} else {
return target[prop];
}
}
});
function reduce(numerator,denominator) {
var gcd = function gcd(a,b){
return b ? gcd(b, a%b) : a;
};
gcd = gcd(numerator,denominator);
return [numerator/gcd, denominator/gcd];
}
var numDenom = /^n([0-9]+)d([0-9]+)$/;
var Rat = new Proxy(makeContext(Array, {
'+':(a,b) => reduce(a[0]*b[1] + a[1]*b[0], a[1]*b[1]),
'-':(a,b) => reduce(a[0]*b[1] - a[1]*b[0], a[1]*b[1]),
'*':(a,b) => reduce(a[0]*b[0], a[1]*b[1]),
'/':(a,b) => reduce(a[0]*b[1], a[1]*b[0])
}), {
has (target, key) { return !!key.match(numDenom); },
get(target, prop, receiver) {
if (typeof prop == 'string') {
var m = prop.match(numDenom);
return reduce(BigInt(m[1]), BigInt(m[2]));
} else {
return target[prop];
}
}
});
@fuunnx

This comment has been minimized.

Copy link

@fuunnx fuunnx commented Aug 27, 2020

Sir, I don't get how it works, I need explanations 🤯

@pyrocto

This comment has been minimized.

Copy link
Owner Author

@pyrocto pyrocto commented Aug 27, 2020

There are four evil kludges at play here. The first is one that various others have discovered: the arithmetic operators do coersion on their operands, and if the operand is an object (as opposed to a primitive), then its valueOf method gets invoked. So the question becomes, "What value should valueOf return?" The result of coersion has to be a number or a string, and multiplication only works with numbers, so we have to return a number.

People have tried packing data about the operand into JavaScript's IEEE 754 floats, but they only hold 64 bits. So if you have a Point(x, y) class, then you can represent it as the number x * 10**12 + y or some such, but the points have much more limited precision and you can only add and subtract them. This is almost useless for polynomials.

The second trick is to have the valueOf method store this in a table (line 123) and use the result of the expression to figure out what to do with the values in the table. Others have also discovered this before. This way we get to store all the information about the objects we're manipulating, but it's still not clear what number to return. This guy uses the number 3 to be able to do a single subtraction, a single division, multiple additions, or multiple multiplications.

The third trick allows us to use arbitrary expressions. It depends on an observation from abstract algebra: numbers chosen uniformly at random from the unit interval are transcendental with probability 1. That implies there are no two fundamentally different arithmetic expressions using each random number once and +-*/ that have the same value. With IEEE 754 floats, I can uniquely distinguish about 2**64 different expressions by their result. So I run through all possible arithmetic expressions in numVars variables (lines 49-66 enumerate the structure of the AST while 68-78 turn it into JS), evaluate the expression with the variables set to the random numbers, and store the expression in a table under the result (90-113).

There's a complication in that JavaScript has operator precedence: in the expression 3-4*5, the multiplication is done first and then the subtraction. So in evaluating the expression, I have to keep track of the order in which objects get coerced (96-97). When I get the coerced result of an expression, I look up the original expression in the table (126-127), permute the objects based on the order they get coerced (132), and then execute the expression with the appropriate methods corresponding to +-*/ (133).

The last trick gets used in Str and Rat above. In a with block of the form with(obj){ body }, if a variable name mentioned in body is a property name of obj, then the property is returned. I use a Proxy for obj (174, 198) with handlers that claim every possible property of a certain form (the has method on lines 178 and 204). Str claims to have all properties that match the regex /^[a-z0-9A-Z_]+$/ other than Str, while Rat claims to have all properties that match the regex /^n([0-9]+)d([0-9]+)$/ (a numerator followed by a denominator). When asked what value those variables have, the Proxy responds with the appropriate data structure: Str says the value of prop is [prop] (181), while Rat says the value of n<numerator>d<denominator> is the pair [<numerator>, <denominator>], where I use BigInt to make sure there's no loss in precision and reduce so the fraction is always in lowest form (208).

@pyrocto

This comment has been minimized.

Copy link
Owner Author

@pyrocto pyrocto commented Aug 27, 2020

By the way, the title and the comment text at the top come from A Modest Proposal by Johnathan Swift. It's a satirical piece drawing attention to the plight of the poor Irish in which he proposes that Britain adopt cannibalism and that the poor should sell their babies to butchers in order to have enough money to feed their families and afford a place to live.

@fuunnx

This comment has been minimized.

Copy link

@fuunnx fuunnx commented Aug 28, 2020

It's clearer, that's clever ! Now I have the taste of babies in mouth, thank you 😄

Didn't know of this piece, I like it !

@pyrocto

This comment has been minimized.

Copy link
Owner Author

@pyrocto pyrocto commented Aug 28, 2020

Haha thx!

@nullhook

This comment has been minimized.

Copy link

@nullhook nullhook commented Dec 24, 2020

This looks clever. Can valueOf differ per operator and can it handle constants?

@pyrocto

This comment has been minimized.

Copy link
Owner Author

@pyrocto pyrocto commented Dec 24, 2020

This looks clever.

Thanks!

Can valueOf differ per operator

No, it's the same for all objects (see line 122). The only difference is how the context (Complex, Dual, Poly, etc.) processes the result from valueOf().

and can it handle constants?

It can, but you have to think of them as needing an explicit cast. For example, you have to represent the complex number 2 as {r:2, i:0}, so you might want to write a function like let cast=x=>({r:x, i:0}) to do the cast from reals to the type the context expects.

@dy

This comment has been minimized.

Copy link

@dy dy commented Aug 24, 2021

That proposal has a lot of potential.
From what I can see:

  • use BigInt to allow any-precision ops
  • pipe operator a | b | c
  • units with (units) { 10em + 10px }
@pyrocto

This comment has been minimized.

Copy link
Owner Author

@pyrocto pyrocto commented Aug 24, 2021

It would be straightforward to wrap BigInts to do fixed-point arithmetic, but for irrational numbers, you'd probably want a stream-based implementation. This gist could help you keep the client code cleaner.

I suppose it might be possible to overload pipe if you generate random numbers in the range [0, 2^32) rather than in [0, 1). If you used the latter, the random numbers would all be coerced to 0.

For computing with units, the symbols have to be valid identifiers, so you'd either have to put the unit before the quantity:
with (units) { em10 + px10 }
or prefix the quantity with some symbol like $ or _ or something :
with (units) { $10em + $10px }

But all this is a big joke; the real tc39 operator overloading proposal can be found here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment