Archive for January, 2022

Records and objects: both the same and different

Saturday, January 29th, 2022

I wrote in my most recent “daily” post about the choices involved in representing records in MIR and LIR, Warp’s intermediate languages. Since then, more questions occurred to me.

MIR has a simple type system and some internal typechecking, which is helpful. LIR erases most type details but does have an even simpler type system that distinguishes JavaScript Values from raw integers/pointers/etc. I already added a Record type to MIR; an alternative would have been to give the NewRecord operation the result type Object, reflecting that records are (currently) represented as objects, but I thought that more internal type checks are always a good thing. Without a separate Record type, it’s theoretically possible that compiler bugs could result in record fields being mutable (of course, there are still ways such bugs could arise even with MIR typechecking, but it’s one more thing that makes it less likely).

I realized there’s a problem with this approach: if I want to take option 2 in the previous post — translating FinishRecord into MIR by breaking it down into smaller operations like Elements, LoadFixedSlot, etc. — it’s not possible to generate type-correct MIR. These operations expect an Object as an operand, but I want them to work on Records.

The point of representing records as objects was (at least in part) to reuse existing code for objects, but that goal exists in tension with distinguishing records from objects and keeping the MIR type system simple. Of course, we could add some form of subtyping to MIR, but that’s probably a bad idea.

So orthogonally to the three options I mentioned in my previous post, there’s another set of three options:

  1. Add Record as an MIR type, like I started out doing; don’t re-use MIR instructions like Elements for records, instead making those operations explicit in CodeGenerator, the final translation from LIR to assembly.
  2. Don’t add any new MIR types; give NewRecord the result type Object and FinishRecord the argument and result types Object
  3. Compile away records when translating JS to MIR, adding whatever new MIR instructions are necessary to make this possible; in this approach, records would desugar to Objects and any operations needed to enforce record invariants would be made explicit,

Option 1 rules out some code re-use and loses some internal checking, since more of the heavy lifting happens in the untyped world. Option 2 allows more code re-use, but also loses some internal checking, since it would be unsound to allow every Object operation to work on records. Option 3 has the advantage that only the JS-to-MIR translation (WarpBuilder / WarpCacheIRTranspiler) would need to be modified, but seems riskier than the first two options with respect to type-correctness bugs — it seems like debugging could potentially be hard if records were collapsed into objects, too.

A colleague pointed out that MIR already has some types that are similar to other types, but where certain additional invariants need to be upheld, such as RefOrNull (used in implementing WebAssembly); this type is effectively equivalent to “pointer”, but keeping it a separate type allows for the representation to change later if the WebAssembly implementors want to. Record seems very similar; we want to avoid committing to the Object representation more than necessary.

My colleague also suggested adding an explicit RecordToObject conversion, which would allow all the Object operations to be re-used for records without breaking MIR typechecking. As long as there’s no need to add an ObjectToRecord conversion (which I don’t think there is), this seems like the most appealing choice, combined with option 1 above. There’s still potential for bugs, e.g. if a compiler bug generates code that applies RecordToObject to a record and then does arbitrary object operations on it, such as mutating fields. Ideally, RecordToObject would produce something that can only be consumed by reads, not writes, but this isn’t practical to do within MIR’s existing type system.

(All of the same considerations come up for tuples as well; I just started with records, for no particular reason.)

I don’t think there’s any way to know which approach is best without having a working prototype, so I’m just going to try implementing this and seeing what happens.

JavaScript is a very interesting language

Friday, January 28th, 2022

The other day I learned about indexed setters in JavaScript. It hadn’t occurred to me that you can do the following:

var z = 5;
Object.defineProperty(Array.prototype, 0, { set: function(y) { z = 42; }});

and the interpreter will happily accept it. This code mutates the global object called Array.prototype, overriding the (implicit) setter method for the property '0'. If I’m to compare this with a more conventional programming language (using C-like syntax for illustrative purposes), this would be like if you could write:

int n = /* ... */;
int[n] a;
a[0] = 5;

but the semantics of the last assignment statement could involve arbitrary side effects, and not necessarily mutating the 0th element of a, depending on the value of some global variable.

Most languages don’t allow you to customize this behavior. In JavaScript, it wasn’t an intentional design decision (as far as I know), but a consequence of a few design choices interacting:

  • Everything is an object, which is to say a bag of key-value pairs (properties)
  • What’s more, properties aren’t required to be simple lookups, but can be defined by arbitrary accessor and mutator functions (setters and getters) that can interact with global mutable state
  • Numbers and strings can be cast to each other implicitly
  • Inheritance is prototype-based, prototypes are mutable, and built-in types aren’t special (their operations are defined by prototypes that user code can mutate)

It’s not immediately obvious that together, these decisions imply user-defined semantics for array writes. But if an array is just a bag of key-value pairs where the keys happen to be integers (not a contiguous aligned block of memory), and if strings are implicitly coerced to integers (“0” can be used in place of 0 and vice versa), and if specifications for built-in types can be dynamically modified by anybody, then there’s nothing to stop you from writing custom setters for array indices.

To someone used to modern statically typed languages, this is remarkable. Programming is communication between humans before it’s communication with machines, and communication is hard when you say “rat” when you really mean “bear” but you won’t tell your conversation partners that that’s what you mean and instead expect them to look it up in a little notebook that you carry around in your pocket (and regularly erase and rewrite). If that’s what you’re going to do, you had better be prepared for your hiking partners to react with less alarm than is warranted when you say “hey, there’s a rat over there.” If your goal is to be understood, it pays to think about how other people will interpret what you say, even if that conflicts with being able to say whatever you want.

And if you’re trying to understand someone else’s program (including if that someone else is you, a month ago), local reasoning is really useful; mental static analysis is hard if random behavior gets overridden in the shadows. More concretely, the kind of dynamic binding that JavaScript allows makes it hard to implement libraries in user space. For example, if you want to build a linked list abstraction and use arrays as the underlying representation, the semantics of your library is completely dependent on whatever modifications anybody in scope has made to the meaning of the array operations. So that’s not an abstraction at all, since it forces people who just want to use your data structure to think about its representation.

This came up for me in my work in progress implementing the tuple prototype methods — the most straightforward ways to re-use existing array library code to build an immutable tuple abstraction don’t work, because of the ability users have to override the meaning of any property of an array, including length and indexed elements. The workarounds I used depend on the code being in a self-hosted library, meaning that it has to live inside the compiler. It makes sense for the record and tuple implementations to live inside the compiler for other reasons (it would be hard for a userland library to guarantee immutability), but you can easily imagine data structures that don’t need to be built into the language, but nevertheless can’t take full advantage of code re-use if they’re implemented as libraries.

Now, plenty of people who use and implement JavaScript agree with me; perhaps even most. The problem is that existing code may depend on this behavior, so it’s very difficult to justify changing the language to reject programs that were once accepted. And that’s all right; it’s a full employment guarantee for compiler writers.

Even so, I can’t help but wonder what code that depends on this functionality — and it must be out there — is actually doing; the example I showed above is contrived, but surely there’s code out there that would break if array setters couldn’t be overridden, and I’d like to understand why somebody chose to write their code that way. I’m inclined to think that this kind of code springs from dependence on prototype inheritance as the only mechanism for code reuse (how much JS imposes that and how much has to do with individual imaginations, I can’t say), but maybe there are other reasons to do this that I’m not thinking of.

I also wonder if anyone would stand up for this design choice if there was an opportunity to magically redesign JS from scratch, with no worries about backwards compatibility; I’m inclined to think there must be someone who would, since dynamic languages have their advocates. I have yet to find an argument for dynamic checking that wasn’t really just an argument for better type systems; if you’re writing a program, there’s a constraint simpler than the program itself that describes the data the program is supposed to operate on. The “static vs. dynamic” debate isn’t about whether those constraints exist or not — it’s about whether they exist only in the mind of the person who wrote the code, or if they’re documented for others to understand and potentially modify. I want to encourage people to write code that invites contributors rather than using tacit knowledge to concentrate power within a clique, and that’s what motivates me to value statically typed languages with strong guarantees. I’ve never seen a substantive argument against them.

But what’s easier than persuading people is to wear my implementor hat and use types as much as possible underneath an abstraction barrier, to improve both performance and reliability, while making it look like you’re getting what you want.

“The sad truth is, there’s very little that’s creative in creativity. The vast majority is submission–submission to the laws of grammar, to the possibilities of rhetoric, to the grammar of narrative, to narrative’s various and possible structurings. In a society that privileges individuality, self-reliance, and mastery, submission is a frightening thing.”
— Samuel R. Delany, “Some Notes for the Intermediate and Advanced Creative Writing Student”, in About Writing

Even when languages offer many degrees of freedom, most people find it more manageable to pick a set of constraints and live within them. Programming languages research offers many ways to offer people who want to declare their constraints ways to do so within the framework of an existing, less constrainted language, as well as inferring those constraints when they are left implicit. When it comes to putting those ideas into practice, there’s more than enough work to keep me employed in this industry for as long as I want to be.

Implementing records in Warp

Thursday, January 20th, 2022

Toward the goal of implementing records and tuples in Warp, I’m starting with code generation for empty records. The two modules I’ve been staring at the most are WarpBuilder.cpp and WarpCacheIRTranspiler.cpp.

While the baseline compiler translates bytecode and CacheIR directly into assembly code (using the MacroAssembler), the optimizing compiler (Warp) uses two intermediate languages: it translates bytecode and CacheIR to MIR; MIR to LIR; and then LIR to assembly code.

As explained in more detail here, WarpBuilder takes a snapshot (generated by another module, WarpOracle.cpp) of running code, and for each bytecode, it generates MIR instructions, either from CacheIR (for bytecode ops that can have inline caches), or directly. For ops that can be cached, WarpBuilder calls its own buildIC(), method, which in turn calls the TranspileCacheIRToMIR() method in WarpCacheIRTranspiler.

A comment in WarpBuilderShared.h says “Because this code is used by WarpCacheIRTranspiler we should generally assume that we only have access to the current basic block.” From that, I’m inferring that WarpCacheIRTranspiler maps each CacheIR op onto exactly one basic block. In addition, the addEffectful() method in WarpCacheIRTranspiler enforces that each basic block contains at most one effectful instruction.

In the baseline JIT implementation that I already finished, the InitRecord and FinishRecord bytecodes each have their own corresponding CacheIR ops; I made this choice by looking at how existing ops like NewArray were implemented, though in all of these cases, I’m still not sure I fully understand what the benefit of caching is (rather than just generating code) — my understanding of inline caching is that it’s an optimization to avoid method lookups when polymorphic code is instantiated repeatedly at the same type, and in all of these cases, there’s no type-based polymorphism.

I could go ahead and add InitRecord and FinishRecord into MIR and LIR as well; this would be similar to my existing code where the BaselineCacheIRCompiler compiles these operations to assembly. To implement these operations in Warp, I would add similar code to CodeGenerator.cpp (the module that compiles LIR to assembly) as what is currently in the BaselineCacheIRCompiler.

But, MIR includes some lower-level operations that aren’t present in CacheIR — most relevantly to me, operations for manipulating ObjectElements fields: Elements, SetInitializedLength, and so on. Using these operations (and adding a few more similar ones), I could translate FinishRecord to a series of simpler MIR operations, rather than adding it to MIR. To be more concrete, it would look something like:


FinishRecord r

== WarpCacheIRTranspiler ==>


e = Elements r
Freeze e
sortedKeys = LoadFixedSlot r SORTED_KEYS_SLOT
sortedKeysElements = Elements sortedKeys
CallShrinkCapacityToInitializedLength sortedKeys
SetNonWritableArrayLength sortedKeysElements
recordInitializedLength = InitializedLength r
SetArrayLength sortedKeysElements recordInitializedLength
CallSort sortedKeys

(I’m making up a concrete syntax for MIR.)

This would encapsulate the operations involved in finishing a record, primarily sorting the keys array and setting flags to ensure that the record and its sorted keys array are read-only. Several of these are already present in MIR, and the others would be easy to add, following existing operations as a template.

The problem with this approach is that FinishRecord in CacheIR would map onto multiple effectful MIR instructions, so I can’t just add a case for it in WarpCacheIRTranspiler.

I could also push the lower-level operations up into CacheIR, but I don’t know if that’s a good idea, since presumably there’s a reason why it hasn’t been done already.

To summarize, the options I’m considering are:

  1. Pass down InitRecord and FinishRecord through the pipeline by adding them to MIR and LIR
  2. Open up FinishRecord (InitRecord isn’t as complicated) in the translation to MIR, which might involve making FinishRecord non-cacheable altogether
  3. Open up FinishRecord in the translation to CacheIR, by adding more lower-level operations into CacheIR

I’ll have to do more research and check my assumptions before making a decision. A bigger question I’m wondering about is how to determine if it’s worth it to implement a particular operation in CacheIR at all; maybe I’m going about things the wrong way by adding the record/tuple opcodes into CacheIR right away, and instead I should just be implementing code generation and defer anything else until benchmarks exist?

Tuple prototype methods ☑️

Tuesday, January 18th, 2022

It’s been a little while. But since my last post, Nicolò’s patches implementing records and tuples in SpiderMonkey landed, which means that I was able to submit my patches implementing the prototype methods for the Tuple type. That code is awaiting review.

Some initial review comments that I received focused on concerns about changing existing code that implements Arrays. Immutable and mutable sequences support a lot of the same operations, so it made sense to re-use existing Array code in SpiderMonkey rather than reinventing the wheel. Section 8.2.3 of the Records nad Tuples proposal lists the tuple prototype methods and, for many of them, specifies that the behavior should be the same as what’s already specified for the equivalent Array method.

In some cases, code reuse required changing existing code. Built-in JavaScript types can have their methods implemented in SpiderMonkey in two different ways: self-hosted (implemented in JavaScript as a library) or native (implemented inside the compiler, in C++). I implemented most of the tuple methods as self-hosted methods, which can easily call existing self-hosted methods for arrays. In some cases, I thought a native implementation would be more efficient: for example, for the toReversed() method, which returns a reversed copy of a given tuple. (Since tuples are immutable, it can’t reverse in-place.) There’s already an efficient C++ implementation of reverse for arrays, and because of how tuples are currently implemented in SpiderMonkey (using the NativeObject C++ type, which is the same underlying type that represents arrays and most other built-in types), making it work for tuples as well just required changing the method’s precondition, not the implementation. However, the maintainers were reluctant to allow any changes to the built-in array methods. I replaced that with a straightforward self-hosted implementation of toReversed(); it seems a shame to not take advantage of existing optimized code, but perhaps I was falling prey to premature optimization. We don’t have any performance benchmarks for code that uses tuples yet, and without profiling, it’s impossible to know what will actually be performance-critical.

While I await further review, I’ll be learning about WarpMonkey, the next tier of optimizing JIT in SpiderMonkey. The work I described in my previous posts was all about implementing records and tuples in the baseline compiler, and that work is finished (I’ll hold off on submitting it for review until after the prototype methods code has been accepted). I expect this to be where the real fun is!