Spring 2025 Programming Languages Homework 3 Solutions This homework includes an ML programming assignment and short answer questions You should use Standard ML of New Jersey SML for the programming portion of the assignment Due Tuesday April 15 2025 at 11 59 PM Eastern Time Submit two files a PDF netid hw3 pdf containing your solution to the short answer questions and another file netid hw3 sml containing solutions to all of the ML questions Late submissions are not accepted No exceptions will be made For the ML portion of the assignment do not use imperative features such as assignment references keyword ref or any mutable data structure such as Array Stick to the feature set discussed in the lecture slides You may use any published ML references to learn the language In particular the book Elements of ML Programming by Jeffrey Ullman is highly recommended reading for the newcomer to ML You may call any functions that are either used or defined in the lecture slides without citing them Otherwise all homework solutions including algorithmic details comments specific approaches used actual ML code etc must be yours alone Plagiarism of any kind will not be tolerated There are 100 possible points For the ML question you will be graded primarily on compliance with all requirements However some portion of the grade will also be dedicated to readability succinctness of the solution use of comments and overall programming style Please see http www smlnj org doc errors html for information on common ML errors Look in this document first to resolve any queries concerning errors before you ask someone else 1 1 5 points Garbage Collection 1 before a garbage collection is invoked Assuming the Mark Sweep garbage collection The above represents the heap space just 1 1 Draw the heap after mark step has been completed Clearly mark all the cells as per the algorithm mentioned in the lecture slides Assume the root pointers are processed from top to bottom Page 2 ABCDEFGHRoots 1 2 Draw the heap after the garbage collection is complete indicating the objects that are live Also construct the free list resulting from the garbage collection Assume the free list is empty before the GC executes Free list A C Page 3 ABCDEFGHRoots01101111BDEFGHRoots000000 2 10 points Garbage Collection 2 Consider the following Java code snippet Main java public class Main public static void main String args Car myCar new Car new Engine new Transmission Driver d new Driver myCar myCar Reconfigure myCar null d Drive System out println GC checkpoint 1 Here is the definition of class Car Car java public class Car private Wheel w1 w2 w3 w4 private Transmission tr public Car Engine pe Transmission pt w1 w2 new Wheel w3 w4 new Wheel pe Start tr pt tr ChangeGear 1 public void Reconfigure w2 null w4 null Here is the definition of class Driver Driver java public class Driver private Car c public Driver Car pc c pc Page 4 public void Drive Miscellaneous classes public class Wheel public Wheel public class Engine public void Start public class Transmission public void ChangeGear int x Note that the new operator is a two step operator first memory is allocated for the object and then the appropriate constructor is executed Assume outbound references are processed in the order listed in the program text from left to right top to bottom For example in class Car the order would be w1 w2 w3 w4 and finally tr With respect to the copy collection algorithm discussed in class please answer the following questions 1 Let s warm up first Identify the roots of at the time GC checkpoint 1 is printed in the Main method That is write the names of the variables args if not null and d 2 Now identify the roots of at the time ChangeGear is executing in the Car constructor Again just the names Disregard the hardware registers args if not null the current Car object this pe pt 3 Draw the state of the FROM SPACE before copy collection begins at the place GC checkpoint 1 is printed Write the class names of the objects in the correct order draw arrows denoting the outbound references along with the names of the variable s providing the outbound references and draw the roots pointing into the heap Page 5 We assume that args is null and therefore not a root Your solution is not required to have this root but it may 4 Assuming copy collection runs on the line labeled GC checkpoint 1 are any objects collected If so which objects No need for pictures diagrams on this question Yes Engine 5 Now draw the state of TO SPACE at the conclusion of copy collection before the space names are swapped As before write the class names of the objects in the correct order draw arrows denoting the outbound references along with the names of the variable s providing the outbound references and draw the roots pointing into the heap Page 6 CarEngineTrans WheelWheelDriverRootsw1w3ctrFROM SPACE before GC executes Page 7 DriverCarWheelWheelTransm Rootsw3w1cTO SPACE before spaces swappedtr 3 15 points Memory Allocation Consider a free list 10 8 16 20 5 and a sequence of allocation requests 8 8 10 10 10 Among the first fit best fit and worst fit algorithms do any of these algorithms perform any better than the others in terms of their ability to satisfy all requests First fit and best fit can satisfy the requests whereas worst fit cannot First fit free list 2 6 5 Best fit free list 2 6 5 Worst fit free list 8 8 2 5 cannot satisfy Under the assumption of a single block of free memory to start would it be possible to reliably achieve constant time allocation until memory is exhausted using one of first fit best fit or worst fit Explain Yes under worst fit The single block of free memory will serve as the one and only entry on the free list We will chip memory from this large block until there is no memory left If however the scenario allows blocks to be freed and returned to the free list i e fragmentation occurs then none of first fit best fit or worst fit can guarantee constant time allocation due to the need to search or manage multiple free blocks and fragmentation For each of the following come up with a free list minimum 3 non zero entries and sequence of allocation requests minimum 3 non zero requests that will result in the following outcomes you are allowed to create a different free list as well as different allocation requests in each part 3 1 Best fit allocation can satisfy all requests but First fit and Worst fit cannot 3 2 First fit allocation can satisfy all requests but