GATE CS 2008 Q54 — Runtime Environments

To determine which statements are true, let us analyze each one individually:

• Statement I: "A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation"
  False. Recursion requires multiple instances of the same function to be active simultaneously. Under static allocation, only a single activation record is allocated per function. Thus, recursion cannot be supported using static storage allocation; it requires dynamic stack allocation.


• Statement II: "Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions"
  True. Access links (or displays) are used to access non-local variables in lexically nested scopes. If a language does not support nested procedures, any non-local variable must be a global variable, which can be accessed directly via static addresses. Thus, access links are only needed when nesting is permitted.


• Statement III: "Recursion in programming languages cannot be implemented with dynamic storage allocation"
  False. Recursion is standardly implemented using dynamic stack-based storage allocation.


• Statement IV: "Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records"
  False. Both recursion and nested procedures can be fully implemented using a stack-based allocation scheme (with the help of access links or displays on the stack). Heap allocation is not required for these features.


• Statement V: "Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records"
  True. When a function returns a nested function (forming a closure), the returned function may still reference variables belonging to the outer function. If a stack-based scheme is used, the outer function's activation record is destroyed as soon as it returns, leaving dangling references. Therefore, a heap-based allocation scheme is required to keep the activation record alive.

Since only statements II and V are true, the correct option is A.