Functional update of data value fields

[blerner]

(migrated from https://github.com/orgs/brownplt/teams/pyret/discussions/8)

This issue is still open:

#835

However, it seems we want type support for it:

#1255

We need a clear decision here. I propose:

• If a field that already exists is updated on a data value, we check the annotations and construct a new instance with the same brands. This is the most useful, and actually something that could clean up a lot of Reactive student programs that end up with lots of fields in structures (x/y values for the dog and the cat and the player, etc)

• If a field that isn't present is updated, we need a call on whether it is an error or it drops its brands and produces a plain record. I don't know which programs we have that we want the extension behavior for. I'm of the opinion “just because we can, don't” and leave it as an error until we have a compelling use case for it. It's much better to leave it as an error and think about supporting it in the future than to try to fix semantics first.

[blerner]

@shriram on Mar 20, 2018

Radical question. Is it time to rethink a design (especially if we might reimplement the language using Stopify, etc.) that gets rid of brands entirely? Brands feel like a weird feature in that they are prominent primarily by their absence: you suddenly say "huh?" and then, if you know enough, realize "Oh, the brands got dropped".

Can you say more about the experience in BS:Reactive? That seems like a good testing ground for what should happen.

[blerner]

@jpolitz on Mar 20, 2018 Author

Let me phrase the question without invoking the word "brand":

• If a field that already exists is updated on a data value, we check the annotations and construct a new instance. This means all the same cases operations, is-foo recognizers, etc, work on the updated value.

• If a field that isn't present is updated, we need a call on whether it is an error, if it gets to "pretend" to be the same kind of data value it was before with some bonus fields, or it starts acting like a plain record that responds false to the is-* recognizers and no longer works with cases. I think either option other than "error" doesn't have a compelling use case I'm aware of, and needs it to be worth it for us to add the complexity.

Re: Reactive, students end up writing data definitions like the below (this is a real game from a real student that we have permission to share; actually a really slick-looking game [https://code.pyret.org/editor#share=19j_m7WvjME5IngjsKW-Be75zKpd2KJwG&v=5e3e157]):

data GameState:
  |game(
      s :: Number,
      multiplier :: Number,
      score :: Number,
      choice :: Number,
      menu-num :: Number,
      cX :: Number,
      cY :: Number,
      dX :: Number,
      dY :: Number,
      RGB :: Number,
      test-rgb :: Number,
      wasd :: Number,
      cowX :: Number,
      cowY :: Number,
      cowSpeed :: Number,
      pigX :: Number,
      pigY :: Number,
      pigSpeed :: Number,
      chickenX :: Number,
      chickenY :: Number,
      chickenSpeed :: Number,
      dogeX :: Number,
      dogeY :: Number,
      dogeSpeed :: Number,
      redDogeX :: Number,
      redDogeY :: Number,
      redDogeSpeed :: Number)
end

Then a simple update function looks like:

|string-equal(key, "1") then:
        game((g.s + 2),g.multiplier,g.score, (g.choice + 3),0,g.cX,g.cY,g.dX,g.dY,g.RGB,g.test-rgb,g.wasd,g.cowX,g.cowY,g.cowSpeed,g.pigX,g.pigY,g.pigSpeed,g.chickenX,g.chickenY,g.chickenSpeed,g.dogeX,g.dogeY,g.dogeSpeed,g.redDogeX,g.redDogeY,g.redDogeSpeed)

When that whole ask: clause could be

g.{ s: g.s + 2, choice: g.choice + 3, menu-num: 0 }

This would also make it way easier to add a new field to these games without onerously updating every single ask clause (of which there may be dozens).

Now, there's lots of ways to improve this code (lists, abstracting the common elements into a "character" datatype, etc). But I think that .{} is pretty compelling on its own here.

[blerner]

@blerner on Mar 20, 2018

ISTR that your first point above was something we agreed upon in principle, but there was a lingering issue of what to do about cross-field invariants. E.g. suppose my module is

# Module PerfectBinTrees
provide {
  node: make-node,
  leaf: leaf
} end
data BinTree:
  | node(left :: BinTree, val :: Number, right :: BinTree)
  | leaf
sharing:
  method height(self) -> Number:
    cases(BinTree) self:
      | leaf => 0
      | node(left, _, _) => 1 + left.height()
    end
  end
end
fun make-node(left :: BinTree, val :: Number, right :: BinTree) -> BinTree:
  if left.height() <> right.height(): raise an error
  else: node(left, val, right)
  end
end

Allowing a client of this code to functionally update an existing left or right field to a tree of a different height would break the perfectness invariant, potentially leading to bugs within the library. I'm not sure whether we care about this semi-contrived scenario enough to prevent this feature from working, though.

If we had a way of supplying cross-field annotations (e.g. hypothetically something like

data PerfectBinTree
  | leaf
  | node(left :: PerfectBinTree, val :: Number, right :: PerfectBinTree)%(equal-heights)
sharing: ... height ...
end
fun equal-heights(left :: PerfectBinTree, _, right :: PerfectBinTree):
  left.height() == right.height()
end

where I'm shamelessly cribbing the refinement syntax and shoving it after the constructor arguments), then we could refine your idea to "We check the field and cross-field annotations and construct a new instance with the same brands." (Actually, I kinda like this idea :) It's surprisingly natural-feeling to me, and gives us dynamically-checked dependent types, even if the type checker isn't intended to ever statically give us that.)

For your second point, I'm torn. This only matters for data values that we're trying to extend; records already can be functionally extended with new fields, and programs that manipulate data-values as data values (i.e. using cases) can't possibly know about the new fields, so they're not impacted at all. It's only when we try accessing a field that might or might not be there, and for which we have no way of checking whether it's there or not (that's the point of a dictionary, not an object), that programs might run into trouble. So I think, just barely, that I'm leaning towards leaving it an error, and given that I'm so torn, and this is the conservative safe thing to do here, I'm ok with that choice.