Implement a simple mark-and-sweep algorithm for your A4 store.
More specifically: using the store and environment definitions
from your Assignment 4 code—
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 A4 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 (HashTable Address Value))