Features and other stuff to do/implement in/around Carth.
<2022-08-16 tis> I just read this. Some really cool stuff! https://dustycloud.org/blog/guile-steel-smelting-pot/
---- older
For inspiration, learn from their mistakes, etc.
Also add related work to readme, after looking closer at it, if applicable.
- Hackett
- Liskell
- Axellang
- Kalyn https://intuitiveexplanations.com/tech/kalyn#preliminary-technical-design-decisions
- Unison https://github.com/unisonweb/unison
Self hosted? Does Sourcehut have anything? Base it on mailing lists (no… or maybe?)
— Update <2022-07-02 lör>: yes, sourcehut does have something! https://todo.sr.ht/~jojo/Carth looks like it might be good enough. Let’s go with that? At least try it out. —
But I need something other than this file. It only pollutes the Git history for no real good. It’s also less useful now that I’ve had to disable magit-todos.
Another reason is that this file doesn’t scale at all. Not that I expect or particularly desire to have contributors, but I also don’t want to scare anyone away xd.
Like type String = [Char] in Haskell.
Rc, ARC, refcount, reference counting, gc, garbage collection
https://verdagon.dev/blog/generational-references
GC is inelegant, needing to stop the world or use a bunch of complex methods. Also, latency is bad.
Do good refcounting instead.
There were other reasons, but I can’t remember them of the top of my head.
https://atp.fm/205-chris-lattner-interview-transcript#gc / https://news.ycombinator.com/item?id=31139610
Chris Lattner: Here’s the way I look at it, and as you said, the ship has somewhat sailed: I am totally convinced that ARC is the right way to go upfront. It is better in a whole bunch of different ways. It gives you deterministic behavior, so it doesn’t have the unpredictable-stutter problem that people like to bash on GCs.
The stutter problem, to me, isn’t really the issue, even though [1:59:30] that’s what GC-haters will bring up all the time. It’s more about being able to reason about when the memory goes away. The most important aspect of that is that ARC gets rid of finalizers.
If you use a garbage-collected language, you use finalizers. Finalizers are the thing that gets run when you’re not object gets destroyed. Finalizers have so many problems that there are entire bodies of work talking about how to work around problems with finalizers.
For example: the finalizer gets run on the wrong thread, it has to get run multiple [2:00:00] times, the object can get resurrected while the finalizer’s running. It happens non-deterministically later. You can’t count on it, and so you can’t use it for resource management for database handles and things like that, for example. There are so many problems with finalizers that ARC just defines away by having deterministic destruction.
There are two arguments that people make [2:00:30] against ARC in favor of a tracing garbage collector, one of which is that ARC adds overhead because you have retain and release operations that run. That is true. The other is that you have to think about cycles in ARC because it doesn’t automatically collect cycles, and that is also true.
The rebuttal I’d give to people is that those problems are also true in garbage collection, just in different ways. In a garbage collector, for example, [2:01:00] people don’t think about it, but garbage collection injects additional code into your application just like ARC does.
There are many different garbage collection algorithms, and not all of them are the same. But most modern garbage collectors, that use a nursery for short-lifetime objects then promote them out — that are generational — use something called a write barrier. Every time you store to a property [2:01:30] of an object, say, you have to run additional code.
Garbage collectors also need the ability to stop all the threads, or at least to be able to stop threads at some point in time, and they need to be able to do so within a specific time bound because they don’t want the garbage collector to take forever. The artifact of that is that typical garbage collectors, in Java for example, will introduce what’s called a safepoint into loops. So now, in your loops, extra code is being run because of the garbage collector.
On more [2:02:00] aggressive garbage collection algorithms — for example, I was reading a blog post recently about Go’s tricolor algorithm — they’re touting the advantage of really low latency and the ability to guarantee response times in a more fine-grained level than most garbage collectors. But to do that, they use this tricolor algorithm which dramatically lowers throughput, because they’re doing almost exactly the same kinds of operations that ARC is doing.
The problem [2:02:30] that it then introduces, though, is that these operations that the garbage collector is introducing are sometimes but not nearly as well optimizable as the ARC overhead that the ARC optimizer applies to.
Furthermore, there’s no out on it. With ARC, I think and hope that the ownership model will give people the ability to take control of those overheads. And if it becomes a problem in practice, or if they’re just that kind of person, they can take full control over the lifetime of their objects, and then know that ARC will never happen. In a garbage collector, you don’t have that.
[2:03:00] The performance side of things I think is still up in the air because ARC certainly does introduce overhead. Some of that’s unavoidable, at least without lots of annotations in your code, but also I think that ARC is not done yet. A ton of energy’s been poured into research for garbage collection, particularly since Java has come up. There’s been hundreds of papers written in the academic circles, tons of work in HotSpot and other Java [2:03:30] implementations to do different tweaks and different tunings and different new kinds of algorithms in garbage collecting. That work really hasn’t been done for ARC yet, so really, I think there’s still a a big future ahead.
On the programming side of things, the cycle side of things, I think it’s also a really interesting question of how much should people think about memory?
When I was baiting you a little bit, you said that the great thing about garbage collection is that you don’t have to think about memory. Of course we know that’s not true, right? Because if [2:04:00] you have a reference to some big object graph that you didn’t mean to keep around (maybe it’s in your undo stack), then you will “leak” that memory. That’s true of a garbage collector, and that’s true of ARC as well. Any automatic memory-management approach has that problem.
There’s this question of if you’re building a large scale system, do you want people to [2:04:30] “never think about memory?” Do you want them to think about memory all the time, like they did in Objective-C’s classic manual retain-and-release? Or do you want something in the middle?
I think that ARC strikes a really interesting balance, whether it’s in Objective-C or Swift. I look at manual retain-and-release as being a very imperative style of memory management, or malloc and free, where you’re telling the code, line by line: this is where you should do a reference-count operation, [2:05:00] this is where you should release the memory, this is what you should do at this point in time.
ARC then takes that model and bubbles it up a big step, and it makes it be a very declarative model. So instead of telling the compiler that this is the place that you should do a retain, you instead say, “This is an owning relationship.” The cool thing about that to me is that not only does it get rid of the mechanics of maintaining reference counting and define away tons of bugs by doing that, it also means that [2:05:30] it is now explicit in your code what your intention was. That’s something that people who maintain your code benefit from.
By saying that I have a weak point or two, the parent object of my thing, that’s a really important relationship to know about and as you’re looking at the code, you’re maintaining the code. Having that be explicit is very valuable, because that talks about the relationship between values. To me, again with the goal of being able to write large scale applications in Swift, I think that’s really useful. [2:06:00] I also don’t think it’s hugely burdensome, though it’s definitely part of the learning curve of learning how Swift works that it has to be balanced in there as well.
So I don’t know. ARC has clear advantages in terms of allowing Swift to scale down to systems that can’t tolerate having a garbage collector, for example, if you want to write firmware in Swift. I think that it does provide a better programming model where programmers think just [2:06:30] a little bit about memory. And I think that going forward, it provides a really high performance model that you can get better than garbage collection in almost every way. I think that in terms of trade-offs, it’s the right one to push forward.
The third piece that garbage collection is really bad about, which is kind of a showstopper for Swift, is interoperability with C code. If you’ve ever worked with Java or other [2:07:00] similar garbage-collected languages, one of the major advantages the garbage collectors give you is that they move objects, and they need to do that so they can compact those objects so they can then efficiently do allocations. The problem is that once you start moving objects around, if you’re interfacing with C code, you can’t have some random C code having a pointer to your object and have it move because then you get a dangling pointer.
Once you get down that line, you end up with things like JNI, the Java Native Interface, where you have to [2:07:30] explicitly pin things, you have to maintain them, it’s very complicated, it’s really buggy. ARC completely defines this away by just saying that something’s in memory, It has predictable lifetime, you can reason about it. Swift provides tools for dealing with unsafe pointers and things like that, and that makes the interoperability with existing C code — but also with Objective-C, and maybe someday C++ code — really simple, really natural and really efficient. I think that’s a huge advantage that ARC [2:08:00] provides that really would be impossible to do with a garbage collector.
That’s my opinion. I think reasonable people disagree, obviously, but it’s something that does come up now and then.
https://gankra.github.io/blah/deinitialize-me-maybe/
Update <2022-07-31 sön>
See another HN thread: https://news.ycombinator.com/item?id=32276580. And a supposedly good paper on current state of high perf RC systems: https://users.cecs.anu.edu.au/~steveb/pubs/papers/lxr-pldi-2022.pdf. (Low-Latency, High-Throughput Garbage Collection, Wenyu Zhao et al.). “A paper I quite enjoyed on automatic reference counting for pure, immutable functional programming: https://arxiv.org/abs/1908.05647”. Also https://xnning.github.io/papers/perceus.pdf and https://www.microsoft.com/en-us/research/uploads/prod/2021/11/flreuse-tr-v1.pdf, about Perceus in Koka.
Update <2022-08-29 mån> Another paper I had open: Counting Immutable Beans: Reference Counting Optimized for Purely Functional Programming
Update <2022-08-03 ons>: I’ve uncancelled this. Now I’m thinking that while GC will probably not be built into the language / the default allocation method, we’ll still probably want a separate Gc type for garbage collected pointers. Sort of like how Rust has Rc as a standalone type, separate from the compiler itself. Anyways, it would probably be fun to implement a GC! So why not do it, when there’s time?
Update <2022-05-24 tis>: I’ve actually changed my mind about refcounting. With some ownership analysys, which we’d need anyways for linear types, one could easily ommit most RC increments / decrements in the generated code. And predictable deinitialization + no GC latency is actually really valuable.
Until we get linear types, and even then, we’ll need some form of GC. Boehm’s seems to be working well enough, but a conservative collector is not ideal, and I think it would be a fun project to write my own GC.
There are many problems with refcounting: Generated llvm ir/asm gets polluted; While performance is more predictable, it’s typically worse overall; Cycle breaking would either require using weak refs where appropriate, which would in turn require user input or an advanced implementation, or a periodic cycle breaker, which would be costly performance wise. So tracing GC is probably a good idea.
GHC seems to prefer throughput over latency, so very long pauses are possible when you’re working with a nontrial amount of data. “You’re actually doing pretty well to have a 51ms pause time with over 200Mb of live data.”.
It could be interesting to add ways of controlling when GC happens
so you can reduce spikes of latency. Haskell has performGC :: IO
() that does this. Here is a gameboy who eliminates spikes at the
cost of overall performance by calling performGC every frame.
A tracing GC would be quite separate from the rest of the program. The only pollution would be calls to the allocator (not much different from the current sitch w malloc) and (de)registrations of local variables in Let forms (a total of two function calls per heap allocated variable).
Implementing a tracing GC would be a fun challenge, and I’m sure it could be fun to try different algorithms etc.
Look at
- https://github.com/mkirchner/gc
- https://youtu.be/FeLHo6tIgKI
- http://www.cofault.com/2022/07/treadmill.html
We need some kind of module system for namespacing. The current (<2022-08-16 tis>) “module system” only pretends to be one, and is really no better than C `#include` with `#pragma once` by default. At minimum, I want what Rust has. Simple, but competent enough for most purposes. It solves the namespacing problem well, but not really anything more than that.
We also need ad-hoc polymorphism, aka. type classes / traits / interfaces / protocols / concepts. Here, I thing Rust’s trait system actually wouldn’t be enough. Some limitations in Rust:
- An `impl` affects only one type. No equivalent of multi-parameter type classes here. Of course, this makes type inference easier / better, but it comes with limitations.
- No higher kinded types, so no Functor, Monad, etc. With GADTs I understand one can achieve something roughly equivalent, but it doesn’t seem practical.
In Carth I’d want higher kinded types, multi-parameter type classes. Multiple instances + implicits could be cool as well, though we’d have to handle the problems they cause. Maybe multiple instances could be practical if we have a method of denoting that an instance is canonical, and that an API only accepts the canonical instance.
Then there’s compile time evaluation. This one would on the one hand be really cool to have, but at the same time we could probably do without it. It might work, and be fairly simple to implement with interpretation, if we allow only a subset of the language to be interpreted in a comptime context, and disallow certain kinds of values from surviving into the runtime context. Later on, it could possibly synergise really well with on-demand compilation. If so, the performance of comptime might improve drastically.
Comptime eval also directly bleeds into dependent types. Maybe not the full thing, but enough to be really practical. E.g. we could be generic over the lengths of fixed-size stack arrays, without having to make it a special case.
So these are things that we want. And the thing is that there is a lot of overlap! A type class instance shares some similarities with modules. What if they were the same thing? Then you get ML-style modules (instances) & signatures (type class). And aren’t modules really similar to records actually? One is a structure of values & functions that exists at comptime, the other is a structure of values & functions that exists at runtime!
Of course, the overlap isn’t total. The different systems have different strengths. Some stratification – i.e. having essentially different languages & namespaces for modules, records, & instances – is really not that horrible. But it would be really elegant if they were all first class citizens using the same language. You could reuse the same abstraction in all contexts. No need to e.g. add a separate, complex system to support closed type families – just define a function that pattern matches on the type!
I want all of these things, and everytime I revisit any of them, I change my ming on what’s the best course.
But right now (<2022-08-16 tis>), I’m feeling that starting out with compile time eval is the right approach. Then we can attempt to implement modules on top of that. If it works – great, two birds with one stone! If it doesn’t – ok, but we still have comptime eval! That’s great on its own. And we can just attempt a Rust-style module system later instead.
comptime Apparently known as staged compilation or staged programming in literature.
Two-Level Type Theory (2LTT) is also related, but I don’t think it’s anything we’d want. I can’t really grock the mathy definition of 2LTT, but as I understand, the gist of it is that your language is really 2 languages. One language at the type layer, and one at the object layer. But we want something more akin to partial evaluation of a single language.
Look at Zig’s comptime.
Start with interpreting a non-strict subset of Carth. Like, don’t even attempt to handle `extern`s to begin with. But what about pointers? Like, at runtime I’m imagining that well end up having multiple different pointer types. Rc, Gc, Raw, etc. But a high-level interpreter actually use the external Gc or whatever.
If we’ve already got on-demand compilation when attempting this, maybe skip straight to implementing comptime that way.
Consider something this:
(defun new-appropriately-sized-vec
{_ n} []
:of (Fun {a (len :of Nat)}
[]
(if (< len 32) (SmallVec a) (BigVec a)))
(if (< n 32)
(small-vec/new n)
(big-vec/new n)))
With dependent types, this should typecheck.
But the types of the branches of the if differ – they depend on the comptime argument len.
So how do we typecheck this?
I guess comptime typechecking would have to be deferred until application basically?
Like how code in a C++ template isn’t typechecked until it’s instantiated.
Maybe comptime function is it’s own type.
I’m watching https://youtu.be/x3evzO8O9e8, and it got me thinking about how type class instances could be resolved in the case of constrains & polymorphism. Consider something like
sort :: forall a. Ord a => [a] -> [a]
concat :: forall a. [[a]] -> [a]
foo :: forall a. Ord a => [[a]] -> [a]
foo xss = concat (sort xs)sort can figure out how to sort a [b] given an Ord b.
foo is aware of Ord a.
But we’re giving sort an [[a]]!
How is that resolved in our system?
How would an instance Ord a => Ord [a] look in Carth with comptime records?
Maybe something like this.
(data Cmp Lt Eq Gt)
(record Ord [a] :of (Fun Type Type)
[cmp (Fun [a a] Cmp)])
(defun ord-list [] ;; can omitt implicit param list. Params are implicitly available in env.
;; braces for implicit parameter list
:of (forall [a] (Fun {(Ord a)} [] (Ord (List a))))
;; braces for constructing record
{ [cmp (fun [xs ys] (cmp-list xs ys))] }) ;; (Ord a) implicitly passed along to cmp-list
;; Can take an implicit param explicitly as well
(defun cmp-list {ord-a} [xs ys] :of (forall [a] (Fun {(Ord a)} [(List a) (List a)] Cmp))
(match [(next xs) (next ys)]
(case [(Some [x xs]) (Some [y ys])]
(match (ord-a/cmp x y) ;; Resolve instance explicitly
(case Eq (cmp-list xs ys))
(case c c)))
(case [(Some _) None] Gt)
(case [None (Some _)] Lt)
(case [None None] Eq)))
(extern cmp_int (Fun [Int Int] Cmp))
(def ord-int :of (Ord Int)
{ [cmp cmp_int] })
We’d probably have some sugar for modules & instances of course, just to make it a bit clearer.
Maybe only record values marked with some keyword like instance should be considered for resolution, for example.
But I think the core idea is sane.
The instance resolver is based on passing instance records as implicits.
And I suppost it should be able some basic implicit computations as well.
Like if we have exactly one (forall [a] (Fun [(Ord a)] (Ord (List a)))) and one (Ord b) and we need a (Ord (List b)),
then the resolver should be able to perform that application.
So the resolver looks at the types of variables & return types of functions, to see if there’s anyone that matches.
When modules are more powerful, like in ML languages, there is suddenly quite a lot of overlap with traits / type classes. Do we feature both? Modules are more powerful in some ways, but less powerful in others.
If possible I’d like to have a single powerful solution that solves all the things that modules, OO classes, and Haskell type classes solve.
https://www.reddit.com/r/ProgrammingLanguages/comments/vqx19e/modules_overcoming_stockholm_and_duningkruger/ https://graydon2.dreamwidth.org/253769.html
https://arxiv.org/abs/1512.01895
https://www.youtube.com/watch?app=desktop&v=hIZxTQP1ifo
I was thinking, impl/instances already seem equivalent to modules in some ways. A collection of functions, constants, & types. Consider instances in Haskell.
Many module systems mostly only solve namespacing and compilation order. E.g. Rust’s.
Differences:
- an instance must, by definition, be an instance of a class. It cannot exist as a class-less module.
- an instance is not named. E.g. functions are instead resolved via the class namespace.
In Rust, there are multiple syntaxes, depending on context:
let x = Add::add(1000, 300); let y = Add::<i32>::add(30, 7); let z: <i32 as Add>::Output = x + y;
Another thing to consider: what about multi-parameter type classes? From haskell wiki: if a single-parameter type class is a set of types, then a multi-parameter type class is a relation between types.
Ok, I think I might be on to something. This description starts out with Haskell’s system, and change things from there.
- Typeclasses that can contain declaration of types, values, & functions.
- Instances that contain definitions for these types, values, & functions.
- Now, let’s rename “instance” to module.
- A module may instance 1 or 0 classes.
- A module is generally bound to a name, except if it instances a class and is marked “canonical”.
- A module is referred to either by name, or by a special form “canon”. Something like “(canon Monoid Int)”. (it should work for higher kinded types)
(sig Semigroup [a]
(def sappend :of (Fun [a a] a)))
(sig Monoid [a] :where [[semi (Semigroup a)]]
(defun mappend [a1 a2] :of (Fun [a a] a)
(semi/sappend a1 a2))
(def mempty :of a))
;; Actually, why have the modules in a :where, and not do it
;; more ML style:
(sig Monoid [a]
(mod semi :of (Semigroup a))
(defun mappend [a1 a2] :of (Fun [a a] a)
(semi/sappend a1 a2))
(def mempty :of a))
;; Starting to look more and more like normal ML modules...
(defun concat [xs]
:of (for [a] :where [[mon (Monoid a)]]
(Fun [(List a)] a))
(foldl mon/mappend mon/mempty xs))
(def concat-result
(concat @Int @@Int/monoid+
(list 1 2 3)))
(sig Abs [a]
(type Positive)
(def abs :of (Fun [a] Positive)))
(sig Sqrt [a] :where [[abs (canon Abs a)]]
(def sqrt :of (Fun [a] abs/Positive)))
;; or alternatively
(sig Sqrt' [a] :where [(canon Abs a)]
(def sqrt :of (Fun [a] (canon Abs a)/Positive)))
(mod (canon Abs Int)
(type Positive Nat)
(defun abs [a]
(to-nat (if (< a 0) (neg a) a))))
(import Abs/abs)
;; Now there is visible to the whole module an
;; `abs` of type (forall [a] :where [[m1 (canon Abs a)]] (Fun [a] m1/abs))
(mod (canon Sqrt Int)
(defun sqrt [a]
;; Should be able to infer Abs instance for the
;; `abs`, from the applicand `a`
(sqrt_nat (abs a))
;; but if it can't, or we want to be explicit
(sqrt_nat (abs ))
))
(mod just-beans
(data Bean SmallBean BigBean)
(type Beans [Bean])
(defun count-beans [beans]
(sum (map (fun
(case SmallBean 1)
(case BigBean 2))
beans))))
(mod Int
(mod semigroup+ :of (Semigroup Int)
(defun sappend [x y] (+ x y)))
(mod monoid+ :of (Monoid Int)
(mod semi semigroup+)
(defun )))
Check out https://ollef.github.io/blog/posts/speeding-up-sixty.html. Great tips!
What syntax to Postfix syntax for module paths? A bit like web-domains - “sub.main.top”. E.g. “vector.collections.std”. Most relevant information floats to the left. Maybe a good idea, maybe not. Consider it.
Look at ML modules.
See https://www.microsoft.com/en-us/research/publication/first-class-modules-for-haskell/ (First class modules for Haskell, Mark Shields & Simon Peyton Jones)
I’m thinking something that would allow the following. It would be less annoying than having to qualify everything. Also, gotta think about how this relates to overloading à la C++.
(module Foo
(data FooThing First Second)
(define: isFirst
(Fun FooThing Bool)
(fun-match
[First True]
[Second False])))
(module Bar
(data BarThing First Second)
(define: isFirst
(Fun BarThing Bool)
(fun-match
[First True]
[Second False])))
;; First, there should be no error for just importing modules with conflicting
;; defs. This is ok in Haskell, unless one of the conflicting defs is used.
(import Foo)
(import Bar)
;; Second, it should be allowed to use one of a set of conflicting defs if the
;; type makes it unambiguous....
;; either explicitly
(define: x FooThing First)
(define: y BarThing First)
;; or implicitly
(define t (isFirst x))
(define u (isFirst y))
Big std => tons of stuff to fix when making changes in the syntax etc. While we’re still breaking things relatively often, keep std small. Even trim it a little. E.g. `<ooooo` is definitely not a must-have in std.
Update <2022-11-06 sön>
Implementing Carth in itself right now just isn’t much fun really. I’m missing a bunch of features. And I’ve also been thinking about the bootstrapping process. I don’t want us to require a ton of bootstrapping steps. Preferarably, there should just be a couple. Something like: haskell compiler -> selfhosted gen 1 -> selfhosted gen 2 -> selfhosted current. But if I start writing the selfhosted compiler too early, I’ll be stuck improving Carth in that still crappy version for a while. I think I’d rather improve Carth a bit more before seriously writing the selfhosted compiler.
Original
At some point or another, we ought to selfhost. This is a particularly good way of dogfeeding the language, as we have to use it to develop it.
Also, I’m actually falling out of love with Haskell just a tiny bit. As soon as you want to add a tiny little effect, you have to rewrite sooo much code to use monadic combinators instead of just applying functions.
Then there are parts of the codebase that I figure might be better off rewritten from scratch. I’ve learned some lessons. Now, I’d want to encapsulate some types better, restricting how they may be constructed & desctructured etc. And if we want to implement on-demand compilation – which we do – that would necessitate a really extensive rewrite anyways.
There are just a few features I’d like to have in place beforehand, like modules. Just enough to make it something of a “real” language. Then we can release 1.0-alpha, and start working on the selfhosted version as 2.0-alpha.
I like the idea of releasing the current state of the compiler as a 1.0, and then doing the rewrite as a 2.0. We’d not be beholden to compatibility, and can change the language as we please. (Not that we’re avoiding breaking backwards compatibility currently, but whatever). It will then also be fine if we want to develop the 1.0 language while we’re still implementing 2.0. It’s fine if they diverge, since they’re not exactly the same language anymore.
keywords: type checking, inferenc, inferrer
I’m not completely happy with the typechecking. 4 module files
(Check, Checked, Infer, Inferred) totalling over 900 SLOC. Also,
solve is not just run once at the outermost level, visiting each
constraint at most once. Because of nested let with polymorphism,
we currently run solve nestedly, and in total, each constraint is
likely visited more than once. This is ugly.
See:
Not specific to the refactor, but this talk on the type inference in Haskell is good: https://youtu.be/x3evzO8O9e8
It’s just kinda messy right now. Many files must be changed when touching just about any part of the AST representation. Also, takes up a lot of lines for not much apparent gain. Use some kind of attribute-tag to change the AST for different stages. Like:
type Expr attr = Expr attr (Expr' attr)
type ParsedExpr = Expr (Type, SrcPos)
type CheckedExpr = Expr CheckedTypeMore or less a prerequisite to compile-time evaluation. Also enables good incremental compilation, and better IDE/LSP support.
https://ollef.github.io/blog/posts/query-based-compilers.html
paper: Build Systems à la Carte
What Benjamin Pierce calls “Separate development” in his ICFP presentation Advanced Module Systems (A Guide for the Perplexed) (p24).
In order to be able to compile modules independently, which would be very good if we could do, the modules can’t be too strongly coupled.
Some languages solve this by having a separate file that defines the module’s interface.
I think OCaml does this with their .mli files.
If we go down the route of “comptime records as modules”, a module interface would be equivalent to a record type, I think.
Consider a module that implements a type class. The module type is a nominal record type. In a module like this, one should maybe be able to leave out the type signatures, like in Haskell. We thus have a depencency on that definition wherever it is.
If the module does not implement a type class, the record type is strutural. In this case, one should be forced to include type signatures for all public members. There are then no dependencies.
For a structurally typed module, we could pretty early on, like during
parsing, extract the signatures of all public members, and construct a
module interface from that.
So the only step before monomorphisation that needs to be done sequentially would thus be to figure out interfaces for nominally typed modules?
… oh but this isn’t true, is it? If we have comptime eval, one would have to know the definition of a function in order to evaluate a function application in a type signature. So actually scrap all of this. it’s probabl not possible for us to employ this stratergy.
optimization
egg / e-graphs looks cool.
Universal quantification is equivalent to a dependent function in Dependent Type Theory / Propositions as Types.
Given we implement comptime eval & passing implicits, we could then get rid of the special semantics of forall, and simply implement it as a sugar for a dependent function.
I’m not sure what the syntax for implicits should be though.
Maybe coupled with a @ sigil or :implicit keyword, interspersed with normal params.
(Fun [@a b] ...)
(foo @a b)
Or maybe in curly brackets, so it looks almost like two separate function calls.
(Fun {a} [b] ...)
(foo {a} b)
I’m thinking .foo .bar 3, since it resembles a prefix version of (foo ∘ bar) 3.
This would also serve as sugar for applying a curried function.
Since .foo bar is equivalent to (foo bar), (.const 123 456) is equivalent to ((const 123) 456).
Alternatively, consider an infix $.
((foo (bar 123)) 456)
(.foo .bar 123 456)
(foo (bar 123) $ 456)
Something like (defvar X (+ 1 x)) is of course invalid, but a case like (defvar ones (box [1 (Some ones)])) actually makes sense, and is easy to codegen. We could choose to allow it, if we wish.
In practice, we will unlikely have more backends than 2 or 3. An abstraction for that few backends doesn’t make that much sense to begin with, and what’s worse is that Low isn’t even a very good abstraction for a C backend!
Say we use QBE as a backend. In that case, the QBE Intermediate Language is our low level IR already – it’s a low-level IR abstracting multiple different machine targets.
I’m thinking we should exchange the LLVM IR-like Low for more of a C– kind of deal. Then we can even more easily generate C, and it will be much more readable. And compiling a C– to say LLVM IR ought not to be all that hard either really. Of difficulty right between Lower and CompileLLVM I’d imagine, so about 1k lines.
If we were to add a third backend, say Risc-V ASM, the calculation today would be something like: 1.6k lines Lower + 3 * 800 lines codegen avg = 4000 lines total compare this to a higher level IR, with a bit more work in some Compile* modules: 1.2k lines Lower + 3 * 1200 lines codegen avg = 4800 lines total These numbers may well be quite a bit off, but my point is that it would likely not cost us more than a couple of thousand lines total. 2k lines for much more readable generated C? Yeah, sounds great!
Add a basic repl based on the JIT. Something very similar to http://www.stephendiehl.com/llvm/.
Could maybe be the starting point for an on-demand architechture? Would probably require some memoization mechanism so that we don’t unnecessarily check, monomorphise, and compile stuff we don’t need to.
Particularly the pre-LLVM ASTs. They’re very hard to read as text, but would probably fit really well as a graph. This could be useful both for debugging the compiler, as well as to debug compiled programs.
I’m not fully convinced yet, but I believe we might want to use bidirectional type checking instead of a unification based, HM-like typechecker in Carth.
HM shares a few properties with bidirectional typechecking, like implicit type abstraction / application, but it’s not the same thing. Proper bidirectional typechecking would give us an easy way to do implicit numeric coercions for proper subtypes, afaik.
- https://lobste.rs/s/mhdvzh/appeal_bidirectional_type_checking
- https://www.haskellforall.com/2022/06/the-appeal-of-bidirectional-type.html
- Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism, by Jana Dunfield & Neelakantan R. Krishnaswami
- Bidirectional Typing, by JANA DUNFIELD & NEEL KRISHNASWAMI
Linear types would allow predictable performance and behaviour of
e.g. IO tasks. Force a single manual file-close or
buffer-flush. Force a single free for malloc. Affine types would
allow better performance. E.g. pure, in-place modification of
array. If noone else points to it, value can be consumed and
modified rather than cloned. Something like: fn push(mut v:
Vec<i32>, x: i32) -> Vec<i32> { v.push(x); v } Implemented as maybe
a wrapper, or an interface? Maybe like in haskell with lolly
operator?
Things to consider: Linear arrow vs. `kind` approach or similar?
Check out Idris Uniqueness types, Linear Haskell’s linear arrows, and however Blodwen does it (linear arrows kind of I think).
Need some kind of system like type classes for ad hoc polymorphism. Maybe Haskell style type classes, Agda style implicits, or Ocaml style modules. Not sure.
“Type classes are functions from types to expressions” https://youtu.be/5QQdI3P7MdY?t=920. Interesting thought! Can we view type families the same way, but functions from types to types or smth? Maybe we can come up with more intuitive terminology.
https://www.microsoft.com/en-us/research/wp-content/uploads/1994/04/classhask.pdf https://static.aminer.org/pdf/PDF/000/542/781/implementing_type_classes.pdf
In Haskell, you can only have a single instance of a specific typeclass for a specific type. This doesn’t always make sense. Consider Semigroup for Int. Both + and * make sense, but we can only have one unless we goof around with newtypes etc, and that kinda sucks.
Consider an approach more like agda. That model is more lika basic Hindley-Milner + dictionsry passing, except the “typeclass” argument can be passed implicitly with the {} syntax! That seems really cool.
I’m not sure how implicit arguments work though. Does the compiler just look at all available bindings and pick the first/only available variable of that type?
https://agda.readthedocs.io/en/v2.5.2/language/implicit-arguments.html
https://agda.readthedocs.io/en/v2.5.2/language/instance-arguments.html
Or just do it kind of Haskell style, but give the instances names and allow multiple, overlapping instances, raisi g an error if the instance is ambiguous somehow.
Problem with instances as implicit arguments: https://youtu.be/2EdQFCP5mZ8?t=1259. We’d have to know exactly which instances exist for the same type, and from where they’re imported and what scoping they’ll have. That sucks. Another horrible thing: imagine creating a sorted list with one instance, and doing a sorted lookup with another (accidentally or not), you could an incorrect result with no error from the compiler!
Maybe an alternative could be to have both primary and
secondary instances, where the primary instances may not overlap
or be orphaned, like Rust, but may be passed implicitly, while
secondary instances may overlap and be orphaned, but must be
“overriden”/passed explicitly.
But that may also not work. For the following code,
foo :: Foo a => a -> a
foo = bar
bar :: Foo a => a -> a
bar = ...consider that we call foo with an explicit secondary
instance. What instance will bar be given? If we must pass
secondary instances explicitly, it seems bar would get the
primary instance, and foo and bar would be called with
different instances. BAD!
Probably last update for this section: this thread has convinced me that Haskell-/Rust-style typeclasses is the best idea.
<2022-08-15 mån>
I see I’ve already considered something similar in the section above.
Maybe we could get a sort of best-of-both-worlds this way. Consider two scenarios:
- The “Compare” trait and a “Map” structure.
We don’t want to have to specify the comparator every time we call an API function of Map, so some kind of implicits are needed. It’s also critical to the correctness of the Map that both “insert” and “lookup” are called with the same “Compare” instance. With plain implicit parameters, this can go wrong. A Map may be constructed in one module with (>) based Compare instance in the context. Then “lookup” is called on the Map in another module with a (<) based Compare instance in the context. No good.
So for these functions, when a trait instance is passed implicitly, there must only exist one.
- “Monoid” for lists
In most contexts, ++ is the operator that makes the most sense for mappend for lists. However, in some cases we may desire another behaviour. For example, mappend could choose the longer of the two lists. In Haskell today, the solution is to newtype wrap the type and provide another instance for that newtype. This works, but is a bit inflexible.
It would not be a problem if an alternative instance could optionally be provided.
My thoughts are only half formed, but I’m thinking that maybe we could have a system where only one canonical instance for a trait may exist,
and it may only be provided by the owner of the trait or the type – no orphans.
But anyone may provide an alternative instance, and may explicitly override the “canonical” instance in a context using a special form like:
(override myIntMulMonoid ...)
Consider: we create an override context, overriding the Cmp instance. In our existing code it may work fine, but what if we call some third party function, and in a future update they add logic to that function that depends on a specific Cmp instance? Maybe this could be fixed by allowing one to specify in the function signature how a trait is to be resolved. Like, you can choose to either always use the primary/canonical instance, or to primarily use the canonical instance, but use the overriden secondary instance if there is one.
tags: Algebraic effects
Seems like it could be more elegant than monad transformers, although maybe not as fast?
Effect fusion seems to make it faster?
Read Wu, Schrijvers 2014, 2015, 2016. I think their papers basically present the concept of fused effects.
github.com/fused-effects/fused-effects
https://youtu.be/vfDazZfxlNs?t=1730
^ det makear sense. Bygg basically upp ett träd av den här datatype, och interpreta det med alla handlers. Varje handler kollar om det är dens variant, och isf kör effekten. För varje handler blir trädet simplare, och till sist är det bara Pure kvar.
Naiv implementering ineffektiv. Bara tänk – måste interpreta ett träd ist för att bara göra effekterna direkt!
Man kan använda free monads för att bygga upp trädet, men detta är inte så effektivt.
Grundidén med papret “fusion for free” är att man vill bara traversa trädet en gång, och inte en gång per effect handler.
Med “fusion” verkar de syfta på funktionaliteten i GHC, att man kan
fusionera ihop funktionsanrop av specifika mönster till mer
effektiva varianter. E.g., map f . map g fusioneras till map (f
. g). På liknande vis fusioneras fold handleState . build . fold
handleReader till bara fold (handleState . handleReader). Kan vi
lösa detta utan kompilatorstöd, eller är det kanske värt att lägga
till?
See the talk on polysemy, it’s a good complement and alternative to the fused effects one. https://youtu.be/-dHFOjcK6pA.
We need type-level lists or sets, and a way to implement Member on that thing. If tuple types could contain higher kinded types, I think we only need classes.
See:
- https://youtu.be/z8SI7WBtlcA, https://youtu.be/z8SI7WBtlcA?t=1433
- Eff language
- https://youtu.be/XAnFUwIaZB8
- https://koka-lang.github.io/koka/doc/book.html#why-effects
In Rust, you can override the global memory allocator. Situational override is not really possible? I think either you use the global allocator, or you allocate with e.g. an arena explicitly.
In Zig, all allocation is explicit, and you have to pass around whichever allocator you want the functions to use. Pro: easy to override allocation for an object or sub-program with e.g. an arena. Con: verbose, bothersome, less convenient.
Maybe we could make heap allocations sort of semi-explicit in Carth, via an Effect system? Easy to override with e.g. arena allocator for specific functions, and not as inconvenient as Zig. Do-notation (or better? (like generalized application)) could make it fairly convenient, and there really is some usefulness to doing it. Would encourage keeping things on the stack whenever possible. But maybe it’s too much inconvenience for a high-level lang? I mean, couldn’t pretty much any closure actually heap allocate for the captures? Hmm.
I’m on the fence here, but the consensus seems to be that type families are better than fundeps. Also, it might be possible to avoid needing to implement Multi-parameter typeclasses if type families are available to compensate. Seems that would reduce ambiguities and mental overhead a bit.
Neither type families or fundeps are necessary if we have dependent types, but that would likely bring difficulties of it’s own.
Type families in Haskell vs Dependent types in a pseudo-Haskell vs Dependent types in Agda:
The wiki page is good. https://en.wikipedia.org/wiki/Type_family. Haskell wiki also has some interesting notes https://wiki.haskell.org/GHC/Type_families.
https://en.wikipedia.org/wiki/Lambda_cube
Does it complicate typechecking? It’s not obvious to me how it would?
In haskell, type families and data families are always open. Probably fine to keep it that way? Not sure the complexity of having both open and closed versions are worth it?
Relations:
- Function
- Value -> Value
- Typeclass
- Type -> Values
- Typefamily
- Type -> Type
- Dependent type
- Value -> Type
I don’t love the names “family” and “class”. Could we use something that makes more clear the relations above? Like “type function” or something? Although, I guess at least “class” wouldn’t be so bad to keep, for familiarity reasons.
Do we need data families as well? I’d prefer not to have to add them also. A little bit of inconvenience remaining is worth it if we can avoid a lot of complexity in the language.
Observation: Type families are just type aliases, but we can pattern match on the input.
Observation: A typeclass with associated types is basically an extension of normal typeclasses that makes it (Type -> (Type, Value)). Defining an associated type in an instance of a typeclass is basically a way of allowing one to add cases to the pattern matching after definition. Consider this:
(type (Foo a)
(Match a
(case Bar Int)
(case Baz Bool)))
this is the same as
(class (Foo' a)
(type (Foo a)))
(instance (Foo' Bar)
(type (Foo Bar) Int))
(instance (Foo' Baz)
(type (Foo Baz) Bool))
The difference being that with the typeclass version of typefamilies, cases/definitions can be separated from the declaration, and user modules can extend the type family by adding another instance.
;; Warning: some pseudocode and unimplemented features
;; The different possible forms, which would be basically
;; equivalent. Each could be convenient, but not sure if
;; it's a good idea to implement all.
;; Single case
;; Alias form
(type (Option a) (Maybe a))
;; <=> closed case form
(type (Option a)
(case (_) (Maybe a)))
;; <=> open case form
(type (Option a))
(type case (Option _) (Maybe a))
;; <=> class form
(class (Foo a)
(type Option))
(class case (Foo a)
(type Option (Maybe a)))
;; Multiple cases
;; Can't be described as alias
...
;; closed case form
(type (Result ok err)
(case (_ Unit) (Maybe ok))
(case (_ _) (Either err ok)))
;; <=> open case form
;;
;; Unlike value pattern matching, order shouldn't matter, as
;; we could be defining each case in a different
;; package. Some other algorithm for handling overlapping
;; instances would have to be used.
(type (Result ok err))
(type case (Result ok err) (Either err ok))
(type case (Result ok Unit) (Maybe ok))
;; <=> class form
(class (Foo ok err)
(type Result))
(class case (Foo ok err)
(type Result (Either err ok)))
(class case (Foo ok Unit)
(type Result (Maybe ok)))
Typeclass (Type, Values) vs Type family + normal typeclass:
;; 1
;; should implicitly create namespace `Iter`, so it's `Iter/Item` and `Iter/next`
(class (Iter it)
(type Item)
(: next (Fun it (Maybe [Item it]))))
(class case (Iter (Array a))
(type Item a)
(define (next arr) ...))
;; 2
;; <=> (except for namespacing)
(type (Iter-item it))
(type case (Iter-item (Array a)) a)
(class (Iter it)
(: next (Fun it (Maybe [(Iter-item it) it]))))
(class case (Iter (Array a))
(define (next arr) ...))
And in real Haskell that compiles, for comparison:
-- 1
class Iter i where
type Item i
next :: i -> Maybe (Item i, i)
instance Iter [a] where
type Item [a] = a
next = \case
[] -> Nothing
a : as -> Just (a, as)
-- 2
type family Item' i
class Iter' i where
next' :: i -> Maybe (Item' i, i)
type instance Item' [a] = a
instance Iter' [a] where
next' = \case
[] -> Nothing
a : as -> Just (a, as)https://blog.rust-lang.org/2021/02/11/Rust-1.50.0.html#a-niche-for-file-on-unix-platforms
class Iter c where
type Item c
next :: c -> Maybe (Item c, c)
nextList :: [a] -> Maybe (a, [a])
nextList = \case
[] -> Nothing
a : as -> Just (a, as)
instance Iter [a] where
type Item [a] = a
next = nextListclass Iter c where
item :: Type
next :: c -> Maybe (item, c)
nextList :: [a] -> Maybe (a, [a])
nextList = \case
[] -> Nothing
a : as -> Just (a, as)
instance Iter [a] where
item = a
next = nextListrecord Iter (C : Set) : Set1 where
field
item : Set
next : C -> Maybe (item × C)
nextList : {A : Set} -> List A -> Maybe (A × List A)
nextList [] = nothing
nextList (x ∷ xs) = just (x , xs)
listIter : {A : Set} -> Iter (List A)
listIter {a} = record
{ item = a
; next = nextList
}
https://github.com/Microsoft/language-server-protocol https://internals.rust-lang.org/t/introducing-rust-language-server-source-release/4209
Prefer somewhat big / wide stdlib. Small / bad standard library + good package manager => npm / cargo situation, where everything has sooo many dependencies. Having a dep is not bad per say, but when the numbers completely blow up, like in rust- and javascript-land, things can get messy. The best way to avoid this, I think, is having a standard library that has you covered for most common things.
Examples of libraries in other ecosystems that should be part of the stdlib: `is-even` in JavaScript, `composition` in Haskell, `rand` in Rust.
Go seems to have done this relatively well. Their stdlib has everything from JPEG codec, to a webserver. The stdlib shouldn’t have everything though, as that will add a bunch of legacy cruft over time, like in Java. Would not be as much of a problem if we’re not afraid of releasing new major versions removing deprecated stuff.
Maybe separate stdlib into core and std. Core could be a smaller subset which is pretty much purely implemented in carth, so it’s easy to use with interpreter and comptime. Conditional compilation to use efficient C/Rust versions normally.
https://www.tweag.io/blog/2022-05-05-existential-optics/ https://github.com/hablapps/DontFearTheProfunctorOptics
How to best structure the numeric typeclasses? Num in Haskell is
a bit coarse. For example, you have to provide *, which doesn’t
make much sense for Vec3, so you can’t give a proper instance for
Vec3 to get +. Maybe numeric-prelude could be a good
alternative to look at?
Lossless etc. No truncation by accident. SBCL LISP does this I think?
Consider type size and overflow though. Maybe only do this for arbitrary-sized Integer, and not for fixed-sized Int.
Mutex, semaphore, etc.
Look at how Rust and Haskell do it.
Also, look at the crate parking_lot, which does replaces the standard Rust primitives with smarter ones. E.g. the mutex does a small number of spins first, to avoid expensive thread juggling by the OS when the critical section is very short, but resort to the usual process interrupts in case it goes on for longer, to avoid priority inversion which is a problem with spinlocks. https://matklad.github.io/2020/01/02/spinlocks-considered-harmful.html https://matklad.github.io/2020/01/04/mutexes-are-faster-than-spinlocks.html
Lock Free Data Structures using STM in Haskell: https://www.microsoft.com/en-us/research/wp-content/uploads/2006/04/2006-flops.pdf
References:
We need good collections & algs for sorting etc. if Carth is going to be of any use to anyone. Would also be a good way to add to the set of test-programs & find the worst pain points of current Carth.
Many of these have implementations to look at and compare to on rosettacode.org.
This list is sort of off the top of my head, so some might not be good fits in a purely functional language. Look at some resource on persistend data structures as well.
- Priority queue
- Binary tree (2-3 tree better?)
- B-tree (specifically 2-3 tree?)
- Random number generator
- bubble, insertion, selection sort
- quicksort
Not that getting users is a primary concern, but if someone is indeed curious, I don’t want them to be scared off by the process of getting started seeming complex.
https://news.ycombinator.com/item?id=23347357 https://www.hillelwayne.com/post/learning-a-language/
System to register a function as a destructor for a value, which can be used to destroy / close resources when the value is no longer used and garbage collection happens. It’s not optimal that resources may stay open for quite a while after last usage, but it’s better than never being closed.
Example use case: We don’t want to have to use linear types to manually destroy Lazy values when we’re done with them, but we still need to make sure that their mutexes are destroyed at some point.
https://www.hboehm.info/gc/finalization.html
Boxing vs monomorphization. Boxing results in smaller binary and dynamically-linkable interface, but results in slower code (but not necessarily always, and maybe not by much!).
Dynamic dispatch: Like Box<dyn TRAIT> in Rust. Might be useful in
places. Should not be that hard to implement – just heap allocate a
vtable, and populate it with all of the class functions. Might need
to add wrappers so that the functions always accept the type by
reference? Or all args by reference? Unless we modify the compiler
to always pass args by reference. In Rust, I suppose they defer
the problem by only allowing one to call &self and optionally
&mut self methods on a trait objects. Don’t have to consider sizes
if you can’t even call self methods in the first place.
Must consider how this interacts with monomorphization vs. boxing vs. value witness tables for static dispatch.b
Read Tristan Hume - A Tour of Metaprogramming Models for Generics for an overview of how different languages implement generics. online, locally.
When compiling a library, especially a dynamically linked one, how do we allow the export of polymorphic functions? We can’t really use monomorphization, as we can’t predict which types there should be instantiations for. Boxing would solve this problem and result in a smaller binary, but the code would most likely be slower, and the FFI would become more complicated.
Maybe monomorphize all package-internal code, and require boxing for all public-facing polymorphic functions? Could require some keyword or special form, like `boxed`, to make it clear when the FFI will be affected.
<2021-06-21 mån>: Try implementing polymorphism w boxing (& dict passing). Mono may really not be all that great, and it’s really not that elegant. Big code size, slow compile times, no HRT, etc. Look at my own old post.
“With that said, I agree that eager monomorphization is an error, in my book.
In a sense, monomorphization is exactly like inlining (copy/pasting). It feels strange that compilers would have complex heuristics to determine when to inline, when not to, and even in recent releases when to outline and yet… they just monomorphize everything template/generic without pause.”
Maybe box by default, and box all external functions, but like inlining, do monomorphization of appropriate function instantiaitons heuristically.
From Tristan’s text, on Haskell’s dictionary passing:
“Another way of implementing dynamic interfaces than associating vtables with objects is to pass a table of the required function pointers along to generic functions that need them. This approach is in a way similar to constructing Go-style interface objects at the call site, just that the table is passed as a hidden argument instead of packaged into a bundle as one of the existing arguments.
This approach is used by Haskell type classes although GHC has the ability to do a kind of monomorphization as an optimization through inlining and specialization.”
See Switf’s approach with the Value Witness Table. Basically, instead of passing generic types as completely opaque boxes, pass them as more of a sort of trait object, with some bundles functions for allocating and copying the type on the stack etc. Otherwise we have to store everything on the heap, even primitive types?
Above paragraph is slightly misleading. Tristan explains witness tables well:
“Swift makes the interesting realization that by using dictionary passing and also putting the size of types and how to move, copy and free them into the tables, they can provide all the information required to work with any type in a uniform way without boxing them. This way Swift can implement generics without monomorphization and without allocating everything into a uniform representation! They still pay the cost of all the dynamic lookups that all boxing-family implementations pay, but they save on the allocation, memory and cache-incoherency costs. The Swift compiler also has the ability to specialize (monomorphize) and inline generics within a module and across modules with functions annotated @inlinable to avoid these costs if it wants to, presumably using heuristics about how much it would bloat the code.
This functionality also explains how Swift can implement ABI stability in a way that allows adding and rearranging fields in structs, although they provide a @frozen attribute to opt out of dynamic lookups for performance reasons.”
This sounds really good! Single definition generation without expensive boxing! Monomorphization as an optimization!
Value Witness Table in Swift seems to contain:
- Size
- Alignment
- Copy constructor
- Move constructor
- Destructor
If this was rust, .clone() would be an explicit call and a move wouldn’t call any constructor or destructor, so the only things contained would be:
- Size
- Alignment
- Destructor (Drop)
We don’t even have Drop yet, so the WVT only has to contain the type’s size and alignment. Not much of a table heh…
We’ll have to do some kind of dictionary passing for the classes Cast, Num, Bitwise, and Ord I think.
So for a polymorphic function, generate a single function that takes
a reference to the value, a VWT (size, alignment), and dictionaries
for any class constraints. In the generated code, use the VWT to get
the size for when we need to allocate memory for the type, or
memcpy. I’m thinking we won’t need to though, right? Since it’s
already on the stack since it’s behind a reference, we don’t need
the size for alloca, and we only do store/load after a gep when
indexing into the type, right? And that will only be done in
monomorphic functions I believe.
We must have what Swift calls “Metadata Patterns” as well. Say we
have (define: (twice a) (Fun a [a . a]) (car (id [a . a]))). We
only pass the VWT of a to twice, but we must also pass the VWT
of (Pair a a) to id, as well as the offset of the second element
of the pair to car. The second VWT and the rest of the metadata
about the datatype must be constructed at runtime. So for every
parametric datatype, we must generate a function that takes a VWT
for each datatype parameter, and returns a type metadata
value. The type metadata, beyond the VWT of the datatype, must also
contain the offsets of each struct member.
Metadata pattern example in Swift:
metadata pattern for Pair<T> - first: T - second: T - value witness table metadata for Pair<Bool> - T: Bool - first: offset 0 - second: offset 1 - value witness table metadata for Pair<Int> - T: Int - first: offset 0 - second: offset 4 - value witness table
Generic member access in Swift:
- Example:
func getSecond<T>(_ pair: Pair<T>) -> T { return pair.second }
- Implementation:
void getSecond(opaque *result, opaque *pair, type *T) { type *PairOfT = get_generic_metadata(&Pair_pattern, T); const opaque *second = (pair + PairOfT->fields[1]); T->vwt->copy_init(result, second, T); PairOfT->vwt->destroy(pair, PairOfT); }
More things to consider when HOF:s are involved! https://youtu.be/ctS8FzqcRug?t=776
Consider the case of a HOF accepting a monomorphic function. Something like:
(define: (apply f a)
(forall (a) (Fun (Fun a a)
a
a))
(f a))
Apply is a higher order function, and the type of the parameter f
is polymorphic (not higher ranked though). Therefore, in the lowered
apply, the lowered type of f will be something like
void (*)(opaque *ret, opaque *arg, void *ctxt)
What if we now have a simple, monomorphic function like neg, of
higher type (Fun Int Int). In the high domain, (Fun Int Int) is
compatible with (Fun a a), but in the low domain,
Int (*)(Int arg, void *ctxt)
is not compatible with
void (*)(opaque *ret, opaque *arg, void *ctxt)
We thus need to generate an abstracting wrapper around concrete functions when passing them to a function that takes a non-concrete function as argument.
Swift uses the terminology “Abstraction Patterns”. “One formal type, many lowered representations”. “Introduce thunks to translate between representations”. To pass a concrete function as an abstract argument, they use what they call a “re-abstraction thunk”. “We need to re-abstract the closure value, to match the abstraciton pattern of the function parameter. We do this using a thunk”.
The method itself is very obvious.
Int closure(Int a) {
return a + 1;
}
void thunk(Int *ret, Int *arg, void *thunk_ctxt) {
Int (*fn_invoke)(Int, void*) = thunk_ctxt->...;
void *fn_context = thunk_ctxt->...;
*ret = fn_invoke(*arg, fn_context);
}
void *thunk_ctxt =allocate(..., closure, NULL);
apply(..., thunk, thunk_ctxt, ...);See:
What if we did
(define (foo x pair)
(match pair
(case [x (let y)] (Some y))
(case [_ _] None)))
instead of
(define (foo x pair)
(match pair
(case [x' y] (if (= x x')
(Some y)
None))))
Like in Rust. Very convenient.
match foo {
(1, x) | (5, x) => x * 2,
(_, y) => y,
}Like F# has. Something to consider. https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/active-patterns
Could enable us to use pattern matching more?
Haskell has something similar.
See matching on the Seq type.
I think Zig has this, and in Rust you can use the external tool
bindgen to generate Rust declarations for C headers ahead of time.
I just think it would be nice to not need to manually translate header files to use external libraries like OpenGL or SDL or whatever.
For infinite recursion/loops, we optimize tail-recursion to loops atm. But it’s not obvious to the untrained eye when this will happen!
A tail keyword that simply causes a compiler error when a recursion can’t be optimized would be good.
Sort of like Rust is considering the `become` keyword to work?
Another alternative / complement would be to add syntax in Carth for the Loop construct in our Low IR.
Sort of like Futhark’s loops.
Possibly using Rust’s builtin stuff. Also possibly use some Zig library?
Otherwise, this Suckless library seems quite nice: https://libs.suckless.org/libgrapheme/
Very small! That’s always a plus :)
Since I’ll likely be adding linear types anyways, adding a borrow checker based on that might not be too difficult. I’m not 100% I’ll do it – there’s Carp or Rust or whatever if you prefer that. I’m more into Rc/GC for this language actually.
But anywho, in case we ever want to add borrow checking, I’ll collect some useful notes here.
Check out Polonius, the new borrow checker in Rust. https://youtu.be/H54VDCuT0J0
We already do dead code elim almost by mistake in Monomorphize, but
we still generate declarations and wrappers for all
extern:s. Getting rid of them would be nice.
Could be used at different steps of compilation, for different purposes.
- Procedural macros
- Can do more advanced generation.
- Derive
- Using a similar mechanism to procedural macros, generate typeclass instances.
- Conditional compilation
- If we for example allow comptime expressions evaluating to syntax at top level, we could use a mechanic similar to procedural macros for conditional compilation. Just have an if-expression on some compiler-defined global variable specifying e.g. what the platform is.
- Dependent types
- Instead of having function and type-function definitions exist in separate spaces, like in Haskell, we could use normal functions. Could also use normal values, instead of having to redefine them at the type level (like having to define peano numbers and use datakinds in haskell).
- Optimization
- Compute stuff att compiletime that can be computed at compiletime. Could probably use a mechanism similar to the dependent types to evaluate glob vars at compile time.
Look at how zig, agda, and rust does it.
Zig doesn’t have macros – their comptime only happens somewhere around the typechecking step. I think their comptime is evaluated by interpreting some mid-level IR. https://www.youtube.com/watch?v=8MbREuiLQrM
Rust has constfn. Interpreting Miri.
Agda idk.
Query-based / on-demand compilation would make things much simpler, I’m fairly sure. Maybe even a prerequisite.
proc-macros + parsing + mutual recursion seems like it might be a
little tricky to solve. What if a proc-macro calls another
proc-macro defined later in the file? Need to parse everything, so
we can parse everything. Chicken and egg problem. Using Haskell
laziness and fix might work. But the proc-macros don’t just need
to be parsed, but also typechecked and interpreted… Seems like
tons of monadic complexity might surface.
Do we do something like the typechecker, finding references and constructing a topological order of recursion groups ahead of time? Maybe use some kind of continuation-mechanism to exit parsing as soon as a proc-macro application is encountered, allowing resumption as soon as it has been defined?
What about this: (direct or indirect) references to self must be at the “same level”, i.e. you can’t use self to generate the syntax of self, but you can call self as a normal (mutually) recursive function.
So basically, if when doing query based compilation (which is depth first), and we reach a parsetime/macro application of self while still parsing self (i.e. it’s in a stack of symbols of currently being parsed defs or smth), we return an error.
Or maybe do like the typechecker and gather macro refs ahead of
time. Like traverse the tree, and within all (parsetime ...) (or
whatever) blocks, gather all referenced names. Do this for the while
graph of referenced names recursively. In the end, we have a graph
of all names necessary to parse the entry definition. Make a
topological order. Compile them (to interpretable AST) in order. If
there are any cyclical groups, compilation error.
https://lobste.rs/s/zon0fi/time_i_tried_porting_zig_serenityos#c_w7ghy3 “Remember: when in doubt, `clang -c -save-temps -emit-llvm test.c && llvm-dis test.bc && less test.ll`”
Like Typescript (I think, I’m not all that familiar with it). Could be nice for error handling, for example. That’s one of the problems in Rust – you have to use all these fancy crates or write a bunch of boilerplate just to allow a function to return two different types of errors.
Java, where exceptions can be combined as a union, essentially:
public Foo foo() throws SomeException, OtherException {
bar(); // throws SomeException
baz(); // throws OtherException
}and Rust, where you have to combine the different types somehow:
fn foo() -> Result<Foo, MyErr> {
bar().map_err(MySomeErr)?;
baz().map_err(MyOtherErr)?;
}
enum MyErr {
MySomeErr(SomeErr),
MyOtherErr(OtherErr)
}when there is a spec.
Would be nice, to have concrete documentation for what is ok and what is not.
https://blog.royalsloth.eu/posts/the-compiler-will-optimize-that-away/
Convenient syntax for using SoA/AoS could be nice for lowe level stuff, or we might consider it too seldom an issue for a somewhat high-level languge like Carth.
Recursion schemes are functions that capture patterns of recursion, like fold and unfold. These 2 are simple to implement. Other schemes, less commonly used yet frequently applicable, like cata, could be implemented as well, but might require some built in support or smart “deriving”.
Look at https://hackage.haskell.org/package/recursion-schemes-5.2.2.1
Maybe deriving functor and/or foldable could include this base functor thingy?
https://wiki.haskell.org/Hoogle
Zig seems to have a smart solution that doesn’t require a separate `async` version of the standard library, unlike Rust with `async-std`.
https://ziglang.org/download/0.6.0/release-notes.html#Async-IO
Also look at how Haskell does it. It’s probably smart.
Either in Carth directly, or via a DSL or something. Some method of doing flattening and parallelisation like Futhark? Compile to OpenGL & Vulkan maybe.
I’m thinking of a system where you annotate functions in a source file with pre- and postconditions, which can then be checked in different modes depending on how much time you’ve got etc.
- Proof-mode. Exchaustive checking of conditions. All possible inputs are generated, and the system checks that the precondition always implies the postcondition.
- Test-mode. Statistical, random testing. Generate enough inputs such that the precondition is fulfilled for a statistically significant subset of the complete set of possible inputs.
- Debug-mode. Functions are not tested ahead of time, instead assertions are inserted and checked at runtime.
- Release-mode. Conditions are completely ignored.
Like a typechecker-pass but for generated documentation. Verify that all links are alive, that examples compile and produce the expected output, etc.
Sort of like in Ada?
“overflowing -10..100” “saturating 1..15” It automatically implements arithmetic operators to saturate, overflow, or panic by default as specified. The range is fit into the smallest integer that can fit it. So “256..511” is stored un a u8, and the semantic 256 is represented as 0 in generated code.
When the int is cast, it is not bitwise cast. Casting “256 :: 256..511” to u16 results in 256. Look at Ada.
Also, niches in Rust is slightly similar.
In Rust, Option<NonZeroU8> fits in a single byte, because the None is stored in the 0.