Typical implementations of Javascript and other high-level languages don't store objects as hash tables. (although that is the mental model they expose to users) Instead, objects are stored as flat buffers, with a side field-to-offset table (usually called the "shape" or "dynamic type") that's shared by all the objects with the same shape. To avoid looking up the side table they also keep some…
In my linear algebra course in college I learned about least squares regression, where it wasn't very motivated outside of "we square the error because it makes error non-negative, really penalizes outliers, and it's easy to compute". Recently, I learned about maximum likelihood estimation, where we pick parameters for a model based on whatever maximizes the likelihood of the observed data. For…
Consider this generator, which implements the Taylor series for arctan(1): function* piTaylor() { let res = 0; let sign = 1; for (let i = 1; true; i += 2) { res += sign / i; sign = -sign; yield 4 * res; } } This function generates successive approximations of pi using the formula: π/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ... Each term alternates between positive and negative, and we multiply the result…
Part 1: expressions, arithmetic Part 2: statements, control flow In my first few attempts at writing a compiler, a big hurdle was compiling control flow (conditionals, loops, etc). I think this stemmed from the fact that the a lot of the common advice that's floating around the internet is for writing an optimizing compiler, so I would hear things like 'static single-assignment', 'control flow…
Background: Fenwick Tree The Fenwick tree is a data structure that is commonly used to perform prefix sum queries and point updates on some array A. Leaving the issue of updates aside the general idea is that, for each index i, it stores the sum of A over the range (i−f(i),i] (yes, that's an open-closed interval), where f(i) returns the least significant bit of i. To compute a prefix sum over…
Part 1: expressions, arithmetic Part 2: statements, control flow Ever since I was a teenager I wanted to create my own systems programming language. Such a programming language would certainly have to be compiled to native code, which meant I'd have to write a compiler. Even though I managed to write several half-working parsers, I'd always fail at the stage of generating assembly code, as the…
Suppose that you want to create a brand new programming language that will change the world. Or that you want to auto-formatter that gets indentation just right . Or maybe you want to write a pre-processor for an existing language, to hack some missing feature into it . Whatever it may be, there are many reasons to write programs that manipulate other programs as data and the first step is to…
Problem Suppose we have two arrays a[1], a[2], ..., a[n] and b[1], b[2], ..., b[m] , and a predicate P(a, b) . For each index i (1 ≤ i ≤ n) we want to find the least j (1 ≤ j ≤ m) such that P(a[i], b[j]) is true. Naive Solution With the information we have, we can't do much. The optimal solution given what we know so far is: Iterate over every i, then over every j, until we find a match. fn…
Estaba hablando con un amigo y me preguntó sobre el uso de FFT en programación competitiva. El texto de abajo surgió en esa conversación. Fourier La clave es que hay muchos problemas que se pueden resolver usando esta función: // tenemos dos bolsas A y B con bolitas con números naturales // queremos saber qué numeros se pueden formar tomando una bolita de A y una de B y sumando sus numeros // //…
Un amigo tenía algunas dudas sobre perfect forwarding en C++, y terminé escribiendo esta explicación. value categories Antes de hablar sobre los detalles de la deduccion de tipos en C++ es fundamental mencionar las value categories. En C++ hay dos tipos de referencias. Referencias a lvalues y referencias a rvalues. Llamemoslas L-refs y R-refs, respectivamente. Normalmente, las L-refs apuntan a…
When you write a type checker, there are a few ways one might go about it. First, you can do it outside-in: given an expression and a type, you check that the expression matches that type by inferring the type that the sub expressions should have, then checking that they do. This operation is typically called checking. Here, type information comes from the outside, and it flows into the…
In an ICPC-style contest, 3-person teams compete in programming challenges, and they are allowed to bring a "notebook" into the contest. A notebook is a printable document, that teams usually fill with implementations of common algorithms, so that they are able to pull them out if needed in a contest. The other day, my ICPC team and I participated in one such contest (though an unofficial one) and…
Whether it be due to numerical precision, image encoding, or logic issues, when writing or hacking on a path tracer, there tends to be a lot of duds. This is not something to be discouraged about, but a natural part of the process. (If anything, that there is any reasonable looking output at all, already means that you are 90% of the way there!) In no particular order, here are some early images…
I am working on a small project that involves a bunch of geometry algorithms. Since it's something I'm doing for fun, I'm rolling my own implementations of every algorithm I use, in modern C++. Right now, I needed a convex hull algorithm that was going to be used for a small amount of vertices (think up to 30 or so). A convex hull is the smallest convex polygon that contains every point in a set.…
Template meta programming has been a mainstay in C++ for years. It provides a system for compile-time polymorphism and generic programming with capabilities not present in many other languages, enriching the language and bringing new opportunities for expressiveness to the table. Why doesn't the C language have such capabilities? Well, besides the fact that C++'s templates were added to the…