CSCI 330 Lab 3: macros, hash tables, and more let-over-lambda

The primary focus of lab3 is to practice creating and using macros, while the secondary focus is to gain further practice with the use of let-over-lambda and with lisp hashes.

The lab can be obtained and submitted through our usual git approach (repo name 'lab3' this time), and the starting repo contains three files: Edit: a sample run of lab3test.cl can be seen here: lab3run.txt, but hasn't been included in the pushed repo.

The memory management simulator

The simulator provides a bldMemMgr function that, using let-over-lambda, creates and returns a simple manager for a pool of memory.

The user invokes this by specirfying how big the pool is (bytes), e.g.
(defvar myMgr (bldMemMgr 1024))

The supported commands are then as follows: (using the myMgr variable for the examples) (a variety of other commands are supported by the dispatcher for the sake of unit testing)

Chunk rounding:

The manager assumes the minimal allocatable chunk of memory is 32 bytes, so rounds the initial memory pool size and all requested chunks up to the nearest multiple of 32.

How the simulator works:

The simulator maintains a hash table that maps all the chunks in memory, using the chunk's memory address as the key and with a list as the associated value. The list elements are the chunks address, size, and t/nil to indicate is the chunk taken/not. (The table starts with a single big free chunk of the chosen memory pool size.)

The simulator maintains a binary search tree recording all the free chunks in memory, where each node in the tree is a list of four elements: address, size, left subtree, right subtree. (The tree starts with a single node representing the initial big free chunk for all of memory.)

The simulator handles requests by searching the tree for the smallest free chunk that is big enough to satisfy the request, splitting off any unused extra portion into a new chunk, and updating the hash table and the tree.

For handling freeing of a chunk, the simulator checks to see if the next chunk in memory is also free and consolidates the two of them if so, then updates the hash table and the tree. (It does not currently consolidate with the preceeding chunk however.)

The implementation

The implementation in lab3fun.cl is, in theory, complete and working (other than the note above about free failing to consolidate a just-released chunk with a free chunk immediately preceeding it in memory). The lab3fun.cl file is fairly extensively commented and (minus the comments) is probably just a couple of hundred lines of lisp, but the implementation is not exactly pretty.

Please let me know as soon as possible if you do find bugs in the implementation!

Your task

For this lab your objective is to add a set of lisp macros to lab3fun.cl that make the bldMemMgr code easier to work with, and refactor the bldMemMgr code to use those macros.

A few simple starter examples would be to create named accessors for the tree nodes and chunk fields, e.g. (leftchild sometree) would replace (caddr sometree) and be would settable, i.e. you could use code like
(setf (lefchild sometree) somenewsubtree)

A sample implementation of leftchild is provided in lab3fun.cl and is used in the taken local method in bldMemMgr.

Declare all your macros near the tlop of lab3fun.cl, and with each macro provide a short note on how to use it and where/how in your refactored code it has proven useful.

Your mark will be based on the correct implementation and use of your macros and on how much they simplify coding/maintenance of the bldMemMgr function and its methods: simply doing the tree node/chunk field accessors would be regarded as a pass, but for higher marks the objective is to see and successfully implement macro syntax suited to the problem.

(Meeting the secondary goals of practice with let-over-lambda and hash tables will come through trying to understand and refactor the given implementation.)

Got a cool idea for syntax you'd like to add but can't work out a macro for it?
Add it in comments near the top of lab3fun.cl and explain what you were trying to do and where it seemed to go wrong. A key aspect of this lab is thinking about how/where macros might help, so a good idea is worth marks even if the code didn't work out in the end.
As always when working with macros, keep in mind that the macro re-writes of the source code take place at compile time, not run time, so the defmacro code doesn't have access to runtime variable/parameter content, all it can do is generate code that will give the desired behaviour at runtime.

Bonus opportunity

There's a 10% bonus if you fix the implementation to also correctly consolidate just-released chunks with immediately-preceeding free chunks (similarly to how it consolidates with immediately-following chunks), without breaking the rest of the functionality.

One suggestion would be to add an extra field to each chunk so that it knows the address of the immediately preceding chunk, just remember that if chunk A precedes B and A gets split into chunks X and Y then you need to update chunk B so it knows the altered address of its predecessor.