49. Representing values

One stack, many kinds of thing

The stack machine from chapter 47 held numbers, and only numbers. That made OP_NEGATE easy: pop, flip the sign, push. Now look at what real Drip programs push:

print -(1 + 2) == nil;
print !true;
print "tea" + "pot";

Numbers, nil, booleans and strings all land in the same stack array. OP_NEGATE must refuse a string. OP_ADD must add numbers but join strings. OP_EQUAL must say 1 == "1" is false. An instruction can only do that if every value on the stack can answer one question: what kind of thing are you?

Drip is dynamically typed (chapter 26): the compiler doesn’t know the answer ahead of time, so the value itself has to carry it, all the way to runtime.

Tagged values

You can write that picture down directly. In TypeScript, a discriminated union (chapter 14) is exactly a tag plus a payload:

type Tagged =
  | { tag: 'nil' }
  | { tag: 'bool'; as: boolean }
  | { tag: 'num'; as: number }
  | { tag: 'obj'; as: Obj };

The instruction checks the tag, and TypeScript narrows the payload for you:

function negate(v: Tagged): Tagged {
  if (v.tag !== 'num') {
    throw new Error(
      'Operand must be a number.');
  }
  return { tag: 'num', as: -v.as };
}

This is close to what clox, the C virtual machine in Crafting Interpreters, does: a small struct holding a type field and a C union for the payload^[1]. Drip is a dialect of that book’s language, Lox.

const nil = { tag: 'nil' };
const num = as => ({ tag: 'num', as });
const str = as => ({ tag: 'obj', as });

function negate(v) {
  if (v.tag !== 'num') {
    return 'Operand must be a number.';
  }
  return num(-v.as);
}

console.log(negate(num(3)));
console.log(negate(str('a')));
console.log(negate(nil));

The tags at work

Here is that first line, print -(1 + 2) == nil;, compiled by the companion compiler and run on the real stack. Watch the tags, not the numbers.

OP_CONSTANT  0 '1'
OP_CONSTANT  1 '2'
OP_ADD
OP_NEGATE
OP_NIL
OP_EQUAL
OP_PRINT

Three rules fell out of that run, and Drip keeps them everywhere:

• Arithmetic checks types. -"a" is a runtime error, Operand must be a number., and so is 1 + nil.
• Equality never fails. Values with different tags are simply unequal. 1 == "1" and nil == false are both false.
• Truthiness looks at tags too. Only nil and false are falsey (chapter 35). 0 and "" are truthy, because their tags aren’t nil or bool.

print nil;
print true;
print 3 + 0.5;
print -0;
print 1 == "1";
print nil == false;
print !nil;
print !0;
print -"a";

How the companion VM stores a value

The Tagged union above works, but think about what it costs in a VM written in JavaScript. Every { tag, as } is a fresh object. So 1 + 2 would allocate a new object to hold 3, and every read of a value would follow a reference to reach its payload. That is the HeapNumber problem from chapter 22, built by hand, for every value in the program.

The companion VM doesn’t write a tag at all. Here is its whole value type, from vm/object.ts:

type Value =
  null | boolean | number | Obj;

null stands for nil, and booleans and numbers are plain JavaScript values. The tag is still there. JavaScript values already carry their type, and the engine keeps track of it (chapter 22’s Smi tag bit is one of V8’s ways^[2]). So reading the tag is just asking JavaScript:

case OP.NEGATE:
  if (typeof peek(0) !== 'number') {
    runtimeError(
      'Operand must be a number.');
  }
  push(-(pop() as number));
  break;

Equality is one line, a === b. For numbers, booleans and null, JavaScript’s === already compares type and contents. For objects it compares identity, which is right for every object Drip has, and chapter 52 makes it right for strings too.

Printing has one surprise. String(-0) gives "0", but Drip prints negative zero as -0, so the VM checks for it first:

function formatNumber(n: number) {
  return Object.is(n, -0)
    ? '-0' : String(n);
}

Your turn

const nil = { tag: 'nil' };
const bool = (as) =>
  ({ tag: 'bool', as });
const num = as => ({ tag: 'num', as });

function isFalsey(v) {
  return false;
}

function valuesEqual(a, b) {
  return a === b;
}

const nil = { tag: 'nil' };
const bool = (as) =>
  ({ tag: 'bool', as });
const num = as => ({ tag: 'num', as });

function format(v) {
  return String(v.as);
}

What you learned

• A dynamically typed VM needs tagged values: a tag saying the type, and a payload with the data. Instructions read the tag first.
• Drip has four tags: nil, boolean, number and object. An object’s payload is a reference to the heap.
• Arithmetic checks tags and can fail. Equality compares tags first and never fails: different types are unequal.
• A value representation is the layout of a value in memory. The companion VM’s Value is null | boolean | number | Obj, so it reads JavaScript’s own tags with typeof, and valuesEqual is ===.

Next: the fourth tag. Strings are the first value that can’t fit in a slot, so they move to the heap.