{{ message }}

Instantly share code, notes, and snippets.

Last active Aug 24, 2021
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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 commented Aug 27, 2020

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

 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 `nd` is the pair `[, ]`, where I use `BigInt` to make sure there's no loss in precision and `reduce` so the fraction is always in lowest form (208).

 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.

 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 commented Aug 28, 2020

 Haha thx!

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

### 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 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 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.