Kright

On programming language design

I’ll keep adding to this text, for now it’s closer to a list of interesting ideas and concepts from different languages. I try to write objectively, but I admit that my subjective experience and knowledge heavily influence the text.

Homoiconicity

wikipedia

The idea is that code in a programming language can be represented as data and transformed somehow. An example - Lisp-like languages.

(* (+ 2 2) 2)

You can look at this as code, or you can look at it as a list. The structure of the list matches the syntax tree. This approach gives gorgeous support for metaprogramming, macros manipulate code like ordinary lists, and then the code can be run.

To manipulate code, the language needs a mechanism for quoting (get the data that describes the code) and splicing (turn that data back into code)

Evaluation strategy

wikipedia

Unexpectedly, Wikipedia turned out to have a whole table with a bunch of different strategies, but globally I’d split them into three:

  1. Call by value - what most programming languages have, when all the function’s arguments are evaluated before it’s called.
  2. Call by name - the argument is passed into the function “lazily” and is evaluated only if it’s needed, but it may be evaluated several times. Used in ordinary languages for booleans in expressions like bool1 && bool2.
  3. Call by need - like call by name, but the result of the first evaluation is remembered. Used in Haskell.

I don’t see the point in looking at all the variants like passing pointers or const references, you can consider them call by value where a pointer to something is passed.

Scala supports a call by name variant, and this feature is cool. Example:

sealed trait MyBool
case object MyFalse extends MyBool
case object MyTrue extends MyBool

def f1(): MyBool =
    println("f1")
    MyFalse

def f2(): MyBool =
    println("f2")
    MyTrue

def myAnd(left: MyBool, right: => MyBool): MyBool =
    if (left == MyFalse)
        MyFalse
    else
        right

myAnd(f1(), f2())

Basically, it’s the same thing that’s done with bool values in most languages, but usually you can’t make a similar type with the means of the language itself.

Besides, all sorts of constructs like

map.getOrElse(key, new Value())

won’t create a new Value if there’s something in the map. Very convenient and pretty.

Function call syntax

The best known one is like in C:

f(1, 2, g())

In LISP the opening paren goes before the function name.

(f 1 2 (g ()))

For some reason, with Lisp I periodically get the feeling that there end up being too many parens.

Besides, in Haskell it could look like this:

f 1 2 (g ())

Basically like in Lisp, but with fewer parens. And from Haskell’s point of view the arguments are passed one at a time. Like, f takes 1, returns a function that gets passed 2, that one returns a function that gets passed (g ()). And you can pass a couple of arguments, do some logic, and then pass one more argument.

This is possible in Scala too, but the syntax is different:

val func = f(1, 2, _)
func(g())

With this approach the language doesn’t forbid currying, but it’s used deliberately and only where it’s needed, all the other calls work efficiently and don’t create lambdas.

There’s also a funny (and close to assembly) variant in Forth - there all the arguments are just thrown onto the stack, and then the function is called.

In some languages (Groovy, Kotlin, Scala, C#) you can make extension methods

extension (a: Int) def myAdd (b: Int): Int = a + b

1.myAdd(2)

In fact these are the same functions of two arguments, but with a different call syntax.

Sometimes languages let you drop the parens

1 myAdd 2

I haven’t come across attempts to generalize this approach to a more general case, in theory it could look like this:

def[T] if(cond: Boolean) then (body: => T) else (otherBody: => T): T = ...

then you could introduce “new” basic constructs of the language.

But the question of resolving the ambiguity of such constructs stays open. For example, if there’s a second definition next to it, but without else:

def if(cond: Boolean) then (body: => Unit)

The parser will have to figure out that it should use the longer definition.

Tuples and Unit

Pascal and Delphi had two separate entities - procedures and functions. The former returned nothing, the latter returned something.

In many languages you can pass N parameters into a function, but you can return only one. And in the jvm, for example, this is nailed down at the bytecode level. You can make an object for a pair of numbers, but the jvm will create it as an object and performance will be lower.

In some languages (Python, Go) everything is symmetric and you can return several values. In some other languages (C++, Scala) the standard library has tuples and a function can return them. As a bonus, tuples usually come with syntax for unpacking them.

val (x, y) = getPair()

You can look at the Unit type as a tuple of zero elements. And at a procedure - as a function with return type Unit.

And if you build tuple support into the language, you get a beautiful universal picture:

  1. Any syntactic construct in the language is an expression. It’s just that some of them return Unit.
  2. Procedures are functions that return Unit
  3. A function can return any number of values
  4. A function takes any number of arguments (and they’re essentially a tuple too)
  5. It’s easy to write wrapper functions for other functions, for example ones that log or memoize results.

Tuples can also be called product types.

Structs and named tuples

If you ignore mutability, you can notice that structs in C are essentially tuples, but every field has a convenient unique name. But, unfortunately, there are nuances with how sizeof() works and a struct with no elements may turn out to be one byte in size (while ideally it should be zero-sized, and there may also be differences between C and C++)

Function arguments can also be seen as a named tuple, some languages allow writing things like f(x=1, y=1).

And if you look at a function as a thing that takes a tuple as input, then tasks like “make a wrapper for a function” turn out to be quite simple and independent of “how many arguments were passed”, because there’s only one argument, in the form of a tuple.

Or, for example, you’ll be able to define Set<T> = Map<T, Unit> and ideally not take up any space for storing the values.

Symmetry between function arguments and the result.

Scala 3 got an experimental feature that lets you define the names of a tuple’s fields in the function signature. And it’s all done at compile time, at runtime it’s the most ordinary tuple.

def divide(a: Int, b: Int): (quotient: Int, remainder: Int) =
  (quotient = a / b, remainder = a % b)

In my opinion this is very beautiful - just like we give names to the arguments, we can give names to the returned fields the same way. You can get this in C if you create a struct and return it, but the thing is that the struct definition has to be given somewhere separately and usually people are too lazy to do that. That’s where the perversions start, like passing a pointer to the place where the result should be written and so on.

Kinds of immutability

There are several, and it’d be nice to tell them apart:

  1. a mutable variable
  2. a variable that can’t be changed in the current context, but generally speaking it can change
  3. a variable that won’t be changed while there’s an immutable reference to it (like in Rust)
  4. an immutable variable that was initialized at some point and will never change again
  5. an expression that can be evaluated at compile time
  6. a compile-time constant (literal)

What the nuances are: In dynamic languages the notions of compilation and execution are mixed together and there are no particular problems. In a static language, if you want to have some compile-time computations (hello, constexpr in C++), in fact you’ll have to come up with some subset of the language (or even end up with a different language). All sorts of constexpr if, constexpr int f() and so on will show up. Maybe if you design a language “from a clean slate”, this will come out more organic.

Immutable variables that won’t change in the future are very convenient for multithreaded programming.

For item 3: a reference has a lifetime, and while the reference is alive, the value accessible through it won’t change. The language allows having either one mutable reference or many immutable ones.

For item 2, C++ has all sorts of const references and const methods, but they act on the whole object “at once”.

In theory the mutability from item 2 can be done with interfaces. Actually, that’s how it’s usually done in JVM languages.

In languages like C++ and Rust it’s hard to make const objects, they lose the ability to be moved. Languages with a GC don’t have this problem.

Nullability

Null errors are easy to make and you want to avoid them. You can split types in the type system into those that allow null and those that don’t.

In Kotlin this is done with a type with ? at the end. For example

String // non nullable
String? // nullable
(String?)? // same as String?

The notation is very compact, but I don’t like it. In generic programming it can cause pain, because an abstract type T can be anything. And what’s worse, for T = String? you get T? == T, but for T=String it’ll be T != T?

In my opinion, this complicates the language, and it’d be more convenient to have (from the type system’s point of view) separate types Option[String], Option[Option[String]] and so on.

I’ll note that Kotlin made this choice for a reason, it’s as close as possible to what the jvm can do.

Extra credit questions:

  1. how do you make the Option[Pointer] type take up as much memory as an ordinary nullable pointer?
  2. What do you do with Option[int] or an abstract Option[T]?

Models of generics

Inspired by this article: https://thume.ca/2019/07/14/a-tour-of-metaprogramming-models-for-generics/

Globally there are two approaches:

  1. monomorphization: generate a new version of the code for each type. This covers generics, macros, code generation. Languages - C, C++, Rust, Haskell, Go, Zig.
  2. boxing: look at different objects in some uniform way.
    1. type erased generics - like collections in java, at runtime their type isn’t known
    2. vtables - the object stores a table of methods (C++, Java, Go, Rust, Python)
    3. dictionary passing - pass a table of functions. (typeclasses in Haskell, witness table in Swift)

The downside of monomorphization - source code bloat and slower compilation. The downside of boxing - potentially lower performance.

OCaml has a funny kind of boxing - all objects are the same size, but from the very first bits you can tell what’s in the object - an actual value (int) or a reference to something on the heap. In Swift the witness tables hold information on how to move or copy the object. And on top of that Swift has the @inlinable annotation, to generate fast code like in C++.

Another interesting point - a language with a JIT can take a step from a “universal” function to monomorphization and get faster code in the hot spots.

Ways to create objects

There are several approaches:

  1. Static constants and variables (singletons), available for the whole lifetime of the program. On the plus side - a simple approach, no need to think about lifetimes. You can put the data in a write-protected region of memory. This approach is often used in microcontrollers. On the downside - the approach only applies to things that will definitely be needed.
  2. You can allocate objects on the stack, as a bonus you get automatic memory release, as a minus - you can’t opt out of the release, that same place on the stack will be reused in the future and the object will “go stale”. The stack size is limited (on the order of 1-10 MB, you can make it bigger if you want).
  3. You can create objects on the heap and manage pointers to them manually or through reference counting. Pros - the object lives on the heap, the object’s size doesn’t matter, you can pass a pointer to it around. Cons - heap allocation may be a bit slower than on the stack. Errors like memory leaks or attempts to delete an object several times are possible. Memory fragmentation is possible, when small objects are scattered all over it and something bigger doesn’t fit between them.
  4. Region-based: a memory region is created for some task, temporary objects are created in it, then when the task finishes the whole region is freed. Pros - simple and fast memory release. Partial resistance to leaks: they’ll stay inside the region. Regions can be used in different ways: for example, you can not free objects at all, create every new one in a new place, not use destructors and then free everything as a whole. It’ll be simple, fast, but possibly not efficient in memory consumption. Or you can allow “freeing” objects in the region, but then you get problems with memory fragmentation. The approach is used in gamedev - for example, you can make a region for the objects of a game level and free it when the player moves to another level. Another variation: a custom allocator for some specific type. For example, you can make an array for a thousand game objects, on “creation” the allocator will return a reference to some object in the array, on release it’ll mark it as “unused”. Pros: compact placement of objects, convenient iteration over all objects of that type. Cons - it hardly makes sense to make separate allocators for every type. If you use a pre-created array of some size, there’ll be an upper limit on the number of objects, and the memory will be taken regardless of how many objects were actually created.
  5. Use a GC. In my opinion, there’s a fundamental difference between a GC and reference counting: a GC can move objects, updating the references between objects. This lets you avoid fragmentation, but takes away control over where objects sit in memory. Technically a language with a GC can have destructors (finalize in Java), but using them isn’t recommended. On the plus side - it’s hard to make a memory leak. The code is simpler, especially multithreaded code. All the complexity of multithreaded freeing of objects and traversing them falls on the virtual machine, but there’s one of it, and there are many programs. Cons - less control, potentially lower performance. In theory, the virtual machine can use regions inside, shuffle objects between them somehow and then free a region with unused objects in one fell swoop. Again, as an optimization the virtual machine can place temporary objects on the stack, but that’s not guaranteed. Another important point - it’s hard to “marry” two languages if each has its own GC that doesn’t know about the other one. Besides, usually a language either has no GC at all, or has it for everything there is in the language, there aren’t really any “in-between” options. Maybe the “in-between” options need some extensions to the type system, to tell apart the “inside GC” and “no GC” contexts and not let references to GC objects escape outside. Since the GC has to know about all the references to a GC object in order to move or free it. But at the same time there has to be some way to manipulate the objects from the “no GC” world, for example in the implementation of the GC.

Exceptions

  1. You can do without them (C, Go, Rust). The language gets simpler. On the downside - you have to explicitly pass error codes or something else along the chain and pay the overhead of passing/checking them. Usually for unforeseen cases there’s still exit(1) or its counterpart for a fatal error like panic().
  2. Checked exceptions. Exceptions that have to be explicitly listed in the function signature. Both the language and the code in it get more complicated, and there are cases when the interface signature has an exception, in practice nobody will ever throw it, but you still have to handle it. In fact the idea isn’t very convenient, Scala/Kotlin dropped it.
  3. Unchecked exceptions. Pros - usually there’s no big overhead if the code doesn’t throw exceptions. If the code does throw them, performance can drop badly. Cons - the language gets more complicated, an exception can fly in from some unexpected place. The programming language gets more complicated, RAII needs special support.
  4. Algebraic effects. Seems like a thoroughly functional and abstract approach. Built-in support exists in Koka and OCaml 5, in Haskell effects are done as libraries. I’m not very familiar with it, I’ll just leave links: wikipedia, an answer on Stack overflow, a description of the Koka language

Fun fact - in Python, code that throws exceptions runs almost as slowly as code that executes normally, because Python itself is interpreted and very slow.

Covariance and contravariance

wikipedia

Say there’s a type Animal and a type Dog inherits from it, and Corgi from that one. Let’s write this as Animal :> Dog and Dog :> Corgi

Covariance: if Animal :> Dog, then (T => Animal) :> (T => Dog) - a function that returns a dog will do anywhere a function returning an animal is expected. Contravariance: if Animal :> Dog, then (Dog => T) :> (Animal => T), the relation goes the other way - where a function of a dog is expected, a function that takes any animal will do too. Invariance: say, if there’s a cage with a dog Box[Dog], you can put a dog in or take one out. But “put in” and “take out” give constraints from both sides, we can’t put an animal into the cage and can’t take a corgi out of the cage, there could be any dog in there. As a result a cage for dogs and a cage for corgis are completely different objects. Bivariance: a variant that usually isn’t mentioned (or maybe I understand it wrong). But sometimes the type may not matter at all. For example, if we want to find out what color the cage is, we don’t care at all who it was made for. def getColor : Box[T] => Color

Basically these relations are everywhere there are generics, but in places it’s “hidden under the hood” and done through bridge methods in the JVM or some other way.

Linear types

wikipedia: Substructural type system

Practical use: the concept of ownership of an object, it has to be deleted exactly once. Used in Rust. There are generalizations with less strict constraints like “use at most once” or “use at least once”.

Cons: in my opinion, in Rust it’s done inconveniently, in places it imposes a bunch of restrictions. Some data structures like doubly linked lists are extremely hard to describe in it. That doesn’t mean the idea of linear types itself is bad, maybe in the future there’ll be some progress in terms of flexibility and convenience.

It’d be very interesting to cross them with a GC language, this would give interesting possibilities:

  1. You can reduce the load on the GC and explicitly state that some things will be deleted and exactly when
  2. The language would let you write both low-level code without a GC and high-level code with it. Right now this is achieved when, for example, people write libraries in C and then use them from Python, but those are two entirely different languages, not one universal one.
  3. GC isn’t the only way, there are narrowly specialized approaches like using allocators that work well in some cases. For example, when the whole arena is freed without deleting each object.

Local functions

In C you can’t declare a function inside a function. Pros - simplicity, cons - bloated function code, inconvenience when writing code.

C++: you can declare a lambda inside a function. You have to explicitly state what gets “captured” and how. There’s a difference between lambdas and functions.

Kotlin: you can declare a function inside a function, but there are restrictions - for example, a local function can’t have the inline modifier. “Capturing” happens automatically (in fact temporary cell objects holding the variables get created)

Scala: like in Kotlin, but fewer restrictions.

Scope for variables

  1. Variables are declared before the block or at its start. Pascal, Delphi, old C standards. The simplest approach
  2. A shared scope for variables inside a function. Often used in interpreted languages, to create just one table for the whole function call. The downside - constructs like loops and so on don’t have their own scope, temporary variables “leak” into the function’s scope.
  3. Variables are declared anywhere in the block, the type is fixed. The approach of most languages.
  4. Every next expression in the block opens “its own” scope, and in it the types of variables may be different. Used in Kotlin and Rust

An example for Rust

fn f() {
    let a = 1;
    let a = a.to_string();
}

In Rust this feature is necessary for linear types, so that after an object is freed you can’t access it anymore.

An example for Kotlin (there it’s called smart cast )

fun f(a: String?) {
    if (a == null) return;
    val nonNullableA: String = a;
}

This approach, it seems to me, noticeably complicates the compilation rules. For example, less trivial cases are possible:

fun f(a: String?, b: String?) {
    if (a == null || b == null) return;
    val nonNullableA: String = a;
    val nonNullableB: String = b;
}

The compiler still copes with the previous code, but not with the next one:

fun f(iter: Iterable<String?>) {
    val iter2: Iterable<String> = iter.filter{ it != null } // error!!
}

What you can do with abstract objects

Depending on the language, some options or others are available. Experience in some language often heavily skews your thinking and some capabilities seem to go without saying. My experience is mostly from the JVM.

  1. Comparing object references: in the Jvm they want to drop it for Value Objects. This will give the JVM more freedom, such objects can be copied and moved.
  2. Comparing an object with an object of another type: Far from always needed. When comparing, say, a String and an Int, the result is always False and most likely the code is incorrect.
  3. Computing a hash: in the JVM every object has it, but maybe it should be an explicit interface.
  4. Cloning an object: again, this feature should be an interface, not a capability of any object
  5. toString(): a method that’s very handy for debugging and so on, but it’s not a given that it’s needed always and everywhere. Again, maybe it should be an interface.
  6. synchronizing on an object - always available in Java, but a bunch of years later it doesn’t look like a good decision.
  7. copying objects - always possible in java (including copying references to objects), but for example not always available in C++.
  8. assigning an object somewhere - can be forbidden in C++ and Rust.
  9. taking a reference to an object - impossible for primitive types in Java.
  10. storing a reference to an object - limited in Rust by lifetimes.
  11. explicitly deleting an object: usually GC languages give no such guarantees. If you want to delete - you make some method that puts the object into some “terminal” state, but there’s no control over how much longer the object will exist.

Coroutines

Done differently in different languages.

Coroutines aren’t about multithreading, they’re about the ability to control the flow of execution - suspend, resume, cancel. And it’s these abilities that allow (but don’t oblige) you to use multithreading.

In my opinion the main problem: “function coloring”. From a coroutine function you can call any function, but from an ordinary function you can’t call a coroutine one. Some special way to call a coroutine from ordinary code gets made and you have to use only that. As a result the language’s syntax, type system and so on get more complicated, instead of one kind of function there are now two.

In kotlin the compiler turns a coroutine’s code into a state machine (inside there’s an int label for storing the state number and a switch over all the possible states). A call to a suspend function can return a special object kotlin.coroutines.intrinsics.COROUTINE_SUSPENDED, from which the caller understands that the computation hasn’t finished yet and also returns COROUTINE_SUSPENDED further up. A coroutine isn’t about multithreading, it’s about controlling the flow of execution, everything can work just fine in a single thread too.

An interesting point: in Python coroutines and generators are done differently. In Kotlin they’re one and the same entity. On top of that, coroutines in kotlin aren’t nailed to the language, you can write some implementation of your own, for example your own class for sequence or for some coroutine model of your own. An example of such a homemade class

Continuations

A very powerful mechanism that in theory lets you emulate exceptions, and coroutines, and algebraic effects. If you go into pure fp with immutable objects, you can also make a continuation that can be called several times, continuing one and the same computation.

In Kotlin they decided that full support isn’t needed and that supposedly a one-shot continuation is perfectly fine for most uses in coroutines. To call a continuation multiple times you’d have to clone the coroutine’s state, because it’s mutable.

Same in OCaml.

Constness and generics

C++ has an interesting thing - there are const-qualifiers for methods. Methods with it can’t change the object. Other languages sometimes lack this ability.

But this constness can also be done through templates, and not as “all or nothing”, but more carefully.

Let’s imagine we have types: ConstValue :> Value. ConstValue has only non-mutating methods, Value is its subtype with methods that change the state.

Suppose there’s a type

class Pair[+T1, +T2](val first: T1, val second: T2)

Since Value is a subtype of ConstValue, we can say that Pair[Value, Value] is a subtype of Pair[ConstValue, ConstValue].

But the coolest part - the types Pair[Value, ConstValue] and Pair[ConstValue, Value] are also possible, you get fine-grained control over which part of the object can be changed and which can’t.

Pure functions and side effects

In my opinion Haskell does it very beautifully - side effects are done through monads, and from the function signature it’s immediately clear whether the function is pure or not. I think this approach is stricter and more beautiful, but most languages don’t have it.

Abstract model vs low-level code

Somewhere there’s a note by Linus that C doesn’t need bool, and you should honestly return a byte or a char, because that’s exactly what the processor does.

On the other side are languages like Haskell, where the declarative description is everything, and no attention at all is paid to the low-level implementation.

And stuck somewhere in the middle are various languages like C++, which have both low-level details and the ability to describe abstract high-level entities. And, unfortunately, this leads to problems - low-level details stick out of various places and don’t let you use the abstractions. For example, fields in a struct are laid out in the order they’re declared. As a result, because of field alignment the struct may turn out bigger than necessary, and the programmer swaps the fields around by hand.

I don’t have a clear understanding yet of how it should be done, but it seems that the “abstract model” and “the way objects are laid out in memory and compiled to code” should be separated. Maybe leave some hints for the compiler or describe such details separately. And not everywhere on a mandatory basis, but only where it matters.

Data-oriented design

Modern processors keep getting more powerful, while memory isn’t speeding up so radically. Bandwidth grows, but latency doesn’t really improve. You can’t cheat the speed of light, in one cycle at 3 GHz light travels ten centimeters.

It’s possible that a modern programming language should give convenient control over the placement of objects in memory and the effect of this will be much better than from some clever compiler optimizations. It may be that even an interpreted language with a data-oriented approach could show very good performance, comparable to a compiled language. An example would be the numpy library for Python - a convenient interface on the outside, a CPU-optimal layout of multidimensional tensors on the inside.

And overall it’s possible that the type system should be developed not so much toward some compiler trickery, but toward a more convenient and expressive description of bytes laid out in memory. And interfaces for calling from language to language are maybe better developed in the same direction - just lay out the data and call a function with a pointer to it. Roughly like in protobuf, but without the serialization losses.

I’m partly inspired by this video: https://youtu.be/rX0ItVEVjHc, it turns out memory access is really very slow and a bad data layout will lead to 90% of the time being spent waiting, and no super-optimal compiler will be able to improve that.

JIT and inlining code on the fly

There’s the Truffle framework, and truffle-ruby on it runs about four times faster than the standard Ruby virtual machine. How did that happen? Like this - the developers write an interpreter of the language in java (and not even a complex virtual machine, just AST evaluation), put a bunch of all sorts of annotations around, and then the JIT gets down to business and aggressively inlines everything, including the interpreter’s actions.

The idea is very beautiful, the implementation - not so much. First, you have to put just a ton of non-obvious annotations and follow some rules. Second, the authors have an example - simpleLanguage, but it takes up several tens of thousands of lines. I don’t mind, but I haven’t really seen any truly simple examples. Third - it’s still tailored to some execution model, and if you try, for example, to interpret assembly this way, the result will be many times slower than the original code. Fourth - you have to profile all of this, look at where the JIT didn’t cope and somehow change the interpreter’s description so that the JIT kicks in. This requires a deep understanding of what’s going on.

As for the beauty of the idea - in theory, you can even call such code from java and vice versa and generally mix languages with each other arbitrarily. The developers even wrote an experimental java interpreter. For example, in theory you can run java 7 or java 24 interpreters this way on a virtual machine with, say, java 22. In practice such interpretation is several times slower than just a jvm with java - I hope it gets better in the future.

The best description I’ve found is this series of articles: https://www.endoflineblog.com/graal-truffle-tutorial-part-1-setup-nodes-calltarget. The only problem is that it has 16 parts and the author has been writing them for 5 years already. And that’s not because the author writes slowly - no, it’s just that truffle requires you to implement the language interpreter as a rather convoluted model with a bunch of nuances.

Approaches to garbage collection and object deletion

  1. Dump everything on the programmer (assembly, C)
  2. Dump everything on the type system and the programmer (RAII in C++, Rust) - fine, but doesn’t fit all scenarios.
  3. Reference counting - if the code is multithreaded, you need synchronization on every acquire/release of a reference. Doesn’t save you from circular references (Swift)
  4. Custom allocators - depend heavily on the scenario, let you sacrifice something for the sake of performance. For example, give up destructors and free an arena of objects in one fell swoop (For example, the bump allocator in das lang).

GC languages stand apart, because there’s a whole bunch of different GCs with all sorts of different properties.

Potentially GCs let you move objects in the heap, compacting them. A GC can be multithreaded, when the GC runs in its own thread and marks/frees objects, almost without getting in the way of other threads. Because a GC can move objects, nothing stops you from giving each thread its own area for new objects and making lots of objects on the cheap.

Variations - the actor model (Erlang, Pony), when messages are tossed between actors and the garbage collector somehow takes this model into account. For example, it runs for one actor’s objects without getting in the way of all the other actors.

Cons - it’s very hard to “marry” two different languages with different GCs to each other. (For example, Python and Lua with each other) Circular references become possible and there are also restrictions on how one GC can move objects, because objects from the second language may refer to them.

A list of interesting programming languages