[go-nuts] Creating a garbage collector in a garbage collected language

Apologies for the title. I originally was going to ask specifically about
the garbage collector, but decided to make it a bit more broad.

If I remember correctly, some parts of the runtime are compiled with a flag
that "disables" the GC and lets you allocate things only on the stack. Then
I assume that the Go memory allocator does some system call to allocate
memory when necessary.

From https://golang.org/pkg/runtime/ :
"Setting GOGC=off disables the garbage collector entirely."

If you are careful, you can write Go such that it avoids requiring any
runtime facilities. The runtime package is carefully written in this
way. It is helped by an undocumented compiler flag that gives an
error in certain cases, such as implicitly allocating memory.

Ian

If we bend the concept of "a constant overhead" in Kolmogorov complexity a
little bit, it can be said that every universal programming language P1
differs from another universal programming language P2 by a constant.
Universality just means that a Turing machine can be implemented both in P1
and P2. The "constant" by which P1 differs from P2 is the length of the
source code written in P1 which implements an interpreter of P2 (or, if
taken in the opposite direction, the length of an interpreter of P1
implemented in P2). The interpreters are written by hand.

This relationship between P1 and P2 can be taken advantage of, when writing
a compiler or a VM, if P2 is a simpler language than P1. The term "simpler"
usually means that P2 is more amenable to direct execution than P1. Going
one step further, P2 can be implemented in P3 which is simpler than P2.

A concrete example: P1=Python, P2=C, P3=assembly.

It is impossible to do the following: Introduce a new language P1, write an
interpreter of P1 in P1 itself, have the interpreter of P1 (written in P1)
use all language features of P1, and execute this interpreter by a machine
- because such a machine does not exist yet. If it was possible, it would
defy causality. However, one can select a proper subset of P1 - let's give
this proper subset the following name: P2 - and if P2 is still a universal
programming language we can write an interpreter of P1 in P2. Since P2 is a
proper subset of P1's features, it is simpler to write an interpreter of P2
by hand in P3 or to design a machine that can execute P2. It this isn't
viable for P2, it may be viable for P3. It this isn't viable for P3 because
it is still too complex, it may be viable for P4. Etc. Note that while P2
is simpler than P1, it may be the case that it runs much slower than P1.

Examples: The Squeak Smalltalk VM is written in a proper subset of
Smalltalk. There is also RPython, a subset of Python, used in the PyPy
project.

Initial x86 CPUs were just interpreters of the (relatively simple by
today's standards) x86 binary code and they have been created by hand, or
by the power of the human mind if you like.

It is a false statement that transitions from P1 to P2, P2 to P3, etc, can
completely avoid the human element.

About bootstrapping: Let's have for example P1=Python, P2=C, P3=assembly,
P4=CPU. Let's in addition assume that the assembly code is actually simpler
than C (so it isn't the bloated modern x86 assembly code). P1, P2 P3 and P4
are universal. In this scenario, the Python interpreter runs as binary code
interpreted by P4 - P1's C implementation is written in P2=C, P2's
implementation is written in P3=asm, and P3's implementation is the binary
code which can be understood by P4=CPU. Since P1=Python is universal, we
could write a full C interpreter in P1=Python and also write a full
assembly language interpreter in P1=Python. Thus, we can now stop using
(can now "delete") the legacy C interpreter which was written in assembly,
and we can also stop using the legacy assembly code interpreter written in
binary. What we however cannot delete is P4=CPU. However, what we could
also do is to write in Python an interpreter for a different assembly
language P3.1=assembly1, then write a new C interpreter P2=C in P3.1, then
continue interpretation of Python code in the Python interpreter written in
C (C running in P3.1 now), implement P3.1 in binary code which can be
understood be P4.1=CPU1, manufacture new P4.1 machines and then turn off
all P4 machines. Or instead of turning them off we could decide to keep P4
machines running alongside with the new P4.1 machines. In general,
bootstrapping means that in principle we can gradually completely replace
any Pi as long as there remain some other universal interpreters.

In the above there hasn't been a word about compilers, just interpreters.
That's understandable, since compilation doesn't bring anything
fundamentally new to the picture because it is in principle just a very
clever method of removing redundant computation from an interpreter.