Don't want the answers but some kind of hints would be nice!
A1.3) (33%) If we ignore closures, values in PLD LISP are numbers, symbols, Nil, or pairs. We will now look at how these can be represented in memory: A number n is represented as a 64-bit word with the value 4n + 2 (so the two last bits are 10). This limits the range of numbers to 62-bit integers. Nil is represented as a 64-bit value with the value 0, stored at index 0 in the heap. You can assume that only index 0 can have the value 0. Index 1 is not used, and can contain any non-zero value. A pair (a.b) is represented as a 64-bit value of the following form: 31 bits for the index i # 1 into the heap where a is stored, followed by 31 bits for the index j #1 into the heap where b is stored, followed by two 0-bits. So the word contains the value 233, +4j. Indices must be less than 231 and can not be equal to 1. A symbols is represented as a 64-bit word with the value 4j + 233, where j is an index into an array of characters stored outside the heap). Characters from index j up to (but not including) the next null character form the symbol. Identical symbols point to the same location. Indices are less than 231. Note that we use that index 1 is unused, so we represent a symbol as a value that would otherwise be a pair where the first element is at index 1. Note that all values are represented as 64-bit values. The representation is designed so the last bit is always 0. This allows mark-sweep collection to use this bit for marking a. Write pseudocode for a function kind that given the representation of a value returns 0 if the value is Nil, 1 if the value is a number, 2 if the value is a symbol, and 3 if the value is a pair. Use C-style notation for extracting bits. b. Write pseudocode for a function equal that by looking at their representation determines if two values are equal. Recall that PLD LISP uses deep equality, so two pairs are equal if they are constructed from the same elements, even if these elements are not stored at the same indices in the heap. Use C-style notation for extracting bits. c. Given that mark-sweep collection is used for reusing heap elements, what forms of fragmentation can occur? d. Garbage collection in the heap can leave some indices into the symbol array unused. If new symbols can be added (e.g., by reading s-expressions from a file), this can mean that the symbol array can fill up even if there are unused indices. Consider how the mark-sweep collector can be modified to also garbage-collect the symbol array. Note that garbage collection of the symbol array are expected to occur relatively seldom, so you can assume that an unmodified collector is used most of the time, so the overhead of collecting the symbol array is only incurred rarely, so efficiency is not essential. A1.3) (33%) If we ignore closures, values in PLD LISP are numbers, symbols, Nil, or pairs. We will now look at how these can be represented in memory: A number n is represented as a 64-bit word with the value 4n + 2 (so the two last bits are 10). This limits the range of numbers to 62-bit integers. Nil is represented as a 64-bit value with the value 0, stored at index 0 in the heap. You can assume that only index 0 can have the value 0. Index 1 is not used, and can contain any non-zero value. A pair (a.b) is represented as a 64-bit value of the following form: 31 bits for the index i # 1 into the heap where a is stored, followed by 31 bits for the index j #1 into the heap where b is stored, followed by two 0-bits. So the word contains the value 233, +4j. Indices must be less than 231 and can not be equal to 1. A symbols is represented as a 64-bit word with the value 4j + 233, where j is an index into an array of characters stored outside the heap). Characters from index j up to (but not including) the next null character form the symbol. Identical symbols point to the same location. Indices are less than 231. Note that we use that index 1 is unused, so we represent a symbol as a value that would otherwise be a pair where the first element is at index 1. Note that all values are represented as 64-bit values. The representation is designed so the last bit is always 0. This allows mark-sweep collection to use this bit for marking a. Write pseudocode for a function kind that given the representation of a value returns 0 if the value is Nil, 1 if the value is a number, 2 if the value is a symbol, and 3 if the value is a pair. Use C-style notation for extracting bits. b. Write pseudocode for a function equal that by looking at their representation determines if two values are equal. Recall that PLD LISP uses deep equality, so two pairs are equal if they are constructed from the same elements, even if these elements are not stored at the same indices in the heap. Use C-style notation for extracting bits. c. Given that mark-sweep collection is used for reusing heap elements, what forms of fragmentation can occur? d. Garbage collection in the heap can leave some indices into the symbol array unused. If new symbols can be added (e.g., by reading s-expressions from a file), this can mean that the symbol array can fill up even if there are unused indices. Consider how the mark-sweep collector can be modified to also garbage-collect the symbol array. Note that garbage collection of the symbol array are expected to occur relatively seldom, so you can assume that an unmodified collector is used most of the time, so the overhead of collecting the symbol array is only incurred rarely, so efficiency is not essential
