Mark-and-sweep Lab
8.9.900

Mark-and-sweep Lab

Implement a simple mark-and-sweep algorithm for your Assignment 7 store.

More specifically: using the store and environment definitions from your Assignment 7 code—or the code below—implement a collect function that accepts a list of environments and a store and returns a list of the unreachable memory locations in the store.

There are many ways you could do this, but I’ll suggest one:

Hint: I strongly suggest using a piece of paper to draw an interesting and complex store that you can use for your test cases.

Here’s my A7 code, in case yours isn’t in good shape:

#lang typed/racket
 
 
;; represents an expression
(define-type ExprC (U Real Symbol String LamC AppC IfC SetC))
(struct LamC ([params : (Listof Symbol)]
              [body : ExprC]) #:transparent)
(struct AppC ([fun : ExprC]
              [args : (Listof ExprC)]) #:transparent)
(struct IfC ([test : ExprC]
             [thn : ExprC]
             [els : ExprC]) #:transparent)
(struct SetC ([var : Symbol]
              [newval : ExprC]))
(define-type PrimV (U '+ '- '* '/))
 
;; represents a value
(define-type Value (U Real Boolean String CloV PrimV
                      ArrayV))
(struct CloV ([params : (Listof Symbol)]
              [body : ExprC]
              [env : Env]))
(struct ArrayV ([addr : Address] [length : Natural])
  #:transparent)
 
;; represents an Environment
(define-type Env (HashTable Symbol Address))
 
;; represents an address
(define-type Address Natural)
 
;; represents a store
(define-type Store (Mutable-HashTable Address Value))