Skip to main content
PRL Project

An Introduction to Region Inference

by David Walker


Type-safe languages such as ML or Java offer extraordinary software engineering advantages over "uncivilized" languages like C. The compile-time checking provided by these languages allows programmers to detect their errors much earlier in the software development cycle and can lead to tremendous gains in productivity.

Then why do so many programmers continue to work in the stone age?

One technical reason for preferring a programming language like C over ML is that it gives programmers much more control over memory management. In C, you can explicitly "free" an object, returning the memory used to store the object to the system so it can be reused. Unfortunately, type-safe languages like ML and Java do not allow explicit deallocation of memory; they typically rely on a garbage collector, which *implicitly* recycles memory locations when it is safe to so.

In this talk, I will introduce you to region-based memory management, which has been developed by Mads Tofte, Jean-Pierre Talpin, and others at DIKU. In this memory management scheme, all values are placed into one of many regions (storage areas). Regions are allocated and explicitly deallocated. When a region is deallocated, all the storage used for that region is reclaimed (and the values stored there can no longer be used). It has several advantages over other forms of memory management. Here are two:

- allocation and deallocation of objects is explicit in a region-annotated program. Because the lifetimes of objects are represented explicitly in programs, there is some hope that users (Nuprl?) may be able to reason about the space complexity of programs.

- there is a sound region-based type system that ensures programs will not deallocate regions too early. Therefore, programmers do not have to worry about dereferencing dangling pointers. Programmers have all of software engineering advantages of type-safe languages with (some) of the control of languages that allow explicit allocation and deallocation.


Mads Tofte's introduction to region inference

Further reading on region inference and links to the ML Kit with regions compiler

Summer School on Region Inference