Spring 2026 Programming Languages Homework 2 cid 136 Due on Sunday March 1 2026 at 11 59 PM Eastern Standard Time EST cid 136 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 cid 136 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 cid 136 Do not collaborate with any person or outside resources e g ChatGPT or similar for the purposes of answering speci c homework questions You may of course consult resources for the purposes of learning more about the subject matter generally Please note that additional resources have been added to the course page for this purpose including a lambda calculus tutorial cid 136 Use the Racket Scheme interpreter for the programming portion of the assignment The Racket inter preter contains interpreters for several Scheme like languages The default language is Racket which is not the language we are interested in The language you want is R5RS which is named after the Scheme language standard of the same name Important Be sure to select R5RS from the language menu before beginning the assignment You should also write lang r5rs at the top of any source les you write to con rm that R5RS is indeed the interpreter being used You can save your Scheme code to an rkt le by selecting Save De nitions from the File menu Be sure to comment your code appropriately and submit the rkt le cid 136 When you re ready to submit your homework upload a single le hw2 netID zip to NYU BrightSpace The zip archive should contain two les hw2 netID pdf containing solutions to the rst four ques tions and hw2 netID rkt containing solutions to the Scheme programming question Make sure that running your rkt le in the DrRacket interpreter does not cause any errors Non compiling programs will not be graded 1 1 25 points Activation Records and Lifetimes The questions below are free thought questions which do not necessarily have a single correct answer Rather they allow you to problem solve in an unstructured way All of these questions center around the runtime stack and activation records Your task is to take what you know from class about the runtime stack and reason about what is possible to achieve under various assumptions In some cases a particular outcome may be possible to achieve but it may not be practical We stop short of requiring a formal proof that something may be impossible or impractical but we nevertheless require that you provide reasoning behind your conclusions In other words we are asking for your educated opinion Your answers are likely and expected to be di erent and unique than any other person s answer 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 speci ed 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 by the foo subprogram Although the behavior appears the same in these two examples there is one fundamental di erence 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 speci ed variable 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 Assume that the subprogram being called must statically declare what the return type will be and that the caller must pass a variable of exactly that type 2 Consider a programming language NoRec In this language programmers are not allowed to write programs with recursion This includes both direct recursion where a subprogram calls itself directly or indirect recursion where a subprogram calls other routines which in turn call the original subprogram For example the call chain f g f is indirectly recursive Now consider how this rule may be enforced Do you think it could be enforced statically If so how If not why not What about dynamically Can it be enforced at runtime If so how If not why not In the case where static or dynamic enforcement is not possible a formal proof is not necessary Just explain your intuition and try to make your answer as concise as possible If you feel an algorithm is necessary to explain that it is possible you can explain it in words or use pseudo code if you wish Assume the language in question does not have subprogram types or pointers to subprograms That is variables that can point to or otherwise reference a subprogram We are also not concerned about performance we only wish to know whether it is possible 3 Now consider another programming language AllRec where every subprogram must terminate in a recursive call again either directly or indirectly through other subprograms Again go through the static and dynamic enforcement cases Is it possible in each case If so how If not why not No formal proof needed Page 2 2 15 points Nested Subprograms Consider the following pseudo code procedure MAIN var X integer 5 procedure OUTER SUB var A integer 2 begin INNER SUB1 X integer procedure INNER SUB1 var D integer 3 var F integer 7 X X 2 D A X print D A F INNER SUB2 end INNER SUB1 procedure INNER SUB2 var G integer 10 begin INNER SUB2 X X 1 D G 1 end INNER SUB2 begin OUTER SUB INNER SUB1 X end OUTER SUB begin OUTER SUB end MAIN Please answer the following a Write the name and evaluated actual parameter value of every subprogram that is called in the order in which each is activated up to the line marked 1 starting with a call to MAIN Assume static scoping rules apply and arguments are passed by value Note that