Compiling data

[jpolitz]

Pyret supports data values with:

• Pattern matching via cases
• Name-based dot access
• Constructor-style printing

The above three features are critical. data supports other features as well, like:

• Methods
• Mutable fields

These are less critical. But the first three are fundamental to Pyret and curricula that use it, so a design must accommodate them, or fundamentally change Pyret.

data T:
  | nd(val, left, right)
  | leaf
end

n = nd(5, leaf, leaf)
n.val # evaluates to 5

cases(T) n:
  | nd(v, l, r) -> v
  | leaf -> 0
end # evaluates to 5 as well

print(nd) # prints "nd(5, leaf, leaf)"

In choosing a representation, we have the following tensions:

• Bucklescript compiles values from OCaml's type into flat arrays with minimal, type-local tag information (integers representing the variant the value came from to compile match expressions
• cases is positional and name-agnostic, just like OCaml ADTs and OCaml's match
• dot access is not positional, and works by (first-order) name, like OCaml records

At the very least, it seems we need to put extra metadata into the values created by data to track their constructor name to allow for pretty printing.

The positional-vs-name debate is more vexing, because:

• If we choose records for the representation, I'm not sure how to get positional matching back without more static information at the Pyret level when visiting a cases expression
• If we choose OCaml ADTs for the representation, we're left with a problem at dot-lookup time, where we need static information to even compile to the right match expression. A generic dynamic solution could redirect through a dictionary stored in metadata to find the right position for the field, but this seems like a total non-starter.

Suggestions welcome, I think I may just need to be jolted into thinking outside the box here.

[blerner]

Of the "less critical" features, I'd like not to give up methods. I still have hope that Pyret can be used to bridge over to an OO intro course, and I don't want to lose dynamic dispatch.

For the position-vs-named debate: Using records requires that we store a mapping from positions to names, or have a method that returns all fields in their proper order. This latter is what Pyret currently does. If we use flat arrays, then the name-to-position mapping is just a classic vtable, so I don't see why that's a "total non-starter". (OO languages do rely on static layout information to de-virtualize the field lookups, by knowing statically what offset the fields will appear within the object layout.)

[jpolitz]

@blerner your parenthetical is what I'm getting at. If all we can do is what Pyret currently does, then Bucklescript's representation of values isn't helping much. One of the main reasons to try BS is to figure out what it takes to drill down to the BS representations, because they are battle-tested and known-fast. If we are building string-based vtables atop them... that's a non-starter for this approach.

So my observation here is that, on something pretty fundamental, I'm concerned that the BS representations will require too much encoding already.

[jpolitz]

Note that if we had Pyret's type information here, we could rely on static layout information to do this well. The issue is that for the super-quick idea of assuming Pyret<->OCaml will be close enough to get going quickly, it already seems like we want Pyret-specific static information, not just OCaml-style static information.