would like advise on creating a minimal rust implementation

[savaki]

First off, thank you for creating such a wonderful project. That said, I'm interested in creating a minimistic version of CUE in rust primarily intended for embedding. In the initial use case, I'm looking at validation and transformation. I did see there was a ticket for cue-rs, but looking at the repo it looks started, then abandoned and it's use of unsafe made me reluctant to use that as a starting point.

As this is a minimalistic version, I'd love to understand which features will take a disproportionate amount of time to implement relative to the value they would provide to validation/transformation use case.

For example, I understand that you could reduce foo: >= 1 and foo: <= 1 to foo: 1, but in the initial use case, it seems like you could just leave them be. Looking for other areas that could be left out of the initial version

[cuematthew]

When I started working here, I attempted a toy implementation. The goals were to learn how to implement CUE, in as few as lines of code as possible, and not caring at all about performance. I worked on this for a month or two. It was extremely useful for thinking about and learning CUE.

It is very difficult to offer advice, other than just go for it. It is not at all easy. There are also several different ways of thinking about CUE and different representations, and if I was starting again now I would make different design decisions than before. Thinking about evaluation strategy is useful - although the main implementation is not, I am certain that CUE can be implemented using call-by-need semantics. Gaining experience with that via toy haskell / lambda-calculus implementations is handy. There's a lovely series at https://github.com/sdiehl/write-you-a-haskell which I've studied before in depth. But you don't have to go that route at all.

Things to keep in mind:

• a reference must always be resolved to the final value - it must be impossible to ever witness an intermediate value. What a reference resolves to changes due to unification.
• disjunctions are hard.
• disjunctions enable loops. Correctly terminating loops is really hard. Establishing a proof that no new data has appeared is ... challenging.

Fun examples to think about that should not error:

{
  x: y & 4
  y: x & int
}

a: {x: 1, b}
b: {y: 2, a}

{
  r: L={L.a}
  i: {a: a: a: a: a: x: 4}
  out: r & i
}

i: int | string | j
j: i
out: i & j

l: {v: >2, t: l | null}
d: {v: 3, t: {v: 4, t: {v: 5}}}
out: l & d

Closedness is also really hard and the subject of much debate internally. I would recommend not implementing closedness to start with.

If you're anything like me (I'm so sorry!), be prepared to try lots of stuff and throw it away. If I had the time to start again now, I would invest weeks in building a framework that allows me to easily inspect and debug the state of the interpreter, before implementing much in the way of semantics. This is the result of spending hours and hours working through traces of the interpreter, with pencil and paper, trying to understand what's actually going on, and where the mistake is. You will frequently find that reversing the order of two lines of code will have a terrifying impact on performance and correctness. It often took me days of thinking to try to understand why.

Finally, IMO, simplification of bounds (as you mentioned), is of no importance to the language whatsoever. I would relegate that feature to a side effect of outputting the state of the interpreter - I think it's better to think of that as a property of the serialization of the interpreter than anything core to the interpreter.

Hopefully this comes across more as "red rag to a bull" and not dissuasion - we would all definitely benefit from more implementations of CUE - especially with a diversity of implementation approaches and design. Good luck!

[infogulch]

Fun examples to think about

Wow those are diabolical. I bet there are bunch of weird cases like this.

[savaki]

I wonder how much would be lost if I peeled off self referencing fields to start with like the case you have here where l references l. Seems like I could get a dramatic simplification for a v0 with only a small number of edge cases being lost.

l: {v: >2, t: l | null}
d: {v: 3, t: {v: 4, t: {v: 5}}}
out: l & d

Also, I was a little confused on

{
  r: L={L.a}
  i: {a: a: a: a: a: x: 4}
  out: r & i
}

why is x repeated so often in the results rather than just a single evaluation at the top? so just binding r once to

// removed one level of a
{a: a: a: a: x: 4}

thank you again!

[cuematthew]

Wow those are diabolical. I bet there are bunch of weird cases like this.

Yes they are. But they also flow naturally from nothing more than unification and references (and disjunctions). To avoid dealing with them, you're going to have to come up with a means to allow you to identify these cases and bail. That is also not easy! Also note that the final example is just a linked list (albeit with the value v having an arbitrary >2 constraint on it). t is the tail. This is a good example of where termination gets tricky - in out you need to keep unrolling l as long as you have new data from the interior of d to unify with it. And then stop at the right moment.

Also, I was a little confused on

  r: L={L.a}
  i: {a: a: a: a: a: x: 4}
  out: r & i

This is a good example of what I meant when I said "What a reference resolves to changes due to unification."

We're calculating out. The first result of r & i is {a: a: a: a: x: 4} - we've unpeeled it one layer. But we also must unify that result with r & i. So we have {a: a: a: a: x: 4} & r & i, which is {a: a: a: a: {x: 4, a: x: 4}} & r.

The result of {a: a: a: a: {x: 4, a: x: 4}} & r is {a: a: a: {x: 4, a: x: 4}} - unpeeling another layer. But we also must unify that result with r & i. So we have {a: a: a: {x: 4, a: x: 4}} & r & i, which is {a: a: a: {x: 4, a: {x: 4, a: x: 4}}} & r.

And so on. We must keep going until we reach a fixed point - i.e. nothing changes if we try the loop again. The way I think about it is that a reference like L={L.a} must be applied to all of our constraints that we currently know of, and if it produces anything new, then we have to apply it again. And again. And again...

Note that you have to keeping trying if any of your constraints yield a new value:

  r1: L={L.a}
  r2: M={M.b}
  i: {a: b: a: b: a: b: x: 4}
  out: r1 & r2 & i

Here, r1 and r2 alternate. But we can only stop when we know that every constraint is failing to produce anything new, and a fixed-point has been reached.

[infogulch]

Following on from savaki's comment, do you think there is an obvious "best" subset of cue features that would still yield an interesting language but would be an easier initial development target? Say, just unification and disjunctions but no references, or some other combination.

[cuematthew]

Keep in mind that we do not know the best way to implement CUE! I think looking at all of these different features in isolation and then in combination would be excellent in terms of learning - I wish I could do that!

With my toy implementation (which was some time ago, and my memory is not perfect), I left disjunctions out initially and tried to add them later. Whilst not insane, it did make me realise that disjunctions are really quite fundamental. But, you can do a lot without them. If you're leaving out disjunctions, then also leave out closedness - closedness is really just a way to create errors; it's just it interacts with disjunctions too (any error in a disjunction branch eliminates the branch).

Without references I think what you have left isn't particularly interesting. Without references you can't say "field1 should be the same as field2" for example, or "field1 must be smaller than field2" and that is really limiting. Once you have simple references, adding labels/aliases isn't too much extra work.

I would definitely leave out as much of subsumption as possible. Yes, it's (eventually) important to know that no value (other than ⊥) can inhabit string & int but it's really not important to know that <10 & int can be simplified to <10 (oh, definitely don't bother with floats and ints to start with - just pick one). In fact, maybe leave out all of subsumption to start with (and so no errors at all) - just get to a point where constraints are being propagated correctly everywhere, and then you can start reasoning about whether certain sets of constraints imply errors. So unification turns out to be much more about merging the fields of structs, and much less about subsumption and merging constraints.

Once you have unification of structs working, adding patterns isn't too bad. And then dynamic fields aren't too bad either, though they're definitely not essential.

Leave out all comprehensions.

[the-nurk]

zig is most likely way more minimal than a rust implementation. both in codebase size, compilation time, and syntax complexity. there's likely lots of overlap between zig compiler and cue evaluation. not that we have access to the zig compiler source. but compile times in rust are bloating as far as i can see and zig's main goal is minimal compile times for minimal syntax. JIT cue compilations/evaluations likely to be faster via zig for that reason. since cue is very 'one-shot focused', this seems to be the correct path. you don't need a bunch of special syntax and constructs to make sure that memory is safe. just do your job as a mathematician lol. especially if cue was actually part of the compilation layer.

just my humble 2c.

[the-nurk]

the zig build system is already pretty analogous to cue flows.

[infogulch]

Maybe it would be easier to write a cue evaluator in zig vs rust. Take Richard Feldman, who recently announced they would rewrite the Roc language compiler from Rust to Zig, and listed compile times (=iteration speed) and lack of need for memory safety in this application among other reasons for the switch.

That said, I don't see how the zig build system being similar to some part of cue is helpful for writing a cue evaluator. 🤷‍♂️

[the-nurk]

oh yeah, zig build system is possibly not related. that's why i made a second comment instead of including it in my original argument.

i mentioned it cause I'm of the opinion that the more pieces of the stack (apis) that we make overlap with one another the easier everything will be.

[the-nurk]

also, yeah, iteration speed is paramount over almost everything other than security for me. it feels like it's a multiplicative speed up for every unit of time you get back in the compilation layer.

this isn't a rigorous argument, but it's good enough to show my point; who cares if you have bad code if you can find and fix it in a heartbeat? the best defense is a fast one not a strong one. speed gives you strength for free, whereas a focus on strength (static rigor) will likely mean you lose speed.

finding bugs and inefficiencies in rust will likely always scale worse than finding bugs in zig given a competent zig/rust design, and testing those fixes will likely always be faster via zig due to compile time and largely equivalent build system capabilities.

testing speed + simple syntax introspection means faster code in all parts of the software lifecycle.

[the-nurk]

i am doing prep work for this re-implementation in zig if anyone wants to collab. after i get the base stuff i need in the go api working so i can use my tool, i'll be wrapping libcue and transitioning to using cuelang at zig build/compile time to guarantee types. then after that a total re-write in zig to fuse with a game engine.