17 Homework 11A
Due:
Tuesday, 3/26 at 9PM
This assignment may be done with an approved PARTNER.
This assignment is entirely AUTOGRADED.
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW11A assignment on Gradescope. This page has additional information, and allows us to format things nicely.
17.1 Manual Memory Management
Manual memory management refers to systems where the allocation and disposal of space for program values must be done by the programmer. This is in contrast to systems (and languages) where space for values is automatically created (when, for example, objects are created) and the space is automatically freed when all references to the objects are no longer present in the program (this is typically called garbage collection, though there are various techniques for accomplishing this, some with different names).
It is hard to perform this with complete accuracy, because mistakes can often go unnoticed. For example, forgetting to free memory will cause "memory leaks", i.e., the program consumes more memory than is needed, but that doesn’t show up in any one place, and can be difficult to debug, as it is an absense of a deallocation (or free), rather than a presence of some problem.
Even more insidiously are aliasing problems that show up, where one piece of memory is used in multiple places, possibly for different purposes. This can also happen if memory is used without being initialized: then old values, from when the memory was last used (which, in general, may be nondeterministic), will cause corruption that may not be detected until much later in the program than the actual failure to initialize.
This just scratches the surface, but describe some of the problems that we’ll see in the simulated memory system you’l be building in this assignment. In all of these cases, the problem is that the bugs that arise are not actual program errors that originate at the source of the problem. In many cases, the only way to notice anything is wrong is that the result of the program is wrong. If you find yourself debugging these types of problems, you will pine for errors that highlight the source of a problem!
While only a few languages use manual memory management exclusively, with C being the primary one, some of the challenges that it provides persist even outside of that context, since manual control over resource allocation and disposal is pervasive in high performance systems.
For example, many languages which use garbage collection by default offer mechanisms to provide manual access to memory for certain high performance purposes. Additionally, reasoning about resources like files or even records in a program can require some of the same techniques if they involve creation, deletion, aliasing, initialization, and mutation.
17.2 Our Representation of Memory
In this assignment, we will model our memory as a list of Cell~s, where a Cell~ has two fields: one that is a Boolean that indicates if it is free (or unallocated), and one that contains the value itself.
This is a simplied model for memory in two ways:
1. We do not have numeric addresses for Cell~s, and as a result, cannot do pointer arithmetic (this is a feature in C/C++ that allows you to leverage the fact that pointers are numbers to add a number to one pointer to get to another pointer). There is no way to allocate an array (since all values are independent), or to iterate from Cell~ to Cell~.
2. A Cell~ can store an LSL value of any size.
Nevertheless, we will still be able to learn a lot from this model that directly translates to either programming in systems that involve manual management of memory or other resources, or building more faithful models of the same.
We represent our Memory~ as the following, noting we have only a single, global, Memory~. It stores both the list of Cell~s and an index of the next available free? cell. Assuming this index isn’t greater than the length of the cells, this means that (list-ref (memory-cells MEMORY) (memory-pos MEMORY)) should return a free? cell.
This is an invariant that your program should mantain: it is not ensured by the Memory~ contract.
| (define-struct cell (free? value)) |
| (define-contract Cell~ (Cell Boolean Any)) |
| (define-struct memory (pos cells)) |
| (define-contract Memory~ (Memory Natural (List Cell~))) |
| (define MEMORYSIZE 100) |
| (define MEMORY |
| (make-memory 0 (build-list MEMORYSIZE (lambda (_) (make-cell #t 0))))) |
17.3 Problem 1
The first task that you have is to implement malloc, which stands for "memory allocate". This should return a Maybe Cell~ – i.e., if there is a Cell~ with the free? field set to #t, it should return it, otherwise, it should return #f. Note that it should first try to use the memory-pos field to return the "next" free cell, and only if that is beyond the bounds should it fall back to scanning through the whole list to see if there are any free? cells mixed earlier into the list.
Before returning the Cell~, it should use set-cell-free?! to update the free? field to be #f, and you should also use set-memory-pos! to update the position of the next free Cell~ in MEMORY.
IMPORTANT: no where in the code you write should you ever have a call to make-cell. The entire idea of manual memory management is that you are working with a fixed amount of memory, determined ahead of time. In our case, that is provided by the constant MEMORY, whose definition should have the only occurrences of make-cell. Your code should only be passing around (references to) Cell~s, and mutating them when they need to be changed.
| (: malloc (-> (Maybe Cell~))) |
| (define (malloc) |
| ...) |
17.4 Problem 2
How might a cell earlier in the MEMORY than (memory-pos MEMORY) be marked as free? Well, when a program is done using a Cell~, it should return it back to the pool of memory by calling free on it. Implement this function next:
| (: free (-> Cell~ False)) |
| (define (free c) |
| ...) |
This should mutate the Cell~, but not return anything, so we have this (and all other functions like that in this assignment) return #f.
17.5 Problem 3
If you think about a long running program, it will call malloc a bunch, and then it will call free on some of those values, and eventually the memory will be a mix of free and used memory. Finding a free memory cell at the end of MEMORY is easy (and, if we were using a vector or array, would be very fast), but finding free memory otherwise involves scanning through all the cells. To solve this, we’ll implement a function that "defragments" the memory by moving all the "used" cells to the beginning, all the "free" cells to the end, and setting the "pos" to be whatever value makes sense. Note: use set-memory-pos! and set-memory-cells!. As mentioned at the beginning, do not allocate new cells with make-cell, or make a new memory with make-memory.
| (: defrag (-> False)) |
| (define (defrag) |
| ...) |
17.6 Problem 4
Now we’d like you to use your memory allocator – i.e., your functions malloc and free to implement an imperative "fibonacci" function (do not directly access MEMORY). i.e., it should take a number n in and return the nth fibonacci number, or return #f if there was not enough free memory to perform the computation.
Note: the mapping your function should perform is:
(fib 0) -> returns 1 |
(fib 1) -> returns 1 |
(fib 2) -> returns 2 |
(fib 3) -> returns 3 |
(fib 4) -> returns 5 |
(fib 5) -> returns 8 |
... |
(Our tests of your code will not work otherwise...)
You’re welcome to search "imperative fibonacci" to look for reference code; we’re giving you, as support code, helpers for updating / reading the value from memory cells, and a function called for-loop that takes a Cell~ called idx that should contain a natural number, a bound, and a body (a zero-argument function) to run for as long as idx is less that the bound. Each iteration idx is incremented.
You must use for-loop and solve the problem imperatively; you may not use recursion, or define other helpers.
| (define (*= c v) |
| (set-cell-value! c v)) |
| (define (deref c) (cell-value c)) |
| (: for-loop (-> Cell~ Natural (-> Any) False)) |
| (define (for-loop idx bound body) |
| (if (>= (cell-value idx) bound) |
| #f |
| (begin (body) |
| (set-cell-value! idx (add1 (cell-value idx))) |
| (for-loop idx bound body)))) |
Now use those to implement fib. You can do it however you’d like, but it must be imperative (no helper functions aside from for-loop), and we’d recommend you use the three local variable style loop that counts up to the nth number. Be sure to check that you get memory back, and be sure to free at the end.
| (: fib (-> Natural (Maybe Natural))) |
| (define (fib n) |
| ...) |
17.7 Problem 5
You may have had bugs while you were solving Problem 4. Maybe there was something wrong with your implementation of malloc, or free. Maybe you figured them out, maybe you haven’t yet and are looking at the rest of the assignment first! Either way, there is more that we can do to reason about programs like this.
In particular, we can start to think about logical invariants that should hold of functions like malloc. One that we can encode into a contract is that malloc should never return a Cell~ that has been returned before, unless it has first been freed. How might we accomplish that?
You can add a trace contract with Record to accomplish this. First, create a list that will be all the currently allocated Cell~s. Then, on the output of malloc, if the Cell~ that is being returned is already in that list, return a non-list value, as that will cause a contract violation and halt the program.
How do you know if it hasn’t been allocated? By using eq?, you can compare for memory identity, rather that value identity. If it is not in the list, it should be added. Then, on free, add a contract with Record on the input that removes the Cell~ from the allocated list. Also, make sure that a Cell~ is not freed multiple times.
17.8 Closing Thoughts
There are certainly other logical invariants that you might want to hold of a memory allocator! For example, one very commonly used tool when programming/debugging C programs is called Valgrind, and it will (usually) detect if there are memory leaks; it does this by dynamic instrumentation, along the lines of the techniques in this class. With your allocator above, you could write a function ensure-no-leaks that wrapped a function (say, an (-> X Y)) and returned the result, but made sure that the amount of free memory at the end was the same as at the beginning (i.e., no memory was leaked).