10 Homework 11
This assignment is due Thursday, 3/27 by MIDNIGHT
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW11 assignment on Gradescope. This page has additional information, and allows us to format things nicely.
10.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.
10.2 Our Representation of Memory
In this assignment, we will model our memory as a list of Cells, 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 simplified model for memory in two ways:
1. We do not have numeric addresses for Cells, 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 Cells 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-mutable-struct cell (free? value)) |
| (define-contract Cell (Struct cell [Boolean Any])) |
| (define-mutable-struct memory (pos cells)) |
| (define-contract Memory (Struct memory [Natural (List Cell)])) |
| (define MEMORY |
| (make-memory 0 (build-list 100 (lambda (_) (make-cell #t 0))))) |
| ; helper provided in case you need to know size |
| (define (memorysize) |
| (length (memory-cells MEMORY))) |
10.3 Problem 0
In order to make it easier (or even possible) to test functions throughout the rest of the assignment, your first task is to write a helper function that allows you to run a block of code using a particular MEMORY. Since MEMORY is a global variable, this function should store the current value of it, then replace it with the given argument, run the block of code (provided as a zero-argument function), and then restore the previous version of MEMORY. The signature of this function is provided for you.
| (: with-memory (-> Memory (-> Any) Any)) |
| (define (with-memory M thnk) |
| ...) |
10.4 Problem 1
The first actual 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) Cells, and mutating them when they need to be changed.
| (: malloc (-> (Maybe Cell))) |
| (define (malloc) |
| ...) |
10.5 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.
10.6 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) |
| ...) |
10.7 Problem 4
Now we’d like you to use your memory allocator – i.e., your functions malloc and free to implement an imperative "sum" function (do not directly access MEMORY). i.e., it should take a number n as input and it should add up the numbers 0,1,2,...,n, or return #f if there was not enough free memory to perform the computation. Note that you may not use a closed form solution for this – we want you to instead, use the imperative for-loop helper that we have given you, 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 strictly less that the bound. Each iteration idx is incremented and the total is updated. So the index should count up, and there should be a separate cell which accumulates the total.
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 sum. You can do it however you’d like, but it must be imperative (no helper functions aside from for-loop). Be sure to check that you get memory back, and be sure to free at the end.
| (: sum (-> Natural (Maybe Natural))) |
| (define (sum n) |
| ...) |
10.8 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 Cells. 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.
10.9 Problem 6
One property that is not captured by your invariant in the previous problem is the idea of a memory leak. i.e., that you allocated memory that you never freed! You may have had bugs like that in your implementation of sum!
In order to identify if a given piece of code is leak-free (which is what tools like Valgrind can do, among other things), implement the following function that ensures that after running the given zero argument function, the same amount of memory is free as before. Note that this does not return the value of your function, only whether there is no memory leak.
NOTE: you are only concerned about the total amount of memory in this – do not worry about the identity of particular cells.
| (: leak-free? (-> (-> Any) Boolean)) |
| (define (leak-free? thnk) |
| ...) |