ah-HA, this is an important distinction

Note that both Zig and C++ work that way --- if you write recursive comptime/template fibonacci, compiler will evaluate it in linear time.

...though it then makes me wonder about separate compilation issues

Both Rust and C++ use ODR here --- each compilation unit gets a separate, fresh copy of "unique stuff computed at comptime", and then its up to the linker to prune away duplicates. Zig just doesn't do separate compilation. I was at first shocked at that, but now that makes sense --- everything you can do with separate compilation, you can do inside a single multi-threaded process, but better, with the exception of two things:

• your program must fit in ram. Original motivation for separate compilation was that programs were too big. These days, we have plenty of RAM. What's more, the most RAM-hungry bit, linking (with lto) is not separate anyway.
• build must be local, no distributed builds. This seems like a bigger issue --- with separate compilation, you might scale beyond a single machine, but with threads and shared address space, you can't use more CPUs than you have. OTOH, if your compiler isn't slow, you can compile a boatload of code on a single computer anyway.

Generics work by checking the types, and then generating the code for them. Template systems do the opposite:

Yeah, that's the thing, one is a proper type system (if the signature works, the body can't break), another is a glorified macro. What I am getting at here is another distinction between Zig and others, which is orthogonal.

In function signatures, there are constructs like Vec<i32> or (in Zig) ArrayList(i32). Usually, those are "programs" in some obscure logical language, but Zig makes them into you usual imperative language. In Rust, Vec<i32> and Vec<i32> are equal types, because those are equivalent terms. In Zig, ArrayList(i32) and ArrayList(i32) literally denote the exact same value, because comptime computations are always interned.

So,

It sounds like what you're doing in your case is attaching a default instance to a particular type. Contrast with modular implicits where the default instance is based on the values that are currently in scope, I think?

is exactly it! With modular implicits, compiler synthesizes the required instance looking at what's in scope. What I am proposing here is to make this "instance synthesis" a very dumb computation in the hands of the programmer. In a way, that's a Zig way to do modular implicits.

How would you implement an Ordering module for a new concrete type, in your made-up syntax?

So here, the "module" is just fn cmp(T, T): Ordering. That is, just a function, not really grouped into mod Ord { fn cmp }. And the way it works, you can declare fn cmp inside the type you are writing:

struct IntPair {
    x: Int,
    y: Int,

    fn cmp(lhs: IntPair, rhs: IntPair): Ordering { /* compare x & y */ }
}

This allows plugging Vec<IntPair> into sort such that compiler figures out (synthesizes) the code for comparing vectors of points. Note that this blesses this particular semantics of cmp. If I want to add a non-standard instance (like comparing points only by X coordinate), I write this as a top-level function:

fn cmp_by_x(lhs: IntPair, rhs: IntPair): Ordering { ... }

fn example(xs: Vec<IntPair>) {
  sort(xs); // uses default ordering
  sort(xs, cmp = |lhs, rhs| lhs.cmp(rhs)); // above elaborated
  sort(xs, cmp = |lhs_vec, rhs_vec| lhs_vec.cmp(rhs_vec, cmp = |lhs_pair, rhs_pair| lhs_pair.cmp(rhs_pair))); // above elaborated more

  sort(xs, cmp: |lhs, rhs| lhs.cmp(rhs, cmp = cmp_by_x)) // uses non-standard ordering
}

The heavy lifting is done by

cmp: fn(T, T): Ordering = T.cmp

in the original declaraion. It says "whatever T at the call-site is, lookup a T declaration with name "cmp"" . This of course can fail, if T doesn't have a cmp, and that would be a compile-time error. With modular implicits, the equivalent says something like "whatever the T is, lookup something with fn(T, T) type and available as an implicit at the call-site". The difference is that the latter behavior is fully implicit and hard-coded into the compiler, while the former is the literal = T.cmp written by the programmer at the declaration site.

This is super half-baked, but one thing I realized about Zig recently is that it really just computes types. That is, type system usually have some sort of computational engine embedded into them, but Zig just makes that explicit. See, in particular, https://matklad.github.io/2023/08/09/types-and-zig.html#Mandatory-Function-Signatures .

Now, the trait/module systems usually have some sort of prologue embedded into them, which allows computing of instances. That is, when, in Rust, you write impl<T: MyTrait> MyTrait for MyType<T>, that actually defines a type-level function mapping impls to impls, and then there's a smart trait solver which figures out that, if you need MyType<Foo>: MyTrait, you could construct that instance from that function and Foo: MyTrait. The same "implicit computation" idea is present in that modular implicits paper --- complier can synthsize new modules from functors.

Which makes me think that perhaps Zig's approach of "let's use explicit first-order language for type-level computation" can be applied to a problem of searching instances?

Or, more concretely, Zig with default arguments I think could be equivalent to modular implicits? Here's some made-up syntax:

fn sort(
  comptime T: type,
   xs: T[],
   // The trick: we provide default value for `cmp`, which also depends on the previous parameter (`T`)
   cmp: fn(T, T): Ordering = T.cmp,
)

struct Vec<T> {
    fn cmp(lhs: Self, rhs: Self,  cmp: fn(T, T): Ordering = T.cmp) 
}

We can then call sort(Vec<Int>, xs), and that'll use Vec<Int>.cmp for sort's cmp default. And Vec<Int>.cmp would use Int.cmp for its default.

That is, we get ourselves type-level "implicit search & construction of derived impls" behavior via seemingly much more tame runtime-level default arguments for functions.

From today's Go blocg, it seems they build something similar

https://go.dev/blog/compat#api

https://github.com/golang/go/blob/master/api/go1.txt

I don’t know how this would actually play out if implemented, but I have a strong suspicion that ability to review “change of the interface” would actually be a great force multiplier for larger projects. Interface changes are costly, and automatically flagging them for more careful review makes much easier to triage PRs, and to explain system-level considerations during the actual review.

I am 0.8 sure that this thing has big drawback and big benefits, so applying a ready-made principle probably won’t give the correct answer for the correct reason here.

Basically, if we have a compilation unit with file A that defines a macro and file B that uses the macro

Yeah, I sort of assume that you don’t want to keep macros in the same CU, as that creates all kinds of problems with order of compilation.

C'monnnnn, it's guaranteed to terminate

Not really! In the presence of macros, the thing we are iterating a fixed-point on isn’t actually a monotonic function. So it terminates by virtue of various dirty hacks, and not because the model naturally terminates.

Though if you expand derives before resolving imports, what do you do if you derive something defined in a separate file?

I don’t understand the question, so I’ll just tell what I know :x) I think two models can be compiled with some amount of reasonableness.

In the first model, input to a proc macro is strictly source code of a specific item. As proc macro looks only at a single item in a single file, you can run this in parallel, before any semantic analysis is done,

In the second model, input to a proc-macro is a fully analyzed crate, with types and such. In this model, you first compile code “normally”, and then run proc macros. And there’s some sort of fixed point thing going on, where proc-macro dumps outputs to some file, and, if the file is updated, the whole compilation is restarted. Or you can imagine that the user writes signatures, and the proc macro only ever provides impls. https://learn.microsoft.com/en-us/dotnet/csharp/roslyn-sdk/source-generators-overview is similar.

I was low key intending for this data to just be distributed as a section within a .lib

Yeah, as long as .api is a part of distributed artifact, that works.

What do you mean by "ADL-shaped"?

Argument-dependent lookup, also known as koenig search. That’s C++ hack with fives the same power as traits/modules — ability to extend types with generic functionality outside of the type itself. The specific thing I’ve ment here is this:

Using structs for both fields and methods is confusing: fields belong to an instant, methods belong to a type. If you do modules, you can keep structs only for fields, and keep “methods” as top-level functions, and add sugar a-la “functions defined in the same module as struct can be called using dot syntax”.

Yup, a whole bunch of opinions here!

I guess the top-level one is that I think that "modules as a unint of polymorphism" and "modules as a unit of compilation/distribution" are almost entirely orthogonal concepts, and they only accidentally share the same name. Eg, "should files be ML modules" is the same as "should files be structs" (they are in Zig) or "should files be classes" (I guess they could have been in Java).

I have more more confident thoughts about CU-modules than ML-modules. I think Rust gets CU-modules almost right, that's what I'd keep and what I've changed:

• keep two-level structure with crates and modules (but I'd maybe just call them "libraries" and "modules"). Having a library as first-class concept is poweful. Allowing hierarchical namespaces within a library leads to reasonably-sized libraries.

• keep libraries anonymous, acyclic, and with explicitly declared dependencies. This helps compilation and logical organization. In large projects (eg, rust-analyzer), it's very helpful to be able to say "this crate should not (transitively) depend on that crate".

• keep tree-based module structure within a library, keep cyclic dependencies between modules (but see https://lobste.rs/s/vx8hbs/rust_module_system_encourages_poor for some arguments why flat structure within a library might be better). You need hierarchy and cyclic deps at some granularity, CU seems the right one.

• promote pub(crate) visibility, it absolutely should be one keyword. I would suggest the following set of visibility: api for "visible outside the current CU", equivalent to Rust's pub with -Dunreachable-pub, pub for "visible throughout CU" (= pub(crate)), and nothing for "visible in current file".

• remove "imports are items". That is, imports should not be visible in submodules. Otherwise, it's just confusing and makes name resolution hard (you need protect from import importing itself. Basically, Rust name res is a fixed point iteration loop, and that seems like gratitious accidental complexity).

• if meta-programming is syntax-based (syntactic proc macros), it should happen before a tree structure of modules is assembled and imports are resolved. You should be able to first expand derives in parallel in every module, and then figure out who imports what.

• remove mod foo; items, infer modules paths from the file system. This is less confusing for the users, and faster to compile.

• remove ::, use . throughout. The type/value separation is confusing, increases syntactic soup, and doesn't actually work in Rust.

• aim for the following compilation model within CU:

  • use parallel waldir to list all files in CU and read them in parallel
  • sequentially assemble all files into a tree
  • for each file in parallel, parse it
  • for each file in parallel, apply syntactic meta progarm, if you have proc macros
  • for each file in parallel, compute a map of symbols defined in file
  • for each import in parallel, resolve import to a symbol (here we use that imports themselves are not symbols)
  • for each symbol, resolve types it mentions (eg, for fn foo(bar: baz::Quux)), we first register that we have function foo in this file, then we resolve all imports in all files, and then we resolve bar::Quux to what it points two.

  I think we don't need any sequential/synchronizing phase besides "assemble modules into a tree", everything else looks like it can be embarassingly parallel.

• add header/signature files. Make it compiler's job to parse the whole CU and then spit out a single .api file, which is added to git, committed to VCS and is a part of a published package. The .api file gives "at a glance" view of the API of a particular library, it's essentaily rustdoc, but you don't need a browser, as it's just a single text file. Additionally, .api enables parallel compillation, and compilation firewall (if .api doesn't change, no need to recompiel downstream)

• use signatures for a following compilation model of many CUs:

  • using explicit graph of CUs (lockfile), download all CUs in parallel
  • compile ".api" files following the graph. This isn't embarrassingly parallel (parallelism is limited by graph's critical path), but it is very fast, because .api files are a fraction of .impl files.
  • now that .api are compiled, compile implementaiton of each CU in-parallel. This is not in the graph order, as CU impls depend only on APIs, not on other impls.
  • link the stuff together.

This compilation model is pretty much "lets add a bunch of indireaction everywhere so that we actually have .api files due to stable ABI, and also let's rewrite linkers", not sure if it'll work for garnet.

Now, whether to integrate this all with ML-modules is unclear. Zig is nice that "everything is a struct" (eg, files are structs), so you could do that. But also, in Zig, it gets confsing whereth stuff is a static field or not:

struct {
  this_is_an_instace_field: u32,
  const this_is_a_const_in_the_type: u32 = 92;
  fn this_is_another_name_in_the_type() void {}
}

If I go for "everything is a module", then I'd probably don't allow attaching methods to structs syntactically. So, something like this:

module M {
    struct Point { x: i32, y: i32 } // structs can _only_ declare methods
  
    // This is `M.get_x`, not `Point.get_x`, but we use some sort of ADL-shaped syntactic sugar to make `p.get_x()` syntax work. 
    fun get_x(self: Point) -> i32 { self.x }
}

~matklad any thoughts on this matter with regard to ML modules? It seems something you might have opinions on. Basically, my question right now is whether it's worth it to be able to have type definitions in our structs/modules, a la associated types. It's an ingredient in the conventional ML module approach, but I personally find it rather annoying to understand and think about it and so far haven't managed to write any code that needs them which can't just be written via normal generics and functors. (At least, it works in my head, basically any types in the module get hoisted out into type params that are inputs to the functor, and the functor can return another functor if it feels like it.)

But if files/packages are modules, then our modules need to be able to include type definitions. Not really any way around that I can see. (And constant values, but that's a lot simpler.) But once you allow that you start getting into messes with HKT's and that whole Thing, and I just don't want to handle it right now.

Ah, I think it's possible to do "explicit type erasure". If Foo(Bar) is a generic type with @T = Bar, we can say that Foo(*) is Foo with some concrete, but unknown type instead of T, which gives the user ability to manually construct wide pointers:

type Draw(@T) = struct
    draw: fn(@T),
end

type Container(@T) = struct
   data: @T
   vtable: Draw(@T)
end

type DynContainer = Container(*)