In which language is KSP programmed

KSP task 8

Equip your VM with a compacting garbage collector according to the "Stop & Copy" method!


1. When the program starts, create the stack dynamically with malloc (). Provide a command line option "--stack n", which provides a stack with n KiB (ATTENTION: n * 1024 bytes, NOT stack slots, NOT n * 1000 bytes). The default value should be n = 64 if this command line option is not specified. Note: You may have to adapt your test to stack overflow!

2. When the program starts, use malloc () to dynamically create your own heap, the size of which can be specified with the command line option "--heap n". Here n should be the total size of the heap in KiB (ATTENTION: n * 1024 bytes, NOT n * 1000 bytes). The default value should be n = 8192 if this command line option is not specified.

3. Divide the heap into two equally sized halves. Modify the creation of objects so that you continuously take the required storage space from half of the heap. Abort your program when half of it is exhausted.

Garbage collector

1. Program a compacting garbage collector according to the "Stop & Copy" procedure which, instead of terminating the program, carries out a collection run. If there is still not enough space for the requested allocation after the run, your VM should terminate with a suitable error message. Notes: The second highest bit of the "size" component can be used very well as the "Broken Heart Flag". The actual "forward pointer" (= byte offset in the target half-memory, where the copied object is located) occupies the remaining 30 bits. This works without any problems, since the "size" component is no longer required for objects that have already been copied. The pointers to the "root objects" can be found in all places in our VM that hold object references: the static data area, the return value register, those stack slots that refer to objects, and - don't forget! - the four components of the big integer processor "bip".

2. Since it is easy to forget a pointer to be tracked when integrating a garbage collector, provide a command line option "--gcpurge" which causes the old half-memory to be overwritten with zeros immediately after a collective run. This should make mistakes of the type mentioned more noticeable.

3. Instrument your garbage collector so that the following values ​​are displayed with the command line option "--gcstats" during the collective run: number of objects created since the last run (and the number of bytes occupied by them), number of living objects ( as well as the number of bytes occupied by it), free space after the collective run (bytes in the currently used half memory). After executing the "halt" instruction, you should explicitly call the garbage collector once so that you can get this statistical information even for small programs with little memory requirement that would otherwise not trigger the GC.

4. The set of instructions is unchanged from Exercise 7; the compiler and assembler also remain exactly the same (except for the version numbers).

5. Here is the final version of the reference implementation:

Test programs

Your VM must execute the following two somewhat larger test programs (with different heap sizes) without errors; then with a good probability it will also be accepted as homework.

Factoring large numbers

This ninja program helps to answer the following question: Given are the numbers 10 ^ n + 1 (n = 1..30). What are the prime factors of each number?

Note: A distinction must be made here between tests for composition, proofs of primality and methods of factorization. There are different algorithms in each of the three areas. A good book that covers these subjects is [Henry Cohen: A Course in Computational Algebraic Number Theory, Springer 1993].

A small computer algebra system

At their core, computer algebra systems are often implemented as an interpreter in a LISP-like language. Therefore njlisp is made available here, a re-implementation of the old muLISP-80 system in Ninja. The Makefile is used for assembling and running. Since the system is interpreted on several levels and these interpreters must all be loaded, a brief explanation of the Makefile targets follows, each together with a small example:

1) "make": creates the binary file njlisp.bin.

2) "make run": lets njlisp run. Try as inputs:
a) (PLUS 3 4)
b) (TIMES (PLUS 3 4) (DIFFERENCE 10 7))
d) (SQUARE 12345)

3) "make musimp": runs njlisp and loads the LISP program musimp.lsp, which allows the mathematical notation of expressions and provides its own programming language (with a more appealing syntax than LISP). Inputs are then expected interactively, which are calculated and output. Try as inputs:
a) 123456789 * 987654321;
b) 1-2 * 3 + 4 * 5;
c) FUNCTION F (N), WHEN N = 0 OR N = 1, N EXIT, F (N-1) + F (N-2) ENDFUN;
d) F (10);
e) FUNCTION G (N), A: 0, B: 1, LOOP WHEN N = 0, A EXIT, H: A + B, A: B, B: H, N: N-1 ENDLOOP ENDFUN;
f) G (100);

4) "make mumath": loads the math modules arith.mus (rational arithmetic) and algebra.ari (elementary algebra) after musimp.lsp. Try as inputs:
a) 5/9 + 7/12;
b) ((236 - 3 * 127) * -13) ^ 16;
c) GCD (861, 1827);
d) (-24) ^ (1/3);
e) (-4) ^ (1/2);
f) #E ^ (3 * #I * #PI / 2);
g) 5 * X ^ 2 / X - 3 * X ^ 1;
h) (5 * X) ^ 3 / X;
i) EXPD ((3 * Y ^ 2-2 * Y + 5) ^ 3);
j) FCTR (6 * X ^ 2 * Y - 4 * X * Y ^ 2 / Z);

Comment: This is only a small part of the functional scope of the system at that time, which ran on microcomputers with a maximum of 64 KiB (!) Main memory. There were around 15 packages (such as the arith.mus and algebra.ari used above) that could solve tasks from the areas of matrices, equations, trigonometry, logarithms, differential and integral calculus, as well as summation and limit value formation.