4. Midterm Project: Memory Allocation and Reclamation

How do we implement references and pointers in languages that do not provide them? In this project you will be developing a solution for implementing linked data structures (such as lists and queues) without relying to OCaml’s explicit ref type, by means of implementing a custom C-style memory allocator.

In order to encode the necessary machinery for dynamically creating references, we notice that one can represent a collection of similar values (e.g., of type int or string) by packaging them into arrays, so such arrays will play the role of random-access memory. For instance, two consecutive nodes with the payloads (15, "a") and (42, "b") of a doubly-linked list containing pairs of integers can be encoded by sub-segments of following three arrays: one for pointer “addresses”, one for integers, and one for strings:

A list “node” (dll_node) is simply a segment of four consecutive entries in a pointer array, with the corresponding links to an integer and a string part of the payload. Therefore, in order to work with a doubly-linked list represented via three arrays, one should manipulate with the encoding of references in by means of changing the contents of those arrays.

The template code for the project can be obtained via the link available on Canvas, In this project, you are expected to deliver the following artefacts:

• An implementation of an array-based memory allocator that can provide storage (of a fixed limited capacity) for dynamically “allocated” pointers, integers, and strings, with a possibility of updating them. Similarly to languages without automatic memory management, such as C, it should be possible to both allocate and “free” consecutive pointer segments, making it possible to reuse the memory (i.e., “reclaim” it by the allocator).

• An implementation of a doubly-linked list, built on top of the allocator interface via the abstract “heap” it provides and the operations for manipulating with the pointers. Crucially, the list should free the memory occupied by its nodes, when the nodes are explicitly removed.

• An implementation of a queue data type (taking int * string pairs), following the module signature from Section Queues and tests for checking that it indeed behaves like a queue. As your queue will not be polymorphic and only be able to accept elements of a specific type, it needs to implement a specialised signature:

  module type Queue =
  sig
    type t
    val mk_queue : int -> t
    val is_empty : t -> bool
    val is_full :  t -> bool
    val enqueue :  t -> (int * string) -> unit
    val dequeue :  t -> (int * string) option
    val queue_to_list : t -> (int * string) list
  end
  

The nature of the task imposes some restrictions and hints some observations:

• You may not use OCaml’s references (i.e., values of type ref) in your implementation.

• As you remember, pointers and arrays are somewhat similar. Specifically, most of the pointer operations expect not just the pointer p value but also a non-negative integer “offset” o, so that the considered value is located by the “address” p + o.

• The allocator only has to provide storage and the machinery to manipulate references storing (a) integers, (b) strings, and (c) pointers which can point to either of the three kinds of values. You are not expected to support references to any other composite data types (such as, e.g., pairs). However, you might need to encode those data types using consecutive pointers with offsets.

More hints on the implementation are provided in the README.md file of the repository template.

This assignment is to be completed in groups of two or three. All participants will be awarded the same grade. Feel free to think on how to split the implementation workload within your team.