mergeded

Backing out a bit to take a different approach to named types.
2 files changed, 20 insertions(+), 386 deletions(-)

M README.md
M fml/tests/test1.gt
M README.md +15 -377
@@ 8,7 8,7 @@ People keep talking about what a small R
 nice it would be, and whether or not Zig or Hare or whatever fits the
 bill.  So, I think it's time to start advertising, at least in a small
 way: I'm trying to make basically the language these people want, a
-language that asks "What would Rust look like if it were small?"  I call
+language that asks "What would Rust look like if it were small?".  I call
 it [Garnet](https://hg.sr.ht/~icefox/garnet). I'm at the point where I
 am fairly sure my design is gonna do at least *something* vaguely
 useful, but I also think it's time to ask for interested parties to talk

          
@@ 18,7 18,7 @@ Garnet strives for smallness by having t
 types, and structs.  Somewhat like Zig, structs double as modules when
 evaluated at compile time. A lot like SML/OCaml, structs also double as
 your tool for defining interfaces/traits/typeclasses/some kind of way of
-reasoning like generics.  If you make sure your code can be evaluated at
+reasoning about generics.  If you make sure your code can be evaluated at
 compile time, you can treat types mostly like normal values, and
 "instantiating a generic" becomes literally just a function that returns
 a function or struct.  Again, this is kinda similar to Zig, but I want

          
@@ 26,7 26,8 @@ to avoid the problem where you don't kno
 before it's actually instantiated.  Again, this is quite similar to ML
 languages, but without an extra layer of awkwardness from having a
 separate module languages.  [It seems to work out in
-theory](https://people.mpi-sws.org/~rossberg/1ml/).
+theory](https://people.mpi-sws.org/~rossberg/1ml/).  Whether it can be
+made actually convenient... well, I hope so.
 
 I also want to solve various things that irk me about Rust, or at least
 make *different* design decisions and see what the result looks like.

          
@@ 34,13 35,14 @@ Compile times should be fast, writing/po
 easy, ABI should be well-defined, and behavior of low-level code should
 be easy to reason about (even if it misses some optimization
 opportunities).  The language is intended for low level stuff more than
-applications, OS's and systems and embedded programming, so async/await
-is unnecessary.  Better ergonomics around borrowing would be nice too,
-though I'm not sure how to do that yet, I just hate that there's no way
-to abstract over ownership and so we have `Fn` and `FnMut` and `FnOnce`.
-However, trading some runtime refcounting/etc for better borrowing
-ergonomics as suggested in [Notes on a Smaller
-Rust](https://without.boats/blog/notes-on-a-smaller-rust/) and [Swift's
+applications: OS's and systems and embedded programming.  This makes
+some Rust features unnecessary, like async/await. Better ergonomics
+around borrowing would be nice too, though I'm not sure how to do that
+yet, I just hate that there's no way to abstract over ownership and so
+we have `Fn` and `FnMut` and `FnOnce`. However, trading some runtime
+refcounting/etc for better borrowing ergonomics as suggested in [Notes
+on a Smaller Rust](https://without.boats/blog/notes-on-a-smaller-rust/)
+and [Swift's
 work](https://github.com/apple/swift/blob/01c22b718cfc80a10feaefaf598aa1087f3766c8/docs/OwnershipManifesto.md)
 is not on the cards; I think there's a lot of potential for a language
 that does this sort of thing, but Garnet is not that language.

          
@@ 365,375 367,11 @@ the implementation's optimizer.
 
 MIT
 
-# References
-
- * <https://rustc-dev-guide.rust-lang.org/>
- * <https://digitalmars.com/articles/b90.html>
- * <https://c9x.me/compile/> (and the related <https://myrlang.org/> )
- * <https://gankra.github.io/blah/swift-abi/> (and related,
-   <https://swift.org/blog/library-evolution/>)
- * <https://en.wikipedia.org/wiki/Operator-precedence_parser>
- * <https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=174ca95a8b938168764846e97d5e9a2c>
- * <https://www.evanmiller.org/statistical-shortcomings-in-standard-math-libraries.html>
- * <https://thume.ca/2019/07/14/a-tour-of-metaprogramming-models-for-generics/>
- * <https://boats.gitlab.io/blog/post/notes-on-a-smaller-rust/>
- * <https://without.boats/blog/revisiting-a-smaller-rust/>
- * <https://dl.acm.org/doi/pdf/10.1145/3428195> (on type inference)
- * <https://queue.acm.org/detail.cfm?id=3212479> (C is not a low level language; the good one)
- * <https://old.reddit.com/r/rust/comments/my3ipa/if_you_could_redesign_rust_from_scratch_today/>
- * <https://lobste.rs/s/j7zv69/if_you_could_re_design_rust_from_scratch>
- * <https://people.mpi-sws.org/~rossberg/1ml/> -- 1ML programming language
- * <http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf> -- Compiling pattern matching
- * <https://research.swtch.com/gomm> and related posts in introduction -- Memory models
- * <https://arxiv.org/abs/1306.6032> -- Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism
- * <https://github.com/nikomatsakis/bidir-type-infer> -- Implementation of the above paper
- * <https://belkadan.com/blog/2021/08/Swift-Regret-Tuples-and-Argument-Lists/?tag=swift-regrets> -- Swift design retrospective, on tuples and argument lists.  Garnet may have fewer problems with this than Swift does, but Garnet still has some of the problems mentioned here.
- * <https://arxiv.org/abs/1512.01895> -- Modular Implicits, stapling
-   typeclasses onto an ML module system.
-
-References on IR stuff:
-
- * <https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/docs/ir.md>
- * <https://blog.rust-lang.org/2016/04/19/MIR.html>
- * <https://llvm.org/docs/LangRef.html>
-
-References on backend stuff:
-
- * <http://troubles.md/posts/wasm-is-not-a-stack-machine/> and the
-   following posts -- Interesting thoughts on webassembly's design
-
-References on borrow checking:
-
- * <http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-alias-based-formulation-of-the-borrow-checker/>
- * <https://github.com/rust-lang/polonius>
- * <https://gankra.github.io/blah/deinitialize-me-maybe/> -- Destroy All Values: Designing Deinitialization in Programming Languages
-
-Technically-irrelelvant but cool papers:
-
- * <https://www.mathematik.uni-marburg.de/~rendel/rendel10invertible.pdf> -- Invertable parsers
-
-What not to do:
-
- * <https://arxiv.org/abs/2201.07845> -- How ISO C became unusable for operating systems development -- I'm a little dubious of the simplicity of its arguments, but it contains lots of references
-
-# Random notes
-
-## CI
-
- * Actual build takes ~1-2 minutes
- * Adding end-to-end unit tests it takes 5 minutes
- * Adding code coverage it takes ~15 minutes -- cargo-tarpaulin ain't
-   instant but most of it is still spent in building it rather than
-   running it.
- * Making a `.deb` package for cargo-tarpaulin would help a lot then.
-   Talked to the Debian Rust packaging team and they're in favor, very
-   helpful folks, but of course understaffed.
-
-## Out Of Context Problems
-
-nee "Undefined Behavior"
-
-Some more thoughts on the lack of undefined behavior is... you COULD
-define "read an invalid pointer" to be "return unknown value, or crash
-the program".  But only if you knew that pointer could never aim at
-memory-mapped I/O.  *Writing* to an invalid pointer could literally do
-anything in terms of corrupting program state.  Some slightly-heated
-discussion with `devsnek` breaks the problem down into two parts: For
-example, WASM does not have undefined behavior.  If you look at a
-computer from the point of view of assembly language + OS, it MOSTLY
-lacks undefined behavior, though some things like data races still can
-result in it.  If you smash a stack in assembly you can look at it and
-define what *is* going to happen.  But from the point of view of the
-assumptions made by a higher-level language, especially one free to
-tinker with the ABI a little, there's no way you can define what will
-happen when a stack gets smashed.  And even if you're writing in
-assembly on a microcontroller then you might still be able to do things
-that put the hardware in an inconsistent state by poking memory-mapped
-I/O.  So, Undefined Behavior usually isn't really Undefined, rather it's
-defined by a system out of the scope of the language definition.  So
-let's just stop calling it Undefined Behavior and call it an `out of
-context problem`.
-
-Things that I think we CAN define context for:
-
- * Integer overflow either overflows or panics.
- * **Constructing** an undefined pointer just is a number in a register.
- * **Reading** an undefined pointer, in the absence of memmapped I/O,
-   either gives a random result, panics, or causes the host system to
-   produce an error (ie by segfaulting your program)
- * We **may** have well-defined pointers that are never valid,
-   ie, null pointer.  Reading and writing to these can do whatever we
-   feel like.  We should probably make them either panic or cause the
-   host system to produce an error.
- * Reading uninitialized data should be a compile-time error.  Manually
-   eliding initialization for performance reasons just means your
-   compiler isn't good enough at avoiding it itself.  A good
-   middle-ground might be some setup where in debug mode you can have
-   runtime checks for reading uninitialized data before it's been
-   written.
- * Order of evaluation of function arguments.
- * Constructing an impossible value, such as having an enum representing
-   integer values 0-5 and stuffing the integer 6 into its slot.  Not
-   sure *how* to deal with this, but it's a case that needs handling.
-
-Here's a list of things that I don't see a way of defining in any
-reasonable/performant way:
-
- * **Writing** an undefined pointer may do anything, ie by smashing the
-   stack.  If correctly executing a program requires assuming an
-   un-smashed stack, well, that's tricky.
- * Reading a pointer pointing to mmapped I/O may similarly do anything.
-   A notable recent experience was when reading a value from memory was
-   *required* to acknowledge an interrupt.
-
-Todo list of other common sources of UB in C, from <https://stackoverflow.com/questions/367633/what-are-all-the-common-undefined-behaviours-that-a-c-programmer-should-know-a>:
-
- * Converting pointers to objects of incompatible types
- * Left-shifting values by a negative amount (right shifts by negative
-   amounts are implementation defined)
- * Evaluating an expression that is not mathematically defined (ie, div
-   by 0)
- * Casting a numeric value into a value that can't be represented by the
-   target type (either directly or via `static_cast`)
- * Attempting to modify a string literal or any other const object
-   during its lifetime
- * A pile of other things that are mostly C++'s fault
-
-Reading material: <https://blog.regehr.org/archives/213> and the follow-on
-articles.  Also, apparently Zig has opt-*in* undefined behavior for
-things like integer overflow, shift checking, etc which sounds pretty
-hot.  Another option is to provide compiler-intrinsic escape hatches,
-similar to Rust's various `unchecked_foo()` functions.
-
-Some of the optimizations that pointer UB enables are talked about here:
-<https://plv.mpi-sws.org/rustbelt/stacked-borrows/paper.pdf>  Would be
-very interesting to have some emperical numbers about how much UB helps
-optimizations.
-
-Again, note that we are NOT trying to make incorrect programs do
-something that could be considered correct, and we are NOT trying to
-define things that are inherently undefinable (such as writing to a
-truly random/unknown pointer).  Sooner or later, defining what is
-defined is up to the *programmer*, and we are trying to make it so that
-there are as few rules and hidden gotchas as possible for the
-*programmer* to handle when dealing with these things.
-
-Other reading material from people doing interesting unsafe Rust things:
-<https://github.com/TimelyDataflow/abomonation/issues/32>
-
-Mandating a different pointer type for referring to mmapped I/O is
-probably not unreasonable, tbqh, and removes a source of semantic
-weirdness that compilers have problems dealing with.  Basically have a
-`MMIOPtr[T]` type that is kinda similar to Rust's `UnsafeCell<T>`,
-but doesn't allow reads/writes to be reordered or optimized away, and
-which has different constraints on what values are allowed for it than a
-normal pointer does.
-
-## On pointers/references
-
-```
-Evy
-A downside of your #[offset] design is that you can create a lot of nonsense and (partial) overlaps all of which you have to check for.  May i suggest a different approach instead? Where you have nominally ordered struct layouts, have a field type padding. Padding is a parameterised type that can take either an alignment/offset, or a size. padding(size: 4) inserts 4 bytes of padding, padding(align: 16) rounds the offset of the next field up to the next multiple of 16 bytes, padding(offset: 0x100) rounds up to offset 256, may be zero-sized, and will error out of the fields before the padding exceed that offset. And padding cannot be used in types which's fields aren't nominally ordered.
--icefox — Today at 12:03 PM
-Oooo
--Evy
-So e.g.:
-type PlicLayout = #[ordered] ${
-  priority:             [U32; 1024]               padding(align:     0x1000),
-  pending:              [U32;   32]               padding(align:     0x1000),
-  enable_for_context:  [[U32;   32]      ; 15872] padding(offset: 0x20_0000),
-  threshold_and_claim: [ThresholdAndClaim; 15872] padding(align:     0x1000),
-}
-
-You can even make align and size paddings available for arbitrary fields or variables. Like:
-let mut x: Atomic(U32) align(cache) padding(align: cache) = 0;
+# References and design notes
 
-let mut raw_u32_le: [u8; 4] align(4) = …;
--icefox — Today at 12:06 PM
-ooooOOOOOooooOOOOOooo
-Downside is I'd have to figure out how all those options interact
--Evy
-In this example, the type of priority is actually ([U32; 1024], [Garbage; PaddingSize]), except that you can only safely touch the .0 payload. In this case, PaddingSize = 0. For enable_for_context it's however much padding is needed to round up to offset 0x20_0000, etc.  Now, two funny things happen now:
-
-1. You could simply demand that types with padded fields will automagically be nominally ordered. Then you can throw the redundant #[ordered] away. If you didn't, well… let's just say that ordering padded fields optimally is not trivial, significantly more complex than a vanilla order by align, size desc.
-
-2. For things like fast zero-copy serialisation, you can demand padding to have specific values instead of »undefined/uninit«. For example by annotating: x: T padding(align: N, fill: 0x00)
-3. To create a paddingless C-like struct, all that's needed is to append padding(offset: 0) to the first field.
--icefox — Today at 12:16 PM
-1) If you need to have things ordered properly in memory then its up to you to define the ordering. That's fine.
--Evy
-Btw.: [Atomic(U32) align(cache); N] align(page)
-Nicely flexible.
--Evy
-This raises the question of how to write something like Rust's
-Box<[i32]>.
-This one is tricky. Technically there are two competing pointer types: Single element pointers and pointers to arrays. The latter ones are fat pointers with a length attached. And actually you get even more pointer types. Like pointers to &dyn T things, where it's data-pointer and vtable-pointer packed together. Or function pointers, which on some platforms are magical.
-
-If you have a more powerful type system than Rust 1.0 had, you wouldn't store a contents: *T, but instead a contents: impl Pointer, no second field needed.
-Nice, when did Rust finally get these traits?
-I feel like reading TWiR is useless, given how often awesome stuff went below my radar.
--repnop, Resident RISC-V Shill — Today at 12:35 PM
-Yeah it's definitely a toss up
--Evy
-#![feature(ptr_metadata)]
-
-assert_eq!(std::ptr::metadata("foo"), 3_usize);
-
-I could've used that a century ago! D:
-[12:39 PM]
-# Characters and strings
+Moved to <https://man.sr.ht/~icefox/garnet/>
 
-Do what Rust does.  No need to innovate here.
-@icefox Do what Swift does. :<
--icefox — Today at 12:42 PM
-What does Swift do?
--@Evy
-I feel like reading TWiR is useless, given how often awesome stuff went below my radar.
--icefox — Today at 12:43 PM
-The problem is what is useful varies by person, and often starts small and slow
-But yes
--Evy
-@icefox
-# References and pointers
-Having looked plenty at proglangs like Herb Sutter's simplified C++ or Ada or in parts C#, i came to have the opinion that this is the wrong approach when designing proglangs. What seems to be a better design is having in, out, in out, move, forward function args. If you think you explicitly need pointers or references, use generic library types like Ptr(T) or Ref(T). Even mutability wrappers like Ptr(Box(T)) (Lisp naming style.) or Ref(Mut(T)) (Rust naming style.). In all other scenarios, it's better to let the language and calling conventions decide whether to use copies or references or what. For example, for tiny args the proglang may decide to turn an in out T into pass-by-value-and-return-by-value behind the scenes. Plus, these annotations allow for way better static checking whether you actually used your function args accordingly to what you specified.
--Evy
-> @icefox
-> What does Swift do?  
-It doesn't just have UTF-8 slice plus Unicode Scalar Values, but also has built-in Grapheme Cluster support.(edited)
--icefox — Today at 12:48 PM
-You still need raw pointers sometimes, but that's an interesting idea. Do you have any references for the "simplified C++"?
--Evy
-Swift is the proglang with the currently best Unicode handling out there. »Best« being defined by how much spec is covered by the letter.
--icefox — Today at 12:48 PM
-The flip side of that is, how do you specify those things in struct fields?
--@icefox
-You still need raw pointers sometimes, but that's an interesting idea. Do you have any references for the "simplified C++"?
--Evy
-Lemme try find the paper.
-https://github.com/hsutter/708
---@icefox
-The flip side of that is, how do you specify those things in struct fields?
--Evy
-What things?
-Pointers?
-Same thing, wrapper types.
--icefox — Today at 12:52 PM
-Like, how do you say &mut Foo or &Foo in that in/out/etc paradigm
-Especially mutability
--Evy
-The sexy thing about in, out,… is that it gives you a lot of »dark magic« and other patterns for free and safely. in T automagically picks whether to use memcpy(T) or &T or &mut T behind the scenes. You you never have to overload functions or traits based on referenceness. And out T gives you safe access to uninitialised buffers, because the compiler can guarantee you never read before you write. forward is »in, until the last use, which is move«, etc.
--@icefox
-Like, how do you say &mut Foo or &Foo in that in/out/etc paradigm
--Evy
-&mut T etc. are impl-details.
-
-If you take an argument in and don't modify it, use in T. If you take it in and observably modify it, you take in out T. If you only return something but never read what you got in (e.g. uninitialised buffers) you use out T. If you take ownership, you use move T. If you are allowed to inspect the data without modifying and then pass along however the caller intended (whether to move or borrow or whatever), you use forward T.
-
-The compiler is free to decide whether or not to use pointers or pass by register or what not. You are 100% oblivious to whether pointers or copies are given.
--icefox — Today at 12:57 PM
-No no
--Evy
-So if you e.g. must have a pointer, e.g. to map a physical address to a virtual one, you take e.g. virt: in Pointer(T).
--icefox — Today at 12:57 PM
-Not for functions
-For structs
-Oh, the wrapper type
--@icefox
-For structs
--Evy
-Vec = struct(T: type) {
-  ptr: Ptr(Mut(T)),
-  len: USize,
-  cap: USize,
-}
--Evy
-Btw., a mutability wrapper would allow for some crazy code patterns. For example, you only need to impl iterators once, and they'll handily allow you to use the same generic iterator type to iterate over T, Ref(Mut(T)),  or just Ref(T). And it gives you dark magic interior mutability patterns like having a field Mut(Bool) for storing a dirty bit. And it does what Rust wants, getting rid of static mut by instead having a static wrapper with interior mutability.
-I/O pointers
-Ptr(T, volatile: true) or something-something. Maybe even Ptr(Volatile(T)). Where  stand-aloneVolatile(T) does its thing depending on in out etc. (i.e. standalone is useless)(edited)
-fn, Fn, FnMut, FnOnce, sigh... can we do anything about that?
-The problem is that upvalues, aka. closure captures, are magic hidden payloads, directly contradicting the explicit self design. If you want to get rid of the army of function traits, you have to make captures explicit. Then your »onceness« or »mutness« etc. emerge from whether your captures are in, in out, etc.
-If any of your captures is out or in out, you got a FnMut. Got a move, it may be a FnOnce. Etc.
-Ada goes a step further by distinguishing between procedures and functions, the latter being allowed to have magic, the former not. The former can even only return stuff via out parameters.
--@icefox
-You still need raw pointers sometimes, but that's an interesting idea. Do you have any references for the "simplified C++"?
--Phlopsi — Today at 2:36 PM
-only because we use programming languages, that are too close to the hardware.
--icefox — Today at 3:17 PM
-Sometimes you need to be close to the hardware.
-I wait with bated breath for someone to write a UART driver in Haskell.
--@Phlopsi
-only because we use programming languages, that are too close to the hardware.  @Evy I agree with you on all the in out stuff. I still don't get the practical usefulness about forward, but I'm tired, so that's fine. 
--Evy
-Imagine things like debug-logging your stuff you pass right through. Your debug logger just says: fn debug(T: type)(x: forward T) -> forward T. If it came in as move, it comes out as move. If it came in as in out, it comes out as in out, etc. But within debug it is treated as an in.
--Evy
-@icefox
-Sometimes you need to be close to the hardware.  
-Ideally only when you're smarter than the compiler/language and making the compiler/language smarter than you is too hard of a problem to solve.
-
-C++ is the perfect example for why e.g. in out is better in the 99% case than spelling out refs vs. moves vs. mutable refs. For an utterly extreme example, look at the amount of junk you need to program to implement a correct forwarding function using current C++. Further more, look at the amount of overload code bloat needed to fine-tune your code for all possible kinds of function args and returns. And that complexity grows exponentially with every added argument or return value. Having in out reduces hundreds of lines of »perfect« C++ code to what looks like a pretty naïve single function.
-
-And i'm frequently wondering whether there are also better ways to abstract over data sharing and memory-mapped structures. I have not yet found the answer.
-'cause like in function args, pointers only give you a »how«, not a »what«. And we apply patches and bandages to things like »volatile« and magical linker scripts etc. to add a »what« to the implemented »how«.
--icefox — Today at 3:39 PM
-Sure, and Rust performs the exact same kind of abstraction of arg representation you're talking about
--Evy
-Rust is like C++ just a »how«.
-The only thing Rust has over C++ is that you can state what ref input a ref output belongs to.
-Which is a biggie, no downplaying that.
--icefox — Today at 3:49 PM
-Not really, functions have no defined ABI
-The compiler can and does turn references into copies and vice versa
-And, there's always going to be times when I'm smarter than the language. The lang is an amplifier for my own reasoning capabilities, and a special purpose amplifier is going to give me a lot more leverage (for lower cost in its problem domain) than one that tries to be equally good at everything.
--Evy
-Very limitedly. Copies to refs is demanded by ABI if your struct size exceeds two registers, or if you have too many args. The reverse is a magical recent optimisation of LLVM. But it gives you none of the semantics and semantic guarantees. You still have to overload traits and shit for ref vs. move, you still cannot distinguish between out and in out with a &mut T (it's always treated as in out), etc.
--icefox — Today at 3:55 PM
-Yeah that part I'm definitely interested in
-```
-
-## On Motivation
+# On Motivation
 
 A quote from Graydon, original creator of Rust, from
 <https://github.com/graydon/rust-prehistory>:

          
M fml/tests/test1.gt +5 -9
@@ 27,16 27,12 @@ fn identity(i: @T): @T =
     i
 end
 
-fn identity2(i: @X): @X =
-    identity(i)
-end
-
 fn main(): I32 =
     --let x: I32 = foo(12)
     --let y: Bool = baz(true)
-    let a: I32 = identity(1)
-    let b: Bool = identity2(true)
-    let c: Bool = identity(false)
-    let d: I32 = identity2(12)
-    3
+    --let a: I32 = identity(1)
+    --let b: Bool = identity2(true)
+    --let c: Bool = identity(false)
+    --let d: I32 = identity2(12)
+    12
 end