Fall 2025 Programming Languages Homework 2 Solutions Due on Sunday October 12 2025 at 11 59 PM Eastern Time ET The homework must be submitted through NYU BrightSpace do not send by email Due to timing considerations late submissions will not be accepted after the deadline above No exceptions will be made I strongly recommend that you submit your solutions well in advance of the deadline in case you have issues using the system or are unfamiliar with NYU BrightSpace Be very careful while submitting to ensure that you follow all required steps Do not collaborate with any person for the purposes of answering homework questions Use the Racket Scheme interpreter for the programming portion of the assignment Important Be sure to select R5RS from the language menu before beginning the assignment You can save your Scheme code to an rkt file by selecting Save Definitions from the File menu Be sure to comment your code appropriately and submit the rkt file When you re ready to submit your homework upload a single file hw2 netID zip to NYU BrightSpace The zip archive should contain two files hw2 netID pdf containing solutions to the first four ques tions and hw2 netID rkt containing solutions to the Scheme programming question Make sure that running your rkt file in the DrRacket interpreter does not cause any errors Non compiling programs will not be graded 1 1 25 points Activation Records and Lifetimes 1 Let s begin with a relatively easy one You are undoubtedly familiar with the concept of a return statement in many imperative languages which causes a subprogram to exit This exiting behavior is also sometimes associated with a value called a return value Normally the the subprogram call essentially becomes an expression and allows the caller to assign the return value however they wish For example x foo assigns the return value to x Consider a variation on this whereby the name of the variable accepting the return value is specified at the time of the call For example x foo would cause foo to be invoked and the return value would be stored into the variable x where x is expected to be accessible from the scope in which foo is called Although the behavior appears the same in these two examples there is one fundamental differ ence in the former example the caller is responsible for storing the return value whereas in the latter example the exiting subprogram is responsible for storing the return value into the specified variable In other words the subprogram being called is aware of where the return value is going Explain how to modify the standard activation record structure to accommodate this new feature How would the feature work Must any new information be placed onto the runtime stack If so where would it go How would the return variable be communicated to subprogram being called How would the subprogram being called store the result The caller would push the address of the specified variable onto the stack The exact location is unimportant as long as both caller and callee know where it is It will be referenceable by some fixed positive offset from the frame pointer Positive because that s where information pushed by the caller is stored If necessary the compiler can provide type enforcement i e confirm that the variable supplied by the caller is compatible with the return type Upon exiting the callee the epilogue would be responsible for dereferencing the memory address previously pushed onto the activation record and storing the return value at the memory address 2 Recall from the lecture that returning an inner subprogram from an outer subprogram1 is problem atic in stack based languages because the non local referencing environment of the inner subprogram will no longer exist at the time that inner is later invoked Slide 27 and 29 from the subprograms lecture demonstrate this issue Can you think of any ways to overcome this specific issue without utilizing the heap That is to make it so that the examples on Slides 27 and 29 execute as expected even though the language is stack based Try to come up with the most general solution possible but it s acceptable if you need to introduce restrictions on the language in order to make this work In that case describe what the restrictions are and why they are necessary This is possible provided the next subprogram to be executed after the inner subprogram is re turned is the inner subprogram itself This can be achieved for example by marking the outer subprogram s activation record as sticky so as to remain on the stack It will remain sticky as long as the inner subprogram or no subprogram is called Once a subprogram other than the inner subprogram is invoked next then the activation record is unmarked and the space is freed Here is the significance of a sticky activation record it is used during non local variable lookups whereas ordinarily it would not be either using a display or static linkage The idea is that lookups will start at the sticky record if one exists and then proceed downward in accordance with an ordinary display or static linkage lookup Special case 1 It is possible for the outer subprogram to return the inner subprogram whereby this inner subprogram is stored in a variable see Add Five on slide 27 that is later returned and passed back further to other callers This can lead to a gap of unused stack space between the sticky activation record and the topmost executing activation record on the stack The easiest solution is to require the inner subprogram to be called prior to returning or otherwise forfeit the ability to later call the inner subprogram The main concern with allowing subprograms to return before the inner subprogram is called is that another outer subprogram could return another inner subprogram lower down in the stack leading to multiple sticky activation records 1To be clear we are assuming that the inner subprogram is nested within the scope of the outer subprogram in a language that uses static scoping rules Page 2 not to mention considerable confusion both on the part of the programmer and the programming language designer Special case 2 Suppose we call inner in accordance with the restrictions above and suppose inner calls one or more other subprograms Special handling would be needed to place the new activation records above the sticky activation record Normally the new activation record would overwrite the sticky activation record A safer option is to simply prohibit the inner subprogram from