Local reasoning about a copying garbage collector

Noah Torp-Smith, Lars Birkedal, John Reynolds

ACM Transactions on Programming Languages and Systems · 2008 · 23 citations · 35 references

DOIFull text

Open access

Concepts

Abstract

We present a programming language, model, and logic appropriate for implementing and reasoning about a memory management system. We state semantically what is meant by correctness of a copying garbage collector, and employ a variant of the novel separation logics to formally specify partial correctness of Cheney's copying garbage collector in our program logic. Finally, we prove that our implementation of Cheney's algorithm meets its specification using the logic we have given and auxiliary variables.

References

35