Style guide for base library about motoko-base HOT 15 CLOSED

Ah, you are right about the type capture issue. Damn, I think we need to get back to and improve our nested types semantics...

I don't necessarily think that the OO and PP interface need to be in the same module. It's probably less confusing if they aren't.

from motoko-base.

@chenyan-dfinity, classes are intended to mirror typical OO-classes (in as simple a way as possible). Emulating functors doesn't really work with them until we relax our restriction on free type vars in type defs. But classes aren't meant to be functors anyway.

True functors would take and return a module. They would require dependent type paths and abstract type members. Not currently a priority. :)

from motoko-base.

@matthewhammer, yes, I would e.g. define it as type Order = {#less; #equal; #more}.

In cases where partial orders arise, maybe the natural type to use would be ?Order.

from motoko-base.

Well, the type system also cannot prevent an order that isn't transitive. Or not reflexive. Or one that returns true one time and false the next. So I don't know if symmetry is a property particularly worth worrying about.

The problem with a Bool is that you typically need twice as many comparisons to figure out the case you're in. If they are expensive that's undesirable.

from motoko-base.

Thanks @chenyan-dfinity for starting this discussion. I agree.

I think OO vs procedural is the most difficult question to answer. Previously I would have tended towards OO, not because I particularly like it (I don't), but because it's a much better fit for our target audience. And because it's the only way currently to provide encapsulation.

But stable variables may change this picture, since we cannot currently allow objects in there. OTOH, it is too early to change directions for the sake of stable (we need some practical proof of their viability first).

A compromise might be to have classes as wrappers around procedural interfaces for everything, but the duplication may also be confusing.

What does everybody think?

from motoko-base.

A few more random thoughts, independent of OO vs PP:

Naming:

• All types should be capitalised, values (including variant tags) shouldn't.
• Classes define types, so they should never be named MakeX but just X.
• Most of the times, data structure types should be named after their functionality, not their implementation (e.g., OrderedMap vs RedBlackTreeMap) -- don't assume that our users know much about data structures.
• Obviously, analogous functions should have the same names across types.

Types:

• Mutators should generally return (). In cases where they could e.g. return the old value, that should be provided by a separate function.
• Orderings should return an Order type, not Bool.
• For now let's not bother with defining signature types for abstractions to allow multiple implementations of the same thing.

Data structures:

• In some cases it's useful to have both functional and imperative versions (sets, ordered maps, queues), in others it isn't (hash maps).
• For non-class types, we could handle the parameterisation issue (functors in ML, type classes in Haskell) by emulating functors, i.e., having a function returning a module. Have we tried? Is it worth it?

Should we take clues from Scala's collection library? Minus the overengineering, of course, more wrt to conventions.

from motoko-base.

What does everybody think?

I think that we do need a style guide, and that sometime soon, the base library should conform to it. However, as we are discussing and realizing, the best style is not always so clear. Thankfully, in many cases above, it is.

All of the stuff that Andreas lists above as "Naming" and "Types" seems reasonable to me, and to be consistent with what we've been doing (or aiming to do).

However, for "Data structures", things are less clear, at least to me, currently.

I agree with the first point (sometimes we want both FP and OO interfaces, and sometimes we only want an OO interface).

For things that seem more like functors but that are not classes (so, not HashMap), what concrete examples are you considering @rossberg? I was thinking about the purely functional Trie API, or any other set/map interface that's pure. I am also thinking about things like graphs (maps with even more structure).

In those cases, we often want a type with associated operations, like the param to a functor. I have not tried writing a function that accepts a module, but I have tried doing some things this week (with Claudio's help) involving this pattern, where one module is parameterized by the types and operations of another. (I'm trying to make the Adapton graph code separate from the "CleanSheets" DSL evaluator).

Even using a class is painful, since as it stands, the internal representation of this functor needs to be lifted out, for various reasons about the current limitations of type variable capture. I may be misconnecting my current experience to this point, but don't think so. (Perhaps @crusso can correct me if this is not connected.) I expect that using a function will have a similar issue, since classes are merely that. (Right?)

from motoko-base.

A compromise might be to have classes as wrappers around procedural interfaces for everything, but the duplication may also be confusing.

If I understand this suggestion, then the Red Black tree module follows it, within a single module.

Perhaps we should do a merging of Trie and TrieMap modules to mirror this pattern?

from motoko-base.

Classes define types, so they should never be named MakeX but just X.

I never quite understand class in Motoko. It is used as both a type and a constructor, sometimes even as a functor. If we are using class as a functor, we should probably name it makeX?

Following the discussion, I have a PR to refactor Heap: #11. And I feel the Heap class I am writing there looks like a functor. I also left some questions there, feel free to leave comments.

from motoko-base.

@chenyan-dfinity I also want to discuss this question ("how do we do functors in Motoko?, always with a class of some form, and if so, what are the patterns?").

I'm creating a companion issue to this one for that tangent #13

from motoko-base.

Orderings should return an Order type, not Bool.

@rossberg One clarification: All such orderings are total (not partial?), right?

(So that Order type is always isomorphic to the 3-way sum type () + () + ())

from motoko-base.

hmm, ?Order is not a well-formed partial order. We need either ?{#less; #equal} or Bool to represent partial orders. Bool feels more natural to me, but it doesn't distinguish between strict/non-strict partial orders. Which one do you prefer?

Also for priority queue, I assume we want to take a partial order, so that heapsort becomes a topological sort.

from motoko-base.

@chenyan-dfinity, I don't understand, why is ?Order not the partial analogue to what Order is for total orders?

from motoko-base.

ah, okay. Total order has the same problem: if Ord(a,b)=#less, I would expect Ord(b,a)=#more. But the type system doesn't prevent you from saying something else. So we are assuming the user providing a properly formed total order function then.

For partial order, if we return Bool or ?{#less; #equal}, it will always be well-formed, and we never need to think about the symmetric case of #more.

from motoko-base.

Okay, I switched back from extract to remove. To make it a bit more symmetric, I also changed swap to replace.

from motoko-base.