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:

• Write a helper function that accepts a value and computes a list of the memory locations it refers to.

• Write a helper function that accepts an environment and computes a list of the memory locations it refers to. Be careful not to include shadowed bindings.

• Write a recursive mark function that accepts a list or set of seen memory locations and a list (representing a queue) of unexamined memory locations and a store. This function will presumably be recursive (essentially, it’s a breadth-first or depth-first search depending on whether you append the new ones to the beginning or end of the list), and should probably return a list of all the memory locations that are referred to.

• Write a sweep function that accepts a store and a list of still-used locations, and returns a list of the no-longer-referred-to locations.

• Bundle it all together into a collect function that uses the environments to compute a list of locations, feeds them into mark, and then uses sweep to determine which ones are unused

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))